Set is Infinite iff exist Subsets of all Finite Cardinalities

From ProofWiki
Jump to navigation Jump to search

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 $\left|{S}\right|$.


Necessary Condition

Suppose $S$ is infinite.

We use mathematical induction on $n$.


For all $n \in \N$, let $P \left({n}\right)$ be the proposition:

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


Basis for the Induction

From Empty Set is Subset of All Sets:

$\varnothing \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 $P \left({k}\right)$ is true, where $k \ge 0$, then it logically follows that $P \left({k+1}\right)$ 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 $\left|{T}\right| = 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 \varnothing\) Set Difference with Proper Subset
\(\displaystyle \exists x\) \(\in\) \(\displaystyle S \setminus T\) Definition of Empty Set
\(\displaystyle \implies \ \ \) \(\displaystyle \left\{ {x}\right\}\) \(\subseteq\) \(\displaystyle S \setminus T\) Definition of Singleton
\(\displaystyle \implies \ \ \) \(\displaystyle \left\{ {x}\right\}\) \(\subseteq\) \(\displaystyle S\) Set Difference is Subset: $S \setminus T \subseteq S$
\(\displaystyle \implies \ \ \) \(\displaystyle T \cup \left\{ {x}\right\}\) \(\subseteq\) \(\displaystyle S\) $T \subseteq S$ and $\left\{ {x}\right\} \subseteq S$, and Union is Smallest Superset

As $x \notin T$ it follows that:

$\left\{ {x}\right\} \cap T = \varnothing$

Thus by Cardinality of Set Union:

$\left|{T \cup \left\{ {x}\right\}}\right| = k + 1$

That is, $T \cup \left\{ {x}\right\}$ is a subset of $S$ whose cardinality is $k + 1$.

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


So $P \left({k}\right) \implies P \left({k+1}\right)$ 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$.

Assume that $S$ is finite.


Let $N = \left\vert{S}\right\vert$.

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, $\left\vert{S}\right\vert \ge \left\vert{T}\right\vert$.


But then $\left\vert{S}\right\vert = N \ge N + 1 = \left\vert{T}\right\vert$, which contradicts the fact that $N < N + 1$.

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

$\blacksquare$


Sources