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?
Best Answer
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.