# A “Completion” of $ZFC^-$

Let $T_0$ be the set theory axiomatized by $ZFC^-$ (that is $ZFC$ without powerset) + every set is countable + $\mathbb{V}=\mathbb{L}$.

Question 1: Suppose $\phi$ is a sentence of set theory. Must there be a large cardinal axiom $A$ such that $\phi$ is decided by $T_0$ + "there are transitive set models of $A$ of arbitrarily high ordinal height?"

Update: no.

Question 2: Is there a set $T$ of $\Pi_2$ sentences, such that $ZFC^- \cup T$ is complete?

Update: no, essentially. See my answer below.

Questions 3 and 4 after comments.

• Question 1 is related to, but different from several previous questions on Mathoverflow, e.g. Nice Algebraic Statements Independent from ZF + V=L (constructibility) or On statements independent of ZFC + V=L or Natural statements independent from true $\Pi^0_2$ sentences. Regarding the first two---Hamkins gives a long list of examples of things independent of $\mathbb{V}= \mathbb{L}$, but it seems that my schema takes care of all of them. (Of course in those questions $ZFC$ was assumed.)
• Moreover, Question 1 was partly motivated by Dorais' answer to the second question above, which references a question of Shelah from The Future of Set Theory.
• I'm leaving "large cardinal axiom" undefined here (so Question 1 can't be formalized), but obviously we should exclude inconsistent axioms, or things like $ZFC +$ "there are no transitive set models of ZFC."
• If we pick a definition of large cardinal axiom", then "every set is countable" + $\mathbb{V}=\mathbb{L}$ + "there are transitive set models of $A$ of arbitrarily high ordinal height" (for each large cardinal axiom $A$) is a set of $\Pi_2$ sentences. So a negative answer to Question 2 implies a negative answer to Question 1.

• We can ignore (recursive) large cardinal axiom schemas $\Gamma$ because we can just replace them by $ZFC_0$+"there is a transitive set model of $\Gamma$" where $ZFC_0$ is some large enough finite fragment of $ZFC$. In particular we don't have to write "$ZFC + A$".

• $T_0$ + this axiom schema (loosely speaking) is of personal significance to me: in fact I believe it to be true. (Namely, given whatever universe of sets $\mathbb{V}$ in which we are working, it seems reasonable to suppose there is a larger universe of sets $\mathbb{W} \models \mathbb{V}=\mathbb{L}$ in which $\mathbb{V}$ is countable, or such that $\mathbb{W}$ is a model of a given large cardinal axiom $A$. Ergo,...)

Let $\mathcal{L}_{\mbox{set}}$ be the language of set theory $\{\in\}$ and let $\mathcal{L}_1$ be $\mathcal{L}_{\mbox{set}} \cup \{P\}$, $P$ a new unary relation symbol. Let $T_1$ be $T_0$ + the axioms asserting that $P \subseteq \mbox{ON}$ is stationary (for $\in$-definable classes) and for every $\alpha \in P$, $(\mathbb{V}_\alpha, \in) \preceq (\mathbb{V}, \in)$. We insist that large cardinal axioms $A$ be sentences of $\mathcal{L}_{\mbox{set}}$.

Question 3: Suppose $\phi$ is a sentence of set theory (i.e. of $\mathcal{L}_{\mbox{set}}$). Must there be a large cardinal axiom $A$ such that $\phi$ is decided by $T_1$ + "there are transitive set models of $A$ of arbitrarily high ordinal height?"

Question 4: Is there a set $T$ of $\Pi_2$ sentences of set theory, such that $T_1 \cup T$ decides every sentence of set theory?

• Incidentally there is a lot of redundancy in $T_1$; for instance if we replaced $ZFC^-$ by $KP$ (Kripke-Platek set theory) we would get the same theory. – Douglas Ulrich Dec 9 '16 at 18:09
• Unsurpisingly, one gets into trouble if you have $T_1$ say that for all $\alpha \in P$, $(\mathbb{V}_\alpha, \in, P) \preceq (\mathbb{V}, \in, P)$. While this theory does make sense, it is in fact inconsistent (it defines truth). – Douglas Ulrich Dec 11 '16 at 21:45
• Also, $T_1$ is equivalent to adding a truth predicate $\Gamma$, and then saying $\{\alpha: (\mathbb{V}_\alpha, \in) \preceq (\mathbb{V}, \in)\}$ is stationary for $\in$-definable classes. – Douglas Ulrich Dec 11 '16 at 21:49

Without a definition of “large cardinal axiom”, I’m going to ignore Q1 and Q3.

The answers to Q2 and Q4 are negative by the following general principle. (For Q4, we take $T_0$ to be the set of $\mathcal L_{\mathrm{set}}$-consequences of $T_1$.)

$\DeclareMathOperator\Tr{Tr}\DeclareMathOperator\Wit{Wit}\let\eq\leftrightarrow\def\gonu#1{\ulcorner#1\urcorner}\let\ob\overline$Proposition: Let $T_0$ be an r.e. theory interpreting Robinson’s arithmetic, and $\Gamma$ a set of sentences for which $T_0$ has a truth predicate $\Tr_\Gamma(x)$, that is, $$\tag{*}T_0\vdash\phi\eq\Tr_\Gamma(\ob{\gonu\phi})$$ for all $\phi\in\Gamma$. Then no extension of $T_0$ by a set of $\Gamma$-sentences is a consistent complete theory.

Proof: Let $S\subseteq\Gamma$, and assume for contradiction that $T=T_0+S$ is consistent and complete. The basic idea of the proof is that we can define in $T$ a truth predicate $\Tr(x)$ for all sentences as “$x$ is $T_0$-provable from a set of true $\Gamma$-sentences”, contradicting Tarski’s theorem on the undefinability of truth.

In more detail, we fix an interpretation of, say, $S^1_2$ in $T_0$ so that we have basic coding of sequences of integers, and a (polynomial-time) proof predicate for $T_0$. We define $\Wit(w,x)$ to be the formula

“the sequence $w$ is a $T_0$-proof of a sentence $x$ from extra axioms, each of which is a sentence $a\in\Gamma$ such that $\Tr_\Gamma(a)$,”

and we put

$$\Tr(x)\eq\exists w\,(\Wit(w,x)\land\forall w'<w\,\neg\Wit(w',\gonu{\neg x})).$$

Claim: Whenever $T$ proves a sentence $\phi$, it also proves $\Tr(\ob{\gonu\phi})$. Whenever $T$ proves $\neg\phi$, it also proves $\neg\Tr(\ob{\gonu\phi})$.

Using the Claim, we can easily finish the proof of the Proposition: by Gödel’s diagonal lemma, there is a sentence $\alpha$ such that

$$T_0\vdash\alpha\eq\neg\Tr(\ob{\gonu\alpha}).$$

Since $T$ is complete, it proves $\alpha$ or $\neg\alpha$. If $T\vdash\alpha$, then $T$ proves $\neg\Tr(\ob{\gonu\alpha})$ by the definition of $\alpha$, and $\Tr(\ob{\gonu\alpha})$ by the Claim, hence $T$ is inconsistent, contrary to our assumptions. The case $T\vdash\neg\alpha$ is similar.

Now, to prove the Claim, assume $T\vdash\phi$. We can fix a $T_0$-proof of $\phi$ from some $\psi_1,\dots,\psi_k\in S$, which has a standard Gödel number $n$.

By $\Sigma^0_1$-completeness, $T$ proves that $\ob n$ is a $T_0$-proof of $\ob{\gonu\phi}$ from $\ob{\gonu{\psi_1}},\dots,\ob{\gonu{\psi_k}}$. Moreover, $T$ proves each $\psi_i$, hence also $\Tr_\Gamma(\ob{\gonu{\psi_i}})$ by $(*)$. Thus,

$$T\vdash\Wit(\ob n,\ob{\gonu{\phi}}).$$

On the other hand, let $m<n$, we will show

$$T\vdash\neg\Wit(\ob m,\ob{\gonu{\neg\phi}}).$$

This again follows by $\Sigma^0_1$-completeness unless $m$ is an actual Gödel number of an actual $T_0$-proof of $\neg\phi$ from some sentences $\chi_1,\dots,\chi_l\in\Gamma$. Since $T$ also proves $\phi$, this means

$$T\vdash\neg\chi_1\lor\dots\lor\neg\chi_l,$$

hence

$$T\vdash\neg\Tr_\Gamma(\ob{\gonu{\chi_1}})\lor\dots\lor\neg\Tr_\Gamma(\ob{\gonu{\chi_l}})$$

by $(*)$, hence $T\vdash\neg\Wit(\ob m,\ob{\gonu{\neg\phi}})$ as needed.

Since $T$ knows that the only numbers below $\ob n$ are $\ob0,\dots,\ob{n-1}$, we have established $T\vdash\Tr(\ob{\gonu\phi})$.

The second part of the Claim is similar: assuming $T\vdash\neg\phi$, we fix its standard proof with Gödel number $n$, and we show

$$T\vdash\Wit(\ob n,\ob{\gonu{\neg\phi}})$$

and

$$T\vdash\neg\Wit(\ob m,\ob{\gonu\phi})$$

for all $m\le n$, which implies $T\vdash\neg\Tr(\ob{\gonu\phi})$.

• Q1 and Q3 are resolved by this also: defining "large cardinal axioms" amounts to picking a certain subset of $\Gamma$, and so we can apply your proposition. – Douglas Ulrich Dec 12 '16 at 18:54
• All right, if you are happy with it, so much the better. – Emil Jeřábek supports Monica Dec 12 '16 at 19:54

Overnight the following occurred to me...

The answer to Question 2 is negative (with an asterisk), and so the same is true of Question 1. Namely, let $T$ be a set of $\Pi_2$ sentence with $ZFC^- \cup T$ consistent; I claim that $ZFC^- \cup T$ does not resolve whether the class of ordinals $\alpha$ such that $\mathbb{V}_\alpha \models ZFC^-$ is stationary. In particular $ZFC^- \cup T$ does not resolve the following sentence $\phi$:

"There is $\alpha$ such that $\mathbb{V}_\alpha \models ZFC^-$ and $\mathbb{V}_\alpha \preceq_2 \mathbb{V}$."

This sentence makes sense since we can define satisfaction for formulas of bounded complexity. This is a particular instance of the schema asserting "$\{\alpha: \mathbb{V}_\alpha \models ZFC^-\}$ is stationary", since the set $\{\alpha: \mathbb{V}_\alpha \preceq_2 \mathbb{V}\}$ is club.

We assume $ZFC^- \cup T \cup \{\phi\}$ is consistent (if not then $T$ is silly---this is the asterisk). On the other hand, $ZFC^- \cup T \cup \{\lnot \phi\}$ is consistent, since given $\mathbb{V} \models ZFC^- \cup T \cup \{\phi\}$, if we let $\alpha$ be least such that $\mathbb{V}_\alpha \models ZFC^-$ and $\mathbb{V}_\alpha \preceq_2 \mathbb{V}$, then $\mathbb{V}_\alpha \models ZFC^- \cup T \cup \{\lnot \phi\}$.

We can play the same game whenever $T$ is a set of $\Pi_n$ sentences, and when we replace $ZFC^-$ by any (stronger) recursive theory.

The truth that we would like to express, but can't, is that the class $\{\alpha: \mathbb{V}_\alpha \preceq \mathbb{V}\}$ is stationary. Since I'm the OP I feel justified in raising the bar for the question; see Question 3 and Question 4 (new).