5
$\begingroup$

Hi I would like to prove this statement.

Show that there is no one-to-one correspondence from the set of positive integers to the power set of the set of positive integers.

[Hint: Assume that there is such a one- to-one correspondence. Represent a subset of the set of positive integers as an infinite bit string with ith bit 1 if i belongs to the subset and 0 otherwise. Suppose that you can list these infinite strings in a sequence indexed by the positive integers. Construct a new bit string with its ith bit equal to the complement of the ith bit of the ith string in the list. Show that this new bit string cannot appear in the list.]

$\endgroup$
8
  • 3
    $\begingroup$ But there is such a correspondence: $n\mapsto \{n\}$. If you want to prove that there isn't any onto correspondence, then it's 'easier' to just prove it is true for all sets, i.e., it is 'easier' to prove Cantor's Theorem. $\endgroup$
    – Git Gud
    Nov 3, 2013 at 11:37
  • 3
    $\begingroup$ @GitGud Many people use the phrase "one-to-one correspondence" to mean "bijection". Probably it's best not to use the word "correspondence" at all, to avoid this type of confusion. $\endgroup$ Nov 3, 2013 at 16:12
  • $\begingroup$ @TrevorWilson: in my experience this is often a difference between UK and US usage. Through my undergrad in the UK, I only knew “one-to-one” as meaning “bijective”. It was only going to the US for grad school that I met people for whom it meant “injective”. $\endgroup$ Nov 3, 2013 at 17:08
  • 2
    $\begingroup$ @PeterLeFanuLumsdaine Ah, so "one-to-one" is also ambiguous. Because the phrase "one-to-one" is symmetric, I can see how this might suggest that it should mean something symmetric ("bijective", rather than "injective".) I suppose this is yet another reason to use the "injective", "surjective", "bijective" terminology exclusively. $\endgroup$ Nov 3, 2013 at 19:02
  • 1
    $\begingroup$ Wikipedia backs me up on this; the items at en.wikipedia.org/wiki/One-to-one#Mathematics are “• One-to-one function, also called an injective function; • One-to-one correspondence, also called a bijective function” $\endgroup$
    – MJD
    Nov 4, 2013 at 16:00

2 Answers 2

6
$\begingroup$

Let $S$ be the set of positive integers. Suppose there is a bijection $f : S \to P(S)$. Then every subset of $S$ is equal to $f(s)$ for some $s \in S$. For any $s\in S$, $f(s)$ is a subset of $S$, and it is certainly the case that either $s\in f(s)$ or $s\notin f(s)$. [For example, there exists $s_1$ such that $f(s_1)= S$, and then $s_1 \in f(s_1)$; likewise, there exists $s_2$ such that $f(s_2) = \emptyset$, and then $s_2 \notin f(s_2)$.] Define $A$ to be the set of all elements $s$ of $S$ such that $s \notin f(s)$; symbolically, $$A = \{s\in S\,|\,s \notin f(s)\}.$$

(In the above notation, $s_1 \notin A$ but $s_2 \in A$.)
Certainly $A$ is a subset of $S$; that is, $A\in P(S)$. Therefore, as $f$ is a bijection, $A = f(a)$ for some $a \in S$.
We now ask the question: does $a$ belong to $A$?
If $a \notin A$, then $a \notin f(a)$, so by definition of $A$, we have $a \in A$. This is a contradiction. And if $a \in A$ then $a \in f(a)$, so by definition of $A$ we have $a \notin A$, again a contradiction.
Thus we have reached a contradiction in any case. So we conclude that there cannot be a bijection from $S$ to $P(S)$.

$\endgroup$
3
  • $\begingroup$ But defining $A$ that way requires Unrestricted Comprehension. Basically, all this does is shows one example of a paradox that can be formed if we allow that; the only difference is that we are then using this paradox as the 'absurdum' part of a 'reducto ad absurdum'. Using the exact same reasoning in this proof, if we use $f(s) = \{s\}$, we can conclude that there is no bijection between the natural numbers and the natural numbers. How is it that we get around this issue? I would really like to know, but I have trouble understanding these apparent inconsistencies. $\endgroup$ Nov 3, 2013 at 21:25
  • $\begingroup$ @AJMansfield: The definition of $A$ above doesn’t need unrestricted comprehension; it’s a valid instance of subset separation (aka subset comprehension), since it begins $\{ s \in S\ | \ldots$, i.e. it’s defining a subset of an existing set, not a whole new set out of nowhere. Subset separation is one of the axioms of ZFC. // Re your second comment, that the same proof would show there’s no bijection between $\mathbb{N}$ and itself, I don’t follow what you’re suggesting there. $\endgroup$ Nov 3, 2013 at 22:19
  • $\begingroup$ @PeterLeFanuLumsdaine Thank you for clarifying that to me, I think I get it now that I have that issue out of the way. By the second half of my comment, I was (erroneously) saying that all the properties of A that are used in the second half are also true if we use $f(s) = \{s\}$, so the reasoning that $f$ can't exist applies to it as well. Again, thanks for the explanation. $\endgroup$ Nov 3, 2013 at 22:29
4
$\begingroup$

Hint: Let $(b_1,b_2,...,b_i,...)$ denotes a new bit string. And let $(a_{i1},a_{i2},...,a_{ii},...)$ denotes the $i$th string that corresponds to the $i$th integer. Take $b_1 \neq a_{11}$, $b_2 \neq a_{22}$, ..., $b_i \neq a_{ii}$, and so on. It's called Cantor's diagonal argument.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.