An easy proof of the uncountability of bijections on natural numbers? - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-22T23:03:02Z http://mathoverflow.net/feeds/question/29475 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/29475/an-easy-proof-of-the-uncountability-of-bijections-on-natural-numbers An easy proof of the uncountability of bijections on natural numbers? Abhishek Parab 2010-06-25T06:47:53Z 2012-11-27T17:16:01Z <p>The proof that I have in mind is as follows - </p> <p>$\text{Gal }(\overline{\mathbb Q}/\mathbb Q)$ is a proper uncountable subgroup of the group of permutations on countably many symbols, hence the latter is uncountable. .</p> <p>But it needs a lot of jargon from topology and algebra. Is there a neat proof like Cantor's diagonal argument?</p> http://mathoverflow.net/questions/29475/an-easy-proof-of-the-uncountability-of-bijections-on-natural-numbers/29476#29476 Answer by Ewan Delanoy for An easy proof of the uncountability of bijections on natural numbers? Ewan Delanoy 2010-06-25T07:07:19Z 2010-06-25T07:07:19Z <p>Indeed, Cantor's argument is readily adapted. Let $\pi_1,\pi_2,\pi_3, \ldots$ be any countable sequence of permutations of $\mathbb N$ ; let us show that this sequence does not exhaust all permutations, by constructing a permutation $\pi$ different from all the $\pi_i$. We first define $\pi$ on the even integers inductively, then define $\pi$ on the odd integers.</p> <p>Let $X$ be any subset of $\mathbb N$ such that both $X$ and ${\mathbb N} \setminus X$ are infinite (e.g. the even integers, the prime numbers ...).<br> Set $\pi(0)$ to be an integer in $X$ different from $\pi_1(0)$. Set $\pi(2)$ to be an integer in $X$ not in $\lbrace \pi(0),\pi_2(2)\rbrace$. Set $\pi(4)$ to be an integer in $X$ not in $\lbrace \pi(0),\pi(2)\pi_3(4)\rbrace$. Continuing like this inductively, we define an injection from the even integers to $X$, such that $\pi(2k-2) \neq \pi_k(2k-2)$ for any $k$ (and hence $\pi \neq \pi_k$).</p> <p>Finally, the set A=${\mathbb N} \setminus \pi(2\mathbb N)$ is countably infinite ; setting $\pi(2k-1)=$ the $k$-th element of $A$ finishes the proof. </p> http://mathoverflow.net/questions/29475/an-easy-proof-of-the-uncountability-of-bijections-on-natural-numbers/29488#29488 Answer by villemoes for An easy proof of the uncountability of bijections on natural numbers? villemoes 2010-06-25T09:30:21Z 2010-06-25T09:30:21Z <p>The fact that any conditionally convergent series [and that such exists] can be rearranged to converge to any given real number $x$ proves that there is an injection $P$ from the reals to the permutations of $\mathbb{N}$. The usual proof (pick positive terms until we exceed $x$, pick negative terms until we "deceed" $x$, repeat) is constructive; if we use a series consisting of easily computable rational numbers (the alternating harmonic series being the canonical example) and a real number $x$ for which we can decide <code>$q&lt;x$</code> or <code>$q&gt;x$</code> or $q=x$ for every rational number $q$, we may compute $P(x)(n)$ for every $n$.</p> http://mathoverflow.net/questions/29475/an-easy-proof-of-the-uncountability-of-bijections-on-natural-numbers/29500#29500 Answer by Carl Mummert for An easy proof of the uncountability of bijections on natural numbers? Carl Mummert 2010-06-25T11:32:50Z 2010-06-25T13:36:10Z <p>I'm not sure what counts as an "easy" proof, but the following seems easy to me. Make a subtree of $\mathbb{N}^{&lt;\mathbb{N}}$ by declaring that a sequence $\sigma$ is in the subtree if (1) $\sigma$ is injective and (2) whenever $\sigma(2n+2)$ is defined, it is equal to the least natural number not in the range of $\sigma \upharpoonright (2n+2)$. Then any path through this tree is a bijection of $\mathbb{N}$, and the tree is perfect because any sequence of even length has infinitely many immediate extensions in the tree (any number not already in the range is a candidate). So the tree has continuum-many paths. </p> http://mathoverflow.net/questions/29475/an-easy-proof-of-the-uncountability-of-bijections-on-natural-numbers/29517#29517 Answer by Qiaochu Yuan for An easy proof of the uncountability of bijections on natural numbers? Qiaochu Yuan 2010-06-25T15:06:04Z 2010-06-25T22:08:51Z <p>Bijections of the natural numbers are equinumerous with functions $\mathbb{N} \to \mathbb{N}$, which are equinumerous with continued fraction expansions of positive irrational numbers.</p> <p><strong>Edit:</strong> Here's one proof of the first assertion. Clearly there are at most as many bijections $\mathbb{N} \to \mathbb{N}$ as functions $\mathbb{N} \to \mathbb{N}$. On the other hand, for any function $f : \mathbb{N} \to \mathbb{N}$ there exists a bijection with $f(i)$ cycles of length $i$. Now apply Cantor-Schroeder-Bernstein.</p> http://mathoverflow.net/questions/29475/an-easy-proof-of-the-uncountability-of-bijections-on-natural-numbers/29541#29541 Answer by Pete L. Clark for An easy proof of the uncountability of bijections on natural numbers? Pete L. Clark 2010-06-25T20:02:33Z 2010-06-25T20:02:33Z <p>Consider the following map $\Phi$ from bijections of the natural numbers to subsets of the natural numbers: to each bijection $\sigma$, associate its fixed point set <code>$S(\sigma) = \{x \in \mathbb{N} \ | \ \sigma(x) = x \}$</code>.</p> <p>It is easy to see that this map is almost surjective: the only subsets which are not in the image are those whose complement consists of a single element. Indeed, a subset of the natural numbers admits a fixed point free permutation iff it does not consists of a single element. In particular, the complement of the image of $\Phi$ is countable. Since the codomain of $\Phi$ is uncountable, so therefore is the image of $\Phi$. </p> <p>This shows that the set of bijections is uncountable. By the usual Schroder-Bernstein argument, it follows that it has continuum cardinality. </p> http://mathoverflow.net/questions/29475/an-easy-proof-of-the-uncountability-of-bijections-on-natural-numbers/114674#114674 Answer by Adam Kapelner for An easy proof of the uncountability of bijections on natural numbers? Adam Kapelner 2012-11-27T17:16:01Z 2012-11-27T17:16:01Z <p>I think there's an easier proof but I can't quite do every step.</p> <p>Imagine the bijection from $f : A \longrightarrow A$ where $A = \{1,2,3\}$. 1 can be mapped to 3 numbers, 2 can be mapped to the remaining 2 numbers and 3 can be mapped to 1 number. Hence the size of the size of the bijection is the factorial of the size of the set being mapped, ie $|A|!$. </p> <p>Thus, the size of the bijection $f : \mathbb{N} \longrightarrow \mathbb{N}$ should be $|\mathbb{N}|!$ which is clearly bigger than $2^{|\mathbb{N}|}$, hence it is uncountable.</p> <p>Can you let me know if this suffices?</p>