6
$\begingroup$

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.

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?

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Douglas Ulrich Dec 9 '16 at 18:09
  • $\begingroup$ 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). $\endgroup$ – Douglas Ulrich Dec 11 '16 at 21:45
  • $\begingroup$ 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. $\endgroup$ – Douglas Ulrich Dec 11 '16 at 21:49
4
$\begingroup$

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})$.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Douglas Ulrich Dec 12 '16 at 18:54
  • $\begingroup$ All right, if you are happy with it, so much the better. $\endgroup$ – Emil Jeřábek supports Monica Dec 12 '16 at 19:54
1
$\begingroup$

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).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.