5
$\begingroup$

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?

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

1 Answer 1

5
$\begingroup$

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.

$\endgroup$
22
  • $\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
    Commented Dec 6, 2015 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$ Commented Dec 6, 2015 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
    Commented Dec 6, 2015 at 19:36
  • $\begingroup$ Continuation of my comment (pressed the enter button inadvertantly): researchgate.net/profile/Ali_Enayat2/… $\endgroup$
    – Ali Enayat
    Commented Dec 6, 2015 at 19:39
  • 1
    $\begingroup$ @Joel: oops! The paper is entitled "Power-like models of set theory" (JSL, 2001) $\endgroup$
    – Ali Enayat
    Commented Dec 6, 2015 at 19:55

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .