No Bijection between Finite Set and Proper Subset

From ProofWiki
Jump to: navigation, search

Theorem

A finite set can not be in one-to-one correspondence with one of its proper subsets.

That is, a finite set is not Dedekind-infinite.


Proof 1

Let $S$ be a finite set, and let $T$ be a proper subset of $S$.

Let $f: T \to S$ be an injection.

By Cardinality of Image of Injection and Cardinality of Subset of Finite Set:

$\size {\Img f} = \size T < \size S$

Here, $\Img f$ denotes the image of $f$.

Thus $\Img f \ne S$, and so $f$ is not a bijection.

$\blacksquare$


Proof 2

Proof by induction:

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

The set $\N_n = \left\{{0, 1, \ldots, n-1}\right\}$ of natural numbers less than $n$ is equivalent to none of its proper subsets.


Here we use the definition of set equivalence to mean that $S$ is equivalent to $T$ if there exists a bijection between them.


Basis for the Induction

$P \left({1}\right)$ is the case:

The set $\N_1 = \left\{{0}\right\}$ is equivalent to none of its proper subsets.

The only proper subset of $\left\{{0}\right\}$ is the empty set $\varnothing$, to which $\left\{{0}\right\}$ is trivially not equivalent.


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 1$, then it logically follows that $P \left({k+1}\right)$ is true.


So this is our induction hypothesis:

The set $\N_k = \left\{{0, 1, \ldots, k-1}\right\}$ is equivalent to none of its proper subsets.


Then we need to show:

The set $\N_{k+1} = \left\{{0, 1, \ldots, k}\right\}$ is equivalent to none of its proper subsets.


Induction Step

Suppose that $P \left({k+1}\right)$ is not true.

Let $\phi: N_{k+1} \to S$ be a bijection where $S \subsetneq N_{k+1}$.

We aim to demonstrate that the existence of such a $\phi$ contradicts the induction hypothesis.


We consider two cases:


Case 1.

Let $S \subseteq N_k$.

Then we define the composite mapping $\phi \circ \phi$ defined as:

$\forall m \in \N_{k+1}: \phi \circ \phi \left({m}\right) = \phi \left({\phi \left({m}\right)}\right)$

From Composite of Bijections is Bijection, $\phi \circ \phi$ is a bijection.

Now consider $T = \phi \circ \phi \left({\N_{k+1}}\right)$, the image set of $\N_{k+1}$ under $\phi \circ \phi$.

Let $m, t \in \N_{k+1}$ such that:

$\phi \circ \phi \left({m}\right) = \phi \left({t}\right)$

Since $\phi$ is an injection it follows that:

$\phi \left({m}\right) = t$

As $S$ is a proper subset of $\N_{k+1}$ it follows from Set Difference with Proper Subset that $\N_{k+1} \setminus S \ne \varnothing$.

Let $x \in \N_{k+1} \setminus S$.

Suppose $\phi \left({x}\right) \in T$.

Then that would mean that $\exists m \in \N_{k+1}$ such that:

$\phi \circ \phi \left({m}\right) = \phi \left({x}\right)$

which from above it would follow that:

$\phi \left({m}\right) = x$

and so $x \in S$.

But this can not happen as $S \cap \left({\N_{k+1} \setminus S}\right) = \varnothing$ from Set Difference Intersection with Second Set is Empty Set.

So it must be the case that $\phi \left({x}\right) \notin T$.

Thus it can be concluded that $\phi \circ \phi$ is a mapping from $\N_{k+1}$ onto a proper subset $T$ of $S$.


Now, consider the mapping $\psi: \N_k \to U$ where $U$ is a proper subset of $\N_k$.

We define $\psi$ as follows:

$\forall a \in \N_k: \psi \left({a}\right) = \begin{cases} a & : a \notin S = \phi \left({N_{k+1}}\right) \\ \phi \left({a}\right) & : a \in S \end{cases}$


The next step is to show that $\psi$ is an injection.

Consider $a, b \in \N_k$ such that $\psi \left({a}\right) = \psi \left({b}\right)$.

Either $\psi \left({a}\right) = \psi \left({b}\right) \in \N_k \setminus S$, in which case:

$\psi \left({a}\right) = a = \psi \left({b}\right) = b$

or $\psi \left({a}\right) = \psi \left({b}\right) \in S$, in which case:

$\psi \left({a}\right) = \phi \left({a}\right) = \psi \left({b}\right) = \phi \left({b}\right)$

As $\phi$ is a injection it follows that $a = b$.

So $\psi \left({a}\right) = \psi \left({b}\right) \implies a = b$ and so by definition $\psi$ is an injection.


Now consider $\psi \left({\N_k}\right)$.

We have that $\psi \left({\N_k}\right) = \N_k \setminus \left({S \setminus T}\right)$ so that $\psi$ is an injection from $\N_k$ to a proper subset of itself.

This contradicts the induction hypothesis.


Case 2.

Let $S \not \subseteq N_k$.

This means that $k \in S$.

There exists $x \in \N_{k+1}$ such that $\phi \left({x}\right) = k$, as $\phi: \N_{k+1} \to S$ is a surjection.

There also exists $y \in \N_{k+1} \setminus S$ as $\N_{k+1} \setminus S \ne \varnothing$ from Set Difference with Proper Subset.

Let $\phi': \N_{k+1} \to S$ be defined as:

$\phi' \left({a}\right) = \begin{cases} \phi \left({a}\right) : & a \ne x \\ y : & a = x \end{cases}$

As $\phi$ is a bijection it follows that $\phi': \N_{k+1} \to S\,'$ is also a bijection, where:

$S\,' = \left({S \setminus \left\{{k}\right\}}\right) \cup \left\{{y}\right\}$

Proceeding as Case 1, we prove the same contradiction in the induction hypothesis.


Thus by Proof by Contradiction, the assumption that $\phi: N_{k+1} \to S$ can be a bijection must be false.


So the truth of $P \left({m}\right)$ for all $m \le k$ implies the proof of $P \left({k+1}\right)$.

The result follows by the Second Principle of Mathematical Induction.


Therefore:

For all $n \in \N$, the set $\N_n = \left\{{0, 1, \ldots, n-1}\right\}$ of natural numbers less than $n$ is equivalent to none of its proper subsets.

$\blacksquare$


Note

Some sources use this result as the property which defines a finite set.


Sources