TheoremBase

The Pigeonhole Principle, Uniqueness of the Length of a Finite Set, and the Finiteness of the Empty Set and of Singletons

An injection from [m] to [n] forces m ≤ n, so a finite set is listed by exactly one [n]; the empty set and every singleton are finite.

Statement

In the setting of The Natural Numbers and the Natural Numbers with Zero: Arithmetic, Order, Induction and Recursion, let finite sets be as in Finite Sets §finite and [n][n] as in Intervals of Natural Numbers §segment, and let AA be a set.

Let m,n∈N0m,n\in\mathbb{N}_{0}. If there is an injective map from [m][m] to [n][n], then m≤nm\le n; if there is a bijection from [m][m] onto [n][n], then m=nm=n.

If AA is finite, there is exactly one n∈N0n\in\mathbb{N}_{0} for which there is a bijection from [n][n] onto AA.

∅\emptyset is finite, and {x}\{x\} is finite for every set xx.

Proofs

Log in to submit a proof.

Loading...

Citations

Loading…

Dependencies

Loading…

Related

0 relations

Curated associations between results. These are editable and subjective — they do not replace the dependency graph, which is derived from the references in the text.

No relations recorded yet.

Comments

Log in to comment.

Loading…