A CH obstruction to a prescribed categoricity threshold

Proof. Each =^*-class is countable: its members are obtained by changing the values of one sequence on finitely many integers. If \kappa=|S|, choice therefore gives

The quotient cannot be countable, since then 2^\omega would be countable. Infinite cardinal multiplication and the reverse inequality \kappa\le2^{\aleph_0} now give |S|=2^{\aleph_0}.

For each k, there are at most 2^{\aleph_0} choices for each of E and R. By CH,

so there are at most continuum many choices for \rho as well. It follows that

An injection from this disjoint union into S gives the stated maps.□

Proof. Write \mathcal D_J=(E_J,R_J,\rho_J). The equality \mathcal D_J=\mathcal D_{[k]}\restriction J gives, for labels a,b\in\mathcal L_{|J|},

The forward implication makes the quotient map well-defined, and the reverse implication makes it injective. The analogous equivalence for R proves preservation and reflection of the quotient relation; equality of the restricted tag functions proves preservation of tags. The maps on labels compose by their definition, so the induced quotient maps do also.□

Proof. Fix p\in B. If the final segment above p has a countable cofinal subset, its cardinality is countable: it is covered by countably many bounded intervals with one endpoint p, together with their endpoints. Otherwise one can recursively choose a strictly increasing sequence (b_\alpha:\alpha<\omega_1) above p. At each stage there are only countably many earlier choices, so the assumption that no countable set is cofinal provides a point above all of them. This sequence must be cofinal above p. A point above the whole sequence would enclose uncountably many b_\alpha’s in a bounded interval, contrary to local countability. The final segment is therefore covered by at most \aleph_1 countable bounded intervals and their endpoints. It has size at most \aleph_1. The same argument in the reversed order applies below p, proving the claim.□

Proof. The right-hand side is a lower bound, since I,B,G_* are sorts and G_* is countably infinite. For the upper bound put \kappa=\max(|I|,|B|,\aleph_0). There are at most \kappa finite injective tuples over I. The order B is infinite, so |G(B)|=|B|; hence every row fiber has size |B|, and every column fiber has size |G_*|=\aleph_0. There are at most \kappa row fibers, indexed by \mathcal T(I)\times\omega, and at most \kappa column fibers, indexed by \mathcal T(I)\times B. All the carriers together consequently have size at most \kappa.□

Proof. Two column representatives differ by a translator v\in G_*. Equation (3.1) changes their binary sequences only at the finitely many indices in v, so their classes modulo =^* agree.

For a fixed tuple t, write z'_{t,n}=z_{t,n}+u_{t,n}, with u_{t,n}\in G(B). Put

Each support is finite, so D_t is countable. At every b\notin D_t, all coordinates of the two bit sequences are identical when computed with the same column representative. The full test for a tuple of length k involves just its 2^k-1 nonempty subsequences. Outside the union of their sets D_{t\restriction J}, all its input colors agree, proving the test assertion.

In the last assertion, the translators between two old representatives belong to G(B)^{M_0}. Their supports in M_1 are still subsets of B^{M_0}, by basic inclusion. At any b outside B^{M_0}, Equation (3.1) therefore leaves every individual bit unchanged. This proves the stronger assertion.□

Proof. Replace I and B by disjoint copies and transport the array indices along these identifications. Use separate disjoint copies for the two group sorts as well. Take tagged, disjoint copies of the appropriate groups for all the fibers. Denote the row points by (t,n,u) for u\in[B]^{<\omega}, and the column points by (t,b,v) for v\in[\omega]^{<\omega}; the tags distinguish the carrier types. Use the regular translation actions and put

Set bits between different tuples to zero, and equip the carriers with exactly the specified projections and other relations. Translation by symmetric difference gives (3.1). The zero row representatives and a zero column representative give the sequence a_{t,b}, as required. Finally, when B is countable, each set E_t(\mathbf z)\subseteq B is countable automatically.□

Proof. All the basic conditions are preserved by a \tau-isomorphism, so the isomorphic image of a basic structure is basic. Now consider an isomorphism of basic structures. It preserves the carrier predicates, every row number n, all tuple-coordinate projections, the fixed labels of G_*, the order, supports, actions, and bits. Transporting a row-choice system along it thus preserves the color at each corresponding base point. Countable bad sets are transported to countable bad sets. This proves invariance of the object condition. Convexity, fixed G_*, and equality of old supports are likewise preserved under an isomorphism of a pair of structures. Applying the same color calculation at each new base point proves invariance of the strong relation. In particular, if f:N\cong N' and M\le_K N, then f[M]\le_K N'.

Reflexivity follows because equality is a basic inclusion and the additional condition has an empty set of new base points. Antisymmetry follows from induced substructure inclusion. To prove transitivity, suppose M_0\le_K M_1\le_K M_2. Basic inclusions compose. Fix a tuple t from I^{M_0}, a point b\in B^{M_2}\setminus B^{M_0}, and row representatives in M_0 for t and its nonempty subsequences. If b\in B^{M_1}\setminus B^{M_0}, choose its column representatives in M_1. The bits against these old rows are unchanged in M_2, by induced substructure, and the tests hold by M_0\le_K M_1. If b\notin B^{M_1}, the selected rows in M_0 are also allowable old representatives for M_1\le_K M_2; this latter inclusion supplies the tests. Hence M_0\le_K M_2.

For coherence, suppose that M_0 is an induced \tau-substructure of M_1, and that both are strong substructures of M_2. Their G_* sorts both equal that of M_2. Convexity of B^{M_0} in B^{M_2} implies its convexity in B^{M_1}. For u\in G(B)^{M_0}, its support in M_2 is exactly its support in M_0; restricting incidence to M_1 gives the same support there. Thus M_0\preccurlyeq_{\mathrm b}M_1. For a tuple from I^{M_0} and b\in B^{M_1}\setminus B^{M_0}, compute colors using rows in M_0 and columns in M_1. They are the same colors computed in M_2, where M_0\le_K M_2 makes the full test pass. Therefore M_0\le_K M_1.□

Proof. Every finite collection of family members has a common upper member, by induction from directedness. In particular, relations agree on overlapping domains: two members embed as induced substructures of a common member. Their union therefore gives a well-defined relational structure U.

The basic data in the union. The carrier predicates still partition the union domain, and every finite tuple in I^U lies in one member. That member supplies a nonempty row fiber for the tuple at every n<\omega. A tuple together with a base point b is also contained in a common member, which supplies the required column fiber. Projection graphs remain single-valued and total by the same finite-parameter argument.

The sorts G_*^{M_i} are all the same set: for any two indices, a common upper member has G_* equal to both. Their labels and group structures agree. Every u\in G(B)^U originates in a member. It has exactly its old support in the union, since a common upper member with any other proposed incident point cannot add to that support. Thus its support is finite. Conversely, every finite subset of B^U lies in a member and is coded there. Uniqueness of its code can be checked in a common member containing any two proposed codes. The support map in U is consequently a bijection onto [B^U]^{<\omega}.

All arguments and values needed for a group operation or an action lie in a common member. This proves semantic totality and uniqueness in the union, as well as the group laws and fiber preservation. For two row points in the same union fiber, a common member containing both supplies their unique translator; the same argument applies to column points. Freeness is also checked in a common member. The fibers are therefore torsors for the required groups. Equation (3.1) follows by putting its finitely many arguments in a common member. No relations outside the prescribed types can appear in the union.

The base order is linear, dense, and without endpoints, since these assertions for finitely many points have witnesses in a containing member. More precisely, if a,c\in B^{M_i} and a<b<c in B^U, choose a member containing b and then a common upper member with M_i. Convexity in that member gives b\in B^{M_i}. Hence B^{M_i} is convex in B^U. A bounded interval in the union is exactly the corresponding interval in any member containing its endpoints, and so is countable. These arguments show that U is basic and that M_i\preccurlyeq_{\mathrm b}U for all i.

The object condition. Fix t\in\mathcal T(I^U), and choose one member M_i containing its entries. Every row of t and of its nonempty subsequences is nonempty already in M_i. Choose all their row representatives in this one member, for every n<\omega. Over B^{M_i} their full test has a countable exception set, by the object condition for M_i. These same colors can be calculated in U with columns from M_i, so the old exception bound remains valid.

For b\in B^U\setminus B^{M_i}, choose a member containing b, followed by a common upper member with M_i. The strong inclusion of M_i into that common member makes the full test pass at b using the selected rows. The same row and column points compute the same colors in U. Thus the test fails only on the original countable set in B^{M_i}.

The convenient choices just made may depend on t. To check the definition with a single global row-choice system in U, compare that system with these choices for t and its finitely many nonempty subsequences. Lemma 3.6 adds at most a countable set of possible differences. For each t, its bad set is therefore countable also for the global system. Hence U is an object.

Strongness of the members. Fix i, a tuple from I^{M_i}, and b\in B^U\setminus B^{M_i}. The same common-upper-member calculation, using rows from M_i, supplies the full test at b. Together with the verified basic inclusion this gives M_i\le_K U.

A common upper bound. Suppose now that every M_i\le_K N. The union is an induced substructure of N, because each finite relation instance can be checked in a member containing its entries. Its G_* sort equals G_*^N, and every union group element has its original support in N. For two points of B^U, choose a member containing both; convexity of that member in N forces every intervening point of B^N into that member and hence into B^U. Thus U\preccurlyeq_{\mathrm b}N.

Fix t\in\mathcal T(I^U) and b\in B^N\setminus B^U. Choose a member M_i containing t, and choose all the rows required for t and its subsequences inside M_i. Because b\notin B^{M_i}, the assumption M_i\le_K N supplies the full test at b. Those representatives are also in U and are eligible for its strong-inclusion test into N. Canonicality outside B^U, from Lemma 3.6, makes this one choice sufficient. Hence U\le_K N.□

Proof. If necessary add one point to make D nonempty. Set T_0=D. Given T_m, for each x\in T_m choose points x^-<x<x^+ in B, and adjoin them to form T_{m+1}. Put T=\bigcup_{m<\omega}T_m. Then T\ne\varnothing, |T|\le\kappa, and T has no endpoints. Let

This is the convex hull of T. It is a union of at most \kappa^2=\kappa closed bounded intervals, each countable after adjoining its endpoints. Thus |B_0|\le\kappa. Convexity and density of B make B_0 dense. If b\in B_0 lies between x,y\in T, choose points of T below x and above y. They give points of B_0 on both sides of b, so B_0 has no endpoints.□

Proof. Put \kappa=|A|+\aleph_0. Choose a nonempty I_0\subseteq I^M of size at most \kappa containing A\cap I^M and every tuple-coordinate projection of every row or column element of A. There are at most \kappa tuples in \mathcal T(I_0). For each of them, and for each n<\omega, choose a representative z_{t,n}\in Z^M_{t,n}. When computing the bad sets E_t for t\in\mathcal T(I_0), always use this same system of choices for all its subtuples. The object condition in M, or an extension of these choices to a full row-choice system in M, shows that each such E_t is countable.

Collect a subset D\subseteq B^M consisting of:

1. (i)

   all points of A\cap B^M, and all base-point projections of column elements of A;

2. (ii)

   \supp(u) for every u\in A\cap G(B)^M;

3. (iii)

   for every requested row point z\in A\cap Z^M_{t,n}, the support of the unique u\in G(B)^M satisfying z=z_{t,n}+u;

4. (iv)

   all the sets E_t, for t\in\mathcal T(I_0).

In (ii)–(iv) the listed sets are included by taking their union. The first three clauses contribute at most \kappa points, since supports and projections are finite for each requested element. The last clause contributes at most \kappa\cdot\aleph_0=\kappa points. Therefore |D|\le\kappa.

Apply Lemma 3.11 to obtain a nonempty convex dense B_0\subseteq B^M without endpoints, containing D, of size at most \kappa. Let

This is exactly the subgroup coding [B_0]^{<\omega}. Define N by retaining I_0,B_0,H, and the whole group G_*^M, together with the fibers

and all relations restricted from M.

Each displayed row orbit is a nonempty H-torsor. Each retained column is the whole old G_*^M-torsor and remains one. The projections land in the retained sorts, the group operations and actions are total there, and Equation (3.1) restricts to these groups and fibers. Thus N is basic and N\preccurlyeq_{\mathrm b}M.

The choices z_{t,n} are present in N: they are obtained by the zero translator. At every b\in B_0, they compute precisely the same colors in N and M, using the retained whole column fibers. The bad set in N for any t\in\mathcal T(I_0) is therefore E_t\cap B_0, which is countable. Hence N is an object. For b\in B^M\setminus B_0, all these full tests pass because E_t\subseteq D \subseteq B_0. The same chosen rows are eligible old representatives from N. This proves the strong condition, so N\le_K M.

It remains to verify containment of the requested data. The choices of I_0 and B_0 retain requested index and base points and all needed projections. A requested group element belongs to H by clause (ii). A requested row point belongs to its retained orbit by clause (iii). A requested column point belongs to a retained whole column fiber by clause (i) and the choice of I_0. All requested elements of G_*^M are present because that entire group was retained. These are all possible carrier types, so A\subseteq |N|. Finally Lemma 3.5 gives

as required.□

Proof. The language and its semantic structures were specified after Definition 3.2. Lemma 3.9 proves isomorphism invariance, substructure, the partial-order properties, and coherence. Lemma 3.10 proves the directed union and smoothness assertions, in particular the required chain axioms. Lemma 3.12 proves the downward bound \aleph_0. Since the language is countable and \LS(K) is by definition infinite, its least possible value is \aleph_0, which is therefore the value attained here.□

Proof. For each \alpha<\eta=\delta^+, fix an injection j_\alpha:\alpha\longrightarrow\delta. These form a set-sized family of choices. Define the functions by transfinite recursion, putting

For each \beta<\omega_1, the set of indices in this supremum is countable, because j_\alpha is injective and \beta is a countable ordinal. Regularity of \omega_1 implies that the supremum is below \delta. Thus the recursion defines a function into \delta at every stage \alpha<\eta.

If \gamma<\alpha and \beta>j_\alpha(\gamma), the term f_\gamma(\beta)+1 occurs in (4.1). Hence

The latter ordinal is countable, proving the assertion.□

Proof. The set V_\omega of hereditarily finite sets is countably infinite, giving the assertion at \gamma=0. At a successor stage,

If \gamma is a nonzero limit ordinal, continuity of ordinal addition and of the cumulative hierarchy gives

The inductive hypothesis gives a lower bound of \sup_{\zeta<\gamma}\beth_\zeta=\beth_\gamma for the cardinality of this union. It also gives the upper bound |\gamma|\cdot\beth_\gamma. Strict increase of the beth sequence implies |\gamma|\leq\beth_\gamma: the map \zeta\mapsto\beth_\zeta, for \zeta<\gamma, is an injection into the ordinal \beth_\gamma. The upper bound is therefore \beth_\gamma, completing the induction.

Since \omega+\omega_2=\omega_2, the first conclusion follows. The rank assertion is the defining property of membership in V_\eta.□

Proof. Fix a well-order of the set D. For distinct a,b\in D, let w(a,b) be the first element of a\SymDiff b in this well-order. This witness exists by set extensionality and belongs to D, since D=V_\eta is transitive.

If A\subseteq D is nonempty and countable, define

Every A_n, and hence C(A), is countable. Any two distinct elements of C(A) lie together in some A_n; their chosen witness lies in A_{n+1}. Thus membership on C(A) is extensional.

Recursively on the finite cardinality of X, set

The seed is nonempty and countable, because there are only finitely many proper subsets of X. This proves (i) and (iii) and directly gives (ii) for proper inclusions; equality gives the remaining case.

Each D_X is nonempty and at most countable, so it admits a surjection from \omega, allowing repetitions when it is finite. For X=\{x\}, choose one whose initial entry is x. All these choices are indexed by a set, and the axiom of choice supplies the family of surjections.□

Proof. Surjectivity of q_t, together with (4.4), identifies the quotient bijectively with D_X. Equation (4.5) identifies its relation with membership on D_X, which is extensional. The tags in (4.6) depend only on the image under q_t, so both the relation and the tags respect the equality relation.

For (i), list J increasingly as \{j_1<\cdots<j_m\}. A label (A,i) of the subtuple t\restriction J=(x_{j_1},\ldots,x_{j_m}) corresponds to (\{j_a:a\in A\},i) in the original tuple. Both labels denote the same entry

Their equality relations, membership relations, and tags therefore agree exactly. This proof applies to every ordered tuple; the enumeration d_Y was fixed for the underlying set Y.

For the full diagram in (ii), suppose \beta\notin F_X. Every membership edge y\in x with x,y\in D_X then satisfies

by (4.2). This is precisely the strict tag inequality required for that edge. Finally, q_t(\{j\},0)=x_j, so the distinguished singleton labels are pairwise inequivalent. All validity conditions now hold.

For a subtuple with underlying set Y=X_J, its quotient is D_Y, whose membership relation is extensional by its own construction. In addition, \beta\notin F_Y follows from (4.3). The same argument proves the validity of this subtuple diagram. Combined with (i), these are exactly the conditions of the full subsequence test.□

Proof. The construction above and Lemma 4.2 give M_{\mathrm u}\in K with

Lemma 3.5 gives total cardinality \kappa=\beth_\eta.

For M_{\mathrm c}, take an index set of cardinality \kappa, base order B=\Q, and constant zero sequences a_{t,b}. Lemma 3.8 supplies a basic structure and makes the object condition automatic because B is countable. Hence M_{\mathrm c}\in K, and Lemma 3.5 gives \|M_{\mathrm c}\|=\kappa.

An isomorphism preserves the unary predicate for the order sort. It therefore cannot identify M_{\mathrm u}, whose order sort is uncountable, with M_{\mathrm c}, whose order sort is countable.□

Proof. Define F recursively in increasing order of the tag \alpha<\delta. At tag \alpha, all predecessors have smaller tags, so their images have already been defined; the displayed formula then defines the images of all elements with tag \alpha. These are sets, since Q is a set. Transfinite recursion and Replacement give a function on Q.

We prove the stated bound by induction on \alpha=\rho(x). If yRx and \beta=\rho(y), the induction hypothesis gives

Thus F(x)\subseteq V_\alpha, and consequently F(x)\in V_{\alpha+1}. At \alpha=0 the predecessor set is empty, so the same conclusion holds. Since \delta is a limit ordinal, \alpha+1<\delta for every \alpha<\delta, and the range of F lies in V_\delta.

For injectivity, induct on \max(\rho(x),\rho(x')). Suppose F(x)=F(x'). For each yRx, equality of these sets supplies y'Rx' with F(y)=F(y'). Both \rho(y)<\rho(x) and \rho(y')<\rho(x'), so the induction hypothesis gives y=y'. This proves that every predecessor of x is a predecessor of x', and the reverse inclusion follows in the same way. Extensionality gives x=x'. At induction parameter zero both predecessor sets are empty, so extensionality gives the conclusion directly.□

Proof. Suppose that such a sequence exists. For each k, let \mathcal D_k be the diagram decoded from s_k. The tests assert that every \mathcal D_k is valid and that

Choose a linearly ordered set X with |X|>|V_\delta|. Such an X can be the initial ordinal of cardinality |V_\delta|^+. For each nonempty finite A\subseteq X, transport \mathcal D_{|A|} along the increasing enumeration of A, so that its labels become

Let Q_A, R_A, and \rho_A denote its quotient, quotient relation, and tag function. If A\subseteq B are nonempty and finite, the label inclusion and Equation (5.2) give a map

By Lemma 2.4, these maps are injective, preserve tags, preserve and reflect the relation, and satisfy

We construct their limit explicitly. Form the set

This is a set-indexed union of countable sets. Declare

Passing to a larger finite common stage preserves equality and reflects it by injectivity. The composition identities therefore show that \sim is an equivalence relation: in particular, two equalities witnessing transitivity can both be read in the stage indexed by the union of their three finite index sets. Put Q=P/{\sim}, and let j_A:Q_A\to Q send a to the class of (A,a). Each j_A is injective, and

Every finite collection of elements of Q lies in the image of one j_A, by taking a union of finitely many index sets.

Define tags on the limit by \rho(j_A(a))=\rho_A(a). Define its relation using a finite common stage: for a\in Q_A, b\in Q_B, and C=A\cup B, set

These definitions are independent of the representatives. Indeed, representatives that describe the same limit points become equal in a finite common stage by Equation (5.3). Taking the union of that stage with all stages used in Equation (5.4) makes the relevant representatives equal simultaneously. Tag preservation gives the same tag, and preservation and reflection of R give the same truth value for the relation. It also follows that each j_A preserves and reflects R, and that

The limit relation is extensional. To see this, take distinct x,x'\in Q and put them in a common stage, say x=j_A(a) and x'=j_A(a'). Injectivity implies a\ne a'. Extensionality in Q_A gives a predecessor distinguishing them. After exchanging a,a' if needed, there is b\in Q_A with

Because j_A preserves and reflects the relation, j_A(b)Rx and \neg(j_A(b)Rx'). This witness remains valid even if larger stages add other predecessors.

For u\in X, consider the element of Q_{\{u\}} represented by the label (\{u\},0), and let q_u be its image in Q. If u\ne v, condition (iii) of Definition 2.1, applied in the stage Q_{\{u,v\}}, says that the two corresponding elements are distinct. Injectivity of the stage map gives q_u\ne q_v. Thus

Lemma 5.1 applies to the set Q, with its extensional relation and tags below \delta. It gives an injection into V_\delta, whence

This contradicts the choice of X.□

Proof. Put \kappa=\xi^+. This is a regular cardinal and a limit ordinal. The beth sequence is strictly increasing and continuous at limit ordinals, so

This gives \cf(\Lambda)\le\kappa. Conversely, a set of fewer than \kappa ordinals below \Lambda can be bounded by beth values with fewer than \kappa indices. Regularity of \kappa bounds these indices below \kappa, and therefore bounds the original set below \Lambda. This proves \cf(\Lambda)=\kappa.

Given an infinite cardinal \nu<\Lambda, choose \alpha<\kappa with \nu\le\beth_\alpha. Since \alpha+1<\kappa,

Thus \Lambda is a strong limit. It is also a limit cardinal: for every cardinal below it, a strictly larger beth value still lies below it. In particular \xi<\Lambda, and for infinite \zeta<\Lambda,

The last inequality uses \xi\cdot\zeta<\Lambda and strong limitness. The successor of \xi^\zeta is also below the limit cardinal \Lambda.□

Proof. By identifying the colors with elements of \xi, it suffices to use the palette \xi. We induct on m, proving the statement for all infinite targets \chi<\Lambda at each step. When m=1, take

If every color class had size less than \chi, their union would have size at most \xi\cdot\chi<\mu. Thus some class has at least \chi elements, from which we select exactly \chi.

Suppose the statement is known for m, and fix a target \chi<\Lambda. Choose an infinite cardinal \zeta<\Lambda such that every \xi-coloring of [\zeta]^m has a homogeneous \chi-element subset. Set

where the last inequality follows from Lemma 5.4. Let c:[\mu]^{m+1}\to\xi. We seek \zeta increasing representatives and a later point x such that the color of any m+1 representatives is unchanged when its last point is replaced by x. Coloring an m-set by the color obtained after adjoining x then reduces to the induction hypothesis. The residual-set tree below groups points by their profiles on the named representatives along each branch. Its node count leaves an unnamed x, whose residuals determine the required branch.

For each \alpha<\zeta, fix an injection

Such an injection exists because |[\alpha+1]^m|\le\zeta. Index potential tree nodes by sequences s\in{}^\alpha q, for \alpha\le\zeta. Define their residual sets X_s\subseteq\mu recursively as follows.

1. (i)

   At the root, put X_\varnothing=\mu.

2. (ii)

   Suppose s has length \alpha<\zeta and X_s is nonempty. Name its least point

   r_s=\min X_s.

   For y\in X_s\setminus\{r_s\}, define its profile u_{s,y}\in{}^{[\alpha+1]^m}\xi by

   u_{s,y}(a)=c\bigl(\{r_{s\upharpoonright\beta}:\beta\in a\} \cup\{y\}\bigr), \qquad a\in[\alpha+1]^m. \tag{5.6}

   For each i<q, put

   X_{s^\frown i} =\{y\in X_s\setminus\{r_s\}:\iota_\alpha(u_{s,y})=i\}.

   If X_s is empty, set every immediate successor residual to the empty set.

3. (iii)

   If \gamma\le\zeta is a nonzero limit ordinal and s\in{}^\gamma q, put

   X_s=\bigcap_{\alpha<\gamma}X_{s\upharpoonright\alpha}. \tag{5.7}

Only nodes with nonempty residuals matter. Every such node has nonempty ancestral residuals, so all representatives in (5.6) are defined. Along a branch the representatives increase strictly: each one is the least point of the current residual, and successor residuals exclude that point. Consequently the arguments of c in (5.6) are (m+1) distinct points. Once \alpha+1\ge m, the index set [\alpha+1]^m includes subsets containing \alpha itself, so the profile includes tests using the just named point r_s.

The number of potential nodes, including those at limit levels, is bounded by

Here \zeta is infinite, q\ge\zeta, and \zeta\cdot\zeta=\zeta. In particular at most q points are named at levels below \zeta. Since \mu=q^+, choose a point x\in\mu that is never named.

There is a unique branch of residuals containing x through all levels at most \zeta. Indeed, if x\in X_s at a successor step, then x\ne r_s, so exactly one of the profile classes contains it. At a limit step, it belongs to the intersection (5.7) along the branch already constructed. Thus the branch cannot disappear at a limit. Write its named representatives as

They increase strictly and are all less than x, so |P|=\zeta.

Define a coloring of the preceding arity by

Consider indices \alpha_0<\cdots<\alpha_m<\zeta. At level \alpha_{m-1} of the branch, all the first m representatives in this list have appeared, including the just named one. The last representative r_{\alpha_m} and the point x belong to the same successor residual at that level. Their profiles therefore agree on \{\alpha_0,\ldots,\alpha_{m-1}\}, giving

By the choice of \zeta, the map d has a homogeneous subset H\subseteq P of cardinality \chi. Equation (5.9) shows that H is homogeneous for c as well. This proves the induction step.□

Proof. Choose the colors recursively. After choosing p_1,\ldots,p_j, maintain the following invariant: for every infinite cardinal \chi<\Lambda, there is a set Y\subseteq X with \chi\le|Y|<\Lambda such that each c_i for 1\le i\le j is constantly p_i on [Y]^i. For j=0 this follows from |X|\ge\Lambda.

Assume the invariant holds at j. For each infinite \chi<\Lambda, Lemma 5.5 supplies a source cardinal \mu_\chi<\Lambda for arity j+1 and target \chi. Choose an existing sample of size at least \mu_\chi, restrict to \mu_\chi points, and apply the lemma to obtain a subset Z_\chi of size \chi on which c_{j+1} has a constant color q_\chi\in C_{j+1}. All earlier colors are retained on this subset.

At least one color occurs as q_\chi for target cardinals \chi unbounded below \Lambda. Otherwise, for every q\in C_{j+1} there would be a bound below \Lambda for the targets assigned color q. Since |C_{j+1}|\le\xi<\cf(\Lambda), the supremum of these bounds would still be below \Lambda. This contradicts the fact that we made the construction for every infinite target below the limit cardinal \Lambda. Choose such a color as p_{j+1}; its samples establish the invariant at j+1.

After this recursion, fix a positive integer k. The invariant at stage k supplies an infinite sample homogeneous in the first k chosen colors. Any k points of that sample give A_k.□

Proof. Suppose instead that |I^M|\ge\Lambda. Fix a well-order of I^M, used only in this proof, and fix row representatives z_{t,n} for every tuple t and every n<\omega in M. Let

be the resulting color profile of t, as defined in Section 3. By CH, |S|=\delta, and Lemma 3.4 gives |B^M|\le\delta. Thus the palette of whole profiles has size at most

For the middle equality, 2^\delta\le\delta^\delta follows from 2\le\delta, while \delta^\delta\le(2^\delta)^\delta=2^\delta gives the reverse inequality.

For each j\ge1, color a j-element subset of I^M by the profile of its increasing enumeration. Apply Lemma 5.6 to these colorings, with every palette equal to S^{B^M}. Obtain profiles p_j\in S^{B^M} and, for each k, an increasing witness tuple t_k of length k whose increasing j-subtuples all have profile p_j, for j\le k.

For the fixed global row representatives, let E_k\subseteq B^M be the countable exceptional set for the full object test of t_k. By the definition of that test, it includes all required checks on the nonempty subsequences of t_k. The set

is countable. Choose b\in B^M\setminus E, possible because B^M is uncountable, and put s_j=p_j(b) for every j\ge1. For each k, evaluation on t_k proves

This is the sequence forbidden by Lemma 5.2. The contradiction proves the bound.□

Proof. Fix a bijection f:I^M\to I^N. Both base orders are nonempty countable dense linear orders without endpoints. There is an order isomorphism g:B^M\to B^N, as follows. Enumerate the two orders and build finite partial increasing bijections, alternately including the next unused point of each enumeration in the domain and in the range. At each step, density supplies a point between the finitely many already matched neighbors, or absence of endpoints supplies a point beyond them. The appropriate interval contains infinitely many points, so the finitely many used points can be avoided. The union is the required bijection g.

The map g induces the group isomorphism

where elements of the coded groups are identified here with their finite supports. Match the two copies of G_* by their distinguished elements. Enumerate B^M as (b_k:k<\omega); this enumeration need not respect its order.

Fix one tuple t of distinct points in I^M, and let f(t) be its coordinatewise image. Choose representatives

Write their bit matrices as

and let d(n,k)=a(n,k)+a'(n,k), with addition in \mathbb Z/2\mathbb Z. Define translators by

Every U_n is finite, since it uses only the first n+1 columns; every V_k is finite, since it uses only the first k rows. The two regions in (5.11) partition the matrix, so

Figure 1 illustrates this allocation of finite supports.

Set \widetilde z'_n=z'_n+U_n and \widetilde w'_k=w'_k+V_k. The action equation for the bit relation and (5.12) give

Because every fiber is a torsor, its points have unique expressions relative to its chosen representative. We therefore obtain bijections of the row and column fibers by setting

These maps are equivariant and hence preserve the action graphs. For arbitrary u\in G(B^M) and v\in G_*, their target bit is

Thus they preserve the entire bit relation, not just the bits at representatives.

Carry out this construction separately for every tuple t. The row and column fibers of distinct tuples are disjoint, and there are no additional bit or action relations between different tuples. Together with f, g, \widehat g, and the distinguished-element map on G_*, these fiber maps give a bijection of the whole universes. They preserve and reflect the sort predicates, tuple and base projections, order, group incidence and operation graphs, action graphs, distinguished elements, and bits. They therefore form an isomorphism of the structures.□

Proof. Fix such a cardinal \mu. By Lemma 3.8, choose a model with |I|=\mu, base order \Q, the specified group torsors, and, for example, zero bit sequences at the chosen representatives. The countable base order makes the object test automatic. Lemma 3.5 gives cardinality exactly \mu, proving existence.

Now let M\in K have cardinality \mu. By Lemmas 3.4 and 3.5,

It follows that |I^M|=\mu. Proposition 5.7 therefore forces B^M to be countable. Any two models of size \mu now have equally sized index sorts and countable base orders, so Lemma 5.9 makes them isomorphic. This proves existence of exactly one isomorphism type at every \mu\ge\Lambda, including \mu=\Lambda itself.□

Proof of Theorem 1.1. Work in ZFC with CH. Theorem 3.13 gives an AEC K with \LS(K)=\aleph_0. Hence

Theorem 4.5 supplies two nonisomorphic models of this cardinality. Theorem 5.10 gives categoricity in every \mu\ge\Lambda. Finally, Cantor’s theorem gives \xi=2^\delta\ge\delta^+=\eta, so \xi^+>\eta. By strict increase of the beth hierarchy,

Thus \lambda=\Lambda^+ satisfies the premise of the proposed transfer and its conclusion fails at \mu=H(K), as claimed.□

Proof of Corollary 6.1. The class and strong relation are given by fixed formulas with the set of coding maps as parameter. Expanding these formulas in the AEC axioms and the stated model assertions gives the sentence \Theta. The construction and its verification in Theorem 1.1 therefore prove, in ZFC, \mathrm{CH}\Rightarrow\Theta.

For each \Phi specified above, its ZFC-provable fixed-family instance applies to the parameter witnessing \Theta. It would give categoricity in h(\aleph_0), contradicting the two nonisomorphic models required by \Theta. Thus ZFC proves \Theta\Rightarrow\neg\Phi.

Gödel’s relative-consistency theorem [6] gives \Con(\mathrm{ZFC})\Rightarrow \Con(\mathrm{ZFC}+\mathrm{CH}). Since the latter theory proves \Theta, its consistency implies \Con(\mathrm{ZFC}+\Theta), and the proved implication \Theta\Rightarrow\neg\Phi then gives \Con(\mathrm{ZFC}+\neg\Phi). If \Phi were a theorem of consistent ZFC, adjoining \neg\Phi could not give a consistent theory.□

Proof. Let M be the model with uncountable base from Theorem 4.5. By Theorem 3.13, choose a countable A\le_K M. Construct an extension N of A by enlarging only its index sort to cardinality \Lambda^+, keeping B^N=B^A, both old group sorts, and all fibers and bits belonging to old tuples. For each new tuple add the required independent torsors and any bit array satisfying the translation law. The countability of B^N makes the object condition automatic. This is a basic inclusion A\subseteq N, and the strong condition is vacuous because the base order has not grown. Thus A\le_K N.

If M and N strongly embedded into a common model P, the image of M would force B^P to be uncountable and the image of N would force |I^P|\ge\Lambda^+. This contradicts Proposition 5.7. There is therefore no joint embedding of M,N, and in particular no amalgam of the two extensions A\le_K M,N.□

Proof. First we construct compatible colors for all tuples over I=I^M. Choose an injection j:I\to\omega. For each nonempty finite X\subseteq I, choose a surjection d_X:\omega\to\omega, requiring d_{\{x\}}(0)=j(x). For example, set d_X(n+1)=n, and choose the zeroth value as prescribed for singletons and as zero otherwise. For a tuple t=(x_1,\ldots,x_k) and a label (J,n)\in\mathcal L_k, put

Define a diagram D_t by equality of these values, by ordinal membership between them, and by the tag \rho_t(J,n)=q_t(J,n). Its quotient is \omega, since the labels ([k],n) already surject onto \omega. Ordinal membership on this quotient is extensional and strictly decreases the tags, which lie below \delta. The distinguished singleton labels have the distinct values j(x_r). Thus D_t is valid. Restricting to a subsequence gives exactly its separately valid diagram: the definition of d_X depends on the underlying finite set, not its position in a larger tuple. Consequently the colors s_t=\iota_k(D_t) satisfy every full-subsequence test. When I is infinite, the unary colors are distinct; when I is finite, there are no tuples at sufficiently large arities. Thus this does not produce the fixed-arity pattern excluded by Lemma 5.2.

Take the ordered sum B'=B^M+\Q, with a disjoint copy of \Q. It is a countable dense order without endpoints, and B^M is convex in it. Keep I^M and the exact old labeled group G_*^M. Enlarge G(B^M) to G(B') by retaining each old code with its old support and adding one new code for every remaining finite subset of B'. Choose old row origins z_{t,n}, and extend each old row torsor to a G(B')-torsor: retain the points with old support coordinates and adjoin one point for each remaining coordinate, with the action given by symmetric difference. Keep every old column torsor, choose an origin w_{t,b} in it, and add a new G_*^M-torsor with an origin w_{t,b} for each new b.

Choose a_t\in2^\omega representing s_t, and prescribe the origin bits by

Extend them to all points by the torsor formula

Unique torsor coordinates make this well-defined. The old translation law (3.1) shows that every old bit, true or false, is unchanged. All group and action values on old arguments are unchanged as well. Give the enlarged carriers exactly the required relations, with zero bits between different tuple fibers. This is a basic inclusion, and its countable base makes the enlarged structure an object.

At every new base point the colors, using the chosen old rows, are the s_t, so all old-tuple tests pass. Changing to other old row points has no effect there: the translators have supports contained in B^M. Changing column origins preserves colors modulo =^*. Hence the inclusion is strong, not just basic. Finally, Lemma 3.5 makes the extension countable.□

Proof. Choose a countable strong map a:A\to H whose image contains B^H, using the downward Löwenheim–Skolem property and then the representative in \mathcal C_0. Define

Injectivity makes this a cosieve. For any f:A\to D, Lemma 7.1, followed by an isomorphism to the chosen representative in \mathcal C_0, gives a countable strong map g:D\to D' adding a base point outside g[B^D]. It follows that gf\in R_A. Thus R_A satisfies (7.1), without any amalgamation assumption.

The image of p_H^*(R_A)\to p_H^*(y_A) consists exactly of maps A\to H factoring as hr with r\in R_A and h:D\to H strong. But a has no such factorization. If a=hr, choose b\in B^D\setminus r[B^A]. Since h(b)\in B^H=a[B^A], there is x\in B^A with h(b)=a(x)=h(r(x)), contrary to injectivity of h.

Sheafification for J_{\neg\neg} inverts the dense inclusion R_A\hookrightarrow y_A. If p_H factored through the sheaf subtopos, its inverse image would therefore send that inclusion to an isomorphism. The omitted element a proves that it does not even send it to a surjection. Finally, models of cardinality at least \Lambda have countable base by Lemmas 3.4 and 3.5 together with Proposition 5.7, and exist by Theorem 5.10.□