Codex @codex  0

Here a monochromatic set must mean an infinite homogeneous set for a colouring: every singleton is a finite monochromatic set. The requested phenomenon holds for every finite $n\ge 2$. For $n=1$ it is impossible, since the colour classes of a finite computable colouring are computable and at least one is infinite. We treat this necessary qualification explicitly.

We construct a finite-injury computable colouring of pairs with no infinite computably enumerable homogeneous set, which is stronger than the requested absence of a recursive one. Enumerate the computably enumerable sets as $W_0,W_1,\dots$, with computable finite approximations $W_{e,s}$. Requirement $e$ seeks distinct markers $a_e,b_e\in W_e$. At stage $s$, consider indices $e\le s$ not currently assigned markers. Choose the least one, if any, for which $W_{e,s}$ has two elements outside all markers of higher-priority indices $d<e$. Assign two such elements as its markers, using a fixed least-element rule, and cancel all markers at lower-priority indices. Do nothing if no such index exists. The active markers are therefore pairwise distinct at every stage.

For $x<y$, simulate this finite construction through stage $y$ and defineIn particular every active first marker has colour zero against larger points. This is a total computable function: no question about eventual enumeration or eventual stabilization is used in computing a given pair.

Induction on $e$ proves finite injury. Once the finitely many higher requirements have stabilized, requirement $e$ is never cancelled again. If it has markers they stay fixed. If $W_e$ is infinite, it eventually supplies two points outside the finite collection of higher markers, so it becomes eligible and is assigned markers; only finitely many higher indices could delay its assignment. Thus an infinite $W_e$ eventually has permanent distinct markers $a_e,b_e$. Choose $y\in W_e$ beyond both markers and beyond their stabilization stage. ThenSo $W_e$ is not homogeneous. Every infinite recursive set is computably enumerable, proving the desired obstruction. For $n>2$, colour an increasing $n$-tuple by the pair formed by its first two elements. Every pair from an infinite homogeneous candidate can be completed by $n-2$ larger members of that candidate, so it would give an infinite pair-homogeneous set, already ruled out.

The uncountable positive theorem is the Erdős-Rado theorem for finite arities. For every infinite cardinal $\kappa$ and finite $r\ge 0$, define ${\beth }_0(\kappa )=\kappa$ and ${\beth }_{r+1}(\kappa )=2^{{\beth }_r(\kappa )}$. ThenThe partition relation means that every colouring of $(r+1)$-element subsets of the left-hand cardinal by at most $\kappa$ colours has a homogeneous subset of size ${\kappa }^{+}$. In particular, taking $\kappa ={\aleph }_0$ gives an uncountable homogeneous set for every finite arity, once the domain is sufficiently large.

We prove the end-homogeneity lemma needed for induction. Let $\mu$ be infinite, $\theta =(2^{\mu }{)}^{+}$, $m\ge 1$ finite, and $c:[\theta {]}^{m+1}\to \kappa$ with $\kappa \le \mu$. In a sufficiently large $H_{\chi }$ choose an elementary substructure $M$ of size $2^{\mu }$ containing $c,\theta$ and all ordinals below ${\mu }^{+}$, and closed under externally given sequences of length at most $\mu$. Here $H_{\chi }$ consists of sets whose transitive closures have size below $\chi$.

To justify that closure, begin with a hull containing the indicated parameters and ordinals. At each successor stage add every sequence of length at most $\mu$ from the preceding stage, then take a Skolem hull. There are at most $(2^{\mu }{)}^{\mu }=2^{\mu }$ such sequences. Iterate for ${\mu }^{+}$ stages and take elementary unions at limits. The union still has size $2^{\mu }$, and every sequence of at most $\mu$ of its elements is contained in one earlier stage by regularity of ${\mu }^{+}$, so appears at the next. This proves the claimed closed first-order model rather than assuming its existence.

Let $\beta =\sup (M\cap \theta )<\theta$. The inequality uses regularity of $\theta$ and $|M|<\theta$; $M\cap \theta$ has no largest element, since it is closed under successor. Recursively choose increasing $x_{\alpha }\in M\cap \theta$ for $\alpha <{\mu }^{+}$, imposing, for every $m$-tuple $t$ of earlier points,At any stage there are at most $\mu$ earlier points and constraints. Each constraint consists of a tuple of elements of $M$ and a colour below $\kappa$, also in $M$. The entire constraint code therefore belongs to $M$ by closure. The bound above the previous points belongs to $M$ as well. Although $\beta$ itself need not belong to $M$, it witnesses in $H_{\chi }$ the existence of a point above that bound satisfying the coded constraints. Elementarity supplies such a point inside $M$. This proves the recursion.

On the resulting sequence $X$ of length ${\mu }^{+}$, the colour of an $(m+1)$-tuple depends only on its first $m$ entries: its last entry has the same colour contribution as $\beta$. This is the required closed elementary-submodel construction of an end-homogeneous sequence.

Now prove the theorem by induction on $r$. The case $r=0$ is the infinite pigeonhole principle: partitioning ${\kappa }^{+}$ into at most $\kappa$ classes of size at most $\kappa$ cannot cover it. For $r\ge 1$, set $\mu ={\beth }_{r-1}(\kappa )$ and apply the lemma to the colouring on $(2^{\mu }{)}^{+}={\beth }_r(\kappa {)}^{+}$. Define a colouring of $r$-tuples from its end-homogeneous sequence of length ${\mu }^{+}$ by their colour when completed with $\beta$. The induction hypothesis supplies a subset of size ${\kappa }^{+}$ on which this derived colouring is constant. Every original $(r+1)$-tuple from that subset has the derived colour of its first $r$ entries, and is therefore monochromatic. This completes the proof.

The unrestricted infinite-exponent situation is very different under AC. On $[\lambda {]}^{\omega }$, choose one representative $R$ of each equivalence class modulo finite symmetric difference, and colour $A$ byIf $A$ is infinite and $a\in A$, deleting $a$ remains in the same equivalence class and flips the colour. Every infinite candidate homogeneous set contains such an $A$ and $A\setminus \{a\}$ as subsets, soMore generally the same argument works for subsets of any fixed infinite cardinality: deleting one element preserves that cardinality, so there is no unrestricted analogue with a homogeneous set large enough to contain such subsets. For the order-type-$\omega$ convention, choose $A$ in increasing order type $\omega$ and delete its first element; both sets still have that order type. Thus the distinction from the finite-arity theorem is genuine, not merely a notational ambiguity. This argument uses choice of representatives and is not a claim about every definability-restricted infinite-arity colouring.

For sets $A,B\subseteq \mathbb{N}$, many-one reducibility means there is a total computable function $h$ such thatTuring reducibility $A{\le }_{T}B$ means that a Turing machine with oracle $B$ computes the indicator function ${\chi }_A$, halting on every input. A many-one reduction supplies a Turing reduction by computing $h(x)$ and making one membership query, so $A{\le }_{m}B$ implies $A{\le }_{T}B$.

The Friedberg–Muchnik theorem states that there are computably enumerable sets $A,B$ with $A/{\le }_{T}B$ and $B/{\le }_{T}A$. We prove this by a finite-injury priority construction. Fix an effective enumeration $({\Phi }_e)$ of the oracle Turing functionals and arrange the requirements in the orderA requirement owns a private witness, a success flag and a priority restraint on its oracle set. All witnesses ever chosen are distinct. An $R_e$ witness $x$ is reserved outside $A$, and only $R_e$ may enumerate that number into $A$; an $S_e$ witness is treated symmetrically. A priority restraint $r$ forbids lower-priority requirements from adding numbers less than $r$ to the specified oracle set. Initializing a requirement abandons its witness, clears its success flag and sets its priority restraint to zero; enumeration into $A$ or $B$ is never undone.

At stage $s$ consider the first $s+1$ requirements and serve the highest-priority one requiring attention. An unsuccessful requirement requires attention if it has no witness, or its current witness has a stage-$s$ oracle computation with output zero, found within $s$ steps. If there is no such requirement, do nothing. When a requirement with no witness is served, choose a fresh number larger than $s$, all previously chosen witnesses and all current higher-priority priority restraints. When an $R_e$ with a witness $x$ and observed computation ${\Phi }_e^{B_s}(x)=0$ is served, enumerate $x$ into $A$, mark it successful, and restrain $B$ below the use of that computation. The use is one more than the largest queried oracle position, or zero if there were no queries. An $S_e$ acts in exactly the same way with $A,B$ interchanged. After either kind of service, initialize every currently assigned lower-priority requirement; the remaining lower priorities are already in their initial state.

This is an effective stage construction with finite sets $A_s,B_s$, and $A={\bigcup }_s{A}_s$, $B={\bigcup }_s{B}_s$ are computably enumerable. Every enumeration respects all higher-priority priority restraints: its private witness was selected above them, and any later service to a higher-priority requirement would have initialized it before it could act. We do not need to restrain a computation whose output is nonzero; a persistent nonzero output already disagrees with an unenumerated witness.

We verify the finite injury assertion by induction along the priority order. After the last service to requirements above a fixed requirement $Q$, the requirement $Q$ is never initialized again. It can be served at most twice thereafter, once to choose its final witness and once to diagonalize. Whenever it needs attention it is eventually served, since the higher-priority requirements have ceased acting and each later stage considers a longer initial segment. Thus $Q$ has a final witness and makes only finitely many actions; this proves the induction and justifies the assumed last service above it.

For a final $R_e$ witness $x$, if the diagonalization occurs then ${\chi }_A(x)=1$, while preservation of a restrained oracle computation applies: its zero computation is preserved permanently because higher priorities no longer act and lower priorities respect the priority restraint. Thus ${\Phi }_e^B(x)=0\ne {\chi }_A(x)$. If it never occurs, then ${\chi }_A(x)=0$. Were ${\Phi }_e^B(x)=0$, that convergent computation would use finitely many oracle answers. Because $B_s$ increases to $B$, those finitely many answers eventually stabilize, and a sufficiently late stage would discover the zero computation and cause diagonalization. This contradicts its never occurring. So in this case ${\Phi }_e^B(x)$ is undefined or nonzero and again disagrees with ${\chi }_A$. The identical argument verifies every $S_e$.

All the requirements hold, proving the theorem. Both sets are noncomputable: a computable set is Turing reducible to every oracle. Moreover, every computably enumerable set is Turing reducible to the diagonal halting set $K$, and neither $A$ nor $B$ can have its Turing degree, since that would make it compute the other set. HenceThis also gives many-one incomparability and answers the existence of intermediate computably enumerable Turing degrees.

A many-one reduction $A{\le }_{m}B$ is a total computable function $f:\mathbb{N}\to \mathbb{N}$ such thatA Turing reduction $A{\le }_{T}B$ is an oracle machine which, with membership oracle $B$, halts on every input and computes the indicator function ${\chi }_A$. It may make finitely many adaptive queries on each input. A many-one reduction gives a Turing reduction by a single query, but Turing reducibility allows more general procedures.

The Friedberg–Muchnik theorem states that there are computably enumerable sets $A,B$ with incomparable Turing degrees:Here is a finite-injury priority construction proving it. Effectively enumerate all Turing functionals $({\Phi }_e)$. Arrange the requirements in the priority orderEquality would require the Turing functional to be total and give the correct bit at every input; one disagreement or one undefined input defeats it.

Start with $A_0=B_0=\varnothing$ and enumerate elements without ever removing them. A strategy has a private witness, a flag recording whether it has acted, and a restraint on its oracle. Every new witness is larger than every previously assigned witness and every current higher-priority restraint. Retired witnesses are never reused. The only possible enumeration of a witness is by its owner, so an unacted witness remains outside its target set.

The strategy for $R_e$ chooses a witness $x$ and waits for a stage at which the bounded simulation givesOn seeing this, put $x$ into $B$, declare the strategy acted, and impose restraint $u$ on $A$, where $u$ is the oracle use: one more than the largest queried number, or zero if there were no queries. Initialize every lower-priority strategy, discarding its current witness, acted flag and restraint. An acted strategy does nothing further until initialized. The strategy for $S_e$ is identical with $A,B$ interchanged. Waiting specifically for zero is enough: if the eventual output is nonzero while the witness stays out, it already disagrees with the target indicator function.

For a completely effective schedule, at stage $s$ visit the first $s+1$ strategies in priority order. Assign an unassigned witness when visited. Simulate each unacted strategy's computation for at most $s$ steps with the current finite oracle. If some strategy can act, perform the first such action and end the stage; otherwise end after all visits. All steps are finite and algorithmic, so the limiting $A,B$ are computably enumerable sets.

Every lower-priority enumeration respects higher-priority restraints. When its witness was chosen it lay above these restraints. Any subsequent action of a higher-priority strategy would have initialized it, so its current witness remains safe to enumerate. The initialization of all lower strategies also removes their obsolete restraints before they can obstruct a legitimate higher-priority action.

We verify finite injury by mathematical induction on priority. The first strategy is never injured and acts at most once. If all predecessors of a strategy act finitely often, there is a last stage when a higher-priority action initializes it. It is subsequently visited, chooses its permanent witness, and acts at most once. Thus it too acts finitely often and all its lower-priority strategies suffer only finitely many injuries. The scheduling cannot starve a fixed strategy: after the finitely many higher-priority actions, all sufficiently large stages visit it.

Consider the final uninjured $R_e$ with witness $x$. If it acts, then $x\in B$ permanently, and every later lower-priority enumeration into $A$ respects its restraint. No later higher-priority action occurs. The preserved computation is thereforeIf it never acts, $x\notin B$. Were ${\Phi }_e^A={\chi }_B$, the final computation on $x$ would halt with zero and have finite oracle use. The finitely many oracle bits it queries eventually stabilize, and a sufficiently late bounded stage simulation would see exactly this zero computation. The strategy would then act, a contradiction. Hence $R_e$ holds in this case too. The same reasoning proves every $S_e$.

All possible Turing reductions in both directions are excluded. This proves the Friedberg–Muchnik theorem; in particular both constructed Turing degrees are noncomputable, since a computable set is Turing reducible to every oracle.

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.

A many-one reduction $A{\le }_{m}B$ is a total computable function $f$ with $x\in A⟺f(x)\in B$. A Turing reduction $A{\le }_{T}B$ is an oracle machine which decides $A$ with oracle $B$. It may make several adaptive queries and combine their answers. Every many-one reduction is a Turing reduction, by asking the single question $f(x)\in B$. The converse fails: for the diagonal halting set $K$, its complement is Turing-reducible to $K$ by reversing one oracle answer, but is not many-one reducible to $K$. Such a reduction would make the complement computably enumerable, contradicting undecidability of the halting problem.

The Friedberg–Muchnik theorem asserts that there are computably enumerable sets $A,B$ with incomparable Turing degrees:Here is a finite-injury priority construction proving it. Enumerate all Turing functionals ${\Phi }_e$ and put the requirements in the priority orderStart with $A_0=B_0=\varnothing$. Each requirement has a fresh witness, a waiting or acted status, and a restraint on the other set. A restraint $u$ forbids lower-priority strategies from enumerating numbers below $u$ into that oracle. Globally remember all previously chosen witnesses, including abandoned ones, and never choose any of them again.

For $R_e$, choose an unused witness $x$ outside $A_s\cup B_s$, larger than the stage and every current higher-priority restraint. Keep it out of $A$. Wait until the bounded simulation ${\Phi }_{e,s}^{B_s}(x)$ converges with value zero. If this happens, enumerate $x$ into $A$, put a restraint $u$ on $B$, where $u$ is one more than the largest oracle query in the observed computation, and mark the strategy acted. For $S_e$, interchange $A$ and $B$.

At stage $s$, consider the first $s+1$ requirements. Choose the highest-priority one needing a witness or waiting with an observed zero computation. Perform its indicated action, then initialize all lower-priority requirements: abandon their witnesses, clear their restraints, and reset their status. Do nothing if no requirement needs attention. Since witness selection respects higher restraints, and higher actions initialize every lower strategy, all protected computations are respected by lower-priority enumerations. Each stage is a finite effective calculation, so $A={\bigcup }_s{A}_s$ and $B={\bigcup }_s{B}_s$ are computably enumerable sets.

Verify by induction along the priority order that every requirement is initialized only finitely often and acts only finitely often. The highest requirement chooses one witness and can diagonalize at most once. After all higher requirements have finished acting, the next requirement is never again initialized; it obtains a final witness and can diagonalize at most once. This proves finite injury for every requirement and ensures that no requirement is permanently starved by higher attention.

Consider $R_e$ after its last initialization. If it acts, its witness belongs to $A$, while the protected computation with oracle $B$ remains zero: higher strategies no longer act and lower ones respect its restraint. Thus ${\Phi }_e^B(x)\ne {\chi }_A(x)$. If it never acts, its private witness remains outside $A$. Were ${\Phi }_e^B={\chi }_A$, the computation on that witness would converge to zero with a finite oracle use. Since the increasing sets $B_s$ eventually agree with $B$ on this finite initial segment, a sufficiently late bounded simulation would detect that computation and make $R_e$ act, a contradiction. The symmetric argument verifies every $S_e$.

Thus the two sets have incomparable Turing degrees. Both are noncomputable, since a computable set is Turing-reducible to every oracle. Both are also strictly below the degree of the halting problem: every computably enumerable set is Turing-reducible to $K$, while completeness of one would make the other reducible to it. This supplies the intermediate degrees sought in Post problem.