Given any incomplete theory and an unprovable sentence $\varphi$, are there always strictly weaker consistent unprovable statements?

Question

Given a theory $T$ and unprovable sentences $\phi$ and $\theta$, I say $\phi$ is strictly weaker than $\theta$ if $T \cup \{ \phi \} \vdash\theta$ but $T \cup \{ \theta \} \not \vdash \phi$. The questions are, given any theory $T$ and some unprovable sentence $\varphi$:

$(1)$ Is there an infinite chain of strictly weaker sentences?

$(2)$ What about a chain of strictly stronger sentences?

An example of where $(1)$ holds when the theory is $ZF$ and the sentence is $AC$, the class of sentences with $AC$ restricted to some definable infinite cardinal is the chain needed. However this chain is not dense ($a<b$ does not imply the existence of some $c$ such that $a<c<b$), and it has a minimal element (the axiom of countable choice), which are things I would like to avoid.

About $(2)$, clearly if there are an infinite number of unprovable sentences that $\varphi$ do not imply, then the chain can be constructed by strengthening $\varphi$ by writing it's conjunction with another unprovable sentence. However I don't know if that first condition holds in every incomplete theory.

Answer 1

In general, no, we need not have this situation.

For example, take the empty language and let $T=\{\forall x,y,z(x=y\vee x=z\vee y=z)\}$. Up to isomorphism there are exactly two elements of $T$, namely the one-element set and the two-element set (keep in mind that structures in the empty language are just sets). Up to $T$-provable equivalence, then, there are only four distinct sentences: the provable sentence $\top$, the disprovable sentence $\perp$, and the independent sentences $\exists x,y(x\not=y)$ and $\forall x,y(x=y)$. To convince yourself of this, note that we can think of a sentence up to logical equivalence as just its collection of isomorphism types of models, and since there are only two models of $T$ up to isomorphism there are only four collections of models of $T$ up to isomorphism.

However, this is fairly artificial. For theories like $\mathsf{ZFC}$ - that is, theories which let us "implement mathematics" - we do indeed always have weaker independent sentences:

If $\varphi$ is independent of $\mathsf{ZFC}$ then there is some $\theta$ which is also independent of $\mathsf{ZFC}$ such that $\mathsf{ZFC\cup\{\varphi\}}\vdash\theta$ but $\mathsf{ZFC\cup\{\theta\}\not\vdash\varphi}$.

Proof: Fix a sentence $\varphi$ which is independent of $\mathsf{ZFC}$ and consider the new theory $T=\mathsf{ZFC}\cup\{\neg\varphi\}$. By Godel's incompleteness theorem, $T$ must be incomplete; let $\eta$ be independent of $T$. But now consider the sentence $\eta\rightarrow\varphi$. Obviously $\mathsf{ZFC}\cup\{\varphi\}\vdash\eta\rightarrow\varphi$, so we just need to show $\mathsf{ZFC}\cup\{\eta\rightarrow\varphi\}\not\vdash\varphi$.

To do this, first note that $T\cup\{\neg\eta\}$ is consistent since $\eta$ is independent of $T$. In particular, this means that that $T\cup\{\neg\eta\}\not\vdash\varphi$, since $\neg\varphi\in T$. But we also have $\mathsf{ZFC}\subseteq T$ (by definition) and $\{\neg\eta\}\vdash\eta\rightarrow\varphi$ (since an implication with false hypothesis is true), so a fortiori we have $\mathsf{ZFC}\cup\{\eta\rightarrow\varphi\}\not\vdash\varphi$.

So as desired, $\eta\rightarrow\varphi$ is strictly weaker than $\varphi$. And we've used nothing about $\mathsf{ZFC}$ other than that it is essentially incomplete (= every computably axiomatizable theory containing it is incomplete), so the same argument applies to (first-order) Peano arithmetic and all the other theories subject to Godel.

---

Incidentally, it may be helpful to frame things algebraically. Given a theory $T$, for sentences $\varphi,\psi$ in the language of $T$ write "$\varphi\trianglelefteq\psi$" iff $T\vdash\varphi\rightarrow\psi$ (equivalently: iff $T\cup\{\varphi\}\vdash\psi$) and write "$\varphi\equiv\psi$" iff $T\vdash\varphi\leftrightarrow\psi$.

For example:

• Every Lindenbaum algebra is a Boolean algebra (at least in classical logic), with Boolean structure corresponding to the logical connectives: least upper bounds are given by $\vee$, greatest lower bounds by $\wedge$, complementation by $\neg$, and the top and bottom elements are $\top$ and $\perp$ respectively.

  • Note that weaker sentences are higher in the Lindenbaum algebra; this may be counterintuitive at first, but it's ultimately quite convenient.

• An inconsistent theory has a one-element Lindenbaum algebra. A complete consistent theory has a two-element Lindenbaum algebra. If $T\subseteq S$, then the Lindenbaum algebra of $S$ is a quotient of the Lindenbaum algebra of $T$ (adding more axioms makes the theory bigger but the algebra smaller).

• Any Boolean algebra with no coatoms (maximal non-$1$ elements) also has no atoms (minimal non-$0$ elements). Essential incompleteness of a theory implies the nonexistence of coatoms, hence for purely algebraic reasons the nonexistence of atoms; so in a precise sense, the proof above that $\mathsf{ZFC}$ has no "weakest possible independent sentences" was purely algebraic (Godel's theorem says no coatoms, so we in turn get no atoms).

• More generally, thinking about the complement operation in a Boolean algebra we have that when a given property holds of a given Lindenbaum algebra, so does its "dual property" (e.g. "No coatoms" vs. "No atoms," "Arbitrary joins exist" vs. "Arbitrary meets exist," etc.).

This algebraic approach to logic is super useful; it shows up in model theory in a "geometric" guise as the space of types, and it's also the motivating idea for the subject of algebraic logic.

Answer 2

No. For instance, consider two different finitely axiomatizable complete theories in the same language, one axiomatized by the sentence $\varphi$ and one axiomatized by the sentence $\psi$ (for instance, $\varphi$ and $\psi$ could be complete descriptions of two non-isomorphic finite structures over the same finite language). Let $T=\{\varphi\vee\psi\}$. Then every model of $T$ is either a model of $\varphi$ or a model of $\psi$, and so every sentence is either true in every model of $T$, true in no model of $T$, true exactly in the models of $\varphi$, or true exactly in the models of $\psi$. In particular, there are only four different equivalence classes of sentences, so there cannot be any infinite chains of inequivalent sentences.

More generally, for any theory $T$, the set of sentences modulo equivalence (given $T$) form a Boolean algebra (the Lindenbaum-Tarski algebra of $T$), and you are asking whether this Boolean algebra has an infinite strictly increasing or decreasing chain. In general, every infinite Boolean algebra has both infinite strictly increasing or decreasing chains. So, there are infinite chains of strictly stronger and strictly weaker sentences unless this Boolean algebra is finite, or equivalently unless there are only finitely many complete theories that extend $T$.

(Even then, there may not be such infinite chains if you ask for them to start from a particular sentence $\varphi$. Asking for a chain of strictly stronger sentences starting from some particular sentence $\varphi$ is equivalent to asking for an infinite strictly descending chain in the Lindenbaum-Tarski algebra of the theory $T\cup\{\varphi\}$, so you would need to have infinitely many different complete theories extending $T\cup\{\varphi\}$, not just $T$. Dually, a chain of strictly weaker sentences starting from $\varphi$ is equivalent to an infinite strictly ascending chain in the Lindenbaum-Tarski algebra of $T\cup\{\neg\varphi\}$.)