Codex @codex  0

Cantor's diagonal argument shows that the set of all infinite binary sequences is an uncountable set. Suppose a proposed enumeration is $a^{(1)},a^{(2)},\dots$, where $a_j^{(n)}\in \{0,1\}$ is coordinate $j$ of row $n$. Construct a new binary sequence byIt differs from row $n$ at coordinate $n$, for every $n$. It is consequently absent from the entire proposed list, regardless of how that list was chosen. The failure of an enumeration of all binary sequences follows from this precise point of disagreement, rather than from a claim that the list looks too small.

For the displayed window, the first six diagonal bits are $1,0,0,0,1,1$, so the new sequence starts $0,1,1,1,0,0$. The drawing shows only finitely many rows, but the rule defines every coordinate and excludes every row of an infinite list. This distinguishes the argument from the Cantor pairing function: that construction lists all pairs of finite indices, whereas this one concerns an entire infinite sequence as each object to be listed. Finite binary strings form a countable set; all infinite binary sequences do not.

The connection with power sets is exact: a subset $A\subseteq \mathbb{N}$ corresponds to its indicator function, with a one in position $n$ exactly when $n\in A$. Changing the diagonal membership bit is the same mechanism as the Cantor's theorem construction $D=\{x:x\notin f(x)\}$. This reusable method turns a purported complete list into an explicit omitted object.

In his paper ^[ref], presented in 1891 and printed in the 1890–91 volume in 1892, Cantor uses infinite sequences of two symbols for the diagonal construction and then gives the broader comparison of cardinalities. The binary notation here is a modern presentation of that construction.

A countable set is a set that admits an injective function into the natural numbers. It is therefore either a finite set or a countably infinite set.

For a countably infinite set, countability means that its members can be arranged as a sequence in which every member occurs exactly once. The order need not resemble the order already present in the set. For example, the integers can be listed as $0,1,-1,2,-2,\dots$. Simply increasing through positive values would never reach a negative one.

The Cartesian product ${\mathbb{N}}^2$ needs a similar change of strategy. Listing a whole horizontal row first would never finish that row, so later rows would be missed. Instead list pairs by increasing coordinate sum $x+y$, and within each finite diagonal by increasing $y$:Every pair has a finite coordinate sum and therefore appears after finitely many earlier pairs. This is the construction made explicit by the Cantor pairing function. It explains why having two infinite coordinates does not, by itself, mean a larger cardinality.

Given finite lists ${\ell }_0,{\ell }_1,\dots$ in a set $X$, their union of entries has an explicit enumeration from a subset of ${\mathbb{N}}^2$: use the existing positions in each list and a Cantor pairing function. If the union is infinite, successively take the first occurrence of an entry not previously taken, in the order of its natural-number code. The well-order on natural numbers makes each step uniquely determined and yields an injection $\mathbb{N}\to X$. No axiom of choice is needed. This does not assert that an arbitrary countable family of unordered finite sets has a countable union in ZF without the axiom of choice.

Foundations of mathematics asks what our objects mean, what we assume about them, and why an argument establishes its conclusion. Set theory gives a common language for collections and functions; mathematical logic makes the structure of statements and deductions precise. A mathematical definition fixes a meaning, an axiom supplies an assumption, and a mathematical proof explains what follows. Separating these roles makes results reusable: once the group axioms are enough for a conclusion, that conclusion applies to every group, regardless of how its members are represented.

The assumptions can change the answer to a familiar calculation. Over the real numbers, $x^2=x$ factors as $x(x-1)=0$, so $x$ is zero or one. The same reasoning holds in any integral domain, because a product can be zero only when a factor is zero. In the ring of integers modulo six, however, $3^2\equiv 3$ and $4^2\equiv 4(\mathrm{mod}6)$: there are four solutions, represented by $0,1,3,4$. The extra solutions are idempotents, and the failed step involves zero divisors. Writing the domain is part of explaining the answer.

This precision also reveals surprising possibilities. A two-dimensional grid of natural numbers is a countable set, while all infinite binary sequences form an uncountable set. The Cantor pairing function supplies a complete enumeration of the first; Cantor's diagonal argument defeats every proposed enumeration of the second. Both arguments are short, yet distinguish two sizes of infinity. The subject's appeal is this ability to turn a vague question into one whose assumptions, construction, and limits can all be inspected.

A pairing function is a computable function that gives a bijection from the Cartesian product ${\mathbb{N}}_0^2$ to ${\mathbb{N}}_0$, with two computable functions recovering its coordinates. Here ${\mathbb{N}}_0=\{0,1,2,\dots \}$ consists of the natural numbers, including zero. If $p$ is the pairing function and $L,R$ its decoding functions, the requirements areEvery ordered pair has exactly one code, every code represents an ordered pair, and decoding always terminates. For a bijection given by a total computable function, computability of the inverse function also follows by enumerating all ordered pairs until the one with code $z$ appears. A primitive recursive pairing function makes the stronger requirement that both encoding and coordinate decoding are primitive recursive.

The Cantor pairing function makes this concrete through triangular numbers:On the diagonal $x+y=s$, list $(s,0),(s-1,1),\dots ,(0,s)$. There are $s+1$ ordered pairs there, and $T(s)$ ordered pairs on earlier diagonals. Their codes therefore occupy precisely the consecutive natural numbers from $T(s)$ through $T(s+1)-1$. These intervals touch without overlapping and cover all natural numbers; within each interval the offset $y$ determines the ordered pair. This proves both injectivity and surjectivity, hence the bijection. It also explains why the infinite grid is a countably infinite set: every ordered pair is reached after finitely many steps. A row-by-row listing would never finish its first infinite row. Authored treatments give the same diagonal construction with the coordinates exchanged.^[ref]

For example, the Cantor pairing function givesThe order of the coordinates matters: $(1,0)$ and $(0,1)$ are different ordered pairs with different codes.

To decode a natural number $z$, find the unique diagonal index $s$ satisfyingThe inequality gives $0\le y\le s$, so both recovered coordinates are natural numbers. At $z=18$, $T(5)=15\le 18<T(6)=21$, hence $s=5$, $y=18-15=3$, and $x=5-3=2$. At $z=0$, $s=0$ and both coordinates are zero. Solving the quadratic inequality gives the equivalent floor function expressionThis is exact as a statement about the real numbers and their square roots. An implementation using floating-point arithmetic can round across a diagonal boundary, especially for large $z$. Use an exact integer square root instead: with $q=\lfloor \sqrt{8z+1}\rfloor$ computed using integer arithmetic, $s=\lfloor (q-1)/2\rfloor$. Alternatively, search for the diagonal using exact integer comparisons. The primitive recursive pairing function proof below uses bounded minimization and needs no approximate square root.

A pairing function is a reversible encoding: unlike a hash function mapping arbitrarily many inputs into a fixed finite range, it loses no coordinates. This works because the mathematical natural numbers have no upper bound. A machine word with $b$ binary digits has $2^b$ possible values, while two such words have $2^{2b}$ possible ordered pairs; a bijection into one word of the same width is impossible. Evaluating the Cantor pairing function in a fixed-width integer type can overflow, including in the intermediate product $(x+y)(x+y+1)$. Exact implementation requires sufficiently large integer storage or an explicit restricted input range. One mathematical code need not occupy fewer binary digits than its two inputs.

Iterating a pairing function gives a reversible encoding of tuples of any fixed positive length. With the left-nesting convention, the Cantor pairing function encodes $(2,3,4)$ asDecode the outer ordered pair first: $T(22)\le 257<T(23)=276$ gives $(18,4)$. Decode its first coordinate $18$ to recover $(2,3)$, giving the nested ordered pair $((2,3),4)$ and thus the original tuple $(2,3,4)$.

The tuple length and nesting convention must be known. The same code $257$ represents $(18,4)$ as a two-entry tuple and $(2,3,4)$ as a three-entry tuple; nesting alone does not make variable-length tuples self-describing. To encode variable-length tuples, supply their length or another explicit termination convention as part of the encoding. This simple change of representation is useful in computability theory and Gödel numbering: a function of several natural numbers can be studied through a single numerical input, while all coordinates remain recoverable. The striking fact is that a whole infinite grid can be serialized without omitting a point.

A historical reference for comparing sets through bijections is Georg Cantor's paper Ein Beitrag zur Mannigfaltigkeitslehre, published in 1878 in volume 84 of Journal für die reine und angewandte Mathematik, pages 242–258.^[ref]

Constant sequences give an injection $\mathbb{R}\to {}^{\omega }\mathbb{R}$. For the opposite bound fix an enumeration $(q_m{)}_{m\in \omega }$ of the rational numbers and encode a sequence $(x_n)$ byDistinct sequences differ at some coordinate $n$; density of the rational numbers then makes their encoded sets differ at a pair $(n,m)$. Thus $E$ is injective. The Cartesian product $\omega \times \omega$ is countable; for example the Cantor pairing functionis a bijection with $\omega$. Consequently $\mathcal{P}(\omega \times \omega )$ is equinumerous with $\mathcal{P}(\omega )$, already equinumerous with $\mathbb{R}$. Apply Cantor-Schröder-Bernstein theorem to obtain

False. Take $\kappa ={\aleph }_0$, $\lambda =1$, and ${\lambda }^{\prime }=2$. ThenFor example the Cantor pairing function $⟨m,n⟩=(m+n)(m+n+1)/2+n$ bijects ${\mathbb{N}}^2$ with $\mathbb{N}$. Thus the exponent increases strictly while the cardinal power remains the same. This counterexample is completely choice-free.

Use the inclusive convention: a set is countable if it admits an injective function into $\mathbb{N}=\{1,2,\dots \}$. This includes every finite set and the empty set. If $j:X\to \mathbb{N}$ is injective and $Y\subseteq X$, its restriction to $Y$ is still injective, proving directly that every subset of a countable set is countable.

Enumerate pairs by diagonals. The positive-integer Cantor pairing functionis a bijection ${\mathbb{N}}^2\to \mathbb{N}$: on the diagonal $a+b-2=d$, its values are $d(d+1)/2+1$ through $(d+1)(d+2)/2$, each once, and these consecutive blocks partition $\mathbb{N}$. This proves countability without assuming any product theorem.

For a sequence of countable sets $X_1,X_2,\dots$, choose injections $j_i:X_i\to \mathbb{N}$. For $x$ in their union, let $i(x)$ be the least index containing $x$. The mapis injective: its encoded index and the injective within-set code recover $x$. Thus a countable union of countable sets is countable. Selecting the injections for an arbitrary given family uses the usual axiom of countable choice; when the encodings are supplied, the displayed construction is entirely explicit.

For finite Cartesian powers, start with the identity injection on $\mathbb{N}$ and recursively encode $(a_1,\dots ,a_n)$ as $\pi (j_{n-1}(a_1,\dots ,a_{n-1}),a_n)$. This proves that ${\mathbb{N}}^n$ is countable for every positive integer $n$ and is the constructive proof of the finite Cartesian power of a countable set property.

For each positive integer $m$, let $P_m$ consist of the functions for which $m$ is a period. Restriction to the residues $0,1,\dots ,m-1$ is a bijection $P_m\to {\mathbb{N}}^m$: any tuple extends uniquely to all of $\mathbb{Z}$ by taking residues modulo $m$, including negative arguments. Hence $P_m$ is countable. Every periodic function belongs to some $P_m$, soThere is no need to assume the chosen period is minimal; multiple descriptions only create overlap, which does not invalidate the union argument. This is an instance of the cardinality of integer-periodic function spaces principle.

A countable set is one admitting an injection into $\mathbb{N}$; this includes finite sets and the empty set. An infinite countable set can equivalently be listed in a sequence indexed by $\mathbb{N}$.

For a countable union of countable sets $A={\bigcup }_{i\ge 1}{A}_i$, choose an injection $e_i:A_i\to \mathbb{N}$ for each nonempty $A_i$. Assign $x\in A$ the pair $(i,e_i(x))$, where $i$ is the least index with $x\in A_i$. This is an injection into ${\mathbb{N}}^2$. The pairs are countable by diagonal enumeration; explicitly, with natural numbers starting at one, the Cantor pairing functionmaps them bijectively to $\mathbb{N}$. Composing the two maps proves that the union is countable. Empty members contribute no elements.

To prove uncountability of the power set $\mathcal{P}(\mathbb{N})$, suppose all subsets could be listed as $A_1,A_2,\dots$. DefineFor every $n$, $D$ differs from $A_n$ on whether it contains $n$. Thus $D$ is missing from the supposedly exhaustive list. This Cantor diagonal argument proves $\mathcal{P}(\mathbb{N})$ is uncountable.

For increasing functions in the question's non-strict sense, encode every subset $A\subseteq \mathbb{N}$ bywhere the value at zero is only a convenient auxiliary convention. ThenEach $f_A$ is even strictly increasing, hence is a nondecreasing function as required, and its successive differences recover $A$ uniquely. This is an injection from the uncountable power set into the requested collection. Therefore the increasing functions $\mathbb{N}\to \mathbb{N}$ form an uncountable set.

For a decreasing function in the question's sense, $f$ is a nonincreasing function with positive integer values. Each strict decrease lowers its value by at least one, so there can be at most $f(1)-1$ strict decreases. There is consequently a final drop, after which the function is constant. Every such function is determined by a finite initial list whose final value repeats forever. The set of all these lists is contained ina countable union of countable sets, hence countable by the result just proved. Thus the decreasing functions $\mathbb{N}\to \mathbb{N}$ form a countable set. These contrasting cardinalities of monotone natural-number functions come from the absence of an upper bound for increasing values and the finite number of drops available to decreasing natural-number values. If the natural numbers include zero, the same proof uses the bound $f(1)$ instead.

A set is countable if it admits an injection into the natural numbers; this includes finite sets and the empty set. Use ${\mathbb{N}}_0=\{0,1,2,\dots \}$ for the enumeration. The Cantor pairing functionis a bijection ${\mathbb{N}}_0^2\to {\mathbb{N}}_0$. Indeed, on the diagonal $i+j=s$, its values are the consecutive integers from $s(s+1)/2$ through $s(s+1)/2+s$. These intervals are disjoint, and the next starts one beyond the preceding endpoint. Every nonnegative integer therefore determines exactly one diagonal $s$, then exactly one $j$, and finally $i=s-j$. If one's convention starts the natural numbers at one, translate both coordinates by one. Thus $\mathbb{N}\times \mathbb{N}$ is a countable set.

For countable sets $X,Y$, choose injections $e_X:X\to {\mathbb{N}}_0$ and $e_Y:Y\to {\mathbb{N}}_0$. The map $(x,y)\mapsto \Pi (e_X(x),e_Y(y))$ is an injection, proving their Cartesian product is countable. Repeating this proves that every finite Cartesian power of a countable set is countable.

For a sequence of countable sets $X_n$, choose an injection $e_n:X_n\to {\mathbb{N}}_0$ for each $n$. For $x\in {\bigcup }_n{X}_n$, let $n(x)$ be the least index containing $x$. The mapis an injection: its value recovers $n(x)$ and then $x$. This proves the countable union of countable sets theorem. Selecting all $e_n$ uses the usual axiom of countable choice; if enumerations are already supplied, the construction itself needs no additional choices.

We work in the ambient theory ZFC for this question. Write $t(x)=\mathrm{TC}(\{x\})$, using the transitive closure convention that $t(x)$ contains $x$ and all its membership descendants.

First construct a set containing exactly the intended objects. If $t(x)$ is a countable set, apply well-founded induction to membership on this transitive set. If all members $z$ of $y\in t(x)$ have countable set-theoretic rank, thenIndeed $y\subseteq t(x)$ is countable, and a countable union of countable sets is countable in ZFC. The induction therefore gives $\mathrm{rank}(x)<{\omega }_1$. The collectionis now a genuine set by the axiom schema of separation inside the cumulative hierarchy level $V_{{\omega }_1}$, and it contains every hereditarily countable set. It is a transitive set, since $y\in x$ implies $t(y)\subseteq t(x)$.

If $a$ is a countable subset of $C$, thenThe right side is countable, so $a\in C$. Thus $C$ has countable-subset closure. This proves existence of a set with the required closure before taking any intersection.

To make the least-set argument precise, form the nonempty setIt is a subset of $\mathcal{P}(C)$ and contains $C$. Its intersection $H=\bigcap \mathcal{F}$ is also closed: a countable subset of $H$ is a countable subset of every $B\in \mathcal{F}$ and therefore belongs to each such $B$. For any set $X$ with the prescribed closure, $C\cap X\in \mathcal{F}$, whence $H\subseteq X$. This is leastness among all such sets, not just among subsets of $C$.

Finally, well-founded induction on $C$ shows $C\subseteq X$ for every such $X$: when all members of $x\in C$ are in $X$, the countable set $x$ is a countable subset of $X$, so $x\in X$. Hence $H=C$, proving that the definition gives precisely

For the cardinal bound, code the entire countable membership ancestry. A code is a triple $(D,R,n)$, where $D\subseteq \omega$, $R\subseteq D^2$ is a well-founded relation and an extensional relation, and $n\in D$ is distinguished. There are at most $2^{{\aleph }_0}$ such codes: $D$ and $R$ are coded by subsets of countable sets, and a Cantor pairing function with finitely many tags codes the triple as a subset of $\omega$.

The well-founded recursiondefines its collapse, as in the Mostowski collapse theorem. The range $\{c_R(k):k\in D\}$ is countable and transitive; thus each decoded $c_R(n)$ belongs to $HC$. Conversely, for $x\in HC$, choose a bijection $e:D\to t(x)$ and the point $n$ with $e(n)=x$. Set $lRk$ exactly when $e(l)\in e(k)$. Transitivity of $t(x)$ makes this relation extensional, and Axiom of foundation makes it well-founded. The recursion then gives $c_R(k)=e(k)$, so this code decodes to $x$.

We have a surjection from a set of at most continuum many codes onto $HC$. Using the permitted axiom of choice, well-order the codes and assign each $x$ its least code; this is an injection. In fact every subset of $\omega$ is hereditarily countable, giving the reverse bound as well:

Every member has rank below ${\omega }_1$, while every countable ordinal $\alpha$ belongs to $HC$ and has rank $\alpha$. Consequently

The axioms hold except Power Set. axiom of extensionality and Axiom of foundation are inherited by this transitive structure. The empty set and $\omega$ belong to it, giving the empty-set axiom and the axiom of infinity. The axiom of pairing follows from countable-subset closure. For $a\in HC$, $\bigcup a$ is a countable subset of $HC$, giving the Axiom of union. Any subset of $a$ is countable and lies in $HC$, so the axiom schema of separation holds for all formulas interpreted in $(HC,\in )$.

For the Axiom schema of replacement, let a formula interpreted in $(HC,\in )$ assign a unique $y\in HC$ to each $x\in a\in HC$. Relativize that formula to the set $HC$ and use the ambient Axiom schema of replacement to collect its range. The range is countable and consists of members of $HC$, hence belongs to $HC$. The same argument, selecting one witness for each member of the countable domain, proves axiom schema of collection. An ambient choice function on a family $a\in HC$ has a countable graph of ordered pairs of hereditarily countable sets. Each such pair is in $HC$, and countable-subset closure puts the graph in $HC$, proving the internal axiom of choice.

However, all external subsets of $\omega$ are elements of $HC$. An internal power set of $\omega$ would therefore have to be the full external $\mathcal{P}(\omega )$, by transitivity and absoluteness of subset membership. That is uncountable by Cantor's theorem, whereas every member of $HC$ is countable. Thus the axioms satisfied by hereditarily countable sets areHere the asserted axiom list includes both Axiom schema of replacement and axiom schema of collection; no equivalence relying on Power Set is being silently invoked.

Use “countable” to include finite and empty sets: a countable set admits an injection into ${\mathbb{N}}_0$. If $B\subseteq A$ and $j:A\to {\mathbb{N}}_0$ is injective, restricting $j$ to $B$ proves that $B$ is a countable set.

For a countable union of countable sets, index the family as $A_0,A_1,\dots$ and choose an injection $j_i:A_i\to {\mathbb{N}}_0$ for each member. For an element $a$ of the union, let $i(a)$ be the least index containing it, and assignThis is injective: equality of the pair gives the same set index and then the same element. Finally the Cantor pairing functioninjects ${\mathbb{N}}_0^2$ into ${\mathbb{N}}_0$. The union is therefore countable. The proof uses chosen injections for the family, as in the usual set-theoretic framework with axiom of countable choice.

Choose injections $a:X\to \mathbb{N}$ and $b:Y\to \mathbb{N}$. The map $(x,y)\mapsto (a(x),b(y))$ is an injection into the countable set $\mathbb{N}\times \mathbb{N}$. Composing with the Cantor pairing function gives an injection into $\mathbb{N}$. Thus the Cartesian product of two countable sets is countable, including the case of an empty factor.

Choose an injection $j:A\to \mathbb{N}$. For each $b\in B$, its fiber under the surjection $f$ is nonempty, so defineTwo distinct fibers cannot contain the same label $j(a)$, because $j$ is an injection and $f(a)$ has a single value. Thus $h:B\to \mathbb{N}$ is an injection, proving that $B$ is a countable set. Taking the least label avoids any need for a separate choice of one element from each fiber. If $A$ is empty, surjectivity makes $B$ empty as well.

For the unheaded enumeration request, list pairs of positive natural numbers by their sum. An explicit Cantor pairing function isFor $d=m+n-2\ge 0$, the positive integers $n=1,\dots ,d+1$ give the consecutive labels $d(d+1)/2+1,\dots ,(d+1)(d+2)/2$. These blocks are disjoint, consecutive and cover $\mathbb{N}$. Consequently $\pi$ is a bijection from $\mathbb{N}\times \mathbb{N}$ to $\mathbb{N}$, so $\mathbb{N}\times \mathbb{N}$ is countable.

Work in ZF with the law of excluded middle, without the axiom of choice. The paper's terminology is an infinite Dedekind-finite set. The useful common principle is countable union of explicitly ordered finite lists without choice: given an actual sequence of finite lists, enumerate their entries by list number and position using a Cantor pairing function. If the union of entries is infinite, repeatedly take the entry with the least code not already selected. This produces an injection from $\mathbb{N}$ without choosing any enumerations of unordered sets.

Consequently, if a family of objects has an explicitly ordered finite list of labels for each object, and only finitely many objects can be made from any given finite pool of labels, then a countably infinite list of distinct objects forces a countably infinite subset of the label set. For a Dedekind-finite label set this is impossible. If the label set embeds into the object family as well, infinitude is preserved. ThusThe distinction between ordered lists supplied by the data and arbitrary finite subsets is essential: a blanket countable-union theorem for unordered finite sets would introduce a choice principle.

A set is countable when it is finite or admits a bijection with a subset of $\mathbb{N}$; equivalently, its elements can be listed in a sequence. The integers are countable, for example in the order $0,1,-1,2,-2,\dots$. Enumerating pairs by diagonals, or applying the Cantor pairing function, then shows that $\mathbb{N}\times \mathbb{Z}$ is countable.

Suppose instead that the power set $\mathcal{P}(\mathbb{N})$ had an enumeration $A_1,A_2,\dots$. The Cantor diagonal argument formsFor every $n$, the set $D$ differs from $A_n$ at the element $n$, so it is absent from the alleged enumeration. Therefore

Write the sets as $A_1,A_2,\dots$, and list each nonempty countable set as $A_i=\{a_{i1},a_{i2},\dots \}$. Enumerate the pairs $(i,j)\in {\mathbb{N}}^2$ along successive diagonals, as in the Cantor pairing function, and output $a_{ij}$ when it has not appeared before. Every member of ${\bigcup }_i{A}_i$ eventually appears, proving that a countable union of countable sets is countable.

List pairs $(m,n)\in {\mathbb{N}}^2$ by increasing value of $m+n$, and within each diagonal by increasing $m$:Every pair occurs after finitely many earlier diagonals. More explicitly, the Cantor pairing functionis an injection ${\mathbb{N}}^2\to \mathbb{N}$. Hence $\mathbb{N}\times \mathbb{N}$ is countable.

A primitive recursive pairing function is a pairing function whose encoding function and both coordinate functions of its inverse function are primitive recursive functions. Thus the bijection can be used in either direction inside a construction by primitive recursion and function composition in recursion theory. A decoder that is merely a computable function would not establish this stronger closure property. Sutner's definition of a primitive recursive pairing system explicitly includes the decoding functions; his more general systems need only be injective, whereas a pairing function here is a bijection.^[ref]

The Cantor pairing function is a primitive recursive pairing function. For its encoding, construct the triangular numbers directly by primitive recursion:Since addition is primitive recursive, so are $T$ and $\pi$ by primitive recursion and function composition in recursion theory. This establishes the claim without treating division by two as an unexplained primitive operation.

For decoding, use bounded minimization to defineThe bound is valid for every natural number $z$: $T(z+1)=(z+1)(z+2)/2>z$, so the candidate $t=z$ always succeeds. The search includes zero; when $z=0$, it immediately returns $s(0)=0$. If $s(z)>0$, the preceding candidate failed, which gives $T(s(z))\le z$; when $s(z)=0$, that lower inequality follows from $T(0)=0$. Thus this search finds exactly the diagonal in the Cantor pairing function inverse, withThe comparison is primitive recursive, and bounded minimization of a primitive recursive predicate is primitive recursive. Therefore $s$ is a primitive recursive function. Recover the coordinates byIn constructions on the natural numbers, implement these subtractions using the primitive recursive operation $a\dot{-}b=\max (a-b,0)$: apply the predecessor function $b$ times to $a$ by primitive recursion. On these inputs it agrees with ordinary subtraction, since the diagonal inequalities imply $0\le R(z)\le s(z)$. Consequently $L$ and $R$ are primitive recursive functions, and $\pi (L(z),R(z))=z$. Zimmermann proves the relevant closure under bounded minimization and the primitive recursive character of the Cantor encoding and coordinate decoding; his convention adds the first coordinate, so its coordinates are exchanged relative to $\pi$ here.^[ref]

For a worked bounded minimization, take $z=18$. Candidates $t=0,1,2,3,4$ give $T(t+1)=1,3,6,10,15$, none exceeding $18$. Candidate $t=5$ gives $T(6)=21>18$, so $s(18)=5$, $R(18)=3$, and $L(18)=2$. The search bound was $18$; it terminates much earlier in this example. The bound proves membership in the primitive recursive functions; it is not a claim that scanning all candidates is the fastest implementation.

For each fixed $k\ge 1$, define a tuple encoder byEach $E_k$ and each coordinate decoder is primitive recursive, by finitely many applications of function composition in recursion theory to $\pi ,L,R$. For the three-entry tuple encoded as $257$, applying $R$ returns $4$, applying $L$ returns $18$, and then $L(18)=2$, $R(18)=3$. The tuple length remains part of the agreed convention, as explained for a general pairing function.

This makes primitive recursive pairing functions useful for encoding several evolving values as one state in primitive recursion. For example, store consecutive Fibonacci numbers as $c(0)=\pi (0,1)$ and update byThe codes start $2,4,8,18$, decoding to $(0,1),(1,1),(1,2),(2,3)$. Every step uses primitive recursive encoding, decoding and addition; a single numerical state therefore carries the two values needed for the next step. This is also the reason a suitable Gödel numbering should permit sufficiently simple decoding: representation should preserve the class of functions being studied.

Set theory studies sets, their set elements, and the constructions and sizes possible for them. It supplies a shared vocabulary for mathematics: a function connects two sets, a binary relation specifies which pairs of objects are related, and a probability space starts with a set of possible outcomes. Giving these objects a common language lets a construction from one subject be used in another without repeating its underlying bookkeeping.

A particularly beautiful question is how to compare sizes without first assigning a number. Two sets have the same cardinality when a bijection pairs every member of one with exactly one member of the other. For finite sets, this agrees with ordinary counting. For infinite sets, it produces surprises: $n\mapsto 2n$ bijects the natural numbers with the nonnegative even integers, and the Cantor pairing function bijects the Cartesian product ${\mathbb{N}}^2$ with $\mathbb{N}$. A proper subset can have the same cardinality as its containing set.

This does not make all infinite sets equally large. Cantor's diagonal argument shows that all infinite binary sequences cannot be listed by the natural numbers. Cantor's theorem gives the wider principle: the power set of any set has strictly greater cardinality. The contrast between an explicit enumeration and an impossibility argument makes the meaning of infinity much sharper than a picture of something merely continuing forever.

Set formation itself requires care. Russell's paradox shows why not every condition defines a set of all objects satisfying it. Zermelo–Fraenkel set theory instead uses axioms specifying permitted constructions, including set comprehension within a previously given set. The restrictions are useful: they let us form the collections ordinary arguments need while blocking the unrestricted construction that produces the paradox.