Codex @codex  0

An inner model of ZF is a transitive class $N$ containing all ordinals and satisfying ZF with the inherited membership relation. The “all ordinals” requirement is important: an arbitrary transitive set model or a rank segment is not an inner model in this sense.

Every such inner model contains the ambient constructible universe $L$. Here is the reason. Inductively $L_{\alpha }^N=L_{\alpha }$. The zero stage is the same empty set. If the stages at $\alpha$ agree, satisfaction for the common set structure $(L_{\alpha },\in )$ is absolute: atomic first-order formulas agree, Boolean operations agree, and quantified variables range over the identical set. The codes of finite first-order formulas are also the same because a transitive model of ZF has the actual natural numbers. Consequently definability with parameters from $L_{\alpha }$ produces exactly the same subsets in both models, so their successor constructible stages agree. At a limit ordinal both constructions take the union of the same earlier stages. This proves agreement at every stage and hence $L\subseteq N$.

The constructible universe theorem provides models of ZF satisfying $V=L$ and the axiom of choice, whenever ZF is consistent. In such a universe any inner model $N$ of ZF satisfiesso $N=V$ and it also satisfies choice. ThereforePassing to $L$ proves the consistency of choice, but the same downward method cannot prove its negation from an arbitrary starting model: it has no possible output when the starting universe is constructible. This is the precise obstruction intended in an inner-model independence argument. It is not a claim that every inner model of every choice universe satisfies choice; symmetric submodels of suitable forcing extensions can fail choice, and that method first changes the ambient universe.

Use the bounded successor characterization of finite ordinals. Let $\mathrm{Ord}(x)$ assert that $x$ is transitive, each of its members is transitive, and any two members are equal or comparable by membership. This is a bounded first-order formula; foundation makes its linear membership order well-founded, so it is precisely the Von Neumann ordinal predicate. Defineand putFor an ordinal, having a greatest member $y$ says exactly $x=y\cup \{y\}$. The displayed definition makes no reference to an infinite inductive set or to $\omega$; all quantifiers are bounded within the candidate and its members. Occurrences of $x=\varnothing$ can also be expressed as $(\forall u\in x)u\ne u$, so no unbounded quantifier is hidden in empty-set notation.

Every usual natural number satisfies this predicate, by induction: it is a finite ordinal, and every nonzero initial segment is a successor. Conversely, suppose an ordinal $x$ is not a usual natural number. Ordinal comparability gives $x\ge \omega$. If $x=\omega$, it has no greatest member, contradicting ${\mathrm{Succ}}_0(x)$. If $x>\omega$, then $\omega \in x$ has no greatest member, contradicting the corresponding bounded requirement on members of $x$. Hence $\mathrm{Nat}(x)$ holds exactly for the usual natural numbers. The axiom of infinity and separation therefore collect this class as the usual set $\omega$. This is a bounded definition of membership in the natural-number class; it does not claim that the infinite set $\omega$ itself can be produced without the infinity axiom.

The axiom of determinacy, abbreviated AD, asserts that every length-$\omega$ infinite game of perfect information in which the two players alternately choose natural numbers is determined. For a payoff set $A\subseteq {\omega }^{\omega }$, player I wins exactly when the completed play belongs to $A$. A strategy specifies the next move at every finite position where its player is to move; determination means that one player has a winning strategy.

Finite games are determined by backward induction, choosing the least move leading to a guaranteed win when several are available. In ZF one can also prove open determinacy, hence determinacy for closed payoffs. Here is the full open-payoff argument. Let $S$ be the finite positions $s$ with $[s]\subseteq A$, so reaching $S$ ensures a win for I. Starting with $W_0=S$, repeatedly add an I-position with some child already in $W$, and a II-position with every child already in $W$; take unions at limit stages. This increasing process stabilizes because the set of finite positions is a set: continuing strict enlargement through its Hartogs number would choose distinct new positions, contradicting that bound. Assign to each admitted position its least entry stage.

At an I-position in the final $W$, choose the least child of smaller entry stage. At a II-position in $W\setminus S$, every child has smaller entry stage. A play following this I-strategy cannot remain outside $S$ forever, since that would give an infinite strictly descending sequence of ordinals. It reaches $S$ and wins. Outside $W$, every child of an I-position remains outside $W$, and a II-position has at least one child outside $W$. Player II chooses the least such child. The play never reaches $S$, so it cannot belong to the open set $A$. The initial position is either inside or outside $W$, proving determination. For a closed payoff apply the same argument to the open complementary payoff for the other player, with the appropriate player assigned to each level. None of these strategies needs a choice principle because moves are natural numbers and least available moves are definable.

To refute simultaneous AD and the axiom of choice, assume choice and well-order all strategies of either player in length $\mathfrak{c}=2^{{\aleph }_0}$. There are exactly $\mathfrak{c}$ strategies for each player, and any fixed strategy has exactly $\mathfrak{c}$ compatible plays, since the opponent's successive moves are arbitrary. At stage $\alpha <\mathfrak{c}$, choose two fresh plays: $x_{\alpha }$ compatible with I's $\alpha$th strategy, and $y_{\alpha }$ compatible with II's $\alpha$th strategy. Fewer than $\mathfrak{c}$ plays have previously been excluded, so this is possible even if $\mathfrak{c}$ is singular. Put $A=\{y_{\alpha }:\alpha <\mathfrak{c}\}$. No $x_{\alpha }$ ever enters $A$. I's $\alpha$th strategy loses on $x_{\alpha }$, and II's $\alpha$th strategy loses on $y_{\alpha }$. Thus this game has no winning strategy for either player, and

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.

The Ehrenfeucht-Mostowski theorem says that an infinite first-order structure $M$, after Skolem expansion, has an elementarily equivalent model generated as a Skolem hull by distinct order-indiscernible sequence $(a_i{)}_{i\in I}$ for any prescribed linear order $I$. Every order automorphism of $I$ extends uniquely to an automorphism preserving this Skolem expansion. The reduct still models $\mathrm{Th}(M)$, but uniqueness of an automorphism in the reduct alone is not asserted. Iterate adjoining witness functions through all successively enlarged languages, so every existential formula in the final language has its own Skolem function. Write $M^{\ast }$ for the resulting expanded structure.

For the Ramsey theorem proof, add constants $c_i$ and require that they are distinct and that every two increasing tuples of the same length agree on every formula of the expanded language. Include $\mathrm{Th}(M^{\ast })$. A finite fragment mentions finitely many formulas and finitely many indices, say $r$ of them. Choose distinct $b_n\in M$. For each arity occurring in those formulas, color the increasing tuples of natural numbers by their finite truth vectors in $M^{\ast }$. Repeated applications of the infinite Ramsey theorem give an infinite subset homogeneous for all these finitely many colorings. Interpret the $r$ constants by its first $r$ elements, in their prescribed order. All the fragment's indiscernibility requirements hold. Thus compactness theorem produces a model $N^{\ast }$ of the whole scheme.

Let $H$ be the Skolem hull of the $c_i$. Whenever an existential formula with parameters in $H$ holds in $N^{\ast }$, its chosen Skolem witness belongs to $H$. The Tarski-Vaught test, proved by the existential step of induction on formulas, therefore makes $H\prec N^{\ast }$. For an order automorphism $\rho :I\to I$, defineTo compare different term presentations, collect all their indices into one increasing tuple. Indiscernibility transfers the equality of the terms to the transported tuple, so this map is well defined. The same argument transfers every relation; it preserves all functions by construction, and the map for ${\rho }^{-1}$ is its inverse. Since every hull element is a term in the generators, uniqueness follows.

For a genuinely ultraproduct proof, keep the distinct $b_n$ and choose a nonprincipal ultrafilter $\mathcal{U}$ on $\mathbb{N}$. For each finite ordered subset $F\subset I$, takewhere ${\mathcal{U}}_F$ is the ordered Fubini product of ultrafilters. Explicitly, a subset $A\subseteq {\mathbb{N}}^F$ is large if its indicator is true after successively applying “for $\mathcal{U}$-almost every $n_i$” in the increasing coordinate order. Projection to any sublist has exactly that sublist's product ultrafilter. Hence for $F\subseteq G$, pulling functions back along ${\mathbb{N}}^G\to {\mathbb{N}}^F$ gives an elementary embedding $M_F\to M_G$ by the Łoś theorem. These embeddings commute. Form their directed limit of elementary embeddings; each finite tuple lies in one stage, so induction on formulas makes the stage embeddings elementary.

At a stage containing $i$, let $a_i$ be the class of the coordinate function $\mathbf{n}\mapsto b_{n_i}$. If $i<j$, equality of these coordinate functions is small: for a fixed first coordinate there is only one possible equal second coordinate, and a singleton is not in $\mathcal{U}$. Thus $a_i\ne a_j$. For any increasing $i_1<\cdots <i_r$, the truth of $\phi (a_{i_1},\dots ,a_{i_r})$ is the same nested ultrafilter test applied to $\phi (b_{n_1},\dots ,b_{n_r})$, independent of the actual indices. This is precisely indiscernibility in the expanded language. Its Skolem hull, and the term-transport construction above, finish the second proof. Both constructions give the required model and the extended index automorphisms.

Here is the first incompleteness theorem in its modern consistency form: every consistent computably enumerable theory $T$ extending Robinson arithmetic is incomplete. The original Gödel sentence proof assumes omega-consistency to obtain both unprovabilities; we give that proof and the strengthening that removes this assumption. We also give the second incompleteness conclusion for theories extending Peano arithmetic.

First arithmetize syntax. Code strings and finite derivations by natural numbers. If the axioms of $T$ are merely computably enumerable, include the finite enumeration certificate for each nonlogical axiom used in a proof. The resulting proof-checking relation ${\mathrm{Prf}}_T(p,q)$ is primitive recursive. Finite strings and computation histories are coded by finite sequences, with bounded local verification of every step; these give arithmetic formulas representing the coding operations. In Robinson arithmetic every true or false instance with fixed numeral inputs is provable with the appropriate sign. Set

The diagonal lemma gives, for any formula $\theta (x)$, a sentence $D$ with $Q⊢D\leftrightarrow \theta (┌D┐)$. To see the construction, let $d(e)$ be the computable syntactic operation substituting the numeral for $e$ into the formula coded by $e$. Form the formula $\delta (x)=\theta (d(x))$, interpreting the displayed coding function through its arithmetic representation, and let $n=┌\delta ┐$. Then $D=\delta (\bar{n})$, and $d(n)=┌D┐$. The representation proves that fixed computation, giving the asserted equivalence.

Apply the diagonal lemma to $\neg {\mathrm{Prov}}_T(x)$, obtainingIf $T⊢G$, an actual finite proof has code $n$, so $Q$ proves its proof-checking instance and $T$ proves ${\mathrm{Prov}}_T(┌G┐)$. The fixed-point equivalence gives its negation, contradicting consistency. Hence $T⊬G$. For each standard numeral $n$, $Q$ proves $\neg {\mathrm{Prf}}_T(\bar{n},┌G┐)$ because there is no such proof. If $T⊢\neg G$, the equivalence gives $T⊢\exists p{\mathrm{Prf}}_T(p,┌G┐)$, contrary to omega-consistency. Thus the original proof gives two unprovabilities under that hypothesis. It also shows that $G$ is true in the standard natural numbers when $T$ is consistent.

For consistency alone use the Rosser sentenceIf $T⊢R$ with code $n$, consistency excludes every proof of $\neg R$. In particular the finitely many codes $q\le n$ all fail their primitive recursive proof tests. Robinson arithmetic verifies those finitely many failures and the actual proof at $n$, and hence proves $\neg R$, a contradiction. If $T⊢\neg R$ with code $m$, consistency excludes every proof of $R$. For $p<m$, Robinson arithmetic verifies all the finitely many failed proof tests. For $p\ge m$, it verifies that $q=m$ is a proof of $\neg R$ with $q\le p$. The elementary arithmetic dichotomy between $p<m$ and $m\le p$ therefore proves the entire displayed condition, hence $R$, again a contradiction. Thus

For the Gödel second incompleteness theorem, now assume $T\supseteq \mathsf{PA}$ and use its ordinary certified proof predicate. PA formalizes proof concatenation and the verification of a coded proof, giving the derivability conditions: if $T⊢A$ then $T⊢{\mathrm{Prov}}_T(┌A┐)$; and inside $T$,The first internal implication is certified by combining two proofs; the second is certified by producing the arithmetic proof that a given finite proof passes its check, with existential introduction. Apply them to $G\to \neg {\mathrm{Prov}}_T(┌G┐)$. From ${\mathrm{Prov}}_T(┌G┐)$, the two internal implications yield provability of both ${\mathrm{Prov}}_T(┌G┐)$ and its negation, and hence provability of $\perp$. ConsequentlyA proof of this consistency sentence in a consistent $T$ would prove $G$, which the first argument excludes. Therefore $\boxed{T⊬\mathrm{Con}(T)}$. This concerns the standard arithmetic consistency sentence and the stated effective, arithmetic hypotheses; it is not a prohibition on proving consistency in a stronger theory.

Use a relative consistency construction: a model of ZF gives one of ZFC through $L$, and we construct a model of New Foundations with urelements from it. In the language with membership and a unary predicate $S$, NFU requires that atoms have no members, extensionality holds between sets, and every stratified formula has a set extension. A type assignment gives equal variables equal types and raises type by one across membership. We prove the actual comprehension scheme, rather than invoke its consistency by name.

Start with a model $M\models \mathsf{ZFC}$ and Skolemize it. Apply the Ramsey construction from Question 1 to obtain increasing ordinal indiscernibles $(c_i{)}_{i\in \mathbb{Z}}$, all greater than $\omega +\omega$. The finite satisfiability step uses the infinite increasing list $\omega \cdot 3,\omega \cdot 4,\dots$ in the original model. Include the ordinal and ordering requirements in the finite truth colorings. Ramsey and compactness produce the indiscernibles; their Skolem hull $N$ still models ZFC. The index shift gives an external structure automorphism $j$ of $N$ with $j(c_i)=c_{i+1}$. Such a model is necessarily externally ill-founded: $(c_0,c_{-1},c_{-2},\dots )$ is an external descending ordinal sequence. No well-founded-model hypothesis is being smuggled in.

For every integer $i$, let $D_i$ be the external domain consisting of the objects of $N$ belonging internally to $V_{c_i}^N$. At type $i+1$, declare $S_{i+1}(y)$ iff $N$ says $y\subseteq V_{c_i}$. Use membership of $N$ only for flagged targets; an unflagged object has no typed members. A flagged object is a set of the preceding type. Set-extensionality holds since all members of a flagged set lie in $D_i$.

Every typed comprehension instance holds. Translate its finitely many typed quantifiers into quantifiers bounded by the appropriate sets $V_{c_r}^N$. Separation in $N$ gives its extension $A\subseteq V_{c_i}^N$ for the distinguished free variable of type $i$. Since $c_i+1\le c_{i+1}$, this subset is an object of $D_{i+1}$ and satisfies its set predicate. Also $j:D_i\to D_{i+1}$ is bijective and preserves the typed relations and flags. This is the required type-shifting automorphism.

Collapse to the single domain $D_0$ by definingIf $S(y)$, its image $j(y)$ is a subset of $V_{c_0}$, so its entire extension is visible in $D_0$. The flag is necessary: an unflagged object might otherwise have a partial visible extension. Flagged coextensive objects have equal images under $j$, by extensionality in $N$, and hence are equal; atoms have no $E$-members.

Now take a stratified untyped formula $\phi (x,\bar{a})$. Shift its type assignment so that $x$ has type zero, allowing negative integer types for other variables. Send a variable of assigned type $r$ to $j^r$ of its untyped value. Equality is preserved, and membership $uEv$ translates to flagged ordinary membership from type $r$ to type $r+1$. A set predicate translates to its flag at that type. Quantifiers correspond bijectively under $j^r:D_0\to D_r$. Thus induction on the formula gives exact agreement between its untyped truth and this typed translation.

Typed comprehension supplies an object $A\in D_1$, flagged at type one, containing exactly the type-zero solutions. Let $b=j^{-1}(A)\in D_0$. It is flagged at type zero, and for every $x\in D_0$, $xEb$ iff $x\in A$ iff $\phi (x,\bar{a})$. This proves all stratified comprehension, including an empty set and the universal set. We have constructedIf infinity is included in the convention for NFU, the same construction supports it: $\omega$ and its successor graph lie far below $c_{-1}$ and are fixed by $j$, since they are definable without parameters in $N$. The domain of the new set $\omega$ is the old $\omega$, since $j(\omega )=\omega$. An ordered pair in the new membership relation is $j^{-2}$ of the old Kuratowski pair. The old successor graph is fixed as a whole by $j$, so its elements are exactly these recoded pairs $(n,n+1)$ as $n$ ranges over $\omega$. It therefore supplies an actual new successor injection with proper range. This does not assume that $j$ fixes each nonstandard natural number. This is the rank-shifting automorphism construction of NFU; its logical ingredients are precisely the proved indiscernible-model construction and ordinary set separation in the typed domains.

The printed arrow is a partial-function arrow. Thus the central objects are partial computable functions $f:{\mathbb{N}}^k\rightharpoonup \mathbb{N}$, with total computable functions as the special case in which every input has an output. Here $\mathbb{N}$ includes zero; changing this convention by a computable shift changes none of the results. A program computing $f$ must halt with output $f(\mathbf{x})$ exactly on its domain, and run forever elsewhere. A finite program is a function in intension, whereas its possibly partial input-output map is a function in extension; many programs have the same extension.

A precise machine model is a register machine with finitely many instructions to increment a register, decrement it conditionally, jump, and halt. Registers hold natural numbers. A Turing machine instead uses a finite transition table, a finite alphabet and an unbounded tape. These models simulate one another: encode the finite nonblank tape, state and head position as numbers for the register simulation; conversely represent each register by a finite tape block and implement its increment and decrement by finite scans. Tuple inputs can be encoded by a primitive recursive pairing function. The equivalence of these formal models is a mathematical result. Their identification with every informal effective procedure is the Church–Turing thesis, rather than an additional mathematical theorem about an already formal notion.

There is also an algebraic description. Begin with zero, successor and projections, close under composition of partial functions and primitive recursion, and then under unbounded minimization. The primitive recursion scheme isApplied within the primitive recursive class it produces only total functions, by mathematical induction on $n$. Unbounded minimization searches $y=0,1,\dots$ for the first zero of $g(\mathbf{x},y)$; its output is defined only if that search reaches such a zero with every preceding necessary computation defined. Composition is likewise strict about the intermediate values it requires. These schemes compile into machine programs using finite subroutines, loops and an unbounded search loop.

For the converse, encode a machine's finite configurations and finite computation histories using Gödel numbering. Testing that a history starts with the specified input, that every adjacent pair follows the transition table, and that its final configuration halts is primitive recursive: all the tests are bounded by the finite code. Extracting the final output is primitive recursive too. For a suitable checking predicate $T$ and output decoder $V$ this proves the Kleene normal form theorem:The symbol $\simeq$ means equality of values and of definedness. A halting computation has a passing history code and every passing history has its actual output; a nonhalting computation has none. This proves that the partial recursive and machine-computable functions coincide, including their domains of divergence.

Finite programs can be effectively listed. Simulating the program with index $e$ gives a universal partial computable function $U(e,\mathbf{x})\simeq {\phi }_e(\mathbf{x})$. Fixing some inputs is effective syntactically: prepend instructions writing those constants and then call the original program. This proves the S-m-n theorem in this machine presentation. In particular, reductions that construct a program from numerical parameters really do produce its index effectively.

The primitive recursive functions are a proper subclass of the total computable functions. Enumerate all valid unary primitive recursive descriptions, interpreting invalid descriptions as zero. Evaluating any fixed valid description terminates by structural induction. Thus the diagonal map $d(n)=g_n(n)+1$ is total and computable, but cannot be one of the enumerated primitive recursive maps, since $d(e)\ne g_e(e)$. This is a total computable diagonal over primitive recursive syntax. The evaluator can terminate on every particular description without itself being primitive recursive.

In contrast, one cannot effectively enumerate exactly the programs for all total computable functions. If such an infinite enumeration were available, wait for its $n$th program and run it on $n$, then add one. Totality makes this another total computable function, while its diagonal disagrees with every listed function. Equivalently, there is no total computable universal evaluator listing precisely all total computable maps.

The halting problem is undecidable. If $H(e,x)$ decided whether program $e$ halts on $x$, construct a program $D$ which halts on input $e$ exactly when $H(e,e)$ says that it does not halt. Taking $e$ to be $D$'s own index gives a contradiction. The halting relation is nevertheless computably enumerable, since finite halting histories can be searched for.

More generally, a set is computably enumerable exactly when it is the domain of a partial computable function. From an enumeration, halt on $x$ when $x$ appears; in the other direction use dovetailing over all inputs of a partial program to enumerate its halting inputs. A set is a computable set exactly when both it and its complement are computably enumerable: dovetail the two searches and return the answer from the one that succeeds. Neither a semidecision procedure nor an unbounded search supplies a uniform negative answer.

Finally, the Rice theorem explains the scope of this obstruction. Let $P$ be a nontrivial property of the extension of a partial computable program. Choose a partial computable $g$ whose $P$-status differs from that of the nowhere-defined function. Given a program $e$ and input $x$, effectively form the program which, on $z$, first waits for $e(x)$ to halt and then computes $g(z)$. If $e(x)$ never halts its extension is nowhere defined; otherwise its extension is $g$. A decision procedure for $P$ would therefore decide the halting problem. Effective descriptions allow universal simulation and positive verification, but not a decision procedure for every semantic property or for termination.

Interpret the language of ordered rings in the standard natural numbers, with nonlogical symbols $0,1,+,\times ,<$. We give a single first-order formula $F(n,y)$ defining $y=n!$, rather than a separate expression with $n$ multiplication signs. The key is Gödel beta-function sequence coding. The remainder relationuses only the allowed symbols; all variables range over $\mathbb{N}$. With $c>0$, it assigns a unique remainder $r$ at each position $i$.

The factorial graph formula via remainder coding asserts that one code contains the initial value $1$, the final value $y$, and every recurrence step. Here is the fully expanded formula, with no remainder-function or factorial symbol:The first equation represents remainder $1$ at position zero: its omitted explicit remainder bound follows from $c>0$. The second line represents remainder $y$ at position $n$. The universally checked equations represent the adjacent remainders and impose multiplication by $i+1$. Uniqueness of remainders therefore forces them, successively, to be $0!,1!,\dots ,n!$, proving $F(n,y)\Rightarrow y=n!$ by mathematical induction. When $n=0$, the recurrence clause is empty and the two endpoint clauses force $y=1$.

Conversely, choose a positive $c$ larger than every value in the finite sequence $0!,1!,\dots ,n!$ and divisible by each positive integer at most $n$. The moduli $d_i=1+(i+1)c$, $0\le i\le n$, are pairwise coprime. Indeed, for $i<j$, a common divisor of $d_i,d_j$ divides $(j-i)c$ and is coprime to $c$, so divides $j-i$. Since $j-i$ divides $c$, the common divisor must be one. The Chinese remainder theorem gives a nonnegative $b$ with $b\equiv i!(\mathrm{mod}{d}_i)$ for every $i$. The chosen values are smaller than their moduli, so they are the actual remainders; the appropriate quotient witnesses then make $F(n,n!)$ true. ThusThe formula has fixed length, independent of $n$. For example, writing its displayed syntax in plain text with one-character variables, ordinary parentheses, and explicit logical connectives takes fewer than $1000$ characters and fewer than $500$ logical-symbol tokens. Its length is therefore $O(1)$ as a uniform definition of the graph. Numeral names for particular input values, if substituted for the variables, add their own encoding lengths. Over the ordered ring $\mathbb{Z}$, restrict every quantifier to nonnegative integers and require $n,y\ge 0$; this gives the same definition on its nonnegative part. It is the chosen arithmetic structure, not ring axioms alone, that makes the formula define factorial.

Use $\mathbb{N}=\{1,2,\dots \}$. If a bijection $f:\mathbb{N}\to \mathbb{N}$ maps $S$ onto the even natural numbers, its restriction is a bijection from $S$ onto an infinite set. Moreover, its restriction to the complement of $S$ maps onto the odd natural numbers. Both sets are therefore infinite.

Conversely, suppose that $S$ and its complement are infinite. Applying the increasing enumeration of an infinite subset of natural numbers to each givesFor completeness, successively choose the least unused member. The process never stops because the set is infinite, and it lists every member: an omitted member would have infinitely many selected natural numbers below it, which is impossible. DefineThis is injective on each list, their images are disjoint, and together their images cover $\mathbb{N}$. Thus it is a bijection and maps $S$ onto $2\mathbb{N}$. Both infinitude conditions are necessary and sufficient. If a convention includes zero in $\mathbb{N}$, index each list from zero and use $2j$, $2j+1$ instead.

A set is a countable set if it admits an injective function into the natural numbers; this includes finite sets and countably infinite sets. A countably infinite set can be listed by a bijection from $\mathbb{N}$.

Let $Z$ be the set of infinite binary sequences. Suppose it were countable and list all its members as $s^{(1)},s^{(2)},\dots$, writing $s_n^{(j)}$ for the $n$th entry of row $j$. A finite listing could be repeated to make such a list as well. Define the binary sequence $y$ by $y_n=1-s_n^{(n)}$. It differs from the $n$th row in coordinate $n$, for every $n$. Thus it belongs to $Z$ but is missing from the list, a contradiction. The set $Z$ is uncountable, by Cantor's diagonal argument.

The predicate is defined by the constructible hierarchy:Here $\mathrm{Def}(A)$ consists of subsets of $A$ definable in the set structure $(A,\in )$ by a first-order formula with finitely many parameters from $A$. To express $x\in L_{\alpha }$ in the language of set theory, assert that $\alpha$ is an ordinal and there is a hierarchy history of length $\alpha +1$ satisfying this recursion whose last stage contains $x$. Formulas are coded by natural numbers and truth is the definable satisfaction for a set structure. Transfinite recursion gives a unique history. The standard coding makes this predicate ${\Delta }_1$ over ZF; thus the constructible-level absoluteness over ZF applies to transitive models of ZF.

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.