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

• Jun 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 $\displaystyle \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 $\displaystyle S' \subset S$ with a bijection $\displaystyle \phi : S \longleftrightarrow S'$.

Any tips?
• Jun 3rd 2009, 01:51 PM
Plato
How does your textbook define infinite set ?
• Jun 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.
• Jun 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.
• Jun 3rd 2009, 10:15 PM
amitface
Here is my solution.

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

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

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

Define the bijection $\displaystyle \phi$ as follows:

Then define the bijection as follows:

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

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

I'll illustrate an example with the real numbers.

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

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

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