Order relations are often fruitfully conceived as being stratified into “levels” in a natural way. The level structure is meant to be compatible with the order, in the sense that as one moves strictly up in the order, one also ascends successively from lower levels to strictly higher levels. With the simple order relation pictured here, for example, we might naturally imagine the least element $0$ on a bottom level, the three middle nodes $a$, $b$, and $c$ on an intermediate level, and node $1$ on a level at the top. With this level structure, as we move up strictly in the order, then we also move up strictly in the hierarchy of levels.
What exactly is a level? Let us be a little more precise. We can depict the intended level structure of our example order more definitely as in the figure here. At the left appears the original order relation, while the yellow highlighted bands organize the nodes into three levels, with node $0$ on the bottom level, nodes $a$, $b$, and $c$ on the middle level, and node $1$ on the top level. This level structure in effect describes a linear preorder relation $\leq$ for which $0\leq a,b,c\leq 1$, with the three intermediate nodes all equivalent with respect to this preorder—they are on the same level.
$\def\<#1>{\left\langle#1\right\rangle}\newcommand{\of}{\subseteq}\newcommand{\set}[1]{{\,{#1}\,}}\renewcommand\emptyset{\varnothing}$Thus, we realize that a level structure of an order relation is simply a linear preorder relation that respects strict instances of the original order, and the levels are simply the equivalence classes of the preorder. More precisely, we define that a linear grading of an order relation $\<A,\preccurlyeq>$ is a linear preorder relation $\leq$ on $A$ for which every strict instance of the original order is also graded strictly by the linear preorder; that is, we require that $$a\prec b\quad\text{ implies }\quad a<b$$ Thus, any strictly lower point in the original order is on a lower level, and we define that objects are on the same level if they are equivalent with respect to the preorder. A linearly graded order is a relational structure $\<A,\preccurlyeq,\leq>$ with two orders on the same domain, the first $\preccurlyeq$ being an order relation on $A$ and the second $\leq$ being a linear preorder relation that grades the first order.
It turns out that there are often far more ways to stratify a given order by levels than one might have expected. For the simple order above, for example, there are thirteen distinct linear grading orders, as shown here.
The conclusion is inescapable that the level concept is not inherent in the order relation itself, for a given order relation may admit a huge variety of different level hierarchies, each of them compatible with the given order.
One should therefore not make the mistake of thinking that if one has an order relation, such as a philosophical reduction notion of some kind or a supervenience relation, then one is automatically entitled to speak of “levels” of the order. One might want to speak of “low-level” phenomena or “high-level” concepts in the order, but one must recognize that the order relation itself does not determine a specific hierarchy of levels, although it does place limitations on the possible stratifications. My point is that there is often surprising flexibility in the nature of the level structure, as the example above shows even in a very simple case, and so what counts as low or high in terms of levels may be much less determined than one expects. In some of the linear gradings above, for example, the node $a$ could be described as high-level, and in others, it is low-level. Therefore if one wants to speak of levels for one’s order, then one must provide further elucidation of the stratification one has in mind.
Meanwhile, we often can provide a natural level structure. In the power set $P(X)$ of a finite set $X$, ordered by the subset relation $A\of B$, for example, we can naturally stratify the relation by the sizes of the set, that is, in terms of the number of elements. Thus, we would place the $\emptyset$ on the bottom level, and the singleton sets $\{a\}$ on the next level, and then the doubletons $\{a,b\}$, and so on. This stratification by cardinality doesn’t quite work when $X$ is infinite, however, since there can be instances of strict inclusion $A\subsetneq B$ where $A$ and $B$ are both infinite and nevertheless equinumerous. Is there a level stratification of the infinite power set order?
Indeed there is, for every order relation admits a grading into levels.
Theorem. Every order relation $\<A,\preccurlyeq>$ can be linearly graded. Indeed, every order relation can be extended to a linear order (not merely a preorder), and so it can be graded into levels with exactly one node on each level.
Proof. Let us begin with the finite case, which we prove by induction. Assume $\preccurlyeq$ is an order relation on a finite set $A$. We seek to find a linear order $\leq$ on $A$ such that $x\preccurlyeq y\implies x\leq y$. If $A$ has at most one element, then we are done immediately, since $\preccurlyeq$ would itself already be linear.
Let us proceed by induction. Assume that every order of size $n$ has a linear grading, and that we have a partial order $\preccurlyeq$ on a set $A$ of size $n+1$. Every finite order has at least one maximal element, so let $a\in A$ be a $\preccurlyeq$-maximal element. If we consider the relation $\preccurlyeq$ on the remaining elements $A\setminus\{a\}$, it is a partial order of size $n$, and thus admits a linear grading order $\leq$. We can now simply place $a$ atop that order, and this will be a linear grading of $\<A,\preccurlyeq>$, because $a$ was maximal, and so making it also greatest in the grading order will cohere with the grading condition.
So by induction, every finite partial order relation can be extended to a linear order.
Now, we consider the general case. Suppose that $\preccurlyeq$ is a partial order relation on a (possibly infinite) set $A$. We construct a theory $T$ in a language with a new relation symbol $\leq$ and constant symbols $\dot a$ for every element $a\in A$. The theory $T$ should assert that $\leq$ is a linear order, that $\dot a\leq \dot b$, whenever it is actually true that $a\preccurlyeq b$ in the original order, and that $\dot a\neq\dot b$ whenever $a\neq b$. So the theory $T$ describes the situation that we want, namely, a linear order that conforms with the original partial order.
The key observation is that every finite subset of the theory will be satisfiable, since such a finite subtheory in effect reduces to the case of finite orders, which we handled above. That is, if we take only finitely many of the axioms of $T$, then it involves a finite partial order on the nodes that are mentioned, and by the finite case of the theorem, this order is refined by a linear order, which provides a model of the subtheory. So every finite subtheory of $T$ is satisfiable, and so by the compactness theorem, $T$ itself also is satisfiable.
Any model of $T$ provides a linear order $\leq$ on the constant symbols $\dot a$, which will be a linear order extending the original order relation, as desired. $\Box$
This material is adapted from my book-in-progress, Topics in Logic, which includes a chapter on relational logic, included an extended section on orders.
$\newcommand\of{\subseteq}\newcommand\N{\mathbb{N}}\newcommand\R{\mathbb{R}}\def\<#1>{\left\langle#1\right\rangle}\newcommand\Z{\mathbb{Z}}\newcommand\Q{\mathbb{Q}}\newcommand\ltomega{{{<}\omega}}\newcommand\unaryminus{-}\newcommand\intersect{\cap}\newcommand\union{\cup}\renewcommand\emptyset{\varnothing}$Let us explore the vast and densely populated expanses of the lattice of all sets of natural numbers—the power set lattice $\<P(\N),\of>$.
We find in this lattice every possible set of natural numbers $A\of\N$, and we consider them with respect to the subset relation $A\of B$. This is a lattice order because the union of two sets $A\union B$ is their least upper bound with respect to inclusion and the intersection $A\intersect B$ is their greatest lower bound. Indeed, it is a distributive lattice in light of $A\intersect(B\union C)=(A\intersect B)\union(A\intersect C)$, but furthermore, as a power set algebra it is a Boolean algebra and every Boolean algebra is a distributive lattice.
The empty set $\emptyset$ is the global least element at the bottom of the lattice, of course, and the whole set $\N$ is the greatest element, at the top. The singletons $\set{n}$ are atoms, one step up from $\emptyset$, while their complements $\N\setminus\set{n}$ are coatoms, one step down from $\N$. One generally conceives of the finite sets as clustering near the Earthly bottom of the lattice, finitely close to $\emptyset$, whereas the cofinite sets soar above, finitely close to the heavenly top. In the vast central regions between, in contrast, we find the infinite-coinfinite sets, including many deeply interesting sets such as the prime numbers, the squares, the square-free numbers, the composites, and uncountably many more.
Question. Which familiar orders can we find as suborders in the power set lattice $P(\N)$ of all sets of natural numbers?
We can easily find a copy of the natural-number order $\<\N,\leq>$ in the power set lattice $P(\N)$, simply by considering the chain of initial segments:
$$\emptyset\of\set{0}\of\set{0,1}\of\set{0,1,2}\of\cdots$$
This sequence climbs like a ladder up the left side of the main figure. Curious readers will notice that although every one of these sets is finite and hence conceived as clinging to Earth, as we had said, nevertheless there is no upper bound for this sequence in the lattice other than the global maximum $\N$—any particular natural number is eventually subsumed. Thus one climbs to the heavens on this ladder, which stretches to the very top of the lattice, while remaining close to Earth all the while on every rung.
The complements of those sets similarly form a infinite descending sequence:
$$\cdots\ \of\ \N\setminus\set{0,1,2}\ \of\ \N\setminus\set{0,1}\ \of\ \N\setminus\set{0}\ \of\ \N$$
This chain of cofinite sets dangles like a knotted rope from the heavens down the right side of the main figure. Every knot on this rope is a cofinite set, which we conceived as very near the top, and yet the rope dangles temptingly down to Earth, for there is no lower bound except $\emptyset$.
Can we find a copy of the discrete integer order $\<\Z,\leq>$ in the power set lattice?
Yes, we can. An example is already visible in the red chain at the right side of main lattice diagram, a sky crane hanging in space. Standing at the set of odd numbers, we can ascend in discrete steps by adding additional even numbers one at a time; or we can descend similarly by removing successive odd numbers. The result is a discrete chain isomorphic to the integer order $\Z$, and it is unbounded except by the extreme points $\emptyset$ and $\N$.
Can we find a dense order, say, a copy of the rational line $\<\Q,\leq>$?
What? You want to find a dense order in the lattice of sets of natural numbers? That might seem impossible, if one thinks of the lattice as having a fundamentally discrete nature. The nearest neighbors of any set, after all, are obtained by adding or removing exactly one element—doing so makes a discrete step up or down with no strictly intermediate set. Does the essentially discrete nature of the lattice suggest that we cannot embed the dense order $\<\Q,\leq>$?
No! The surprising fact is that indeed we can embed the rational line into the power set lattice $P(\N)$. Indeed, much more is true—it turns out that we can embed a copy of any countable order whatsoever into the lattice $P(\N)$. Every countable order that occurs anywhere at all occurs in the lattice of sets of natural numbers.
Theorem. The power set lattice on the natural numbers $P(\N)$ is universal for all countable orders. That is, every order relation on a countable domain is isomorphic to a suborder of $\<P(\N),\of>$.
Proof. Let us prove first that every order relation $\<L,\preccurlyeq>$ is isomorphic to the subset relation $\of$ on a collection of sets. Namely, for each $q\in L$ let $q{\downarrow}$ be the down set of $q$, the set of predecessors of $q$:
$$q{\downarrow}=\set{p\in L\mid p\preccurlyeq q}\of L$$
This is a subset of $L$, and what I claim is that
$$p\preccurlyeq q\quad\text{ if and only if }\quad p{\downarrow}\of q{\downarrow}.$$
This is almost immediate. For the forward implication, if $p\preccurlyeq q$, then any order element below $p$ is also below $q$, and so $p{\downarrow}\of q{\downarrow}$. Conversely, if $p{\downarrow}\of q{\downarrow}$, then since $p\in p{\downarrow}$, we must have $p\in q{\downarrow}$ and hence $p\preccurlyeq q$ as desired. So the map $p\mapsto p{\downarrow}$ is an isomorphism of the original order $\<L,\preccurlyeq>$ with the family of all downsets $\set{p{\downarrow}\mid p\in L}$ using the subset relation.
To complete the proof, we simply observe that the power set lattice $P(L)$ of a countably infinite set $L$ is isomorphic to $P(\N)$, and for finite $L$ it is isomorphic to the power set lattice below a finite set of natural numbers. This is because any bijection of $L$ with a set of natural numbers induces a corresponding isomorphism of the respective subsets. So we may find a copy of $L$ inside $P(\N)$, as desired. $\Box$
One may make the proof more concrete by combining the two steps, like this: if $\<L,\preccurlyeq>$ is any countable order relation, then enumerate the domain set $L=\set{p_0,p_1,p_2,\ldots}$, and for each $p\in L$ let $A_p=\set{n\in\N\mid p_n\preccurlyeq p}\of\N$. This is like the down set of $p$, except we take the indices of the elements instead of the elements themselves. It follows that $p\preccurlyeq q$ if and only if $A_p\of A_q$, and so the mapping $p\mapsto A_p$ is an order isomorphism of $\<L,\preccurlyeq>$ with the collection of $A_p$ sets under $\of$, as desired.
Since the set of rational numbers $\Q$ is countable, it follows as an instance of the universality theorem above that we may find a copy of the rational line $\<\Q,\leq>$ inside the power set lattice $\<P(\N),\of>$. Can you find an elegant explicit presentation of rational line in the powerset lattice? In light of the characterization of $\Q$ as a countable endless dense linear order, it will suffice to find any chain in $P(\N)$ that forms a countable endless dense linear order.
But wait, there is more! We can actually find a copy of the real line $\<\R,\leq>$ in the power set lattice on the naturals! Wait…really? How is that possible? The reals are uncountable, and so this would be an uncountable chain the lattice of sets of natural numbers, but every subset $A\of\N$ is countable, and there are only countably many elements to add to $A$ as you go up. How could there be an uncountable chain in the lattice?
Let me explain.
Theorem. The power set lattice on the natural numbers $\<P(\N),\of>$ has an uncountable chain, and indeed, it has a copy of the real continuum $\<\R,\leq>$.
Proof. We have already observed that there must be a copy of the rational line $\<\Q,\leq>$ in the power set lattice $P(\N)$. In other words, there is a map $q\mapsto A_q\of\N$ such that
$$p<q\quad\text{ if and only if }\quad A_p\of A_q$$
for any rational numbers $p,q\in\Q$.
We may now find our desired copy of the real continuum simply by completing this embedding. Namely, for any real number $r\in\R$, let
$$A_r=\bigcup_{\substack{q\leq r\\ q\in\Q}} A_q.$$
Since the sets $A_q$ for rational numbers $q$ form a chain, it follows easily that $r\leq s$ implies $A_r\of A_s$. And if $r<s$, then $A_r$ will be strictly contained in some $A_q$ for a rational number $q$ strictly between $r<q<s$, and consequently strictly contained in $A_s$. From this, it follows that $r\leq s$ if and only if $A_r\of A_s$, and so we have found a copy of the real number order in the power set lattice, as desired. $\Box$
Let us now round out the surprising events of this section by proving another shocking fact—we can also find an uncountable antichain in the power set lattice $P(\N)$.
Theorem. The power set lattice on the natural numbers $\<P(\N),\of>$ has an uncountable antichain, a collection of continuum many pairwise incomparable sets.
Proof. Consider the tree of finite binary sequences $2^{\ltomega}$. This is the set of all finite binary sequences, ordered by the relation $s\leq t$ that holds when $t$ extends $s$ by possibly adding additional binary digits on the end. This is a countable order relation, and so by universality theorem above we may find a copy of it in the power set lattice $P(\N)$. But let us be a little more specific. We shall label each node $s$ of the tree $2^{\ltomega}$ with a distinct natural number. For any infinite binary path $x\in 2^\omega$ through the tree, let $A_x$ be the set of numbers that appear along the path. Every $A_x$ is infinite, but if $x\neq y$, then $x$ and $y$ will eventually branch away from each other, and consequently $A_x$ and $A_y$ will have only finitely many numbers in common. In particular, neither $A_x$ nor $A_y$ will be a subset of the other, and so we have found an antichain in the powerset lattice. The number of paths through the binary tree is the number of infinite binary sequences, which is the same as the cardinality of the continuum of real numbers, as desired. $\Box$
So the lattice $P(\N)$ offers a rich complexity. But is there also homogeneity to be found here? Place yourself at one of the sets in the central region of the lattice, an infinite coinfinite set. There are various new elements for you to add to make a larger set—you can add just this element, or just that one, or any of infinitely many new atoms for you to add to make a larger set. And you could add any combination of those atoms. Above any coinfinite point in the lattice, therefore, one finds a perfect copy of the whole lattice again. Looking upward from any coinfinite set, it always looks the same.
Theorem. The lattice of all sets of natural numbers is homogenous in several respects.
The lattice of sets above any given coinfinite set $A\of\N$ is isomorphic to the whole power set lattice $P(\N)$.
The lattice of sets below any given infinite set $B\of\N$ is isomorphic to the whole power set lattice $P(\N)$.
For any two infinite coinfinite sets $A,B\of \N$, there is an automorphism of the lattice $P(\N)$ carrying $A$ to $B$.
Proof. Let us prove statement (2) first. Consider any infinite set $B\of\N$ and the sublattice in $P(\N)$ below it, which is precisely the power set lattice $P(B)$ of all subsets of $B$. Since $B$ is an infinite set of natural numbers, there is a bijection $\pi:B\to\N$. We may therefore transform subsets of $B$ to subsets of $\N$ by applying the bijection. Namely, for any $X\of B$ define $\bar\pi(X)=\pi[B]=\set{\pi(b)\mid b\in X}$. Since $\pi$ is injective, we have $X\of Y$ if and only if $\bar\pi(X)\of\bar\pi(Y)$, and the map $\bar\pi$ maps onto $P(\N)$ precisely because $\pi$ is surjective, so every $Z\of\N$ is $Z=\bar\pi(X)$, where $X=\pi^{\unaryminus 1}Z=\set{b\in B\mid \pi(b)\in Z}$. So $\bar\pi$ is an isomorphism of the lattice $P(B)$ with $P(\N)$, as desired.
For statement (1), consider any cofinite set $A\of\N$ and let $A{\uparrow}$ be the part of the power set lattice above $A$, meaning $A\uparrow=\set{X\of\N\mid A\of X}$. Since the complement $B=\N\setminus A$ is infinite, there is a bijection of it with the whole set of natural numbers $\pi:B\to\N$. I claim that the lattice $A{\uparrow}$ is isomorphic with the lattice $P(B)$, which by statement (1) we know is isomorphic to $P(\N)$. To see this, we simply cast $A$ out of any set $X$ containing $A$. What remains is a subset of $B$, and every subset of $B$ will be realized. More specifically, if $A\of X$ we define $\tau(X)=X\setminus A=X\intersect B$, and observe that $X\of Y$ if and only if $\tau(X)\of\tau(Y)$, for the sets already containing $A$. And if $Z\of B$, then $Z=\tau(A\union Z)$. So $\tau$ is an isomorphism of the lattice $A{\uparrow}$ with $P(B)$, which by statement (1) is isomorphic to the whole lattice $P(\N)$, as desired.
Finally, let us fix two infinite coinfinite sets $A,B\of \N$. In particular, $A$ and $B$ are in bijection, as are the complements $\N\setminus A$ and $\N\setminus B$. By combining these two bijections, we get a bijection $\pi:\N\to\N$ of $\N$ with itself that carries $A$ exactly to $B$, that is, for which $\pi[A]=B$. (The reader will have an exercise in my book to give a careful account of this construction.) Because $\pi$ is a bijection of $\N$ with itself, it induces a corresponding automorphism of the lattice, defined by $\bar\pi(X)=\pi[X]$ for $X\of\N$. This is an isomorphism of $P(\N)$ with itself, and $\bar\pi(A)=\pi[A]=B$, as desired. $\Box$
Statement (3) of the theorem shows that any two infinite coinfinite sets, being automorphic images of one another, play the same structural role in the lattice $P(\N)$—they will have all the same lattice-theoretic properties. In light of this theorem, therefore, one should not look for structure theorems concerning particular sets in the lattice. Rather, the structure theory of $P(\N)$ is about the structure as a whole, as with the theorems I have proved above.
This is a selection from my book in progress Topics in Logic. It appears in chapter 3, which is on relational logic, and which includes a section on orders with a subsection specifically on the lattice of all sets of natural numbers, because I find it fascinating.
This will be a talk for the conference Fudan Model Theory and Philosophy of Mathematics, held at Fudan University in Shanghai and online, 21-24 August 2021. My talk will take place on Zoom on 23 August 20:00 Beijing time (1pm BST).
Abstract. Tennenbaum famously proved that there is no computable presentation of a nonstandard model of arithmetic or indeed of any model of set theory. In this talk, I shall discuss the Tennenbaum phenomenon as it arises for computable quotient presentations of models. Quotient presentations offer a philosophically attractive treatment of identity, a realm in which questions of identity are not necessarily computable. Objects in the presentation serve in effect as names for objects in the final quotient structure, names that may represent the same or different items in that structure, but one cannot necessarily tell which. Bakhadyr Khoussainov outlined a sweeping vision for quotient presentations in computable model theory and made several conjectures concerning the Tennenbaum phenomenon. In this talk, I shall discuss joint work with Michał Godziszewski that settles and addresses several of these conjectures.
This is a talk for the Logik Kolloquium at the University of Konstanz, spanning the departments of mathematics, philosophy, linguistics, and computer science. 19 July 2021 on Zoom. 15:15 CEST (2:15 pm BST).
Abstract: An enduring mystery in the foundations of mathematics is the observed phenomenon that our best and strongest mathematical theories seem to be linearly ordered and indeed well-ordered by consistency strength. For any two of the familiar large cardinal hypotheses, one of them generally proves the consistency of the other. Why should this be? Why should it be linear? Some philosophers see the phenomenon as significant for the philosophy of mathematics—it points us toward an ultimate mathematical truth. Meanwhile, the linearity phenomenon is not strictly true as mathematical fact, for we can prove that the hierarchy of consistency strength is actually ill-founded, densely ordered, and nonlinear. The counterexample statements and theories, however, are often dismissed as unnatural. Linearity is thus a phenomenon only for the so-called “naturally occurring” theories. But what counts as natural? Is there a mathematically meaningful account of naturality? In this talk, I shall criticize this notion of naturality, and attempt to undermine the linearity phenomenon by presenting a variety of natural hypotheses that reveal ill-foundedness, density, and incomparability in the hierarchy of consistency strength.
The talk should be generally accessible to university logic students.
Consider this fascinating vision of recursive chess — the etching below was created by Django Pinter, a tutorial student of mine who has just completed his degree in the PPL course here at Oxford, given to me as a parting gift at the conclusion of his studies. Django’s idea was to play chess, but in order for a capture to occur successfully on the board, as here with the black Queen attempting to capture the opposing white knight, the two pieces would themselves sit down for their own game of (recursive) chess. The idea was that the capture would be successful only in the event that the subgame was won. Notice in the image that not only is there a smaller recursive game of chess, but also a still tinier subrecursive game below that (if you inspect closely), while at the same time larger pieces loom in the background, indicating that the main board itself is already several levels deep in the recursion.
The recursive chess idea may seem clear enough initially, and intriguing. But with further reflection, we might wonder how does it work exactly? What precisely is the game of recursive chess? This is my question here.
My goal with this post is to open a discussion about what ultimately should be the precise the rules and operations of recursive chess. I’m not completely sure what the best rule set will be, although I do offer several proposals here. I welcome further proposals, commentary, suggestions, and criticism about how to proceed. Once we settle upon a best or most natural version of the game, then I shall hope perhaps to prove things about it. Will you help me decide what is the game of recursive chess?
Let me describe several natural proposals:
Naïve recursion. Although this seems initially to be a simple, sound proposal, ultimately I find it problematic. The naïve idea is that when one piece wants to capture another in the game at hand, then the two pieces themselves play a game of chess, starting from the usual chess starting position. I would find it natural that the attacking piece should play as white in this game, going first, and if that player wins the subgame, then the capture in the current game is successful. If the subgame is a loss, then the capture is unsuccessful.
There seem, however, to be a variety of ways to handle the losing subgame outcome, and since these will apply with several of the other proposals, let me record them here:
Failed-capture. If the subgame is lost, then the capture in the current game simply does not occur. Both pieces remain on their original squares, and the turn of play passes to the opponent. Notice that this will have serious affects in certain chess situations involving zugswang, a position where a player has no good move — because if one of them is a capture, then the player can aim to play badly in the subgame and thereby legally pass the turn of play to the opponent without having made any move. This situation will in effect cause the subgame players to attempt to lose, rather than win, which seems undesirable.
Failed-capture-with-penalty. If the subgame is lost, then the capture does not occur, but furthermore, the attacking piece is itself lost, removed from the board, and the turn of play passes to the opponent. In effect, under this rule, every attempt at capture is putting the life of the capturing piece at risk, which makes a certain amount of sense from a military point of view. I think perhaps this is a good rule.
Failed-capture-with-retry. If the subgame is lost, then the capture does not occur, but both pieces remain on their original squares, and the attacking player is allowed to proceed with another (different) move. Attempting the same attack from the same board position multiple times is subject to the three-fold repetition rule. This interpretation amounts in effect to the game play searching a large part of the game tree, exploring the possible capturing moves, but with the first successful option fixed as official. It invites manipulation by the opponent, who might play badly against a misguided capture attempt, causing it to be fixed as the official move.
Drawn subgame. A further complication arises from the fact that the subgame can itself be drawn, rather than won. Is this sufficient to cause the penalty or the retry? Or does this count as a failed capture?
As I see it, however, the principal problem with the naïve recursion rule is that it seems to be ill-founded. After all, we can have a game with a capture, which leads to a subgame with a capture, which leads to a deeper subgame with a capture, and so on descending forever. How is the outcome determined in this infinitely descending situation? None of the subgames is ever resolved with a definite conclusion until all of them are, and there seems no coherent way to assign resolutions to them. All infinitely many subgames are simply left hanging mid-play, and indeed mid-move. For this reason, the naïve recursion idea seems ultimately incoherent to me as a game rule.
What we would seem to need instead is a well-founded recursion, one which would ultimately bottom-out in a base case. With such a recursion, every outcome of the game would be well-defined. Such a well-founded recursion would be achieved, for example, if on every subgame there were strictly fewer pieces. Eventually, the subgames would reduce to king versus king, a drawn game, and then the drawn subgame rule would be invoked to whatever affect it cause. But the recursion would definitely terminate. And perhaps most recursions would terminate because the stronger player was ultimately mating in all his attacks, without requiring any invocation of the drawn subgame rule.
We can easily describe several natural subgame positions with one fewer piece. For example, when one piece attacks another, we may naturally consider the positions that would result if we performed the capture, or if we removed the attacking piece; and we might further consider swapping the roles of the players in these positions. Such cases would constitute a well-founded recursion, because the subgame position would have fewer pieces than the main position. In this way, we arrive at several natural recursion rules for recursive chess.
Proof-of-sufficiency recursion. The motivating idea of this recursion rule is that in order for an attack to be successful, the attacking player must prove that it will be sufficient for the attack to be successful. So, when piece A attacks piece B in the game, then a subgame is set up from the position that would result if A were successfully to capture B, and the players proceed in the game in which the attack has occurred. This is the same as proceeding in the main game, under the assumption that the attack was successful. If the attacking player can win this subgame, then it shows in a sense the sufficiency of the attack as a means to win, and so on the proof-of-sufficiency idea, we allow this as a reason for the attack to have been successful.
One might object that this recursion seems at first to amount to just playing chess as usual, since the subgame is the same as the original game with the attack having succeeded. But there is a subtle difference. For a misguided attack, the attacked player can play suboptimally in the subgame, intentionally losing that game, and then play differently in the main game. There is, of course, no obligation that the players respond the same at the higher-level games as in the lower games, and this is all part of their strategic calculation.
Proof-of-necessity recursion. The motivating idea of this recursion rule, in contrast, is that in order for an attack to be successful, the attacking player must prove that it is necessary that the attack take place. When piece A attacks piece B in the main game, then a subgame is set up in which the attack has not succeeded, but instead the attacking piece is lost, but the color sides of the players are swapped. If a black Queen attacks a white knight, for example, then in the subgame position, the queen is removed, and the players proceed from that positions, but with the opposite colors. By winning this subgame, the attacking player is in effect demonstrating that if the attack were to fail, then it would be devastating for them. In other words, they are demonstrating the necessity of the success of the attack.
For the both the proof-of-sufficiency and the proof-of-necessity versions of the recursion, it seems to me that any of the three failed-capture rules would be sensible. And so we have quite a few different interpretations here for what is the game of recursive chess.
What is your proposal? Please let me know in the comments. I am interested to hear any comments or criticism.
Abstract. Zermelo famously proved that second-order ZFC is quasi-categorical—the models of this theory are precisely the rank-initial segments of the set-theoretic universe cut off at an inaccessible cardinal. Which are the fully categorical extensions of this theory? This question gives rise to the notion of categorical large cardinals, and opens the door to several puzzling philosophical issues, such as the conflict between categoricity as a fundamental value in mathematics and reflection principles in set theory. (This is joint work with Robin Solberg, Oxford.)
This is an excerpt from my book-in-progress on diverse elementary topics in logic, from the chapter on model theory. My view is that Boolean-valued models should be elevated to the status of a standard core topic of elementary model theory, adjacent to the ultrapower construction. The theory of Boolean-valued models is both beautiful and accessible, both generalizing and explaining the ultrapower method, while also partaking of deeper philosophical issues concerning multi-valued truth.
Boolean-valued models
Let us extend our familiar model concept from classical predicate logic to the comparatively fantastic realm of multi-valued predicate logic. We seek a multi-valued-truth concept of model, with a domain of individuals of some kind and interpretations for the relations, functions, and constants from a first-order language, but in which the truths of the model are not necessarily black and white, but exhibit their truth values in a given multi-valued logic. Let us focus especially on the case of Boolean-valued models, using a complete Boolean algebra $\newcommand\B{\mathbb{B}}\B$, since this case has been particularly well developed and successful; the set-theoretic method of forcing, for example, amounts to using $\B$-valued models of set theory with carefully chosen complete Boolean algebras $\B$ and has been used impressively to establish a sweeping set-theoretic independence phenomenon, showing that numerous set-theoretic principles such as the axiom of choice and the continuum hypothesis are independent of the other axioms of set theory.
The main idea of Boolean-valued models, however, is applicable with any theory, not just set theory, and there are Boolean-valued graphs, Boolean-valued orders, Boolean-valued groups, rings, and fields. So let us develop a little of this theory, keeping in mind that the basic construction and ideas also often work fruitfully with other multi-valued logics, not just Boolean algebras.
Definition of Boolean-valued models
We defined in an earlier section what it means to be a model in classical first-order predicate logic—one specifies the domain of the model, a set of individuals that will constitute the universe of the model over which all the quantifiers will range, and then provides interpretations on that domain for each relation symbol, function symbol, and constant symbol in the language. For each relation symbol $R$, for example, and any suitable tuple of individuals $a,b$ from the domain, one specifies whether $R(a,b)$ is to hold or fail in the model.
The main idea for defining what it means to be a model in multi-valued predicate logic is to replace these classical yes-or-no atomic truths with multi-valued atomic truth assertions. Specifically, for any Boolean algebra $\B$, a $\B$-valued model $\mathcal{M}$ in the language $\mathcal{L}$ consists of a domain $M$, whose elements are called names, and an assignment of $\B$-valued truth values for all the simple atomic formulas using parameters from that domain:$\newcommand\boolval[1]{[\![#1]\!]}$\begin{eqnarray*} % \nonumber % Remove numbering (before each equation) s=t&\mapsto& \boolval{s=t} \\ R(s_0,\ldots,s_n) &\mapsto& \boolval{R(s_0,\ldots,s_n)} \\ y=f(s_0,\ldots,s_n) &\mapsto& \boolval{y=f(s_0,\ldots,s_n)} \end{eqnarray*} The double-bracketed expressions here $\boolval{\varphi}$ denote an element of the Boolean algebra $\B$—one thinks of $\boolval{\varphi}$ as the $\B$-truth value of $\varphi$ in the model, and the model is defined by specifying these values for the simple atomic formulas.
We shall insist in any Boolean-valued model that the atomic truth values obey the laws of equality: $$\begin{array}{rcl} \boolval{s=s} &=& 1\\ \boolval{s=t} &=& \boolval{t=s}\\ \boolval{s=t}\wedge\boolval{t=u} &\leq& \boolval{s=u}\\ \bigwedge_{i<n}\boolval{s_i=t_i}\wedge\boolval{R(\vec s)} &\leq & \boolval{R(\vec t)}.\end{array}$$And if the language includes functions symbols, then we also insist on the functionality axioms: $$\begin{array}{rcl} \bigwedge_{i<n}\boolval{s_i=t_i}\wedge\boolval{y=f(\vec s)} &\leq& \boolval{y=f(\vec t)}\\ \bigvee_{t\in M}\boolval{t=f(\vec s)} &=& 1\\ \boolval{t_0=f(\vec s)}\wedge\boolval{t_1=f(\vec s)} &\leq& \boolval{t_0=t_1}.\\ \end{array}$$ These requirements assert respectively in the Boolean-valued context that the equality axiom holds for function application, that the function takes on some value, and that the function takes on at most one value. In effect, the Boolean-valued model treatment of functions regards them as as defined by their graph relations, and these functionality axioms ensure that the relation has the features that would be expected of such a graph relation.
In summary, a $\B$-valued model is a domain of names together with $\B$-valued truth assignments for the simple atomic assertions about those names, which obey the equality and functionality axioms.
Boolean-valued equality
The nature of equality in the Boolean-valued setting offers an interesting departure from the usual classical treatment that is worth discussing explicitly. Namely, in classical predicate logic with equality, distinct elements of the domain are taken to represent distinct individuals in the model—the assertion $a=b$ is true in the model only when $a$ and $b$ are identical as elements of the domain. In the Boolean-valued setting, however, we want to relax this in order to allow equality assertions to have an intermediate Boolean value. For this reason, distinct elements of the domain can no longer be taken to represent definitely distinct individuals, since the equality assertion $\boolval{a=b}$ might have some nonzero or intermediate degree of truth. The elements of the domain of a Boolean-valued model are allowed in effect a bit of indecision or indeterminacy about who they are and whether they might be identical. This is why we think of the elements of the domain as names for individuals, rather than as the individuals themselves. Two different names can have an intermediate truth-value possibility of naming the same or different individuals.
Extending to Boolean-valued truth
By definition, every $\B$-valued model provides $\B$-valued truth assertions for the simple atomic formulas. We now extend these Boolean-valued truth assignments to all assertions of the language through the following natural recursion: $$\begin{array}{rcl} \boolval{\varphi\wedge\psi} &=& \boolval{\varphi}\wedge\boolval{\psi}\\ \boolval{\neg\varphi} &=& \neg\boolval{\varphi}\\ \boolval{\exists x\,\varphi(x,\vec s)} &=& \bigvee_{t\in M}\boolval{\varphi(t,\vec s)},\text{ if this supremum exists in }\B\\ \end{array}$$ On the right-hand side, we make the logical calculations in each case using the operations of the Boolean algebra $\B$. In the existential case, the supremum may range over an infinite set of Boolean values, if the domain of the model is infinite, and so this supremum might not be realized as an element of $\B$, if it is not complete. This is precisely why one commonly considers $\B$-valued models especially in the case of a complete Boolean algebra $\B$—the completeness of $\B$ ensures that this supremum exists and so the recursion has a solution.
The reader may check by induction on $\varphi$ that the general equality axiom now has Boolean value one. $$\boolval{\vec s=\vec t\wedge \varphi(\vec s)\implies\varphi(\vec t)}=1$$ The Boolean-valued structure $\mathcal{M}$ is full if for every formula $\varphi(x,\vec x)$ in $\mathcal{L}$ and $\vec s$ in $M$, there is some $t\in M$ such that $\boolval{\exists x\,\varphi(x,\vec s)}=\boolval{\varphi(t,\vec s)}$. That is, a model is full when it is rich enough with names that the Boolean value of every existential statement is realized by a particular witness, reducing the infinitary supremum in the recursive definition to a single largest element.
A simple example
For every natural number $n\geq 3$ let $C_n$ be the graph on $n$ vertices forming an $n$-cycle with edge relation $x\sim y$. So we have a triangle $C_3$, a square $C_4$, a pentagon $C_5$, and so on. Let $\B=P(\set{n\in\newcommand\N{\mathbb{N}}\N\mid n\geq 3})$ be the power set of these indices, which forms a complete Boolean algebra. We define a $\B$-valued graph model $\mathcal{C}$ as follows. We take as names the sequences $a=\langle a_n\rangle_{n\geq 3}$ with $a_n\in C_n$ for every $n$.
We define the equality and $\sim$ edge relations on these names as follows: \begin{eqnarray*} \boolval{a=b}&=&\set{n\mid a_n=b_n} \\ \boolval{a\sim b}&=&\set{n\mid C_n\newcommand\satisfies{\models}\satisfies a_n\sim b_n}. \end{eqnarray*} Thus, two names are equal exactly to extent that they have the same coordinates, and two names are connected by the edge relation $\sim$ exactly to the extent to that this is true on the coordinates. It is now easy to verify the equality axioms, since $a\sim b$ is true to at least the extent that $a’\sim b’$, $a=a’$, and $b=b’$ are true, since if $a_n=a’_n$, $b_n=b’_n$, and $a’_n\sim b’_n$ in $C_n$, then also $a_n\sim b_n$. So this is a $\B$-valued graph model.
So we have a Boolean-valued graph. Is it connected? Does that question make sense? Of course, we don’t have an actual graph here, but only a $\B$-valued graph, and so in principle we only know how to compute the Boolean value of statements that are expressible in the language of graph theory. Since connectivity is not formally expressible, except in the bounded finite cases, this question might not be sensible.
Let me argue that it is indeterminate whether this graph is a complete graph with every pair of distinct nodes connected by an edge. After all, $C_3$ is the complete graph on three vertices, and it will follow from the theorem below that the Boolean value of the statement $\forall x,y\,(x=y\vee x\sim y)$ contains the element $3$ and therefore this Boolean value is not zero. Meanwhile, the assertion that the graph is not complete, however, also gets a nonzero Boolean value, since every $C_n$ except $C_3$ has distinct nodes with no edge between them. In a robust sense, the graph-theoretic truths of $\mathcal{C}$ combine the truths of all the various graphs $C_n$.
Note also that as $n$ increases, the graphs $C_n$ have nodes that are increasingly far apart. Fix any name $\langle a\rangle_{n\geq 3}$ and choose $\langle b\rangle_{n\geq 3}$ such that the distance between $a_n$ and $b_n$ in $C_n$ is not bounded by any particular uniform bound. In $\mathcal{C}$, it follows that $a$ and $b$ have no particular definite finite distance, and this can be viewed as a sense in which $\mathcal{C}$ is not connected.
A combination of many models
Let us flesh out the previous example with a more general analysis. Suppose we have a family of models $\set{M_i\mid i\in I}$ in a common language $\mathcal{L}$. Let $\B=P(I)$ be the power set of the set of indices $I$, a complete Boolean algebra. We define a $\B$-valued model $\mathcal{M}$ as follows. The set of names will be precisely the product of the models $M=\prod_i M_i$, which is to say, the $I$-tuples $s=\langle s_i\mid i\in I\rangle$ with $s_i\in M_i$ for every $i\in I$, and the simple atomic truth values are defined like this: \begin{eqnarray*} \boolval{s=t}&=&\set{i\in I\mid s_i=t_i} \\ \boolval{R(s,\ldots,t)}&=&\set{i\in I\mid M_i\satisfies R(s_i,\dots,t_i)}\\ \boolval{u=f(s,\ldots,t)} &=& \set{i\in I\mid M_i\satisfies u_i=f(s_i,\dots,t_i)}. \end{eqnarray*} One can now prove the equality and functionality axioms, and so this is a $\B$-valued model.
Theorem. The Boolean-valued model $\mathcal{M}$ described above is full, and Boolean-valued truth can be computed coordinatewise: $$\boolval{\varphi(s,\dots,t)}=\set{i\in I\mid M_i\satisfies\varphi(s_i,\dots,t_i)}.$$
Proof. We prove this by induction on $\varphi$, for assertions using only simple atomic formulas, $\wedge$, $\neg$, and $\exists$. The simple atomic case is part of what it means to be a Boolean-valued model. If the theorem is true for $\varphi$, then it will be true for $\neg\varphi$, since negation in $\B$ is complementation in $I$, as follows: $$\boolval{\neg\varphi}=\neg\boolval{\varphi}=I-\set{i\in I\mid M_i\satisfies\varphi}=\set{i\in I\mid M_i\satisfies\neg\varphi}.$$ If the theorem is true for $\varphi$ and $\psi$, then it will be true for $\varphi\wedge\psi$ as follows: \begin{eqnarray*} \boolval{\varphi\wedge\psi} &=& \boolval{\varphi}\wedge\boolval{\psi} \\ &=& \set{i\in I\mid M_i\satisfies\varphi}\cap\set{i\in I\mid M_i\satisfies\psi}\\ &=& \set{i\in I\mid M_i\satisfies\varphi\wedge\psi}. \end{eqnarray*} For the quantifier case $\exists x\, \varphi(x,s,\dots,t)$, choose $u_i\in M_i$ for which $M_i\satisfies\varphi(u_i,s_i,\dots,t_i)$, if possible. It follows that $$\set{i\in I\mid M_i\satisfies\exists x\,\varphi(x,s_i,\dots,t_i)}=\set{i\in I\mid M_i\satisfies\varphi(u_i,s_i,\dots,t_i)},$$ and from this it follows that $\boolval{\varphi(v,s,\dots,t)}\leq\boolval{\varphi(u,s,\dots,t)}$, since whenever $v_i$ succeeds as a witness then so also will $u_i$. Consequently, the model is full, and we see that \begin{eqnarray*} \boolval{\exists x\,\varphi(x,s,\dots,t)} &=& \bigvee_{v\in M}\boolval{\varphi(v,s,\dots,t)}\\ &=& \boolval{\varphi(u,s,\dots,t)}\\ &=& \set{i\in I\mid M_i\satisfies\exists x\,\varphi(x,s_i,\dots,t_i)}, \end{eqnarray*} as desired. $\Box$
Boolean ultrapowers
Every Boolean-valued model can be transformed into a classical model, a $2$-valued model, by means of a simple quotient construction. Suppose that $\mathcal{M}$ is a $\B$-valued model for some Boolean algebra $\B$ and that $\mu\newcommand\of{\subseteq}\of\B$ is an ultrafilter on the Boolean algebra.
Define an equivalence relation $=_\mu$ on the set of names by $$a=_\mu b\quad\text{ if and only if }\quad \boolval{a=b}\in\mu.$$ The quotient structure $\mathcal{M}/\mu$ will consist of equivalence classes $[a]_\mu$ of names by this equivalence relation. We define the atomic truths of the quotient structure similarly by reference to whether these truths hold with a value in $\mu$. Namely, $$R^{\mathcal{M}/\mu}([a]_\mu,\ldots,[b]_\mu)\quad\text{ if and only if }\quad \boolval{R(a,\dots,b)}\in\mu.$$ For function symbols $f$, we define $$[c]_\mu=f([a]_\mu,\dots,[b]_\mu)\quad\text{ if and only if }\quad \boolval{c=f(a,\dots,b)}\in\mu.$$ These definitions are well-defined modulo $=_\mu$ precisely because of the equality axiom properties of the Boolean-valued model $\mathcal{M}$. For example, if $a=_\mu a’$, then $\boolval{a=a’}\in\mu$, but $\boolval{a=a’}\wedge\boolval{R(a)}\leq \boolval{R(a’)}$ by the equality axiom, and so if $\boolval{R(a)}$ is in $\mu$, then so will be $\boolval{R(a’)}$.
We defined atomic truth in the quotient structure by reference to the truth value being $\mu$-large. In fact, this reduction will continue for all truth assertions in the quotient structure, which we prove as follows.
Theorem. (Łoś theorem for Boolean ultrapowers) Suppose that $\mathcal{M}$ is a full $\B$-valued model for a Boolean algebra $\B$, and that $\mu\of\B$ is an ultrafilter. Then a statement is true in the Boolean quotient structure $\mathcal{M}/\mu$ if and only if the Boolean value of the statement is in $\mu$. $$\mathcal{M}/\mu\satisfies\varphi([a]_\mu,\dots,[b]_\mu)\quad\text{ if and only if }\quad\boolval{\varphi(a,\dots,b)}\in\mu.$$
Proof. We prove this by induction on $\varphi$. The simple atomic case holds by the definition of the quotient structure. Boolean connectives $\wedge$, $\neg$ follow easily using that $\mu$ is a filter and that it is an ultrafilter. Consider the quantifier case $\exists x\, \varphi(a,\dots,b,x)$, where by induction the theorem holds for $\varphi$ itself. If the quotient structure satisfies the existential $\mathcal{M}/\mu\satisfies\exists x\,\varphi([a],\dots,[b],x)$, then there is a name $c$ for which it satisfies $\varphi([a],\dots,[b],[c])$, and so by induction $\boolval{\varphi(a,\dots,b,c)}\in\mu$, in which case also $\boolval{\exists x\,\varphi(a,\dots,b,x)}\in\mu$, since this latter Boolean value is at least as great as the former. Conversely, if $\boolval{\exists x\,\varphi(a,\dots,b,x)}\in\mu$, then by fullness this existential Boolean value is realized by some name $c$, and so $\boolval{\varphi(a,\dots,b,c)}\in\mu$, which by induction implies that the quotient satisfies $\varphi([a],\dots,[b],[c])$ and consequently also $\exists x\,\varphi([a],\dots,[b],x)$, as desired. $\Box$
Note how fullness was used in the existential case of the inductive argument.
This will be a talk for the Department Colloquium of the Philosophy Department of the University of Notre Dame, 26 March 12 pm EST (4pm GMT).
Abstract: Potentialism is the view, originating in the classical dispute between actual and potential infinity, that one’s mathematical universe is never fully completed, but rather unfolds gradually as new parts of it increasingly come into existence or become accessible or known to us. Recent work emphasizes the modal aspect of potentialism, while decoupling it from arithmetic and from infinity: the essence of potentialism is about approximating a larger universe by means of universe fragments, an idea that applies to set-theoretic as well as arithmetic foundations. The modal language and perspective allows one precisely to distinguish various natural potentialist conceptions in the foundations of mathematics, whose exact modal validities are now known. Ultimately, this analysis suggests a refocusing of potentialism on the issue of convergent inevitability in comparison with radical branching. I shall defend the theses, first, that convergent potentialism is implicitly actualist, and second, that we should understand ultrafinitism in modal terms as a form of potentialism, one with surprising parallels to the case of arithmetic potentialism.
This will be an event for the $\Phi$-Math Reading Group at the Institute for Logic, Language, and Computation (ILLC) at the University of Amsterdam, 19 March 2021 6pm CET (5pm GMT). Zoom access here.
I shall make a brief presentation of the overall contents of the book, including a discussion of my perspective on the subject, and then get into some of the detailed issues with which the book engages. After this, we shall open up for discussion and comments.
I was so glad to be involved with this project of Hannah Hoffman. She had inquired on Twitter whether mathematicians could provide a proof of the irrationality of root two that rhymes. I set off immediately, of course, to answer the challenge. My wife Barbara Gail Montero and our daughter Hypatia and I spent a day thinking, writing, revising, rewriting, rethinking, rewriting, and eventually we had a set lyrics providing the proof, in rhyme and meter. We had wanted specifically to highlight not only the logic of the proof, but also to tell the fateful story of Hippasus, credited with the discovery.
Hannah proceeded to create the amazing musical version:
The diagonal of a square is incommensurable with its side
an astounding fact the Pythagoreans did hide
but Hippasus rebelled and spoke the truth
making his point with irrefutable proof
it’s absurd to suppose that the root of two
is rational, namely, p over q
square both sides and you will see
that twice q squared is the square of p
since p squared is even, then p is as well
now, if p as 2k you alternately spell
2q squared will to 4k squared equate
revealing, when halved, q’s even fate
thus, root two as fraction, p over q
must have numerator and denomerator with factors of two
to lowest terms, therefore, it can’t be reduced
root two is irrational, Hippasus deduced
as retribution for revealing this irrationality
Hippasus, it is said, was drowned in the sea
but his proof live on for the whole world to admire
a truth of elegance that will ever inspire.
This was a talk for the Kobe Set Theory Workshop, held on the occasion of Sakaé Fuchino’s retirement, 9-11 March 2021.
Abstract. I shall discuss senses in which set-theoretic forcing can be seen as a computational process on the models of set theory. Given an oracle for the atomic or elementary diagram of a model of set theory $\langle M,\in^M\rangle$, for example, one may in various senses compute $M$-generic filters $G\subset P\in M$ and the corresponding forcing extensions $M[G]$. Meanwhile, no such computational process is functorial, for there must always be isomorphic alternative presentations of the same model of set theory $M$ that lead by the computational process to non-isomorphic forcing extensions $M[G]\not\cong M[G’]$. Indeed, there is no Borel function providing generic filters that is functorial in this sense.
This is joint work with Russell Miller and Kameryn Williams.
Abstract. The principle of open determinacy for class games — two-player games of perfect information with plays of length ω, where the moves are chosen from a possibly proper class, such as games on the ordinals — is not provable in Zermelo-Fraenkel set theory ZFC or Gödel-Bernays set theory GBC, if these theories are consistent, because provably in ZFC there is a definable open proper class game with no definable winning strategy. In fact, the principle of open determinacy and even merely clopen determinacy for class games implies Con(ZFC) and iterated instances Con(Con(ZFC)) and more, because it implies that there is a satisfaction class for first-order truth, and indeed a transfinite tower of truth predicates $\text{Tr}_\alpha$ for iterated truth-about-truth, relative to any class parameter. This is perhaps explained, in light of the Tarskian recursive definition of truth, by the more general fact that the principle of clopen determinacy is exactly equivalent over GBC to the principle of elementary transfinite recursion ETR over well-founded class relations. Meanwhile, the principle of open determinacy for class games is strictly stronger, although it is provable in the stronger theory GBC+$\Pi^1_1$-comprehension, a proper fragment of Kelley-Morse set theory KM.
This is currently a draft version only of my article-in-progress on the topic of linearity in the hierarchy of consistency strength, especially with large cardinals. Comments are very welcome, since I am still writing the article. Please kindly send me comments by email or just post here.
This article will be the basis of the Weeks 7 & 8 discussion in the Graduate Philosophy of Logic seminar I am currently running with Volker Halbach at Oxford in Hilary term 2021.
I present instances of nonlinearity and illfoundedness in the hierarchy of large cardinal consistency strength—as natural or as nearly natural as I can make them—and consider philosophical aspects of the question of naturality with regard to this phenomenon.
It is a mystery often mentioned in the foundations of mathematics, a fundamental phenomenon to be explained, that our best and strongest mathematical theories seem to be linearly ordered and indeed well-ordered by consistency strength. Given any two of the familiar large cardinal hypotheses, for example, generally one of them will prove the consistency of the other.
Why should it be linear? Why should the large cardinal notions line up like this, when they often arise from completely different mathematical matters? Measurable cardinals arise from set-theoretic issues in measure theory; Ramsey cardinals generalize ideas in graph coloring combinatorics; compact cardinals arise with compactness properties of infinitary logic. Why should these disparate considerations lead to principles that are linearly related by direct implication and consistency strength?
The phenomenon is viewed by many in the philosophy of mathematics as significant in our quest for mathematical truth. In light of Gödel incompleteness, after all, we must eternally seek to strengthen even our best and strongest theories. Is the linear hierarchy of consistency strength directing us along the elusive path, the “one road upward” as John Steel describes it, toward the final, ultimate mathematical truth? That is the tantalizing possibility.
Meanwhile, we do know as a purely formal matter that the hierarchy of consistency strength is not actually well-ordered—it is ill-founded, densely ordered, and nonlinear. The statements usually used to illustrate these features, however, are weird self-referential assertions constructed in the Gödelian manner via the fixed-point lemma—logic-game trickery, often dismissed as unnatural.
Many set theorists claim that amongst the natural assertions, consistency strengths remain linearly ordered and indeed well ordered. H. Friedman refers to “the apparent comparability of naturally occurring logical strengths as one of the great mysteries of [the foundations of mathematics].” Andrés Caicedo says,
It is a remarkable empirical phenomenon that we indeed have comparability for natural theories. We expect this to always be the case, and a significant amount of work in inner model theory is guided by this belief.
Stephen G. Simpson writes:
It is striking that a great many foundational theories are linearly ordered by <. Of course it is possible to construct pairs of artificial theories which are incomparable under <. However, this is not the case for the “natural” or non-artificial theories which are usually regarded as significant in the foundations of mathematics. The problem of explaining this observed regularity is a challenge for future foundational research.
John Steel writes “The large cardinal hypotheses [the ones we know] are themselves wellordered by consistency strength,” and he formulates what he calls the “vague conjecture” asserting that
If T is a natural extension of ZFC, then there is an extension H axiomatized by large cardinal hypotheses such that T ≡ Con H. Moreover, ≤ Con is a prewellorder of the natural extensions of ZFC. In particular, if T and U are natural extensions of ZFC, then either T ≤ Con U or U ≤ Con T.
Peter Koellner writes
Remarkably, it turns out that when one restricts to those theories that “arise in nature” the interpretability ordering is quite simple: There are no descending chains and there are no incomparable elements—the interpretability ordering on theories that “arise in nature” is a wellordering.
Let me refer to this position as the natural linearity position, the assertion that all natural assertions of mathematics are linearly ordered by consistency strength. The strong form of the position, asserted by some of those whom I have cited above, asserts that the natural assertions of mathematics are indeed well-ordered by consistency strength. By all accounts, this view appears to be widely held in large cardinal set theory and the philosophy of set theory.
Despite the popularity of this position, I should like in this article to explore the contrary view and directly to challenge the natural linearity position.
Main Question. Can we find natural instances of nonlinearity and illfoundedness in the hierarchy of consistency strength?
I shall try my best.
You have to download the article to see my candidates for natural instances of nonlinearity in the hierarchy of large cardinal consistency strength, but I can tease you a little by mentioning that there are various cautious enumerations of the ZFC axioms which actually succeed in enumerating all the ZFC axioms, but with a strictly weaker consistency strength than the usual (incautious) enumeration. And similarly there are various cautious versions of the large cardinal hypothesis, which are natural, but also incomparable in consistency strength.
(Please note that it was Uri Andrews, rather than Uri Abraham, who settled question 16 with the result of theorem 17. I have corrected this from an earlier draft.)
This brief unpublished note (11 pages) contains an overview of the Gödel fixed-point lemma, along with several generalizations and applications, written for use in the Week 3 lecture of the Graduate Philosophy of Logic seminar that I co-taught with Volker Halbach at Oxford in Hilary term 2021. The theme of the seminar was self-reference, truth, and consistency strengths, and in this lecture we discussed the nature of Gödel’s fixed-point lemma and generalizations, with various applications in logic.
Gödel’s fixed-point lemma An application to the Gödel incompleteness theorem
Finite self-referential schemes An application to nonindependent disjunctions of independent sentences
Gödel-Carnap fixed point lemma Deriving the double fixed-point lemma as a consequence An application to the provability version of Yablo’s paradox
Kleene recursion theorem An application involving computable numbers An application involving the universal algorithm An application to Quine programs and Ouroborous chains
