## 2.1. Countable Infinity

### Theorem 2.1.4: Dedekind Theorem

A set

**S**is infinite if and only if there exists a proper subset**A**of**S**which has the same cardinality as**S**.### Proof:

The proof contains some gaps that you are supposed to fill in as an exercise.
Assume that **S** is countable. Then, by definition,

- there exists a bijection
*f*from**S**to**N**

*g*from

**N**to

**N**defined as

*g(n) = n + 1*, which is a bijection from**N**to**N \**{1}.

*h(s) = (f*from^{-1}o g o f)(s) = f^{-1}(g(f(s)))**S**to**S**

*f*and

*g*are bijections,

*h*is also a bijection between

**S**and h(

**S**). But

*h(*is now a proper subset of

**S**)**S**- which element is in

**S**but not in h(

**S**) ? Hence,

**S**is equivalent to a proper subset of itself.

Assume that **S** is uncountable. Then we can extract a countable
subset **B** of **S**. By the above proof, there is a bijection
*h* from **B** to a proper subset **A** of **B**. Now
define the function

*f(s) = s*if*s*is in**S**\**B**and*f(s) = h(s)*if*s*is in**B**.

*f*is a bijection between

**S**and

*f(*, and

**S**)*f(*is a proper subset of

**S**)**S**- do you see why ? Hence,

**S**is again equivalent to a proper subset of itself.

Assume that **S** is finite. If **S** has, say, *N* elements,
then a proper subset of **S** contains at most *N - 1* elements.
But then it is impossible to find a bijection from **S** to this
proper subset - do you see why ?