\documentclass[oneside]{amsart} \usepackage[letterpaper]{geometry} %\geometry{ % textwidth=6in, % Adjust the text width % textheight=9in, % Adjust the text height (optional) % marginparwidth=1in, % Adjust the margin for sidenotes (optional) %} \geometry{letterpaper, portrait, margin=1.2in} \usepackage{amsmath,amsfonts,amssymb}% \usepackage[all]{xy} \usepackage[usenames]{color} \usepackage{setspace} \usepackage{comment} \usepackage{centernot} \usepackage{microtype} \usepackage{bm} \usepackage{inconsolata} \usepackage{lucide-icons} %%% MATH \usepackage{amsmath,amsthm,amsfonts,amssymb, stmaryrd}% \usepackage{mathrsfs} \usepackage{graphicx} %%% BIBLIOGRAPHY %\usepackage[numbers]{natbib} %% numbers is required. %%% LINKS %\usepackage[colorlinks,cite] \usepackage{enumerate} %LaTeX 3 \usepackage{xparse, expl3} % for \sout{} strikeout \usepackage[normalem]{ulem} \usepackage{url} % %%%%%%%%% REFERENCES %%%%%%%% % \definecolor{DarkBlue}{rgb}{0,0,.7} \usepackage{hyperref} \hypersetup{ colorlinks = true, citecolor=DarkBlue, urlcolor=DarkBlue, linkcolor=DarkBlue } %%\usepackage{hypernat} % \usepackage{aliascnt} \usepackage[capitalize]{cleveref} \crefname{lemma}{Lemma}{Lemmas} \crefname{corollary}{Corollary}{Corollaries} \crefname{claim}{Claim}{Claims} \crefname{theorem}{Theorem}{Theorems} \crefname{equation}{Equation}{Equations} \crefname{example}{Example}{Examples} \crefname{convention}{Convention}{Conventions} \crefname{section}{Section}{Sections} \crefname{subsection}{Section}{Sections} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%% BIBLIOGRAPHY %%%%%%%% %\usepackage[numbers]{natbib} %% numbers is required. %\usepackage[% % minnames=1,maxnames=99,maxcitenames=4, %% style=alphabetic, %% doi=false,url=false, % firstinits=true,hyperref,natbib,backend=bibtex]{biblatex} %\bibliography{bibliography} %%\addbibresource{bibliography.bib} %\renewcommand\bibname{References} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %\definecolor{LightGray}{rgb}{.6,.6,.6} %\usepackage{vruler} \setvruler[10pt][1][1][4][1][10pt][10pt][0pt][1.025\textheight] %\setstretch{1.0} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % Share numbering while preserving each environment's cleveref type. \newtheorem{theorem}{Theorem}[section] % Main counter tied to sections \newaliascnt{lemma}{theorem} \newtheorem{lemma}[lemma]{Lemma} \aliascntresetthe{lemma} \newaliascnt{proposition}{theorem} \newtheorem{proposition}[proposition]{Proposition} \aliascntresetthe{proposition} \newaliascnt{corollary}{theorem} \newtheorem{corollary}[corollary]{Corollary} \aliascntresetthe{corollary} \newaliascnt{claim}{theorem} \newtheorem{claim}[claim]{Claim} \aliascntresetthe{claim} \newaliascnt{conjecture}{theorem} \newtheorem{conjecture}[conjecture]{Conjecture} \aliascntresetthe{conjecture} \newaliascnt{question}{theorem} \newtheorem{question}[question]{Question} \aliascntresetthe{question} % 2. DEFINITION STYLE (Bold header, Upright body) % Recommended for concepts, problems, and examples \theoremstyle{definition} \newaliascnt{definition}{theorem} \newtheorem{definition}[definition]{Definition} \aliascntresetthe{definition} \newaliascnt{example}{theorem} \newtheorem{example}[example]{Example} \aliascntresetthe{example} \newaliascnt{convention}{theorem} \newtheorem{convention}[convention]{Convention} \aliascntresetthe{convention} % 3. REMARK STYLE (Italic header, Upright body) % Recommended for notes, remarks, and annotations \theoremstyle{remark} \newaliascnt{remark}{theorem} \newtheorem{remark}[remark]{Remark} \aliascntresetthe{remark} \newaliascnt{note}{theorem} \newtheorem{note}[note]{Note} \aliascntresetthe{note} \newaliascnt{notation}{theorem} \newtheorem{notation}[notation]{Notation} \aliascntresetthe{notation} \newaliascnt{summary}{theorem} \newtheorem{summary}[summary]{Summary} \aliascntresetthe{summary} \newtheorem*{acknowledgement}{Acknowledgement} % 4. UNNUMBERED VARIANTS \newtheorem*{theorem*}{Theorem} \newtheorem*{lemma*}{Lemma} \newtheorem*{proposition*}{Proposition} \newtheorem*{corollary*}{Corollary} \newtheorem*{definition*}{Definition} \newtheorem*{remark*}{Remark} \include{macros} \begin{document} \title{A counterexample to Vaught's Conjecture for $\Lwow$} \date{} \begin{abstract} We construct a sentence of $\Lwow$ having exactly $\aleph_1$ many countable models up to isomorphism, but no perfect set of non-isomorphic models. This disproves Vaught's conjecture for infinitary logic. The construction follows a framework devised by Robin Knight, and the proof has been formally verified in Lean. \end{abstract} \author{Nathanael L.\ Ackerman} \address{Harvard University, Cambridge, MA, %02138, USA} \email{nate@aleph0.net} \author{Cameron E.\ Freer} \address{Massachusetts Institute of Technology, Cambridge, MA, %02139, USA} \email{freer@mit.edu} \author{Robin W.\ Knight} \address{University of Oxford, Oxford, UK} \email{knight@maths.ox.ac.uk} \subjclass[2020]% {Primary: 03C15; % Model theory of denumerable and separable structures Secondary: 03C75, % Other infinitary logic 03E15% Descriptive set theory } \keywords{Vaught's conjecture, Knight systems, number of models, infinitary logic} \maketitle \tableofcontents %%%% %%%% %%%% %%%% %%%% %%%% %%%% %%%% \section{Introduction} %%%% %%%% %%%% %%%% %%%% %%%% %%%% %%%% The beginning of modern model theory can be traced back to a paper of Vaught titled ``Denumerable models of complete theories'' \cite{MR186552}. That paper introduced many of the fundamental concepts and ideas used in model theory, and it ended with the following question which gave rise to the conjecture that bears his name: \begin{question}[{\cite[p.~320]{MR186552}}] Can it be proved, without the use of the continuum hypothesis, that there exists a complete theory having exactly $\aleph_1$ non-isomorphic denumerable models? \end{question} The statement that all countable first-order theories either have countably many or continuum many countable models (up to isomorphism) has since been known as ``Vaught's conjecture''. The most significant advance in the study of Vaught's conjecture of the next several decades was Morley's paper ``The number of countable models'' \cite{MR288015}. In this paper Morley made two important advances. First, he showed that if Vaught's conjecture were to fail, then any counterexample must be a scattered theory with precisely $\aleph_1$ many models. Second, he showed that these results were true not just of first-order logic but also of sentences of the infinitary logic $\Lwow$. In light of the first advance, Vaught's conjecture is usually taken today to mean the ``absolute'' version, namely the statement that every countable first-order theory with an uncountable collection of models (up to isomorphism) has a (non-empty) perfect set of non-isomorphic models. In particular, this formulation, unlike the original, is absolute between models of set theory and does not depend on whether the continuum hypothesis holds. Morley's results for $\Lwow$ not only suggested a natural generalization of Vaught's conjecture for sentences of $\Lwow$, but also opened the door for a much wider generalization. Several years earlier, Lopez-Escobar \cite{MR188059} showed that there is a close connection between the countable model theory of $\Lwow$ and the descriptive set theory of continuous actions of $\Sym{\infty}$ on Polish spaces. This implies that Vaught's conjecture for $\Lwow$ can be seen as the $\Sym{\infty}$ case of what is known as the topological Vaught conjecture. \begin{conjecture}[Topological Vaught Conjecture] If a Polish group $G$ acts continuously on a Polish space $X$, then either there are countably many orbits, or there is a (non-empty) perfect subset of $X$ whose distinct points lie in distinct orbits. \end{conjecture} In this way, the topological Vaught conjecture for the Polish group $\Sym{\infty}$ can be seen as one of the oldest problems in both model theory and descriptive set theory. %%%% %%%% %%%% %%%% %%%% %%%% \subsection{Previous Results and Approaches} %%%% %%%% %%%% %%%% %%%% %%%% Over the years, Vaught's conjecture has been attacked from many different directions, but two are especially worth mentioning. The first approach encompasses a wide body of research showing that in many well-behaved situations Vaught's conjecture does indeed hold. These can, roughly, be grouped into four classes. First, there are those specific types of structures on which Vaught's conjecture has been shown to hold. These include any theory of Boolean algebras \cite{MR1142919}, modules over a serial ring \cite{MR1782111}, varieties \cite{MR1191612}, trees \cite{MR0526920}, and theories with a definable discrete linear order \cite{MR4836650}. Second, there are abstract properties of the theories which imply Vaught's conjecture. These include $\w$-stable theories \cite{MR788270}, superstable theories of finite rank \cite{MR2467429}, o-minimal theories \cite{MR929381}, almost chainable theories \cite{MR4347566} and sentences of $\Lwow$ in which the equality symbol is not used \cite{MR3403092}. Third is work showing that certain higher computability bounds on the complexity of models imply Vaught's conjecture. One of the most important papers in this vein is \cite{MR723338}. There Sacks showed that if either no model of a given theory has its maximum allowed Scott rank, or if no Scott rank has multiple models of the theory, then Vaught's conjecture holds of that theory. More recently, in \cite{MR3010050} it was shown (assuming ZFC + Projective Determinacy) that a theory with uncountably many countable models up to isomorphism is a counterexample if and only if it satisfies ``hyperarithmetic-is-recursive on a cone''. The fourth class of examples where Vaught's conjecture is known to hold deals with the study of Polish groups and the topological Vaught conjecture. In \cite{MR1467467} it was shown that the topological Vaught conjecture held for all continuous actions of nilpotent Polish groups on Polish spaces. In \cite{MR1022169} it was shown, among other things, that Vaught's conjecture holds for all abelian Polish groups. The second approach to attacking Vaught's conjecture consisted in studying consequences of the existence of a counterexample. For example, in \cite{MR3156527} it was shown that if Vaught's conjecture fails, then there must be a sentence of $\Lwow$ and a $b \in 2^\w$ such that the class of all $b$-computable models is hyperarithmetic in $b$, but exactly one isomorphism class has an index set that is not hyperarithmetic in $b$. In \cite{MR1295968} it was shown that if a group has an action that is a counterexample to the topological Vaught conjecture then there must be a ``minimal'' such action, i.e., one where for any invariant Borel set $C$, either $C$ or its complement contains countably many orbits. The paper \cite{MR2289896} contained the striking result that if there is a counterexample to Vaught's conjecture for $\Lwow$, then there must be a counterexample for $\Lwow$ which has no models of size $\aleph_2$. Hjorth's tour-de-force \cite{MR1800351} established that if $G$ is a Polish group which does not satisfy the topological Vaught conjecture then there must be a closed subgroup of $G$ which has $\Sym{\infty}$ as a continuous homomorphic image. Finally, for an informative survey of various different approaches which have been tried, see \cite{MR3451890}. %%%% %%%% %%%% %%%% %%%% %%%% \subsection{History of Our Proof} %%%% %%%% %%%% %%%% %%%% %%%% Our proof that there is a counterexample to Vaught's conjecture for $\Lwow$ arose in a very unusual way. It began back in 2002 when Knight announced he had proved that there is a first-order counterexample to Vaught's conjecture \cite{Knight2002}. Given the importance of the result, the community spent a great deal of effort trying to validate Knight's paper, including a conference at Notre Dame dedicated to the paper, which both Knight and Ackerman attended. However, despite these efforts, Knight's argument did not achieve general acceptance as a correct proof, although no definitive flaw in the construction had been identified. Over the next several years, Knight attempted several new formulations of his approach, with the goal of making it more understandable by the community. During that time Ackerman read, and gave feedback on, several of Knight's drafts, including some which were not made public. Then, in February 2026, Ackerman and Freer approached Knight with the idea to use AI coding agents to help formalize his proof in Lean. Knight agreed and gave Ackerman and Freer a draft of a new, clearer version of the infinitary argument which he had been working on but had not yet made public. While Knight had not thoroughly vetted this proof for errors, it was, at its core, a streamlined presentation of his earlier approach. Over the following 8 months, Freer worked extensively with coding agents (Claude Code and Codex with models ranging from Opus 4.5 through 5.5, Fable 5 and 5.1, and GPT 5.2 through 6) and occasional help from GPT Pro (5.2 through 6) to formalize the infinitary argument from Knight's recent working draft. This involved using an agentic coding ``skill'' \texttt{lean4-skills} \cite{lean4-skills} that Freer had developed to streamline and improve the process of using Lean, as well as the Lean LSP MCP server \cite{lean-lsp-mcp}. During this time, Freer periodically consulted with Ackerman as difficulties arose. Eventually this process led to a formally verified counterexample to Vaught’s conjecture for infinitary logic, with the entire argument certified in Lean. The formal proof makes use of Freer's \texttt{infinitary-logic} Lean library \cite{infinitary-logic} for standard results in the model theory of $\Lwow$ and descriptive set theory. A version of the complete formal proof has been checked by Comparator and is available on the Palomar Registry \cite{Palomar}. Another version of the formal proof, available on GitHub \cite{github}, has a cleaner API so as to provide reusable building blocks for further refinements and extensions. It follows the present exposition somewhat more closely than the first complete Lean proof, although its proof organization still differs in some places, and not every line of this exposition has been formally verified. The process of producing the counterexample turned out to be less straightforward than typical formalization projects. Knight's working draft presented a very complicated combinatorial object along with a strategy for deriving a counterexample from its various structural and extension properties. While the properties that Knight described were essentially sufficient to yield a counterexample, substantial revisions to the combinatorial object were required in order for it to satisfy these conditions. Closing this gap involved a great deal of human mathematical direction and AI-assisted exploration. Near the end, SMT and Horn clause solvers were used to investigate finite configurations and test proposed lemmas, though the final Lean proof does not involve trusting these solvers, and subsequently the resulting complicated objects were substantially simplified. Once a counterexample was found, Freer helped guide the AI to further streamline the argument while Ackerman wrote the first draft of this paper. Our goal is for the presentation in this paper to describe abstractions that highlight the key ideas present in all of Knight's papers while also outlining the overall path to a formally verified proof. Many details are elided, especially near the end of the argument; we plan to describe the argument more fully in a forthcoming manuscript. %%%% %%%% %%%% %%%% %%%% %%%% \subsection{Outline} %%%% %%%% %%%% %%%% %%%% %%%% After this outline and some notation, the rest of this paper has three main sections. First, in \cref{Knight Systems Section}, we introduce ``Knight systems'', a framework for showing that a class of countable structures has exactly $\aleph_1$ many isomorphism types and no perfect set of non-isomorphic structures. While the \emph{specific} framework of Knight systems is introduced here for the first time by Ackerman, it abstracts the central structural ideas developed throughout Knight's earlier work, going back to his 2002 paper \cite{Knight2002}. Second, in \cref{Toy Example Section}, we introduce a ``toy example'' of a Knight system built from trees. While the class of structures will not end up being the set of models of a sentence of $\Lwow$, it is instructive to see how one might try to build a Knight system from trees, and many of the features we see in trees will occur in the eventual counterexample. As such, this toy example is a useful framework to keep in mind while reading through the much more complicated section on the counterexample. Third, in \cref{Counterexample Section}, we introduce the counterexample in three parts. First, in \cref{Plans and Templates Subsection}, we introduce the basic components of the counterexample, culminating in the notion of a template system. Second, in \cref{Knight System of Counterexample Subsection}, we discuss how one would build a weak Knight system out of a template system. Finally, in \cref{Legal Templates Subsection}, we introduce the combinatorial notion of ``legal templates''. This is defined specifically so that the weak Knight system built from them would be a Knight system and hence witness that they describe a counterexample. We then derive the main theorem, that the weak Knight system constructed in \cref{Knight System of Counterexample Subsection} is in fact a Knight system, from three substantial propositions. These propositions were the main aspects which required a large amount of guided AI work. They have been formally verified in Lean, but their proofs are omitted here. %%%% %%%% %%%% %%%% %%%% %%%% \subsection{Notation} %%%% %%%% %%%% %%%% %%%% %%%% We now give some conventions and notation which are specific to this paper. All languages will be relational and all relation symbols have arity at least $1$. For a language $\Lang$, let $\Lang^n \subseteq \Lang$ be the language consisting of only those relation symbols in $\Lang$ of arity $n$. All structures will be countable with non-empty domains. We will use script letters for structures with the corresponding Roman letters for their domain, e.g.,\ $\cM$ has underlying set $M$. Bold letters will represent tuples of elements or tuples of variables. We will write $\aa \subseteq \cM$ to mean that all elements of the tuple $\aa$ are in $M$. For $n \in \w$, let $[n] = \{0, 1, \ldots, n-1\}$. If $E$ is a symmetric relation on a set $X$ we say that a subset $X_0 \subseteq X$ is an \defn{$E$-antichain} if $(\forall x, y \in X_0)\, (x \neq y) \rightarrow \neg E(x, y)$. If $\Lang$ is a countable language let $\Str_{\Lang}(\w)$ be the collection of $\Lang$-structures with underlying set $\w$ given the standard topology. We say that a non-empty closed subset of $\Str_{\Lang}(\w)$ is a \defn{perfect set} of models if it has no isolated points. %%%% %%%% %%%% %%%% %%%% %%%% %%%% %%%% \section{Knight Systems} \label{Knight Systems Section} %%%% %%%% %%%% %%%% %%%% %%%% %%%% %%%% In this section we introduce the key abstractions of this paper, culminating in the notion of a Knight system. We then show that any class of structures which is the base of a Knight system must have $\aleph_1$ many structures up to isomorphism as well as no perfect set of non-isomorphic structures. %%%% %%%% %%%% %%%% %%%% %%%% \subsection{Geometry Languages} %%%% %%%% %%%% %%%% %%%% %%%% An important aspect of the construction is a background finitary geometry on each structure, and we will only attempt to characterize the structure of the finite sets which are closed in this geometry. \begin{definition} Suppose $\Lang_a$ is a language where, for each $n \geq 1$, the language $\Lang_a^n$ has a unique relation symbol $P_n$. We define the \defn{theory of $\Lang_a$-geometry} to be the countable theory $\ThGeo[\Lang_a] \subseteq \Lwow(\Lang_a)$ consisting of the following sentences. \begin{itemize} \item For $n \geq 1$, \[ (\forall x_0, \dots, x_{n-1})\, P_n(x_0, \dots, x_{n-1}) \rightarrow \bigwedge_{i < j \in [n]} (x_i \neq x_j) \] and if $\sigma\: [n] \to [n]$ is a bijection then \[ (\forall x_0, \dots, x_{n-1})\, P_n(x_0, \dots, x_{n-1}) \leftrightarrow P_n(x_{\sigma(0)}, \dots, x_{\sigma(n-1)}). \] \item For all $n \geq 1$, \[ (\forall x_0, \dots, x_{n-1})\bigwedge_{i < j \in [n]} (x_i \neq x_j) \rightarrow \bigvee_{k \in \w}(\exists x_n, \dots, x_{n+k -1})\, P_{n+k}(x_0, \dots, x_{n+k-1}). \] \item For $n_0, n_1, k\geq 1$ if $P_{n_0}(x_0, \dots, x_{n_0-1})$ and $P_{n_1}(y_0, \dots, y_{n_1-1})$ and $z_0, \dots, z_{k-1}$ is an enumeration of $\{x_i\}_{i \in [n_0]} \cap \{y_i\}_{i \in [n_1]}$ then $P_k(z_0, \dots, z_{k-1})$ holds. \end{itemize} If $\Lang_a \subseteq \Lang$ and $\cM$ is an $\Lang$-structure which satisfies $\ThGeo[\Lang_a]$ then we say $\cM$ has a \defn{$\Lang_a$-geometry} and we call a tuple satisfying a relation in $\Lang_a$ \defn{closed}. \end{definition} An $\Lang_a$-structure $\cM$ satisfies $\ThGeo[\Lang_a]$ if there is a locally finite closure relation $\cl_{\cM}$ on $M$ such that $\{\aa \st \cM \models P_n(\aa)\}$ is precisely the collection of enumerations of non-empty closed sets of size $n$. For our purposes, it is not enough to simply define the closed sets. We also need to define, for each tuple enumerating a closed set, an ``invariant'' of the tuple. This invariant is meant to capture all relevant information about the tuple. \begin{definition} Suppose that \begin{itemize} \item $\Lang_a, \Lang_b, \Lang_c$ are languages with $\Lang_c \cap \Lang_b =\emptyset$ and $\Lang_a \subseteq \Lang_c$, and \item for each $n \geq 1$, we have $|\Lang_a^n| = 1$ and $|\Lang_b^n| > 0$. \end{itemize} We define the theory of \defn{$(\Lang_a, \Lang_b, \Lang_c)$-structured geometry}, denoted by $\ThStrGeo<\Lang_a>[\Lang_b](\Lang_c)$, to consist of the following collections of sentences. \begin{itemize} \item[(a)] $\ThGeo[\Lang_a]$. \item[(b)] For all $n \geq 1$ and $P_n \in \Lang_a^n$, \[ (\forall x_0, \dots, x_{n-1})\, P_n(x_0, \dots, x_{n-1}) \leftrightarrow \bigvee_{Q_n \in \Lang_b^n} Q_n(x_0, \dots, x_{n-1}). \] \item[(c)] For all $n \geq 1$ and distinct $Q_n, Q_n'\in \Lang_b^n$, \[ (\forall x_0, \dots, x_{n-1})\, Q_n(x_0, \dots, x_{n-1}) \rightarrow \neg Q_n'(x_0, \dots, x_{n-1}). \] \item[(d)] For any $k, n \geq 1$, any $Q \in \Lang_b^n$, any $R \in \Lang_b^k \cup \Lang_c^k$, and any sequence $\_{j \in [k]} \subseteq [n]$, \begin{align*} (\forall x_0,\dots, x_{n-1})&(\forall y_0, \dots, y_{n-1})\, [Q(x_0, \dots, x_{n-1}) \And Q(y_0, \dots, y_{n-1})] \\ % &\rightarrow [R(x_{i_0}, \dots, x_{i_{k-1}}) \leftrightarrow R(y_{i_0}, \dots, y_{i_{k-1}})]. \end{align*} \end{itemize} If $\Lang_a, \Lang_b, \Lang_c \subseteq \Lang$ and $\cM$ is an $\Lang$-structure which satisfies $\ThStrGeo<\Lang_a>[\Lang_b](\Lang_c)$ then we say that $\cM$ has an \defn{$(\Lang_a, \Lang_b, \Lang_c)$-structured geometry}. We call elements of $\Lang_b$ \defn{invariants}. If $\cM\models \ThStrGeo<\Lang_a>[\Lang_b](\Lang_c)$ and $\cM \models Q(\aa)$ where $Q \in \Lang_b$ then we call $Q$ the \defn{invariant} of $\aa$. We also refer to $\cM$ as a \defn{lift} of $\cM\rest[\Lang_c]$. \end{definition} So $\cM$ has an $(\Lang_a, \Lang_b, \Lang_c)$-structured geometry if (a) $\cM$ has an $\Lang_a$-geometry, (b, c) every enumeration of a closed set realizes a unique invariant in $\Lang_b$, and (d) the relation symbols in $\Lang_b$ completely determine the quantifier-free $(\Lang_b \cup \Lang_c)$-structure of their arguments. A useful intuition is that the relation symbols in $\Lang_a$ define a finitary geometry and the relation symbols in $\Lang_b$ provide ``invariants'' for each finite closed set. \begin{convention} For the rest of \cref{Knight Systems Section} we fix languages $\Lang_a, \Lang_b, \Lang_c$ with $\Lang_a \subseteq \Lang_c$, $\Lang_b \cap \Lang_c = \emptyset$ and such that for all $n \geq 1$, we have $\Lang_a^n = \{P_n\}$ and $|\Lang_b^n| > 0$ and $|\Lang_c^n| \leq \w$. \end{convention} %%%% %%%% %%%% %%%% %%%% %%%% \subsection{Invariant Diagrams and Invariant Systems} %%%% %%%% %%%% %%%% %%%% %%%% A key feature of structured geometries is that an invariant determines which atomic formulas hold on its arguments. In this way an invariant of a tuple determines the structure of a tuple. We will be interested in classes where the structure of a specific invariant is the same across all models in the class. \begin{definition} \label{Invariant diagram definition} An \defn{invariant diagram} is a collection $\ID$ of pairs of formulas satisfying the following. \begin{itemize} \item[(a)] If $(P(x_0, \dots, x_{n-1}), \psi(y_0, \dots, y_{k-1})) \in \ID$ then $\{y_i\}_{i \in [k]} \subseteq \{x_i\}_{i \in [n]}$ and $P \in \Lang_b$, and either $\psi(y_0, \dots, y_{k-1})$ is an atomic formula or the negation of an atomic formula. \item[(b)] For every $Q\in \Lang_b^n$, $R \in \Lang_b^k\cup \Lang_c^k$ and $\_{i \in [k]} \subseteq [n]$ precisely one of the following holds: \begin{itemize} \item $(Q(x_0, \dots, x_{n-1}), R(x_{j_0}, \dots, x_{j_{k-1}})) \in \ID$, or \item $(Q(x_0, \dots, x_{n-1}), \neg R(x_{j_0}, \dots, x_{j_{k-1}})) \in \ID$. \end{itemize} \item[(c)] For each $Q \in \Lang_b$ there is an $(\Lang_b\cup\Lang_c)$-structure $\cM$ where \begin{itemize} \item $\cM \models \ThStrGeo<\Lang_a>[\Lang_b](\Lang_c)$, \item $\cM \models (\exists \xx)\, Q(\xx)$, and \item for all $Q^* \in \Lang_b^n$ and $\_{i \in [k]} \subseteq [n]$ with $\bigl(Q^*(x_0, \dots, x_{n-1}), \psi(x_{j_0}, \dots, x_{j_{k-1}})\bigr) \in \ID$, we have \[ \cM \models (\forall x_0, \dots, x_{n-1})\, Q^*(x_0, \dots, x_{n-1}) \rightarrow \psi(x_{j_0}, \dots, x_{j_{k-1}}). \] \end{itemize} \end{itemize} \end{definition} \cref{Invariant diagram definition} (a) and (b) tell us that an invariant completely determines the quantifier-free structure of its arguments. \cref{Invariant diagram definition} (c) then tells us that each invariant is realized in a structure which is \emph{compatible} with the invariant diagram. \begin{definition} We say that an $(\Lang_b \cup \Lang_c)$-structure $\cM$ is \defn{compatible with $\ID$} if it satisfies the following two conditions. \begin{itemize} \item $\cM \models \ThStrGeo<\Lang_a>[\Lang_b](\Lang_c)$. \item For $Q \in \Lang_b^n$, an atomic or negated atomic $(\Lang_b \cup \Lang_c)$-formula $\psi(y_0, \dots, y_{k-1})$, and $\_{i \in [k]} \subseteq [n]$ with $\bigl(Q(x_0, \dots, x_{n-1}), \psi(x_{j_0}, \dots, x_{j_{k-1}})\bigr) \in \ID$, we have \[ \cM \models (\forall x_0, \dots, x_{n-1})\, Q(x_0, \dots, x_{n-1}) \rightarrow \psi(x_{j_0}, \dots, x_{j_{k-1}}). \] \end{itemize} \end{definition} In other words, $\cM$ is compatible with $\ID$ if the information contained in any closed tuple in $\cM$ agrees with the information the invariant diagram says should hold of any tuple with its invariant. It will be important, though, that invariants carry information beyond just the quantifier-free information. We therefore need a notion of ``information up to complexity $\beta$''. \begin{definition} \label{Invariant system definition} An \defn{invariant system} (on $\Lang_b$) is a collection of maps $\mbf{\tau} = \<\tau_\beta\>_{\beta \in \w_1}$ which satisfy the following. \begin{itemize} \item[(a)] For all $\beta \in \w_1$, we have $\tau_\beta\: \Lang_b \to \Lang_b$. \item[(b)] For all $n \geq 1$, for all $\beta \in \w_1$, we have $\tau_\beta\rest[\Lang_b^n]:\Lang_b^n \to \Lang_b^n$, i.e., for all invariants $Q$, $\tau_\beta(Q)$ has the same arity as $Q$. \item[(c)] For all $\alpha \leq \beta \in \w_1$, we have $\tau_\alpha \circ \tau_\beta = \tau_\beta \circ \tau_\alpha = \tau_\alpha$. \item[(d)] If for all $\beta \in \w_1$ we have $\Lang_b[\mbf{\tau}, \beta] = \{Q \in \Lang_b \st \tau_\beta(Q) = Q\}$, then \begin{itemize} \item[(i)] for all $\beta \in \w_1$, we have $|\Lang_b[\mbf{\tau}, \beta]| \leq \w$, \item[(ii)] for all $\beta \in \w_1$, we have $\Lang_b[\mbf{\tau}, \beta] \neq \Lang_b$, and \item[(iii)] $\Lang_b = \bigcup_{\beta \in \w_1}\Lang_b[\mbf{\tau}, \beta]$. \end{itemize} We also let $\Lang_b[\mbf{\tau}, \w_1] = \Lang_b$. \end{itemize} For $\beta \in \w_1$ we say that the elements of $\Lang_b[\mbf{\tau}, \beta]$ are \defn{$\beta$-invariants}. We define the \defn{$\mbf{\tau}$-rank} of an invariant $Q$, denoted by $\rank[\mbf{\tau}](Q)$, to be the least $\beta$ such that $\tau_\beta(Q) = Q$. \end{definition} The intuition is that an invariant system gives us a way to take a $\beta$-invariant and an $\alpha < \beta$ and return the projection of the $\beta$-invariant ``down to complexity $\alpha$''. Note that all information in $\Lang_c$ is preserved under projection, and hence can be thought of as having ``complexity $0$''. Also note that condition (d) implies $|\Lang_b| = \aleph_1$. \begin{definition} Suppose $\cM$ is an $(\Lang_b \cup \Lang_c)$-structure. We define the \defn{$\beta$-projection} of $\cM$, denoted by $\tau_\beta(\cM)$, to be the $(\Lang_b \cup \Lang_c)$-structure satisfying the following. \begin{itemize} \item $\cM$ and $\tau_\beta(\cM)$ have the same underlying set $M$. \item For all relation symbols $R \in \Lang_c^n$ and all tuples $a_0, \dots, a_{n-1} \in M$, \[ \tau_\beta(\cM) \models R(a_0, \dots, a_{n-1})\text{ if and only if }\cM \models R(a_0, \dots, a_{n-1}). \] \item For all relation symbols $R \in \Lang_b^n$ and all tuples $a_0, \dots, a_{n-1} \in M$, we have $\tau_\beta(\cM) \models R(a_0, \dots, a_{n-1})$ if and only if there is an $R^* \in \Lang_b$ with $\tau_\beta(R^*) = R$ and $\cM \models R^*(a_0, \dots, a_{n-1})$. \end{itemize} Suppose $\cM$ is an $(\Lang_a, \Lang_b, \Lang_c)$-structured geometry. We define the \defn{$\mbf{\tau}$-rank} of $\cM$, denoted by $\rank[\mbf{\tau}](\cM)$, to be the least $\beta$ such that $\tau_\beta(\cM) = \cM$. \end{definition} We can think of the $\beta$-projection of $\cM$ as the structure which is obtained by replacing all invariants in $\cM$ with their projections down to $\beta$ and keeping all other information the same. It will be important to know when an invariant diagram and an invariant system are compatible. \begin{definition} Suppose $\ID$ is an invariant diagram and $\mbf{\tau} = \<\tau_\beta\>_{\beta \in \w_1}$ is an invariant system. We say that $\ID$ and $\mbf{\tau}$ are \defn{compatible} if for all $\beta \in \w_1$, \begin{itemize} \item if $(P(\xx), Q(\yy)) \in \ID$ with $P, Q \in \Lang_b$ then $(\tau_\beta(P)(\xx), \tau_\beta(Q)(\yy)) \in \ID$, and \item if $P \in \Lang_b$ and $Q \in \Lang_c$ then \[ (P(\xx), Q(\yy)) \in \ID \text{ if and only if }(\tau_\beta(P)(\xx), Q(\yy)) \in \ID. \] \end{itemize} \end{definition} An invariant diagram and an invariant system are compatible if for all $\beta$, taking the $\beta$-projection in the invariant system of relations preserves the structure of the invariant diagram. The following lemma is immediate. \begin{lemma} Suppose $\ID$ is an invariant diagram and $\mbf{\tau} = \<\tau_\beta\>_{\beta \in \w_1}$ is an invariant system compatible with $\ID$. Then for every $(\Lang_b \cup \Lang_c)$-structure $\cM$ which is compatible with $\ID$ and every $\beta \in \w_1$, we have that $\tau_\beta(\cM)$ is compatible with $\ID$. \end{lemma} %%%% %%%% %%%% %%%% %%%% %%%% \subsection{Density} %%%% %%%% %%%% %%%% %%%% %%%% When studying structures which are compatible with an invariant diagram $\ID$, a natural first place to look would be those structures where, if an invariant extension is realized somewhere in the model it must be realized everywhere in the model --- specifically on those structures which satisfy the following axioms for all $(Q(\xx\yy), R(\xx)) \in \ID$: \[ (\exists \xx^*\yy^*)\, Q(\xx^*\yy^*) \rightarrow [(\forall \xx)\, R(\xx) \rightarrow (\exists \yy)\, Q(\xx\yy)]. \] However, this extension property is too strong and would, by a standard back and forth argument, force every model to be ultrahomogeneous with respect to partial isomorphisms between closed sets. Instead we will want a weakened extension property that uses the fact that invariants have projections that lose information. \begin{definition} \label{Density theory definition} Suppose $\ID$ is an invariant diagram and $\mbf{\tau} = \<\tau_\beta\>_{\beta \in \w_1}$ is an invariant system compatible with $\ID$. For $\alpha < \beta \leq \w_1$ we define the \defn{$(\alpha, \beta)$-density theory} of $\ID$ and $\mbf{\tau}$, denoted by $\DensityTh~\beta~<\ID>[\mbf{\tau}](\alpha)$, to consist of the following sentences. \begin{itemize} \item[(a)] $\ThStrGeo<\Lang_a>[\Lang_b](\Lang_c)$. \item[(b)] Whenever $\bigl(Q(x_0, \dots, x_{n-1}), \psi(x_{j_0}, \dots, x_{j_{k-1}})\bigr) \in \ID$, we have \[ (\forall x_0, \dots, x_{n-1})\, Q(x_0, \dots, x_{n-1}) \rightarrow \psi(x_{j_0}, \dots, x_{j_{k-1}}). \] \item[(c)] For all $Q, R \in \Lang_b[\mbf{\tau}, \beta]$ with $(Q(\xx\yy), R(\xx)) \in \ID$, we have \[ (\forall \xx)\, R(\xx) \rightarrow (\exists \yy)\bigvee_{\substack{Q^* \in \Lang_b[\mbf{\tau}, \beta]\\ \tau_\alpha(Q^*) =\tau_\alpha(Q)}} Q^*(\xx\yy). \] \end{itemize} We say that an $(\Lang_b \cup \Lang_c)$-structure is \defn{$(\alpha, \beta)$-dense} (with respect to $\ID$ and $\mbf{\tau}$) if it satisfies the theory $\DensityTh~\beta~<\ID>[\mbf{\tau}](\alpha)$. When $\beta =\w_1$ we will omit mention of it. \end{definition} Intuitively an $(\Lang_b \cup \Lang_c)$-structure $\cM$ satisfies $(\alpha, \beta)$-density with respect to $\ID$ and $\mbf{\tau}$ if whenever we have a tuple $\aa \in \cM$ with invariant $R$ that has rank at most $\beta$, and there is an invariant $Q$ of rank at most $\alpha$ which not only is an extension of $\tau_\alpha(R)$, but also is the projection of \emph{some} extension of $R$ of rank at most $\beta$, then we can find an extension of $\aa$ to a closed tuple $\aa\bb$ whose invariant has an $\alpha$-projection equal to $Q$. Note that this is weaker than just saying that whenever $(Q(\xx\yy), R(\xx)) \in \ID$ with both $Q$ and $R$ having rank at most $\alpha$, then $\tau_\alpha(\cM)$ satisfies the extension property with respect to $(Q(\xx, \yy), R(\xx))$. \begin{remark} Note that the conjunction of $\DensityTh<\ID>[\mbf{\tau}](\alpha)$ is a sentence in $\Lwtw(\Lang_b \cup \Lang_c)$, not in $\Lwow(\Lang_b \cup \Lang_c)$, because \cref{Density theory definition} (c) has an uncountable disjunction. This will not be a problem, however, as our counterexample will not contain the full density axioms themselves but rather will be a ``shadow'' of a class that satisfies them. \end{remark} The following lemmas are immediate. \begin{lemma} Suppose $\rank[\mbf{\tau}](\cM) \leq \beta$. Then $\cM \models \DensityTh~\beta~<\ID>[\mbf{\tau}](\alpha)$ if and only if $\cM \models \DensityTh<\ID>[\mbf{\tau}](\alpha)$. \end{lemma} \begin{lemma} Suppose $\alpha < \beta$ and $\cM \models \DensityTh<\ID>[\mbf{\tau}](\beta)$. Then $\cM \models \DensityTh<\ID>[\mbf{\tau}](\alpha)$. \end{lemma} \begin{lemma} Suppose $\alpha \leq \beta$, $\cM$ is compatible with $\ID$ and $\tau_{\beta}(\cM)\models \DensityTh<\ID>[\mbf{\tau}](\alpha)$. Then $\cM \models \DensityTh<\ID>[\mbf{\tau}](\alpha)$. \end{lemma} %%%% %%%% %%%% %%%% %%%% %%%% \subsection{Back and Forth Systems} %%%% %%%% %%%% %%%% %%%% %%%% We now introduce one of the fundamental tools for studying structured geometries in a theory. \begin{definition} \label{Back and forth system definition} Suppose $\cM$ and $\cN$ are $\Lang_c$-structures which have an $\Lang_a$-geometry. For $\alpha \in \ORD$, a \defn{back and forth system} (of length $\alpha$) between $\cM$ and $\cN$ is a sequence $\_{i \leq \alpha}$ which satisfies the following. \begin{itemize} \item[(a)] For $i < j \leq \alpha$ we have $I_j \subseteq I_i$ and $I_\alpha \neq \emptyset$. \item[(b)] For each $i \leq \alpha$, the set $I_i$ consists of pairs of closed finite tuples $(\aa, \bb)$ of the same length, where $\aa \subseteq \cM$ and $\bb \subseteq \cN$. \item[(c)] If $\ell \leq \alpha$ and $(\_{i \in [n]}, \_{i \in [n]}) \in I_\ell$, then for all relation symbols $R \in \Lang_c^k$ and all sequences $\_{i \in [k]} \subseteq [n]$, we have \[ \cM \models R(a_{j_0}, \dots, a_{j_{k-1}})\text{ if and only if }\cN \models R(b_{j_0}, \dots, b_{j_{k-1}}). \] \item[(d)] For each $i < j \leq \alpha$ and each pair $(\aa, \bb) \in I_{j}$, \begin{itemize} \item[(i)] if $\aa^* \subseteq \cM$ and $\aa\aa^*$ is closed then there is a $\bb^* \subseteq \cN$ such that $(\aa\aa^*, \bb\bb^*) \in I_i$, and \item[(ii)] if $\bb^* \subseteq \cN$ and $\bb\bb^*$ is closed then there is a $\aa^* \subseteq \cM$ such that $(\aa\aa^*, \bb\bb^*) \in I_i$. \end{itemize} % \end{itemize} We say that $\cM$ and $\cN$ are \defn{$\alpha$-equivalent}, denoted by $\cM \equiv_\alpha \cN$, if there is a back and forth system of length $\alpha$, each component of which is non-empty. \end{definition} If $\_{i \leq \beta}$ is a back and forth system between $\cM$ and $\cN$ and $(\aa, \bb) \in I_\alpha$ (for $\alpha \leq \beta$) then we can think of $\aa$ and $\bb$ as being ``indistinguishable up to complexity $\alpha$''. Note, though, that the relation of $\equiv_\beta$ need not be an equivalence relation (although it is symmetric). One way to fix this would be to require that $(\<\>, \<\>) \in I_i$ for each $i \leq \beta$, and indeed this is what is done in classic back and forth arguments. But as in our context the empty tuple is not closed, this would remove the condition that all tuples in our back and forth systems are closed. The following is a generalization of a standard result. \begin{proposition} \label{Countably many equiv-beta classes implies no perfect set} Suppose $\Phi$ is a class of geometric $\Lang_c$-structures closed under isomorphism such that for all $\beta \in \w_1$, all $\equiv_\beta$-antichains in $\Phi$ are countable. Then there does not exist a perfect set of non-isomorphic models in $\Phi$. \end{proposition} \begin{proof} Suppose to get a contradiction that there is a perfect set $P$ of non-isomorphic models in $\Phi$. Let $BO$ be the collection of codes for countable linear orders $(L, \leq)$ such that there are distinct $\cM, \cN \in P$ and a sequence $\_{i \in L}$ which satisfy the conditions of \cref{Back and forth system definition}, each element of which is non-empty. If $L$ is ill-founded then by a standard back and forth argument we must have $\cM \cong \cN$. Therefore, because no two elements of $P$ are isomorphic, any linear order in $BO$ must be well-founded. But $BO$ is a $\Sigma_1^1$-class as the conditions in \cref{Back and forth system definition} are Borel in an appropriate space. So by $\Sigma_1^1$-bounding \cite[Corollary~25.14]{MR1940513} there must be a $\gamma < \w_1$ such that all orders in $BO$ have order type at most $\gamma$. Therefore if $\cM, \cN \in P$ and $\cM \equiv_{\gamma+1} \cN$ we must have $\cM = \cN$. Hence $P$ is an antichain in $\equiv_{\gamma+1}$. But $|P| = 2^\w$, getting us our contradiction. \end{proof} %%%% %%%% %%%% %%%% %%%% %%%% \subsection{Weak Knight Systems} %%%% %%%% %%%% %%%% %%%% %%%% We now introduce one of the basic structures in this section. The intuition is that a weak Knight system consists, for each $\beta$, of a collection of models of rank at most $\beta$ which satisfy density below $\beta$ and where being in the weak Knight system is preserved by projections in the invariant system. \begin{definition} Suppose $\ID$ is an invariant diagram and $\mbf{\tau}$ is an invariant system compatible with $\ID$. A \defn{weak Knight system} (for $\ID$ and $\mbf{\tau}$) is a sequence $\_{\beta \in \w_1}$ satisfying the following for each $\beta \in \w_1$. \begin{itemize} \item Each $K_\beta$ is an isomorphism closed collection of countable $(\Lang_b \cup \Lang_c)$-structures compatible with $\ID$ and with rank at most $\beta$. \item For all $\alpha < \beta$ and all $\cM \in K_\beta$, $\cM \models \DensityTh<\ID>[\mbf{\tau}](\alpha)$, i.e. $\cM$ satisfies $\alpha$-density. \item For all $\alpha < \beta$ and all $\cM \in K_\beta$, $\tau_\alpha(\cM) \in K_\alpha$. \end{itemize} We will let $K = \bigcup_{\beta \in \w_1} K_\beta$. We call $K_{-\infty} = \{\cM\rest[\Lang_c] \st \cM \in K\}$ the \defn{base} of $\mbf{K}$. \end{definition} Note that for a weak Knight system we do not assume for each $\beta$ that $K_\beta$ contains at most countably many non-isomorphic structures. One of the main advantages of weak Knight systems is that they give a way to produce back and forth systems between their models. \begin{proposition} \label{Knight systems imply equiv-beta equivalence} Suppose that \begin{itemize} \item[(a)] $\_{\beta \in \w_1}$ is a weak Knight system (for $\ID$ and $\mbf{\tau}$), \item[(b)] $\cM, \cN \in K_\beta$, and \item[(c)] there is an invariant $Q \in \Lang_b$ such that $\cM \models (\exists \xx)\, Q(\xx)$ and $\cN \models (\exists \xx)\, Q(\xx)$. \end{itemize} Then $\cM\rest[\Lang_c] \equiv_\beta \cN\rest[\Lang_c]$. \end{proposition} \begin{proof} For $i \leq \beta$ let $I_i$ be the collection of pairs $(\aa, \bb)$ such that \begin{itemize} \item $\aa \subseteq \cM$ and $\bb \subseteq \cN$ are closed and of the same length, and \item there is a $Q \in \Lang_b$ such that $\tau_i(\cM) \models Q(\aa)$ and $\tau_i(\cN) \models Q(\bb)$. \end{itemize} It suffices to show that $\_{i \leq \beta}$ is a back and forth system. The fact that when $i < j \leq \beta$ we have $I_j \subseteq I_i$ follows from the compatibility of $\mbf{\tau}$ and $\ID$ and the fact that $\tau_i = \tau_i \circ \tau_{j}$. Further, because $\cM, \cN \in K_\beta$ we have $\max\{\rank[\mbf{\tau}](\cM), \rank[\mbf{\tau}](\cN)\} \leq \beta$ and so $\tau_\beta(\cM) = \cM$ and $\tau_\beta(\cN) = \cN$. So if $\cM \models Q(\aa)$ and $\cN \models Q(\bb)$ we have $(\aa, \bb) \in I_\beta$. Hence \cref{Back and forth system definition} (a) holds. \cref{Back and forth system definition} (b) is immediate and \cref{Back and forth system definition} (c) follows from the fact that invariants determine the quantifier-free $\Lang_c$-structure on their arguments. We now show \cref{Back and forth system definition} (d.i); the proof of \cref{Back and forth system definition} (d.ii) is identical. Suppose $i < j \leq \beta$, $(\aa, \bb) \in I_{j}$ and $\aa \aa^*$ is closed in $\cM$. Let $P_{\aa}, P_{\bb}, Q_{\aa\aa^*} \in \Lang_b$ be such that $\tau_{j}(\cM) \models P_{\aa}(\aa)$, $\tau_{j}(\cM) \models Q_{\aa\aa^*}(\aa\aa^*)$ and $\tau_{j}(\cN) \models P_{\bb}(\bb)$. We then have $(Q_{\aa\aa^*}, P_\aa) \in \ID$ and $P_\aa = P_\bb$. Because $\tau_{j}(\cN) \in K_{j}$ we have that $\tau_{j}(\cN)$ satisfies $i$-density. Therefore there must be some $\bb^* \subseteq \cN$ and $Q_{\bb\bb^*} \in\Lang_b$ such that $\tau_{j}(\cN) \models Q_{\bb\bb^*}(\bb\bb^*)$ and $\tau_i(Q_{\bb\bb^*}) = \tau_i(Q_{\aa\aa^*})$. But then $(\aa\aa^*, \bb\bb^*) \in I_i$. As $(\aa, \bb)$ was arbitrary this implies \cref{Back and forth system definition} (d.i) and so $\_{i \leq \beta}$ is a back and forth system. \end{proof} In most situations we will have that ``most'' structures in the base of a weak Knight system will have lifts of high rank. In this situation the existence of a weak Knight system ensures that the base does not contain a perfect set of non-isomorphic models. \begin{theorem} \label{Weak Knight systems and perfect sets of models} Suppose that \begin{itemize} \item[(a)] $\mbf{K} = \_{\beta \in \w_1}$ is a weak Knight system, and \item[(b)] for all $\beta \in \w_1$, \[ \{\cM \in K_{-\infty} \st (\forall \cN \in K_\beta)\, \cN\rest[\Lang_c] \neq \cM\} \] has countably many isomorphism classes. \end{itemize} Then $K_{-\infty}$ does not contain a perfect set of non-isomorphic models. \end{theorem} \begin{proof} Fix $\beta \in \w_1$. Let \[ A_\beta = \{\cM \in K_{-\infty} \st (\forall \cN \in K_\beta)\, \cN \rest[\Lang_c] \neq \cM\}. \] By (b) $A_\beta$ has only countably many isomorphism classes. For $\cM, \cN \in K_\beta$ define $\cM \sim \cN$ if there is some $Q \in \Lang_b$ such that $\cM \models (\exists \xx)\, Q(\xx)$ and $\cN \models (\exists \xx)\, Q(\xx)$. Note that every relation symbol in $\Lang_b$ which is realized in a structure in $K_\beta$ must have rank at most $\beta$ and hence be in $\Lang_b[\mbf{\tau}, \beta]$. But $\Lang_b[\mbf{\tau}, \beta]$ is countable and so any $\sim$-antichain must be countable. By the definition of $A_\beta$, any model $\cM \in K_{-\infty}\setminus A_\beta$ must have a lift $\cM^* \in K_\beta$. By \cref{Knight systems imply equiv-beta equivalence} if $B$ is a $\equiv_\beta$-antichain among elements of $K_{-\infty} \setminus A_\beta$ then there must be an $\sim$-antichain $B^+$ such that $B = \{\cM\rest[\Lang_c] \st \cM \in B^+\}$. Therefore every $\equiv_\beta$-antichain in $K_{-\infty}\setminus A_\beta$ must be countable. Hence, because $A_\beta$ is countable up to isomorphism, any $\equiv_\beta$-antichain in $K_{-\infty}$ must be countable as well. But then by \cref{Countably many equiv-beta classes implies no perfect set}, $K_{-\infty}$ does not contain a perfect set of non-isomorphic models. \end{proof} %%%% %%%% %%%% %%%% %%%% %%%% \subsection{Knight Systems and Knight Classes} %%%% %%%% %%%% %%%% %%%% %%%% We now introduce the central object in this section, the Knight system. This is a weak Knight system with extra properties which ensure that its base satisfies the conditions of being a counterexample to Vaught's conjecture (provided the base is the class of countable models of a sentence of $\Lwow$). First, though, we need a few related definitions. \begin{definition} Suppose $\mbf{K} = \_{\beta \in \w_1}$ is a weak Knight system (for $(\ID, \mbf{\tau})$) and $\beta\in \w_1$. We say that $\cM \in K_\beta$ is \defn{maximal at level $\beta$} (for $\mbf{K}$) if whenever $\beta^* > \beta$ and $\cM^* \in K_{\beta^*}$ and $\tau_{\beta}(\cM^*) = \cM$, then $\cM = \cM^*$. We say that $\cM$ is \defn{maximal} if it is maximal at some level. We say $\mbf{K}$ \defn{has few maximal models} if for all $\beta \in \w_1$, up to isomorphism, there are countably many models which are maximal at $\beta$. \end{definition} \begin{definition} \label{Nice tuples definition} Suppose that $\mbf{K} = \_{\beta \in \w_1}$ is a weak Knight system (for $(\ID, \mbf{\tau})$), that $\cM$ is an $\Lang_c$-structure, and that $\aa \subseteq \cM$ is closed. We say that $\aa$ is \defn{eventually determined in $\cM$ with respect to $\mbf{K}$} if there are $\alpha_\aa \in \w_1$ and $Q \in \Lang_b$ satisfying the following conditions. \begin{itemize} \item There is some lift $\cM^*$ of $\cM$ with $\cM^* \in K_{\alpha_\aa}$ and $\cM^*\models Q(\aa)$. \item Whenever $\alpha^* > \alpha_{\aa}$ and $\cM^*$ is a lift of $\cM$ with $\cM^* \in K_{\alpha^*}$ then $\cM^* \models Q(\aa)$. \end{itemize} When the structure and weak Knight system are understood, we simply say that a tuple is ``eventually determined''. We say that $\cM$ is \defn{eventually determined with respect to $\mbf{K}$} if every closed tuple in $\cM$ is eventually determined. \end{definition} In other words, a tuple is eventually determined if all lifts past a certain level have to agree on the invariant of the tuple, and a structure is eventually determined if all closed tuples are eventually determined. Note that a structure being eventually determined does not necessarily imply that there is a maximal lift. This is because the levels at which the tuples stabilize could have a supremum which is a limit ordinal, and there might be no lift of the structure at that limit level. \begin{lemma} \label{Main theorem about niceness} If $\cM$ is eventually determined then there is an $\alpha_{\cM} < \w_1$ such that whenever $\cM^* \in K$ is a lift of $\cM$ we have $\rank[\mbf{\tau}](\cM^*) \leq \alpha_{\cM}$. \end{lemma} \begin{proof} Let $\<\aa_i\>_{i \in \w}$ be an enumeration of all closed tuples of $\cM$. For $i \in \w$ let $\alpha_{\aa_i} \in \w_1$ be minimal such that it satisfies the conditions in \cref{Nice tuples definition}. Note that as $K_\beta$ is closed under isomorphism for each $\beta$, the value $\alpha_{\aa_i}$ depends only on the isomorphism type of $(\cM, \aa_i)$. Let $\alpha_{\cM} = \sup\{\alpha_{\aa_i} +1 \st i \in \w\}$. Suppose to get a contradiction there is a $\cM^* \in K$ which is a lift of $\cM$ with $\rank[\mbf{\tau}](\cM^*) > \alpha_{\cM}$. Then for each $i \in \w$ and each $Q \in \Lang_b$, since $\aa_i$ is eventually determined, we have that $\cM^* \models Q(\aa_i)$ if and only if $\tau_{\alpha_{\cM}}(\cM^*) \models Q(\aa_i)$. Therefore $\cM^* = \tau_{\alpha_{\cM}}(\cM^*)$ and so $\rank[\mbf{\tau}](\cM^*) \leq \alpha_{\cM}$, yielding a contradiction. \end{proof} \begin{definition} \label{Knight system definition} Suppose $\mbf{K} = \_{\beta \in \w_1}$ is a weak Knight system (for $\ID$ and $\mbf{\tau}$). We say $\mbf{K}$ is a \defn{Knight system} if \begin{itemize} \item[(a)] $K_{-\infty} = \{\cM \rest[\Lang_c] \st \cM \in K\text{ and } \cM\text{ is maximal with respect to }\mbf{K}\}$, \item[(b)] $\mbf{K}$ has few maximal models, \item[(c)] if $\cM \in K_{-\infty}$ then $\cM$ is eventually determined with respect to $\mbf{K}$, and \item[(d)] for every invariant $Q \in \Lang_b$ there is some $\cM \in K$ where $\cM \models (\exists \xx)\, Q(\xx)$. \end{itemize} \end{definition} \begin{definition} \label{Knight class definition} We say a collection $\Phi$ of $\Lang_c$-structures is a \defn{Knight class} if there is an invariant diagram $\ID$, a compatible invariant system $\mbf{\tau} = \<\tau_\beta\>_{\beta \in \w_1}$, and a Knight system $\mbf{K} = \_{\beta \in \w_1}$ (for $(\ID, \mbf{\tau})$) such that $\Phi = K_{-\infty}$. We say that $\mbf{K}$ \defn{witnesses} that $\Phi$ is a Knight class. \end{definition} We then have the following theorem, which is the culmination of all the results in this section. \begin{theorem} \label{Knight classes have omega_1 many models} Suppose $\Phi$ is a Knight class. \begin{itemize} \item[(a)] $\Phi$ has precisely $\aleph_1$ many countable models up to isomorphism. \item[(b)] There does not exist a perfect set of non-isomorphic models in $\Phi$. \end{itemize} \end{theorem} \begin{proof} As $\mbf{K}$ has few maximal models, there are at most $\aleph_1$ many maximal models for $\mbf{K}$ up to isomorphism. But by \cref{Knight system definition} (a) every element of $\Phi$ is the reduct of (at least) one maximal model for $\mbf{K}$. Therefore $\Phi$ has at most $\aleph_1$ many models up to isomorphism. For all $\cM \in \Phi$, let $\alpha_{\cM}$ be as in \cref{Main theorem about niceness}. If $Q \in \Lang_b$ and $\rank[\mbf{\tau}](Q) > \alpha_{\cM}$, then $Q$ is not realized in any lift of $\cM$. Therefore, as there are $Q$ with arbitrarily large ranks, $\{\alpha_{\cM} \st \cM \in \Phi\}$ must be cofinal in $\w_1$ and hence have size $\aleph_1$. Therefore $\Phi$ must have at least $\aleph_1$ many models up to isomorphism and so (a) holds. Fix $\beta \in \w_1$. Let \[ A_\beta = \{\cM \in \Phi \st \text{ no lift of }\cM\text{ is maximal at any }\delta \geq \beta\}. \] Because $\mbf{K}$ has few maximal models, $A_\beta$ has only countably many isomorphism classes. But then $\{\cM \in \Phi \st (\forall \cN \in K_\beta)\, \cN \rest[\Lang_c] \neq \cM\}$ also has countably many models up to isomorphism. Therefore, by \cref{Weak Knight systems and perfect sets of models}, $\Phi$ does not have a perfect set of non-isomorphic models and (b) holds. \end{proof} \begin{definition} We say that a sentence $\sigma \in \Lwow(\Lang_c)$ is a \defn{Knight sentence} if the collection of countable models of $\sigma$ forms a Knight class. \end{definition} The following is immediate from \cref{Knight classes have omega_1 many models}. \begin{theorem} \label{Knight sentences are counterexamples to Vaught's conjecture} If $\sigma\in \Lwow(\Lang_c)$ is a Knight sentence then $\sigma$ has $\aleph_1$ many countable models up to isomorphism and does not have a perfect set of non-isomorphic models. Hence $\sigma$ is a counterexample to Vaught's conjecture for $\Lwow$. \end{theorem} %%%% %%%% %%%% %%%% %%%% %%%% %%%% %%%% \section{Toy Example} \label{Toy Example Section} %%%% %%%% %%%% %%%% %%%% %%%% %%%% %%%% We will now introduce a toy example. This example will produce a Knight class, even though it will not produce a Knight sentence. Walking through how we create the Knight system, and seeing what fails, will hopefully help provide insight into how the eventual counterexample behaves. %%%% %%%% %%%% %%%% %%%% %%%% \subsection{Labeled Geometric Trees} %%%% %%%% %%%% %%%% %%%% %%%% We now introduce the structures of our example. They will be trees with labels that are meant to capture information about the rank of elements. \begin{definition} Let $\Lang_a = \{P_n\}_{n \geq 1}$ where, for each $n \geq 1$, the relation symbol $P_n$ is of arity $n$. Let $\Lang_c = \Lang_a \cup \{\leq\}$ where $\leq$ is a binary relation symbol. We say an $\Lang_c$-structure $\cM$ is a \defn{geometric tree} if it satisfies the following. \begin{itemize} \item $\leq$ is a partial order with a greatest element called the root. \item For all $a \in \cM$, the set $\{a' \in \cM \st a' \geq a\}$ is finite and linearly ordered. \item For $n \geq 1$, we have \[ (\forall x_0, \dots, x_{n-1})\, P_n(x_0, \dots, x_{n-1}) \leftrightarrow \bigg[\Bigl(\bigwedge_{i < j \in [n]} x_i \neq x_j\Bigr) \And (\forall y)\, \bigg[\Bigl(\bigvee_{i \in [n]} y \geq x_i \Bigr) \rightarrow \Bigl(\bigvee_{i \in [n]} y = x_i\Bigr)\bigg]\bigg]. \] \end{itemize} If $\cM$ is a geometric tree and $a, b \in \cM$, we will say $\cM \models a <_1 b$ if $\cM \models a < b$ and $\cM \models (\forall c)\, a \leq c \leq b \rightarrow (c = a \Or c = b)$, i.e., $a$ is an immediate predecessor of $b$. \end{definition} In other words, a geometric tree is a tree where the closed sets are finite upwards closed sets. Note that in a geometric tree, the tree ordering is infinitarily definable from the geometry. The following is immediate, and says that geometric trees have an $\Lang_a$-geometry. \begin{lemma} If $\cM$ is a geometric tree then $\cM \models \ThGeo[\Lang_a]$. \end{lemma} The following is an important function on geometric trees. \begin{definition} Suppose $\cM$ is a countable geometric tree. The \defn{$\cM$-rank} is a map $\rank[\cM]\:M \to \w_1 \cup \{\infty\}$ where $\rank[\cM](a)$ is defined as follows. \begin{itemize} \item If $\cM \models (\forall b)\, b \not <_1 a$ then $\rank[\cM](a) = 0$. \item If there is a sequence $\_{i \in \w}$ such that for all $i \in \w$ we have $\cM \models a_{i+1} <_1 a_i$ and $a_0 = a$, then $\rank[\cM](a) = \infty$. \item Otherwise, $\rank[\cM](a) = \sup \{\rank[\cM](b) + 1 \st b <_1 a\}$. \end{itemize} \end{definition} \begin{definition} By a \defn{labeled tree} we mean a pair $\<(T, \leq), \mu\>$ where \begin{itemize} \item $(T, \leq)$ is a rooted tree, \item $\mu\:T \to \w_1 \cup \{\infty\}$, \item for all $a < b \in T$, we have $\mu(a) < \mu(b)$, where $\infty < \infty$. \end{itemize} We call $T$ the \defn{underlying set} of the labeled tree and we call $\mu$ the \defn{labeling}. We say that a labeled tree is \defn{finite} when its underlying set is. If $T_0 \subseteq T$ is an upwards closed set and $\mu_0 = \mu\rest[T_0]$, then we say that $\<(T, \leq), \mu\>$ \defn{extends} \linebreak $\<(T_0, \leq\,\rest[T_0 \times T_0]), \mu_0\>$. \end{definition} It is useful to think of a labeled tree as assigning a value $\alpha \in \w_1$ when we know the rank of the node is $\alpha$, but assigning the value $\infty$ if either the node is ill-founded or we don't yet know what the actual rank is. Our invariants will be built out of these finite labeled trees. \begin{definition} For $n\geq 1$ let $\Lang_b^n = \{Q_\zeta \st \zeta\text{ is a finite labeled tree with underlying set }[n]\}$. \end{definition} We will be interested in an invariant diagram which will allow all ``local labelings'' to be combined into a ``global labeling''. \begin{definition} Let $\IDtree$ be the invariant diagram such that whenever $\zeta = \<([n], \leq), \mu\>$ is a finite labeled tree and $P \in \Lang_b \cup \Lang_c$ then $(Q_\zeta(x_0, \dots, x_{n-1}), P(x_{i_0}, \dots, x_{i_{k-1}})) \in \IDtree$ precisely when one of the following holds. \begin{itemize} \item $P$ is $\leq$ and $i_0 \leq i_1$, \item $P$ is $P_k$, $i_0, \dots, i_{k-1}$ are distinct elements and $\{i_j\}_{j \in [k]}$ is an upwards closed set in $([n], \leq)$, \item $P$ is $Q_{\zeta^*}$ where $\zeta^* = \<([k], \leq_{\zeta^*}), \nu\>$, the map $i_\ell \mapsto \ell$ is an isomorphism between $([n], \leq_\zeta)\rest[\{i_j\}_{j \in [k]}]$ and $([k], \leq_{\zeta^*})$, the sequence $\{i_j\}_{j \in [k]}$ is upwards closed, and $\nu(j) = \mu(i_j)$ for all $j \in [k]$. \end{itemize} We call a structure compatible with $\IDtree$ a \defn{labeled geometric tree}. \end{definition} \begin{definition} Suppose $\cM$ is an $(\Lang_b \cup \Lang_c)$-structure. Let $\glabeling[\cM]$ be the collection of pairs $(a, \alpha) \in M \times (\w_1 \cup \{\infty\})$ such that there is a $\zeta = \<([n], \leq), \mu\>$ and a sequence $a_0, \dots, a_{n-1} \in M$ such that \begin{itemize} \item $\cM \models Q_{\zeta}(a_0, \dots, a_{n-1})$, \item $a = a_k$ for some $k \in [n]$, and \item $\mu(k) = \alpha$. \end{itemize} \end{definition} Because $\IDtree$ forces relations $Q_\zeta$ and $Q_{\zeta^*}$ to ``assign'' the same label to any common argument, we have the following immediate lemma. \begin{lemma} Suppose $\cM$ is compatible with $\IDtree$. Then $\cM \rest[\Lang_c]$ is a geometric tree, $\glabeling[\cM]$ is the graph of a function $\labeling[\cM]$ such that $\<(M, \leq), \labeling[\cM]\>$ is a labeled tree, and $\labeling[\cM](a) \geq \rank[\cM](a)$ for all $a \in M$. \end{lemma} %%%% %%%% %%%% %%%% %%%% %%%% \subsection{Knight System: Attempt 1} \label{Knight System: Attempt 1 subsection} %%%% %%%% %%%% %%%% %%%% %%%% We now attempt to build a Knight system over a class of trees. As we will see, the obvious thing to try will fail. However, seeing how it fails will be helpful for understanding the eventual counterexample. In particular, as the next example shows, if we intend for invariants to capture the relevant information about their arguments, we will have to restrict attention to some special collection of trees. \begin{example} Let $A \subseteq \w$. Let $\cM_A$ be the structured tree satisfying the following. \begin{itemize} \item $M_A = \{\\} \cup \{\ \st i \in \w\} \cup \{\ \st i \in A \text{~and~} j \in [i+2]\} \cup \{\ \st i \not \in A\}$. \item $a \leq b$ if $b$ is an initial segment of $a$. \item $\labeling[\cM_A] = \rank[\cM_A]$. \end{itemize} All elements of the form $\$ have rank $1$ and so all tuples of the form $\<\, \\>$ satisfy the same invariant. However, we can only extend a map from $\{\, \\}$ to $\{\, \\}$ to an automorphism of the structure if either $i = j$ or $\{i, j\}\cap A = \emptyset$. Further, if $A, B \subseteq \w$ are distinct, then $\cM_A \not \cong \cM_B$. As such, these trees contain a great deal more information than is captured by their labels. \end{example} \begin{definition} Suppose $\beta \in \w_1$. We say a countable geometric tree $\cM$ is \defn{$\beta$-full} if for all $\gamma < \beta$, \[ (\forall a \in M)\, \rank[\cM](a) > \gamma \rightarrow (\exists^\w b)\, b <_1 a\text{ and } \rank[\cM](b) = \gamma. \] We say $\cM$ is \defn{full} if it is $\theta_{\cM}$-full where $\theta_{\cM} = \inf\{\beta \st \range(\rank[\cM])\subseteq \beta\cup \{\infty\}\}$, and every node of rank $\infty$ has infinitely many immediate predecessors of rank $\infty$. Let $\Phi$ be the collection of full geometric trees. \end{definition} The following is then straightforward. \begin{lemma} \label{Full trees have structure preserved by invariants} Suppose that \begin{itemize} \item $\cM$, $\cN$ are full trees, \item $\labeling[\cM] = \rank[\cM]$ and $\labeling[\cN] = \rank[\cN]$, \item $\range(\rank[\cM]) \subseteq \range(\rank[\cN])$, \item $A \subseteq M$ is a finite closed set, and \item $i\:A \to \cN$ is an embedding of labeled geometric trees. \end{itemize} Then $i$ extends to an embedding of labeled geometric trees from $\cM$ to $\cN$. \end{lemma} \cref{Full trees have structure preserved by invariants} tells us that among full trees the invariant of the tuple completely determines the structure of a tuple. For this reason we will want to focus our attention on full trees. The fact that trees compatible with $\IDtree$ always have a global labeling function suggests a natural collection of projection functions, i.e. functions $\tau^-_\beta$ which replace all rank values of $\beta$ and above with $\infty$ and keep the rest the same. \begin{definition} \label{beta-truncation function} We define the \defn{$\beta$-truncation function}, denoted by $\trunc[\beta]$, to be the function \linebreak $\trunc[\beta]\: \w_1 \cup \{\infty\} \to \w_1 \cup \{\infty\}$ where \[ \trunc[\beta](\alpha) = \begin{cases} \alpha & \text{ if }\alpha < \beta,\\ \infty & \text{ otherwise.} \end{cases} \] \end{definition} We then define the following invariant system. \begin{definition} For $\beta \in \w_1$ let $\tau_\beta^-\:\Lang_b \to \Lang_b$ be the map given by $\tau_\beta^-(Q_\zeta) = Q_{\zeta^*}$ for $\zeta = \<(T, \leq), \mu\>$, where $\zeta^* = \<(T, \leq), \trunc[\beta] \circ \mu\>$. \end{definition} The following lemma then holds, because whenever $\alpha < \beta$, we have $\trunc[\alpha] \circ \trunc[\beta]= \trunc[\beta] \circ \trunc[\alpha] = \trunc[\alpha]$. \begin{lemma} $\mbf{\tau}^- = \<\tau^-_\beta\>_{\beta \in \w_1}$ is an invariant system compatible with $\IDtree$. \end{lemma} We would now like to define a Knight system with respect to $\IDtree$ and $\mbf{\tau}^-$. Unfortunately, as we will see, no such Knight system can exist, and we will eventually need to modify the definition of $\mbf{\tau}^-$. But it will be instructive to see \emph{why} such a Knight system can't exist, before we show how to create one for a closely related invariant system. First notice that if $\mbf{K}^- = \_{\beta \in \w_1}$ is a weak Knight system for $\mbf{\tau}^-$ then for any $\cM \in K^-_\beta$ we must have (a) $\tau_\beta^-(\cM) = \cM$ and (b) for all $\alpha < \beta$, the structure $\cM$ is $\alpha$-dense (with respect to $\IDtree$ and $\mbf{\tau}^-$). \begin{definition} Suppose $\beta \in \w_1$. We say that a labeled geometric tree $\cM$ has \defn{labels cut off at $\beta$} if \[ (\forall a \in M)\, \labeling[\cM](a) \geq \beta \rightarrow \labeling[\cM](a) = \infty. \] \end{definition} The following is immediate. \begin{lemma} \label{Characterizing labels cut off} Suppose $\cM$ is a labeled geometric tree. Then the following are equivalent. \begin{itemize} \item $\cM$ has labels cut off at $\beta$. \item $\tau^-_\beta(\cM) = \cM$. \end{itemize} \end{lemma} Therefore any $\cM \in K^-_\beta$ must have labels cut off at $\beta$. \begin{definition} Suppose $\beta \leq \w_1$. A labeled geometric tree $\cM$ has \defn{$\beta$-true labels} if, for all $a \in M$, we have \[ \rank[\cM](a) < \beta \rightarrow \rank[\cM](a)= \labeling[\cM](a). \] We say that $\cM$ has \defn{true labels} if it has $\w_1$-true labels. \end{definition} We then have the following characterization of when a labeled geometric tree is $\beta$-dense (with respect to $\IDtree$ and $\mbf{\tau}^-$). \begin{proposition} \label{Characterize beta-density} Suppose $\cM$ is a countable labeled geometric tree compatible with $\IDtree$. Then the following are equivalent. \begin{itemize} \item[(a)] $\cM$ is $\beta$-dense (with respect to $\IDtree$ and $\mbf{\tau}^-$), \item[(b)] $\cM\rest[\Lang_c]$ is $\beta$-full, $\cM$ has $\beta$-true labels and for all $n \in \w$ and $a \in M$, \begin{align*} \label{Characterize beta-density: Equation 1} \tag{\lucideicon{sprout}} \beta + n < \labeling[\cM](a) \rightarrow |\{b \in M\st b <_1 a\text{ and }\labeling[\cM](b) \geq \beta + n\}| = \w. \end{align*} \end{itemize} \end{proposition} \begin{proof} Assume (a). Note if $\tau_\beta^-(Q_\zeta) = Q_{\zeta^*}$ then the labeling of $\zeta^*$ must have range in $\beta \cup \{\infty\}$. That $\cM$ has $\beta$-true labels then follows from an easy induction. The fact that $\cM$ is $\beta$-full follows from the fact that the collection of invariants with a labeling whose range is contained in $\beta \cup \{\infty\}$ has amalgamation, in the obvious sense. By density we may add arbitrarily many immediate predecessors labeled $\gamma < \beta$ whenever $\gamma$ is less than the label of a node. Further these labels are preserved by projection. Now suppose $a \in M$, $n \in \w$ and $\beta + n < \labeling[\cM](a)$. Let $\_{i \in [k]}$ be such that $a = a_{k-1} <_1 a_{k-2} <_1 \dots <_1 a_{0}$ where $a_{0}$ is the root. Let $\zeta$ be such that $\cM \models Q_\zeta(a_{0}, \dots, a_{k-1})$. Let $\zeta^- = \<([n+k+1], \leq), \mu^-\>$ where $\mu^-(k+i) = \beta + (n - i)$ for $0 \leq i \leq n$ and $k+n <_1^- k+n-1<_1^- \dots <_1^- k <_1^- k-1$. Because $\tau_\beta^-(Q_{\zeta^-})(x_0, \dots, x_{k+n})$ implies the label of each of $x_k, \dots, x_{k+n}$ is $\infty$, if $\zeta^*$ is such that $\tau_\beta^-(Q_{\zeta^-}) = \tau_{\beta}^-(Q_{\zeta^*})$ we have $Q_{\zeta^*}(x_0, \dots, x_{k+n})$ implies the label of $x_k$ is at least $\beta + n$. Let $\zeta^{+\ell}$ be the disjoint amalgamation (in the obvious sense) of $\ell$ copies of $\zeta^-$ over $\zeta$. Then if $Q_{\zeta^{\dagger \ell}}$ is such that $\tau_{\beta}^-(Q_{\zeta^{\dagger \ell}}) = \tau_\beta^-(Q_{\zeta^{+\ell}})$ and $\cM \models Q_{\zeta^{\dagger \ell}}(a_0,\dots, a_{k-1}, b_0, \dots, b_{\ell \cdot (n+1) -1})$ then there must be $\ell$ many elements among $b_0, \dots, b_{\ell \cdot (n+1)-1}$ which have label at least $\beta+n$ and which are immediate predecessors to $a_{k-1}$. Therefore, as $\ell$ was arbitrary, by $\beta$-density (b) holds. Now suppose (b) holds. Suppose $\gamma < \beta$ and $\gamma < \labeling[\cM](a)$. Then if $\gamma \geq \rank[\cM](a)$ we would have $\rank[\cM](a) \leq \gamma < \beta$ and so $\rank[\cM](a) = \labeling[\cM](a) > \gamma$ getting a contradiction. So we must have $\gamma < \rank[\cM](a)$. But then $\beta$-fullness and $\beta$-true labels imply that there must be infinitely many immediate predecessors of $a$ with label and rank $\gamma$. Now suppose $\cM \models Q_{\zeta}(a_0, \dots, a_{n-1})$ and $\zeta^-= \<([n + k], \leq^-), \mu^-\>$ is an extension of $\zeta$. By reordering if necessary we can assume all parents precede their children in $[n+k]$. We then choose $a_n,\dots, a_{n+k-1}$ by induction where, if we have $a_0, \dots, a_{n+i-1}$ we choose a new $a_{n+i}$ satisfying the following. \begin{itemize} \item $a_{n+i} \not \in \{a_j\}_{j \in [n+i]}$. \item If $n+i <_1^- \ell$ then $a_{n+i} <_1 a_\ell$. \item If $\mu^-(n+i) < \beta$ then $\rank[\cM](a_{n+i}) = \mu^-(n+i)$. \item If $\mu^-(n+i) \geq \beta$ then let $(b_0, \dots, b_{z-1})$ be the longest chain among elements $\leq^- n+i$ where $\mu^-(b_j) \geq \beta$ for all $j \in [z]$. Choose $a_{n+i}$ to be any new element with $\labeling[\cM](a_{n+i}) \geq \beta + (z-1)$. Note that we can always find one by \eqref{Characterize beta-density: Equation 1}. \end{itemize} It is then immediate that there is some invariant $Q_{\zeta^+}$ where $\cM \models Q_{\zeta^+}(a_0, \dots, a_{n+k-1})$ and $\tau^-_\beta(Q_{\zeta^-}) = \tau^-_\beta(Q_{\zeta^+})$. Therefore, as $\zeta$ and $\zeta^-$ were arbitrary, $\cM$ satisfies $\beta$-density and (a) holds. \end{proof} Putting together \cref{Characterizing labels cut off} and \cref{Characterize beta-density}, we obtain the following. \begin{proposition} Suppose $\cM$ is a countable labeled geometric tree. Then the following are equivalent. \begin{itemize} \item[(a)] $\cM$ is $\alpha$-dense for all $\alpha < \beta$ and $\tau^-_\beta(\cM) = \cM$. \item[(b)] Either \begin{itemize} \item $\beta = 0$ and all nodes are labeled with $\infty$, \item $\beta = \w \cdot \delta$ is a limit ordinal and $\cM$ is $\beta$-full, has $\beta$-true labels and has labels cut off at $\beta$, or \item $\beta = \alpha + 1$ is a successor ordinal, $\cM$ has true labels, $\range(\rank[\cM]) \subseteq \beta \cup \{\infty\}$, it is $\alpha$-full and every element of rank $\infty$ has infinitely many immediate predecessors of rank $\infty$. \end{itemize} \end{itemize} \end{proposition} \begin{proof} The equivalence of (a) and (b) for $\beta = 0$ or a limit follows immediately from \cref{Characterizing labels cut off} and \cref{Characterize beta-density}. Now suppose $\beta = \alpha+1$. Assume (a). We then have that $\cM$ satisfies $\alpha$-density and hence also $\alpha$-fullness. We also have $\range(\labeling[\cM]) \subseteq \beta \cup \{\infty\}$. If $\labeling[\cM](a) < \alpha$ then by $\alpha$-density, $\labeling[\cM](a) = \rank[\cM](a)$. But then also by $\alpha$-density, if $\labeling[\cM](a) = \alpha$ it has infinitely many immediate predecessors of all ranks $< \alpha$, and so $\rank[\cM](a) = \alpha$. Further, if $\labeling[\cM](a) = \infty$ then \cref{Characterize beta-density} ensures that there are infinitely many immediate predecessors $b$ with $\labeling[\cM](b) \geq \alpha+1$. But as labels are cut off at $\alpha+1$, these predecessors are labeled $\infty$. Repeating this produces an infinite descending chain and so $\rank[\cM](a) =\infty$. Assume (b) holds. The fact that $\cM$ has true labels and $ \range(\rank[\cM]) \subseteq \beta \cup \{\infty\}$ implies that $\tau^-_\beta(\cM) = \cM$. To show that $\cM$ satisfies $\alpha$-density we use \cref{Characterize beta-density}. If for any $a \in \cM$ we have $\alpha + n < \labeling[\cM](a)$, then we must have $\rank[\cM](a) = \infty$ and its infinitely many immediate predecessors with $\rank[\cM]$ equal $\infty$ satisfy the condition in \cref{Characterize beta-density} (b). Therefore $\cM$ satisfies $\alpha$-density and (a) holds. \end{proof} Now suppose $\mbf{K}^- = \_{\beta \in \w_1}$ is a weak Knight system. If $\cM \in K^-_\beta$ and $\beta > 1$ then $\cM$ is either the one-element tree or the infinitely branching ill-founded tree in which every infinite node has infinitely many leaf children. Therefore we must have $\range(\labeling[\cM]) \subseteq \{0, \infty\}$ as well. Any other structure in $K^-$ must be in either $K_0^-$ or $K_1^-$ and hence also must have labels contained in $\{0, \infty\}$. In particular $K^-$ can contain no structure with ordinal labels other than $0$ and so $\mbf{K}^-$ can't be a Knight system. %%%% %%%% %%%% %%%% %%%% %%%% \subsection{Knight System: Attempt 2} %%%% %%%% %%%% %%%% %%%% %%%% The key obstruction to $\mbf{\tau}^-$ occurred because of the interplay between $\beta$-density and being a fixed point of $\tau^-_{\beta+1}$. This suggests that a possible solution is to limit ourselves to limit $\beta$. \begin{definition} For $\beta \in \w_1$ let $\tau_\beta = \tau^-_{\w \cdot \beta}$ and let $\mbf{\tau} = \<\tau_\beta\>_{\beta \in \w_1}$. \end{definition} The following is then immediate. \begin{lemma} $\mbf{\tau} = \<\tau_\beta\>_{\beta \in \w_1}$ is an invariant system compatible with $\IDtree$. \end{lemma} \cref{Characterize beta-density} suggests the following potential Knight system. \begin{definition} For $\beta \in \w_1$, let $K_\beta$ be the collection of labeled geometric trees $\cM$ satisfying the following. \begin{itemize} \item $\cM$ is full. \item $\cM$ has $\w \cdot \beta$-true labels. \item $\cM$ has labels cut off at $\w \cdot \beta$. \item For all $\alpha < \beta$, $\tau_\alpha(\cM) \neq \cM$. \end{itemize} \end{definition} Now we turn our attention to maximal and eventually determined models. \begin{proposition} \label{Maximal models in labeled geometric trees} A labeled geometric tree is maximal for $\mbf{K}$ if and only if it is full and has true labels. \end{proposition} \begin{proof} If $\cM$ is maximal, then $\cM \in K_\beta$ for some $\beta$, so $\cM$ is full by definition. From the definition of $K_\beta$ we have whenever $\cM \in K_\beta$ that $\labeling[\cM] = \trunc[\w \cdot \beta] \circ \rank[\cM]$. Let $\kappa(\cM) = \min \{\delta \st \range(\rank[\cM]) \subseteq \w \cdot \delta \cup \{\infty\}\}$. First assume that $\cM \in K_\beta$ is full but does not have true labels. Then $\beta < \kappa(\cM)$. Let $\cN \in K_{\kappa(\cM)}$ be the truly labeled expansion of $\cM\rest[\Lang_c]$. We then have $\cN \in K_{\kappa(\cN)}$ and $\tau_\beta(\cN) = \tau_\beta(\cM) = \cM$. Therefore $\cM$ is not maximal. Hence we have the implication from left to right. Conversely, assume that $\cM$ is full and has true labels. By the definition of $\kappa(\cM)$, we have $\cM \in K_{\kappa(\cM)}$. Suppose that $\gamma > \kappa(\cM) = \beta$, that $\cN \in K_\gamma$, and that $\tau_\beta(\cM) = \tau_\beta(\cN)$. Since projection preserves the underlying tree, $\cN$ and $\cM$ must have the same rank function. Let $a \in M$. If $\rank[\cN](a) \in \w_1$ then we have $\rank[\cN](a) < \w \cdot \beta$, and so $\labeling[\cN](a) = \rank[\cN](a) = \labeling[\cM](a)$. But if $\rank[\cN](a) = \infty$ then we must have $\labeling[\cN](a) = \infty$ since $\rank[\cN] \leq \labeling[\cN]$. Therefore $\cM = \cN$ and $\cM$ is maximal. \end{proof} \begin{proposition} \label{Full geometric trees are nice} Every full geometric tree is eventually determined with respect to $\mbf{K}$. \end{proposition} \begin{proof} Suppose $\cM$ is a full geometric tree and $\gamma = \min \{\beta \st \range(\rank[\cM]) \subseteq \w \cdot \beta \cup \{\infty\}\}$. Let $\cM^* \in K_\gamma$ be the labeled geometric tree whose labelings are true and where $\cM^*$ is a lift of $\cM$. Now suppose, towards a contradiction, that $\zeta > \gamma$, that $\cM^\dagger \in K_\zeta$, and that $\cM^\dagger$ is a lift of $\cM$. Then $\cM^\dagger$ must have $\w \cdot \zeta$-true labels and so $\cM^\dagger = \cM^*$. But $K_\gamma \cap K_\zeta = \emptyset$, yielding the contradiction. Now let $\aa \subseteq \cM$ be any closed tuple and let $Q_\aa$ be its invariant in $\cM^*$, which captures the ranks of its elements. Then $\cM^* \models Q_\aa(\aa)$ and the second condition in \cref{Nice tuples definition} holds vacuously. Therefore $\aa$ is eventually determined. \end{proof} Putting this all together, we have the following theorem. \begin{theorem} $\mbf{K}$ is a Knight system that witnesses that $\Phi$, the collection of full geometric trees, is a Knight class. Hence $\Phi$ has precisely $\aleph_1$ many models up to isomorphism and no perfect set of non-isomorphic models. \end{theorem} \begin{proof} The fact that $\mbf{K}$ is a weak Knight system for $\Phi$ is immediate. It is also immediate that if $\zeta = \<(T, \leq), \mu\>$ then $Q_\zeta$ is realized in any truly labeled full tree $\cM$ with $\range(\mu) \subseteq \range(\rank[\cM])$ and where the label of the root of $\cM$ agrees with that of the root of $\zeta$. Hence all invariants are realized in some model in $K$. The fact that $\mbf{K}$ has only countably many maximal models of any given rank follows from \cref{Maximal models in labeled geometric trees} and the fact that all ranks of maximal models in $K_\beta$ are contained in $\w \cdot \beta \cup \{\infty\}$. The fact that all models in $\Phi$ have maximal lifts also follows from \cref{Maximal models in labeled geometric trees}. Finally the fact that all models in $\Phi$ are eventually determined follows from \cref{Full geometric trees are nice}. \end{proof} Hence if there were a sentence of $\Lwow(\Lang_c)$ whose countable models were precisely the full geometric trees, then that sentence would be a Knight sentence and hence a counterexample to Vaught's conjecture. However, by \cite{MR4567359}, no theory of trees can be a counterexample to Vaught's conjecture. Therefore there can be no sentence of $\Lwow(\Lang_c)$ which pins down the countable full geometric trees. %%%% %%%% %%%% %%%% %%%% %%%% %%%% %%%% \section{The Counterexample} \label{Counterexample Section} %%%% %%%% %%%% %%%% %%%% %%%% %%%% %%%% We now turn our attention to the counterexample. We will present it in three subsections. First, in \cref{Plans and Templates Subsection}, we will introduce the basic types of objects the counterexample is built from. This will culminate in the notion of a \emph{template system}. Then, in \cref{Knight System of Counterexample Subsection}, we will show how we can build a weak Knight system, along with a corresponding sentence of $\Lwow$ from a template system. Finally, in \cref{Legal Templates Subsection}, we will introduce the legal template system whose corresponding weak Knight system is an actual Knight system. This will then give us a counterexample to Vaught's conjecture. %%%% %%%% %%%% %%%% %%%% %%%% \subsection{Plans and Templates} \label{Plans and Templates Subsection} %%%% %%%% %%%% %%%% %%%% %%%% We begin by introducing the background geometry we will want our structures to have. \begin{definition} A \defn{plan} on a non-empty set $A$ is a finitary convex geometry $\cP \subseteq \PowersetFinite(A)$ in which every closed set of size at least $2$ has precisely two extreme points. In other words: $\emptyset \in \cP$, we have $\bigcup \cP = A$, the geometry $\cP$ is closed under intersections, every finite set is contained in some closed set, and its closure operator $\cl_{\cP}$ satisfies \begin{itemize} \item (Convexity) $(\forall B \in \cP)(\forall x, y \in A \setminus B)\, (x \neq y) \And \bigl(x \in \cl_{\cP}(B \cup \{y\})\bigr) \rightarrow \bigl(y \not \in \cl_{\cP}(B \cup \{x\})\bigr)$, and \item (Extreme Points) $(\forall B \in \cP, |B| \geq 2)\, |\{ b \in B \st B \setminus \{b\} \in \cP\}| = 2$. \end{itemize} \end{definition} \begin{definition} Suppose $\cP$ is a plan on $A$. A \defn{graded face} for $\cP$ is a pair $(B, j)$ such that $B \in \cP$ and $1 \leq j \leq |B|$. We let $\GradedFace[\cP]$ be the collection of graded faces for $\cP$. If $(B, j)$ is a graded face, we call $B$ the \defn{scope} and $j$ the \defn{grade}. We let $s_{\cP}\:\GradedFace[\cP] \to \cP$ be the map which takes a graded face and returns its scope and we let $g_{\cP}\: \GradedFace[\cP] \to \w$ be the map which takes a graded face and returns its grade. If $(B_0, j_0), (B_1, j_1) \in \GradedFace[\cP]$ then we say $(B_0, j_0) \leq (B_1, j_1)$ if $B_0 \subseteq B_1$ and $j_0 \leq j_1$. \end{definition} We now introduce the combinatorial objects associated to a plan that will be used as components of invariants. \begin{definition} A \defn{frame} on a plan $\cP$ is a map $c\:D \to \GradedFace[\cP]$. We call the elements of $D$ the \defn{cells} of the frame and define the scope of a cell $d$ to be $s_{\cP}(c(d))$ and the grade of a cell $d$ to be $g_{\cP}(c(d))$. We will abuse notation and write $s_{\cP}(d)$ for $s_{\cP}(c(d))$ and $g_{\cP}(d)$ for $g_{\cP}(c(d))$. If $U \in \GradedFace[\cP]$ we let $D \downarrow U = \{d \in D \st (s(d), g(d)) \leq U\}$. For $d \in D$ we let $D \downarrow d = D \downarrow c(d)$. \end{definition} Note that the cells of a frame have no structure other than that which is given via the map into the graded faces. \begin{definition} Suppose $c$ is a frame with cells $D$. A \defn{label} of $c$ is a map $\ell\: D \to \OrdLabels$. A \defn{local label} at $d \in D$ is a map $\ell_d\: D \downarrow d \to \OrdLabels$. A \defn{row system} for $c$ is a collection $\Sigma = (\ell_d)_{d \in D}$ such that for all $d \in D$, the label $\ell_d$ is a local label at $d$ with $\range(\ell_d) \subseteq \{-\infty\} \cup \w^2$. \end{definition} We are finally ready to define the type of objects which will make up our invariants. \begin{definition} A \defn{template} for $\cP$ is a triple $t = (c, \Sigma, p)$ where $c$ is a frame for $\cP$, where $\Sigma = (\ell_d)_{d \in D}$ is a row system for $c$, and where $p$ is a label for $c$. We define the \defn{range} of the template $t$ to be $\range(t) = \range(p)$. For $\alpha \in \w_1$ we say that $t$ is an \defn{$\alpha$-template} if $\range(t) \subseteq \{-\infty\} \cup \alpha \cup \{\infty\}$. \end{definition} There are two types of equivalence of templates which will be important: isomorphism and renaming. \begin{definition} Suppose $\iota\:D_0 \to D_1$ is a bijection. \begin{itemize} \item Suppose $c\:D_1 \to \GradedFace[\cP]$ is a frame. We say that $c \circ \iota$ is the \defn{renaming of $c$ by $\iota$}. \item Suppose $\ell: D_1 \to \OrdLabels$ is a label. We say that $\ell \circ \iota$ is a \defn{renaming of $\ell$ by $\iota$}. \item Suppose $\Sigma = (\ell_d)_{d \in D_1}$ is a row system. We define $(\ell_{\iota(d)} \circ \iota\rest[D_0 \downarrow d])_{d \in D_0}$ to be a \defn{renaming of $\Sigma$ by $\iota$}. \item Suppose $t = (c, \Sigma, p)$ is a template and $c'$, $\Sigma'$ are the renamings by $\iota$ of $c$ and $\Sigma$ respectively. We call $(c', \Sigma', p \circ \iota)$ the \defn{renaming of $t$ by $\iota$}. \end{itemize} For templates $t_0, t_1$, we write $t_0 \RenameEq t_1$ when $t_1$ is a renaming of $t_0$ by some map. \end{definition} As the cells are intended to have no internal structure, the specific sets representing cells are not relevant for the notion of a template, and we think of renamings of templates as being ``the same''. \begin{definition} Suppose $i\:A \to A^*$ is a bijection and $\cP^* = \{i[B] \st B \in \cP\}$. \begin{itemize} \item We say that $i$ is an \defn{isomorphism from $(A, \cP)$ to $(A^*, \cP^*)$}. \item Suppose $c\:D \to \GradedFace[\cP]$ and $c^*\:D \to \GradedFace[\cP^*]$ are frames. We say that $i$ is an \defn{isomorphism from $c$ to $c^*$} if $c^* = \hat{\imath} \circ c$ where $\hat{\imath}\:\GradedFace[\cP] \to \GradedFace[\cP^*]$ is the map that takes $(B, j)$ to $(i[B], j)$. \item Suppose $t = (c, \Sigma, p)$ and $t^* = (c^*, \Sigma, p)$ are templates. We say that $i$ is an \defn{isomorphism from $t$ to $t^*$} if it is an isomorphism from $c$ to $c^*$. \end{itemize} \end{definition} Note that isomorphisms only deal with reindexing of the underlying set of the plan, not with renaming the cells. We now define two different ways we can restrict a template. \begin{definition} Suppose $\cP$ is a plan on $A$ with $\emptyset \neq A_0 \subseteq A$ and suppose $A_0$ is closed, i.e., $A_0 \in \cP$. \begin{itemize} \item We define $\cP \rest[A_0] = \{X \in \cP \st X \subseteq A_0\}$. We call $\cP\rest[A_0]$ the \defn{restriction} of $\cP$ to $A_0$. \item Suppose $c\:D \to \GradedFace[\cP]$ is a frame. We define $D_0 = D\rest[A_0] = \{d\in D\st s_{\cP}(d) \subseteq A_0\}$ and $c\rest[A_0]\:D_0 \to \GradedFace[{\cP\rest[A_0]}]$ to be the map where $c\rest[A_0] = c\rest[D_0]$. \item Suppose $\ell\: D \to \OrdLabels$ is a label. We let $\ell\rest[A_0] = \ell\rest[D_0]$. For $d \in D_0$, if $\ell_d$ is a local label we let $\ell_d \rest[A_0] = \ell_d \rest[D_0 \downarrow d]$. \item Suppose $\Sigma = (\ell_d)_{d \in D}$ is a row system. We define $\Sigma\rest[A_0] = (\ell_d\rest[A_0])_{d \in D_0}$. \item Suppose $t = (c, \Sigma, p)$ is a template. We define $t\rest[A_0] = (c\rest[A_0], \Sigma\rest[A_0], p\rest[A_0])$. \item Suppose $t$ is a template on $A_t$. We say that a template $u$ \defn{extends} $t$ if $A_t$ is closed in the underlying plan of $u$ and $u\rest[A_t] = t$. \end{itemize} \end{definition} Note that the ordering between graded faces does not change when the plan is restricted. Specifically, if $A_0 \subseteq A$ is closed and $(B_0, j_0), (B_1, j_1) \in \GradedFace[\cP] \cap \GradedFace[{\cP\rest[A_0]}]$, then whether or not $(B_0, j_0)$ is less than $(B_1, j_1)$ does not depend on whether they are considered as elements of $\GradedFace[\cP]$ or $\GradedFace[\cP\rest[A_0]]$. We now turn to the notion of a $\beta$-truncation. \begin{definition} We extend the $\beta$-truncation function $\trunc[\beta]$ from \cref{beta-truncation function} so that $\trunc[\beta](-\infty) = -\infty$. \end{definition} \begin{definition} Suppose $\beta \in \w_1$. We define the \defn{$\beta$-truncation} of a template $t=(c, \Sigma, p)$ to be $(c, \Sigma, \trunc[\beta] \circ p)$. We denote it by $\trunc[\beta](t)$. \end{definition} Just as in the case of full trees, the $\beta$-truncation of a template takes all values of the label which are $\geq \beta$ and replaces them with $\infty$. \begin{definition} \label{Template system definition} Suppose $T$ is a collection of templates which satisfy the following whenever $t = (c, \Sigma, p) \in T$ with underlying finite set $A$. \begin{itemize} \item[(a)] Both the underlying set of $t$ and the cells of $t$ are finite subsets of $\w$. \item[(b)] If $i\:A \to B$ is a bijection with $B \subseteq \w$ then $(\hat{\imath} \circ c, \Sigma, p) \in T$. \item[(c)] If $\emptyset \neq A_0 \subseteq A$ is closed then $t\rest[A_0] \in T$. \item[(d)] For all $\beta \in \w_1$, we have $\trunc[\w + \w \cdot \beta](t) \in T$. \item[(e)] For all $\beta \in \w_1$, there is a $t_\beta \in T$ such that $\trunc[\w + \w \cdot \beta](t_\beta) \neq t_\beta$. \item[(f)] For all $n \in \w$, there is a $t_n\in T$ whose underlying set has size at least $n$. \item[(g)] For every $\beta \in \w_1$, letting $\lambda = \w + \w \cdot \beta$, every $\delta < \lambda$, and all templates $t,u \in T$, if there is a template $u'$ with $u' \RenameEq u$ such that $u'$ extends $\trunc[\lambda](t)$, then there are a template $v \in T$ on the same underlying set as $u$ and a template $v'$ with $v' \RenameEq v$ such that $v'$ extends $t$ and $\trunc[\delta](v) \RenameEq \trunc[\delta](u)$. \end{itemize} We say that $T^*$ is a \defn{template system} if the following hold. \begin{itemize} \item $T^* \subseteq T$. \item If $t \in T^*$ then the underlying set of $t$ and the cells of $t$ are initial segments of $\w$. \item If $t \in T$ has underlying set $[n]$ then there is some $t^* \in T^*$ which is a renaming of $t$. \item If $t, t' \in T^*$ and $t \RenameEq t'$ then $t = t'$. \end{itemize} \end{definition} In \cref{Template system definition}, condition (a) tells us that the underlying set as well as the cells of anything in $T$ are finite subsets of $\w$. In this way, we are able to bound the size of the collection $T$. Condition (b) tells us that $T$ is closed under isomorphisms of templates and conditions (c) and (d) tell us that $T$ is closed under the restriction to smaller sets as well as appropriate truncation. Conditions (e) and (f) tell us that there are \emph{enough} templates in $T$ in the sense that there are arbitrarily \emph{complex} templates and templates whose underlying set is arbitrarily large. Condition (g) tells us that there are enough templates to allow the density axioms to function the way we would like. There is one challenge with regarding classes that satisfy conditions (a) -- (g) as the invariants, and that is the fact that information can be encoded in both the structure of the specific underlying sets and cells chosen. To get around this, we only consider templates whose underlying set and cells are each initial segments of $\w$, and we also only allow one template per $\RenameEq$-class. %%%% %%%% %%%% %%%% %%%% %%%% \subsection{Knight Systems} \label{Knight System of Counterexample Subsection} %%%% %%%% %%%% %%%% %%%% %%%% We now show how templates can be used as invariants and how to use a template system to build a weak Knight system. \begin{definition} Suppose $\Lang_a = \{P_n\}_{n \geq 1}$ where each $P_n$ has arity $n$. We say that an $\Lang_a$-structure $\cM$ is a \defn{plan} if $\cM \models \ThGeo[\Lang_a]$ and $\{\emptyset\} \cup \bigcup_{n \geq 1} \bigl\{\{a_i\}_{i \in [n]} \st \cM \models P_n(a_0, \dots, a_{n-1})\bigr\}$ is a plan. \end{definition} We now define the theory describing those geometries which are plans. \begin{definition} \label{Theory describing plans} Let $\ThPlan\subseteq \Lwow(\Lang_a)$ consist of the following sentences. \begin{itemize} \item $\ThGeo[\Lang_a]$. \item (Singletons) $(\forall x)\, P_1(x)$. \item (Convexity) \begin{align*} (\forall x_0, \dots, x_{n-1})& (\forall y, z)\, \Bigl[P_n(x_0, \dots, x_{n-1}) \And (y \neq z) \And \bigwedge_{i \in [n]} \bigl[(x_i \neq y) \And (x_i \neq z)\bigr]\Bigr]\\ % & \rightarrow \bigl[y \in \cl(\{x_i\}_{i \in [n]} \cup \{z\}) \rightarrow z \not \in \cl(\{x_i\}_{i \in [n]} \cup \{y\})\bigr], \end{align*} where $a \in \cl(\{b_i\}_{i \in [n]})$ is the infinitary formula which says that there is a finite set $\{e_i\}_{i \in [m]}$ such that $\{b_i\}_{i \in [n]} \cup \{a\} \subseteq \{e_i\}_{i \in [m]}$, that $P_m(e_0, \dots, e_{m-1})$ holds, and that for any $\{i_j\}_{j \in [k]}$ if $P_k(e_{i_0}, \dots, e_{i_{k-1}})$ and $b_r$ is among $\{e_{i_j}\}_{j \in [k]}$ for each $r \in [n]$ then $a$ is among $\{e_{i_j}\}_{j \in [k]}$. \item (Extreme Points) For all $n\geq 3$, the following two sentences hold: \begin{align*} (\forall & x_0, \dots, x_{n-1})\, P_n(x_0, \dots, x_{n-1}) \\ % &\rightarrow \bigvee_{i < j \in [n]} \bigl[P_{n-1}(x_0, \dots, x_{i-1}, x_{i+1}, \dots, x_{n-1}) \And P_{n-1}(x_0, \dots, x_{j-1}, x_{j+1}, \dots, x_{n-1})\bigr]; \end{align*} % \begin{align*} (\forall & x_0, \dots, x_{n-1})\, P_n(x_0, \dots, x_{n-1}) \\ % & \rightarrow \neg \bigl[P_{n-1}(x_1, \dots, x_{n-1}) \And P_{n-1}(x_0, x_2, \dots, x_{n-1}) \And P_{n-1}(x_0, x_1, x_3, \dots, x_{n-1})\bigr]. \end{align*} \end{itemize} \end{definition} In \cref{Theory describing plans}, the (Singletons) sentence ensures that all singletons are closed, the (Convexity) sentences ensure that the geometry is convex and the (Extreme Points) sentences ensure that every closed set of size at least 2 has precisely 2 extreme points. The following is then immediate. \begin{lemma} An $\Lang_a$-structure $\cM$ is a plan if and only if $\cM \models \ThPlan$. \end{lemma} We now introduce the languages $\Lang_b$ and the corresponding invariant diagram and invariant system. \begin{definition} Suppose $T$ is a template system. We define $\Lang_b[T] = \{Q_t\}_{t \in T}$ where $Q_t$ has arity $n$ when the underlying set of $t$ is $[n]$. \end{definition} We now can introduce the invariant system. Note that we are choosing to have the projections $\tau_\beta$ project down to templates with labels in $\OrdLabels[\w + \w \cdot \beta]$. See the discussion at the end of \cref{Knight System: Attempt 1 subsection} for motivation for why this is necessary. \begin{definition} Suppose $\beta \in \w_1$. For each $t \in T$, we let $\tau_\beta(Q_t) = Q_{t^*}$, where $t^*$ is the unique element of $T$ satisfying $t^* \RenameEq \trunc[\w + \w \cdot \beta](t)$. We let $\mbf{\tau} = \<\tau_\beta\>_{\beta \in \w_1}$. \end{definition} Note that as $\trunc[\w + \w \cdot \alpha] \circ \trunc[\w + \w \cdot \beta] = \trunc[\w + \w \cdot \beta] \circ \trunc[\w + \w \cdot \alpha] = \trunc[\w + \w \cdot \alpha]$ whenever $\alpha \leq \beta$, we have that $\mbf{\tau}$ is an invariant system. We now introduce our (countable) language $\Lang_c[T]$. For technical reasons having to do with the abstract machinery of Knight systems we want $\Lang_b[T]$ and $\Lang_c[T]$ to be disjoint. However, the intuition is that the base language should be those invariants which have rank $0$. \begin{definition} We let $\Lang_c[T] = \Lang_a \cup \{R_t \st t \in T \text{ and }\tau_0(Q_t) = Q_t\}$, where each $R_t$ is a new relation symbol of the same arity as $Q_t$. \end{definition} We are now ready to define our invariant diagram. \begin{definition} Let $\IDtemp[T]$ be the invariant diagram such that whenever $t = (c, \Sigma, p)$ is a template with underlying set $[n]$ then $(Q_t(x_0, \dots, x_{n-1}), R(x_{i_0}, \dots, x_{i_{k-1}})) \in \IDtemp[T]$ precisely when one of the following holds. \begin{itemize} \item $R$ is $P_k$, $i_0, \dots, i_{k-1}$ are distinct elements and $\{i_j\}_{j \in [k]}$ is closed in the geometry of $t$. \item $R$ is $Q_{t^*}$ where the underlying set of $t^*$ is $[k]$ and the map $i_j \mapsto j$ is an isomorphism between $t^\dagger$ and $t^*$ where $t^\dagger \RenameEq t \rest[{\{i_j\}_{j \in[k]}}]$. \item $R$ is $R_{t^-}$ where $(Q_t(x_0, \dots, x_{n-1}), Q_{t^+}(x_{i_0}, \dots, x_{i_{k-1}})) \in \IDtemp[T]$ and $t^- \RenameEq \trunc[\w](t^+)$. \end{itemize} We call a structure compatible with $\IDtemp[T]$ a \defn{$T$-structure}. \end{definition} The following is immediate. \begin{lemma} $\IDtemp[T]$ and $\mbf{\tau}$ are compatible. \end{lemma} Before we introduce our weak Knight system, we will need a more fine-grained notion of density than what will be guaranteed by the invariant system. This is analogous to how, in the case of trees, we wanted trees in $K_\beta$ to have density at all levels below $\w \cdot \beta$, not just the limit levels that would be forced by the conditions on being in a weak Knight system. \begin{definition} We let $D[\beta]$ be the collection of axioms \[ (\forall \xx)\, \bigg(Q_t(\xx) \rightarrow (\exists \yy)\bigvee_{\substack{s \in T\\ \trunc[\beta](s) \RenameEq \trunc[\beta](u)}} Q_s(\xx\yy)\bigg) \] for each $(Q_u(\xx\yy), Q_t(\xx)) \in \IDtemp[T]$ with $u, t \in T$. \end{definition} We now define the weak Knight system associated to $T$. \begin{definition} For $\beta \in \w_1$, let $K_\beta[T]$ be the collection of $(\Lang_b[T] \cup \Lang_c[T])$-structures $\cM$ such that \begin{itemize} \item $\cM$ is compatible with $\IDtemp[T]$, \item $\tau_\beta(\cM) = \cM$, and \item $\cM \models D[\alpha]$ for all $\alpha < \w + \w \cdot \beta$. \end{itemize} We let $\mbf{K}[T] = \_{\beta \in \w_1}$, let $K[T] = \bigcup_{\beta \in \w_1} K_\beta[T]$ and let $K_{-\infty}[T] = \{\cM\rest[{\Lang_c[T]}] \st \cM \in K[T]\}$. \end{definition} We now give the countable theory of $\Lwow(\Lang_c)$ which captures the base of $\mbf{K}[T]$. \begin{definition} \label{Knight sentence from template system} Let $\sigma[T] \in \Lwow(\Lang_c)$ be the (countable) conjunction of the following sentences where $\cR[T] = \Lang_c[T] \setminus \Lang_a$. \begin{itemize} \item[(a)] $\bigwedge \ThPlan$. \item[(b)] For all $n \geq 1$, \begin{itemize} \item for all $P_n \in \Lang_a^n$, \[ (\forall x_0, \dots, x_{n-1})\, P_n(x_0, \dots, x_{n-1}) \leftrightarrow \bigvee_{R_n \in \cR[T]^n} R_n(x_0, \dots, x_{n-1}); \] \item for all distinct $R_n, R_n'\in \cR[T]^n$, \[ (\forall x_0, \dots, x_{n-1})\, R_n(x_0, \dots, x_{n-1}) \rightarrow \neg R_n'(x_0, \dots, x_{n-1}); \] \item for any $k\geq 1$, any $R \in \cR[T]^n$, any $S \in \Lang_c[T]^k$, and any sequence $\_{j \in [k]} \subseteq [n]$, \begin{align*} (\forall x_0,\dots, x_{n-1})(\forall y_0, \dots, y_{n-1})\, [R(x_0, \dots, x_{n-1}) & \And R(y_0, \dots, y_{n-1})] \\ % & \rightarrow [S(x_{i_0}, \dots, x_{i_{k-1}}) \leftrightarrow S(y_{i_0}, \dots, y_{i_{k-1}})]. \end{align*} \end{itemize} \item[(c)] If $(Q_t(\xx), \psi(\yy)) \in \IDtemp[T]$, where $R_t \in \cR[T]$ and $\psi(\yy)$ is an atomic or negated atomic $\Lang_c[T]$-formula, \[ (\forall \xx)\, \bigl[R_t(\xx) \rightarrow \psi(\yy)\bigr]. \] \item[(d)] For all $n \in \w$, for all $t, t^* \in T$, if $R_t\in \Lang_c[T]$ and $R_{t^*} \in \cR[T]$ with $(Q_t(\xx\yy), Q_{t^*}(\xx)) \in \IDtemp[T]$, then \[ (\forall \xx)\, \Bigg[ R_{t^*}(\xx) \rightarrow (\exists \yy)\bigvee_{\substack{{s\in T}\\ R_{s} \in \Lang_c[T]\\ \trunc[n](s) \RenameEq \trunc[n](t)}} R_s(\xx\yy) \Bigg]. \] \end{itemize} \end{definition} The intuition is that the relation symbols in $\Lang_c[T] \setminus \Lang_a$ are meant to capture the relation symbols in $\Lang_b[T]$ of rank $0$. As such, \cref{Knight sentence from template system} (a) describes the geometry, \cref{Knight sentence from template system} (b) and (c) provide the remaining conditions for structured geometry and enforce compatibility with $\IDtemp[T]$, and \cref{Knight sentence from template system} (d) is equivalent to density. We then have the following. \begin{theorem} \label{K[T] is weak Knight system over sigma[T]} $\mbf{K}[T]$ is a weak Knight system whose class of $\Lang_c$-reducts is the collection of models of $\sigma[T]$. \end{theorem} \begin{proof} All the conditions of $\mbf{K}[T]$ being a weak Knight system are immediately satisfied, except for the following claim. \begin{claim} For any $\alpha < \beta$ and $\cM \in K_\beta$, $\tau_\alpha(\cM) \in K_\alpha$. \end{claim} \begin{proof} Write $\lambda_\alpha = \w + \w \cdot \alpha$. Let $\cN = \tau_\alpha(\cM)$. Idempotence of $\tau_\alpha$ gives $\tau_\alpha(\cN) = \cN$. Further, as $\cM$ is compatible with $\IDtemp[T]$ and compatibility with $\IDtemp[T]$ is preserved by projection, we have that $\cN$ is compatible with $\IDtemp[T]$. It remains to show $\cN \models D[\delta]$ for all $\delta < \lambda_\alpha$. Fix such a $\delta$ and suppose $\cN \models Q_s(\aa)$ and $u$ is a template extending $s$. We must find an extension of $\aa$ in $\cN$ whose template agrees with $u$ after truncating to $\delta$. Let $t$ be the template such that $\cM \models Q_t(\aa)$. We then have $s \RenameEq \trunc[\lambda_\alpha](t)$. By \cref{Template system definition} (g), there is a template $v$ on the same underlying set as $u$ whose restriction to the underlying set of $t$ is a renaming of $t$ and such that $\trunc[\delta](v) \RenameEq \trunc[\delta](u)$. Since $\delta < \lambda_\alpha < \w + \w \cdot \beta$, we have $\cM \models D[\delta]$. Applying this to the extension $v$ of $t$ we get a tuple $\bb \subseteq \cM$ and template $w$ such that $\cM \models Q_w(\aa\bb)$ and $\trunc[\delta](w) \RenameEq \trunc[\delta](v)$. But in $\cN$, the tuple $\aa\bb$ realizes the invariant associated to $\trunc[\lambda_\alpha](w)$. So $\trunc[\delta](\trunc[\lambda_\alpha](w)) = \trunc[\delta](w) \RenameEq \trunc[\delta](u)$. This is the required witness to $D[\delta]$. As $\delta$ was arbitrary less than $\w + \w \cdot \alpha$, this implies that $\tau_\alpha(\cM) \in K_\alpha$. \end{proof} Therefore $\mbf{K}$ is a weak Knight system and it suffices to show that its base is the collection of models of $\sigma[T]$, i.e., $\{\cM \st \cM \models \sigma[T]\} = \{\cM\rest[{\Lang_c[T]}] \st \cM \in K_0\}$. But this follows from the fact that for every invariant $Q_t$ fixed by $\tau_0$ there is an equivalent relation symbol $R_t \in \Lang_c[T]$ and up to that equivalence the models of $\sigma[T]$ are precisely the structures in $K_0$. \end{proof} Putting this all together we have the following. \begin{theorem} If $\mbf{K}[T]$ is a Knight system then $\sigma[T]$ is a Knight sentence and hence a counterexample to Vaught's conjecture for $\Lwow$. \end{theorem} \begin{proof} This is immediate from \cref{Knight sentences are counterexamples to Vaught's conjecture,K[T] is weak Knight system over sigma[T]}. \end{proof} %%%% %%%% %%%% %%%% %%%% %%%% \subsection{Legal Templates} \label{Legal Templates Subsection} %%%% %%%% %%%% %%%% %%%% %%%% We have now reduced the problem of finding a counterexample to Vaught's conjecture for $\Lwow$ to the problem of finding a template system such that $\mbf{K}[T]$ is a Knight system. Finding such a template system required a great deal of work using coding agents to interact with LLMs, Lean, and SMT and Horn clause solvers. The first example we found was substantially more complicated; here we present a considerably simplified such example. We will need several definitions, the first of which are the ``visibility maps'' from $\OrdLabels$ to $\OrdLabels$. \begin{definition} Let $i, k \in \w$. We let $\visible[i]\:\OrdLabels \to \OrdLabels$ be the map where \begin{itemize} \item $\visible[i](-\infty) = -\infty$ and $\visible[i](\infty) = \infty$, and \item for $\alpha \in \w_1$ and $n \in \w$, \[ \visible[i](\w \cdot \alpha + n) = \begin{cases} \w \cdot \alpha + i & \text{ if } n < k, \\ \w \cdot \alpha + n & \text{ otherwise.} \end{cases} \] \end{itemize} We say that $x \in \OrdLabels$ is \defn{self-visible at $k$} if $\visible[k](x) = x$. \end{definition} \begin{definition} Suppose $r$ is a frame with cells $D$ and $u, v$ are labelings of $r$. We write $u \Rightarrow v$ if there are functions $f\:\w \to \OrdLabels$ and $h\:\OrdLabels \to \OrdLabels$ which satisfy the following. \begin{itemize} \item $f$ is antitone, i.e., for all $a \leq b \in \w$, $f(a)\geq f(b)$. \item For all $k\in \w$, the value $f(k)$ is self-visible at $k$. \item $h$ is non-decreasing. \item $h(-\infty) = -\infty$. \item For all $i \leq k \in \w$ and $x$ with $h(x) \leq f(k)$, we have \[ h(\visible[i](x)) = \visible[i](h(x)). \] \item For all $d \in D$, we have \[ v(d) = \min \{h(u(d)), f(g(d))\}, \] where $g(d)$ is the grade of $d$. \end{itemize} \end{definition} We now give the defining property of our template system. \begin{definition} Suppose $t = (c, \Sigma, p)$ is a template with $\Sigma = (\ell_d)_{d \in D}$ and $g, s$ are the grade and scope functions. For $U$ a graded face a \defn{local labeling} $r\:D\downarrow U \to \OrdLabels$ is \defn{lawful} with respect to $\Sigma$ if it satisfies the following. \begin{itemize} \item (Orderliness) For all $d \in D\downarrow U$, the value $r(d)$ is self-visible at $g(d)$. \item (Locality) For all $d \in D \downarrow U$, we have $\ell_d \Rightarrow r_d$, where $r_d \colon D \downarrow d \to \OrdLabels$ is defined by $r_d(e)=\min\{r(e),r(d)\}$. \item (Availability) For all $d, e \in D\downarrow U$, if $s(d) \subseteq s(e)$ and $g(d) = g(e)$ then there is an $e' \in D$ with $c(e) = c(e')$ and $r(d) \leq r(e')$. \end{itemize} We define a \defn{lawful labeling} with respect to $\Sigma$ in the obvious analogous way. We say a (local) labeling is lawful with respect to $t$ when it is lawful with respect to $\Sigma$. For $\gamma \in \OrdLabels$ and $q$ a lawful local labeling (with respect to $t$) let \[ B_\gamma(q) = \{r\st r\text{ is lawful and } \min\{r, \gamma\} = \min\{q, \gamma\}\}. \] We say the rows of $\Sigma$ are \defn{bountiful} if for every graded face $U$, lawful local map $q$ with $\dom(q) = D\downarrow U$, $\gamma \in \{-\infty\} \cup \w_1 \cup \{\infty\}$ which is self-visible at $g(U)$ and graded face $V \leq U$ we have \[ \{r \rest[D \downarrow V] \st r \in B_\gamma(q)\} = B_\gamma(q \rest[D \downarrow V]). \] \end{definition} \begin{definition} Suppose $t = (c, \Sigma, p)$ is a template over the plan $(A, \cP)$ with $\Sigma = (\ell_d)_{d \in D}$. We say $t$ is \defn{legal} if it satisfies the following. \begin{itemize} \item $\range(c) = \GradedFace[\cP]$, i.e., every graded face has a cell. \item $p$ is lawful with respect to $\Sigma$. \item For each $d \in D$, $\ell_d$ is lawful. \item The rows of $(\ell_d)_{d \in D}$ are bountiful. \item For each $d$, $\range(\ell_d) \subseteq \{-\infty\} \cup \{\w \cdot n + i \st n \in \w, i \leq g(d) + 1\}$. \end{itemize} \end{definition} We then have the following proposition. \begin{proposition} \label{Legal templates form a template system} There is a template system $L$ such that \begin{itemize} \item all templates in $L$ are finite legal templates, and \item all finite legal templates are isomorphic to renamings of templates in $L$. \end{itemize} \end{proposition} \begin{proof} Let $T$ be the collection of legal templates whose underlying sets and cells are finite subsets of $\w$. It suffices to verify \cref{Template system definition} (a) -- (g) as then we can let $L$ choose one representative of each cell-renaming class on each underlying set $[n]$ with cell set an initial segment of $\w$. First, \cref{Template system definition} (a) -- (c), (e), (f) are straightforward. To see (d) suppose $t = (c, \Sigma,p)$ is legal and let $\lambda = \w + \w \cdot \beta$. We must show $(c, \Sigma, \trunc[\lambda]\circ p)$ is legal. Note $\trunc[\lambda]$ is non-decreasing, preserves minima and commutes with visibility, i.e. $\trunc[\lambda] \circ \visible[i] = \visible[i] \circ\trunc[\lambda]$. Now suppose $u \Rightarrow v$ and $f,h$ witness this fact. Let $f' = \trunc[\lambda]\circ f$ and $h' = \trunc[\lambda]\circ h$. It is then straightforward to check that $f', h'$ witness that $u \Rightarrow \trunc[\lambda] \circ v$. Finally we need to verify that $\trunc[\lambda] \circ p$ is lawful. But each of orderliness, locality, and availability follows straightforwardly from the above. Therefore $\trunc[\lambda](t)$ is legal, proving \cref{Template system definition} (d). To see \cref{Template system definition} (g) suppose $t, u$ are legal templates and some renaming of $u$ extends $\trunc[\lambda](t)$ where $\lambda = \w + \w \cdot \beta$. Since legality is preserved by cell renaming, we may assume without loss of generality that $u$ literally extends $\trunc[\lambda](t)$. Write $A_t \subseteq A_u$ for their underlying sets and let $p_t, p_u$ be the corresponding labelings. We also identify the cells of $t$ with the corresponding cells of $u$. Let $V_t = (A_t, |A_t|)$, $V_u = (A_u, |A_u|)$. Choose $\delta < \lambda$. If $A_u = A_t$ take $v = t$. Otherwise $A_t \subsetneq A_u$. Choose $\gamma$ where $\delta \leq \gamma < \lambda$ and $\gamma$ is self-visible at $|A_u|$. Such a $\gamma$ exists as $\lambda$ is a limit ordinal. Since $u$ extends $\trunc[\lambda](t)$, we have \[ \min\{p_t, \gamma\} = \min\{p_u \rest[D_u\downarrow V_t], \gamma\}, \] where $D_u$ is the set of cells of $u$. Both labelings are lawful with respect to rows restricted to $D_u \downarrow V_t$. Thus $p_t \in B_\gamma(p_u \rest[D_u\downarrow V_t])$. So, by bountifulness, there is an $r \in B_\gamma(p_u)$ such that $r \rest[D_u\downarrow V_t] = p_t$. Let $v = (c_u, \Sigma_u, r)$ (where $u = (c_u, \Sigma_u, p_u)$). Since $r$ is lawful and the frame and rows are those of $u$, $v$ is legal. It extends $t$ and has the same underlying set as $u$. Finally, because $r \in B_\gamma(p_u)$ we have $\min\{r, \gamma\} = \min \{p_u, \gamma\}$. So, because $\delta \leq \gamma$, $\trunc[\delta] \circ r = \trunc[\delta] \circ p_u$. Therefore $\trunc[\delta](v) = \trunc[\delta](u)$ as required. So \cref{Template system definition} (g) holds. \end{proof} Note the collection of legal templates does not itself form a template system, as template systems by design have only a single element out of each cell-renaming class. Between \cref{K[T] is weak Knight system over sigma[T]} and \cref{Legal templates form a template system}, the class of models of $\sigma[L]$ is the base of a weak Knight system $\mbf{K}[L]$. All that is left to show $\sigma[L]$ is a counterexample to Vaught's conjecture is to show that $\mbf{K}[L]$ is in fact a Knight system. This proof, which is substantial, has been formalized. We will now give a rough outline of the approach. Specifically we will mention three propositions without proof and show how to prove from them that $\mbf{K}[L]$ is a Knight system. \begin{definition} Suppose $t \in L$ has underlying set $[n]$. We define a \defn{chart} on $t$ to be a finite structure $\cM$ of size $n$ such that for some enumeration $\{a_i\}_{i \in [n]}$ of $\cM$ we have the following for all $R \in \Lang_b[L]^k \cup \Lang_c[L]^k$ and all $\_{j \in [k]} \subseteq [n]$: \[ \cM \models R(a_{i_0}, \dots, a_{i_{k-1}})\text{ if and only if }\bigl(Q_t(x_0, \dots, x_{n-1}), R(x_{i_0}, \dots, x_{i_{k-1}})\bigr) \in \IDtemp[L]. \] For $\beta \in \w_1$, let $C_\beta[L]$ be the category of charts on $t$ such that $\trunc[\w + \w \cdot \beta](t) = t$, with morphisms the embeddings between them. \end{definition} A chart is then a finite structure determined by the invariant of an enumeration of its whole domain. \begin{proposition} \label{Charts have (HP) (JEP) (AP)} For all $\beta \in \w_1$ the category $C_\beta[L]$ satisfies the following. \begin{itemize} \item (Hereditary Property) If $\cM \in C_\beta[L]$ and $\emptyset \neq M_0 \subseteq M$ with $M_0$ closed then $\cM\rest[M_0] \in C_\beta[L]$. \item (Joint Embedding Property) If $\cM, \cN \in C_\beta[L]$ then there is a $\cR \in C_\beta[L]$ with embeddings $i\:\cM \to \cR$ and $j \: \cN \to \cR$. \item (Amalgamation Property) If $\cM, \cN, \cR \in C_\beta[L]$ with $\cM \subseteq \cN$ and $\cM \subseteq \cR$ then there is a $\cQ \in C_\beta[L]$ and embeddings $i\:\cN \to \cQ$ and $j\:\cR \to \cQ$ such that $j\rest[\cM] = i\rest[\cM]$. \end{itemize} \end{proposition} \begin{lemma} \label{Fraisse limits exist} For each $\beta \in \w_1$ there is then a structure $\cF_\beta \in K_\beta$ satisfying the following. \begin{itemize} \item Every chart in $C_\beta[L]$ embeds into $\cF_\beta$. \item Whenever \begin{itemize} \item $Q_s, Q_t\in \Lang_b[L][\mbf{\tau}, \beta]$, \item $(Q_t(\xx\yy), Q_s(\xx)) \in \IDtemp[L]$, \item $\cF_\beta \models Q_s(\aa)$, \end{itemize} there is a $\bb \subseteq \cF_\beta$ such that $\cF_\beta \models Q_t(\aa\bb)$. \end{itemize} We call $\cF_\beta$ the \defn{$\beta$-\Fraisse\ limit} of $\mbf{K}$. \end{lemma} \begin{proof} Since $C_\beta[L]$ has only countably many isomorphism types the existence of $\cF_\beta$ follows immediately from \cref{Charts have (HP) (JEP) (AP)} and the standard \Fraisse\ construction. The fact that $\cF_\beta \in K_\beta$ follows from the fact that the extension property of $\cF_\beta$ implies $\cF_\beta$ satisfies $D[\delta]$ for all $\delta < \w + \w \cdot \beta$. \end{proof} We now describe three key properties of the lifts of a specific $\Lang_c[L]$-structure. \begin{proposition} \label{Properties of legal template system} For every $\beta \in \w_1$ and every $\cM \models \sigma[L]$ the following hold. \begin{itemize} \item (Boundedness) The set $\{\rank[\mbf{\tau}](\cN) \st \cN \in K\text{ and }\cN \rest[{\Lang_c[L]}] = \cM\}$ is countable. \item (Reconstruction) If $\cN, \cR \in K_\beta$ and $\cN \rest[{\Lang_c[L]}] = \cR\rest[{\Lang_c[L]}] = \cM$ then $\cN = \cR$. \item (Limits) If $\beta$ is a limit ordinal and for all $\alpha < \beta$ there is a $\cN_\alpha \in K_\alpha$ with $\cN_\alpha\rest[{\Lang_c[L]}] = \cM$ then there is a $\cN_\beta \in K_\beta$ such that $\cN_\beta \rest[{\Lang_c[L]}] = \cM$. \end{itemize} \end{proposition} Boundedness tells us that no structure in the base has lifts of arbitrarily large ranks. Reconstruction tells us that lifts of a structure at a given level must be unique. Limits tell us that if $\beta$ is a limit and a structure has lifts of all levels $\alpha < \beta$ then it must have a lift of level $\beta$. It is worth observing that by \cref{Maximal models in labeled geometric trees} all three of these conditions also hold of the collection of full trees and their corresponding Knight system. \begin{proposition} \label{Only countably many maximal structures at each level} For each $\beta$ there are only countably many $(\Lang_b[L] \cup \Lang_c[L])$-structures up to isomorphism that are maximal at $\beta$. \end{proposition} We can now put together these results to get the following. \begin{theorem}[Counterexample to Vaught's Conjecture] \label{Knight sentence from legal template system} The sentence $\sigma[L]$ has $\aleph_1$ many countable models up to isomorphism and has no perfect set of non-isomorphic countable models. In particular, $\sigma[L]$ is a counterexample to Vaught's conjecture for $\Lwow$. \end{theorem} \begin{proof} We already have shown in \cref{K[T] is weak Knight system over sigma[T]} that $\mbf{K}[L]$ is a weak Knight system, so by \cref{Knight classes have omega_1 many models} it suffices to show \cref{Knight system definition} (a) -- (d). First note that \cref{Knight system definition} (b) is exactly \cref{Only countably many maximal structures at each level}. \cref{Knight system definition} (d) follows immediately from \cref{Fraisse limits exist}. \begin{claim} \label{Knight sentence from legal template system: Claim 1} For every $\beta \in \w_1$ and $\cM \in K_\beta$ there is a unique $\cN \in K$ such that $\tau_\beta(\cN) = \cM$ and $\cN$ is maximal. \end{claim} \begin{proof} For each $\cM \in K_{-\infty}$ and $\beta \in \w_1$ define $\cM_\beta$ by induction as follows. \begin{itemize} \item Let $\cM_0 \in K_0$ be such that $\cM_0 \rest[{\Lang_c[L]}] = \cM$. Note that such a $\cM_0$ exists by the definition of a weak Knight system and is unique by \cref{Properties of legal template system} (Reconstruction). \item If $\beta$ is a non-zero limit ordinal and $\cM_i$ has been defined for each $i < \beta$, then by \cref{Properties of legal template system} (Limits) there must be a $\cM_\beta \in K_{\beta}$ such that $\cM_\beta\rest[{\Lang_c[L]}] = \cM$. But by \cref{Properties of legal template system} (Reconstruction) such an $\cM_\beta$ must be unique. \item If $\beta = \alpha +1$ then let $\cM_\beta$ be any element of $K_{\beta}$ such that $\tau_{\alpha}(\cM_\beta) = \cM_\alpha$, if one exists. If one exists, by \cref{Properties of legal template system} (Reconstruction) it must be unique. If none exist stop the induction. \end{itemize} If this process stops, it must stop at some successor stage $\alpha + 1$. In this case, $\cM_\alpha$ is the unique maximal lift of $\cM$ and every lift of $\cM$ is of the form $\tau_\zeta(\cM_\alpha)$ for some $\zeta \leq \alpha$. Suppose this process does not stop. By \cref{Properties of legal template system} (Boundedness), there is a $\gamma \in \w_1$ such that for all $\zeta \geq \gamma$, we have $\rank[\mbf{\tau}](\cM_\zeta) \leq \gamma$, and so $\tau_\gamma(\cM_\zeta) = \cM_\zeta$. But then by \cref{Properties of legal template system} (Reconstruction), we must have $\cM_\gamma = \tau_\gamma(\cM_\zeta) = \cM_\zeta$. Therefore $\cM_\gamma$ is the unique maximal lift of $\cM$ and every lift of $\cM$ is of the form $\tau_\zeta(\cM_\gamma)$ for some $\zeta \leq \gamma$. The claim follows. \end{proof} Note that \cref{Knight system definition} (a) is immediate from \cref{Knight sentence from legal template system: Claim 1}. We also have from \cref{Properties of legal template system} (Reconstruction) and \cref{Knight sentence from legal template system: Claim 1} that for each $\cM \in K_{-\infty}$ there is a unique maximal lift and all other lifts are projections of it. Therefore $\cM$ is eventually determined and \cref{Knight system definition} (c) holds. \end{proof} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \bibliographystyle{amsnomr} \bibliography{bibliography} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \end{document}