Proof of Countable Sets: a Bijection from ℕ onto ℕ×ℕ, Finite Sets, Subsets, Surjective Images, Images, Products, and the Integers and Rationals

For (i): the identity $\mathrm{id}_{\mathbb{N}}$ is a bijective map $\mathbb{N}\to\mathbb{N}$ by Basic Properties of Functions: Equality, Composition, Identity, Inverse and Restriction (iii), hence surjective by Injective, Surjective and Bijective Functions between Classes (iii), so $\mathbb{N}$ is countable by Countable Set (i).

For (ii), $\le$ and $<$ denote the order and the strict order of $\mathbb{N}$, as in The Natural Numbers and the Natural Numbers with Zero: Arithmetic, Order, Induction and Recursion (v). Sums of natural numbers are rearranged by Arithmetic and Order of the Natural Numbers (i) and Arithmetic and Order of the Natural Numbers (ii), cancelled by Arithmetic and Order of the Natural Numbers (v) and compared by Arithmetic and Order of the Natural Numbers (ix), and inequalities are chained and compared by Arithmetic and Order of the Natural Numbers (vi) and Arithmetic and Order of the Natural Numbers (vii). Two further consequences are used throughout: for $a,b\in\mathbb{N}$ we have $a<a+b$, by Arithmetic and Order of the Natural Numbers (viii); and if $a<b$, then $a+1\le b$, since $b=a+d$ for some $d\in\mathbb{N}$ by Arithmetic and Order of the Natural Numbers (viii), $1\le d$ by Arithmetic and Order of the Natural Numbers (x), and so $a+1\le a+d$.

Triangular numbers. The map $\mathbb{N}\times\mathbb{N}\to\mathbb{N}$, $(k,u)\mapsto u+(k+1)$, exists (Maps and Relations Given by Formulas (ii)), its values lying in $\mathbb{N}$ by Natural Numbers Are the Successors in Omega: One Is Least and Not a Successor of a Natural Number, the Successor Is Injective, and N Is Closed under Addition and Multiplication (vi) (under the guard $k\in\mathbb{N}\wedge u\in\mathbb{N}$, $k$, $u$ and $1$ are terms of type $\mathbb{N}$ by Typed Terms under a Predicative Guard: Variables, Parameters, Values of Maps and Ordered Pairs, and Predicative Equations and Memberships between Them (i) and Typed Terms under a Predicative Guard: Variables, Parameters, Values of Maps and Ordered Pairs, and Predicative Equations and Memberships between Them (ii), so $u+(k+1)$ is one by Sums and Differences of Natural Numbers as Typed Terms (i)). By Recursion on the Natural Numbers Starting at One (i), applied with the set $\mathbb{N}$, the element $1$ and this map, there is a map $T:\mathbb{N}\to\mathbb{N}$ with $T(1)=1$ and $T(k+1)=T(k)+(k+1)$ for every $k\in\mathbb{N}$. It has three properties. First, $T(k)<T(k+1)$ for every $k\in\mathbb{N}$, as $T(k)<T(k)+(k+1)$. Second, $k\le T(k)$ for every $k\in\mathbb{N}$: $T(1)=1$, and if $k\neq1$, then $k=i+1$ for some $i\in\mathbb{N}$ by Arithmetic and Order of the Natural Numbers (xii), and $T(k)=T(i)+k=k+T(i)$, so $k<T(k)$. Third, if $i,k\in\mathbb{N}$ and $i<k$, then $T(i)<T(k)$, and hence $i\le k$ implies $T(i)\le T(k)$. Indeed, fix $i$ and let $A=\{d\in\mathbb{N}:T(i)<T(i+d)\}$, a set (by The Order on Omega (ii) its condition is the membership $(T(i),T(i+d))\in{<}$ of a pair term in the class $<$: under the guard $d\in\mathbb{N}$, $d$ and $i$ are terms of type $\mathbb{N}$ by Typed Terms under a Predicative Guard: Variables, Parameters, Values of Maps and Ordered Pairs, and Predicative Equations and Memberships between Them (i) and Typed Terms under a Predicative Guard: Variables, Parameters, Values of Maps and Ordered Pairs, and Predicative Equations and Memberships between Them (ii), $i+d$ is one by Sums and Differences of Natural Numbers as Typed Terms (i), $T(i)$ and $T(i+d)$ are terms of type $\mathbb{N}$ by Typed Terms under a Predicative Guard: Variables, Parameters, Values of Maps and Ordered Pairs, and Predicative Equations and Memberships between Them (iii), and their pair is a term by Typed Terms under a Predicative Guard: Variables, Parameters, Values of Maps and Ordered Pairs, and Predicative Equations and Memberships between Them (iv); the membership is expressed by a predicative formula by Typed Terms under a Predicative Guard: Variables, Parameters, Values of Maps and Ordered Pairs, and Predicative Equations and Memberships between Them (vi), so $A$ is a set of the form $\{x\in D:t\in C\}$ of Typed Terms under a Predicative Guard: Variables, Parameters, Values of Maps and Ordered Pairs, and Predicative Equations and Memberships between Them (vii)). Then $1\in A$ by the first property, and if $d\in A$, then $T(i)<T(i+d)<T((i+d)+1)=T(i+(d+1))$, so $d+1\in A$. By Arithmetic and Order of the Natural Numbers (xiii), $A=\mathbb{N}$; and if $i<k$, then $k=i+d$ for some $d\in\mathbb{N}$ by Arithmetic and Order of the Natural Numbers (viii), so $T(i)<T(k)$.

The diagonal of a pair. Let $m,n\in\mathbb{N}$. Since $1\le m$ by Arithmetic and Order of the Natural Numbers (x) and $m<m+n$, we have $1<m+n$, so $m+n\neq1$, and by Arithmetic and Order of the Natural Numbers (xii) there is $j\in\mathbb{N}$ with $m+n=j+1$; it is unique by cancellation, and we write $j_{m,n}$ for it. As $1\le m$, $n+1\le n+m=j_{m,n}+1$, so $n\le j_{m,n}$. Hence $n\le T(j_{m,n})$ by the second property of $T$, and, adding $m+n$ to both sides by Arithmetic and Order of the Natural Numbers (ix),

$$T(m+n)=T(j_{m,n}+1)=T(j_{m,n})+(m+n)\ge n+(m+n),$$

so $(m+n)+n<T(m+n)+1$, as $T(m+n)<T(m+n)+1$ by Arithmetic and Order of the Natural Numbers (xi).

The map $\sigma$. For $m,n\in\mathbb{N}$ let $\sigma(m,n)=(T(m+n)+1)-((m+n)+n)$, the difference in $\mathbb{N}_{0}$; it is defined because $(m+n)+n\le T(m+n)+1$ in the order of $\mathbb{N}_{0}$, which agrees with that of $\mathbb{N}$ by The Natural Numbers and the Natural Numbers with Zero: Arithmetic, Order, Induction and Recursion (x). Thus $\sigma(m,n)\in\mathbb{N}_{0}$ and $((m+n)+n)+\sigma(m,n)=T(m+n)+1$, by The Difference of Two Natural Numbers with Zero (i). Here $\sigma(m,n)\neq0$, since $((m+n)+n)+0=(m+n)+n$ by Arithmetic of Addition on Omega: Recursion Rules, Associativity, Commutativity, Cancellation and Compatibility with the Order (i), which differs from $T(m+n)+1$, since $(m+n)+n<T(m+n)+1$ excludes equality by Arithmetic and Order of the Natural Numbers (vii); so $\sigma(m,n)\in\mathbb{N}$, as $\mathbb{N}=\mathbb{N}_{0}\setminus\{0\}$ by The Natural Numbers and the Natural Numbers with Zero: Arithmetic, Order, Induction and Recursion (ii). This defines a map $\sigma:\mathbb{N}\times\mathbb{N}\to\mathbb{N}$ (Maps and Relations Given by Formulas (ii); under the guard $m\in\mathbb{N}\wedge n\in\mathbb{N}$, $m$, $n$ and $1$ are terms of type $\mathbb{N}$ by Typed Terms under a Predicative Guard: Variables, Parameters, Values of Maps and Ordered Pairs, and Predicative Equations and Memberships between Them (i) and Typed Terms under a Predicative Guard: Variables, Parameters, Values of Maps and Ordered Pairs, and Predicative Equations and Memberships between Them (ii), $m+n$, $(m+n)+n$ and $T(m+n)+1$ are terms of type $\mathbb{N}$ by Sums and Differences of Natural Numbers as Typed Terms (i) and Typed Terms under a Predicative Guard: Variables, Parameters, Values of Maps and Ordered Pairs, and Predicative Equations and Memberships between Them (iii), and, as $(m+n)+n\le T(m+n)+1$ for all $m,n\in\mathbb{N}$, the difference defining $\sigma(m,n)$ is a term of type $\mathbb{N}_{0}$ by Sums and Differences of Natural Numbers as Typed Terms (ii)), $\mathbb{N}\times\mathbb{N}$ being a set by Membership in a Cartesian Product, and the Cartesian Product of Two Sets Is a Set (ii). For $N\in\mathbb{N}$, the uniqueness in The Difference of Two Natural Numbers with Zero (i) gives $\sigma(m,n)=N$ if and only if $((m+n)+n)+N=T(m+n)+1$. Since $((m+n)+n)+N=(m+n)+(N+n)$ and, by the display above, $T(m+n)+1=(m+n)+(T(j_{m,n})+1)$, cancelling $m+n$ shows that, for $N\in\mathbb{N}$,

$$\sigma(m,n)=N\iff N+n=T(j_{m,n})+1.$$

Where $\sigma(m,n)$ lies. Let $m,n\in\mathbb{N}$, $N=\sigma(m,n)$ and $j=j_{m,n}$. Then $N\le T(j)$, and $T(i)<N$ for every $i\in\mathbb{N}$ with $i<j$. For the first, $N+1\le N+n=T(j)+1$, as $1\le n$ by Arithmetic and Order of the Natural Numbers (x), so $N\le T(j)$. For the second, let $i\in\mathbb{N}$ with $i<j$. Then $j\neq1$, as $1\le i$, so $j=i'+1$ for some $i'\in\mathbb{N}$ by Arithmetic and Order of the Natural Numbers (xii); and $i\le i'$, since $i'<i$ would give $j=i'+1\le i$. As $n\le j$, $n+1\le j+1$ by Arithmetic and Order of the Natural Numbers (ix), and with $T(j)=T(i')+j$ this gives, by Arithmetic and Order of the Natural Numbers (ii) and Arithmetic and Order of the Natural Numbers (i) for the equalities and Arithmetic and Order of the Natural Numbers (ix) for the inequality,

$$(T(i')+1)+n=T(i')+(n+1)\le T(i')+(j+1)=T(j)+1=N+n,$$

so $T(i')+1\le N$ by Arithmetic and Order of the Natural Numbers (ix), and therefore $T(i')<N$. By the third property of $T$, $T(i)\le T(i')$, so $T(i)<N$.

$\sigma$ is injective. Every element of $\mathbb{N}\times\mathbb{N}$ is a pair $(m,n)$ with $m,n\in\mathbb{N}$, by The Cartesian Product of Two Classes (i) and Membership in a Cartesian Product, and the Cartesian Product of Two Sets Is a Set (i). Let $m,n,m',n'\in\mathbb{N}$ with $\sigma(m,n)=\sigma(m',n')=N$, and let $j=j_{m,n}$ and $j'=j_{m',n'}$. If $j<j'$, the previous paragraph applied to $(m',n')$ and $i=j$ gives $T(j)<N$, while applied to $(m,n)$ it gives $N\le T(j)$, which is impossible; likewise $j'<j$ is impossible, so $j=j'$ by Arithmetic and Order of the Natural Numbers (vii). Then $N+n=T(j)+1=N+n'$, so $n=n'$, and $m+n=j+1=m'+n$, so $m=m'$. Hence $(m,n)=(m',n')$, and $\sigma$ is injective by Injective, Surjective and Bijective Functions between Classes (i).

$\sigma$ is surjective. Let $N\in\mathbb{N}$. The set $S=\{k\in\mathbb{N}:N\le T(k)\}$ (by The Order on Omega (i) its condition is the membership $(N,T(k))\in{\le}$ of a pair term in the class $\le$: under the guard $k\in\mathbb{N}$, $k$ and $N$ are terms of type $\mathbb{N}$ by Typed Terms under a Predicative Guard: Variables, Parameters, Values of Maps and Ordered Pairs, and Predicative Equations and Memberships between Them (i) and Typed Terms under a Predicative Guard: Variables, Parameters, Values of Maps and Ordered Pairs, and Predicative Equations and Memberships between Them (ii), $T(k)$ is one by Typed Terms under a Predicative Guard: Variables, Parameters, Values of Maps and Ordered Pairs, and Predicative Equations and Memberships between Them (iii), and the pair is a term by Typed Terms under a Predicative Guard: Variables, Parameters, Values of Maps and Ordered Pairs, and Predicative Equations and Memberships between Them (iv); the membership is expressed by a predicative formula by Typed Terms under a Predicative Guard: Variables, Parameters, Values of Maps and Ordered Pairs, and Predicative Equations and Memberships between Them (vi), so $S$ is a set of the form $\{x\in D:t\in C\}$ of Typed Terms under a Predicative Guard: Variables, Parameters, Values of Maps and Ordered Pairs, and Predicative Equations and Memberships between Them (vii)) contains $N$ by the second property of $T$, so by Arithmetic and Order of the Natural Numbers (xv) it has an element $j$ with $j\le k$ for every $k\in S$. As $N\le T(j)<T(j)+1$, there is $n\in\mathbb{N}$ with $T(j)+1=N+n$, by Arithmetic and Order of the Natural Numbers (viii). We show $n\le j$. If $j=1$, then $N\le T(1)=1\le N$, so $N=1$, and $1+n=T(1)+1=1+1$, so $n=1=j$. If $j\neq1$, then $j=i+1$ for some $i\in\mathbb{N}$ by Arithmetic and Order of the Natural Numbers (xii), and $i<j$ by Arithmetic and Order of the Natural Numbers (xi); so $i\notin S$, since $i\in S$ would give $j\le i$. Hence $T(i)<N$ by Arithmetic and Order of the Natural Numbers (vii), and so $T(i)+1\le N$. With $T(j)=T(i)+j$ this gives, by Arithmetic and Order of the Natural Numbers (ii) and Arithmetic and Order of the Natural Numbers (i) for the equalities and Arithmetic and Order of the Natural Numbers (ix) for the inequality,

$$N+n=T(j)+1=(T(i)+1)+j\le N+j,$$

so $n\le j$, by Arithmetic and Order of the Natural Numbers (i) and Arithmetic and Order of the Natural Numbers (ix). Therefore $n<j+1$, as $j<j+1$ by Arithmetic and Order of the Natural Numbers (xi), and so $j+1=n+m$ for some $m\in\mathbb{N}$, by Arithmetic and Order of the Natural Numbers (viii). Then $m+n=j+1$, so $j_{m,n}=j$ by the uniqueness of $j_{m,n}$, and $N+n=T(j)+1$ gives $\sigma(m,n)=N$, where $(m,n)\in\mathbb{N}\times\mathbb{N}$ by Membership in a Cartesian Product, and the Cartesian Product of Two Sets Is a Set (i). So $\sigma$ is surjective by Injective, Surjective and Bijective Functions between Classes (ii).

Thus $\sigma$ is a bijection by Injective, Surjective and Bijective Functions between Classes (iii), and its inverse $\tau=\sigma^{-1}:\mathbb{N}\to\mathbb{N}\times\mathbb{N}$ is a bijection by Basic Properties of Functions: Equality, Composition, Identity, Inverse and Restriction (vi). Explicitly, for $N\in\mathbb{N}$, $\tau(N)$ is the pair $(m,n)$ found in the previous paragraph: with $j$ the least $k\in\mathbb{N}$ such that $N\le T(k)$, $n$ is given by $N+n=T(j)+1$ and $m$ by $m+n=j+1$ (the least such $k$ is unique by Arithmetic and Order of the Natural Numbers (vi), and $n$ and $m$ exist by Arithmetic and Order of the Natural Numbers (viii), as in the previous paragraph, and are unique by Arithmetic and Order of the Natural Numbers (v)). Since $\tau$ is surjective, $\mathbb{N}\times\mathbb{N}$ is countable by Countable Set (i).

For (iii), let $X$ be finite: by Finite Sets (i) there are $n\in\mathbb{N}_{0}$ and a bijection $h:[n]\to X$, where $[n]=\{k\in\mathbb{N}:k\le n\}$ by Intervals of Natural Numbers: Initial Segments, Adding One Element, Splitting and Shifting (i) (a set by Routine Facts Used Without Citation: Arithmetic, Maps, Predicativity and Indices (v), with $[n]\subseteq\mathbb{N}$ by Elements of a Segment Are Natural Numbers, and Mixed Transitivity of the Order on the Natural Numbers (i)). If $X=\emptyset$, then $X$ is countable by Countable Set (i). Otherwise fix $x_{0}\in X$. By Maps Defined by Cases (i) there is a map $f:\mathbb{N}\to X$ with $f(k)=h(k)$ for $k\in\mathbb{N}$ with $k\in[n]$, and $f(k)=x_{0}$ for the other $k\in\mathbb{N}$, as $h(k)\in X$ for $k\in[n]$ by Values, Restriction and Equality of a Map, and the Map $u\mapsto t(u)$ as a Defined Set Symbol (ii). Every $x\in X$ is $h(k)$ for some $k\in[n]$, by Injective, Surjective and Bijective Functions between Classes (iii) and Injective, Surjective and Bijective Functions between Classes (ii); then $k\in\mathbb{N}$ and $f(k)=h(k)=x$. So $f$ is surjective, and $X$ is countable by Countable Set (i).

For (iv), let $X$ be countable and $Y\subseteq X$. If $Y=\emptyset$, then $Y$ is countable by Countable Set (i). Otherwise fix $y_{0}\in Y$. Then $X\neq\emptyset$, as $y_{0}\in X$, so by Countable Set (i) there is a surjective map $f:\mathbb{N}\to X$. By Maps Defined by Cases (i) there is a map $g:\mathbb{N}\to Y$ with $g(n)=f(n)$ for $n\in\mathbb{N}$ with $f(n)\in Y$, and $g(n)=y_{0}$ for the other $n\in\mathbb{N}$. Every $y\in Y$ lies in $X$, so $y=f(n)$ for some $n\in\mathbb{N}$, by Injective, Surjective and Bijective Functions between Classes (ii); then $f(n)\in Y$, so $g(n)=f(n)=y$. So $g$ is surjective, and $Y$ is countable by Countable Set (i).

For (v), let $X$ be countable and $g:X\to Y$ surjective. If $X=\emptyset$, then $Y=\emptyset$, since every $y\in Y$ is $g(x)$ for some $x\in X$, by Injective, Surjective and Bijective Functions between Classes (ii); so $Y$ is countable by Countable Set (i). Otherwise there is a surjective map $f:\mathbb{N}\to X$, by Countable Set (i), and the composite $g\circ f:\mathbb{N}\to Y$ is a surjective map by Basic Properties of Functions: Equality, Composition, Identity, Inverse and Restriction (ii) and Basic Properties of Functions: Equality, Composition, Identity, Inverse and Restriction (viii); so $Y$ is countable by Countable Set (i).

For (vi), let $X\subseteq A$ be countable. The image $g(X)=g[X]$ is a set, by Sets and Maps: Ordinary Notation (vii). For $x\in X$ we have $(x,g(x))\in g$ by Values, Restriction and Equality of a Map, and the Map $u\mapsto t(u)$ as a Defined Set Symbol (ii), so $g(x)\in g[X]$ by The Image and the Preimage of a Class under a Class (i); hence there is a map $h:X\to g(X)$ with $h(x)=g(x)$ for every $x\in X$ (Maps and Relations Given by Formulas (i)). Every $v\in g[X]$ satisfies $(u,v)\in g$ for some $u\in X$, by The Image and the Preimage of a Class under a Class (i), and then $v=g(u)=h(u)$ by Values, Restriction and Equality of a Map, and the Map $u\mapsto t(u)$ as a Defined Set Symbol (i), as $u\in A$. So $h$ is surjective, and $g(X)$ is countable by (v).

For (vii), let $X$ and $Y$ be countable; $X\times Y$ is a set by Membership in a Cartesian Product, and the Cartesian Product of Two Sets Is a Set (ii), and every element of it is a pair $(u,v)$ with $u\in X$ and $v\in Y$, by The Cartesian Product of Two Classes (i) and Membership in a Cartesian Product, and the Cartesian Product of Two Sets Is a Set (i). If $X=\emptyset$ or $Y=\emptyset$, then $X\times Y=\emptyset$, which is countable by Countable Set (i). Otherwise there are surjective maps $f:\mathbb{N}\to X$ and $g:\mathbb{N}\to Y$, by Countable Set (i). Since $(f(a),g(b))\in X\times Y$ for $a,b\in\mathbb{N}$, by Values, Restriction and Equality of a Map, and the Map $u\mapsto t(u)$ as a Defined Set Symbol (ii) and Membership in a Cartesian Product, and the Cartesian Product of Two Sets Is a Set (i), there is a map $h:\mathbb{N}\times\mathbb{N}\to X\times Y$ with $h(a,b)=(f(a),g(b))$ (Maps and Relations Given by Formulas (ii)). For $(u,v)\in X\times Y$ there are $a,b\in\mathbb{N}$ with $f(a)=u$ and $g(b)=v$, by Injective, Surjective and Bijective Functions between Classes (ii), and then $h(a,b)=(u,v)$. So $h$ is surjective, and $X\times Y$ is countable by (ii) and (v).

For (viii): $\mathbb{Z}$ is a set whose elements are the classes $[a,b]$ with $a,b\in\mathbb{N}$, by The Integers (i), so there is a map $q:\mathbb{N}\times\mathbb{N}\to\mathbb{Z}$ with $q(a,b)=[a,b]$ (Maps and Relations Given by Formulas (ii); under the guard $a\in\mathbb{N}\wedge b\in\mathbb{N}$, $a$ and $b$ are terms of type $\mathbb{N}$ by Typed Terms under a Predicative Guard: Variables, Parameters, Values of Maps and Ordered Pairs, and Predicative Equations and Memberships between Them (i), so $[a,b]$ is a term of type $\mathbb{Z}$ by Integer and Rational Brackets as Typed Terms (i)). It is surjective, since every $u\in\mathbb{Z}$ is $[a,b]$ for some $a,b\in\mathbb{N}$ by The Integers (ii). Hence $\mathbb{Z}$ is countable by (ii) and (v).

For (ix): $\mathbb{Q}$ is a set whose elements are the classes $[x,m]$ with $x\in\mathbb{Z}$ and $m\in\mathbb{N}$, by The Rational Numbers (i), so there is a map $r:\mathbb{Z}\times\mathbb{N}\to\mathbb{Q}$ with $r(x,m)=[x,m]$ (Maps and Relations Given by Formulas (ii); under the guard $x\in\mathbb{Z}\wedge m\in\mathbb{N}$, $x$ is a term of type $\mathbb{Z}$ and $m$ one of type $\mathbb{N}$ by Typed Terms under a Predicative Guard: Variables, Parameters, Values of Maps and Ordered Pairs, and Predicative Equations and Memberships between Them (i), so $[x,m]$ is a term of type $\mathbb{Q}$ by Integer and Rational Brackets as Typed Terms (ii)). It is surjective, since every $u\in\mathbb{Q}$ is $[x,m]$ for some $x\in\mathbb{Z}$ and $m\in\mathbb{N}$ by The Rational Numbers (ii). The set $\mathbb{Z}\times\mathbb{N}$ is countable by (viii), (i) and (vii), so $\mathbb{Q}$ is countable by (v).

For (x): $\mathbb{Q}\times\mathbb{Q}$ is countable by (ix) and (vii).