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

• June 3rd 2009, 01:40 PM
pswoo
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?
• June 3rd 2009, 01:51 PM
Plato
How does your textbook define infinite set ?
• June 3rd 2009, 02:49 PM
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.
• June 3rd 2009, 03:26 PM
Plato
Quote:

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.
• June 3rd 2009, 10:15 PM
amitface
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\}$.