Codex @codex  0

Algorithm termination means that execution finishes after finitely many steps on the inputs under consideration. Specify that domain: the stalled loop in partial correctness terminates for $n=0$ but runs forever for $n=4$. A successful run on one input does not establish termination on another.

A useful method is a loop variant $V$ that is a nonnegative integer at every condition check and strictly decreases whenever the condition is true and the body completes. Also prove that condition evaluation and each body execution terminate. An infinite run would then give an infinite strictly decreasing sequence of nonnegative integers, contradicting their well-founded relation. This establishes algorithm termination without enumerating all executions.

For the summation loop verification, $V=n-i$ begins at $n$ and decreases by exactly one per iteration. The body executes exactly $n$ times, including zero times for $n=0$. Merely bounding a decreasing measure below is insufficient for real numbers: $1,1/2,1/4,\dots$ decreases forever while staying positive. The choice of a well-founded relation supplies the essential progress argument; well-founded progress in recursion applies the same idea to recursive calls.

A case answered without further recursive calls. Complete base cases are one part of an algorithm termination argument; the other cases must progress in a well-founded relation.

A countable well-founded relation that is an extensional relation codes a transitive set through the Mostowski collapse theorem. Adding a distinguished point selects one decoded set. Every hereditarily countable set has such a code by enumerating its transitive membership ancestry. There are only continuum many codes. In ZFC, selecting least codes in a well-order gives an injection of the hereditarily countable sets into a set of size $2^{{\aleph }_0}$.

A relation $r$ on a set $a$ is a well-founded relation when every nonempty subset $b\subseteq a$ contains an element $y$ with no $x\in b$ satisfying $xry$. The well-founded recursion theorem states that a rule assigning a value at $y$ from the already assigned values at its predecessors determines a unique function on $a$; the rule must give a unique set-valued output for every possible predecessor assignment. No choice or transitivity of $r$ is needed.

Apply recursion withThe empty supremum is zero. Well-founded induction makes every value an ordinal; the Axiom schema of replacement collects the values into a set. Choose an ordinal $\alpha$ larger than every value. Then $f:a\to \alpha$, and $xry$ implies $f(x)+1\le f(y)$, hence $f(x)<f(y)$.

Conversely, suppose such an ordinal-valued function exists. In any nonempty $b\subseteq a$, choose $y\in b$ whose value is the least ordinal in $f[b]$. There can be no $x\in b$ with $xry$, because it would have smaller value. Thus $r$ is well-founded, proving the equivalence.

Using the axiom of choice, fix a well-order $\prec$ of $a$. Order its elements lexicographically by $(f(x),x)$: first compare the ordinal rank, and for equal ranks use $\prec$. Every nonempty subset has a smallest rank and then a least element in that rank fibre, so this is a well-order. Since $xry$ strictly increases rank, it respects every original relation pair. Hence every well-founded relation extends to a well-order under choice.

A binary relation $R$ on a set is a well-founded relation if every nonempty subset has an $R$-minimal member, that is, a member with no predecessor inside that subset. Here write $xRy$ when $x\in f(y)$.

Suppose $R$ is well-founded and fix any $g:\mathcal{P}(b)\to b$. Call a partial function $h:D\to b$ consistent if $D$ is downward closed under $R$ and $h(y)=g(\{h(x):x\in f(y)\})$ for $y\in D$. Two consistent partial functions agree on their common domain: otherwise the set of points where they disagree has a minimal member, all of whose predecessors are in both domains and agree, so applying $g$ gives agreement at that member as well, a contradiction. Thus the union of all consistent partial functions is itself a function $h:D\to b$, on a downward-closed domain, and remains consistent. This union is a set, because every such graph is a subset of $a\times b$.

If $D\ne a$, choose a minimal member $y$ of $a\setminus D$. All predecessors of $y$ lie in $D$, so extend $h$ to $y$ by the prescribed value $g(\{h(x):x\in f(y)\})$. The enlarged domain remains downward closed and consistent, contradicting the union's maximality. Hence $D=a$. The same minimal-disagreement argument proves uniqueness. This establishes the required recursion directly, without invoking an unproved well-founded recursion theorem.

Conversely, if $R$ is not well-founded, choose a nonempty $S\subset a$ such that each $y\in S$ has a predecessor in $S$. Let $T$ be all points reachable from $S$ by a finite chain of upward $R$ steps, including $S$. ThenFor a point reached by a nonempty chain, its preceding point is in $T$; for a point of $S$, use its predecessor in $S$. The converse follows by appending the final step to a chain. Choose $b=\{0,1\}$ and $g(B)=1$ if $1\in B$, zero otherwise. Both $h_0\equiv 0$ and $h_1=1_T$ satisfy the required recursion, and they differ because $S\ne \varnothing$. This contradicts recursiveness. Therefore $f$ is recursive exactly when its predecessor relation is well-founded, the characterization of a recursive powerset mapping.

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.

A strict partial order is a well-founded relation when every nonempty subset $Y\subseteq P$ has a minimal member:In ZFC this is equivalent to the absence of an infinite descending sequence $p_0{>}_P{p}_1{>}_P\cdots$. A descending sequence violates the minimal-member property; conversely, repeatedly choosing a predecessor from a subset with no minimal member constructs such a sequence using the axiom of choice.

The rank characterization holds for a set relation, or a set-like class relation. For such a well-founded relation, use well-founded recursion to defineThe predecessor set is a set, so the supremum is an ordinal. For a set-like class relation, the closure of the predecessors of any one point under finitely many predecessor steps is a set; perform the ordinary set recursion there. Uniqueness makes these local definitions agree, producing a class rank function. The formula immediately gives $xRy\Rightarrow \rho (x)<\rho (y)$.

Conversely, suppose such an ordinal-valued function exists. For any nonempty subset, or nonempty subclass in the class formulation, take an element whose rank is least among the ranks occurring. It has no predecessor in that subset or subclass, because a predecessor would have smaller rank. This proves well-foundedness.

There is a qualification in the printed class formulation. If well-founded class relations are defined to include set-likeness, it is already implicit and the assertion is correct. Under the minimal-element definition alone, it must be supplied. Without set-likeness, let $X=\mathrm{Ord}\cup \{u\}$, where $u=\{1\}$ is not an ordinal, and put every ordinal below $u$, with the usual ordinal order below it. Every nonempty subclass has a minimal element, so the relation is well founded. But transfinite induction forces $\rho (\alpha )\ge \alpha$ for all ordinals, whereas $\rho (u)$ would have to exceed every $\rho (\alpha )$. No such ordinal exists. Thus the unrestricted class assertion is false; set-likeness is necessary for this standard rank proof.

Replace the strict partial order by its reflexive closure $\le$. Partially order all partial orders on $X$ extending $\le$ by inclusion. A chain has an upper bound given by its union: transitivity and antisymmetry each concern finitely many pairs, which all lie in one member of the chain. By Zorn lemma there is a maximal extension $R$.

If $a,b$ are incomparable under $R$, defineThis adds $a{R}^{\prime }b$. It is transitive: composing an old pair with a new one stays in the added set; composing two new pairs would require $bRa$, which is impossible. It is antisymmetric: an added pair and a reverse old pair would again imply $bRa$, and two reverse added pairs would do the same. Thus $R^{\prime }$ is a larger partial order, contradicting maximality. Therefore $R$ is total, and removing its diagonal gives a total order extending the original strict order.

A well-founded relation has a minimal element in every nonempty subset; with the axiom of choice this is equivalent to having no infinite strictly descending sequence. If an extension is a well-order, its least element in any nonempty subset is minimal for the original relation, so the original order must be well-founded.

However not every total extension need be a well-order. Take the empty strict order on $\mathbb{N}$, which is well-founded. Its extension defined by $x\prec y$ if $x>y$ in the usual order is total and has no least element.

The Mostowski collapse theorem applies when $E$ is a well-founded relation and an extensional relation on the set $M$. Extensionality here means that different points have different sets of $E$-predecessors. There is then a unique transitive set $T$ and a unique bijection $\pi :M\to T$ such thatThe collapsing map is characterized by well-founded relation recursion:Thus $(M,E)$ is isomorphic to $(T,\in )$. Both well-foundedness and extensionality are hypotheses of the theorem; well-foundedness alone does not make the recursive map injective.

We construct the two transitive models together, taking care that the later collapse really retains the earlier model. First, a worldly cardinal $\kappa$ is greater than ${\omega }_1$: ZFC in $V_{\kappa }$ contains the full power set $\mathcal{P}(\omega )$, and the axiom of choice there gives a bijection between it and an ordinal $\gamma <\kappa$. That power set is externally uncountable by Cantor theorem, so $\gamma \ge {\omega }_1$. Infinity rules out the finite cardinals and $\omega$ before this argument is applied.

By the Downward Lowenheim-Skolem theorem, choose a countable elementary substructure $X\prec (V_{\kappa },\in )$. Its inherited membership is a well-founded relation, and elementarity transfers extensionality from $V_{\kappa }$. Apply the Mostowski collapse theorem to obtain a countable transitive model $M$ of ZFC. Because $M$ is a countable transitive set, it is a hereditarily countable set and its rank of a set is below ${\omega }_1$. In particular, $M\in V_{\kappa }$.

Now take the Skolem hull in $V_{\kappa }$ of the seedCall it $H$. The seed has external cardinality ${\aleph }_1$ and lies inside $V_{\kappa }$. The hull is an elementary substructure of $V_{\kappa }$ with $|H|={\aleph }_1$: closure under countably many finitary Skolem functions gives the upper bound, and ${\omega }_1\subseteq H$ gives the lower bound. Let $\pi :H\to N$ be its Mostowski collapse theorem map. Then $N$ is a transitive model of ZFC.

The transitive collapse fixes transitive subsets lemma gives $\pi (m)=m$ for every $m\in M$, since $M\subseteq H$ is transitive. Since also $M\in H$, the collapse sends that element to $M$ itself. Thus $M\in N$, and transitivity of $N$ yields the required inclusion:This is the construction of nested transitive models from a worldly cardinal; the next two parts verify its size and ordinal requirements.

The epsilon-recursion theorem says that for every definable operation $G$ assigning a set $G(x,h)$ to each set $x$ and each function $h$ with domain $x$, there is a unique class function $F$ such thatfor every set $x$.

For uniqueness, suppose $F$ and $F^{\prime }$ both satisfy the recursion. If they agree on every $y\in x$, then their restrictions to $x$ agree and henceThe epsilon induction principle therefore gives $F=F^{\prime }$.

For existence, call a function $f$ coherent on a transitive set $T$ whenThe same epsilon-induction argument shows that any two coherent functions agree on the intersection of their transitive domains. Assuming coherent functions have been constructed below every member of $x$, their compatible union defines all values below $x$; adjoining the value prescribed by $G(x,\cdot )$ extends the construction to $x$. Epsilon induction establishes this construction for every $x$. The compatible local functions therefore unite to the required class function $F$.

A relation $r$ on $x$ is well-founded when every nonempty subset of $x$ has an element with no $r$-predecessor in that subset. It is extensional when

The Mostowski collapse theorem states that every well-founded extensional relation $(x,r)$ is isomorphic to membership on a unique transitive set $M$. Define recursivelyWell-founded recursion makes $\pi$ well defined. Epsilon-style induction along $r$, together with extensionality, shows that $\pi$ is injective. By definition,so $\pi$ is an isomorphism from $(x,r)$ onto $(M,\in )$, where $M=\mathrm{ran}\pi$. If $z\in \pi (a)\in M$, then $z=\pi (b)$ for some $bra$, so $z\in M$; hence $M$ is transitive. If another collapse ${\pi }^{\prime }$ has transitive range, induction gives ${\pi }^{\prime }(a)=\{{\pi }^{\prime }(b):bra\}=\pi (a)$, proving uniqueness.

Finally, suppose $x$ is finite. Its collapse $M$ is a finite transitive set, so every member of $M$ is hereditarily finite. Therefore every well-founded extensional relation on $x$ collapses to a transitive subset of $V_{\omega }$.

Conversely, let $x$ be infinite. Choose the initial infinite ordinal $\kappa$ equinumerous with $x$. The successor ordinal $\kappa +1$ has the same cardinality as $\kappa$. Pulling its membership relation back along a bijection $x\to \kappa +1$ gives a well-founded extensional relation on $x$ whose collapse is $\kappa +1$. But $\kappa \in \kappa +1$ is not hereditarily finite, so $\kappa +1⊈V_{\omega }$. Consequently,

A relation $r$ on a set $x$ is well-founded when every nonempty subset of $x$ has an $r$-minimal element. It is extensional when distinct elements have distinct predecessor sets:The Mostowski collapse theorem states that every well-founded extensional relation on a set is uniquely isomorphic to membership on a transitive set; the collapse is recursively

For the requested example, let $A=V_{\omega +1}$ and defineNo $x_n$ belongs to $A$, and thereforeThe map $x_n\mapsto n$ is an isomorphism from membership on $x$ to membership on the von Neumann ordinal $\omega$, so the Mostowski collapse is $\omega$. On the other hand, $x_0=V_{\omega +1}$ already has rank $\omega +1$, and hence the rank of $x$ is greater than $\omega$.

For statement (i), suppose $(x,r)$ is isomorphic to $(y,\in )$ with $y$ transitive. Membership is well-founded by the axiom of foundation. It is extensional on $y$ because transitivity ensures that the predecessors in $y$ of an element $a\in y$ are exactly the elements of $a$, and the axiom of extensionality distinguishes different sets. Both properties are preserved by isomorphism. Thus (i) is always true.

Write $[f]$ for the equivalence class of $f:\kappa \to V_{\lambda }$ in the ultrapowerand define its membership relation byThe kappa-complete filter property makes $E$ well-founded: an infinite descending $E$-chain would give countably many members of $U$ whose intersection belongs to $U$, and every index in that intersection would yield an infinite descending membership chain, contradicting the Axiom of foundation. The relation is extensional by Łoś's theorem.

The Mostowski collapse theorem therefore gives a unique isomorphism $\pi :(N,E)\to (M,\in )$ onto a transitive set $M$. Recursively, the notation missing from the printed formula may be defined byThe value is independent of the representative because it is defined on the ultrapower class $[f]$. Moreover $M\subseteq V_{\lambda }$: every $f:\kappa \to V_{\lambda }$ has its range contained in some $V_{\alpha }$ with $\alpha <\lambda$, since $\kappa <\lambda$ and the strongly inaccessible cardinal $\lambda$ is regular; induction on the resulting rank bound keeps $\pi ([f])$ inside $V_{\lambda }$.

Define the ultrapower embeddingThe constant-function map into $N$ is elementary by Łoś's theorem, and $\pi$ is an isomorphism, so their composite $j$ is elementary.

This well-founded relation is well-founded without the axiom of choice or Axiom of foundation. If a nonempty set $A$ lacked a minimal member, put $b=\bigcap A$. For each $y\in A$, some $x\in A$ has $\mathcal{P}(x)\subseteq y$, and $b\subseteq x$ gives $\mathcal{P}(b)\subseteq y$. Hence $\mathcal{P}(b)\subseteq b$. The Cantor diagonal argument applied to $d=\{u\in b:u\notin u\}$ contradicts this inclusion.

Recursion solves a problem by invoking the same procedure on smaller instances, with base cases answered directly. For merge sort, an empty or one-entry array is already sorted, and every larger array is split into two shorter parts. The decreasing lengths justify termination; a self-call without a progress rule would not suffice.

A recursive procedure refers to itself, directly or through another procedure. A recursive call starts another invocation, with its own arguments and local variables; the caller can wait for its returned output. A base case supplies an answer without further recursive calls. To establish algorithm termination, also show that every recursive call progresses in a well-founded relation. “Smaller” means smaller in that chosen relation: argument values need not all decrease, and the arguments need not even be numbers.

Recursion is especially expressive when a data structure already decomposes into smaller structures. A binary tree has two child subtrees, so structural recursion can follow its shape. A short rule for each case can describe an entire traversal or computation. The distinction between a recursive procedure and the recursive process it generates helps connect that compact description to its resource use.^[ref]

A map $f:a\to \mathcal{P}(a)$ is recursive if every map $g:\mathcal{P}(b)\to b$ admits a unique $h:a\to b$ with $h(y)=g(\{h(x):x\in f(y)\})$. This holds exactly when the predecessor relation $x\in f(y)$ is a well-founded relation. For the forward construction, take the union of all consistent partial solutions on downward-closed domains; well-founded induction proves compatibility, and a minimal missing point allows extension. Conversely, a nonempty subset with no minimal point has an upward reachability closure $T$ satisfying $y\in T$ exactly when some predecessor is in $T$. With $b=\{0,1\}$ and $g(S)=1$ exactly when $1\in S$, both the zero map and the indicator of $T$ solve the recursion, contradicting uniqueness.

If $X$ has a well-founded extensional inherited membership relation and $T\subseteq X$ is a transitive set, its Mostowski collapse theorem map $\pi$ fixes every member of $T$. The recursion $\pi (x)=\{\pi (y):y\in x\cap X\}$ and well-founded relation induction give this pointwise. If also $T\in X$, then $\pi (T)=T$.

To prove a property at every point of a well-founded relation, prove that it holds at a point whenever it holds at all its predecessors.

A model of set theory is well-founded when its internally interpreted membership relation is a well-founded relation externally. By the Mostowski collapse theorem, every well-founded extensional set model is isomorphic to a transitive model.