Thread: a set is infinite iff there is a bijection between it and a proper subset

1. a set is infinite iff there is a bijection between it and a proper subset

I've been trying to prove that a set S is infinite if any only if there is a proper subset S' and a bijection $\phi : S \longleftrightarrow S'$.

Assuming the bijection exists, it's pretty clear that S cannot be finite, and it was easy to prove this. But I'm not having much luck going the other direction:

Assuming S is not finite, prove there exists $S' \subset S$ with a bijection $\phi : S \longleftrightarrow S'$.

Any tips?

2. How does your textbook define infinite set ?

3. The textbook's definition is as follows:

A set S is finite if it is empty or if there is a natural number n such that {1, 2, ..., n} and S have the same cardinality. A set that is not finite is said to be infinite.

... so essentially we have infinite defined as not finite.

4. Originally Posted by pswoo
The textbook's definition is as follows:
A set S is finite if it is empty or if there is a natural number n such that {1, 2, ..., n} and S have the same cardinality. A set that is not finite is said to be infinite.
... so essentially we have infinite defined as not finite.
That is a definition that I do not use in my presentations of this material.
Therefore, sad to say, I do not see a good way to do this.
Maybe someone else here knows this approach.

5. Here is my solution.

We'll prove that if $S$ is infinite, then $S$ is in bijection with a proper subset of itself.

This is obvious if $S$ is countable, as if we remove one element, we still have a countable set, so we'll assume $S$ is uncountable.

It is true that any infinite set has a countable subset $A=\{s_1,s_2,s_3\cdots\}$.

Define the bijection $\phi$ as follows:

Then define the bijection as follows:

If $x\notin A$ then $\phi(x)=x$.
Otherwise, $\phi(x)=s_{i+1},$, where $s_i=x$.

Then $\phi$ is a bijection from $S$ to $S\smallsetminus s_1$.

I'll illustrate an example with the real numbers.

$\mathbb{R}$ has a countable subset, $\{1,2,\cdots\}$.

Then $\phi$ will map 1 to 2, 2 to 3, etc .. and everything else will remain fixed.

We thus have a bijection from $\mathbb{R}$to $\mathbb{R}\smallsetminus \{1\}$.