# Set is Infinite iff exist Subsets of all Finite Cardinalities

## Theorem

A set $S$ is infinite if and only if for all $n \in \N$, there exists a subset of $S$ whose cardinality is $n$.

## Proof

Let the cardinality of a set $S$ be denoted $\card S$.

### Necessary Condition

Suppose $S$ is infinite.

We use mathematical induction on $n$.

For all $n \in \N$, let $\map P n$ be the proposition:

There exists a subset of $S$ whose cardinality is $n$.

#### Basis for the Induction

$\O \subseteq S$

From Cardinality of Empty Set, its cardinality is $0$.

This is our basis for the induction.

#### Induction Hypothesis

Now we need to show that, if $\map P k$ is true, where $k \ge 0$, then it logically follows that $\map P {k + 1}$ is true.

So this is our induction hypothesis:

There exists a subset of $S$ whose cardinality is $k$.

Then we need to show:

There exists a subset of $S$ whose cardinality is $k+1$.

#### Induction Step

This is our induction step:

By the induction hypothesis, there exists $T \subseteq S$ such that $\card T = k$.

First, note that $S \ne T$, otherwise by definition of infinite $S$ would be finite.

So $T$ is therefore a proper subset of $S$.

So:

 $\displaystyle S \setminus T$ $\ne$ $\displaystyle \O$ Set Difference with Proper Subset $\displaystyle \exists x$ $\in$ $\displaystyle S \setminus T$ Definition of Empty Set $\displaystyle \leadsto \ \$ $\displaystyle \set x$ $\subseteq$ $\displaystyle S \setminus T$ Definition of Singleton $\displaystyle \leadsto \ \$ $\displaystyle \set x$ $\subseteq$ $\displaystyle S$ Set Difference is Subset: $S \setminus T \subseteq S$ $\displaystyle \leadsto \ \$ $\displaystyle T \cup \set x$ $\subseteq$ $\displaystyle S$ $T \subseteq S$ and $\set x \subseteq S$, and Union is Smallest Superset

As $x \notin T$ it follows that:

$\set x \cap T = \O$

Thus by Cardinality of Set Union:

$\card {T \cup \set x} = k + 1$

That is, $T \cup \set x$ is a subset of $S$ whose cardinality is $k + 1$.

This is the set whose existence was to be be proved.

So $\map P k \implies \map P {k + 1}$ and the result follows by the Principle of Mathematical Induction.

Therefore:

For all $n \in \N$, there exists a subset of $S$ whose cardinality is $n$.

$\Box$

### Sufficient Condition

Suppose that for all $n \in \N$, there exists a subset of $S$ whose cardinality is $n$.

Aiming for a contradiction, suppose that $S$ is finite.

Let $N = \card S$.

As $N \in \N$ it follows that $N + 1 \in \N$.

By hypothesis, there exists a subset $T \subseteq S$ whose cardinality is $N + 1$.

From Cardinality of Subset of Finite Set, $\card S \ge \card T$.

But then $\card S = N \ge N + 1 = \card T$, which contradicts the fact that $N < N + 1$.

From this contradiction it follows that $S$ can not be finite.

$\blacksquare$