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.