==== TABLE OF CONTENTS ====
A-CH-Obstruction-to-a-Prescribed-Categoricity-Threshold//00-introduction.tex
A-CH-Obstruction-to-a-Prescribed-Categoricity-Threshold//01-colors.tex
A-CH-Obstruction-to-a-Prescribed-Categoricity-Threshold//02-aec.tex
A-CH-Obstruction-to-a-Prescribed-Categoricity-Threshold//03-categoricity.tex
A-CH-Obstruction-to-a-Prescribed-Categoricity-Threshold//04-endpoint.tex
A-CH-Obstruction-to-a-Prescribed-Categoricity-Threshold//05-conclusion.tex
A-CH-Obstruction-to-a-Prescribed-Categoricity-Threshold//06-booleanization.tex
A-CH-Obstruction-to-a-Prescribed-Categoricity-Threshold//matrix-decomposition.tex
A-CH-Obstruction-to-a-Prescribed-Categoricity-Threshold//paper.tex
A-CH-Obstruction-to-a-Prescribed-Categoricity-Threshold//preamble.tex
A-CH-Obstruction-to-a-Prescribed-Categoricity-Threshold//references.bib
===========================
==== BEGIN A-CH-Obstruction-to-a-Prescribed-Categoricity-Threshold//00-introduction.tex ====
\begin{abstract}
Assuming the continuum hypothesis, we construct an abstract elementary
class with L\"owenheim--Skolem number \(\aleph_0\) that is categorical in
every sufficiently large cardinal but has at least two nonisomorphic
models of cardinality \(\beth_{\omega_2}\).
Thus categoricity does not transfer down to the proposed bound
\(\beth_{(2^{\aleph_0})^+}\), which equals \(\beth_{\omega_2}\) under CH.
Consequently, if ZFC is consistent, the prescribed-threshold
form of Shelah's categoricity conjecture is not provable in ZFC.
\end{abstract}
\section{Introduction}\label{sec:introduction}
Categoricity asks whether a class has exactly one model of a given
cardinality, up to isomorphism. For an abstract elementary class \(K\),
write \(I(K,\kappa)\) for the number of isomorphism types of its models
of cardinality \(\kappa\), and \(\LS(K)\) for its
L\"owenheim--Skolem number. Thus categoricity in \(\kappa\) means
\(I(K,\kappa)=1\). Put
\begin{equation}\label{eq:hanf-function}
h(\kappa)=\beth_{(2^\kappa)^+},\qquad H(K)=h(\LS(K)).
\end{equation}
Here cardinal successors are identified with their initial ordinals when
used as beth indices, and the beth hierarchy starts at
\(\beth_0=\aleph_0\). All structures and index sets are set-sized, all
languages are finitary, and categoricity includes existence.
The AEC axioms are recalled in Section~\ref{sec:aec}.
\subsection{The prescribed threshold and the result}
For complete first-order theories in a countable language, Morley's
categoricity theorem transfers categoricity from one uncountable
cardinal to every uncountable cardinal \cite{Morley1965}.
Abstract elementary classes retain a coherent notion of strong
substructure and closure under increasing unions while allowing classes
that are not axiomatized by a first-order theory. Shelah introduced
this framework in the mid-1970s for classes of models in infinitary logics
\cite[Section~2]{BoneyVasey2017Survey}.
His categoricity questions for abstract elementary classes have
both qualitative and quantitative forms. Qualitative eventual
categoricity asks for a cardinal \(\chi(\kappa)\), depending only on
the infinite cardinal \(\kappa\), such that, whenever
\(\LS(K)\le\kappa\), categoricity in some
\(\lambda\ge\chi(\kappa)\) implies categoricity in every
\(\mu\ge\chi(\kappa)\). The prescribed-threshold form asks for the
particular bound in~\eqref{eq:hanf-function}:
\begin{equation}\label{eq:target}
\begin{gathered}
\text{If \(K\) is categorical in some \(\lambda\ge H(K)\),}\\
\text{then it is categorical in every \(\mu\ge H(K)\).}
\end{gathered}
\end{equation}
No amalgamation, joint embedding, tameness, or absence of maximal
models is assumed here. The exact formulation, with both endpoints
included, appears in the discussion of the general conjecture in
\cite[Section~2.3]{SarochTrlifaj2024}.
The number \(H(K)\) is a general existence bound: a model at that size
gives arbitrarily large models by the presentation and
Ehrenfeucht--Mostowski methods; see
\cite[Claim~0.6]{Shelah1999CategoricityAP}.
Existence alone does not assert uniqueness or that every given model
extends to arbitrarily large ones. Categoricity transfers in the
literature obtain stronger conclusions under structural assumptions.
For example, amalgamation and \(\LS(K)\)-tameness yield transfer from a
successor categoricity cardinal at least \(H(K)\) down to \(H(K)\) and
throughout the tail \cite[Corollary~9.10]{Vasey2017Downward}.
The distinction between these assumptions and the bare AEC axioms is
essential for the construction below.
The distinction between a prescribed bound and an unspecified uniform
threshold is already explicit in Grossberg's discussion of the two
forms of the conjecture \cite[Chapter~2, Section~4, Conjectures~4.4--4.6]{Grossberg2021Draft}.
There the possible failure of the prescribed bound is considered
separately from eventual categoricity. A transfer at the prescribed
bound for arbitrary AECs is claimed in
\cite[Theorem~4.1]{Espindola2023Spectra}. The CH construction below has
the opposite conclusion at that bound. Its proof therefore includes
explicit verification of all AEC axioms, as well as separate arguments
for the endpoint models and for the higher categoricity tail.
Section~\ref{sec:booleanization} also identifies a specific obstruction
to the canonical-point step in the cited proof: on the countable-model
site, a dense cosieve need not be lifted by a large categorical model.
The comparison concerns that specific factorization, not alternative
constructions of points.
\begin{theorem}\label{thm:main}
Assume the continuum hypothesis. There is an abstract elementary class
\(K\) in a countable finitary relational language such that
\begin{enumerate}[label=\textup{(\roman*)}]
\item \(\LS(K)=\aleph_0\);
\item \(K\) has at least two nonisomorphic models of cardinality
\(\beth_{\omega_2}=H(K)\);
\item putting \(\Lambda=\beth_{(2^{\aleph_1})^+}\),
the class \(K\) is categorical in every cardinal
\(\mu\ge\Lambda\).
\end{enumerate}
In particular, \(\lambda=\Lambda^+>H(K)\) is a categoricity cardinal
from which downward transfer to \(H(K)\) fails.
\end{theorem}
Theorem~\ref{thm:main} refutes the prescribed-threshold transfer under
CH. Combining the construction with G\"odel's relative consistency of
CH gives the corresponding conditional nonprovability statement;
Corollary~\ref{cor:consistency} states it with a precise first-order
formulation. The same class is categorical on the higher tail beginning
at \(\Lambda\), so the obstruction is compatible with qualitative
eventual categoricity. The construction and both cardinal bounds are
proved here without a qualitative eventual-categoricity theorem.
\subsection{The mechanism of the construction}
There are two principal sorts. The index sort \(I\) controls the size
of the model. The base sort \(B\) is a dense linear order without
endpoints whose bounded intervals are countable; hence
\(|B|\le\aleph_1\). For each nonempty finite ordered tuple of distinct entries from \(I\),
the structure has row fibers indexed by \(\omega\) and column fibers
indexed by \(B\). A row fiber is a torsor for \([B]^{<\omega}\), and a
column fiber for \([\omega]^{<\omega}\), with symmetric difference as
addition: choosing an origin identifies a fiber with its group, but no
origin is named in the language. Choosing one point in each fiber displays
the bit relation as an \(\omega\)-by-\(B\) matrix. Changing row origins
alters finitely many entries in each row, and changing column origins
alters finitely many entries in each column.
When \(B\) is countable, these changes absorb every matrix of bits.
All models in \(K\) with countable base orders and equally sized
index sorts are therefore isomorphic. When \(B\) is uncountable,
the matrix retains a family of colors in \(2^\omega/=^*\), the quotient
of binary sequences by equality outside a finite set. These colors are
meaningful outside a countable set of columns. We impose tests on them,
separately for each tuple. The tests describe countable extensional
relations whose rank labels lie below \(\omega_1\).
In the following overview, \(V_\alpha\) denotes the ordinary cumulative
hierarchy of sets. The technical features can be summarized as follows.
\begin{enumerate}
\item \emph{Exceptions compatible with strong substructure.}
An object may have countably many exceptional columns for each
tuple. A strong inclusion requires every newly added column to
pass the tests on old tuples. Finite row supports make these
outside tests exactly independent of old choices of origins.
This permits both small strong submodels and arbitrary directed
unions, including smoothness.
\item \emph{Local rank approximation.}
An \(\omega_2\)-long sequence of functions
\(\omega_1\to\omega_1\), increasing modulo countable sets,
lets countable membership diagrams drawn from
\(V_{\omega_2}\) pass the rank tests at all but countably many
coordinates. This produces the model of size
\(\beth_{\omega_2}\) with uncountable \(B\).
\item \emph{An obstruction to large index sets.}
A fixed coherent pattern for every finite arity would give
arbitrarily large extensional structures with ranks below
\(\omega_1\), contradicting their collapse into
\(V_{\omega_1}\). A finite partition argument and an
unbounded-sample selection produce such a pattern if
\(|I|\ge\Lambda\) and \(B\) is uncountable.
\end{enumerate}
Finite-support groups, torsors with no named origins, and parity
relations have a close predecessor in the Hart--Shelah examples
\cite[Section~1]{HartShelah1990}. Their canonical structures also use
binary-sequence colors modulo finitely supported sequences,
\(2^\omega/2^{<\omega}\), the same quotient as eventual equality \cite[Section~3]{HartShelah1990}. The present construction
couples finite row and column translations with a locally countable
base order; the surviving colors encode the extensional rank diagrams
needed for the endpoint obstruction. Allowed finite color diagrams and
ranks also play a central role in the coloring classes studied by
Kolesnikov and Lambie-Hanson \cite{KolesnikovLambieHanson2016}.
Here the encoded diagrams are countable, and the full-subsequence tests
supply the exact compatibility used in their limit.
The first mechanism separates the invariance needed for objects from
the exact invariance needed for extensions. The last two mechanisms
compare local approximations, with different exceptional sets, to one
global pattern. Their proofs are given explicitly; in particular, no
infinite homogeneous subset is assumed.
Section~\ref{sec:colors} defines the diagram tests.
Section~\ref{sec:aec} constructs the AEC and verifies all its axioms.
Section~\ref{sec:endpoint} constructs the two endpoint models.
Section~\ref{sec:categoricity} proves the fixed-pattern obstruction,
uses it to bound models with uncountable base, and then establishes
categoricity on the tail. Section~\ref{sec:conclusion} combines the
results and explains the failure of amalgamation and joint embedding.
Section~\ref{sec:booleanization} proves the dense-cosieve obstruction
and makes the precise comparison with the cited topos argument.
\subsection{Conventions}
The construction in Sections~\ref{sec:colors}--\ref{sec:categoricity} is
carried out in ZFC with CH. Throughout those sections,
\begin{equation}\label{eq:standing-cardinals}
\delta=\omega_1,\qquad \eta=\delta^+=\omega_2,\qquad
S=2^\omega/=^*,\qquad \xi=2^\delta,\qquad
\Lambda=\beth_{\xi^+}.
\end{equation}
The relation \(=^*\) means equality except at finitely many natural
numbers. ``Countable'' includes finite, and ``tuple'' in the color
tests always means a nonempty finite ordered tuple with distinct
entries. Subsequences preserve the order of the remaining positions.
The hierarchy \(V_\alpha\) is the ordinary cumulative hierarchy of
sets; it is unrelated to the model sorts. We use choice for set-indexed
families only.
==== END A-CH-Obstruction-to-a-Prescribed-Categoricity-Threshold//00-introduction.tex ====
==== BEGIN A-CH-Obstruction-to-a-Prescribed-Categoricity-Threshold//01-colors.tex ====
\section{Countable diagrams and their tests}
\label{sec:colors}
The construction uses colors that encode countable diagrams with
ordinal tags. A finite tuple passes a test when its diagram and all
subsequence diagrams are valid and agree exactly on their shared
labels. These tests will define the object condition in
Section~\ref{sec:aec}; the endpoint construction will realize them
outside a tuple-dependent countable set of coordinates.
Restrictions and ranks of finite color patterns also occur in coloring
classes \cite[Definitions~1.1--1.7]{KolesnikovLambieHanson2016}.
There the rank measures extensions of finite monochromatic diagrams.
Here ordinal tags are assigned to the elements of countable extensional
relations, and the tests require exact agreement under restriction.
Throughout the construction we work in ZFC with CH and put
\(\delta=\omega_1\). For \(a,a'\in 2^\omega\), write \(a=^*a'\) if
\(\{n<\omega:a(n)\ne a'(n)\}\) is finite, and set
\[
S=2^\omega/{=^*}.
\]
The quotient here is a set of colors; its elements will later be
realized by binary sequences in structures.
\subsection{Diagrams, codes, and restrictions}
For a positive integer \(k\), write \([k]=\{1,\ldots,k\}\) and let
\[
\mathcal L_k
=\{(J,i):\varnothing\ne J\subseteq[k],\ i<\omega\}.
\]
The set \(\mathcal L_k\) is countably infinite. A label records a
nonempty set of tuple positions and an integer coordinate.
\begin{definition}[Valid diagrams]\label{col:diagram}
An \emph{arity-\(k\) diagram} is a triple
\(\mathcal D=(E,R,\rho)\), where \(E,R\) are binary relations on
\(\mathcal L_k\) and \(\rho:\mathcal L_k\to\delta\).
It is \emph{valid} if the following conditions hold.
\begin{enumerate}[label=\textup{(\roman*)}]
\item
\(E\) is an equivalence relation. The relation \(R\) and the tags
respect \(E\): whenever \(aEa'\) and \(bEb'\),
\[
aRb\ \Longleftrightarrow\ a'Rb',
\qquad
\rho(a)=\rho(a').
\]
\item
On the quotient \(Q_{\mathcal D}=\mathcal L_k/E\), use \(R\) and
\(\rho\) also for the induced relation and tag function. They satisfy
\[
yRx\ \Longrightarrow\ \rho(y)<\rho(x).
\]
The relation \(R\) is extensional: distinct \(x,x'\in Q_{\mathcal D}\)
have different predecessor sets
\[
\{y\in Q_{\mathcal D}:yRx\}
\quad\hbox{and}\quad
\{y\in Q_{\mathcal D}:yRx'\}.
\]
\item
The labels \((\{j\},0)\), for \(j\in[k]\), lie in pairwise distinct
\(E\)-classes.
\end{enumerate}
\end{definition}
Let \(\mathfrak D_k\) be the set of all arity-\(k\) diagrams,
including the invalid ones.
\begin{lemma}[Coding]\label{col:coding}
There are injections
\[
\iota_k:\mathfrak D_k\longrightarrow S
\qquad(k\ge1)
\]
whose ranges are pairwise disjoint.
\end{lemma}
\begin{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
\[
2^{\aleph_0}\le\kappa\cdot\aleph_0.
\]
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,
\[
\delta^{\aleph_0}
=(2^{\aleph_0})^{\aleph_0}
=2^{\aleph_0},
\]
so there are at most continuum many choices for \(\rho\) as well.
It follows that
\[
\left|\coprod_{k\ge1}\mathfrak D_k\right|
\le\aleph_0\cdot2^{\aleph_0}=|S|.
\]
An injection from this disjoint union into \(S\) gives the stated
maps.
\end{proof}
Fix such coding maps for the remainder of the proof. A color in
the range of \(\iota_k\) uniquely decodes to an arity-\(k\) diagram.
A color outside that range is not a code of the required arity.
The coding maps are fixed set parameters in the definition of the
class, not symbols of its language. Allowing codes for invalid
diagrams will let us assign colors at exceptional coordinates.
We next specify restriction, including its position reindexing.
If \(\varnothing\ne J\subseteq[k]\), enumerate
\(J=\{j_1<\cdots<j_m\}\) and define
\[
\ell_J:\mathcal L_m\longrightarrow\mathcal L_k,
\qquad
\ell_J(U,i)=(\{j_u:u\in U\},i).
\]
For an arity-\(k\) diagram \(\mathcal D\), its restriction
\(\mathcal D\restriction J\) is the arity-\(m\) diagram obtained
by pulling back both relations and the tag function along
\(\ell_J\). Thus it retains exactly those labels whose position
sets are contained in \(J\). In particular, for
\(\varnothing\ne U\subseteq[m]\),
\begin{equation}\label{col:restriction-composition}
(\mathcal D\restriction J)\restriction U
=\mathcal D\restriction\{j_u:u\in U\}.
\end{equation}
Validity of a diagram does not by itself guarantee extensionality
of a restriction; the tests below require validity of every
constituent diagram separately.
\begin{definition}[The full subsequence test]\label{col:test}
Given \(k\ge1\) and colors
\((s_J:\varnothing\ne J\subseteq[k])\), let
\[
T_k\bigl((s_J)_J\bigr)
\]
mean that both of the following conditions hold.
\begin{enumerate}[label=\textup{(\roman*)}]
\item
For every nonempty \(J\subseteq[k]\), the color \(s_J\) decodes
under \(\iota_{|J|}\) to a valid diagram \(\mathcal D_J\).
\item
For every nonempty \(J\subseteq[k]\),
\[
\mathcal D_J
=\mathcal D_{[k]}\restriction J.
\]
\end{enumerate}
For an ordered tuple \(t=(x_1,\ldots,x_k)\) of distinct elements,
write \(t\restriction J=(x_{j_1},\ldots,x_{j_m})\).
Colors attached to \(t\) and its nonempty subsequences pass the
test when \(T_k((s_{t\restriction J})_J)\) holds.
\end{definition}
The order in this definition is the order of the tuple positions.
It requires no order on the set from which tuple entries are
chosen. Equation~\eqref{col:restriction-composition} shows that
agreement with the full diagram implies agreement between every
two nested subsequences.
\begin{lemma}[Maps between quotient diagrams]\label{col:quotients}
Suppose the test in Definition~\ref{col:test} passes. If
\(\varnothing\ne J\subseteq[k]\), then the label map \(\ell_J\)
induces an injective map
\[
Q_{\mathcal D_J}\longrightarrow
Q_{\mathcal D_{[k]}}.
\]
This map preserves tags and preserves and reflects \(R\).
The quotient maps for nested subsequences compose.
\end{lemma}
\begin{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|}\),
\[
aE_Jb\ \Longleftrightarrow\
\ell_J(a)E_{[k]}\ell_J(b).
\]
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.
\end{proof}
The tests permit the tuple-dependent diagrams constructed in
Section~\ref{sec:endpoint}. They do not permit one fixed color \(s_j\)
for each arity \(j\) such that
\(T_k((s_{|J|})_{\varnothing\ne J\subseteq[k]})\) holds for every
\(k\ge1\). Lemma~\ref{col:no-pattern} will prove this obstruction;
it is the ingredient that later bounds models with uncountable base.
==== END A-CH-Obstruction-to-a-Prescribed-Categoricity-Threshold//01-colors.tex ====
==== BEGIN A-CH-Obstruction-to-a-Prescribed-Categoricity-Threshold//02-aec.tex ====
\section{The abstract elementary class}\label{sec:aec}
We now turn the tests of Section~\ref{sec:colors} into a class of
structures. The distinction between the object condition and the strong
substructure condition is essential: objects allow countably many bad
coordinates for each tuple, whereas a strong extension must introduce no
bad coordinate for an old tuple outside the old base order.
\subsection{The axioms and the basic structures}
\begin{definition}[Abstract elementary class]\label{aec:definition}
An \emph{abstract elementary class} is a pair
\(K=(\mathcal C,\le_K)\), where \(\mathcal C\) is a class of set-sized
structures in one fixed set-sized finitary language \(\tau\), and
\(\le_K\) is a partial order on \(\mathcal C\), with the following
properties. Write \(|M|\) for a structure's underlying set and
\(\|M\|\) for its cardinality.
\begin{enumerate}[label=\textup{(\arabic*)}]
\item \emph{Isomorphisms and substructures.}
The class is closed under \(\tau\)-isomorphisms; \(M\le_K N\) implies
that \(M\) is a \(\tau\)-substructure of \(N\); and if
\(f:N\cong N'\) and \(M\le_K N\), then \(f[M]\le_K N'\).
\item \emph{Coherence.}
If \(M_0\) is a \(\tau\)-substructure of \(M_1\), and
\(M_0\le_K M_2\) and \(M_1\le_K M_2\), then \(M_0\le_K M_1\).
\item \emph{Unions and smoothness.}
For every nonzero ordinal \(\gamma\) and every increasing chain
\((M_i:i<\gamma)\) under \(\le_K\), its union \(U\) belongs to
\(\mathcal C\), and \(M_i\le_K U\) for all \(i<\gamma\).
If also \(M_i\le_K N\) for every \(i<\gamma\), where
\(N\in\mathcal C\), then \(U\le_K N\).
\item \emph{Downward L\"owenheim--Skolem property.}
There is an infinite cardinal
\(\theta\ge|\tau|+\aleph_0\) such that, for every \(M\in\mathcal C\)
and every \(A\subseteq |M|\), there exists \(N\le_K M\) with
\(A\subseteq |N|\) and \(\|N\|\le |A|+\theta\).
\end{enumerate}
The least such infinite cardinal \(\theta\) is denoted by \(\LS(K)\).
\end{definition}
We will prove the union and common-upper-bound assertions directly for
every nonempty set-indexed directed family of strong substructures. This
in particular proves all the chain assertions in
Definition~\ref{aec:definition}, with no restriction on the chain's
cofinality.
For a nonempty set \(I\), let \(\mathcal T(I)\) be the set of all
nonempty finite ordered tuples of distinct members of \(I\).
If \(t=(a_1,\ldots,a_k)\) and
\(\varnothing\ne J\subseteq[k]\), write \(t\restriction J\) for the subsequence in
the original order. No order is placed on the sort \(I\).
Finite-support groups and torsors also occur in the Hart--Shelah
construction \cite[Section~1]{HartShelah1990};
see also \cite[Definition~3.1 and Fact~3.2]{BoneyVasey2018HartShelah}.
We specify two families of torsors, one for rows and one for columns,
and the precise finite-support action on their common bit relation.
\begin{definition}[Basic structures]\label{aec:basic}
A basic structure has the following data, with pairwise disjoint
underlying carriers.
\begin{enumerate}[label=\textup{(\alph*)}]
\item A nonempty set \(I\), and a nonempty dense linear order \(B\)
without endpoints in which every bounded interval is countable.
\item A group sort \(G(B)\) coding \([B]^{<\omega}\) under symmetric
difference. More precisely, an incidence relation determines a
bijection
\[
\supp:G(B)\longrightarrow[B]^{<\omega},
\qquad
\supp(u+u')=\supp(u)\SymDiff\supp(u').
\]
There is also a group sort \(G_*\) identified, by a separate unary
singleton label for each of its elements, with
\([\omega]^{<\omega}\) under symmetric difference. These labels
exhaust \(G_*\).
\item For each \(t\in\mathcal T(I)\) and \(n<\omega\), a nonempty
set \(Z_{t,n}\) with a free transitive action of \(G(B)\). For each
\(t\in\mathcal T(I)\) and \(b\in B\), a nonempty set \(W_{t,b}\)
with a free transitive action of \(G_*\). We write both actions
additively. Thus each element of a fiber is obtained uniquely by
translating any one chosen element of that fiber.
\item A binary relation on row and column points, written as its
indicator \(e(z,w)\in\{0,1\}\). It can hold only when the row and
column have the same tuple \(t\). On these pairs it satisfies
\begin{equation}\label{aec:bit}
e(z+u,w+v)
=
e(z,w)+\boldsymbol 1_{b\in\supp(u)}
+\boldsymbol 1_{n\in v}\pmod 2
\end{equation}
for \(z\in Z_{t,n}\), \(w\in W_{t,b}\), \(u\in G(B)\), and
\(v\in G_*\). In the last term \(v\) is read through its fixed
finite-subset label. Here \(\boldsymbol 1_P\) is \(1\) when
\(P\) holds and \(0\) otherwise.
\end{enumerate}
The domain consists exactly of the listed carriers. There are no
additional relations or distinguished representatives.
\end{definition}
Here is an explicit countable finitary relational language for these
data. Use unary predicates for \(I,B,G(B),G_*\), for each carrier
\[
Z_{k,n}=\bigcup_{\substack{t\in\mathcal T(I)\\|t|=k}}Z_{t,n}
\quad(k\ge1,\ n<\omega),
\qquad
W_k=\bigcup_{\substack{t\in\mathcal T(I)\\|t|=k,\ b\in B}}W_{t,b},
\]
and for each singleton label in \(G_*\). The carrier predicates,
excluding the labels within \(G_*\), partition the domain.
For each \(k,n\), a \((k+1)\)-ary projection graph associates a
row point with its \(k\) tuple entries. For each \(k\), a
\((k+2)\)-ary projection graph associates a column point with its
tuple entries and its coordinate \(b\). These projections are
semantically total and single-valued on their carriers, have distinct
tuple coordinates in \(I\), and have exactly the nonempty fibers
required in Definition~\ref{aec:basic}. A carrier may be empty if
there are no tuples of its length.
Use binary relations for the order, finite-set incidence, and the
bit relation, and ternary graphs for group operations and the two
actions. Every operation and action is semantically total on its
stated domain. Operation graphs give precisely the specified groups;
action graphs preserve the indicated fibers and give precisely the
free transitive actions. There are no relation instances outside
these specified types. In particular, bits between different tuple
fibers are zero. This last requirement rules out any unspecified
structure linking different tuples.
All the symbols just listed are indexed by countable sets, and each
has finite arity. The language is therefore countable and finitary.
Using operation graphs is harmless: in an inclusion of induced
relational substructures, a graph triple already in the smaller
object remains in the larger one. Semantic uniqueness in the larger
object forces it to give the same operation or action value on the
old arguments. The smaller object's semantic totality supplies the
needed closure on those arguments.
The fixed coding maps and tests from Section~\ref{sec:colors} are set
parameters in the definition of the class, not additional language
symbols. Neither the countability restrictions nor the condition
using these tests needs to be first-order expressible.
\begin{definition}[Basic inclusion]\label{aec:basic-inclusion}
For basic structures \(M_0,M_1\), write
\(M_0\preccurlyeq_{\mathrm b}M_1\) if \(M_0\) is an induced
\(\tau\)-substructure of \(M_1\), and the following further conditions
hold:
\begin{enumerate}[label=\textup{(\roman*)}]
\item \(G_*^{M_0}=G_*^{M_1}\) as underlying sets;
\item \(B^{M_0}\) is a convex suborder of \(B^{M_1}\);
\item for every \(u\in G(B)^{M_0}\),
\(\supp^{M_1}(u)=\supp^{M_0}(u)\).
\end{enumerate}
All inclusions here and below allow equality.
\end{definition}
Condition (iii) forbids an old finite-set code from acquiring new
members in the larger base order. Since support gives a bijection
onto finite subsets in both objects, this condition makes the old
group exactly the naturally included copy of
\([B^{M_0}]^{<\omega}\) in \([B^{M_1}]^{<\omega}\). The group
elements themselves may have arbitrary underlying codes.
Basic inclusions compose: induced substructures, convexity,
equality of \(G_*\), and support preservation each compose.
\begin{lemma}[Size of the base order]\label{aec:order-size}
Every order \(B\) in a basic structure has cardinality at most
\(\aleph_1\).
\end{lemma}
\begin{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.
\end{proof}
\begin{lemma}[Size of a basic structure]\label{aec:size}
For every basic structure \(M\),
\begin{equation}\label{aec:size-equation}
\|M\|=\max\bigl(|I^M|,|B^M|,\aleph_0\bigr).
\end{equation}
\end{lemma}
\begin{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\).
\end{proof}
\subsection{Colors, objects, and strong inclusions}
A \emph{row-choice system} in a basic structure is a family
\(\mathbf z=(z_{t,n}:t\in\mathcal T(I),\,n<\omega)\) with
\(z_{t,n}\in Z_{t,n}\). Such systems exist by choice, since the
structure and the indexing set are set-sized. For \(b\in B\) define
\begin{equation}\label{aec:color}
c_t^{\mathbf z}(b)
=
\bigl[(e(z_{t,n},w))_{n<\omega}\bigr]_{=^*}\in S,
\qquad w\in W_{t,b}.
\end{equation}
\begin{lemma}[Representative independence]\label{aec:representatives}
The color in \eqref{aec:color} is independent of \(w\).
If \(\mathbf z,\mathbf z'\) are two row-choice systems, then,
for each fixed \(t\), their colors \(c_t^{\mathbf z}(b)\) and
\(c_t^{\mathbf z'}(b)\) agree outside a countable subset of \(B\).
The full subsequence test for a fixed tuple therefore has the
same truth value for the two systems outside a countable set.
More strongly, suppose \(M_0\preccurlyeq_{\mathrm b}M_1\).
For a tuple in \(\mathcal T(I^{M_0})\) and a point
\(b\in B^{M_1}\setminus B^{M_0}\), compute colors in \(M_1\)
using row representatives from \(M_0\). These colors are
independent of every such row choice, with no exceptional
coordinates.
\end{lemma}
\begin{proof}
Two column representatives differ by a translator \(v\in G_*\).
Equation~\eqref{aec:bit} 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
\[
D_t=\bigcup_{n<\omega}\supp(u_{t,n}).
\]
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~\eqref{aec:bit}
therefore leaves every individual bit unchanged. This proves
the stronger assertion.
\end{proof}
For a row-choice system \(\mathbf z\) and a tuple
\(t=(a_1,\ldots,a_k)\), let
\begin{equation}\label{aec:bad-set}
E_t(\mathbf z)=
\left\{b\in B:
\neg T_k\bigl((c_{t\restriction J}^{\mathbf z}(b))_{\varnothing\ne J\subseteq[k]}\bigr)
\right\},
\end{equation}
where \(T_k\) is the full subsequence test of
Definition~\ref{col:test}.
\begin{definition}[Objects and strong substructures]\label{aec:objects}
A basic structure is an \emph{object} if \(E_t(\mathbf z)\) is
countable for every \(t\in\mathcal T(I)\), for one, equivalently
every, row-choice system \(\mathbf z\).
Let \(\mathcal C\) be the class of objects.
For \(M_0,M_1\in\mathcal C\), declare \(M_0\le_K M_1\) if
\(M_0\preccurlyeq_{\mathrm b}M_1\), and, for every
\(t\in\mathcal T(I^{M_0})\) and every
\(b\in B^{M_1}\setminus B^{M_0}\), the full test for \(t\)
passes when its colors in \(M_1\) are computed using row
representatives in \(M_0\), for \(t\) and all its nonempty
subsequences. Put \(K=(\mathcal C,\le_K)\).
\end{definition}
Both formulations are well-defined by
Lemma~\ref{aec:representatives}. The exceptional set in the
object condition is allowed to depend on \(t\); no single
countable set is required to work for all tuples. In a strong
inclusion, there are no exceptions among the new base-order
points.
\begin{lemma}[Free realization of bit arrays]\label{aec:arrays}
Let \(I\ne\varnothing\), and let \(B\) be an order satisfying
Definition~\ref{aec:basic}(a). For every family of binary
sequences
\((a_{t,b}\in 2^\omega:t\in\mathcal T(I),\,b\in B)\),
there is a basic structure whose index and base sorts are disjoint
copies of \(I\) and \(B\), with row-choice colors, under these
identifications,
\[
c_t(b)=[a_{t,b}]_{=^*}.
\]
If \(B\) is countable, every basic structure with base sort
\(B\) is an object.
\end{lemma}
\begin{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
\begin{equation}\label{aec:array-realization}
e((t,n,u),(t,b,v))
=
a_{t,b}(n)+\boldsymbol 1_{b\in u}
+\boldsymbol 1_{n\in v}\pmod2.
\end{equation}
Set bits between different tuples to zero, and equip the
carriers with exactly the specified projections and other
relations. Translation by symmetric difference gives
\eqref{aec:bit}. 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.
\end{proof}
\subsection{Isomorphisms, the partial order, and coherence}
\begin{lemma}\label{aec:order-coherence}
The class and strong relation are isomorphism invariant,
\(\le_K\) is a partial order whose comparisons are induced
substructure inclusions, and coherence holds.
\end{lemma}
\begin{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\).
\end{proof}
\subsection{Directed unions and smoothness}
\begin{lemma}\label{aec:directed}
Let \((M_i:i\in D)\) be a nonempty set-indexed family of
objects directed under strong inclusion: any two members
have a common strong upper bound within the family.
Its union \(U\) is an object, and \(M_i\le_K U\) for every
\(i\in D\). If \(N\) is an object with \(M_i\le_K N\)
for all \(i\in D\), then \(U\le_K N\).
\end{lemma}
\begin{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\).
\emph{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~\eqref{aec:bit} 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\).
\emph{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~\ref{aec:representatives}
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.
\emph{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\).
\emph{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~\ref{aec:representatives}, makes this one
choice sufficient. Hence \(U\le_K N\).
\end{proof}
The proof does not put an arbitrary preselected countable
set of union row points into one stage. It first puts the
finite tuple into a member and then selects all the needed
row representatives there. This is what permits both the
object-condition argument and smoothness at chains of
countable cofinality.
\subsection{The downward L\"owenheim--Skolem bound}
We first record explicitly the small convex-hull fact
needed for arbitrary requested subsets.
\begin{lemma}\label{aec:convex-hull}
Let \(B\) be a nonempty dense linear order without
endpoints, with countable bounded intervals. For every
infinite cardinal \(\kappa\) and every \(D\subseteq B\)
of size at most \(\kappa\), there is a nonempty convex
suborder \(B_0\) containing \(D\), of size at most
\(\kappa\), which is dense and has no endpoints.
\end{lemma}
\begin{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
\[
B_0=\{b\in B:\text{there exist }x,y\in T
\text{ with }x\le b\le y\}.
\]
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.
\end{proof}
\begin{lemma}\label{aec:ls}
For every \(M\in\mathcal C\) and every
\(A\subseteq |M|\), there is \(N\le_K M\) such that
\(A\subseteq |N|\) and
\(\|N\|\le |A|+\aleph_0\).
\end{lemma}
\begin{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:
\begin{enumerate}[label=\textup{(\roman*)}]
\item all points of \(A\cap B^M\), and all
base-point projections of column elements of \(A\);
\item \(\supp(u)\) for every
\(u\in A\cap G(B)^M\);
\item 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\);
\item all the sets \(E_t\), for
\(t\in\mathcal T(I_0)\).
\end{enumerate}
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~\ref{aec:convex-hull} to obtain a
nonempty convex dense \(B_0\subseteq B^M\)
without endpoints, containing \(D\), of size
at most \(\kappa\).
Let
\[
H=\{u\in G(B)^M:\supp^M(u)\subseteq B_0\}.
\]
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
\begin{align*}
Z^N_{t,n}&=\{z_{t,n}+u:u\in H\}
&&(t\in\mathcal T(I_0),\ n<\omega),\\
W^N_{t,b}&=W^M_{t,b}
&&(t\in\mathcal T(I_0),\ b\in B_0),
\end{align*}
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~\eqref{aec:bit} 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~\ref{aec:size} gives
\[
\|N\|=\max(|I_0|,|B_0|,\aleph_0)
\le\kappa,
\]
as required.
\end{proof}
\begin{theorem}\label{aec:class}
The pair \(K=(\mathcal C,\le_K)\) of
Definition~\ref{aec:objects} is an abstract
elementary class in a fixed countable finitary
relational language, with
\[
\LS(K)=\aleph_0.
\]
It has the union and common-upper-bound
properties for every nonempty set-indexed
directed family of strong substructures.
\end{theorem}
\begin{proof}
The language and its semantic structures were
specified after Definition~\ref{aec:basic}.
Lemma~\ref{aec:order-coherence} proves
isomorphism invariance, substructure, the
partial-order properties, and coherence.
Lemma~\ref{aec:directed} proves the directed
union and smoothness assertions, in
particular the required chain axioms.
Lemma~\ref{aec:ls} 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.
\end{proof}
==== END A-CH-Obstruction-to-a-Prescribed-Categoricity-Threshold//02-aec.tex ====
==== BEGIN A-CH-Obstruction-to-a-Prescribed-Categoricity-Threshold//03-categoricity.tex ====
\section{A bound on uncountable base orders and categoricity on a tail}
\label{sec:categoricity}
Continue to work in ZFC with CH and with the class $K$ of
Section~\ref{sec:aec}. Recall the cardinals
\[
\delta=\omega_1,\qquad \xi=2^\delta,
\qquad \Lambda=\beth_{\xi^+}.
\]
Section~\ref{sec:endpoint} has supplied an object with uncountable $B$.
Its diagrams depend on the tuple and the coordinate, and their validity
has tuple-dependent countable exceptions. We first rule out a stronger
configuration: one fixed color for each arity passing every finite test.
A finite partition argument then forces precisely this configuration
if an uncountable-base object has at least $\Lambda$ index points.
This proves the universal bound $|I|<\Lambda$ for such objects.
Categoricity at and above $\Lambda$ will then follow by classifying the
remaining, countable-base objects through a matrix isomorphism calculation.
\subsection{The obstruction to a fixed pattern}
We first give the rank argument used to bound a diagram limit.
It is the ordinal-tagged form of the Mostowski collapse
\cite{Mostowski1949}; the construction and its range bound are proved
below. The following lemma concerns a set, with no countability
assumption on it or on its predecessor sets.
\begin{lemma}[Collapse of the tagged relation]\label{col:collapse}
Let \(Q\) be a set with an extensional binary relation \(R\) and
a function \(\rho:Q\to\delta\) such that
\[
yRx\ \Longrightarrow\ \rho(y)<\rho(x).
\]
Then there is an injection \(F:Q\to V_\delta\) satisfying
\[
F(x)=\{F(y):yRx\}.
\]
More precisely, \(F(x)\in V_{\rho(x)+1}\) for every \(x\in Q\).
\end{lemma}
\begin{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
\[
F(y)\in V_{\beta+1}\subseteq V_\alpha,
\qquad \beta<\alpha.
\]
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.
\end{proof}
The proof uses the whole powerset \(V_{\alpha+1}=\mathcal P(V_\alpha)\).
Thus the bound remains valid when many local diagrams contribute
predecessors to the same element.
\begin{lemma}[No fixed pattern at all finite arities]\label{col:no-pattern}
There is no sequence \((s_j:j\ge1)\) of elements of \(S\) such that
\begin{equation}\label{col:fixed-pattern}
T_k\bigl((s_{|J|})_{\varnothing\ne J\subseteq[k]}\bigr)
\quad\text{holds for every }k\ge1.
\end{equation}
\end{lemma}
\begin{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
\begin{equation}\label{col:pattern-restrictions}
\mathcal D_k\restriction J=\mathcal D_{|J|}
\qquad(\varnothing\ne J\subseteq[k]).
\end{equation}
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
\[
\{(U,i):\varnothing\ne U\subseteq A,\ i<\omega\}.
\]
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~\eqref{col:pattern-restrictions} give a map
\[
j_{A,B}:Q_A\longrightarrow Q_B.
\]
By Lemma~\ref{col:quotients}, these maps are injective, preserve
tags, preserve and reflect the relation, and satisfy
\[
j_{B,C}j_{A,B}=j_{A,C}
\qquad(A\subseteq B\subseteq C).
\]
We construct their limit explicitly. Form the set
\[
P=\{(A,a):\varnothing\ne A\subseteq X
\text{ is finite},\ a\in Q_A\}.
\]
This is a set-indexed union of countable sets. Declare
\begin{equation}\label{col:limit-equivalence}
(A,a)\sim(B,b)
\quad\Longleftrightarrow\quad
j_{A,A\cup B}(a)=j_{B,A\cup B}(b).
\end{equation}
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
\[
j_Bj_{A,B}=j_A.
\]
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
\begin{equation}\label{col:limit-relation}
j_B(b)\,R\,j_A(a)
\quad\Longleftrightarrow\quad
j_{B,C}(b)\,R_C\,j_{A,C}(a).
\end{equation}
These definitions are independent of the representatives.
Indeed, representatives that describe the same limit points
become equal in a finite common stage by
Equation~\eqref{col:limit-equivalence}. Taking the union of
that stage with all stages used in
Equation~\eqref{col:limit-relation} 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
\[
yRx\ \Longrightarrow\ \rho(y)<\rho(x)
\qquad(x,y\in Q).
\]
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
\[
bR_Aa,\qquad \neg(bR_Aa').
\]
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
\textup{(iii)} of Definition~\ref{col:diagram}, 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
\[
|X|\le |Q|.
\]
Lemma~\ref{col:collapse} applies to the set \(Q\), with
its extensional relation and tags below \(\delta\).
It gives an injection into \(V_\delta\), whence
\[
|X|\le |Q|\le |V_\delta|.
\]
This contradicts the choice of \(X\).
\end{proof}
\begin{remark}[What the pattern quantifiers require]
\label{col:pattern-quantifiers}
Lemma~\ref{col:no-pattern} rules out one fixed sequence of
colors satisfying every finite test. To obtain the
contradiction, it is enough to find, for each \(k\), a
separate ordered \(k\)-tuple whose \(j\)-element subsequences
all have color \(s_j\), and whose full subsequence test
passes. Each such tuple certifies precisely the instance
of Equation~\eqref{col:fixed-pattern} for that \(k\).
The tuples need not be nested or come from a common
infinite homogeneous set: the fixed colors determine
the same decoded diagrams, and the tests determine
every increasing position restriction between them.
This is the form used below in Proposition~\ref{cat:bounded}.
\end{remark}
\subsection{The cardinal and finite partition estimates}
The finite-arity proof uses the end-homogeneous method of classical
partition calculus \cite{ErdosRado1956}. We give the particular estimate
and the subsequent selection of fixed colors explicitly, so their
cardinal bounds and quantifiers are part of the argument.
For a set $X$ and a positive integer $m$, write $[X]^m$ for its
$m$-element subsets. A subset $Y\subseteq X$ is \emph{homogeneous} for
a map $c:[X]^m\to C$ if $c$ is constant on $[Y]^m$.
Cardinals used as ordered sets below are identified with their initial
ordinals.
\begin{lemma}\label{cat:cardinals}
The cardinal $\Lambda$ is a strong limit and
\[
\cf(\Lambda)=\xi^+>\xi.
\]
If $\zeta<\Lambda$ is infinite, then both $\xi^\zeta$ and
$(\xi^\zeta)^+$ are below $\Lambda$.
\end{lemma}
\begin{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
\[
\Lambda=\sup_{\alpha<\kappa}\beth_\alpha.
\]
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$,
\[
2^\nu\le 2^{\beth_\alpha}=\beth_{\alpha+1}<\Lambda.
\]
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$,
\[
\xi^\zeta\le (2^\xi)^\zeta
=2^{\xi\cdot\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$.
\end{proof}
\begin{lemma}[Finite partition estimate]\label{cat:finite-partition}
For every positive integer $m$ and every infinite cardinal
$\chi<\Lambda$, there is a cardinal $\mu<\Lambda$ such that every
map $c:[\mu]^m\to C$ with $|C|\le\xi$ has a homogeneous subset of
cardinality $\chi$.
\end{lemma}
\begin{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
\[
\mu=(\max(\xi,\chi))^+<\Lambda.
\]
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
\[
q=\xi^\zeta,\qquad \mu=q^+<\Lambda,
\]
where the last inequality follows from Lemma~\ref{cat:cardinals}.
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
\begin{equation}\label{cat:profile-codes}
\iota_\alpha:{}^{[\alpha+1]^m}\xi\longrightarrow q.
\end{equation}
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.
\begin{enumerate}[label=(\roman*)]
\item At the root, put $X_\varnothing=\mu$.
\item 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
\begin{equation}\label{cat:profile}
u_{s,y}(a)=c\bigl(\{r_{s\upharpoonright\beta}:\beta\in a\}
\cup\{y\}\bigr),
\qquad a\in[\alpha+1]^m.
\end{equation}
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.
\item If $\gamma\le\zeta$ is a nonzero limit ordinal and
$s\in{}^\gamma q$, put
\begin{equation}\label{cat:limit-residual}
X_s=\bigcap_{\alpha<\gamma}X_{s\upharpoonright\alpha}.
\end{equation}
\end{enumerate}
Only nodes with nonempty residuals matter. Every such node has
nonempty ancestral residuals, so all representatives in
\eqref{cat:profile} 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 \eqref{cat:profile} 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
\begin{equation}\label{cat:tree-count}
\left|\bigcup_{\alpha\le\zeta}{}^\alpha q\right|
\le |\zeta+1|\cdot q^\zeta
=\zeta\cdot(\xi^\zeta)^\zeta
=\xi^\zeta=q.
\end{equation}
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
\eqref{cat:limit-residual} along the branch already constructed.
Thus the branch cannot disappear at a limit. Write its named
representatives as
\[
r_\alpha\quad(\alpha<\zeta),
\qquad P=\{r_\alpha:\alpha<\zeta\}.
\]
They increase strictly and are all less than $x$, so $|P|=\zeta$.
Define a coloring of the preceding arity by
\[
d:[P]^m\longrightarrow\xi,
\qquad d(A)=c(A\cup\{x\}).
\]
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
\begin{equation}\label{cat:arity-reduction}
c(\{r_{\alpha_0},\ldots,r_{\alpha_m}\})
=d(\{r_{\alpha_0},\ldots,r_{\alpha_{m-1}}\}).
\end{equation}
By the choice of $\zeta$, the map $d$ has a homogeneous subset
$H\subseteq P$ of cardinality $\chi$. Equation~\eqref{cat:arity-reduction}
shows that $H$ is homogeneous for $c$ as well. This proves the
induction step.
\end{proof}
\subsection{Extracting a forbidden pattern}
The next lemma combines the finite partition estimates without
asserting the existence of a common infinite homogeneous subset.
\begin{lemma}\label{cat:finite-patterns}
Let $X$ be a set with $|X|\ge\Lambda$. For each positive integer
$j$, let $c_j:[X]^j\to C_j$, where $|C_j|\le\xi$. There are colors
$p_j\in C_j$ such that for every positive integer $k$ there is
$A_k\in[X]^k$ satisfying
\[
c_j(A)=p_j\qquad
(1\le j\le k,\ A\in[A_k]^j).
\]
The sets $A_k$ need not be nested.
\end{lemma}
\begin{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~\ref{cat:finite-partition} 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$.
\end{proof}
\begin{proposition}\label{cat:bounded}
If $M\in K$ and $B^M$ is uncountable, then $|I^M|<\Lambda$.
\end{proposition}
\begin{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
\[
c_t:B^M\longrightarrow S
\]
be the resulting color profile of $t$, as defined in
Section~\ref{sec:aec}. By CH, $|S|=\delta$, and
Lemma~\ref{aec:order-size} gives $|B^M|\le\delta$. Thus the palette
of whole profiles has size at most
\begin{equation}\label{cat:palette}
|S^{B^M}|\le\delta^\delta=2^\delta=\xi.
\end{equation}
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~\ref{cat:finite-patterns}
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
\[
E=\bigcup_{1\le k<\omega}E_k
\]
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
\[
T_k\bigl((s_{|J|})_{\varnothing\ne J\subseteq\{1,\ldots,k\}}\bigr).
\]
This is the sequence forbidden by Lemma~\ref{col:no-pattern}.
The contradiction proves the bound.
\end{proof}
\begin{remark}\label{cat:separate-witnesses}
The witness tuples $t_k$ may be unrelated. At the chosen coordinate
$b$, the length-$k$ witness certifies validity of the one diagram
decoded from $s_k$, together with its restrictions along every
increasing inclusion of positions. Those fixed diagrams are exactly
the data to which Lemma~\ref{col:no-pattern} applies. The proof uses
only countably many full-tuple exceptional sets; it does not seek a
coordinate good for every tuple in $I^M$.
\end{remark}
\subsection{Isomorphisms when the base order is countable}
\begin{lemma}\label{cat:countable-base}
If $M,N\in K$ have countable base orders and $|I^M|=|I^N|$, then
$M\cong N$.
\end{lemma}
\begin{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
\[
\widehat g:G(B^M)\longrightarrow G(B^N),
\qquad u\longmapsto g[u],
\]
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
\[
\begin{array}{ll}
z_n\in Z^M_{t,n},&w_k\in W^M_{t,b_k},\\
z'_n\in Z^N_{f(t),n},&w'_k\in W^N_{f(t),g(b_k)}.
\end{array}
\]
Write their bit matrices as
\[
a(n,k)=e^M(z_n,w_k),\qquad
a'(n,k)=e^N(z'_n,w'_k),
\]
and let $d(n,k)=a(n,k)+a'(n,k)$, with addition in $\mathbb Z/2\mathbb Z$.
Define translators by
\begin{equation}\label{cat:triangle-supports}
\begin{split}
U_n&=\{g(b_k):k\le n\text{ and }d(n,k)=1\}\in G(B^N),\\
V_k&=\{n:n<k\text{ and }d(n,k)=1\}\in G_*.
\end{split}
\end{equation}
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 \eqref{cat:triangle-supports} partition the matrix, so
\begin{equation}\label{cat:triangle-equation}
\boldsymbol 1_{g(b_k)\in U_n}
+\boldsymbol 1_{n\in V_k}=d(n,k)\pmod2
\qquad(n,k<\omega).
\end{equation}
Figure~\ref{fig:matrix-decomposition} illustrates this allocation of
finite supports.
\input{figures/matrix-decomposition}
Set $\widetilde z'_n=z'_n+U_n$ and
$\widetilde w'_k=w'_k+V_k$. The action equation for the bit relation
and \eqref{cat:triangle-equation} give
\[
e^N(\widetilde z'_n,\widetilde w'_k)
=a'(n,k)+d(n,k)=a(n,k).
\]
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
\begin{equation}\label{cat:equivariant-maps}
\begin{aligned}
z_n+u&\longmapsto\widetilde z'_n+\widehat g(u)
&&(u\in G(B^M)),\\
w_k+v&\longmapsto\widetilde w'_k+v
&&(v\in G_*).
\end{aligned}
\end{equation}
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
\[
\begin{split}
e^N(\widetilde z'_n+\widehat g(u),\widetilde w'_k+v)
&=a(n,k)+\boldsymbol 1_{g(b_k)\in\widehat g(u)}
+\boldsymbol 1_{n\in v}\\
&=a(n,k)+\boldsymbol 1_{b_k\in u}+\boldsymbol 1_{n\in v}\\
&=e^M(z_n+u,w_k+v).
\end{split}
\]
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.
\end{proof}
\begin{theorem}\label{cat:tail}
The class $K$ is categorical in every cardinal $\mu\ge\Lambda$.
\end{theorem}
\begin{proof}
Fix such a cardinal $\mu$. By Lemma~\ref{aec:arrays}, 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~\ref{aec:size} gives cardinality exactly $\mu$, proving
existence.
Now let $M\in K$ have cardinality $\mu$. By
Lemmas~\ref{aec:order-size} and~\ref{aec:size},
\[
|B^M|\le\delta<\Lambda\le\mu,
\qquad
\mu=\max(|I^M|,|B^M|,\aleph_0).
\]
It follows that $|I^M|=\mu$. Proposition~\ref{cat:bounded} 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~\ref{cat:countable-base} makes them isomorphic. This proves
existence of exactly one isomorphism type at every $\mu\ge\Lambda$,
including $\mu=\Lambda$ itself.
\end{proof}
==== END A-CH-Obstruction-to-a-Prescribed-Categoricity-Threshold//03-categoricity.tex ====
==== BEGIN A-CH-Obstruction-to-a-Prescribed-Categoricity-Threshold//04-endpoint.tex ====
\section{Two models at the prescribed endpoint}\label{sec:endpoint}
We construct an object whose index sort is \(V_\eta\) and whose order sort
has cardinality \(\delta\), where
\[
\delta=\omega_1,\qquad \eta=\delta^+=\omega_2.
\]
The construction assigns to every finite tuple a countable extensional
membership diagram. Actual ranks below \(\eta\) are replaced, separately
at each order point, by tags below \(\delta\). For any one tuple, all
required inequalities hold outside a countable set of order points.
The exception set is allowed to depend on the tuple, as in the definition
of \(K\).
\subsection{Ranks represented modulo countable sets}
\begin{lemma}\label{end:domination}
There are functions \(f_\alpha:\delta\longrightarrow\delta\), for
\(\alpha<\eta\), such that for all \(\gamma<\alpha<\eta\) the set
\[
E_{\gamma,\alpha}
=\{\beta<\delta:f_\gamma(\beta)\geq f_\alpha(\beta)\}
\]
is countable.
\end{lemma}
\begin{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
\begin{equation}\label{end:diagonal-formula}
f_\alpha(\beta)
=
\sup\{f_\gamma(\beta)+1:
\gamma<\alpha,\ j_\alpha(\gamma)<\beta\},
\qquad \sup\varnothing=0.
\end{equation}
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
\eqref{end:diagonal-formula}. Hence
\[
f_\gamma(\beta)<f_\alpha(\beta),
\qquad
E_{\gamma,\alpha}\subseteq j_\alpha(\gamma)+1.
\]
The latter ordinal is countable, proving the assertion.
\end{proof}
\begin{lemma}\label{end:hierarchy-size}
The cumulative hierarchy satisfies
\[
|V_{\omega+\gamma}|=\beth_\gamma
\quad\text{for every ordinal }\gamma.
\]
In particular, \(|V_\eta|=\beth_\eta\), and every element of \(V_\eta\)
has rank below \(\eta\).
\end{lemma}
\begin{proof}
The set \(V_\omega\) of hereditarily finite sets is countably
infinite, giving the assertion at \(\gamma=0\). At a successor
stage,
\[
|V_{\omega+(\gamma+1)}|
=|\mathcal P(V_{\omega+\gamma})|
=2^{\beth_\gamma}
=\beth_{\gamma+1}.
\]
If \(\gamma\) is a nonzero limit ordinal, continuity of ordinal
addition and of the cumulative hierarchy gives
\[
V_{\omega+\gamma}
=\bigcup_{\zeta<\gamma} V_{\omega+\zeta}.
\]
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\).
\end{proof}
\subsection{Compatible countable membership diagrams}
Put \(D=V_\eta\). We first choose a countable set of diagram
entries for each nonempty finite subset of \(D\). The closure
below ensures extensionality separately for every such set.
Starting from a nonempty countable set of entries, we repeatedly
adjoin one distinguishing membership witness for each pair of
distinct entries. The resulting set remains countable and has an
extensional membership relation, even when the entries themselves
are large sets.
\begin{lemma}\label{end:countable-closures}
There is a family
\[
(D_X:\varnothing\ne X\in[D]^{<\omega})
\]
of nonempty countable subsets of \(D\) such that:
\begin{enumerate}[label=\textup{(\roman*)}]
\item \(X\subseteq D_X\);
\item \(D_Y\subseteq D_X\) whenever
\(\varnothing\ne Y\subseteq X\);
\item the relation of actual membership on \(D_X\) is
extensional: for distinct \(a,b\in D_X\), some
\(w\in D_X\) belongs to exactly one of \(a,b\).
\end{enumerate}
We may also fix surjections \(d_X:\omega\longrightarrow D_X\)
such that \(d_{\{x\}}(0)=x\) for each \(x\in D\).
\end{lemma}
\begin{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
\[
A_0=A,\qquad
A_{n+1}=A_n\cup
\{w(a,b):a,b\in A_n,\ a\ne b\},
\qquad
C(A)=\bigcup_{n<\omega}A_n.
\]
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
\[
D_X=C\left(
X\cup
\bigcup_{\varnothing\ne Y\subsetneq X}D_Y
\right).
\]
The seed is nonempty and countable, because there are only
finitely many proper subsets of \(X\). This proves
\textup{(i)} and \textup{(iii)} and directly gives
\textup{(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.
\end{proof}
Fix the functions from Lemma~\ref{end:domination} and the
sets and enumerations from Lemma~\ref{end:countable-closures}.
For every nonempty finite \(X\subseteq D\), define
\begin{equation}\label{end:bad-set}
F_X=
\bigcup_{\substack{x,y\in D_X\\y\in x}}
E_{\rank(y),\rank(x)}.
\end{equation}
Each index pair is legitimate:
\(\rank(y)<\rank(x)<\eta\). There are countably many
pairs in the union, so \(F_X\) is countable. Moreover,
\begin{equation}\label{end:bad-monotone}
\varnothing\ne Y\subseteq X
\quad\Longrightarrow\quad
F_Y\subseteq F_X.
\end{equation}
Indeed, \(D_Y\subseteq D_X\), so every edge used to define
\(F_Y\) is also used to define \(F_X\).
We use the label sets and the coding maps of
Section~\ref{sec:colors}. For an ordered tuple
\[
t=(x_1,\ldots,x_k)
\]
of distinct elements of \(D\), write \(X=\{x_1,\ldots,x_k\}\).
If \(\varnothing\ne J\subseteq[k]\), let
\(X_J=\{x_j:j\in J\}\). Define a map from the label set
\(\mathcal L_k\) by
\[
q_t(J,i)=d_{X_J}(i).
\]
For each \(\beta<\delta\), define an arity-\(k\) diagram
\(\mathcal D_{t,\beta}=(\mathcal E_t,R_t,\rho_{t,\beta})\) by
\begin{align}
\ell\mathcal E_t\ell'
&\quad\Longleftrightarrow\quad
q_t(\ell)=q_t(\ell'), \label{end:diagram-equality}\\
\ell R_t\ell'
&\quad\Longleftrightarrow\quad
q_t(\ell)\in q_t(\ell'), \label{end:diagram-membership}\\
\rho_{t,\beta}(\ell)
&=f_{\rank(q_t(\ell))}(\beta).
\label{end:diagram-tags}
\end{align}
All entries of \(q_t\) lie in \(D_X\), by the inclusion
property of the closures. Since the labels \(([k],i)\)
enumerate all of \(D_X\), the map \(q_t\) is onto \(D_X\).
\begin{lemma}\label{end:diagrams}
For every tuple \(t\) as above, the equality quotient of
\(\mathcal D_{t,\beta}\) identifies with \(D_X\), with its
actual membership relation, for every \(\beta<\delta\).
The diagrams satisfy the following additional properties.
\begin{enumerate}[label=\textup{(\roman*)}]
\item If \(\varnothing\ne J\subseteq[k]\), restriction of
\(\mathcal D_{t,\beta}\) to the labels belonging to
\(J\), with the increasing reindexing of positions,
is exactly \(\mathcal D_{t\restriction J,\beta}\).
\item If \(\beta\notin F_X\), then every diagram
\(\mathcal D_{t\restriction J,\beta}\), including the full
diagram, is valid.
\end{enumerate}
Consequently, for every \(\beta\notin F_X\), the colors
\[
s_{t\restriction J,\beta}
=\iota_{|J|}(\mathcal D_{t\restriction J,\beta}),
\qquad \varnothing\ne J\subseteq[k],
\]
pass the full subsequence test of
Definition~\ref{col:test}.
\end{lemma}
\begin{proof}
Surjectivity of \(q_t\), together with
\eqref{end:diagram-equality}, identifies the quotient
bijectively with \(D_X\).
Equation~\eqref{end:diagram-membership} identifies its
relation with membership on \(D_X\), which is
extensional. The tags in \eqref{end:diagram-tags}
depend only on the image under \(q_t\), so both the
relation and the tags respect the equality relation.
For \textup{(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
\[
d_{\{x_{j_a}:a\in A\}}(i).
\]
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 \textup{(ii)}, suppose
\(\beta\notin F_X\). Every membership edge \(y\in x\)
with \(x,y\in D_X\) then satisfies
\[
f_{\rank(y)}(\beta)<f_{\rank(x)}(\beta)
\]
by \eqref{end:bad-set}. 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
\eqref{end:bad-monotone}. The same argument proves
the validity of this subtuple diagram. Combined
with \textup{(i)}, these are exactly the conditions
of the full subsequence test.
\end{proof}
For all \(t\) and all \(\beta<\delta\), define
\begin{equation}\label{end:prescribed-colors}
s_{t,\beta}=\iota_k(\mathcal D_{t,\beta}),
\qquad k=|t|.
\end{equation}
The coding maps are defined on arbitrary diagrams, so
this prescription also makes sense at the exceptional
coordinates in \(F_X\).
\subsection{Realizing the colors in an object}
Let \(B=\delta\times\Q\) with its lexicographic order.
This is a dense linear order without endpoints:
within any rational block there are points above and
below each given point; if two points belong to
different blocks, a larger point in the earlier block
lies strictly between them. The interval between
points in blocks \(\alpha\leq\alpha'<\omega_1\) is
contained in
\[
\bigl([\alpha,\alpha']\cap\omega_1\bigr)\times\Q,
\]
which is countable. Thus \(B\) meets the order
requirements for a basic structure and has
cardinality \(\delta\). Fix a bijection
\(\beta\mapsto b_\beta\) from \(\delta\) to \(B\);
this indexing is independent of the order.
Take \(I=D\). For every nonempty finite ordered tuple \(t\) of
distinct elements of \(I\), and every \(\beta<\delta\), choose a binary
sequence \(a_{t,b_\beta}\in2^\omega\) representing \(s_{t,\beta}\).
The tuples and coordinates form a set, so these simultaneous choices
are available in ZFC.
The order \(B\) has the properties required by Lemma~\ref{aec:arrays}.
Apply that lemma to this family of sequences, using disjoint tagged
copies of \(I\), \(B\), and the other carriers as in its construction.
It gives a basic structure \(M_{\mathrm u}\) and a row-choice system
\(\mathbf z\) such that
\[
c_t^{\mathbf z}(b_\beta)
=[a_{t,b_\beta}]_{=^*}
=s_{t,\beta}.
\]
If \(X\) is the underlying set of \(t\), Lemma~\ref{end:diagrams}
therefore makes its full subsequence test pass whenever
\(\beta\notin F_X\). In the notation of~\eqref{aec:bad-set},
\[
E_t(\mathbf z)\subseteq\{b_\beta:\beta\in F_X\}.
\]
The right-hand side is countable. This verifies the object condition
for every tuple, so \(M_{\mathrm u}\in K\). The chosen representatives
verify that condition; they are not named in the structure.
\begin{theorem}\label{end:two-models}
The class \(K\) has two nonisomorphic models of
cardinality \(\beth_\eta\). One has an order sort
of cardinality \(\aleph_1\), and the other has a
countable order sort.
\end{theorem}
\begin{proof}
The construction above and Lemma~\ref{end:hierarchy-size} give
\(M_{\mathrm u}\in K\) with
\[
|I^{M_{\mathrm u}}|=|V_\eta|=\beth_\eta,
\qquad
|B^{M_{\mathrm u}}|=\aleph_1.
\]
Lemma~\ref{aec:size} 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~\ref{aec:arrays} supplies a basic structure and makes the object
condition automatic because \(B\) is countable. Hence
\(M_{\mathrm c}\in K\), and Lemma~\ref{aec:size} 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.
\end{proof}
==== END A-CH-Obstruction-to-a-Prescribed-Categoricity-Threshold//04-endpoint.tex ====
==== BEGIN A-CH-Obstruction-to-a-Prescribed-Categoricity-Threshold//05-conclusion.tex ====
\section{The endpoint failure and its logical scope}\label{sec:conclusion}
\begin{proof}[Proof of Theorem~\ref{thm:main}]
Work in ZFC with CH. Theorem~\ref{aec:class} gives an AEC \(K\) with
\(\LS(K)=\aleph_0\). Hence
\[
H(K)=\beth_{(2^{\aleph_0})^+}=\beth_{\omega_2}
=\beth_\eta.
\]
Theorem~\ref{end:two-models} supplies two nonisomorphic models of this
cardinality. Theorem~\ref{cat:tail} 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,
\[
\Lambda=\beth_{\xi^+}>\beth_\eta=H(K).
\]
Thus \(\lambda=\Lambda^+\) satisfies the premise of the proposed
transfer and its conclusion fails at \(\mu=H(K)\), as claimed.
\end{proof}
\subsection{The set-theoretic formulation}
For a literal first-order consistency statement, let \(\Theta\) assert
that there is a set
\(p=(\iota_k:k\ge1)\) of coding maps as in Lemma~\ref{col:coding}
for which the particular formulas of Definition~\ref{aec:objects}
define an AEC \(K_p\) with \(\LS(K_p)=\aleph_0\), two
nonisomorphic models of cardinality \(h(\aleph_0)\), and
categoricity in \(\Lambda^+>h(\aleph_0)\), where
\(\Lambda=\beth_{(2^{\aleph_1})^+}\).
Here the fixed definitions and the AEC and categoricity conditions
are expanded into one sentence of set theory; all quantified
parameters, structures, maps, and sequences are sets.
For the statements involving \(\Phi\), fix a first-order formulation
of the universal assertion~\eqref{eq:target} such that ZFC proves
its implication to the following fixed-family instance: for every
valid \(p\), if \(K_p\) is an AEC with \(\LS(K_p)=\aleph_0\),
\(\Lambda^+>h(\aleph_0)\), and categoricity in \(\Lambda^+\),
then \(K_p\) is categorical in \(h(\aleph_0)\).
The conclusions about \(\Phi\) below are read separately for each
such formulation. In particular, ZFC proves
\(\Theta\Rightarrow\neg\Phi\).
\begin{corollary}\label{cor:consistency}
ZFC proves \(\mathrm{CH}\Rightarrow\Theta\).
For each fixed \(\Phi\) as above, it also proves
\(\mathrm{CH}\Rightarrow\neg\Phi\), and
\[
\Con(\mathrm{ZFC})
\quad\Longrightarrow\quad
\Con(\mathrm{ZFC}+\Theta)
\quad\Longrightarrow\quad
\Con(\mathrm{ZFC}+\neg\Phi).
\]
If ZFC is consistent, no such \(\Phi\) is a theorem of ZFC.
\end{corollary}
\begin{proof}[Proof of Corollary~\ref{cor:consistency}]
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~\ref{thm:main} 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\"odel's relative-consistency theorem
\cite{Godel1938} 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.
\end{proof}
The corollary gives one-sided nonprovability, not independence in both
directions: neither an unconditional ZFC proof of \(\neg\Phi\) nor
consistency of \(\Phi\) is asserted. The constructed class is categorical
on a higher tail, so the obstruction concerns the prescribed endpoint
and is compatible with qualitative eventual categoricity. No qualitative
eventual-categoricity theorem is used in the argument.
\subsection{Why structural transfer theorems do not apply}
For clarity, the construction fails both joint embedding and
amalgamation, although neither failure was needed as an input to the
proof. Joint embedding means that any two models admit strong
embeddings into a common model. Amalgamation requires such embeddings
over a given common strong submodel, agreeing on that submodel.
\begin{proposition}\label{prop:no-amalgamation}
The class \(K\) has neither joint embedding nor amalgamation.
The failure of amalgamation can be witnessed over a countable model.
\end{proposition}
\begin{proof}
Let \(M\) be the model with uncountable base from
Theorem~\ref{end:two-models}. By Theorem~\ref{aec:class}, 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~\ref{cat:bounded}.
There is therefore no joint embedding of \(M,N\), and in particular
no amalgam of the two extensions \(A\le_K M,N\).
\end{proof}
Proposition~\ref{prop:no-amalgamation} explains why results imposing
amalgamation, such as \cite[Corollary~9.10]{Vasey2017Downward}, do not
contradict Theorem~\ref{thm:main}. Likewise, the existence Hanf theorem
does not imply that the particular model \(M\) has arbitrarily large
extensions. The full class has arbitrarily large models with countable
base; its uncountable-base part has the separate bound proved in
Proposition~\ref{cat:bounded}. That part cannot itself have
L\"owenheim--Skolem number \(\aleph_0\), because it has no countable
models.
==== END A-CH-Obstruction-to-a-Prescribed-Categoricity-Threshold//05-conclusion.tex ====
==== BEGIN A-CH-Obstruction-to-a-Prescribed-Categoricity-Threshold//06-booleanization.tex ====
\section{An obstruction to Booleanizing the canonical point}
\label{sec:booleanization}
The distinction between an extension somewhere in the class and an
extension inside a fixed model also affects the topos argument in
\cite[Theorem~4.1]{Espindola2023Spectra}. We give a concrete obstruction
on the site of countable models: adding a base point is always possible
there, but need not be possible inside a given countable-base model.
The resulting dense cosieve prevents that model's canonical presheaf
point from factoring through the full double-negation subtopos.
Throughout this section we retain CH and the class constructed above.
\subsection{Adding base points to a countable model}
\begin{lemma}\label{bool:extension}
Every countable \(M\in K\) has a countable strong extension \(M'\)
with \(I^{M'}=I^M\) and \(B^M\subsetneq B^{M'}\).
\end{lemma}
\begin{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
\[
q_t(J,n)=d_{\{x_r:r\in J\}}(n).
\]
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~\ref{col:no-pattern}.
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
\[
a_{t,b}(n)=
\begin{cases}
e^M(z_{t,n},w_{t,b}),&b\in B^M,\\
a_t(n),&b\in B'\setminus B^M.
\end{cases}
\]
Extend them to all points by the torsor formula
\[
e'(z_{t,n}+u,w_{t,b}+v)
=a_{t,b}(n)+\boldsymbol1_{b\in\supp(u)}
+\boldsymbol1_{n\in v}\pmod2.
\]
Unique torsor coordinates make this well-defined. The old translation
law~\eqref{aec:bit} 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~\ref{aec:size} makes the extension countable.
\end{proof}
\subsection{The site and the canonical point}
Let \(\mathcal C_0\) be a small skeleton of the category of countable
models in \(K\) and strong embeddings. We use covariant presheaves
\(\mathcal P=\mathrm{Set}^{\mathcal C_0}\), that is, presheaves on
\(\mathcal C_0^{\mathrm{op}}\), and write
\(y_A=\operatorname{Hom}_{\mathcal C_0}(A,-)\). A cosieve on \(A\)
is a collection of maps out of \(A\) closed under postcomposition,
or equivalently a subfunctor of \(y_A\). The double-negation topology
\(J_{\neg\neg}\) on \(\mathcal C_0^{\mathrm{op}}\) declares a
cosieve \(R\) covering exactly when
\begin{equation}\label{bool:density}
\text{for every } f:A\to D\text{ there is }g:D\to E
\text{ with }gf\in R.
\end{equation}
Thus \(\operatorname{Sh}(\mathcal C_0^{\mathrm{op}},J_{\neg\neg})\)
is the full double-negation Booleanization of \(\mathcal P\).
For a regular infinite cardinal \(\theta\), a poset is
\(\theta\)-directed if every subset of cardinality less than
\(\theta\) has an upper bound. A model \(M\) is
\(\theta\)-presentable if \(\operatorname{Hom}_K(M,-)\) preserves
\(\theta\)-directed colimits; its presentability rank is the least
regular infinite \(\theta\) with this property.
Our site is also the countable \emph{internal-size} site in the convention
of \cite[Definition~2.3 and the notation at the end of
Section~2]{Espindola2022Eventual}. Indeed, for every regular
\(\theta>\aleph_0\), a model of cardinality less than \(\theta\)
is \(\theta\)-presentable: its image in a \(\theta\)-directed
colimit lies in one stage, coherence makes the factorization strong,
and embeddings give uniqueness. Conversely, every model is the union
of its strong submodels of cardinality less than \(\theta\), a
\(\theta\)-directed family by the downward
L\"owenheim--Skolem property and regularity of \(\theta\).
If the model has cardinality at least \(\theta\), its identity
cannot factor through any member of this family. An uncountable model
of cardinality \(\nu\) therefore has presentability rank \(\nu^+\).
A countable model has rank either \(\aleph_0\) or \(\aleph_1\).
The cited convention assigns internal size \(\nu\) to rank
\(\nu^+\), and assigns a limit rank to itself. Thus internal and
underlying cardinalities agree here, including at \(\aleph_0\).
For any \(H\in K\), let \(\mathcal C_0/H\) have as objects the
strong maps \(c:C\to H\) with \(C\in\mathcal C_0\), and as arrows
the commuting triangles. It is \(\aleph_1\)-filtered: countably many
images are contained in a countable strong submodel of \(H\), and
coherence gives the required transition maps. Parallel arrows over
\(H\) are equal because the maps into \(H\) are injective.
The canonical point \(p_H:\mathrm{Set}\to\mathcal P\) has inverse
image
\begin{equation}\label{bool:point}
p_H^*(X)=\mathop{\mathrm{colim}}_{(C,c)\in\mathcal C_0/H}X(C),
\qquad p_H^*(y_A)=\operatorname{Hom}_K(A,H).
\end{equation}
The first formula preserves colimits and finite limits, giving a
point; in fact it preserves countable limits since the indexing
category is \(\aleph_1\)-filtered. In the second formula, a
representative \(r:A\to C\) maps to \(cr\). Every map into \(H\)
occurs this way, and two representatives with the same composite
agree after passing to a common countable strong submodel of \(H\).
No identification of all points of \(\mathcal P\) with models of
\(K\) is needed.
\begin{proposition}\label{bool:obstruction}
If \(H\in K\) has countable base, its canonical point \(p_H\)
does not factor through
\(\operatorname{Sh}(\mathcal C_0^{\mathrm{op}},J_{\neg\neg})\).
This applies, in particular, to every model on the categoricity tail
\(\|H\|\ge\Lambda\).
\end{proposition}
\begin{proof}
Choose a countable strong map \(a:A\to H\) whose image contains
\(B^H\), using the downward L\"owenheim--Skolem property and then
the representative in \(\mathcal C_0\). Define
\[
R_A=\{r:A\to D\text{ in }\mathcal C_0:
r[B^A]\subsetneq B^D\}\subseteq y_A.
\]
Injectivity makes this a cosieve. For any \(f:A\to D\),
Lemma~\ref{bool:extension}, 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
\eqref{bool:density}, 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~\ref{aec:order-size} and~\ref{aec:size} together with
Proposition~\ref{cat:bounded}, and exist by Theorem~\ref{cat:tail}.
\end{proof}
\subsection{The precise comparison}
The proof of \cite[Theorem~4.1]{Espindola2023Spectra}, in the cited
version, starts with the full double-negation subtopos on the
internal-size site and asserts that the large categorical model gives
a point of it. Proposition~\ref{bool:obstruction} rules out the
canonical factorization for the present class, even though its point
preserves countable limits. A topology generated by a smaller chosen
family of covers could omit \(R_A\); in that case it would not be
the full double-negation topology used in that step.
This is an explicit obstruction to that step, not a classification of
all points of the Booleanization or a proof that it has no points.
It does not analyze alternative constructions of points or establish
what additional hypotheses would suffice to repair the cited argument.
==== END A-CH-Obstruction-to-a-Prescribed-Categoricity-Threshold//06-booleanization.tex ====
==== BEGIN A-CH-Obstruction-to-a-Prescribed-Categoricity-Threshold//matrix-decomposition.tex ====
\begin{figure}[tbp]
\centering
\begin{tikzpicture}[x=.52cm,y=.52cm,>=Latex,font=\small]
\definecolor{rowshade}{RGB}{182,218,223}
\definecolor{columnshade}{RGB}{249,221,167}
\foreach \n in {0,...,6}{
\foreach \k in {0,...,6}{
\ifnum\k>\n
\fill[columnshade] (\k,-\n) rectangle ++(1,-1);
\else
\fill[rowshade] (\k,-\n) rectangle ++(1,-1);
\fi
}
}
\draw[step=1,gray!60,thin] (0,0) grid (7,-7);
\draw[->] (0,.9) -- (7.6,.9) node[right] {column \(k\)};
\draw[->] (-1,0) -- (-1,-7.6) node[below] {row \(n\)};
\foreach \k in {0,...,6}
\node at (\k+.5,.35) {\(\k\)};
\foreach \n in {0,...,6}
\node at (-.4,-\n-.5) {\(\n\)};
\draw[very thick,linkblue] (0,-4) rectangle (5,-5);
\draw[very thick,orange!70!black] (5,0) rectangle (6,-5);
\node[anchor=west,align=left] at (8,-1.2)
{\(k\le n\): adjust in row \(n\)\\
at most \(n+1\) positions};
\node[anchor=west,align=left] at (8,-3.2)
{\(n<k\): adjust in column \(k\)\\
at most \(k\) positions};
\node[anchor=west,align=left] at (8,-5.7)
{Highlighted examples:\\
row \(n=4\), column \(k=5\)};
\node at (7.5,-6.5) {\(\cdots\)};
\node at (6.5,-7.5) {\(\vdots\)};
\end{tikzpicture}
\caption{A finite portion of the countably infinite difference matrix.
The two regions partition its entries. Each row uses only the finitely
many positions \(k\le n\), and each column only the finitely many
positions \(n<k\); within these positions one shifts exactly where the
difference bit is one. Thus finite row and column translations remove
every difference matrix. The column enumeration need not respect the
dense order.}
\label{fig:matrix-decomposition}
\end{figure}
==== END A-CH-Obstruction-to-a-Prescribed-Categoricity-Threshold//matrix-decomposition.tex ====
==== BEGIN A-CH-Obstruction-to-a-Prescribed-Categoricity-Threshold//paper.tex ====
\documentclass[11pt]{article}
\input{preamble}
\title{A CH obstruction to a prescribed categoricity threshold}
\author{OpenAI}
\date{September 24, 2026}
\begin{document}
\maketitle
\input{sections/00-introduction}
\clearpage
\tableofcontents
\input{sections/01-colors}
\input{sections/02-aec}
\input{sections/04-endpoint}
\input{sections/03-categoricity}
\input{sections/05-conclusion}
\input{sections/06-booleanization}
\clearpage
\bibliographystyle{plain}
\bibliography{references}
\end{document}
==== END A-CH-Obstruction-to-a-Prescribed-Categoricity-Threshold//paper.tex ====
==== BEGIN A-CH-Obstruction-to-a-Prescribed-Categoricity-Threshold//preamble.tex ====
\usepackage[T1]{fontenc}
\usepackage[utf8]{inputenc}
\usepackage{lmodern}
\usepackage[margin=1in]{geometry}
\usepackage{amsmath,amssymb,amsthm,mathtools}
\usepackage{needspace}
\usepackage{enumitem,booktabs,array}
\usepackage{microtype}
\usepackage{tikz}
\usetikzlibrary{arrows.meta,positioning,calc,decorations.pathreplacing}
\usepackage{xcolor}
\definecolor{linkblue}{RGB}{25,65,105}
\usepackage[colorlinks=true,linkcolor=linkblue,citecolor=linkblue,urlcolor=linkblue,breaklinks=true]{hyperref}
\hypersetup{pdftitle={A CH obstruction to a prescribed categoricity threshold},pdfauthor={OpenAI}}
\usepackage[capitalise,noabbrev,nameinlink]{cleveref}
\numberwithin{equation}{section}
\newtheorem{theorem}{Theorem}[section]
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{corollary}[theorem]{Corollary}
\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}
\theoremstyle{remark}
\newtheorem{remark}[theorem]{Remark}
\AddToHook{cmd/subsection/before}{\Needspace{9\baselineskip}}
\AddToHook{env/theorem/before}{\Needspace{2\baselineskip}}
\AddToHook{env/lemma/before}{\Needspace{2\baselineskip}}
\AddToHook{env/proposition/before}{\Needspace{2\baselineskip}}
\AddToHook{env/corollary/before}{\Needspace{2\baselineskip}}
\AddToHook{env/definition/before}{\Needspace{2\baselineskip}}
\AddToHook{env/remark/before}{\Needspace{2\baselineskip}}
\DeclareMathOperator{\LS}{LS}
\DeclareMathOperator{\cf}{cf}
\DeclareMathOperator{\rank}{rank}
\DeclareMathOperator{\supp}{supp}
\DeclareMathOperator{\Con}{Con}
\newcommand{\Q}{\mathbb Q}
\newcommand{\N}{\mathbb N}
\newcommand{\SymDiff}{\triangle}
\setlist{itemsep=2pt,topsep=5pt}
\setcounter{tocdepth}{2}
\emergencystretch=1.5em
\allowdisplaybreaks[2]
==== END A-CH-Obstruction-to-a-Prescribed-Categoricity-Threshold//preamble.tex ====
==== BEGIN A-CH-Obstruction-to-a-Prescribed-Categoricity-Threshold//references.bib ====
@article{Godel1938,
author = {G{\"o}del, Kurt},
title = {The Consistency of the Axiom of Choice and of the Generalized
Continuum-Hypothesis},
journal = {Proceedings of the National Academy of Sciences of the
United States of America},
volume = {24},
number = {12},
pages = {556--557},
year = {1938},
doi = {10.1073/pnas.24.12.556},
note = {\url{https://doi.org/10.1073/pnas.24.12.556}}
}
@article{Shelah1999CategoricityAP,
author = {Shelah, Saharon},
title = {Categoricity for abstract classes with amalgamation},
journal = {Annals of Pure and Applied Logic},
volume = {98},
number = {1--3},
pages = {261--294},
year = {1999},
doi = {10.1016/S0168-0072(98)00016-5},
eprint = {math/9809197},
archivePrefix = {arXiv},
primaryClass = {math.LO},
note = {\url{https://doi.org/10.1016/S0168-0072(98)00016-5}}
}
@article{Vasey2017Downward,
author = {Vasey, Sebastien},
title = {Downward categoricity from a successor inside a good frame},
journal = {Annals of Pure and Applied Logic},
volume = {168},
number = {3},
pages = {651--692},
year = {2017},
doi = {10.1016/j.apal.2016.10.003},
eprint = {1510.03780},
archivePrefix = {arXiv},
primaryClass = {math.LO},
note = {\url{https://doi.org/10.1016/j.apal.2016.10.003}}
}
@article{SarochTrlifaj2024,
author = {{\v{S}}aroch, Jan and Trlifaj, Jan},
title = {Deconstructible abstract elementary classes of modules
and categoricity},
journal = {Bulletin of the London Mathematical Society},
volume = {56},
number = {12},
pages = {3854--3866},
year = {2024},
doi = {10.1112/blms.13172},
eprint = {2312.02623},
archivePrefix = {arXiv},
primaryClass = {math.RT},
note = {\url{https://doi.org/10.1112/blms.13172}}
}
@incollection{BoneyVasey2017Survey,
author = {Boney, Will and Vasey, Sebastien},
title = {A survey on tame abstract elementary classes},
booktitle = {Beyond First Order Model Theory},
editor = {Iovino, Jos{\'e}},
publisher = {CRC Press},
pages = {353--427},
year = {2017},
eprint = {1512.00060},
archivePrefix = {arXiv},
primaryClass = {math.LO},
note = {Preprint: \url{https://arxiv.org/abs/1512.00060v4}}
}
@article{HartShelah1990,
author = {Hart, Bradd T. and Shelah, Saharon},
title = {Categoricity over {$P$} for first order {$T$} or categoricity for {$\phi\in L_{\omega_1\omega}$} can stop at {$\aleph_k$} while holding for {$\aleph_0,\ldots,\aleph_{k-1}$}},
journal = {Israel Journal of Mathematics},
volume = {70},
number = {2},
year = {1990},
pages = {219--235},
doi = {10.1007/BF02807869},
eprint = {math/9201240},
archivePrefix = {arXiv},
note = {\url{https://doi.org/10.1007/BF02807869}}
}
@article{BoneyVasey2018HartShelah,
author = {Boney, Will and Vasey, Sebastien},
title = {Good frames in the {Hart--Shelah} example},
journal = {Archive for Mathematical Logic},
volume = {57},
year = {2018},
pages = {687--712},
doi = {10.1007/s00153-017-0599-7},
eprint = {1607.03885},
archivePrefix = {arXiv},
note = {\url{https://doi.org/10.1007/s00153-017-0599-7}}
}
@article{KolesnikovLambieHanson2016,
author = {Kolesnikov, Alexei and Lambie-Hanson, Chris},
title = {The {Hanf} number for amalgamation of coloring classes},
journal = {The Journal of Symbolic Logic},
volume = {81},
number = {2},
year = {2016},
pages = {570--583},
doi = {10.1017/jsl.2015.48},
eprint = {1409.2508},
archivePrefix = {arXiv},
note = {\url{https://doi.org/10.1017/jsl.2015.48}}
}
@misc{Grossberg2021Draft,
author = {Grossberg, Rami},
title = {A Course in Model Theory {I}: Introduction},
year = {2021},
note = {Author draft dated October 30, 2021. \url{https://www.math.cmu.edu/~rami/MOAB1.pdf}}
}
@article{ErdosRado1956,
author = {Erd{\H o}s, Paul and Rado, Richard},
title = {A partition calculus in set theory},
journal = {Bulletin of the American Mathematical Society},
volume = {62},
year = {1956},
pages = {427--489},
doi = {10.1090/S0002-9904-1956-10036-0},
note = {\url{https://doi.org/10.1090/S0002-9904-1956-10036-0}}
}
@article{Mostowski1949,
author = {Mostowski, Andrzej},
title = {An undecidable arithmetical statement},
journal = {Fundamenta Mathematicae},
volume = {36},
year = {1949},
pages = {143--164},
doi = {10.4064/fm-36-1-143-164},
note = {\url{https://doi.org/10.4064/fm-36-1-143-164}}
}
@article{Morley1965,
author = {Morley, Michael},
title = {Categoricity in power},
journal = {Transactions of the American Mathematical Society},
volume = {114},
number = {2},
pages = {514--538},
year = {1965},
doi = {10.1090/S0002-9947-1965-0175782-0},
note = {\url{https://doi.org/10.1090/S0002-9947-1965-0175782-0}}
}
@misc{Espindola2022Eventual,
author = {Esp{\'i}ndola, Christian},
title = {A proof of {Shelah}'s eventual categoricity conjecture and an
extension to accessible categories with directed colimits},
year = {2022},
eprint = {1906.09169},
archivePrefix = {arXiv},
primaryClass = {math.LO},
note = {Version 7, April 13, 2022.
\url{https://arxiv.org/abs/1906.09169v7}}
}
@misc{Espindola2023Spectra,
author = {Esp{\'i}ndola, Christian},
title = {A complete classification of categoricity spectra of accessible
categories with directed colimits},
year = {2023},
eprint = {2301.13167},
archivePrefix = {arXiv},
primaryClass = {math.LO},
note = {Version 1. \url{https://arxiv.org/abs/2301.13167v1}}
}
==== END A-CH-Obstruction-to-a-Prescribed-Categoricity-Threshold//references.bib ====