# Pluralism-inspired mathematics, including a recent breakthrough in set-theoretic geology, Set-theoretic Pluralism Symposium, Aberdeen, July 2016

Set-theoretic Pluralism, Symposium I, July 12-17, 2016, at the University of Aberdeen.  My talk will be the final talk of the conference.

Abstract. I shall discuss several bits of pluralism-inspired mathematics, including especially an account of Toshimichi Usuba’s recent proof of the strong downward-directed grounds DDG hypothesis, which asserts that the collection of ground models of the set-theoretic universe is downward directed. This breakthrough settles several of what were the main open questions of set-theoretic geology. It implies, for example, that the mantle is a model of ZFC and is identical to the generic mantle and that it is therefore the largest forcing-invariant class. Usuba’s analysis also happens to show that the existence of certain very large cardinals outright implies that there is a smallest ground model of the universe, an unexpected connection between large cardinals and forcing. In addition to these results, I shall present several other instances of pluralism-inspired mathematics, including a few elementary but surprising results that I hope will be entertaining.

# My very first lemma, which also happened to involve a philosophical dispute

Let me recall the time of my very first lemma, which also happened to involve a philosophical dispute.

It was about 35 years ago; I was a kid in ninth grade at McKinley Junior High School, taking a class in geometry, taught by a charismatic math teacher. We were learning how to do proofs, which in that class always consisted of a numbered list of geometrical assertions, with a specific reason given for each assertion, either stating that it was “given” or that it followed from previous assertions by a theorem that we had come to know. Only certain types of reasons were allowed.

My instructor habitually used the overhead projector, writing on a kind of infinite scroll of transparency film, which he could wind up on one end of the projector, so as never to run out of room. During the semester, he had filled enough spools, it seemed, to fill the library of Alexandria.

One day, it came to be my turn to present to the rest of the class my proof of a certain geometrical theorem I had been assigned. I took the black marker and drew out my diagram and theorem statement. In my proof, I had found it convenient to first establish a certain critical fact, that two particular line segments in my diagram were congruent $\vec{PQ}\cong\vec{RS}$. In order to do so, I had added various construction lines to my diagram and reasoned with side-angle-side and so on.

Having established the congruency, I had then wanted to continue with my proof of the theorem. Since the previous construction lines were cluttering up my diagram, however, I simply erased them, leaving only my original diagram.

The class erupted with objection!  How could I sensibly continue now with my proof, claiming that $\vec{PQ}\cong\vec{RS}$, after I had erased the construction lines? After all, are those lines segments still congruent once we erase the construction lines that provided the reason we first knew this to be true? Many of the students believed that my having erased the construction lines invalidated my proof.

So there I was, in a ninth-grade math class, making a philosophical argument to my fellow students that the truth of the congruence $\vec{PQ}\cong\vec{RS}$ was independent of my having drawn the construction lines, and that we could rely on the truth of that fact later on in my proof, even if I were to erase those construction lines.

After coming to an uneasy, tentative resolution of this philosophical dispute, I was then allowed to continue with the rest of my proof, establishing the main theorem.

I realized only much later that this had been my very first lemma, since I had isolated a mathematically central fact about a certain situation, proving it with a separate argument, and then I had used that fact in the course of proving a more general theorem.

# The Vopěnka principle is inequivalent to but conservative over the Vopěnka scheme

• J. D. Hamkins, “The Vopěnka principle is inequivalent to but conservative over the Vopěnka scheme.” (manuscript under review)
@ARTICLE{Hamkins:The-Vopenka-principle-is-inequivalent-to-but-conservative-over-the-Vopenka-scheme,
author = {Joel David Hamkins},
title = {The Vop\v{e}nka principle is inequivalent to but conservative over the Vop\v{e}nka scheme},
journal = {},
year = {},
volume = {},
number = {},
pages = {},
month = {},
note = {manuscript under review},
abstract = {},
keywords = {},
source = {},
eprint = {1606.03778},
archivePrefix = {arXiv},
primaryClass = {math.LO},
url = {http://jdh.hamkins.org/vopenka-principle-vopenka-scheme},
}

Abstract. The Vopěnka principle, which asserts that every proper class of first-order structures in a common language admits an elementary embedding between two of its members, is not equivalent over GBC to the first-order Vopěnka scheme, which makes the Vopěnka assertion only for the first-order definable classes of structures. Nevertheless, the two Vopěnka axioms are equiconsistent and they have exactly the same first-order consequences in the language of set theory. Specifically, GBC plus the Vopěnka principle is conservative over ZFC plus the Vopěnka scheme for first-order assertions in the language of set theory.

The Vopěnka principle is the assertion that for every proper class $\mathcal{M}$ of first-order $\mathcal{L}$-structures, for a set-sized language $\mathcal{L}$, there are distinct members of the class $M,N\in\mathcal{M}$ with an elementary embedding $j:M\to N$ between them. In quantifying over classes, this principle is a single assertion in the language of second-order set theory, and it makes sense to consider the Vopěnka principle in the context of a second-order set theory, such as Godel-Bernays set theory GBC, whose language allows one to quantify over classes. In this article, GBC includes the global axiom of choice.

In contrast, the first-order Vopěnka scheme makes the Vopěnka assertion only for the first-order definable classes $\mathcal{M}$ (allowing parameters). This theory can be expressed as a scheme of first-order statements, one for each possible definition of a class, and it makes sense to consider the Vopěnka scheme in Zermelo-Frankael ZFC set theory with the axiom of choice.

Because the Vopěnka principle is a second-order assertion, it does not make sense to refer to it in the context of ZFC set theory, whose first-order language does not allow quantification over classes; one typically retreats to the Vopěnka scheme in that context. The theme of this article is to investigate the precise meta-mathematical interactions between these two treatments of Vopěnka’s idea.

Main Theorems.

1. If ZFC and the Vopěnka scheme holds, then there is a class forcing extension, adding classes but no sets, in which GBC and the Vopěnka scheme holds, but the Vopěnka principle fails.
2. If ZFC and the Vopěnka scheme holds, then there is a class forcing extension, adding classes but no sets, in which GBC and the Vopěnka principle holds.

It follows that the Vopěnka principle VP and the Vopěnka scheme VS are not equivalent, but they are equiconsistent and indeed, they have the same first-order consequences.

Corollaries.

1. Over GBC, the Vopěnka principle and the Vopěnka scheme, if consistent, are not equivalent.
2. Nevertheless, the two Vopěnka axioms are equiconsistent over GBC.
3. Indeed, the two Vopěnka axioms have exactly the same first-order consequences in the language of set theory. Specifically, GBC plus the Vopěnka principle is conservative over ZFC plus the Vopěnka scheme for assertions in the first-order language of set theory. $$\text{GBC}+\text{VP}\vdash\phi\qquad\text{if and only if}\qquad\text{ZFC}+\text{VS}\vdash\phi$$

These results grew out of my my answer to a MathOverflow question of Mike Shulman, Can Vopěnka’s principle be violated definably?, inquiring whether there would always be a definable counterexample to the Vopěnka principle, whenever it should happen to fail. I interpret the question as asking whether the Vopěnka scheme is necessarily equivalent to the Vopěnka principle, and the answer is negative.

The proof of the main theorem involves the concept of a stretchable set $g\subset\kappa$ for an $A$-extendible cardinal, which has the property that for every cardinal $\lambda>\kappa$ and every extension $h\subset\lambda$ with $h\cap\kappa=g$, there is an elementary embedding $j:\langle V_\lambda,\in,A\cap V_\lambda\rangle\to\langle V_\theta,\in,A\cap V_\theta\rangle$ such that $j(g)\cap\lambda=h$. Thus, the set $g$ can be stretched by an $A$-extendibility embedding so as to agree with any given $h$.

# The hierarchy of logical expressivity

I’d like to give a simple account of what I call the hierarchy of logical expressivity for fragments of classical propositional logic. The idea is to investigate and classify the expressive power of fragments of the traditional language of propositional logic, with the five familiar logical connectives listed below, by considering subsets of these connectives and organizing the corresponding sublanguages of propositional logic into a hierarchy of logical expressivity.

• conjunction (“and”), denoted $\wedge$
• disjunction (“or”), denoted  $\vee$
• negation (“not”), denoted $\neg$
• conditional (“if…, then”), denoted  $\to$
• biconditional (“if and only if”), denoted  $\renewcommand\iff{\leftrightarrow}\iff$

With these five connectives, there are, of course, precisely thirty-two ($32=2^5$) subsets, each giving rise to a corresponding sublanguage, the language of propositional assertions using only those connectives. Which sets of connectives are equally as expressive or more expressive than which others? Which sets of connectives are incomparable in their expressivity? How many classes of expressivity are there?

Before continuing, let me mention that Ms. Zoë Auerbach (CUNY Graduate Center), one of the students in my logic-for-philosophers course this past semester, Survey of Logic for Philosophers, at the CUNY Graduate Center in the philosophy PhD program, had chosen to write her term paper on this topic.  She has kindly agreed to make her paper, “The hierarchy of expressive power of the standard logical connectives,” available here, and I shall post it soon.

To focus the discussion, let us define what I call the (pre)order of logical expressivity on sets of connectives. Namely, for any two sets of connectives, I define that $A\leq B$ with respect to logical expressivity, just in case every logical expression in any number of propositional atoms using only connectives in $A$ is logically equivalent to an expression using only connectives in $B$. Thus, $A\leq B$ means that the connectives in $B$ are collectively at least as expressive as the connectives in $A$, in the sense that with the connectives in $B$ you can express any logical assertion that you were able to express with the connectives in $A$. The corresponding equivalence relation $A\equiv B$ holds when $A\leq B$ and $B\leq A$, and in this case we shall say that the sets are expressively equivalent, for this means that the two sets of connectives can express the same logical assertions.

The full set of connectives $\{\wedge,\vee,\neg,\to,\iff\}$ is well-known to be complete for propositional logic in the sense that every conceivable truth function, with any number of propositional atoms, is logically equivalent to an expression using only the classical connectives. Indeed, already the sub-collection $\{\wedge,\vee,\neg\}$ is fully complete, and hence expressively equivalent to the full collection, because every truth function can be expressed in disjunctive normal form, as a disjunction of finitely many conjunction clauses, each consisting of a conjunction of propositional atoms or their negations (and hence altogether using only disjunction, conjunction and negation). One can see this easily, for example, by noting that for any particular row of a truth table, there is a conjunction expression that is true on that row and only on that row. For example, the expression $p\wedge\neg r\wedge s\wedge \neg t$ is true on the row where $p$ is true, $r$ is false, $s$ is true and $t$ is false, and one can make similar expressions for any row in any truth table. Simply by taking the disjunction of such expressions for suitable rows where a $T$ is desired, one can produce an expression in disjunctive normal form that is true in any desired pattern (use $p\wedge\neg p$ for the never-true truth function). Therefore, every truth function has a disjunctive normal form, and so $\{\wedge,\vee,\neg\}$ is complete.

Pressing this further, one can eliminate either $\wedge$ or $\vee$ by systematically applying the de Morgan laws
$$p\vee q\quad\equiv\quad\neg(\neg p\wedge\neg q)\qquad\qquad p\wedge q\quad\equiv\quad\neg(\neg p\vee\neg q),$$
which allow one to reduce disjunction to conjunction and negation or reduce conjunction to disjunction and negation. It follows that $\{\wedge,\neg\}$ and $\{\vee,\neg\}$ are each complete, as is any superset of these sets, since a set is always at least as expressive as any of it subsets. Similarly, because we can express disjunction with negation and the conditional via $$p\vee q\quad\equiv\quad \neg p\to q,$$ it follows that the set $\{\to,\neg\}$ can express $\vee$, and hence also is complete. From these simple observations, we may conclude that each of the following fourteen sets of connectives is complete. In particular, they are all expressively equivalent to each other.
$$\{\wedge,\vee,\neg,\to,\iff\}$$
$$\{\wedge,\vee,\neg,\iff\}\qquad\{\wedge,\to,\neg,\iff\}\qquad\{\vee,\to,\neg,\iff\}\qquad \{\wedge,\vee,\neg,\to\}$$
$$\{\wedge,\neg,\iff\}\qquad\{\vee,\neg,\iff\}\qquad\{\to,\neg,\iff\}$$
$$\{\wedge,\vee,\neg\}\qquad\{\wedge,\to,\neg\}\qquad\{\vee,\to,\neg\}$$
$$\{\wedge,\neg\}\qquad \{\vee,\neg\}\qquad\{\to,\neg\}$$

Notice that each of those complete sets includes the negation connective $\neg$. If we drop it, then the set $\{\wedge,\vee,\to,\iff\}$ is not complete, since each of these four connectives is truth-preserving, and so any logical expression made from them will have a $T$ in the top row of the truth table, where all atoms are true. In particular, these four connectives collectively cannot express negation $\neg$, and so they are not complete.

Clearly, we can express the biconditional as two conditionals, via $$p\iff q\quad\equiv\quad (p\to q)\wedge(q\to p),$$ and so the $\{\wedge,\vee,\to,\iff\}$ is expressively equivalent to $\{\wedge,\vee,\to\}$. And since disjunction can be expressed from the conditional with $$p\vee q\quad\equiv\quad ((p\to q)\to q),$$ it follows that the set is expressively equivalent to $\{\wedge,\to\}$. In light of $$p\wedge q\quad\equiv\quad p\iff(p\to q),$$ it follows that $\{\to,\iff\}$ can express conjunction and hence is also expressively equivalent to $\{\wedge,\vee,\to,\iff\}$. Since
$$p\vee q\quad\equiv\quad(p\wedge q)\iff(p\iff q),$$ it follows that $\{\wedge,\iff\}$ can express $\vee$ and hence also $\to$, because $$p\to q\quad\equiv\quad q\iff(q\vee p).$$ Similarly, using $$p\wedge q\quad\equiv\quad (p\vee q)\iff(p\iff q),$$ we can see that $\{\vee,\iff\}$ can express $\wedge$ and hence also is expressively equivalent to $\{\wedge,\vee,\iff\}$, which we have argued is equivalent to $\{\wedge,\vee,\to,\iff\}$.  For these reasons, the following sets of connectives are expressively equivalent to each other.
$$\{\wedge,\vee,\to,\iff\}$$
$$\{\wedge,\vee,\to\}\qquad\{\wedge,\vee,\iff\}\qquad \{\vee,\to,\iff\}\qquad \{\wedge,\to,\iff\}$$
$$\{\wedge,\iff\}\qquad \{\vee,\iff\}\qquad \{\to,\iff\}\qquad \{\wedge,\to\}$$
And as I had mentioned, these sublanguages are strictly less expressive than the full language, because these four connectives are all truth-preserving and therefore unable to express negation.

The set $\{\wedge,\vee\}$, I claim, is unable to express any of the other fundamental connectives, because $\wedge$ and $\vee$ are each false-preserving, and so any logical expression built from $\wedge$ and $\vee$ will have $F$ on the bottom row of the truth table, where all atoms are false. Meanwhile, $\to,\iff$ and $\neg$ are not false-preserving, since they each have $T$ on the bottom row of their defining tables. Thus, $\{\wedge,\vee\}$ lies strictly below the languages mentioned in the previous paragraph in terms of logical expressivity.

Meanwhile, using only $\wedge$ we cannot express $\vee$, since any expression in $p$ and $q$ using only $\wedge$ will have the property that any false atom will make the whole expression false (this uses the associativity of $\wedge$), and $p\vee q$ does not have this feature. Similarly, $\vee$ cannot express $\wedge$, since any expression using only $\vee$ is true if any one of its atoms is true, but $p\wedge q$ is not like this. For these reasons, $\{\wedge\}$ and $\{\vee\}$ are both strictly weaker than $\{\wedge,\vee\}$ in logical expressivity.

Next, I claim that $\{\vee,\to\}$ cannot express $\wedge$, and the reason is that the logical operations of $\vee$ and $\to$ each have the property that any expression built from that has at least as many $T$’s as $F$’s in the truth table. This property is true of any propositional atom, and if $\varphi$ has the property, so does $\varphi\vee\psi$ and $\psi\to\varphi$, since these expressions will be true at least as often as $\varphi$ is. Since $\{\vee,\to\}$ cannot express $\wedge$, this language is strictly weaker than $\{\wedge,\vee,\to,\iff\}$ in logical expressivity. Actually, since as we noted above $$p\vee q\quad\equiv\quad ((p\to q)\to q),$$ it follows that $\{\vee,\to\}$ is expressively equivalent to $\{\to\}$.

Meanwhile, since $\vee$ is false-preserving, it cannot express $\to$, and so $\{\vee\}$ is strictly less expressive than $\{\vee,\to\}$, which is expressively equivalent to $\{\to\}$.

Consider next the language corresponding to $\{\iff,\neg\}$. I claim that this set is not complete. This argument is perhaps a little more complicated than the other arguments we have given so far. What I claim is that both the biconditional and negation are parity-preserving, in the sense that any logical expression using only $\neg$ and $\iff$ will have an even number of $T$’s in its truth table. This is certainly true of any propositional atom, and if true for $\varphi$, then it is true for $\neg\varphi$, since there are an even number of rows altogether; finally, if both $\varphi$ and $\psi$ have even parity, then I claim that $\varphi\iff\psi$ will also have even parity. To see this, note first that this biconditional is true just in case $\varphi$ and $\psi$ agree, either having the pattern T/T or F/F. If there are an even number of times where both are true jointly T/T, then the remaining occurrences of T/F and F/T will also be even, by considering the T’s for $\varphi$ and $\psi$ separately, and consequently, the number of occurrences of F/F will be even, making $\varphi\iff\psi$ have even parity. If the pattern T/T is odd, then also T/F and F/T will be odd, and so F/F will have to be odd to make up an even number of rows altogether, and so again $\varphi\iff\psi$ will have even parity. Since conjunction, disjunction and the conditional do not have even parity, it follows that $\{\iff,\neg\}$ cannot express any of the other fundamental connectives.

Meanwhile, $\{\iff\}$ is strictly less expressive than $\{\iff,\neg\}$, since the biconditional $\iff$ is truth-preserving but negation is not. And clearly $\{\neg\}$ can express only unary truth functions, since any expression using only negation has only one propositional atom, as in $\neg\neg\neg p$. So both $\{\iff\}$ and $\{\neg\}$ are strictly less expressive than $\{\iff,\neg\}$.

Lastly, I claim that $\iff$ is not expressible from $\to$. If it were, then since $\vee$ is also expressible from $\to$, we would have that $\{\vee,\iff\}$ is expressible from $\to$, contradicting our earlier observation that $\{\to\}$ is strictly less expressive than $\{\vee,\iff\}$, as this latter set can express $\wedge$, but $\to$ cannot, since every expression in $\to$ has at least as many $T$’s as $F$’s in its truth table.

These observations altogether establish the hierarchy of logical expressivity shown in the diagram displayed above.

It is natural, of course, to want to extend the hierarchy of logical expressivity beyond the five classical connectives. If one considers all sixteen binary logical operations, then Greg Restall has kindly produced the following image, which shows how the hierarchy we discussed above fits into the resulting hierarchy of expressivity. This diagram shows only the equivalence classes, rather than all $65536=2^{16}$ sets of connectives.

If one wants to go beyond merely the binary connectives, then one lands at Post’s lattice, pictured below (image due to Emil Jeřábek), which is the countably infinite (complete) lattice of logical expressivity for all sets of truth functions, using any given set of Boolean connectives. Every such set is finitely generated.

# Drunk Science: Infinity, special guest, June 23, 2016

I shall be special guest at Drunk Science: Infinity, an experimental comedy show in Brooklyn, during which three intoxicated comedians will compete to offer the best dissertation defense on the topic of my research.

\newcommand\PA{\text{PA}}
\newcommand\Con{\mathop{\text{Con}}}
\newcommand\proves{\vdash}
\newcommand{\concat}{\mathbin{{}^\smallfrown}}
\newcommand\restrict{\upharpoonright}
$Theorem There is a Turing machine program$p$, carrying out the specific algorithm described in the proof, such that for any function$f:\N\to\N$, there is a model of arithmetic$M\models\PA$, or indeed a model of set theory$M\models\ZFC$or more (if consistent), such that the function computed by program$p$inside$M$agrees exactly with$f$on all standard finite input. The proof is elementary, relying essentially only on the ideas of the classical proof of the Gödel-Rosser theorem. To briefly review, for any computably axiomatized theory$T$extending$\PA$, there is a corresponding sentence$\rho$, called the Rosser sentence, which asserts, “for any proof of$\rho$in$T$, there is a smaller proof of$\neg\rho$.” That is, by smaller, I mean that the Gödel-code of the proof is smaller. One constructs the sentence$\rho$by a simple application of the Gödel fixed-point lemma, just as one constructs the usual Gödel sentence that asserts its own non-provability. The basic classical facts concerning the Rosser sentence include the following: • If$T$is consistent, then so are both$T+\rho$and$T+\neg\rho$•$\PA+\Con(T)$proves$\rho$. • The theories$T$,$T+\rho$and$T+\neg\rho$are equiconsistent. • If$T$is consistent, then$T+\rho$does not prove$\Con(T)$. The first statement is the essential assertion of the Gödel-Rosser theorem, and it is easy to prove: if$T$is consistent and$T\proves\rho$, then the proof would be finite in the meta-theory, and so since$T$would have to prove that there is a smaller proof of$\neg\rho$, that proof would also be finite in the meta-theory and hence an actual proof, contradicting the consistency of$T$. Similarly, if$T\proves\neg\rho$, then the proof would be finite in the meta-theory, and so$T$would be able to verify that$\rho$is true, and so$T\proves\rho$, again contradicting consistency. By internalizing the previous arguments to PA, we see that$\PA+\Con(T)$will prove that neither$\rho$nor$\neg\rho$are provable in$T$, making$\rho$vacuously true in this case and also establishing$\Con(T+\rho)$and$\Con(T+\neg\rho)$, for the second and third statements. In particular,$T+\Con(T)\proves\Con(T+\rho)$, which implies that$T+\rho$does not prove$\Con(T)$by the incompleteness theorem applied to the theory$T+\rho$, for the fourth statement. Let’s now proceed to the proof of the theorem. To begin, we construct what I call the Rosser tree over a c.e. theory$T$. Namely, we recursively define theories$R_s$for each finite binary string$s\in 2^{{<}\omega}$, placing the initial theory$R_{\emptyset}=T$at the root, and then recursively adding either the Rosser sentence$\rho_s$for the theory$R_s$or its negation$\neg\rho_s$at each stage to form the theories at the next level of the tree. $$R_{s\concat 1}=R_s+\rho_s$$ $$R_{s\concat 0}=R_s+\neg\rho_s$$ Each theory$R_s$is therefore a finite extension of$T$by successively adding the appropriate Rosser sentences or their negations in the pattern described by$s$. If the initial theory$T$is consistent, then it follows by induction using the Gödel-Rosser theorem that all the theories$R_s$in the Rosser tree are consistent. Extending our notation to the branches through the tree, if$f\in{}^\omega 2$is an infinite binary sequence, we let$R_f=\bigcup_n R_{f\upharpoonright n}$be the union of the theories arising along that branch of the Rosser tree. In this way, we have constructed a perfect set of continuum many distinct consistent theories. I shall now describe a universal algorithm for the case of computing binary functions. Consider the Rosser tree over the theory$T=\PA+\neg\Con(\PA)$. This is a consistent theory that happens to prove its own inconsistency. By considering the Gödel-codes in order, the algorithm should begin by searching for a proof of the Rosser sentence$\rho_{\emptyset}$or its negation in the initial theory$R_{\emptyset}$. If such a proof is ever found, then the algorithm outputs$0$or$1$on input$0$, respectively, depending on whether it was the Rosser sentence or its negation that was found first, and moves to the next theory in the Rosser tree by adding the opposite statement to the current theory. Then, it starts searching for a proof of the Rosser sentence of that theory or its negation. At each stage in the algorithm, there is a current theory$R_s$, depending on which prior proofs have been found, and the algorithm searches for a proof of$\rho_s$or$\neg\rho_s$. If found, it outputs$0$or$1$accordingly (on input$n=|s|$), and moves to the next theory in the Rosser tree by adding the opposite statement to the current theory. If$f:\N\to 2=\{0,1\}$is any binary function on the natural numbers, then let$R_f$be the theory arising from the corresponding path through the Rosser tree, and let$M\models R_f$be a model of this theory. I claim that the universal algorithm I just described will compute exactly$f(n)$on input$n$inside this model. The thing to notice is that because$\neg\Con(\PA)$was part of the initial theory, the model$M$will think that all the theories in the Rosser tree are inconsistent. So the model will have plenty of proofs of every statement and its negation for any theory in the Rosser tree, and so in particular, the function computed by$p$in$M$will be a total function. The question is which proofs will come first at each stage, affecting the values of the function. Let$s=f\restrict n$and notice that$R_s$is true in$M$. Suppose inductively that the function computed by$p$has worked correctly below$n$in$M$, and consider stage$n$of the procedure. By induction, the current theory will be exactly$R_s$, and the algorithm will be searching for a proof of$\rho_s$or its negation in$R_s$. Notice that$f(n)=1$just in case$\rho_s$is true in$M$, and because of what$\rho_s$asserts and the fact that$M$thinks it is provable in$R_s$, it must be that there is a smaller proof of$\neg\rho_s$. So in this case, the algorithm will find the proof of$\neg\rho_s$first, and therefore, according to the precise instructions of the algorithm, it will output$1$on input$n$and add$\rho_s$(the opposite statement) to the current theory, moving to the theory$R_{s\concat 1}$in the Rosser tree. Similarly, if$f(n)=0$, then$\neg\rho_s$will be true in$M$, and the algorithm will therefore first find a proof of$\rho_s$, give output$0$and add$\neg\rho_s$to the current theory, moving to$R_{s\concat 0}$. In this way, the algorithm finds the proofs in exactly the right way so as to have$R_{f\restrict n}$as the current theory at stage$n$and thereby compute exactly the function$f$, as desired. Basically, the theory$R_f$asserts exactly that the proofs will be found in the right order in such a way that program$p$will exactly compute$f$on all standard finite input. So every binary function$f$is computed by the algorithm in any model of the theory$R_f$. Let me now explain how to extend the result to handle all functions$g:\N\to\N$, rather than only the binary functions as above. The idea is simply to modify the binary universal algorithm in a simple way. Any function$g:\N\to \N$can be coded with a binary function$f:\N\to 2$in a canonical way, for example, by having successive blocks of$1$s in$f$, separated by$0$s, with the$n^{\rm th}$block of size$g(n)$. Let$q$be the algorithm that runs the binary universal algorithm described above, thereby computing a binary sequence, and then extract from that binary sequence a corresponding function from$\N$to$\N$(this may fail, if for example, the binary sequence is finite or if it has only finitely many$0$s). Nevertheless, for any function$g:\N\to \N$there is a binary function$f:\N\to 2$coding it in the way we have described, and in any model$M\models R_f$, the binary universal algorithm will compute$f$, causing this adapted algorithm to compute exactly$g$on all standard finite input, as desired. Finally, let me describe how to extend the result to work with models of set theory, rather than models of arithmetic. Suppose that$\ZFC^+$is a consistent c.e. extension of ZFC; perhaps it is ZFC itself, or ZFC plus some large cardinal axioms. Let$T=\ZFC^++\neg\Con(\ZFC^+)$be a slightly stronger theory, which is also consistent, by the incompleteness theorem. Since$T$interprets arithmetic, the theory of Rosser sentences applies, and so we may build the corresponding Rosser tree over$T$, and also we may undertake the binary universal algorithm using$T$as the initial theory. If$f:\N\to 2$is any binary function, then let$R_f$be the theory arising on the corresponding branch through the Rosser tree, and suppose$M\models R_f$. This is a model of$\ZFC^+$, which also thinks that$\ZFC^+$is inconsistent. So again, the universal algorithm will find plenty of proofs in this model, and as before, it will find the proofs in just the right order that the binary universal algorithm will compute exactly the function$f$. From this binary universal algorithm, one may again design an algorithm universal for all functions$g:\N\to\N$, as desired. One can also get another kind of universality. Namely, there is a program$r$, such that for any finite$s\subset\N$, there is a model$M$of$\PA$(or$\ZFC$, etc.) such that inside the model$M$, the program$r$will enumerate the set$s$and nothing more. One can obtain such a program$r$from the program$p$of the theorem: just let$r$run the universal binary program$p$until a double$0$is produced, and then interprets the finite binary string up to that point as the set$s$to output. Let me now also discuss another form of universality. Corollary There is a program$p$, such that for any model$M\models\PA+\Con(\PA)$and any function$f:M\to M$that is definable in$M$, there is an end-extension of$M$to a taller model$N\models\PA$such that in$N$, the function computed by program$p$agrees exactly with$f$on input in$M$. Proof We simply apply the main theorem inside$M$. The point is that if$M$thinks$\Con(\PA)$, then it can build what it thinks is the tree of Rosser extensions, and it will think that each step maintains consistency. So the theory$T_f$that it constructs will be consistent in$M$and therefore have a model (the Henkin model) definable in$M$, which will therefore be an end-extension of$M$. QED This last application has a clear affinity with a theorem of Woodin’s, recently extended by Rasmus Blanck and Ali Enayat. See Victoria Gitman’s posts about her seminar talk on those theorems: Computable processes can produce arbitrary outputs in nonstandard models, continuation. Alternative proof. Here is an alternative elegant proof of the theorem based on the comments below of Vadim Kosoy. Let$T$be any consistent computably axiomatizable theory interpreting PA, such as PA itself or ZFC or what have you. For any Turing machine program$e$, let$q(e)$be a program carrying out the following procedure: on input$n$, search systematically for a finite function$h:X\to\mathbb{N}$, with$X$finite and$n\in X$, and for a proof of the statement “program$p$does not agree with$h$on all inputs in$X$,” using the function$h$simply as a list of values for this assertion. For the first such function and proof that is found, if any, give as output the value$h(n)$. Since the function$e\mapsto q(e)$is computable, there is by Kleene’s recursion theorem a program$p$for which$p$and$f(p)$compute the same function, and furthermore,$T$proves this. So the program$p$is searching for proofs that$p$itself does not behave in a certain way, and then it is behaving in that way when such a proof is found. I claim that the theory$T$does not actually prove any of those statements, “program$p$does not agree with$h$on inputs in$X$,” for any particular finite function$h:X\to\mathbb{N}$. If it did prove such a statement, then for the smallest such function and proof, the output of$p$would indeed be$h$on all inputs in$X$, by design. Thus, there would also be a proof that the program did agree with this particular$h$, and so$T$would prove a contradiction, contrary to our assumption that it was consistent. So$T$actually proves none of those statements. In particular, the program$p$computes the empty function in the standard model of arithmetic. But also, for any particular finite function$h:X\to\mathbb{N}$, we may consistently add the assertion “program$p$agrees with$h$on inputs in$X$” to$T$, since$T$did not refute this assertion. For any function$f:\mathbb{N}\to\mathbb{N}$, let$T_f$be the theory$T$together with all assertions of the form “program$p$halts on input$n$with value$k$”, for the particular value$k=f(n)$. I claim that this theory is consistent, for if it is not, then by compactness there would be finitely many of the assertions that enable the inconsistency, and so there would be a finite function$h:X\to\mathbb{N}$, with$h=f\upharpoonright X$, such that$T$proved the program$p$does not agree with$h$on inputs in$X$. But in the previous paragraph, we proved that this doesn’t happen. And so the theory$T_f$is consistent. Finally, note that in any model of$T_f$, the program$p$computes the function$f$on standard input, because these assertions are exactly made in the theory. QED # Burak Kaya, Ph.D. March 2016 Burak Kaya successfully defended his dissertation, “Cantor minimal systems from a descriptive perspective,” on March 24, 2016, earning his Ph.D. degree at Rutgers University under the supervision of Simon Thomas. The dissertation committee consisted of Simon Thomas, Gregory Cherlin, Grigor Sargsyan and myself, as the outside member. The defense was very nice, with an extremely clear account of the main results, and the question session included a philosophical discussion on various matters connected with the dissertation, including the principle attributed to Gao that any collection of mathematical structures that has a natural Borel representation has a unique such representation up to Borel isomorphism, a principle that was presented as a Borel-equivalence-relation-theory analogue of the Church-Turing thesis. Abstract. In recent years, the study of the Borel complexity of naturally occurring classification problems has been a major focus in descriptive set theory. This thesis is a contribution to the project of analyzing the Borel complexity of the topological conjugacy relation on various Cantor minimal systems. We prove that the topological conjugacy relation on pointed Cantor minimal systems is Borel bireducible with the Borel equivalence relation$\newcommand\d{\Delta^+_{\mathbb{R}}}\d$. As a byproduct of our analysis, we also show that$\d$is a lower bound for the topological conjugacy relation on Cantor minimal systems. The other main result of this thesis concerns the topological conjugacy relation on Toeplitz subshifts. We prove that the topological conjugacy relation on Toeplitz subshifts with separated holes is a hyperfinite Borel equivalence relation. This result provides a partial affirmative answer to a question asked by Sabok and Tsankov. As pointed Cantor minimal systems are represented by properly ordered Bratteli diagrams, we also establish that the Borel complexity of equivalence of properly ordered Bratteli diagrams is$\d$. # Famous quotations in their original first-order language Historians everywhere are shocked by the recent discovery that many of our greatest thinkers and poets had first expressed their thoughts and ideas in the language of first-order predicate logic, and sometimes modal logic, rather than in natural language. Some early indications of this were revealed in the pioneering historical research of Henle, Garfield and Tymoczko, in their work Sweet Reason: We now know that the phenomenon is widespread! As shown below, virtually all of our cultural leaders have first expressed themselves in the language of first-order predicate logic, before having been compromised by translations into the vernacular.$\neg\lozenge\neg\exists s\ G(i,s)(\exists x\ x=i)\vee\neg(\exists x\ x=i)\left(\strut\neg\exists t\ \exists d\ \strut D(d)\wedge F(d)\wedge S_t(i,d)\right)\wedge\left(\strut\neg\exists t\ w\in_t \text{Ro}\right)\wedge\left(\strut \text{Ru}(i,y)\to \lozenge\text{C}(y,i,qb)\wedge \text{Ru}(i)\wedge\text{Ru}(i)\wedge\text{Ru}(i)\wedge\text{Ru}(i)\right)\neg B_i \exists g\ G(g)\forall b\ \left(\strut G(b)\wedge B(b)\to \exists x\ (D(b,x)\wedge F(x))\right)(\exists!w\ W_1(w)\wedge W_2(w)), \ \ \exists w\ W_1(w)\wedge W_2(w)\wedge S(y,w)$?$\exists s\ Y(s)\wedge S(s)\wedge \forall x\ L(x,s)\exists p\ \left[\forall c\ (c\neq p\to G(c))\right]\wedge\neg G(p)\exists l\ \left[L(l)\wedge \boxdot_l\left({}^\ulcorner\,\forall g\ \text{Gl}(g)\to \text{Gd}(g){}^\urcorner\right)\wedge\exists s\ \left(SH(s)\wedge B(l,s)\right)\right](\forall p\in P\ \exists c\in\text{Ch}\ c\in p)\wedge(\forall g\in G\ \exists c\in\text{Cr}\ c\in g)\forall x (F(w,x)\to x=F)B\wedge \forall x\ \left[S(x)\wedge T(x)\to \exists!w\ W(w)\wedge\text{Gy}(x,w)\wedge\text{Gi}(x,w)\right]\exists!x\ D(x)\wedge D(\ {}^\ulcorner G(i){}^\urcorner\ )\forall f\ \forall g\ \left(\strut H(f)\wedge H(g)\to f\sim g\right)\wedge\forall f\ \forall g\ \left(\strut\neg H(f)\wedge \neg H(g)\to \neg\ f\sim g\right)\exists w\ \left(\strut O(w)\wedge W(w)\wedge\exists s\ (S(s)\wedge L(w,s))\right)C(i)\to \exists x\ x=i\neg\neg\left(\strut H(y)\wedge D(y)\right)\neg (d\in K)\wedge\neg (t\in K)W(i,y)\wedge N(i,y)\wedge\neg\neg\lozenge L(i,y)\wedge \left(\strut \neg\ \frac23<0\to\neg S(y)\right)\lozenge \text{CL}(i)\wedge\lozenge C(i)\wedge \lozenge (\exists x\ x=i)\wedge B(i)\forall x\ K_x({}^\ulcorner \forall m\ \left[M(m)\wedge S(m)\wedge F(m)\to\boxdot\ \exists w\ M(m,w)\right]{}^\urcorner)\forall e\forall h\ \left(\strut G(e)\wedge E(e)\wedge H(h)\to \neg L(i,e,h)\right)\forall p\ \boxdot\text{St}(p)\lozenge^w_i\ \forall g\in G\ \lozenge (g\in C)\forall m\ (a\leq_C m)\forall t\ (p\geq t)\wedge \forall t\ (p\leq t)\forall x\ (F(x)\iff x=h)(\forall x\ \forall y\ x=y)\wedge(\exists x\ \exists y (x=x>y=y))\forall p\ \left(\strut\neg W(p)\to \neg S(p)\right)\forall p \left(\strut E(p)\to \forall h\in H\ A(p,h)\right)\$

Dear readers, in order to assist with this important historical work, please provide translations into ordinary English in the comment section below of any or all of the assertions listed above. We are interested to make sure that all our assertions and translations are accurate.

In addition, any readers who have any knowledge of additional instances of famous quotations that were actually first made in the language of first-order predicate logic (or similar) are encouraged to post comments below detailing their knowledge. I will endeavor to add such additional examples to the list.

Thanks to Philip Welch, to my brother Jonathan, and to Ali Sadegh Daghighi (in the comments) for providing some of the examples, and to Timothy Gowers for some improvements.