Skip to main content
MathOverflow

Return to Answer

added 382 characters in body
Source Link
Joel David Hamkins
Joel David Hamkins
  • 236.2k
  • 44
  • 777
  • 1.4k

Let me give twoa few examples.

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 first-order atomic diagram ofassertions $T$$\varphi_\alpha$ asserting first, together with the assertions that the elements satisfyingthat there is precisely one object $u$ on level $\alpha$ of the predicate tree that satisfies $B$ are linearly ordered by the tree order, and furthermoresecondly, that in this case, every $v<_T u$ also has $B(v)$. These assertions can be made in the statementslogic $L_{\infty,\omega}$ using constants for each level of the tree that precisely one element on that level is inelements of $B$$T$. Thus Thus, altogether, $P$ is the theory asserting that    $B$ is a cofinal cofinal branch through the tree.

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 a model wouldsubtheory will involve determinethe assertions concerning unboundedly many levels of $T$, and so the model of that subtheory will pick out a cofinal branch throughin $T$, and; but there is no such branch branch.

Example 2. But next, let me giveHere is a much betterdifferent kind of related example, using a purely first-order language. You had alluded to the possibility that there might be noonly first-order example, but this isn't quite right, because of set/class issueslogic.

Let $P$ be the theory in the language of set theory $\in$ augmented with a predicate $\newcommand\Tr{\text{Tr}}\Tr$, meant to to serve as a truth truth-predicate, plus a constant for every object in the the universe. The The theory $P$ asserts that $\Tr$ obeys all instances instances of the recursive 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))$.

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.

Let me give two examples.

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 first-order atomic diagram of $T$, together with the assertions that the elements satisfying the predicate $B$ are linearly ordered by the tree order, and furthermore, the statements for each level of the tree that precisely one element on that level is in $B$. Thus, $P$ is the theory asserting that  $B$ is a cofinal branch through the tree.

But under our assumptions that the tree $T$ is Ord-Aronszajn, there can be no model of all of $P$, because such a model would determine a cofinal branch through $T$, and there is no such branch.

Example 2. But next, let me give a much better example, using a purely first-order language. You had alluded to the possibility that there might be no first-order example, but this isn't quite right, because of set/class issues.

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(\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))$.

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

Let me give a few examples.

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.

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.

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

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

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.

added 35 characters in body
Source Link
Joel David Hamkins
Joel David Hamkins
  • 236.2k
  • 44
  • 777
  • 1.4k

Let $P$ be the theory in the language of set theory $\in$ augmented with a predicate $Tr$$\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$$\Tr$ obeys all instances of the recursive Tarskian truth definition:

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

Let $P$ be the theory in the language of set theory $\in$ augmented with a predicate $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(\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))$.

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(\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))$.
Source Link
Joel David Hamkins
Joel David Hamkins
  • 236.2k
  • 44
  • 777
  • 1.4k

Let me give two 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 first-order atomic diagram of $T$, together with the assertions that the elements satisfying the predicate $B$ are linearly ordered by the tree order, and furthermore, the statements for each level of the tree that precisely one element on that level is in $B$. Thus, $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$, because such a model would determine a cofinal branch through $T$, and 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. But next, let me give a much better example, using a purely first-order language. You had alluded to the possibility that there might be no first-order example, but this isn't quite right, because of set/class issues.

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 $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(\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