What feature(s) must a (non 1st-order) language with proper-class-many formulas have in order to guarantee that:

There is a proper class P of formulas such that both

(a) every set-sized sub-collection of P is satisfiable, and

(b) no proper-class-sized sub-collection of P is satisifable?

  • $\begingroup$ Do you know of any such class P of formulas? $\endgroup$
    – Wojowu
    Dec 6 '15 at 15:30

Let me give a few examples.

Example 1. Let us work in Gödel-Bernays set theory, and assume that $T\subset {}^{<\text{Ord}}2$ is a proper class tree of height Ord, but there is no cofinal branch.

(This theory is consistent relative to an inaccessible cardinal, because if $\kappa$ is inaccessible and not weakly compact, then there is a $\kappa$-Aronszajn tree $T\subset {}^{<\kappa}2$, and then $V_\kappa$ with all subsets is a model of GBC where $T$ has the desired property.)

In the logic $L_{\infty,\omega}$, which allows arbitrary sized conjunctions and disjunctions, with a constant for every element of $T$ and a unary predicate symbol $B$, consider the theory $P$ consisting of the assertions $\varphi_\alpha$ asserting first, that there is precisely one object $u$ on level $\alpha$ of the tree that satisfies $B$, and secondly, that in this case, every $v<_T u$ also has $B(v)$. These assertions can be made in the logic $L_{\infty,\omega}$ using constants for the elements of $T$. Thus, altogether, $P$ is the theory asserting that $B$ is a cofinal branch through the tree.

Every set-sized subtheory of $P$ mentions only a bounded number of levels, and so we can find a model by picking any node above that bound and using the predecessors of that node as the instantiation of $B$.

But under our assumptions that the tree $T$ is Ord-Aronszajn, there can be no model of all of $P$ or even of a proper class sized subtheory of $P$, because any such subtheory will involve the assertions concerning unboundedly many levels of $T$, and so the model of that subtheory will pick out a cofinal branch in $T$; but there is no such branch.

Meanwhile, there is a strong connection between your property and (non)weak compactness, because an inaccessible cardinal $\kappa$ is weakly compact just in case we have the $\kappa$-compactness property for $L_{\kappa,\kappa}$ theories of size $\kappa$. (And there are diverse variations on this.)

Example 2. Here is a different kind of related example using only first-order logic.

Theorem. There is a proper class first-order theory $P$, such that every set-sized subtheory of $P$ has a model, but no class is a model of the whole of $P$.

Proof. We interpret this as a theorem scheme in ZFC, where by "class" we mean a definable class (allowing parameters). Thus, I shall provide a definition of a theory $P$, and then prove first, that every set-sized subtheory of $P$ is satisfiable, and second, that no definable class is a model of $P$.

Let $P$ be the theory in the language of set theory $\in$ augmented with a predicate $\newcommand\Tr{\text{Tr}}\Tr$, meant to serve as a truth-predicate, plus a constant for every object in the universe. The theory $P$ asserts that $\Tr$ obeys all instances of the recursive Tarskian truth definition:

  • $\Tr(a\in b)$ just in case $a\in b$ holds.
  • $\Tr(a=b)$ just in case $a=b$.
  • $\Tr(\varphi\wedge\psi)$ just in case $\Tr(\varphi)$ and $\Tr(\psi)$.
  • $\Tr(\neg\varphi)$ just in case $\Tr(\varphi)$ does not hold.
  • $\Tr(\exists x\ \varphi)$ just in case there is $a$ such that $\Tr(\varphi(a))$.

For any set many such assertions, we can find a model, since we can find some $V_\theta$ large enough to contain all the parameters mentioned in the subtheory, and then use truth in $\langle V_\theta,\in\rangle$, which will satisfy all the assertions made in the subtheory.

But no definable class can satisfy $P$, because this is exactly the content of Tarski's theorem on the non-definability of truth. QED

Meanwhile, this theory $P$ of the theorem does has proper-class sized subtheories that are satisfiable, since we could, for example, restrict to the quantifier-free assertions; since there are so many constants, we can produce proper class trivially satisfiable subtheories.

  • $\begingroup$ Joel, Thank you! In Example 2's theorem, can "no class is a model of the whole of P" be strengthened to "no class is a model of any class-sized sub theory of P"? Is there a 1st order theory such that no proper-class-sized sub-theory is satisfiable (but every set-sized sub-theory is satisfiable)? $\endgroup$
    – Haidar
    Dec 6 '15 at 15:56
  • $\begingroup$ The first example now has this feature, but the second example has trivial proper class satisfiable subtheories. Perhaps one can modify it. $\endgroup$ Dec 6 '15 at 16:05
  • 1
    $\begingroup$ @Your first example can be arranged without appeal to the consistency of an inaccessible, since it is known that in every model of ZF + V = HOD there is a definable Ord-tree (a tree of height Ord each proper initial segment of which is a set) which has no definable branches. This follows from one of the main results of the following paper of mine: $\endgroup$
    – Ali Enayat
    Dec 6 '15 at 19:36
  • $\begingroup$ Continuation of my comment (pressed the enter button inadvertantly): researchgate.net/profile/Ali_Enayat2/… $\endgroup$
    – Ali Enayat
    Dec 6 '15 at 19:39
  • 1
    $\begingroup$ @Joel: oops! The paper is entitled "Power-like models of set theory" (JSL, 2001) $\endgroup$
    – Ali Enayat
    Dec 6 '15 at 19:55

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.