Proofy Proof: Invertibility means Bijectivity?

In class today we talked about this statement:

If f: A→B is invertible, then f is bijective.

and how exactly we would go about proving it. We figured most of it out in class:

First off, we assume that f: A→B is invertible. That means that (∃ g:B→A)(∀a∈A)((g∘f)(a) = a). We want to show that f is invertible.

Since bijective means that a function is both injective and surjective, we can prove that the function most be both in two steps.

First of all, we can prove that the function is one-to-one by contradiction. The definition of one-to-one is: (∃ a,c ∈A)(f(a)=f(c)⇒a=c), so to prove by contradiction, we’ll assume f(a) = f(c), but a≠c.

By definition, g(f(a)) = a and g(f(c)) = c, but a≠c, even though g(f(a)) = g(f(c)). ⇒⇐

So let’s try to now prove that the function must also be onto by contradiction. The definition of onto is: (∀v∈B)(∃u∈A)(f(u)=v). To prove by contradiction, we’ll assume that f(u)≠v.

By definition, g(u) = v; f(v) = u. But if this function is going from A to B, the contradiction states that no matter what element of A is put into the function, you will not get an element of B as an output. So if that is true, there is no possible way that the outputs given for the function, f, would map back to the original element. The definition relies on the fact that g(u) = v. ⇒⇐

So, since the function must be both surjective and injective, if a function If f: A→B is invertible, then f must be bijective to avoid any contradictions.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s