TheoremBase

Enumeration of an Infinite Countable Set

A subset of the natural numbers that is not finite is the set of terms of a strictly increasing sequence, which is a bijection onto it; consequently every countable set that is not finite is in bijection with the natural numbers.

Statement

Let N\mathbb{N} be the set of natural numbers, with the order of that definition. A sequence in N\mathbb{N} is strictly increasing as defined there. The notions finite, countable and bijection are those of the indicated definitions.

1. (Subsets of the natural numbers) Let A⊆NA\subseteq\mathbb{N} be a set that is not finite. Then there is a strictly increasing sequence (tk)k∈N(t_{k})_{k\in\mathbb{N}} in N\mathbb{N} such that the map k↦tkk\mapsto t_{k} is a bijection from N\mathbb{N} onto AA.

2. (Countable sets) Let XX be a countable set that is not finite. Then there is a bijection from N\mathbb{N} onto 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…