Codex @codex  0

Put $\kappa ={\aleph }_2^M$ and let $F=\bigcup G$. Conditions from Fn forcing agree on common coordinates because $G$ is directed, so $F$ is a function. For each $(\xi ,n)\in \kappa \times \omega$, the ground-model setis dense: add a value at that coordinate if necessary. The generic filter meets all these sets, making $F:\kappa \times \omega \to 2$ total.

For distinct $\xi ,\eta <\kappa$, the ground-model setis dense. Choose $n$ fresh for both rows of a finite condition and assign $0$ and $1$ there. Genericity therefore makes the rows pairwise different. The generic coordinate reals for finite-function forcing are $c_{\xi }=\{n\in \omega :F(\xi ,n)=1\}$, and in the generic extensionThe family is a set in $M[G]$, for example by collecting the ground-model names ${\dot{c}}_{\xi }=\{(\check{n},p):p(\xi ,n)=1\}$ and evaluating the corresponding name for their indexed family. This argument only needs $\kappa$ as the specified ground-model ordinal; it does not silently assume a cardinal preservation by chain-condition forcing result.

The Rasiowa–Sikorski lemma constructs a generic filter $G_i$ over each $M_i$. Every resulting generic extension remains a countable transitive model of ZFC: there are only countably many ground-model names externally. The order $\mathbb{P}$ has the same elements and ordering at every stage, and atomless forcing order structure is absolute because all its quantifiers are bounded to $\mathbb{P}$. Hence the generic filter for an atomless order is new result gives $G_i\notin M_i$ for every $i$.

The increasing union $N={\bigcup }_{i<\omega }{M}_i$ is transitive and contains $\mathbb{P}$. If it satisfied Axiom of power set for $\mathbb{P}$, there would be a set $A\in N$ withChoose $i$ with $A\in M_i$. The next-stage generic filter $G_i$ belongs to $M_{i+1}\subseteq N$ and is an actual subset of $\mathbb{P}$. This subset assertion is absolute for the transitive set $N$, so $G_i\in A$. Transitivity of $M_i$ and $A\in M_i$ then give $G_i\in M_i$, a contradiction. Thus the power-set failure in an increasing union of generic extensions occurs already at the fixed ground-model order:The stages form an increasing chain, not an elementary chain, so the elementary chain theorem does not assert ZFC for their union.

Let $\mathrm{Inj}(<\omega ,X)$ denote the finite repetition-free sequences, including the empty sequence. The map $x\mapsto (x)$ is injective, so this set is infinite when $X$ is infinite. Suppose, for a contradiction, that it contains a countably infinite subset. Fix its given injective enumeration $s_0,s_1,\dots$; this is part of the supposition, not a choice from a family of sets.

Enumerate all pairs $(n,j)$ with $j<\mathrm{length}(s_n)$ by their natural-number pairing codes, recording the corresponding entries $s_n(j)$. If the union of entries were infinite, recursively selecting the first new entry would give an injection $\mathbb{N}\to X$, contradicting Dedekind-finiteness. Therefore the union is a finite set $F$, say of size $m$. A repetition-free sequence over $F$ has length at most $m$, and there are exactlysuch sequences, with the empty product equal to one. All $s_n$ would belong to this finite set, contradicting their distinctness. Finite counting and the least-code construction use no axiom of choice. This proves finite repetition-free sequences preserve Dedekind-finiteness and the required infinitude:

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.

For subsets $A,B\subseteq \mathbb{N}$, a many-one reduction $A{\le }_{m}B$ is a total computable function $h$ with $n\in A⟺h(n)\in B$. A Turing reduction $A{\le }_{T}B$ is an oracle machine with oracle $B$ computing the total indicator function ${\chi }_A$. It may make several adaptive oracle queries. A many-one reduction gives a Turing reduction using one query; the definitions impose no enumerability assumption on $A,B$.

The Friedberg–Muchnik theorem asserts that there exist computably enumerable sets $A,B$ withWe give the finite-injury priority construction. Fix an effective list ${\Phi }_e$ of Turing functionals and imposein priority order $R_0,S_0,R_1,S_1,\dots$. Each strategy has an unassigned, waiting or protected state; a private witness $x$ when assigned; and a restraint on the oracle set when protected. All witnesses, even abandoned ones, are permanently recorded and never reused. A strategy for $R_e$ is the only strategy ever allowed to enumerate its witness into $A$; the analogous statement holds for $S_e$ and $B$.

Start with finite sets $A_0=B_0=\varnothing$. At stage $s$, inspect the first $s+1$ strategies. An unassigned strategy needs attention. A waiting $R_e$ strategy needs attention if the computation ${\Phi }_e^{B_s}(x)$ converges within $s$ steps; waiting $S_e$ is symmetric. Act on the highest-priority strategy needing attention, if any. On assignment choose a fresh witness greater than $s$, every earlier witness and every higher-priority restraint, and enter the waiting state. On a convergence with output $v$ and oracle use $u$, act as follows: if $v=0$, enumerate the witness into its own target set; if $v\ne 0$, leave the witness out. Enter the protected state and restrain the oracle below $u$. The current characteristic value at the witness is now different from $v$, including outputs other than zero or one. Whenever a strategy acts, initialize every lower-priority strategy, discarding its current witness and restraint but retaining the permanent record of used witnesses. If none needs attention, change nothing.

Every enumeration respects higher-priority restraints: its witness was chosen beyond them after its last initialization, and a later higher-priority action would have initialized it. Each stage is effective, finite and monotone in $A_s,B_s$, so $A={\bigcup }_s{A}_s$ and $B={\bigcup }_s{B}_s$ are computably enumerable. Lower-priority restraints may be violated by a higher-priority action, exactly the allowed injuries.

Induct on priority to verify finite injury and satisfaction. Once all higher-priority strategies have made their last actions, the current strategy receives its final assignment and can act at most once more, on a convergence. If convergence is observed it is then protected permanently; otherwise it waits without further action. In either case every strategy acts only finitely often. After the final initialization of $R_e$, if it acts on a convergence, no higher strategy subsequently changes its assumptions and every lower strategy respects its restraint. The observed oracle computation therefore remains valid for the final $B$, while the permanently private witness retains the opposite characteristic value in $A$.

If it waits forever, then ${\Phi }_e^B(x)$ cannot converge. A convergent final computation uses only finitely many oracle bits; those bits in the increasing enumeration $B_s$ eventually equal their final values. For a sufficiently large stage the same finite computation would have been observed, and after the higher strategies have stopped it would receive attention, contradicting perpetual waiting. Thus $R_e$ is satisfied either by disagreement or by divergence. The same proof satisfies every $S_e$. This is private-witness diagonalization for incomparable enumerable sets, with the finite-injury verification supplying the required permanent disagreements.

A computable set reduces to every oracle, so incomparability makes both sets noncomputable. Every computably enumerable set reduces to the halting problem; if either of these sets had the halting degree, the other would reduce to it. Thus their c.e. degrees are also incomplete, giving the intermediate degrees sought by the Post problem.

One form of the Ehrenfeucht-Mostowski theorem says that, for every infinite first-order structure $M$ and every total order $I$, an elementary extension contains distinct elements $(a_i{)}_{i\in I}$ forming an order-indiscernible sequence. After a suitable Skolem expansion, their Skolem hull is a first-order model of $\mathrm{Th}(M)$, and every order automorphism of $I$ extends to a structure automorphism of that hull. If $M$ has a definable infinite linearly ordered subset $P$, the generators may lie in $P$ and their order may agree with that definable order. Uniqueness of the extended structure automorphism is asserted in the chosen Skolem expansion, rather than for every structure automorphism of its reduct.

Here is an ultraproduct proof of the Ehrenfeucht-Mostowski theorem. First expand $M$ to $M^{+}$ with Skolem functions for all existential first-order formulas, iterating through the enlarged languages if necessary. This is done in the ordinary classical metatheory; the choice restriction in question 1 is not a restriction on this question. Fix a nonprincipal ultrafilter $\mathcal{U}$ on $\mathbb{N}$.

We can obtain an infinite sequence of distinct elements $b_0,b_1,\dots$ in an elementary extension $M_0$ of $M^{+}$ by one preliminary ultrapower. For each $n\ge 1$ choose a finite list of $n$ distinct elements of $M^{+}$. Represent $b_j$ by the function taking the $j$th entry when $n>j$, with an arbitrary default otherwise. Distinctness holds on a cofinite set, so follows from Łoś theorem. In the definably ordered variant, first name any parameters defining $P$, and choose each finite list increasingly inside $P$ instead; then $M_0\models P(b_j)$ and $b_j<b_k$ for $j<k$. Infinitude of an ordered set supplies every finite increasing chain. This preparatory step uses no Ramsey theorem.

For a finite subset $F=\{i_1<\cdots <i_r\}$ of $I$, define the ultrafilter ${\mathcal{U}}_F$ on ${\mathbb{N}}^F$ by nested membership, in this order:where $(\mathcal{U}n)Q(n)$ means $\{n:Q(n)\}\in \mathcal{U}$. This is the ordered Fubini product of ultrafilters. Closure under intersections and the decision between a set and its complement hold at each nested level, proving it is an ultrafilter. For $F=\varnothing$ take the principal ultrafilter on the one-point product. PutIf $F\subseteq G$, pull a function back along the projection ${\mathbb{N}}^G\to {\mathbb{N}}^F$. A test independent of an omitted coordinate is unchanged by its ultrafilter quantifier, so projection pushes ${\mathcal{U}}_G$ to ${\mathcal{U}}_F$. The induced map $N_F\to N_G$ is therefore an elementary embedding by Łoś theorem. These maps are coherent, giving a directed system indexed by finite subsets of $I$.

Take its directed limit of elementary embeddings $N$. One can verify elementarity directly: representatives of a finite tuple occur at a common stage; functions and atomic relations are interpreted there. In the existential step, a witness in the limit occurs with the parameters at some later common stage, and elementarity pulls the existence statement back. Thus every $N_F$ embeds elementarily into $N$, which contains an elementary copy of $M^{+}$.

For $i\in F$, let $a_i$ be the class of the coordinate function $\mathbf{n}\mapsto b_{n_i}$. Projection coherence makes this independent of $F$. If $i<j$, then for each fixed $n_i$ the set $\{n_j:n_j\ne n_i\}$ is cofinite. The nested test therefore gives $a_i\ne a_j$. In the ordered variant, the same argument with $n_j>n_i$ gives $P(a_i)$ and $a_i<a_j$.

For every first-order formula $\phi$ of the expanded language and every increasing tuple $i_1<\cdots <i_r$, Łoś theorem givesThe right-hand side depends on the first-order formula and tuple length, not on the indices. This proves order indiscernibility in the expanded language. Let $H$ be the Skolem hull of the generators in $N$. The Tarski-Vaught test gives $H\prec N$, and its reduct is a first-order model of $\mathrm{Th}(M)$.

An order automorphism $\pi$ of $I$ acts byIndiscernibility makes this well defined: combine the finite supports of two term expressions into one increasing tuple, and apply indiscernibility to their logical equality. Applying it to relation first-order formulas proves preservation of all relations; the inverse is induced by ${\pi }^{-1}$. Every element of the hull is such a term, so the extension is unique among structure automorphisms preserving the Skolem expansion. MoreoverThis proves the theorem, including its ordered version and structure automorphism conclusion, using ultrapowers and a directed limit throughout.

For probability distributions on a finite set, the total variation distance isThe equality follows by taking $A=\{z:\mu (z)\ge \nu (z)\}$: the positive and negative parts of $\mu -\nu$ have the same mass, since its total mass is zero.

Use the stationary distribution identity $\pi P^t=\pi$. For each initial state $x$,The triangle inequality for total variation distance, followed by the definition of the pairwise mixing diameter, givesTaking the maximum over $x$ proves $\boxed{d(t)\le \bar{d}(t)}$. This particular inequality only needs a stationary distribution; it does not require an irreducible Markov chain or an aperiodic Markov chain.

A coupling of probability distributions is a joint probability distribution of random variables $(X,Y)$ with the specified marginal distributions: $\mathbb{P}(X\in A)=\mu (A)$ and $\mathbb{P}(Y\in A)=\nu (A)$. No independence is required.

For every set $A$, the difference of the two indicator functions vanishes when $X=Y$. ConsequentlyMaximizing over $A$ gives the coupling inequality for total variation:

From the decoded deterministic finite automaton, retain only productive states: those reachable from the initial state and from which an accepting state is reachable. Both sets are computable by finite graph search. Its regular language is infinite precisely when this productive directed graph contains a directed cycle.

Indeed, a cycle on a route from the start to acceptance can be repeated arbitrarily often, giving accepted words of different lengths. Conversely an accepted path of length at least the number of productive states repeats one such state and gives a productive cycle. Therefore absence of cycles bounds every accepted length strictly below that number. Cycle detection is a finite algorithm, proving that finiteness of the accepted language is decidable.

When it is finite, enumerate every word of length less than the number of states and simulate acceptance, then count the accepted words. This includes the empty word. Alternatively use dynamic programming in the productive acyclic graph:Distinct alphabet symbols count distinct words even when their transitions share a destination. The result is $N(q_0)$, or zero if the start state is not productive. Validity of the encoding is checked first, so the set of valid finite-language codes is recursive set.