Let Gamma consist of all subsets of N Prove that Gamma is un

Let Gamma consist of all subsets of N. Prove that Gamma is uncountable. Prove that the set of all bijections f: N rightarrow N is uncountable.

Solution

13)

This can be proved by a diagonal argument. Given a sequence T = {A₁,A₂,...} of subsets of N, define a new set A by the condition that n belongs to A if and only if n does not belong to A_n. This is enough to ensure, for every n, that A does not equal A_n. Therefore A was not part of the sequence T. Hence T is uncountable.

14)

Let A₁,A₂,A₃… be any countable sequence of permutations of N; let us show that this sequence does not exhaust all permutations, by constructing a permutation A different from all the Ai. We first define A on the even integers inductively, then define A on the odd integers.

Let X be any subset of N such that both X and NX are infinite (e.g. the even integers, the prime numbers ...).

Set A(0) to be an integer in X different from A₁(0). Set A(2) to be an integer in X not in {A(0),A₂(2)}. Set A(4) to be an integer in X not in {A(0),A(2)A₃(4)}. Continuing like this inductively, we define an injection from the even integers to X, such that A(2k2) A_k(2k2) for any k (and hence A A_k).

Finally, the set S = NA(2N) is countably infinite.

setting A(2k1)= the k-th element of S finishes the proof for odd integers and also the entire proof for N.