Hello, friends. As you well know, many times in math you formulate a proof that seems air-tight yet always seems to hold some infinitesimal flaw. Particularly, I have recently been reviewing some old stuff for fun and the following bothers me. I know and have been able to do the normal proofs rather easily, but the following proof to me seems simpler. Is there anything wrong with it?
Problem: Let be countable. Prove that is countable.
Lemma: is countable for any finite .
Proof: By virtue of the Schroder-Bernstein theorem we must only find an injection from to and one backwards.
For the first one, merely let be given by . To see that this is injective assume that and since a pair of -tuples are
equal only when their components are equal we see that particularly we must have that and the conclusion follows.
For an injection backwards let be the first primes and let be given by . Now suppose that
. To see that this is injective we may either use a congruence argument noting the coprimeness of all primes, or more
simply, note that the LHS and RHS of the above represent a prime factorization of the same natural number and by virtue of the FTA (particularly that prime factorizations are unique) we must have
that the exponents of each prime are equal. Thus, and the conclusion follows. .
Now, considering the problem at hand. We know that since are countable that there exists which are bijections. Therefore, define a mapping
by . To see that this is a bijeciton we first show that it is injective.
Suppose that . Now, appealing, once again, to the definition of an -tuple we see that
and since each of these functions are individually injective it follows that and the conclusion follows.
To show that is surjective let . Since and are surjective we know there exists some such that
. But from this we see that for the above that and which shows 's surjectivity.
From this we see that is a bijection, and in particulary we see that (where denotes having the same cardinal number), but from the lemma we know that and since is an equivalence relation (specifically transitive) we see that which finishes the arugment.
Is that correct? Thank you VERY much in advance for taking the time to read this.
Unless I missed something, it's correct.
But I wonder what the "normal proofs" were, as it seems to me that it's a common one you used (Surprised)
I guess that I have weird books. The books that I have on the subject seem give rather geometric argumens to prove that is countable and then use induction to prove the general case.
Originally Posted by Moo
Regardless, thank you very much Moo.