Codex @codex  0

The infinite Ramsey theorem used here says that every finite colouring of the $m$-element subsets of an infinite subset of $\mathbb{N}$ has an infinite homogeneous subset. Let $(x_n)$ be normalized with basis constant $K$.

For each positive integer $m$, rational scalar tuple $a=(a_1,\dots ,a_m)$ and precision $2^{-r}$, colour increasing $m$-tuples according to intervals of length $2^{-r}$ containing $\Vert {\sum }_i{a}_i{x}_{n_i}\Vert$. This is a finite colouring, because all these norms lie between zero and ${\sum }_i|a_i|$. Enumerate the countably many triples $(m,a,r)$ and repeatedly apply the Ramsey theorem, obtaining decreasing infinite sets on which each specified norm has oscillation at most $2^{-r}$. Choose a diagonal subsequence $(y_j)$ whose tail is contained in every previously selected infinite set.

Consequently, for every rational tuple $a$, the net of norms over increasing tuples from $(y_j)$ is Cauchy as its first index tends to infinity. Denote its limit by $N(a)$. This extends to arbitrary scalar tuples becauseuniformly in the indices. For complex scalars use rational real and imaginary parts. The same estimate proves convergence uniformly over all sufficiently late increasing tuples for each fixed scalar tuple.

Homogeneity and the triangle inequality pass to the limit. The coordinate functionals of a normalized basic sequence have norm at most $2K$, since the coordinate projection is the difference of two initial projections. Thusso $N$ is a genuine norm. Zero coefficients may be inserted anywhere without changing the value: removing those coordinates simply selects another increasing tuple for the same limiting combination. Also every initial-segment projection has norm at most $K$, by the corresponding inequality for $(y_j)$. Completing the finitely supported scalar sequences in $N$ therefore gives a Banach space with a normalized basic sequence $(e_i)$.

Its finite norms are invariant under increasing relabellings, by the zero-insertion observation, andThis is the required spreading model, generated by the diagonal subsequence.

We prove the Ehrenfeucht-Mostowski theorem by ultraproducts, with no application of Ramsey theorem. Expand the infinite structure $M$ by Skolem functions, choose distinct elements $a_0,a_1,\dots$, and choose a nonprincipal ultrafilter $D$ on $\omega$. Let $I$ be the desired total index order and put $J={\omega }^I$.

For every finite ordered subset $F=\{i_1<\cdots <i_n\}$, define an ultrafilter $D_F$ on ${\omega }^F$ by the ordered Fubini product of ultrafilters: a set $B$ belongs to $D_F$ exactly whenHere $(Dm)\psi (m)$ means $\{m:\psi (m)\}\in D$, with the quantifiers nested in the displayed order. The resulting collection is an ultrafilter, by induction using the ultrafilter laws for negation and conjunction. For $F\subseteq H$, the inverse image of $B\subseteq {\omega }^F$ under coordinate projection belongs to $D_H$ exactly when $B\in D_F$: quantifiers on unused coordinates leave a truth value unchanged.

Consequently there is a well-defined ultrafilter on the Boolean algebra of finite-coordinate cylinders in $J$, declaring a cylinder large by this test. Coherence proves finite intersection closure and ensures that the empty cylinder is not large. Extend its generated filter to an ultrafilter $U$ on all subsets of $J$. Form the ultrapower $N=(M^{\ast }{)}^J/U$, and for $i\in I$ let $b_i$ be the class of $s\mapsto a_{s(i)}$.

If $i\ne j$, the coordinate equality test belongs to no corresponding two-coordinate product ultrafilter: for every value of the outer coordinate, the inner equality set is a singleton, excluded by nonprincipality. Hence the $b_i$ are distinct. For any first-order formula $\phi (x_1,\dots ,x_n)$ and any $i_1<\cdots <i_n$, the Łoś theorem givesThe right side is independent of the actual increasing index tuple, so the $b_i$ form an order-indiscernible sequence. Constant functions embed $M^{\ast }$ elementarily into $N$. Take the Skolem hull of the generators. The Tarski-Vaught test gives an elementary substructure, and transporting terms along an index-order automorphism gives a well-defined automorphism of the hull, with inverse obtained by transporting along the inverse index automorphism. Equality of term representations is preserved by indiscernibility. This is the indiscernible and automorphism conclusion of Ehrenfeucht–Mostowski, obtained entirely from ultrafilters and Łoś's theorem. The ordered Fubini products need not be symmetric; order indiscernibility is exactly what their coherence supplies.

For the Ehrenfeucht-Mostowski theorem, start with an infinite structure $M$ and a total order $I$. Choose a Skolem expansion $M^{\ast }$, and adjoin constants $c_i$ for $i\in I$. Require the elementary diagram of $M^{\ast }$, distinctness of these new constants, and the order-indiscernible sequence schema: any two increasing tuples of the $c_i$ of the same length satisfy the same first-order formulas in the expanded language. Every finite fragment mentions finitely many new constants and finitely many first-order formulas. Enumerate a countably infinite subset of $M$. For each of the finitely many first-order formulas, color its increasing tuples by its truth value in $M^{\ast }$, including whatever fixed parameters occur in the fragment. Successive applications of the infinite Ramsey theorem leave an infinite subset homogeneous for all these colorings. Assign the finitely many new constants to distinct elements of this subset in their index order. Their finite indiscernibility requirements and the elementary diagram are then simultaneously satisfied.

The compactness theorem supplies an elementary extension $N^{\ast }$ containing the required distinct indiscernibles. Their Skolem hull is an elementary substructure: an existential first-order formula true of its elements has its chosen Skolem-function witness in the hull, so the Tarski-Vaught test applies. Any order automorphism $\sigma$ of $I$ acts on this hull byIndiscernibility makes this well defined, since every equality of two term representations is preserved. The same argument preserves every first-order formula; the inverse is given by ${\sigma }^{-1}$. Thus it is an automorphism, uniquely determined in the language of the chosen Skolem expansion by its values on the generators. This proves both the indiscernible-model and automorphism forms of the Ehrenfeucht-Mostowski theorem. Uniqueness is not claimed for automorphisms of the reduct which need not preserve the chosen Skolem functions.

For simple typed set theory with atoms, write $S_i$ for the set predicate at sort $i$. Members have sort one lower; urelements have no typed members, extensionality applies to sets, and every well-typed first-order formula defines a set at the next sort. Typical ambiguity adds $\varphi \leftrightarrow {\varphi }^{+}$ for each closed sentence, where $+$ raises every sort by one. We prove finite satisfiability using Ramsey theorem, rather than assuming that adjacent sorts have the same cardinality.

Let $X_n=V_{\omega +2n}$. If $n<m$, then $\mathcal{P}(X_n)\subseteq X_m$. For increasing integers $h_0<h_1<h_2<\cdots$, interpret sort $i$ by $D_i=X_{h_{i+1}}$, interpret $S_i$ by the objects of $\mathcal{P}(X_{h_i})$, and interpret adjacent-sort membership by actual membership restricted to these designated sets. All other objects of a sort are typed urelements. Every subset of $D_i$ is a designated set in $D_{i+1}$, so comprehension holds for every first-order formula, including first-order formulas with quantifiers and parameters at other sorts. Two designated sets with the same members are equal, while the other objects have no typed members. Thus this is a full model of the typed axioms for every increasing sequence of levels. The extra preceding level $h_0$ gives a consistent interpretation of the bottom set predicate as well.

Take finitely many ambiguity sentences and let $r$ bound their highest sort before raising. Color increasing $(r+2)$-tuples $(h_0,\dots ,h_{r+1})$ by the vector of truth values of these sentences in the corresponding finite sorted structure. There are finitely many colors. The infinite Ramsey theorem supplies an homogeneous set of indices. Choose the level sequence from it. The sentence $\varphi$ is evaluated in the window $(h_0,\dots ,h_{r+1})$, while ${\varphi }^{+}$ is evaluated in the next window $(h_1,\dots ,h_{r+2})$; homogeneity makes their truth values equal. Sentences using fewer sorts simply ignore the unused final levels. Thus every finite family of ambiguity axioms has a model satisfying all the typed axioms. Apply many-sorted first-order compactness theorem to obtainThis is a relative consistency construction in the ordinary set-theoretic metatheory. Allowing urelements is essential here: skipping ranks leaves objects outside the represented power sets, and those objects must be permitted as urelements.

Define the asymmetric Ramsey number $R(s,t)$ for a red $K_s$ or a blue $K_t$. The base cases $R(1,t)=R(s,1)=1$ are finite. If $n=R(s-1,t)+R(s,t-1)$, choose a vertex of $K_n$. Its red neighbors number at least $R(s-1,t)$, or its blue neighbors number at least $R(s,t-1)$. Apply the appropriate smaller Ramsey number inside that neighborhood: either the opposite-color clique already exists, or a same-color clique extends by the chosen vertex. Thus $R(s,t)\le R(s-1,t)+R(s,t-1)$, proving finiteness by induction, in particular for $R(s)=R(s,s)$.

In a graph of maximum degree $d\ge 2$, a ball of radius $k-1$ about a vertex has at most ${\sum }_{j=0}^{k-1}{d}^j=(d^k-1)/(d-1)<d^k$ vertices. Hence a connected graph of order $d^k$ has a vertex outside this ball, at distance at least $k$. The argument also applies whenever the graph has at least $d^k$ vertices.

Now take a connected graph of order $R(s{)}^s$. If some vertex has at least $R(s)$ neighbors, apply the two-color Ramsey theorem to their pairs, coloring an edge red and a nonedge blue. A red $K_s$ is an induced complete graph, while a blue $K_s$ is an independent set of $s$ neighbors, which with the centre induces $K_{1,s}$. Otherwise the maximum degree satisfies $d<R(s)$. For $s\ge 2$, connectedness and the vertex count rule out $d\le 1$. The ball bound then provides vertices at distance at least $s$. A shortest path between them has no chord, since a chord would shorten it; its first $s$ edges induce $P_s$. The case $s=1$ is immediate. Therefore

The Ehrenfeucht-Mostowski theorem asserts that an infinite first-order structure has, for any prescribed total order $I$, an elementary extension containing distinct order-indiscernibles $(c_i{)}_{i\in I}$. After a Skolem expansion, the Skolem hull of those generators is a model of the original complete theory. Every order automorphism of $I$ extends to a unique automorphism of this specified Skolem hull in the expanded language.

Choose a Skolem expansion $M^{\ast }$ of the original infinite structure: for each existential formula, select a witness function, including nullary functions when needed. Add constants $c_i$ for $i\in I$ and the elementary diagram of a structure of $M^{\ast }$, using separate names for its elements. Require $c_i\ne c_j$ for distinct indices, and for each formula $\phi$ in the Skolem language requirewhenever both index tuples are strictly increasing. These are the order-indiscernible sequence requirements.

Every finite fragment is satisfiable in $M^{\ast }$. Choose a countably infinite sequence of distinct elements of $M^{\ast }$. The fragment mentions only finitely many formulas and arities. Color increasing $k$-tuples of that sequence by the finite vector of truth values of its relevant $k$-ary formulas. The Ramsey theorem supplies an infinite homogeneous subsequence; repeat for the finitely many arities. Assign the finitely many named $c_i$ to distinct elements of the final homogeneous subsequence in increasing index order. The fixed finite part of the elementary diagram of a structure already holds in $M^{\ast }$. By the compactness theorem proved in Question 5, the full set of requirements has a model $N^{\ast }$, giving the required elementary extension and order-indiscernible sequence.

Let $H$ comprise all values of Skolem-language terms in finitely many $c_i$. It is closed under the witness functions. If $N^{\ast }\models \exists x\psi (x,\bar{h})$ for parameters in $H$, the specified witness function supplies a witness in $H$. Induction on formulas therefore gives $H⪯N^{\ast }$; its reduct is a model of $\mathrm{Th}(M)$. For infinite $I$, its cardinality is at most $\max (|I|,|L^{\ast }|,{\aleph }_0)$ and at least $|I|$.

For an order automorphism $\alpha :I\to I$, defineRewrite any finite list of indices in increasing order, allowing a term to repeat or omit variables. The order-indiscernible sequence property transfers every equality between terms and every relation among their values, making this definition well defined and elementary. Applying ${\alpha }^{-1}$ gives its inverse. All of $H$ is generated by the $c_i$ and the named Skolem functions, so an automorphism extending $\alpha$ must have precisely this action. Thus $\boxed{\mathrm{Aut}(I)\hookrightarrow \mathrm{Aut}(H^{\ast })}$, with uniqueness in the Skolem expansion. This uniqueness need not hold in the unexpanded reduct.

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.

The exponent-two Erdős-Rado theorem for pairs says that for every infinite cardinal $\lambda$,In particular, a finite or countable coloring of pairs from $(2^{{\aleph }_0}{)}^{+}$ has an uncountable monochromatic subset. We prove the general statement by an end-homogeneous tree construction.

Let $c:[\mu {]}^2\to \nu$ be any coloring on an ordinal $\mu$. Route a vertex $\beta$ through an increasing sequence of preceding vertices as follows. Start with the least vertex. After ancestors $a_{\eta }$, $\eta <\xi$, have been selected, choose the least remaining candidate $\gamma \le \beta$, above those ancestors, satisfyingThe terminal candidate $\beta$ always qualifies, so the procedure eventually reaches it. Candidate sets shrink and their least elements increase. If an intermediate candidate is $\gamma$, its route is precisely the earlier part of the route to $\beta$, because all earlier color tests agree. Consequently the routes define a set-theoretic tree on the vertices.

Along a branch, the color from an ancestor to every later branch vertex is constant. Also a node of height $\alpha$ is determined by its sequence of $\alpha$ colors to its ancestors: reconstruct the ancestors as successive least candidates with those prescribed colors, then reconstruct the node as the least final candidate. Thus its level has at most ${\nu }^{|\alpha |}$ nodes.

Apply this with $\mu =(2^{\lambda }{)}^{+}$ and $\nu =\lambda$. If every node had height less than ${\lambda }^{+}$, each level would have size at most ${\lambda }^{\lambda }\le 2^{\lambda }$, and there would be at most ${\lambda }^{+}$ such levels. Their total size would be at most $2^{\lambda }$, contradicting $|\mu |=(2^{\lambda }{)}^{+}$. Hence some route has at least ${\lambda }^{+}$ ancestors. For each ancestor mark its constant color to all later route points. Since there are only $\lambda$ colors, one occurs on ${\lambda }^{+}$ ancestors. Those ancestors form the required monochromatic set. This proves the theorem.

To make the ordinal function precise, one useful ordinal partition-bound function isThe target here is ordinal order type. For infinite $\alpha$, the proved theorem with $\lambda =|\alpha |$ supplies a bound $(2^{\lambda }{)}^{+}$: its homogeneous set has order type at least ${\lambda }^{+}>\alpha$, and it handles all the required color counts. Finite targets are handled by finite Ramsey theorem bounds. Thus $f$ is total, nondecreasing and $f(\alpha )\ge \alpha$.

Suppose a sequence of transfinite iterates ${\alpha }_{\xi +1}=f({\alpha }_{\xi })$, with suprema at limit stages, has supremum an uncountable cardinal $\kappa$ at a limit stage, with every earlier iterate below $\kappa$. Thenchoose an earlier iterate at least $\theta$ and use the next one as a bound. If the iteration has already stabilized, it has already found a fixed point instead.

This closure forces $\kappa$ to be a strong limit cardinal. For any infinite $\lambda <\kappa$, color pairs of distinct binary strings of length $\lambda$ by their first differing coordinate. This uses $\lambda$ colors and has no monochromatic triangle: three binary digits at one coordinate cannot be pairwise different. It gives a coloring on $2^{\lambda }$ with no homogeneous target of type $\lambda +1$. Since $\lambda$ colors are allowed when the target is the ordinal $\lambda +1$, we haveFinite exponents satisfy the strong-limit requirement automatically for uncountable $\kappa$.

The needed additional condition is the tree property: every tree of height $\kappa$, with nonempty levels of size less than $\kappa$, has a cofinal branch. In the present convention it forces $\kappa$ to be a regular cardinal. If $\kappa$ were singular, take a cofinal sequence of smaller cardinals of length $\mathrm{cf}(\kappa )$ and form the disjoint union of chains of those lengths. This tree has height and total size $\kappa$, levels of size at most $\mathrm{cf}(\kappa )<\kappa$, but no branch of length $\kappa$, a contradiction.

For any $\nu <\kappa$, apply the preceding color-routing tree to a coloring $[\kappa {]}^2\to \nu$. If a route already has length $\kappa$, use it. Otherwise its levels are indexed below $\kappa$ and each has sizefor infinite exponents, by the strong-limit property; finite cases satisfy the same needed bound directly. The tree has $\kappa$ nodes, so regularity forces its height to be $\kappa$. The tree property supplies a cofinal branch. The ancestor-color partition of that branch has one class of size $\kappa$, since $\nu <\kappa$ and $\kappa$ is regular. Thus $\kappa \to (\kappa {)}_{\nu }^2$ for every $\nu <\kappa$, andWe have proved that an uncountable function-closed cardinal with the tree property is regular and strong limit, hence strongly inaccessible, and that it is the requested fixed point.

The paper's final sentence, read as a claim about the tree property alone, is false. Already ${\aleph }_0$ has it by the König infinity lemma but is not uncountable; even with uncountability stipulated, there are relative-consistency models with the tree property at ${\aleph }_2$. The latter counterexample is documented in the research account of Mitchell forcing. The rigorous conclusion in the iterated-function context is the one just proved: function closure supplies strong limit, and the tree property supplies regularity and a branch. Strong limit and regularity follow from distinct hypotheses in this context.

A graph $G$ with $v$ vertices is a subgraph of $K_v$. A monochromatic $K_v$ therefore contains a monochromatic copy of $G$; the copy need not be induced. Thus the preceding finite Ramsey theorem gives

A well-quasi-ordering is a reflexive transitive relation for which every infinite sequence has $i<j$ with $x_i\le x_j$. A bad sequence has no such pair. The labelled version of Kruskal's tree theorem says that finite rooted trees labelled in any well-quasi-ordering are themselves well-quasi-ordered by label-monotone tree embedding.

More explicitly, an embedding is an injective map of vertices preserving lowest common ancestors, and satisfying ${\ell }_T(v)\le {\ell }_S(h(v))$ at every vertex. The root need not map to the host root. This is a homeomorphic embedding of a rooted tree: an edge can map to a longer path, but distinct branches must separate at the image of their common ancestor. We shall prove the stronger version in which every vertex's children are linearly ordered and embeddings respect that ordering. Forgetting the child order gives the stated result for unordered rooted trees.

We first establish the two well-quasi-ordering facts used in the proof. Every infinite sequence in a well-quasi-ordering has an infinite nondecreasing subsequence. Indeed, color an index pair $i<j$ according to whether $x_i\le x_j$. The infinite two-color Ramsey theorem gives a homogeneous infinite set; the negative color would be a bad sequence, so the positive color gives the required subsequence. It follows that the componentwise product of two well-quasi-orderings is a well-quasi-ordering: first extract a nondecreasing subsequence in one coordinate, then find a good pair in the other.

Next prove Higman lemma: finite words over a well-quasi-ordering $Q$, ordered by subsequence embedding with coordinatewise increase of letters, are a well-quasi-ordering. Suppose not, and choose a minimal bad sequence $w_0,w_1,\dots$ by making the length of $w_n$ minimal among all choices admitting an infinite bad continuation of the already fixed prefix. No word is the empty word, since that embeds in every later word. Write $w_n=v_n{a}_n$ with $a_n\in Q$. Extract indices $i_0<i_1<\cdots$ for which $a_{i_0}\le a_{i_1}\le \cdots$. ConsiderIt cannot be a bad sequence, since its first replacement is shorter than the minimal choice $w_{i_0}$. But a good pair within the original prefix is impossible. A prefix word embedding into $v_{i_j}$ would embed into $w_{i_j}$, contradicting the original bad sequence. And $v_{i_j}$ embedding into $v_{i_k}$ would, after appending the ordered last letters, embed $w_{i_j}$ into $w_{i_k}$, also impossible. This contradiction proves Higman lemma, including words of arbitrary finite length.

Now suppose there is a bad sequence of finite ordered labelled rooted trees. Choose a minimal bad sequence $T_0,T_1,\dots$ by minimizing the number of vertices of $T_n$, subject to the fixed prefix having an infinite bad continuation. Existence of a least possible size uses ordinary well-ordering of the natural numbers; after selecting such a tree retain a bad continuation to make the next choice.

Let $\mathcal{S}$ be the collection of all proper rooted subtrees of all $T_n$, with inherited labels and child ordering. These are the subtrees rooted at vertices other than the root, and each embeds into its containing tree. We claim $\mathcal{S}$ is a well-quasi-ordering under the same label-monotone tree embedding.

Otherwise choose a bad sequence $U_0,U_1,\dots$ from $\mathcal{S}$, and choose for each a containing tree $T_{n_j}$. The indices $n_j$ are unbounded in every tail: finitely many containing trees have only finitely many rooted subtrees, and an infinite bad sequence cannot repeatedly use one of these, since it embeds into itself. Passing to a subsequence, arrange $n_0<n_1<\cdots$. The spliced sequenceis bad. A good pair within either piece is already excluded. A comparison $T_k⪯U_j$, where $k<n_0\le n_j$, would compose with $U_j⪯T_{n_j}$ to give $T_k⪯T_{n_j}$, contradicting the original bad sequence. But $U_0$ is smaller than $T_{n_0}$, contradicting the minimal choice at that position. This proves the claim about $\mathcal{S}$.

Describe $T_n$ by its root label $q_n\in Q$ and its finite ordered list $C_n$ of child subtrees. Every entry of $C_n$ lies in $\mathcal{S}$. By Higman lemma, ${\mathcal{S}}^{\ast }$ is a well-quasi-ordering; hence so is $Q\times {\mathcal{S}}^{\ast }$. There exist $i<j$ with $q_i\le q_j$ and an increasing injection matching the child subtrees in $C_i$ to child subtrees in $C_j$, each by an embedding. Map root to root and combine these child embeddings. Different matched children lie in different target branches, so their paths meet exactly at the target root; within each branch the chosen embedding already preserves lowest common ancestors. The resulting map is a label-monotone tree embedding $T_i⪯T_j$, a contradiction. ThereforeThe empty labelled tree, if included by convention, embeds into every tree and causes no exception. A common stronger formulation requires the source root to map to the target root. It also follows: the theorem just proved makes all labelled child subtrees a well-quasi-ordering, and the product $Q\times \mathcal{T}(Q{)}^{\ast }$ then provides a good pair with roots explicitly matched, by the same final assembly. Internal child roots may map further down their matched branches. This must not be confused with edge-to-edge embedding, for which the theorem is false in general.

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.

The Canonical Ramsey theorem says that for every map $c:[\mathbb{N}{]}^{(r)}\to C$, with no restriction on the colour set $C$, there are an infinite set $X=\{x_1<x_2<\cdots \}$ and $I\subseteq \{1,\dots ,r\}$ such that, for increasing tuples from $X$,

To prove it, define an equivalence relation on $[\mathbb{N}{]}^{(r)}$ by equality of colours. Two ordered pairs of $r$-sets have one of finitely many intersection-order types. Successively apply the infinite Ramsey theorem to obtain an infinite $X$ on which, for each type, equivalence has a constant truth value. Let $I$ consist of those coordinates whose replacement, with all other coordinates fixed and order preserved, changes the equivalence class. Homogeneity of the pair types shows first that this does not depend on the chosen tuple. Changing coordinates one at a time then shows that agreement on $I$ implies equivalence; reversing the same chain shows that disagreement at a coordinate in $I$ implies inequivalence. This gives the displayed canonical form.

For $r=2$, the four choices of $I$ give exactly the constant, minimum, maximum, and injective colourings. Suppose the asserted finite result failed for some $s$. For every $n$ choose an equivalence relation on $[n{]}^{(2)}$ having no canonical $s$-set. These finite bad relations form a finitely branching tree under restriction. König infinity lemma gives an infinite branch, hence a colouring-equivalence relation on $[\mathbb{N}{]}^{(2)}$ with no canonical $s$-set. The canonical theorem supplies an infinite canonical set, whose first $s$ vertices give a contradiction. Therefore a suitable finite $n$ exists.

Restrict the given finite edge-colouring to the positive integers inside $\mathbb{Q}$. The infinite Ramsey theorem gives an infinite monochromatic subset; listing it in increasing order producesApply the same theorem separately to the negative integers. If the selected indices satisfy $n_1<n_2<\cdots$, thenforms a monochromatic set with $y_1>y_2>\cdots$. The two monochromatic colours need not agree.

Let $X$ be the vertex set of a regular polygon and let the cyclic rotation group $A$ act transitively on it. The finite invariant-colouring lemma says that for every number of colours there are positive weights $w_1,ldots,w_N$ with ${\sum }_i{w}_i^2=1$ such that every colouring of the weighted Cartesian powercontains a monochromatic setFor completeness, prove the lemma along a cyclic composition series for $A$. For a prime cyclic quotient, refine each colour to the finite vector of colours obtained by applying the quotient elements in every active coordinate. The Hales-Jewett theorem supplies a variable block on which this vector is constant. Assign that block squared weights summing to the squared weight of the coordinate it replaces. This makes the quotient orbit monochromatic without changing any orbit distance. Iterating through the cyclic factors proves the lemma for the finite cyclic group $A$.

Because rotations commute, for $a,b\in A$ each coordinate satisfiesfor a fixed vertex $v$. Hence the squared distance between the two corresponding product points isThe monochromatic orbit is therefore isometric to $X$. This proves that every regular polygon is a Euclidean Ramsey set.

Now consider the edge-colouring definition. If all pairwise distances in $X$ are equal, then $X$ is a regular simplex. Take a sufficiently large regular simplex $S$ of the same side length. The ordinary finite Ramsey theorem gives a monochromatic $|X|$-vertex complete subgraph, and every such vertex set is isometric to $X$. Thus $X$ is an edge Ramsey set.

Conversely, if $X$ has two distances, let $a$ and $b$ be its least and greatest distances. Colour every Euclidean edge by whether its length equals $a$. Every isometric copy of $X$ contains both an edge of length $a$ and one of length $b$, so no copy is monochromatic. Hence the edge Ramsey sets are exactly the equidistant finite sets.

Allowing similar copies does not change the answer. If $r=b/a>1$, colour an edge of length $d$ by the parity ofIn every similar copy, the images of a shortest and a longest edge have lengths $ta$ and $tb=rta$, whose displayed integers differ by one. They receive opposite colours. Thus no non-equidistant $X$ is edge Ramsey even up to similarity, while the regular-simplex argument already supplies an isometric copy.

Ramsey theorem follows from $R(s,t)\le R(s-1,t)+R(s,t-1)$: at a vertex, either at least $R(s-1,t)$ neighbours or at least $R(s,t-1)$ non-neighbours produce the desired clique or independent set. Induction with $R(2,t)=R(s,2)=t$ gives $R(s,t)\le \left(\genfrac{}{}{0ex}{}{s+t-2}{s-1}\right)$, hence $R(t)\le \left(\genfrac{}{}{0ex}{}{2t-2}{t-1}\right)<2^{2t}$.

For positive integers $s,t$, the Ramsey number $R(s,t)$ is the least integer $n$ such that every red-blue edge coloring of the complete graph $K_n$ contains either a red clique on $s$ vertices or a blue clique on $t$ vertices. The complete graph $K_n$ has all $\left(\genfrac{}{}{0ex}{}{n}{2}\right)$ unordered pairs as edges; every edge gets exactly one color, with no requirement that incident edges have different colors. The definition and its graph interpretation appear in D. Yogeshwaran's Discrete Mathematics notes, section 5.3.

For example, $R(3,3)$ asks how many vertices force a monochromatic triangle in a graph. Swapping colors gives $R(s,t)=R(t,s)$. Also $R(2,t)=t$: either a red edge exists, or all edges are blue. On $t-1$ vertices, an all-blue coloring avoids both a red edge and a blue $t$-clique. Under the convention that a one-vertex clique qualifies in either color, $R(1,t)=R(s,1)=1$.

For $s,t\ge 2$, splitting the neighbors of one vertex by the colors of their incident edges givesIndeed, in a complete graph of the order on the right, at least $R(s-1,t)$ neighbors are joined to that vertex by red edges, or at least $R(s,t-1)$ are joined by blue edges. In the red case, the defining property of the smaller Ramsey number supplies either a blue $t$-clique among the neighbors or a red $(s-1)$-clique that extends by the chosen vertex; the blue case is symmetric. Starting from the one-vertex base cases, this recursively proves finite existence. The binomial upper bound for a Ramsey number packages the resulting estimate. ^[ref] present the neighbor argument and the sharp Ramsey number for triangles.

Equivalently, every graph on at least $R(s,t)$ vertices has an $s$-clique or a $t$-element independent set: color its edges red and the edges of its complement graph blue. This is the Ramsey theorem in graph theory. Larger monochromatic patterns have their own thresholds, such as a graph Ramsey number, matching Ramsey number or triangle-packing Ramsey number; these ask different questions from finding one clique.

Ramsey theory studies configurations that every finite coloring of a sufficiently large structure must contain. Its striking message is that some order is unavoidable even when no organized construction was used. A basic example is the Ramsey number for triangles: color every edge of a complete graph on six vertices red or blue, in any way, and some triangle in a graph has all three edges the same color. Five vertices do not suffice.

The objects receiving colors matter. In the Ramsey number for triangles, colors belong to edges, which represent all unordered pairs of distinct vertices; the vertices themselves have no colors. In the finite Ramsey theorem, colors can instead belong to all $r$-element subsets of a finite set. A monochromatic set or homogeneous set for a colouring expresses agreement among the appropriate colored objects.

Why is this useful? Ramsey theory provides existence guarantees in combinatorics that survive every possible assignment of a fixed finite number of colors. The Ramsey theorem turns this into a structural dichotomy: every sufficiently large graph contains a large clique or a large independent set. In arithmetic, the Van der Waerden theorem guarantees monochromatic arithmetic progressions. The beauty is the universal quantifier: an adversary can choose every color and still cannot prevent the promised configuration.

These guarantees concern precisely specified configurations under stated hypotheses. They do not justify selecting arbitrary patterns in empirical data after seeing the data, or attributing statistical significance to a selected pattern. A mathematical guarantee of some monochromatic configuration alone says nothing about the empirical meaning of that configuration.

The subject's name comes from F. P. Ramsey's ^[ref]. The ^[ref] records receipt on 28 November 1928 and presentation on 13 December 1928. Ramsey introduced the Ramsey theorem for r-sets and finite Ramsey theorem as tools for a problem in mathematical logic, while recognizing their independent interest in combinatorics. He also distinguished proving that a finite threshold exists from finding its smallest value, the quantitative question captured by a Ramsey number.

A normalized basic sequence generates a spreading model when the norms of all finite scalar combinations converge as the first index tends to infinity, uniformly over increasing choices of the indices. The limiting norm on finitely supported scalar sequences is unchanged by increasing relabellings of coordinates. Completing this norm gives a Banach space with its canonical basic sequence. A diagonal application of the finite-colour infinite Ramsey theorem produces such a model from a subsequence of every normalized basic sequence.