Showing that set is infinite iff there's a proper subset that has bijection with given set.

Question

I'm trying to solve a problem from Kenneth O. Rosen Discrete Mathematics and its Applications:

Show that set S is infinite if and only if there is a proper subset A of S such that there is one-to-one correspondence between A and S.

---

Proof:

Let $S$ be finite so it's cardinality is equal to $n$, where $n \in \mathbb{N} $. Then from the fact that $A$ is a proper subset of $S$ it follows that $|A| < n$. But since $S$ and $A$ have one-to-one correspondence $|A|=|S|=n$. Contradiction, therefore $S$ is infinite.

---

But I am not really sure if I've proven it correctly. To me it's paradoxical that a set that is smaller than it's superset can have bijection with it and I don't understand how that is possible. I did read some similar questions:

• How is there a bijection between an infinite set and a proper subset?
• Prove that a set is infinite if and only if it is equipotent to a proper subset.

But still could not understand. The book does not give notion of infinite sets at least not now.

Did I prove this problem correctly? How is it possible that a set that is smaller has all elements of its superset?

Answer 1

No, this is not a complete proof. 'If and only if'-statements are always two statements disguised as one. You need to show two directions:

• First you need to show that if $S$ is infinite, then a proper subset $A$ and a bijection from $S$ to $A$ exist.

• Then you show that if $S$ has a proper subset $A$ and a bijection $S$ to $A$, then $S$ if infinite.

Both of these statements can be proven directly or by contradiction. You have already proven the second statement.

Here you have a complete proof. The first part is your proof (slightly rephrased).

Let $S$ be a set, let $A$ be a proper subset of $S$ and $f: A \rightarrow S$ a bijection. Assume that $S$ is finite. $|A| < |S|$ holds true because $A$ is a proper subset of $S$. But since there is a bijection between $S$ and $A$, $|A|=|S|$ also holds true. So there is a contradiction, therefore $S$ must be infinite.

Now let $S$ be an infinite set. Let $T$ be an countably infinite subset of $S$. We can w.l.o.g. assume that $T = \mathbb{N}$, because for every countably infinite set there is a bijection to $\mathbb{N}$. Now let $T' = \mathbb{N} \setminus \{ 1 \}$ and $g: T' \rightarrow \mathbb{N}, n \mapsto n - 1$. $g$ is a bijection because every element of $\mathbb{N}$ has a corresponding element in $T'$ and vice versa. Now let $A = S \setminus \{ 1 \}$ and $f: A \rightarrow S, x \mapsto f(x)$, where $f(x) = g(x) = x - 1$ if $x \in T'$, otherwise $f(x) = x$. $f$ is a bijection because on $T' \subset S$ it acts like $g$ which is a bijection, on $S \setminus T'$ it is the identity and $f(A) = S$.

Did I prove this problem correctly? How is it possible that a set that is smaller has all elements of its superset?

No, this is not possible. But a one-to-one correspondence does not mean that every element in one set is also in the other. It means that you can associate every element from one set with exactly one unique element from the other set, without leaving any elements unassociated. In my proof I constructed a one-to-one correspondence between $\mathbb{N} \setminus \{ 1 \}$ and $\mathbb{N}$ via the function $n \mapsto n-1$. $\mathbb{N} \setminus \{ 1 \}$ is clearly a proper subset of $\mathbb{N}$, but still you can construct a bijection. This is a unique property of infinite sets, that does not apply to finite sets.

Answer 2

Consider the discrete case, the set of all natural numbers $N$. This set includes all integers greater than 0. Here are the first ten elements of the set: $$ N=\{1,2,3,4,5,6,7,8,9,10...\} $$ We can then remove all odd numbers to get a new set $P$: $$ P=\{2,4,6,8,10...\} $$ We only have $5$ elements now, but we can continue the pattern to get $10$. We can do this only because $|N|$ is a countable infinity. $$ P=\{2,4,6,8,10,12,14,16,18,20...\} $$ However, this result is the same as the result if all elements in $N$ were scaled by a factor of $2$. See: $$ 2N=\{2,4,6,8,10,12,14,16,18,20...\} $$ Thus, $P=2N$. However, since scaling all the elements of a set by a single (nonzero) factor does not change the cardinality, we must conclude that since $|N|=|2N|$ and $|P|=|2N|$, $|P|=|N|$.

Thus, your proof is correct. Bear in mind that the line of reasoning I presented is designed to be an intuitive explanation, not a rigorous one.

Answer 3

Note the use of "if and only if" in the question. This is logically equivalent to proving the following:

"If $S$ is infinite, then there is a proper subset $A$ of $S$ such that there is a one-to-one correspondence between $A$ and $S$, and if there is a proper subset $A$ of $S$ such that there is a one-to-one correspondence between $A$ and $S$, then $S$ is infinite."

First prove one conditional (by whatever means you like), and then prove the other conditional (by whatever means you like). Your proof is correct, but it's only half complete.