# Modality definability in Kripke’s theory of truth

James Walsh

###### Abstract.

In _Outline of a Theory of Truth_ , Kripke introduces some of the central
concepts of the logical study of truth and paradox. He informally defines some
of these—such as groundedness and paradoxicality—using modal locutions. We
introduce a modal language for regimenting these informal definitions. Though
groundedness and paradoxicality are expressible in the modal language, we
prove that intrinsicality—which Kripke emphasizes but does not define
modally—is not. We characterize the modally definable relations and completely
axiomatize the modal semantics.

Thanks to Dan Appel, Reid Dale, Noah Schweber, Ted Slaman, and Kentarô
Yamamoto for helpful discussion. Thanks to Neil Barton, Wes Holliday, and
Andrew Lee for comments on drafts.

##  1\. Introduction

In _Outline of a Theory of Truth_ , Kripke writes that

> It has long been recognized that some of the intuitive trouble with Liar
> sentences is shared with such sentences as [the truth-teller, i.e., “This
> sentence is true”] which, though not paradoxical, yield no determinate truth
> conditions.  ([5], p. 693)

So _paradoxicality_ is just one of the troubling features that self-
referential sentences can exhibit. Others are _ungroundedness_ and _non-
intrinsicality_. One of the great successes of Kripke’s theory is that it
facilitates a classification of sentences according to these properties.
Kripke informally describes groundedness and paradoxicality using modal
locutions.

> …[The truth-teller] is ungrounded, but not paradoxical. This means that we
> _could_ consistently use the predicate ‘true’ so as to give [the truth-
> teller] a truth value, though [we need] not do so.…[The liar] _cannot_ have
> a truth value…. We _could_ consistently use the word ‘true’ so as to give a
> truth value to such a sentence as [the truth-teller] …. The same does not
> hold for the paradoxical sentences.  ([5], p. 708, emphasis added111Except
> to the first instance of ‘could’, which is emphasized in the original.)

Yet Kripke does not describe the intrinsic sentences using modal locutions.
This is a striking contrast. Is it a mere coincidence that modal locutions
appear in the description of the grounded and paradoxical sentences but not of
the intrinsic sentences? Or does it reflect some inherent discrepancy between
the objects being defined?

The standard way of studying these objects obviates this question. In
particular, Kripke replaces the informal _modal_ glosses on paradoxicality and
groundedness with official _extensional_ mathematical definitions.
Nevertheless, the modal glosses are nice examples of modality occurring
naturally in a logico-mathematical context, so it is worth regimenting them in
a way that retains their modal flavor. For the purposes of taking these modal
definitions “at face value,” we introduce a modal language and an attendant
interpretation $\mathbf{FIX}$. Our modal language is propositional, but it
contains structured atomic formulas (like in first-order logic) as opposed to
propositional variables. In particular, there are atomic formulas of the form:

$T(x)\quad\text{for ``$x$ is true''}$ $F(x)\quad\text{for ``$x$ is false''.}$

We also use $N(x)$ is an abbreviation for $\neg T(x)\wedge\neg F(x)$. Kripke’s
informal modal definitions of groundedness and paradoxicality are
straightforwardly formalizable in this setting.

We provide a complete and decidable axiomatization of the modal semantics. We
introduce the following axioms:

$\displaystyle\mathbf{Con}$ $\displaystyle\quad\neg\big{(}T(x)\wedge
F(x)\big{)}$ $\displaystyle\mathbf{Ground}$ $\displaystyle\quad(\lozenge
T(x)\wedge\lozenge F(x))\to\lozenge N(x)$ $\displaystyle\mathbf{Min_{n}}$
$\displaystyle\quad\big{(}\lozenge N(x_{1})\wedge\dots\wedge\lozenge
N(x_{n})\big{)}\to\lozenge\big{(}N(x_{1})\wedge\dots\wedge N(x_{n})\big{)}$

and define $\mathbf{S5[Con,Ground,Min_{n}]}$ as the normal modal logic that
results from adjoining these axioms to $\mathbf{S5}$. Our main completeness
theorem is the following:

######  Theorem.

For all formulas $\varphi$ with $n$ variables, the following are equivalent:

  1. (i)

$\mathbf{FIX}\Vdash\varphi$

  2. (ii)

$\mathbf{S5[Con,Ground,Min_{n}]}\vdash\varphi$

This completeness theorem falls out of an exact characterization of the sets
(and, in general, the $n$-ary relations) that are modally definable over
$\mathbf{FIX}$. From this characterization, we infer that the set of intrinsic
sentences is _not_ modally indefinable. Thus, it is not a mere coincidence
that Kripke does not lapse into modal language when defining intrinsicality.
Indeed, we are able to show that the intrinsic sentences are indiscernible
within the modal language from another set, namely, the set of _inevitable_
sentences, which we define later in the paper. The characterization of the
modally definable sets builds on a classic normal form theorem for
$\mathbf{S5}$ from [2]. According to Carnap’s theorem, every formula is
$\mathbf{S5}$-equivalent to a disjunction of formulas in a very special form.
This normal form result and its corollaries adumbrated here resemble classic
results in model theory (particular, results in o-minimality and quantifier
elimination). We conclude with a discussion of this analogy.

##  2\. Kripke’s Theory of Truth

In this section we review the relevant aspects of Kripke’s theory of truth
[5]. Kripke presents a flexible framework and emphasizes that it can be
developed in various specific ways. We will focus on a specific implementation
that Kripke highlights, namely, the strong Kleene fixed point construction.

Let $\mathcal{L}$ be the first-order language of arithmetic. Let
$\mathcal{L}_{T}$ be the language of arithmetic augmented with the unary
predicate $\mathsf{True}(x)$. Some presentations also include a predicate
$\mathsf{False}(x)$, but one may interpret falsity as truth-of-negation,
whence the second predicate is strictly unnecessary. As usual,
$\ulcorner\varphi\urcorner$ is the Gödel number of the $\mathcal{L}_{T}$
sentence $\varphi$ according to some standard Gödel numbering.

###  2.1. Strong Kleene logic

Kripke defines his interpretations of $\mathcal{L}_{T}$ using the trivalent
logic $\mathsf{K3}$, also known as the strong Kleene logic. According to
$\mathsf{K3}$, a structure $w$ can stand in one of three semantic relations
with a formula $\varphi$:

  * •

$w\vDash_{\mathsf{K3}}\varphi$, i.e., $\varphi$ is true in $w$

  * •

$w\mathrel{\mathchoice{\reflectbox{$\displaystyle\vDash$}}{\reflectbox{$\textstyle\vDash$}}{\reflectbox{$\scriptstyle\vDash$}}{\reflectbox{$\scriptscriptstyle\vDash$}}}_{\mathsf{K3}}\varphi$,
i.e., $\varphi$ is false in $w$

  * •

$w\uparrow_{\mathsf{K3}}\varphi$ i.e., $\varphi$ is neither in $w$

The semantics of conjunction is given by the following clauses:

  * •

$w\vDash_{\mathsf{K3}}\varphi\wedge\psi$ if $w\vDash_{\mathsf{K3}}\varphi$ and
$w\vDash_{\mathsf{K3}}\varphi$

  * •

$w\mathrel{\mathchoice{\reflectbox{$\displaystyle\vDash$}}{\reflectbox{$\textstyle\vDash$}}{\reflectbox{$\scriptstyle\vDash$}}{\reflectbox{$\scriptscriptstyle\vDash$}}}_{\mathsf{K3}}\varphi\wedge\psi$
if
$w\mathrel{\mathchoice{\reflectbox{$\displaystyle\vDash$}}{\reflectbox{$\textstyle\vDash$}}{\reflectbox{$\scriptstyle\vDash$}}{\reflectbox{$\scriptscriptstyle\vDash$}}}_{\mathsf{K3}}\varphi$
or
$w\mathrel{\mathchoice{\reflectbox{$\displaystyle\vDash$}}{\reflectbox{$\textstyle\vDash$}}{\reflectbox{$\scriptstyle\vDash$}}{\reflectbox{$\scriptscriptstyle\vDash$}}}_{\mathsf{K3}}\psi$

  * •

$w\uparrow_{\mathsf{K3}}\varphi$ otherwise.

The semantics of negation is given by the following clauses:

  * •

$w\vDash_{\mathsf{K3}}\neg\varphi$ if
$w\mathrel{\mathchoice{\reflectbox{$\displaystyle\vDash$}}{\reflectbox{$\textstyle\vDash$}}{\reflectbox{$\scriptstyle\vDash$}}{\reflectbox{$\scriptscriptstyle\vDash$}}}_{\mathsf{K3}}\varphi$

  * •

$w\mathrel{\mathchoice{\reflectbox{$\displaystyle\vDash$}}{\reflectbox{$\textstyle\vDash$}}{\reflectbox{$\scriptstyle\vDash$}}{\reflectbox{$\scriptscriptstyle\vDash$}}}_{\mathsf{K3}}\neg\varphi$
if $w\vDash_{\mathsf{K3}}\varphi$

  * •

$w\uparrow_{\mathsf{K3}}\neg\varphi$ otherwise.

The semantics of the universal quantifier is given by the following clauses:

  * •

$w\vDash_{\mathsf{K3}}\forall x\;\varphi(x)$ if for every $d\in w$,
$w\vDash_{\mathsf{K3}}\varphi(d)$.

  * •

$w\mathrel{\mathchoice{\reflectbox{$\displaystyle\vDash$}}{\reflectbox{$\textstyle\vDash$}}{\reflectbox{$\scriptstyle\vDash$}}{\reflectbox{$\scriptscriptstyle\vDash$}}}_{\mathsf{K3}}\forall
x\;\varphi(x)$ if for some $d\in w$,
$w\mathrel{\mathchoice{\reflectbox{$\displaystyle\vDash$}}{\reflectbox{$\textstyle\vDash$}}{\reflectbox{$\scriptstyle\vDash$}}{\reflectbox{$\scriptscriptstyle\vDash$}}}_{\mathsf{K3}}\varphi(d)$.

  * •

$w\uparrow_{\mathsf{K3}}\forall x\;\varphi(x)$ otherwise.

###  2.2. Classification of sentences

Kripke introduces a large collection of 3-valued (true, false, neither) models
for $\mathcal{L}_{T}$. These 3-valued models are typically called “fixed
points,” since Kripke defines them as the fixed points of a certain function
(namely, the Kripke jump). The details of this function are not important for
us, but the “fixed points” terminology is ubiquitous, so we will continue to
use it.

######  Remark 2.1.

Each fixed point $w$ has the following properties:

  1. (1)

For each $\varphi$, $\varphi$ and $\mathsf{True}(\ulcorner\varphi\urcorner)$
have the same semantic value in $w$.

  2. (2)

$w$ is consistent, i.e., there is no $\varphi$ such that
$w\Vdash_{\mathsf{K3}}\varphi$ and $w\Vdash_{\mathsf{K3}}\neg\varphi$.

  3. (3)

Hence, there is no $\varphi$ such that
$w\Vdash_{\mathsf{K3}}\mathsf{True}(\ulcorner\varphi\urcorner)\wedge\mathsf{True}(\ulcorner\neg\varphi\urcorner)$

For any formula $\varphi(x)$ in the language of $\mathcal{L}_{T}$, we can
formulate an $\mathcal{L}_{T}$ sentence $\psi$ which “says”
$\varphi(\ulcorner\psi\urcorner)$. In particular, $\psi$ and
$\varphi(\ulcorner\psi\urcorner)$ have the same semantic value in each fixed
point. For instance, there are $\mathcal{L}_{T}$ sentences
$\lambda,\tau,\gamma$ such that:

  * •

$\lambda$ has the same semantic value as
$\neg\mathsf{True}(\ulcorner\lambda\urcorner)$ in every fixed point.

  * •

$\tau$ has the same semantic value as $\mathsf{True}(\ulcorner\tau\urcorner)$
in every fixed point.

  * •

$\gamma$ has the same semantic value as
$\mathsf{True}(\ulcorner\gamma\urcorner)\vee\neg\mathsf{True}(\ulcorner\gamma\urcorner)$
in every fixed point.

In fact, there are many such sentences. We will sometimes appeal to this fact,
which is well-known in the theory of truth literature:

######  Remark 2.2.

There are infinitely many logically independent truth-teller sentences. That
is, there is an infinite collection $T$ of sentences such that:

  * •

For all $\tau\in T$, $\tau$ has the same semantic value as
$\mathsf{True}(\ulcorner\tau\urcorner)$ in every fixed point.

  * •

For any sequence $\tau_{1},\dots,\tau_{n}$ of sentences from $T$ and any
assignment of true, false, and neither to $\tau_{1},\dots,\tau_{n}$, there is
a fixed point realizing exactly that truth-value assignment.

######  Definition 2.3.

A sentence is _grounded_ just in case (i) it has the value true in all models
or (ii) it has the value false in all models.

######  Remark 2.4.

There is a _minimum_ fixed point in which all ungrounded sentences have the
value neither. Hence, a sentence is _ungrounded_ just in case it has the value
neither in some fixed point. The following claims follow:

  1. (1)

If a sentence has value true in one fixed point and false in another, then it
has value neither in the minimum fixed point.

  2. (2)

If $\varphi_{1},\dots,\varphi_{n}$ are ungrounded, then they all have value
neither in the minimum fixed point.

The liar $\lambda$ , truth-teller $\tau$, and tautology-teller $\gamma$ are
all ungrounded, so they all have value neither in the minimum model.

######  Definition 2.5.

A sentence is _paradoxical_ just in case it has value neither in all models.

The liar $\lambda$ is paradoxical. But the truth-teller $\tau$ and tautology-
teller $\gamma$ are not paradoxical:

  * •

$\tau$ has value true in some models and value false in others.

  * •

$\gamma$ has value true in some models and does not have the value false in
any models.

Though neither $\tau$ nor $\gamma$ is paradoxical, it is worth noting that
$\gamma$ alone cannot take on both of the binary truth values. We introduce
the following definition to discuss this property of $\gamma$:

######  Definition 2.6.

A sentence is _inevitable_ if it has one of the binary truth-values in some
fixed point and the other binary truth-value in no fixed point.

Any grounded sentence is inevitable. There are also ungrounded inevitable
sentences. For instance, if $\tau$ is a truth-teller, then the sentence
$\tau\vee\neg\tau$ is inevitable (inevitably true) as is $\tau\wedge\neg\tau$
(inevitably false).

_Informally_ , the intrinsic sentences are those inevitable sentences whose
truth/falsity does not depend on any _arbitrary_ sentences. Here is a more
precise definition:

######  Definition 2.7.

A fixed point $w$ is _intrinsic_ if for every fixed point $v$,

$\\{\varphi\mid\varphi\text{ is {true} in }w\\}\cup\\{\varphi\mid\varphi\text{
is {true} in }v\\}$

is consistent. A sentence $\varphi$ is _intrinsic_ if it is true or false in
an intrinsic fixed point.

Note that inevitability and intrinsicality come apart. The tautology-teller
$\gamma$ is both intrinsic and inevitable. By contrast, $\tau\vee\neg\tau$ is
inevitable but not intrinsic. The issue is that any fixed point which makes
$\tau\vee\neg\tau$ true must either make $\tau$ true or $\neg\tau$ true. So
$\tau\vee\neg\tau$ can only be made true by making a binary truth-value
assignment that is incompatible with other possible binary truth-value
assignments.

##  3\. Modal Systems

In this section we introduce our modal framework, including the language,
semantics, and axiom systems. Let’s start with a presentation of the modal
language. In what follows:

  * •

$\mathcal{X}$ is a countably infinite set of variables.

  * •

$T$ and $F$ are one-place predicate symbols.

  * •

$\neg$, $\wedge$, and $\Box$ are sentential connectives.

######  Definition 3.1.

The formulas of $\mathcal{L}_{\Box}$ are defined as follows:

$\varphi::=T(x)\mid
F(x)\mid\neg\varphi\mid(\varphi\wedge\varphi)\mid\Box\;\varphi$

That is, a formula is a predicate applied to a variable, a negation of a
formula, a conjunction of formulas, or a box appended to a formula. Though
$\vee,\to,\leftrightarrow,\lozenge$ are not officially part of the language we
sometimes use these symbols as abbreviations in the standard way. Note that
the language $\mathcal{L}_{\Box}$ neither contains quantifiers nor
propositional variables.

For the rest of this paper we will be working with this signature, i.e., with
predicates $T$ and $F$. For instance, when we discuss the modal logic
$\mathbf{S5}$, we mean the modal logic $\mathbf{S5}$ _in this signature_.

######  Definition 3.2.

$\mathbf{S5}$ is the classical modal logic containing all instances of the
following axioms:

$\displaystyle\mathbf{K}$ $\displaystyle\quad\Box(A\to B)\to(\Box A\to\Box B)$
$\displaystyle\mathbf{T}$ $\displaystyle\quad\Box A\to A$
$\displaystyle\mathbf{5}$ $\displaystyle\quad\lozenge A\to\Box\lozenge A$

and closed under the following rule:

$\displaystyle\mathbf{RN}$ $\displaystyle\quad\text{If $A$ is a theorem, so is
$\Box A$}.$

We will now introduce models for interpreting the formal system $\mathbf{S5}$.

######  Definition 3.3.

For a set $W$, a _variable assignment_ $V$ is a pair of functions
$V_{1},V_{2}:\mathcal{X}\to\mathcal{P}(W)$.

######  Definition 3.4.

Given $w\in W$ and variable assignment $V$, we define $\Vdash_{V}$ as follows:

  * •

$W,w\Vdash_{V}T(x)$ if $w\in V_{1}(x)$.

  * •

$W,w\Vdash_{V}F(x)$ if $w\in V_{2}(x)$.

  * •

$W,w\Vdash_{V}\neg\varphi$ if $W,w\nVdash_{V}\varphi$.

  * •

$W,w\Vdash_{V}\varphi\wedge\psi$ if $W,w\Vdash_{V}\varphi$ and
$W,w\Vdash_{V}\psi$.

  * •

$W,w\Vdash_{V}\Box\;\varphi$ if for all $v\in W$, $W,v\Vdash_{V}\varphi$.

We say that $W\Vdash_{V}\varphi$ if for all $w\in W$, $W,w\Vdash_{V}\varphi$.

We will be particularly interested in a particular $\mathbf{S5}$ structure.

######  Definition 3.5.

Let $\mathbf{FIX}$ be the set of Kripke’s fixed points, i.e., the set of
Kripke’s 3-valued $\mathcal{L}_{T}$ models. An _$\mathcal{L}_{T}$
-realization_ is a function $\star:\mathcal{X}\to\mathcal{L}_{T}$, i.e., a
mapping from variables to $\mathcal{L}_{T}$ formulas. Each
$\mathcal{L}_{T}$-realization $\star$ determines a variable assignment
$V^{\star}$:

  1. (i)

$V^{\star}_{1}(x)$ is the set of models in which $x^{\star}$ is true.

  2. (ii)

$V^{\star}_{2}(x)$ is the set of models in which $x^{\star}$ is false.

$\mathbf{FIX}\Vdash\varphi$ just in case
$\mathbf{FIX}\Vdash_{V^{\star}}\varphi$ for every
$\mathcal{L}_{T}$-realization $\star$.

For any $\star$, $\mathbf{FIX}\Vdash_{V^{\star}}\mathbf{S5}$. In fact,
$\mathbf{FIX}$ validates other principles that can be stated in the modal
language $\mathcal{L}_{\Box}$.

######  Definition 3.6.

$\mathbf{S5[Con]}$ extends $\mathbf{S5}$ with the following axiom:

$\mathbf{Con}\quad\neg\big{(}T(x)\wedge F(x)\big{)}.$

In what follows, $N(x)$ is an abbreviation for the formula:

$\neg T(x)\wedge\neg F(x).$

######  Definition 3.7.

$\mathbf{S5[Con,Ground]}$ extends $\mathbf{S5[Con]}$ with the following axiom:

$\mathbf{Ground}\quad(\lozenge T(x)\wedge\lozenge F(x))\to\lozenge N(x).$

We will introduce more axioms as they are needed. For now we note the
following.

######  Proposition 3.8.

For any $\star$, $\mathbf{FIX}\Vdash_{V^{\star}}\mathbf{S5[Con,Ground]}$.

###### Proof.

By Remark 2.1 and Remark 2.4. ∎

##  4\. Single Variable Definability

The motivations discussed in the introduction concerned definability of _sets_
, such as the set of grounded sentences. To study definability of sets, it
suffices to focus on 1-formulas (i.e., formulas with a single variable).
Accordingly, in this section we will limit our attention to 1-formulas. We
will turn to $n$-formulas for $n>1$ in subsequent sections. Characterizing the
definable sets is much easier than characterizing the definable $n$-ary
relations, so this section will also serve as a warm up for the later
sections.

######  Definition 4.1.

An $\mathcal{L}_{\Box}$ formula $\varphi(x)$ _defines_ $\mathcal{A}$ over
$\mathbf{FIX}$ just in case for every $\mathcal{L}_{T}$-realization $\star$:

$\mathbf{FIX}\Vdash_{V^{\star}}\varphi(x)\Longleftrightarrow
x^{\star}\in\mathcal{A}.$

Let’s provide some examples:

$\displaystyle x\text{ is grounded }$
$\displaystyle:=\Box\;T(x)\vee\Box\;F(x)$ $\displaystyle x\text{ is
paradoxical }$ $\displaystyle:=\neg\lozenge T(x)\wedge\neg\lozenge F(x)$
$\displaystyle x\text{ is inevitable }$ $\displaystyle:=\big{(}\lozenge
T(x)\wedge\neg\lozenge F(x)\big{)}\vee\big{(}\neg\lozenge T(x)\wedge\lozenge
F(x)\big{)}$

One conspicuous absence from the list is _intrinsicality_. This is not an
oversight. One goal of this section is to show that the intrinsic sentences
have no modal definition.

###  4.1. Normal Forms

One of our main tools will be a normal form theorem due to [2]. Let’s begin by
drawing a distinction between two kinds of formulas.

######  Definition 4.2.

An _extensional_ formula is one without any modal operators. An _intensional_
formula is one all of whose variables occurs only in the scope of a modal
operator.

Note that the distinction between extensional and intensional formulas is
exclusive but not exhaustive.

######  Definition 4.3.

Let $\Gamma$ be a set of formulas and $T$ a modal system. A formula $\varphi$
is _$\Gamma$ -maximal_ for $T$ if each of the following holds:

  1. (1)

$T+\varphi$ is consistent

  2. (2)

$\varphi\in\Gamma$

  3. (3)

For every $\psi\in\Gamma$, one of the following holds:

    1. (a)

$T\vdash\varphi\to\psi$

    2. (b)

$T\vdash\varphi\to\neg\psi$

The following notion is inspired by the model-theoretic notion of an isolated
type:

######  Definition 4.4.

The _extensional 1-isolators_ for $T$ are the $\Gamma$-maximal formulas for
$T$ where $\Gamma$ is the set of extensional 1-formulas.

######  Proposition 4.5.

The extensional 1-isolators for $\mathbf{S5}$:

  1. (i)

$T(x)\wedge F(x)$

  2. (ii)

$T(x)\wedge\neg F(x)$

  3. (iii)

$\neg T(x)\wedge F(x)$

  4. (iv)

$\neg T(x)\wedge\neg F(x)$

$\mathbf{S5[Con]}$ refutes (i) and makes the additional conjuncts in (ii) and
(iii) redundant. Hence, we have the following:

######  Proposition 4.6.

The extensional 1-isolators for $\mathbf{S5[Con]}$ are:

$T(x),F(x),N(x)$

There is an analogous notion of intensional 1-isolators:

######  Definition 4.7.

The _intensional 1-isolators_ for $T$ are the $\Gamma$-maximal formulas for
$T$ where $\Gamma$ is the set of intensional 1-formulas.

Let’s restrict our attention to $\mathbf{S5[Con]}$ and its extensions. Here is
how we characterize the intensional 1-isolators of such a system. We begin by
considering all formulas of the form:

${}^{+}_{\neg}\lozenge T(x)\wedge^{+}_{\neg}\lozenge
F(x)\wedge^{+}_{\neg}\lozenge N(x)$

That is, for each of the extensional 1-isolators, we choose whether it is
possible or not and add that choice as a conjunct. Call these the _intensional
pre-1-isolators_. To isolate the intensional 1-isolators we must figure out
which of the intensional pre-1-isolators are consistent.

$\mathbf{S5[Con]}$ refutes exactly one of the intensional pre-1-isolators.

$\mathbf{S5[Con]}\vdash\neg\big{(}\neg\lozenge T(x)\wedge\neg\lozenge
F(x)\wedge\neg\lozenge N(x)\big{)}$

$\mathbf{S5[Con,Ground]}$ refutes one more in addition:

$\mathbf{S5[Con,Ground]}\vdash\neg\big{(}\lozenge T(x)\wedge\lozenge
F(x)\wedge\neg\lozenge N(x)\big{)}$

######  Definition 4.8.

A _1-isolator_ for $T$ is a $T$-consistent conjunction $\varphi\wedge\psi$
where $\varphi$ is an extensional 1-isolator and $\psi$ is an intensional
1-isolator.

We are now ready to state Carnap’s theorem. To make sense of Carnap’s theorem,
recall the convention that an empty disjunction of formulas is just a
contradiction.

######  Theorem 4.9 (essentially [2]).

For $T$ extending $\mathbf{S5}$:

  1. (1)

Every extensional 1-formula is $T$ equivalent to a disjunction of extensional
1-isolators for $T$.

  2. (2)

Every intensional 1-formula is $T$ equivalent to a disjunction of intensional
1-isolators for $T$.

  3. (3)

Every 1-formula is $T$ equivalent to a disjunction of 1-isolators for $T$.

###  4.2. Counting

[2] calculates the number of formulas up to provable equivalence in the modal
_logic_ $\mathbf{S5}$. Note the emphasis on the word _logic_. The system that
Carnap studies is in the typical language of modal logic, i.e., without the
predicates $T,F$ but with propositional variables $p_{1},p_{2},\dots$. There
are far more equivalence classes of 1-formulas in our system $\mathbf{S5}$
than in the modal logic Carnap studied.

######  Proposition 4.10.

Up to $\mathbf{S5}$-equivalence, there are exactly $4{,}294{,}967{,}296$ many
1-formulas.

###### Proof.

Let’s introduce some abbreviations:

$B(x)$:

$T(x)\wedge F(x)$

$T_{only}(x)$:

$T(x)\wedge\neg F(x)$

$F_{only}(x)$:

$\neg T(x)\wedge F(x)$

$N(x)$:

$\neg T(x)\wedge\neg F(x)$

$\mathbf{S5}$ has 4 extensional 1-isolators and 15 intensional 1-isolators,
namely, all formulas of the form:

${}^{+}_{\neg}\lozenge B(x)\wedge^{+}_{\neg}\lozenge
T_{only}(x)\wedge^{+}_{\neg}\lozenge F_{only}(x)\wedge^{+}_{\neg}\lozenge
N(x)$

except for the one with all negations.

Each extensional 1-isolator is inconsistent with the intensional 1-isolators
claiming that it is impossible, and consistent otherwise.

So, for instance, $B(x)$ is consistent with all and only those intensional
1-isolators of the form:

$\lozenge B(x)\wedge^{+}_{\neg}\lozenge T_{only}(x)\wedge^{+}_{\neg}\lozenge
F_{only}(x)\wedge^{+}_{\neg}\lozenge N(x)$

of which there are exactly $2^{3}=8$.

A 1-isolator is a consistent conjunction of an extensional 1-isolator and an
intensional 1-isolator. So there are $4\times 8=32$ many 1-isolators for
$\mathbf{S5}$. Hence, the number of formulas up to provable equivalence is
exactly $2^{32}=4{,}294{,}967{,}296$. ∎

######  Proposition 4.11.

Up to $\mathbf{S5[Con]}$-equivalence, there are exactly $4096$ 1-formulas.

###### Proof.

We approach this calculation in a similar way. This time the extensional
1-isolators are $T(x),F(x),N(x)$.

Focus on $T(x)$ for a moment. It is consistent with all and only those
intensional 1-isolators of the form:

$\lozenge T(x)\wedge^{+}_{\neg}\lozenge F(x)\wedge^{+}_{\neg}\lozenge N(x)$

of which there are exactly $2^{2}=4$.

A 1-isolator is a consistent conjunction of an extensional 1-isolator and an
intensional 1-isolator. So there are $3\times 4=12$ many 1-isolators for
$\mathbf{S5[Con]}$. Hence, the number of formulas up to provable-equivalence
is exactly $2^{12}=4096$. ∎

######  Proposition 4.12.

Up to $\mathbf{S5[Con,Ground]}$-equivalence, there are exactly $1024$
1-formulas.

###### Proof.

Again, the extensional 1-isolators are $T(x),F(x),N(x)$.

Focus on $T(x)$ for a moment. It is consistent with all and only those
intensional 1-isolators of the form:

$\lozenge T(x)\wedge^{+}_{\neg}\lozenge F(x)\wedge^{+}_{\neg}\lozenge N(x)$

_except_ (by the $\mathbf{Ground}$ axiom) for

$\lozenge T(x)\wedge\lozenge F(x)\wedge\neg\lozenge N(x).$

So $T(x)$ is consistent with $2^{2}-1=4-1=3$ intensional 1-isolators.
Likewise, $F(x)$ is consistent with $3$ intensional 1-isolators. $N(x)$ is
consistent with $4$ (there is no need to delete one since we focus on formulas
including $\lozenge N(x)$).

A 1-isolator is a consistent conjunction of an extensional 1-isolator and an
intensional 1-isolator. So there are $3+3+4=10$ many 1-isolators for
$\mathbf{S5[Con]}$. Hence, the number of formulas up to provable-equivalence
is exactly $2^{10}=1024$. ∎

###  4.3. Completeness

In this subsection we present a complete axiomatization of the one-variable
fragment of the modal theory of $\mathbf{FIX}$. Completeness follows easily
from Carnap’s normal form theorem. The connection between normal forms and
completeness theorems was explored previously in [3]. We extend this result to
the full modal language in a later section.

######  Lemma 4.13.

For any 1-isolator $\varphi$, if $\varphi$ is
$\mathbf{S5[Con,Ground]}$-consistent, then there is some $\star$ and some $w$
such that $\mathbf{FIX},w\Vdash_{V^{\star}}\varphi$.

###### Proof.

Suppose $\varphi$ is a 1-isolator, i.e.,
$\varphi=\varepsilon(x)\wedge\iota(x)$ where $\varepsilon(x)$ is an
extensional 1-isolator and $\iota(x)$ is an intensional 1-isolator.
$\mathbf{S5[Con,Ground]}\vdash\varepsilon(x)\to\lozenge\varepsilon(x)$. Hence
$\iota(x)$ has $\lozenge\varepsilon(x)$ as a conjunct.

We now break into cases depending on which extensional 1-isolator
$\varepsilon(x)$ is. In each case we will break into subcases, checking each
intensional 1-isolator that has $\lozenge\varepsilon(x)$ as a conjunct. In
each subcase we find an assignment $\star$ that satisfies $\varphi$.

_Case 1:_ Suppose that $\varepsilon(x)$ is $T(x)$. We must check the following
intensional 1-isolators:

  1. (i)

$\iota(x)=\lozenge T(x)\wedge\lozenge F(x)\wedge\lozenge N(x)$. Let
$x^{\star}=\tau$. Then there is some $w$ such that
$\mathbf{FIX},w\Vdash_{V^{\star}}\varepsilon(x)\wedge\iota(x)$.

  2. (ii)

$\iota(x):=\lozenge T(x)\wedge\neg\lozenge F(x)\wedge\lozenge N(x)$. Let
$x^{\star}=\gamma$. Then there is some $w$ such that
$\mathbf{FIX},w\Vdash_{V^{\star}}\varepsilon(x)\wedge\iota(x)$.

  3. (iii)

$\iota(x):=\lozenge T(x)\wedge\neg\lozenge F(x)\wedge\neg\lozenge N(x)$. Let
$x^{\star}=0=0$. Then for any $w$,
$\mathbf{FIX},w\Vdash_{V^{\star}}\varepsilon(x)\wedge\iota(x)$.

We leave Cases 2 ($\varepsilon(x)$ is $F(x)$) and 3 ($\varepsilon(x)$ is
$N(x)$) to the reader. ∎

######  Theorem 4.14.

For all 1-formulas $\varphi\in\mathcal{L}_{\Box}$, the following are
equivalent:

  1. (i)

$\mathbf{FIX}\Vdash\varphi$

  2. (ii)

$\mathbf{S5[Con,Ground]}\vdash\varphi$

###### Proof.

The soundness direction is Proposition 3.8. Let’s focus on completeness.
Suppose that $\mathbf{S5[Con,Ground]}\nvdash\varphi$. Then, by classical
logic, $\mathbf{S5[Con,Ground]}+\neg\varphi$ is consistent. By Theorem 4.9,

$\mathbf{S5[Con,Ground]}\vdash\neg\varphi\leftrightarrow(\psi_{1}\vee\dots\vee\psi_{k})$

where each $\psi_{i}$ is a 1-isolator. By classical logic, at least one of
these 1-isolators $\psi_{i}$ is consistent. By Lemma 4.13, we infer that there
is some $\star$ such that $\mathbf{FIX}\Vdash_{V^{\star}}\psi_{i}$. Hence
$\mathbf{FIX}\Vdash_{V^{\star}}\neg\varphi$, so $\mathbf{FIX}\nVdash\varphi$.
∎

######  Proposition 4.15.

Every $\mathbf{FIX}$-definable $A\subseteq\mathcal{L}_{T}$ is definable by a
(possibly empty) disjunction of intensional 1-isolators for
$\mathbf{S5[Con,Ground]}$.

###### Proof.

Every $\mathbf{FIX}$-definable $A\subseteq\mathcal{L}_{T}$ is definable by an
intensional 1-formula. Indeed, if $\varphi$ defines $A$, then this means that
exactly the elements of $A$ satisfy $\varphi$ at _every_ world. So
$\Box\varphi$ also defines $A$. The result follows since every intensional
1-formula is equivalent to a disjunction of intensional 1-isolators (see
Theorem 4.9). ∎

######  Corollary 4.16.

The number of $\mathbf{FIX}$-definable sets is exactly $64$.

###### Proof.

There are exactly $6$ intensional 1-isolators for $\mathbf{S5[Con,Ground]}$.
$2^{6}=64$. The result then follows from Proposition 4.15. ∎

###  4.4. Descriptive complexity

In this subsection we will finally fulfill our promise to prove the following
result:

######  Theorem 4.17.

The set of intrinsic sentences is not $\mathbf{FIX}$-definable.

There are multiple ways of verifying this, and we will present two. One could
check all 64 single variable definitions, although this would be tedious.
Luckily, there are more conceptual arguments.

Every $\mathbf{FIX}$-definable is definable by an intensional 1-formula. This
is because if $\varphi$ $\mathbf{FIX}$-defines a set $\mathcal{A}$, then so
does $\Box\varphi$. We have already seen that each intensional 1-formula is
$\mathbf{S5[Con,Ground]}$-equivalent to a disjunction of intensional
1-isolators. So, pushing quantifiers in, we see that every modal definition is
equivalent to a formula of the following form:

$\big{(}{}_{\lozenge}^{\Box}{}_{\neg}^{+}{}_{F}^{T}(x)\wedge\dots\wedge{}_{\lozenge}^{\Box}{}_{\neg}^{+}{}_{F}^{T}(x)\big{)}\vee\dots\vee({}_{\lozenge}^{\Box}{}_{\neg}^{+}{}_{F}^{T}(x)\wedge\dots\wedge{}_{\lozenge}^{\Box}{}_{\neg}^{+}{}_{F}^{T}(x)\big{)}$

Let’s say that any such formula is in _basic form_.

######  Definition 4.18.

Let $\mathsf{Fix}$ be an $\mathcal{L}_{2}$ formula defining the set of fixed
points. We define a translation that maps $\star:\mathcal{L}_{\Box}$ formulas
in basic form to $\mathcal{L}_{2}$ formulas.

$(A\vee\dots\vee A)^{\star}:=A^{\star}\vee\dots\vee A^{\star}$

$(\Box_{F}^{T}(x))^{\star}:=\forall
X\big{(}\mathsf{Fix}(X)\to\ulcorner_{F}^{T}(x)^{\star}\urcorner\in X\big{)}$

$(\Box\neg_{F}^{T}(x))^{\star}:=\forall
X\big{(}\mathsf{Fix}(X)\to\ulcorner_{F}^{T}(x)^{\star}\urcorner\notin
X\big{)}$

$(\lozenge_{F}^{T}(x))^{\star}:=\exists
X\big{(}\mathsf{Fix}(X)\wedge\ulcorner_{F}^{T}(x)^{\star}\urcorner\in
X\big{)}$

$(\lozenge\neg_{F}^{T}(x))^{\star}:=\exists
X\big{(}\mathsf{Fix}(X)\wedge\ulcorner_{F}^{T}(x)^{\star}\urcorner\notin
X\big{)}$

$T(x)^{\star}=x$

$F(x)^{\star}=Neg(x^{\star})$

######  Lemma 4.19.

If $\varphi$ modally defines $A$, then $\varphi^{\star}$ defines $A$ over the
standard interpretation of second-order arithmetic.

###### Proof.

This follows directly by analyzing the semantics of the modal language. ∎

######  Theorem 4.20.

Every modally definable set is
$\mathsf{Boolean}\text{-}\Sigma^{1}_{1}$-definable in the language of second-
order arithmetic.

###### Proof.

The set of fixed points is $\Delta^{1}_{1}$-definable (see [1, §6]). In
particular, we can choose a $\Sigma^{1}_{1}$ formula $\mathsf{Fix}$ defining
the set of fixed points. ∎

The desired indefinability result then follows from the following theorem:

######  Theorem 4.21 ([1]).

The set of intrinsic sentences is $\Sigma^{1}_{1}$-complete in a $\Pi^{1}_{1}$
parameter.

######  Corollary 4.22.

The set of intrinsic sentences is not modally definable.

###### Proof.

No $\Sigma^{1}_{1}$-complete in a $\Pi^{1}_{1}$ parameter set admits a
$\mathsf{Boolean}\text{-}\Sigma^{1}_{1}$ definition. ∎

###  4.5. Indiscernibility

The previous result demonstrates the non-definability of a great number of
sets, but it is a coarse tool. For instance, descriptive complexity
considerations do not yield the non-definability of the arithmetic truths,
since they form a $\Delta^{1}_{1}$ set, but the the arithmetic truths are not
definable.

We will now prove the indefinability of the intrinsic sentences in another
way. Informally, sets $\mathcal{A}$ and $\mathcal{B}$ are
$\mathbf{FIX}$-indiscernible just in case every formula that applies to the
$\mathcal{A}$s applies to the $\mathcal{B}$s and vice-versa. We will prove
that the intrinsic sentences and the inevitable sentences are
$\mathbf{FIX}$-indiscernible, whence the set of intrinsic sentences—the
smaller of the two sets—cannot be definable.

######  Definition 4.23.

$\mathcal{A}$ and $\mathcal{B}$ are $\mathbf{FIX}$_-indiscernible_ if for
every $\varphi(x)\in\mathcal{L}_{\Box}$, TFAE:

  1. (1)

For all $\star$ with $x^{\star}\in\mathcal{A}$,
$\mathbf{FIX}\Vdash_{\mathbf{V^{\star}}}\varphi(x)$.

  2. (2)

For all $\star$ with $x^{\star}\in\mathcal{B}$,
$\mathbf{FIX}\Vdash_{\mathbf{V^{\star}}}\varphi(x)$.

######  Theorem 4.24.

The set of intrinsic sentences and the set of inevitable sentences are
$\mathbf{FIX}$-indiscernible.

###### Proof.

Let $\mathcal{A}$ be the set of intrinsic and $\mathcal{B}$ the set of
inevitable sentences. Then (2) implies (1) (Definition 4.23) is trivial.

It suffices to check that (1) implies (2). So assume (1), i.e.,

$\oplus\quad\text{For all $\star$ with $x^{\star}$ intrinsic,
$\mathbf{FIX}\Vdash_{\mathbf{V^{\star}}}\varphi(x)$}.$

We may assume that $\varphi$ is an intensional formula (if it is not, just
stick a $\Box$ in front of it). We may then assume that $\varphi$ is in normal
form, i.e., $\varphi$ is a disjunction of intensional 1-isolators.

Now the intensional 1-isolators are the following six formulas:

  1. (i)

$\lozenge T(x)\wedge\lozenge F(x)\wedge\lozenge N(x)$

  2. (ii)

$\lozenge T(x)\wedge\neg\lozenge F(x)\wedge\lozenge N(x)$

  3. (iii)

$\neg\lozenge T(x)\wedge\lozenge F(x)\wedge\lozenge N(x)$

  4. (iv)

$\lozenge T(x)\wedge\neg\lozenge F(x)\wedge\neg\lozenge N(x)$

  5. (v)

$\neg\lozenge T(x)\wedge\lozenge F(x)\wedge\neg\lozenge N(x)$

  6. (vi)

$\neg\lozenge T(x)\wedge\neg\lozenge F(x)\wedge\lozenge N(x)$

Note that the set of inevitable sentences is defined by the disjunction
$(ii)\vee(iii)\vee(iv)\vee(v)$.

Suppose, for the sake of contradiction, that (2) fails. Then there is some
$\star$ such that $y^{\star}=\psi$ is inevitable and that
$\mathbf{FIX}\nVdash_{\mathbf{V^{\star}}}\varphi(y)$. So $\varphi$ must be
missing one of the disjuncts required to define the inevitable sentences,
i.e., (ii)–(iv). Let’s break into cases.

_Case 1:_ $\varphi$ is missing disjunct (ii). But $\gamma$ is intrinsic and
$ii(\gamma)$. So if $x^{\star}=\gamma$, then
$\mathbf{FIX}\nVdash_{\mathbf{V^{\star}}}\varphi(x)$, contra $\oplus$.

_Case 2:_ $\varphi$ is missing disjunct (iii). But $\neg\gamma$ is intrinsic
and $iii(\neg\gamma)$. So if $x^{\star}=\neg\gamma$, then
$\mathbf{FIX}\nVdash_{\mathbf{V^{\star}}}\varphi(x)$, contra $\oplus$.

_Case 3:_ $\varphi$ is missing disjunct (iv). But $0=0$ is intrinsic and
$iv(0=0)$. So if $x^{\star}=0=0$, then
$\mathbf{FIX}\nVdash_{\mathbf{V^{\star}}}\varphi(x)$, contra $\oplus$.

_Case 4:_ $\varphi$ is missing disjunct (v). But $0=1$ is intrinsic and
$v(0=1)$. So if $x^{\star}=0=1$, then
$\mathbf{FIX}\nVdash_{\mathbf{V^{\star}}}\varphi(x)$, contra $\oplus$. ∎

######  Remark 4.25.

If $\mathcal{A}$ and $\mathcal{B}$ are $\mathbf{FIX}$-indiscernible and
$\mathcal{A}\subset\mathcal{B}$, then $\mathcal{A}$ is not
$\mathbf{FIX}$-definable. Hence Theorem 4.24 entails that the set of intrinsic
sentences is not $\mathbf{FIX}$-definable.

##  5\. Multivariable Definability

The logic and combinatorics become more involved—but also more
interesting—when there are many variables. 1-formulas are used to define
_sets_ of sentences. 2-formulas (i.e., formulas with two distinct variables)
are used to define _binary relations_ on sentences. Likewise, $n$-formulas
(i.e., formulas with $n$ distinct variables) are used to define _$n$ -ary
relations_ on sentences.

######  Definition 5.1.

An $\mathcal{L}_{\Box}$ formula $\varphi(x_{1},\dots,x_{n})$ _defines_
$\mathcal{A}$ over $\mathbf{FIX}$ just in case for every
$\mathcal{L}_{T}$-realization $\star$:

$\mathbf{FIX}\Vdash_{V^{\star}}\varphi(x_{1},\dots,x_{n})\Longleftrightarrow\langle
x_{1}^{\star},\dots,x_{n}^{\star}\rangle\in\mathcal{A}.$

###  5.1. Counting Formulas

Let’s begin with some relatively easy counting problems. We will turn to more
difficult counting problems in a later subsection.

####  5.1.1. The Bare Modal System

Carnap’s normal form theorems generalize to $n$ variables. We summarize the
important information for $\mathbf{S5}$ with the following bullets:

  * •

The _extensional $n$-isolators_ are the formulas of the form:

$\mathrel{\begin{subarray}{c}B\\\ T_{only}\\\ F_{only}\\\
N\end{subarray}}(x_{1})\wedge\dots\wedge\mathrel{\begin{subarray}{c}B\\\
T_{only}\\\ F_{only}\\\ N\end{subarray}}(x_{n})$

  * •

The _intensional pre-n-isolators_ are the formulas of the form:

${}^{+}_{\neg}\lozenge\varphi_{1}\wedge\dots\wedge^{+}_{\neg}\lozenge\varphi_{4^{n}}$

where $\varphi_{1},\dots,\varphi_{4^{n}}$ are the extensional $n$-isolators.

  * •

$\mathbf{S5}$ refutes exactly one of these, namely:

$\neg\lozenge\varphi_{1}\wedge\dots\wedge\neg\lozenge\varphi_{4^{n}}$

and the rest are the intensional $n$-isolators.

  * •

The $n$-isolators are the consistent conjunctions $\varphi\wedge\psi$ for
$\varphi$ an extensional $n$-isolator and $\psi$ an intensional $n$-isolator.

With this terminology on board, we can state the general version of Carnap’s
theorem:

######  Theorem 5.2 (essentially [2]).

For $T$ extending $\mathbf{S5}$:

  1. (1)

Every extensional $n$-formula is $T$ equivalent to a disjunction of
extensional $n$-isolators for $T$.

  2. (2)

Every intensional $n$-formula is $T$ equivalent to a disjunction of
intensional $n$-isolators for $T$.

  3. (3)

Every $n$-formula is $T$ equivalent to a disjunction of $n$-isolators for $T$.

Let’s solve a counting problem.

######  Proposition 5.3.

Up to $\mathbf{S5}$-provable equivalence, the number of $n$-formulas is
exactly: $2^{(4^{n}2^{(4^{n}-1)})}$.

###### Proof.

$\mathbf{S5}$ has $4^{n}$ extensional $n$-isolators and $2^{(4^{n})}-1$
intensional $n$-isolators.

Each extensional $n$-isolator is inconsistent with the intensional 1-isolators
claiming that it is impossible, and consistent otherwise.

So fixing a particular extensional $n$-isolator $\varepsilon$, there are
$2^{(4^{n}-1)}$ many intensional $n$-isolators with $\lozenge\varepsilon$ as a
conjunct.

So there are $4^{n}\times 2^{(4^{n}-1)}$ many $n$-isolators. So the number of
formulas up to provable equivalence is $2^{(4^{n}2^{(4^{n}-1)})}$. ∎

####  5.1.2. With the Consistency Axiom

Let’s turn out attention to $\mathbf{S5[Con]}$. We summarize the important
information in the following bullets:

  * •

The _extensional $n$-isolators_ are the formulas of the form:

$\mathrel{\begin{subarray}{c}T\\\ F\\\
N\end{subarray}}(x_{1})\wedge\dots\wedge\mathrel{\begin{subarray}{c}T\\\ F\\\
N\end{subarray}}(x_{n})$

  * •

The _intensional pre-n-isolators_ are the formulas of the form:

${}^{+}_{\neg}\lozenge\varphi_{1}\wedge\dots\wedge^{+}_{\neg}\lozenge\varphi_{3^{n}}$

where $\varphi_{1},\dots,\varphi_{3^{n}}$ are the extensional $n$-isolators.

  * •

$\mathbf{S5[Con]}$ refutes exactly one of these, namely:

$\neg\lozenge\varphi_{1}\wedge\dots\neg\lozenge\varphi_{3^{n}}$

and the rest are the intensional $n$-isolators.

  * •

The $n$-isolators are the consistent conjunctions $\varphi\wedge\psi$ for
$\varphi$ an extensional $n$-isolator and $\psi$ an intensional $n$-isolator.

######  Proposition 5.4.

Up to $\mathbf{S5[Con]}$-provable equivalence, the number of $n$-formulas is
exactly: $2^{(3^{n}2^{(3^{n}-1)})}$.

###### Proof.

$\mathbf{S5[Con]}$ has $3^{n}$ extensional $n$-isolators and $2^{(3^{n})}-1$
intensional $n$-isolators.

Each extensional $n$-isolator is inconsistent with the intensional 1-isolators
claiming that it is impossible, and consistent otherwise.

So fixing a particular extensional $n$-isolator $\varepsilon$, there are
$2^{(3^{n}-1)}$ many intensional $n$-isolators with $\lozenge\varepsilon$ as a
conjunct.

So there are $3^{n}\times 2^{(3^{n}-1)}$ many $n$-isolators. So the number of
formulas up to provable equivalence is $2^{(3^{n}2^{(3^{n}-1)})}$. ∎

###  5.2. Matrices

The combinatorics of definability is much harder when $n>1$. In this section,
for the sake of developing intuitions, we focus on the 2-variable case. Let’s
begin by considering this matrix:

TT | TF | TN
---|---|---
FT | FF | FN
NT | NF | NN
Table 1. All extensional 2-isolators.

We identify each cell of the matrix with an extensional 2-isolator. In
particular, we identify the cell AB with the formula $A(x_{1})\wedge
B(x_{2})$. For instance, we identify the cell TN with the formula
$T(x_{1})\wedge N(x_{2})$. This yields an association of extensional
2-isolators with pairs of numbers, via Table 2. We will often consider subsets
$\mathcal{S}$ of the $3\times 3$ matrix and we move freely between writing as
though $\mathcal{S}$ contains NN, $N(x_{1})\wedge N(x_{2})$, and (3,3),
trusting that no confusion will arise.

1,1 | 1,2 | 1,3
---|---|---
2,1 | 2,2 | 2,3
3,1 | 3,2 | 3,3
Table 2. Standard numbering of the $3\times 3$ matrix.

Each intensional 2-isolator for $\mathbf{S5[Con]}$ corresponds to a subset of
the $3\times 3$ matrix. In particular, each intensional 2-isolator has the
form:

$\bigwedge\\{\lozenge\varphi\mid\varphi\in\mathcal{S}\\}\wedge\bigwedge\\{\neg\lozenge\varphi\mid\varphi\notin\mathcal{S}\\}$

where $\mathcal{S}$ is some subset of the matrix.

However, it is not the case that _each_ subset $\mathcal{S}$ of the matrix
yields an intensional 2-isolator for $\mathbf{S5[Con]}$. The issue is that
some of the subsets of the matrix correspond to $\mathbf{S5[Con]}$-refutable
formulas, and intensional 2-isolators are consistent by definition. For
instance, letting $\mathcal{S}$ be the empty set yields the formula:

$\bigwedge\\{\neg\lozenge\varphi\mid\varphi\notin\emptyset\\}$

which is refuted by $\mathbf{S5[Con]}$, whence it is not an intensional
2-isolator.

The crucial question for us is to identify which subsets of the matrix
actually reflects the intensional properties of $\mathcal{L}_{T}$ sentences.
Let’s review some examples.

Consider Table 3, Table 4, Table 5, and Table 6. Each of these images exhibits
a subset of the $3\times 3$ matrix. In each case, consider the following
question: Is there a variable assignment $\star$ such that $x_{1}^{\star}$ and
$x_{2}^{\star}$ can attain all and only these combinations of values? Put
another way, given a subset $\mathcal{S}$ of the $3\times 3$ matrix, is there
a variable assignment $\star$ such that
$\mathbf{FIX}_{V^{\star}}\Vdash\bigwedge\\{\lozenge\varphi\mid\varphi\in\mathcal{S}\\}\wedge\bigwedge\\{\neg\lozenge\varphi\mid\varphi\notin\mathcal{S}\\}$?

TT | TF | TN
---|---|---
✗ | ✗ | ✗
✗ | ✗ | ✗
Table 3. A proper subset of the extensional 2-isolators. TT | TF | ✗
---|---|---
✗ | ✗ | ✗
✗ | ✗ | ✗
Table 4. A proper subset of the extensional 2-isolators. TT | ✗ | ✗
---|---|---
✗ | FF | ✗
✗ | ✗ | NN
Table 5. A proper subset of the extensional 2-isolators. TT | ✗ | TN
---|---|---
✗ | ✗ | FN
NT | ✗ | ✗
Table 6. A proper subset of the extensional 2-isolators.

The answers are given here:

Table 3: Yes. Let $x_{1}^{\star}$ be a grounded truth (e.g., $0=0$) and
$x_{2}^{\star}$ be a truth-teller.

Table 4: No. Note that the first two columns are non-empty but the third is
empty. Thus, the axiom $\mathbf{Ground}$

$\big{(}\lozenge T(x)\wedge\lozenge F(x)\big{)}\to\lozenge N(x)$

rules out this possibility, and $\mathbf{FIX}\Vdash\mathbf{Ground}$.

Table 5: Yes. Let $x_{1}^{\star}$ and $x_{2}^{\star}$ be the same truth-
teller.

Table 6: No. However, one cannot see that there is no such assignment merely
deploying the principles codified in $\mathbf{S5[Con,Ground]}$. Indeed, we
must introduce the following axiom:

$\mathbf{Min_{2}}:=\big{(}\lozenge N(x)\wedge\lozenge
N(y)\big{)}\to\lozenge\big{(}N(x)\wedge N(y)\big{)}$

Even though $\mathbf{S5[Con,Ground]}\nvdash\mathbf{Min_{2}}$, it is still the
case that $\mathbf{FIX}\Vdash\mathbf{Min_{2}}$ (by Remark 2.4). Note that the
axiom $\mathbf{Min_{2}}$ rules out Table 6 since the third row is non-empty
and the third column is non-empty but the corner element NN is missing.

This last example identifies the _only_ constraint on intensional 2-isolators
that is not codified in the $\mathbf{S5[Con,Ground]}$ axioms.

###  5.3. The Prime Conditions

For the full completeness theorem we need new axioms:

$\mathbf{Min_{n}}:=\big{(}\lozenge N(x_{1})\wedge\dots\wedge\lozenge
N(x_{n})\big{)}\to\lozenge\big{(}N(x_{1})\wedge\dots\wedge N(x_{n})\big{)}$

######  Remark 5.5.

For $n>k$, $\mathbf{Min_{n}}\vdash\mathbf{Min_{k}}$. To see this, just pick an
instance of $\mathbf{Min_{n}}$ wherein some variables are repeated. For
instance, to see that $\mathbf{Min_{3}}\vdash\mathbf{Min_{2}}$ note that the
following instance of $\mathbf{Min_{3}}$:

$\big{(}\lozenge N(x_{1})\wedge N(x_{1})\wedge\lozenge
N(x_{2})\big{)}\to\lozenge\big{(}N(x_{1})\wedge N(x_{1})\wedge
N(x_{2})\big{)}$

is (logically equivalent to) an instance of $\mathbf{Min_{2}}$.

In the previous subsection we identified intensional $2$-isolators with
subsets of the $3\times 3$ matrix. For the $n$-variable case, we must turn
from matrices to _tensors_ , which are generalizations of matrices beyond two
dimensions. In particular, will be interested in $3^{n}$ tensors, i.e.,
$\underbrace{3\times\ldots\times 3}\limits_{\mbox{\scriptsize$n$ times}}$
matrices.

Let $[3]^{n}$ be the set of triples from the set $\\{1,2,3\\}$. This is the
set of positions in a $3^{n}$ tensor. We can no longer speak only of rows and
columns. Instead, we speak in terms of _slices_. The rows are the 1-slices,
the columns are the 2-slices, and so on. How do we speak of the first row, the
second row, the third column, etc.? The 1st row is the 1st layer in the 1st
slice, the third column is the 3rd layer in the second slice, and so on. We
introduce the following notation.

######  Definition 5.6.

For $k\leq 3$ and $j\leq n$, the _$k^{th}$ -layer of the $j^{th}$ slice_
(written $j_{k}$) is

$\\{a\in[3^{n}]\mid\exists b_{1},\dots,\exists b_{n-1}\;a=\langle b_{1},\dots
b_{j-1},k,b_{j},\dots,b_{n-1}\rangle\\}$

Note that as $j_{k}$ is defined, it is a set of _positions_ in the $3^{n}$
tensor. That is, so far we have still only discussed positions. The tensors we
are interested in are 0-1 valued tensors, i.e., assignments of 0 and 1 to
these positions. It is easiest to think of these as just _subsets_ of
$[3]^{n}$, and that is how we will proceed.

We now introduce a definition that will be crucial to the proofs of the
remaining theorems:

######  Definition 5.7.

A tensor $\mathcal{S}\subseteq[3]^{n}$ meets the _prime conditions_ if:

  1. (1)

$\mathcal{S}$ is non-empty.

  2. (2)

For all $j\leq n$, if $\mathcal{S}$ intersects $j_{1}$ and $j_{2}$, then
$\mathcal{S}$ intersects $j_{3}$.

  3. (3)

For all $l\leq n$, for any $t$ slices $s^{1},\dots,s^{t}$, if $\mathcal{S}$
intersects $s^{i}_{3}$ for each $i\leq t$, then $\mathcal{S}$ intersects
$s^{1}_{3}\cap\dots\cap s^{t}_{3}$.

######  Remark 5.8.

In the case $n=2$, the prime conditions can be stated very simply (note that
when we refer to row 1, column 2, etc. we have in mind Table 1). We state them
here to aid the reader’s intuition. A set $\mathcal{S}$ of extensional
2-isolators meets the _prime conditions_ if:

  1. (1)

$\mathcal{S}$ is non-empty.

  2. (2)

    1. (a)

If $\mathcal{S}$ intersects row 1 and row 2, it intersects row 3.

    2. (b)

If $\mathcal{S}$ intersects column 1 and column 2, it intersects column 3.

  3. (3)

If $\mathcal{S}$ intersects row 3 and column 3, it contains (3,3).

###  5.4. The Main Lemma

The main technical lemma of this paper connects the prime conditions with
$\mathbf{FIX}$-satisfiability. That is, this lemma shows that those sets that
satisfy the prime conditions are exactly the sets that reflect the intensional
properties of $\mathcal{L}_{T}$ sentences.

######  Lemma 5.9.

For $\mathcal{S}\subseteq[3]^{n}$, TFAE:

  1. (1)

$\mathcal{S}$ meets the prime conditions.

  2. (2)

There is an $\mathcal{L}_{T}$ realization $\star$ such that

$\mathbf{FIX}\Vdash_{V^{\star}}\bigwedge\\{\lozenge\varphi\mid\varphi\in\mathcal{S}\\}\wedge\bigwedge\\{\neg\lozenge\varphi\mid\varphi\notin\mathcal{S}\\}.$

###### Proof.

(2) implies (1): This follows from soundness, i.e.,

$\mathbf{FIX}\Vdash\mathbf{S5[Con,Ground,Min_{n}]}.$

See Remark 2.1 and Remark 2.4.

(1) implies (2): Suppose that $\mathcal{S}$ meets the prime conditions. There
are two cases to consider.

  1. (I)

$\mathcal{S}$ does not contain $(3,\dots,3)$.

  2. (II)

$\mathcal{S}$ does contain $(3,\dots,3)$.

Case (I): There are very few ways a set can meet the prime conditions and omit
(3,…,3). The important thing to note is that:

######  Claim 1.

For some $j\leq n$ and some $i\leq 2$, $\mathcal{S}$ is contained in the $i$th
layer of the $j$th slice.

###### Proof.

To see that the claim holds, suppose that for all $j\leq n$, for all $i\leq
2$, $\mathcal{S}$ is not contained in the $i$th layer of the $j$th slice.
Since $\mathcal{S}$ meets the prime conditions, $\mathcal{S}$ is non-empty.
Thus, for every $j$, $\mathcal{S}$ must intersect _some_ layer of the $j$th
slice. We reason as follows:

  * •

$\mathcal{S}$ is not contained in the first layer of the $j$th slice, so
$\mathcal{S}$ intersects either the second or third layer of the $j$th slice.

  * •

$\mathcal{S}$ is not contained in the second layer of the $j$th slice, so
$\mathcal{S}$ intersects either the first or third layer of the $j$th slice.

It follows that either $\mathcal{S}$ intersects $j_{3}$ or it intersects both
$j_{1}$ and $j_{2}$. In the latter case, the prime conditions imply that
$\mathcal{S}$ intersects $j_{3}$. So either way, $\mathcal{S}$ intersects
$j_{3}$.

So, for every $j$, $\mathcal{S}$ intersects $j_{3}$. The prime conditions
imply that $\mathcal{S}$ contains $(3,\dots,3)$, a contradiction. This
completes the proof of the claim. ∎

With the claim on board we now set about finishing Case (I) by induction. The
base case is $n=2$.

Base Case: We can split into the subcases provided by the claim ($\mathcal{S}$
is contained either in the first row, the second row, the first column, or the
second column). Suppose for simplicity’s sake that $\mathcal{S}$ is contained
in the first row. There are only so many sets contained in the first row:

  1. (i)

$\mathcal{S}$ is the first row. Let $A^{\star}$ be $0=0$ and $B^{\star}$ be
$\tau$.

  2. (ii)

$\mathcal{S}$ contains just the leftmost and the rightmost elements of the
first row. Let $A^{\star}$ be $0=0$ and $B^{\star}$ be $\gamma$.

  3. (iii)

$\mathcal{S}$ contains the two rightmost elements of the first row. Let
$A^{\star}$ be $0=0$ and $B^{\star}$ be $\neg\gamma$.

  4. (iv)

$\mathcal{S}$ is just the leftmost element. Let $A^{\star}$ be 0=0 and
$B^{\star}$ be 0=0.

  5. (v)

$\mathcal{S}$ is just the middle element. Let $A^{\star}$ be 0=0 and
$B^{\star}$ be 0=1.

  6. (vi)

$\mathcal{S}$ is just the rightmost element. Let $A^{\star}$ be 0=0 and
$B^{\star}$ be $\lambda$.

By the prime conditions, $\mathcal{S}$ cannot contain just the two leftmost
elements of the first row, so these cases are exhaustive.

The reasoning is similar if $\mathcal{S}$ is contained in the second row,
first column, or second column. We leave these cases to the reader.

Induction step: Assume the induction hypothesis: For any
$\mathcal{S}\subseteq[3]^{n}$ meeting the prime conditions, there is an
appropriate realization $\star$. Now let $\mathcal{T}\subseteq[3]^{n+1}$ meet
the prime conditions. By Claim 1, $\mathcal{T}$ is contained in the $i$th
layer of the $j$th slice. The key observation is that the $i$th layer of the
$j$th slice _is_ a $3^{n}$ tensor. More precisely, the $j$th conjunct is the
same in all the entries in $j_{i}$, so ignoring this conjunct in all entries
yields a $3^{n}$ tensor $\mathcal{T}\restriction[3]^{n}$. Apply the induction
hypothesis to get an $\mathcal{L}_{T}$ realization $\star$ such that

$\mathbf{FIX}\Vdash_{V^{\star}}\bigwedge\\{\lozenge\varphi\mid\varphi\in\mathcal{T}\restriction[3]^{n}\\}\wedge\bigwedge\\{\neg\lozenge\varphi\mid\varphi\notin\mathcal{T}\restriction[3]^{n}\\}.$

To extend $\star$ to a realization $\sharp$ for $\mathcal{T}$, just let

$x_{j}^{\sharp}=\begin{cases}0=0&\text{ if }i=1\\\ 0=1&\text{ if }i=2\\\
\lambda&\text{ if }i=3\end{cases}$

Case (II): Assume that $(3,\dots,3)\in\mathcal{S}$. We must define sentences
$A^{1},\dots,A^{n}$. Pick some $k$ such that $2^{k}>3^{n}$. Take a set
$\\{\tau_{1},\dots,\tau_{k}\\}$ of independent truth-tellers (see Remark 2.2).
There are $2^{k}$-many formulas of the form:

${}^{+}_{\neg}\tau_{1}\wedge\dots\wedge^{+}_{\neg}\tau_{k}$

Fix some enumeration $C_{1},\dots,C_{2^{k}}$ of these formulas. We then define
the formulas
$A^{1}_{1},\dots,A^{1}_{3^{n}},\dots,A^{n}_{1},\dots,A^{n}_{3^{n}}$ so that
$A^{i}_{j}$ is a conditional of the form $C_{j}\to\theta$ where
$\theta\in\\{0=0,0=1,\lambda\\}$.

More precisely, we proceed as follows. We fix a numbering $\Phi$ of the cells
in the $3^{n}$ tensor. Then $\Phi(j)$ is some formula
$\varphi_{1}(x_{1})\wedge\dots\wedge\varphi_{n}(x_{n})$. Let $\Phi(j)_{i}$ be
the $i$th conjunct of $\Phi(j)$. We then define:

$A^{i}_{j}=C_{j}\to\begin{cases}0=0&\text{ if }\Phi(j)_{i}=T(x_{i})\\\
0=1&\text{ if }\Phi(j)_{i}=F(x_{i})\\\ \lambda&\text{ if
}\Phi(j)_{i}=N(x_{i})\end{cases}$

We define $\mathcal{S}^{\Phi}:=\\{k\leq 3^{n}\mid\Phi(k)\in\mathcal{S}\\}$.

We define $A^{i}$ as follows:

$A^{i}\equiv\bigwedge\\{A^{i}_{j}\mid
j\in\mathcal{S}^{\Phi}\\}\wedge\bigwedge\\{C_{j}\to\lambda\mid
j\in\\{1,\dots,2^{k}\\}-\mathcal{S}^{\Phi}\\}$

Let $\star$ be a variable assignment such that $x_{i}^{\star}=A^{i}$ for each
$i\leq n$.

######  Claim 2.

If $\varphi\in\mathcal{S}$, then
$\mathbf{FIX}\Vdash_{V^{\star}}\lozenge\varphi$.

###### Proof.

Suppose that $\varphi\in\mathcal{S}$. Note that $\varphi$ is a conjunction of
the form $\varphi_{1}(x_{1})\wedge\dots\wedge\varphi_{n}(x_{n})$. Note also
that $\Phi^{-1}(\varphi)$ is some number $k\leq 3^{n}$. Since $C_{k}$ is a
Boolean statement about independent truth-tellers, there is some $w$ such that
$\mathbb{N},w\vDash_{\mathsf{K3}}C_{k}$ (see Remark 2.2).

Let $i\leq n$. Note that $A^{i}_{k}$ is a conditional of the form
$C_{k}\to\theta$.

$A^{i}$ is a conjunction of conditionals with antecedent $C_{j}$ such that for
$j\neq k$,
$\mathbb{N},w\mathrel{\mathchoice{\reflectbox{$\displaystyle\vDash$}}{\reflectbox{$\textstyle\vDash$}}{\reflectbox{$\scriptstyle\vDash$}}{\reflectbox{$\scriptscriptstyle\vDash$}}}_{\mathsf{K3}}C_{j}$.
Which is to say that for all conjuncts $A^{i}_{j}$ of $A^{i}$ except for
$A^{i}_{k}$, $\mathbb{N},w\vDash_{\mathsf{K3}}A^{i}_{j}$. Thus,
$\mathbb{N},w\vDash_{\mathsf{K3}}A^{i}\leftrightarrow A^{i}_{k}$. Since
$\mathbb{N},w\vDash_{\mathsf{K3}}C_{k}$, we infer that,
$\mathbb{N},w\vDash_{\mathsf{K3}}A^{i}\leftrightarrow\theta$.

We now want to prove that $\mathbf{FIX},w\Vdash_{V^{\star}}\varphi_{i}$, where
$\varphi_{i}$ is the $i$th conjunct of $\varphi$. Let’s break into cases
depending on which formula $\varphi_{i}$ is.

_Case 1:_ Suppose $\varphi_{i}$ is $T(x_{i})$, i.e, $\varphi$ is in the 1st
layer of the $i$th slice. Since $k=\Phi^{-1}(\varphi)$,
$\Phi(j)_{i}=T(x_{i})$. So, $\theta$ is $0=0$. So
$\mathbb{N},w\vDash_{\mathsf{K3}}A^{i}$. So
$\mathbb{N},w\vDash_{\mathsf{K3}}\mathsf{True}(\ulcorner A^{i}\urcorner)$.
Since $x_{i}^{\star}=A^{i}$, $\mathbf{FIX},w\Vdash_{V^{\star}}T(x_{i})$.

_Case 2:_ Suppose $\varphi_{i}$ is $F(x_{i})$, i.e, $\varphi$ is in the 2nd
layer of the $i$th slice. Since $k=\Phi^{-1}(\varphi)$,
$\Phi(j)_{i}=F(x_{i})$. So, $\theta$ is $0=1$. So
$\mathbb{N},w\mathrel{\mathchoice{\reflectbox{$\displaystyle\vDash$}}{\reflectbox{$\textstyle\vDash$}}{\reflectbox{$\scriptstyle\vDash$}}{\reflectbox{$\scriptscriptstyle\vDash$}}}_{\mathsf{K3}}A^{i}$.
So $\mathbb{N},w\vDash_{\mathsf{K3}}\mathsf{True}(\ulcorner\neg
A^{i}\urcorner)$. Since $x_{i}^{\star}=A^{i}$,
$\mathbf{FIX},w\Vdash_{V^{\star}}F(x_{i})$.

_Case 3:_ Suppose $\varphi_{i}$ is $N(x_{i})$, i.e, $\varphi$ is in the 3rd
layer of the $i$th slice. Since $k=\Phi^{-1}(\varphi)$,
$\Phi(j)_{i}=N(x_{i})$. So, $\theta$ is $\lambda$. So
$\mathbb{N},w\uparrow_{\mathsf{K3}}A^{i}$. So
$\mathbb{N},w\nVdash_{\mathsf{K3}}\mathsf{True}(\ulcorner A^{i}\urcorner)$ and
$\mathbb{N},w\nVdash_{\mathsf{K3}}\mathsf{True}(\ulcorner\neg
A^{i}\urcorner)$. Since $x_{i}^{\star}=A^{i}$,
$\mathbf{FIX},w\Vdash_{V^{\star}}N(x_{i})$.

So $\mathbf{FIX},w\Vdash_{V^{\star}}\varphi$. So for all $v\in\mathbf{FIX}$,
$\mathbf{FIX},v\Vdash_{V^{\star}}\lozenge\varphi$. That is,
$\mathbf{FIX}\Vdash_{V^{\star}}\lozenge\varphi$. ∎

######  Claim 3.

If $\varphi\notin\mathcal{S}$, then
$\mathbf{FIX}\nVdash_{V^{\star}}\lozenge\varphi$.

###### Proof.

We prove the contrapositive. Suppose
$\mathbf{FIX}\Vdash_{V^{\star}}\lozenge\varphi$. Then there is some $w$ such
that $\mathbf{FIX},w\Vdash_{V^{\star}}\varphi$. We now break into cases
depending on whether any of the $C_{s}$ is true at $w$.

_Case 1:_ Suppose $\mathbb{N},w\uparrow_{\mathsf{K3}}C_{s}$ for all $s\leq
16$. We claim that $A^{1},\dots,A^{n}$ all have value neither in $w$.

To see this, note that $A^{i}$ is a conjunction of conditionals each of which
has an antecedent $C_{s}$, which has value neither. A conditional with a
neither antecedent cannot be false, so $A^{i}$ cannot be false. $A_{i}$ is
true only if all its conjuncts are true. Since
$2^{k}>3^{n}\geq|\mathcal{S}^{\Phi}|$, there is some $j\leq 2^{k}$ such that
$j\notin\mathcal{S}^{\Phi}$. But then by definition of $A^{i}$,
$C_{j}\to\lambda$ is a conjunct of $A^{i}$, and this has value neither.

So $\varphi$ is the formula $N(x_{1})\wedge\dots\wedge N(x_{n})$. Since we are
working in Case (II), we have assumed that this formula belongs to
$\mathcal{S}$.

_Case 2:_ Suppose $\mathbb{N},w\vDash_{\mathsf{K3}}C_{s}$ for exactly one $s$.
We split into subcases depending on whether $s>3^{n}$ or $s\leq 3^{n}$.

_Subcase 2.1:_ Suppose $s>3^{n}$. $A^{i}$ is a conjunction of conditionals of
the form $C_{j}\to\theta^{A}_{i}$ such that for $j\neq s$,
$\mathbb{N},w\mathrel{\mathchoice{\reflectbox{$\displaystyle\vDash$}}{\reflectbox{$\textstyle\vDash$}}{\reflectbox{$\scriptstyle\vDash$}}{\reflectbox{$\scriptscriptstyle\vDash$}}}_{\mathsf{K3}}C_{j}$,
whence $\mathbb{N},w\vDash_{\mathsf{K3}}A^{i}_{j}$. Accordingly,
$\mathbb{N},w\vDash_{\mathsf{K3}}A^{i}\leftrightarrow\theta$, where $\theta$
is the consequent of $A^{i}_{s}$. Since $s>3^{n}$, $\theta$ is $\lambda$.
Hence, $\mathbb{N},w\uparrow_{\mathsf{K3}}A^{i}$. Hence,
$\mathbb{N},w\nVdash_{\mathsf{K3}}\mathsf{True}(\ulcorner A^{i}\urcorner)$ and
$\mathbb{N},w\nVdash_{\mathsf{K3}}\mathsf{True}(\ulcorner\neg
A^{i}\urcorner)$. Since $x_{i}^{\star}=A^{i}$,
$\mathbf{FIX},w\Vdash_{V^{\star}}N(x_{i})$.

Thus, $\varphi$ is $N(x_{1})\wedge\dots\wedge N(x_{n})$, i.e., (3,…, 3). Once
again, since we are working in Case (II), we have assumed that this formula
belongs to $\mathcal{S}$.

_Subcase 2.2:_ Suppose that $s\leq 3^{n}$. As in the previous subcase,
$\mathbb{N},w\vDash_{\mathsf{K3}}A^{i}_{s}\leftrightarrow\theta$ where
$\theta$ is the consequent of $A^{i}_{s}$.

Now $A^{i}$ itself is a conjunction of conditionals which is defined to
include $A^{i}_{s}$ if and only if $s\in\mathcal{S}^{\Phi}$. Let’s split into
subsubcases depending on whether $s\in\mathcal{S}^{\Phi}$.

_Subsubcase 2.2.1:_ Suppose $s\in\mathcal{S}^{\Phi}$. Then
$\mathbb{N},w\vDash_{\mathsf{K3}}A^{i}\leftrightarrow A^{i}_{s}$, whence
$\mathbb{N},w\vDash_{\mathsf{K3}}A^{i}\leftrightarrow\theta$. We reason as
follows:

$\displaystyle\varphi_{i}\text{ is }T(x_{i})$
$\displaystyle\Longleftrightarrow\mathbf{FIX},w\Vdash_{V^{\star}}T(x_{i})$
$\displaystyle\Longleftrightarrow\mathbb{N},w\Vdash_{\mathsf{K3}}\mathsf{True}(\ulcorner
A^{i}\urcorner)$
$\displaystyle\Longleftrightarrow\mathbb{N},w\Vdash_{\mathsf{K3}}A^{i}$
$\displaystyle\Longleftrightarrow\mathbb{N},w\Vdash_{\mathsf{K3}}\theta$
$\displaystyle\Longleftrightarrow\theta\text{ is }0=0$
$\displaystyle\Longleftrightarrow\Phi(s)_{i}=T(x_{i})$

Exactly analogous arguments deliver exactly analogous conclusions.
Summarizing, we have:

$\displaystyle\varphi_{i}\text{ is }T(x_{i})$
$\displaystyle\Longleftrightarrow\Phi(s)_{i}=T(x_{i})$
$\displaystyle\varphi_{i}\text{ is }F(x_{i})$
$\displaystyle\Longleftrightarrow\Phi(s)_{i}=F(x_{i})$
$\displaystyle\varphi_{i}\text{ is }N(x_{i})$
$\displaystyle\Longleftrightarrow\Phi(s)_{i}=N(x_{i})$

These equivalences show that $\varphi=\Phi(s)$. It is the assumption of
Subsubcase 2.2.1 that $s\in\mathcal{S}^{\Phi}$, i.e., $\Phi(s)\in\mathcal{S}$,
so $\varphi\in\mathcal{S}$, which is desired result.

_Subsubcase 2.2.2:_ Suppose $s\notin\mathcal{S}^{\Phi}$. Then $A^{i}_{s}$ is
$C_{s}\to\lambda$. So $\mathbb{N},w\uparrow_{\mathsf{K3}}A^{i}_{s}$, whence
$\mathbb{N},w\uparrow_{\mathsf{K3}}A^{i}$. As before, we conclude that
$\mathbf{FIX},w\Vdash_{V^{\star}}N(x_{i})$. So $\varphi$ is
$N(x_{1})\wedge\dots\wedge N(x_{n})$. By the assumption of Case (II),
$\varphi\in\mathcal{S}$.

This completes the proof of Claim 3. ∎

Claim 2 and Claim 3 jointly yield Case (II) of (1) implies (2). This completes
the proof of Lemma 5.9. ∎

###  5.5. Completeness

Combining Lemma 5.9 (the analysis of $\mathbf{FIX}$-satisfiability in terms of
the prime conditions) with Carnap’s normal form theorem (Theorem 4.9), yields
a complete axiomatization of the modal theory of $\mathbf{FIX}$.

######  Theorem 5.10.

For all $n$-formulas $\varphi\in\mathcal{L}_{\Box}$, the following are
equivalent:

  1. (i)

$\mathbf{FIX}\Vdash\varphi$

  2. (ii)

$\mathbf{S5[Con,Ground,Min_{n}]}\vdash\varphi$

###### Proof.

The soundness direction is trivial. Let’s focus on completeness. Suppose that
$\mathbf{S5[Con,Ground,Min_{n}]}\nvdash\varphi$. By the normal form theorem,

$\mathbf{S5[Con,Ground,Min_{n}]}\vdash\neg\varphi\leftrightarrow(\psi_{1}\vee\dots\psi_{k})$

where each $\psi_{i}$ is a disjunction of $n$-isolators. Since $\psi$ is
consistent, at least one of the disjuncts $\psi_{i}$ is also consistent. It
follows that $\psi_{i}$ meets the prime conditions. By Lemma 5.9, there is an
$\mathcal{L}_{T}$ realization $\star$ such that

$\mathbf{FIX}\Vdash_{V^{\star}}\psi_{i}.$

Hence, we infer that $\mathbf{FIX}\nVdash\varphi.$ ∎

###  5.6. Counting Definable Relations

Lemma 5.9 yields an explicit characterization of the $\mathbf{FIX}$-definable
binary relations, namely, each $\mathbf{FIX}$-definable binary relation is a
disjunction of intensional 2-isolators. The following counting result follows
from this characterization.

######  Theorem 5.11.

The number of $\mathbf{FIX}$-definable binary relations is exactly $2^{276}$.

###### Proof.

First we need to determine the number of intensional 2-isolators. By Lemma
5.9, this is to count the number of subsets of the $3\times 3$ matrix meeting
the prime conditions.

There are $2^{3^{2}}$ subsets of the $3\times 3$ matrix in total. We must
subtract those sets that do not meet the prime conditions:

  1. (1)

The empty set. Subtract 1.

  2. (2)

The number of sets that intersect the first two rows but not the third is
$(2^{3}-1)^{2}=49$. Indeed, we must pick at least one element from the first
row and at least one from the second and none from the third. The first row
has three cells. Hence it has $2^{3}-1=7$ non-empty subsets. Likewise for the
second. So we must subtract $7^{2}=49$ total.

  3. (3)

The number of sets that intersect the first two columns but not the third is
likewise $(2^{3}-1)^{2}=49$.

  4. (4)

We must add back in all those sets that violated both the rows condition and
the columns condition. Note that if a set intersects the first two rows but
not the third and the first two columns but not the third then it is a subset
of the upper left $2\times 2$ square. Exactly $7$ of these sets intersects the
first two rows and first two columns.

  5. (5)

The sets that intersect row 3 and column 3 but not (3,3). There are
$2^{2}-1=3$ non-empty subsets of the first two slots of the 3rd row. Multiply
this by the $3$ ways of doing the same for the 3rd column. Then multiply this
with the number of ways of filling in the upper left $2\times 2$ square, which
is $2^{4}=16$. This makes for $3\times 3\times 16$ total.

Here is the calculation:

$2^{9}-1-49\times 2+7-3\times 3\times 16=276$

So there are $276$ intensional 2-isolators. The definable binary relations are
exactly the disjunctions of intensional 2-isolators, so there are $2^{276}$ of
them. This completes the proof. ∎

How many $\mathbf{FIX}$-definable $n$-ary relations are there? One could
presumably concoct a formula using the inclusion–exclusion principle. Yet it
would probably be difficult to write down an informative one. The following
coarse estimate proposition follows immediately:

######  Proposition 5.12.

The number of $\mathbf{FIX}$-definable $n$-ary relations is $2^{k}$ for some
$k$ in the interval $(2^{3^{n}-1},2^{{3^{n}}})$.

###### Proof.

A definable $n$-ary relation is a disjunction of intensional $n$-isolators. So
this number is $2^{k}$ where $k$ is the disjunction of intensional
$n$-isolators. So now we will calculate bounds on $k$.

Each intensional $n$-isolator is a subset of the set of extensional
$n$-isolators, i.e., subset of the $3^{n}$ tensor. This yields the upper bound
$2^{3^{n}}$.

Every subset of the $3^{n}$ tensor that includes $(3,\dots,3)$ is an
intensional $n$-isolator. There are $2^{3^{n}-1}$ such subsets. This yields
the lower bound. ∎

Clearly this interval is huge (and only grows as $n$ grows). One could perhaps
use the inclusion–exclusion principle to count exactly the number of
$\mathbf{FIX}$-definable $n$-ary relations, but it is not clear whether the
resulting formula would be at all informative. Instead of focusing on the
exact number, one could aim to find a more informative estimate, but we will
not pursue this further in this paper.

##  6\. Conclusions

The results in this paper concern extensions of the modal logic $\mathbf{S5}$.
Many of the interesting phenomena that arise in modal logic do not arise in
$\mathbf{S5}$. $\mathbf{S5}$ has Kripke semantics, but the accessibility
relation is not so interesting: Often we think of the worlds as just forming
an unstructured set (as we do in this paper). Moreover, as [2] observed,
neighboring modalities collapse into one modal, so there is no non-trivial
iteration of modality in $\mathbf{S5}$. So a pessimist might conclude that
$\mathbf{S5}$ is somewhat boring. The results presented in this paper suggest
a different perspective, namely, that by precluding some interesting
phenomena, $\mathbf{S5}$ makes room for others.

In support of this point, let me sketch an analogy with first-order model
theory. Carnap’s normal form theorem resembles some classic results of first-
order model theory. Indeed, normal form theorems and attendant
characterizations of definable sets are standard goals in model theory _when
they are possible_. Recall that model theorists often divide first-order
theories into the _tame_ and the _wild_. The following contrasting theorems
give some sense of the divide between the tame and the wild:

######  Theorem 6.1 ([4]).

The first-order theory of $\mathbb{Z}$ as a ring is not decidable.

######  Theorem 6.2 ([7]).

The first-order theory of $\mathbb{Q}$ as a field is not decidable.

######  Theorem 6.3 (Tarski 1930).

The first-order theory of $\mathbb{R}$ as a field is decidable.222See [9].

The decidable/undecidable dichotomy is not exactly the same as the model-
theoretic tame/wild dichotomy, but in these particular instances they
coincide. In particular, Tarski’s theorem follows from o-minimality. A
structure is _o-minimal_ if every definable set is a finite union of intervals
and a theory is o-minimal if all its structures are. Of course, there is much
that o-minimal theories cannot express. The first-order theory of the reals,
for instance, cannot define the set of integers or define the sine function.
However, this permits logicians to give sharp, detailed characterizations of
definable sets.

Much of model theory is “concerned with discovering and charting the “tame”
regions of mathematics, where wild phenomena like…Gödel incompleteness are
absent, or at least under control” [10]. Of course, one can easily concoct
tame theories that do not encode substantial tracts of mathematics. The more
interesting theories are both tame _and_ rich, as the first-order theory of
the reals is. Such theories have been the locus of considerable model-
theoretic research and are the source of many applications of model theory to
mainstream mathematics.

Sometimes wild theories like arithmetic have fragments that are both tame and
rich. One method for isolating tame fragments of wild theories is pruning the
signature (i.e., prohibiting some symbols from appearing in the formulas). A
famous instance of this is Presburger’s theorem (contrast with Gödel’s
theorem):

######  Theorem 6.4 ([6]).

The theory of $\mathbb{Z}$ as an additive group is decidable.

Presburger’s theory is tame according to various model-theoretic criteria,
e.g., it eliminates quantifiers.

Another method for isolating tame fragments of wild theories is to axiomatize
the behavior of certain formulas using modal logic. Provability logic is
perhaps the most famous instance of this phenomenon. First-order $\mathbf{PA}$
is a wild system. Much research in the meta-theory of $\mathbf{PA}$ concerns
the behavior of the provability predicate $Prov_{\mathsf{PA}}(\cdot)$ within
$\mathbf{PA}$. Solovay showed that this fragment of $\mathbf{PA}$ is tame, in
the following sense:

######  Theorem 6.5 ([8]).

The behavior of the predicate $Prov_{\mathsf{PA}}(\cdot)$ within $\mathbf{PA}$
is axiomatized by the decidable modal logic $\mathbf{GL}$.

The present project is another project in this spirit, although with a focus
on definability rather than axiomatization. Kripke’s work of truth is
straightforwardly formalizable in second-order arithmetic $\mathbf{PA_{2}}$ or
in set theory $\mathbf{ZFC}$, but these theories are firmly on the wild side
of the tame/wild divide. By isolating a modal fragment we are able to classify
definable sets in a manner analogous to o-minimality (every definable set is a
finite union of sets of a very special form). As a consequence we see
that—though $\mathbf{S5}$ precludes some interesting phenomena—it permits very
sharp results.

## References

  * [1] John P Burgess  “The truth is never simple”  In _The Journal of Symbolic Logic_ 51.3 Cambridge University Press, 1986, pp. 663–681
  * [2] Rudolf Carnap  “Modalities and quantification”  In _The Journal of Symbolic Logic_ 11.2 Cambridge University Press, 1946, pp. 33–64
  * [3] Kit Fine  “Normal forms in modal logic.”  In _Notre Dame Journal of Formal Logic_ 16.2 Duke University Press, 1975, pp. 229–237
  * [4] Kurt Gödel  “Über formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme I”  In _Monatshefte für mathematik und physik_ 38 Springer, 1931, pp. 173–198
  * [5] Saul Kripke  “Outline of a theory of truth”  In _The Journal of Philosophy_ 72.19 JSTOR, 1975, pp. 690–716
  * [6] Mojzesz Presburger  “Uber die vollstandigkeiteines gewissen systems der arithmetik ganzer zahlen, in welchen die addition als einzige operation hervortritt”  In _Comptes-Rendus du ler Congres des Mathematiciens des Pays Slavs_ , 1929
  * [7] Julia Robinson  “Definability and decision problems in arithmetic”  In _The Journal of Symbolic Logic_ 14.2 Cambridge University Press, 1949, pp. 98–114
  * [8] Robert M Solovay  “Provability interpretations of modal logic”  In _Israel journal of mathematics_ 25 Springer, 1976, pp. 287–304
  * [9] Alfred Tarski  “A decision method for elementary algebra and geometry”  In _Quantifier Elimination and Cylindrical Algebraic Decomposition_ Springer, 1998, pp. 24–84
  * [10] Lou Van Den Dries  “O-minimal structures and real analytic geometry”  In _Current Developments in Mathematics_ International Press of Boston, 1998, pp. 105–152


# A sub-functor for Ext and Cohen-Macaulay associated graded modules with
bounded multiplicity-II

Ankit Mishra<EMAIL_ADDRESS>and  Tony J. Puthenpurakal
<EMAIL_ADDRESS>Department of Mathematics, IIT Bombay, Powai, Mumbai
400 076

###### Abstract.

Let $(A,\mathfrak{m})$ be a Cohen-Macaulay local ring, then notion of
$T$-split sequence was introduced in part-1 of this paper for
$\mathfrak{m}$-adic filtration with the help of numerical function
$e^{T}_{A}$. We have explored the relation between AR-sequences and $T$-split
sequences. For a Gorenstein ring $(A,\mathfrak{m})$ we define a Hom-finite
Krull-Remak-Schmidt category $\mathcal{D}_{A}$ as a quotient of the stable
category $\operatorname{\underline{CM}}(A)$. This category preserves
isomorphism, i.e. $M\cong N$ in $\mathcal{D}_{A}$ if and only if $M\cong N$ in
$\operatorname{\underline{CM}}(A)$.This article has two objectives; first
objective is to extend the notion of $T$-split sequence, and second objective
is to explore function $e^{T}_{A}$ and $T$-split sequence. When
$(A,\mathfrak{m})$ be an analytically unramified Cohen-Macaulay local ring and
$I$ be an $\mathfrak{m}$-primary ideal then we extend the techniques in part-1
of this paper to the integral closure filtration with respect to $I$ and prove
a version of Brauer-Thrall-II for a class of such rings.

###### Key words and phrases:

Associated graded rings and modules, Brauer-Thrall conjectures, strict
complete intersections, Henselian rings, Ulrich modules, integral closure
filtration

###### 1991 Mathematics Subject Classification:

Primary 13A30, 13C14; Secondary 13D40, 13D07

##  1\. Introduction

Dear Reader,
While reading this paper it will be a good idea to keep a copy of part 1,
[Putrn], of this paper with you. The notation used in this paper are same as
that of [Putrn].
Let $(A,\mathfrak{m})$ be a Cohen-Macaulay local ring of dimension $d\geq 1$
and let $\operatorname{CM}(A)$ be the category of maximal Cohen-Macaulay
$A$-modules. In [Putrn] second author has constructed
$T\colon\operatorname{CM}(A)\times\operatorname{CM}(A)\rightarrow\operatorname{mod}(A)$,
a sub-functor of $\operatorname{Ext}^{1}_{A}(-,-)$ as follows: Let $M$ be an
MCM $A$-module. Set

$e^{T}_{A}(M)=\lim_{n\rightarrow\infty}\frac{(d-1)!}{n^{d-1}}\ell\left(\operatorname{Tor}^{A}_{1}(M,\frac{A}{\mathfrak{m}^{n+1}})\right).$

This function arose in the second author’s study of certain aspects of the
theory of Hilbert functions [Pu0],[PuMCM]. Using [Pu0, Theorem 18] we get that
$e^{T}_{A}(M)$ is a finite number and it is zero if and only if $M$ is free.
Let $s\colon 0\rightarrow N\rightarrow E\rightarrow M\rightarrow 0$ be an
exact sequence of MCM $A$-modules. Then by [Pu_stable, 2.6] we get that
$e^{T}_{A}(E)\leq e^{T}_{A}(M)+e^{T}_{A}(N)$. Set
$e^{T}(s)=e^{T}_{A}(M)+e^{T}_{A}(N)-e^{T}_{A}(E)$.

######  Definition 1.1.

We say $s$ is $T$-split if $e^{T}_{A}(s)=0$.

######  Definition 1.2.

Let $M,N$ be MCM $A$-modules. Set

$T_{A}(M,N)=\\{s\mid s\ \text{is a $T$-split extension}\\}.$

We proved [Putrn, 1.4],

######  Theorem 1.3.

(with notation as above)
$T_{A}\colon\operatorname{CM}(A)\times\operatorname{CM}(A)\rightarrow\operatorname{mod}(A)$
is a sub-functor of $\operatorname{Ext}^{1}_{A}(-,-)$.

It is not clear from the definition whether $T_{A}(M,N)$ is non-zero. Theorem
[Putrn, 1.5] shows that there are plenty of $T$-split extensions if
$\dim\operatorname{Ext}^{1}_{A}(M,N)>0$. We proved [Putrn, 1.5]

######  Theorem 1.4.

Let $(A,\mathfrak{m})$ be a Cohen-Macaulay local ring and let $M,N$ be MCM
$A$-modules. Then

$\operatorname{Ext}^{1}_{A}(M,N)/T_{A}(M,N)\quad\text{has finite length.}$

Note Theorem 1.4 has no content if $M$ is free on the punctured spectrum of
$A$. One of our motivations of this paper was to investigate $T_{A}(M,N)$ when
$M$ is free on the punctured spectrum of $A$.

Now assume $(A,\mathfrak{m})$ is Henselian and $M$ is an indecomposable MCM
$A$-module with $M_{\mathfrak{p}}$ is free for all $\mathfrak{p}\in$
Spec${}^{0}(A)=$ Spec$(A)\setminus\\{\mathfrak{m}\\}$, then a fundamental
short exact sequence known as the Auslander-Reiten (AR)-sequence ending at $M$
exists. For a good introduction to AR-sequences see [Yoshino, Chapter 2].

The following result gives a large number of examples of AR-sequences which
are $T$-split.

######  Theorem 1.5.

Let $(Q,\mathfrak{n})$ be a Henselian regular local ring and
$\underline{f}=f_{1},\ldots,f_{c}\in\mathfrak{n}^{2}$ a regular sequence. Set
$I=(f_{1},\ldots,f_{c})$ and $(A,\mathfrak{m})=(Q/I,\mathfrak{n}/I)$. Assume
$\dim A=1$. Let $M$ be an indecomposable MCM $A$-module with
$\operatorname{cx}_{A}M\geq 2$. Assume $M$ is free on Spec${}^{0}(A)$. Set
$M_{n}=\operatorname{Syz}_{n}^{A}(M)$, then for $n\gg 0$ the AR-sequences
ending in $M_{n}$ are $T$-split.

For hypersurfaces defined by quadrics we prove:

######  Theorem 1.6.

Let $(Q,\mathfrak{n})$ be a Henselian regular local ring with algebraically
closed residue field $k=Q/\mathfrak{n}$ and let
$f\in\mathfrak{n}^{2}\setminus\mathfrak{n}^{3}$. Assume the hypersurface
$A=Q/(f)$ is an isolated singularity. Then all but finitely many AR-sequences
in $A$ are $T$-split.

Theorems 1.5 and 1.6 shows that $T$-split sequences are abundant in general.
However the following example is important:

######  Example 1.7.

There exists a complete hypersurface isolated singularity $A$ and an
indecomposable MCM $A$-module $M$ such that $T_{A}(M,N)=0$ for any MCM
$A$-module $N$.

######  1.8.

Now assume $A$ is Gorenstein. As observed in [Pu_stable] the function
$e^{T}_{A}(-)$ is infact a function on $\operatorname{\underline{CM}}(A)$ the
stable category of all MCM $A$-modules. Let $M$ and $N$ be MCM $A$-modules. It
is well-known that we have a natural isomorphism

$\eta\colon\text{\text@underline{Hom}}_{A}(M,N)\cong\text{Ext}^{1}_{A}(\Omega^{-1}(M),N)$

Let $T_{A}(\Omega^{-1}(M),N)$ denotes the set of all $T$-split sequences in
Ext${}^{1}_{A}(\Omega^{-1}(M),N)$. We denote
$\eta^{-1}(T_{A}(\Omega^{-1}(M),N))$ by $\mathcal{R}(M,N)$. Then $\eta$
induces following isomorphism

$\frac{\text{\text@underline{Hom}}_{A}(M,N)}{\mathcal{R}(M,N)}\cong\frac{\text{Ext}^{1}_{A}(\Omega^{-1}(M),N)}{T_{A}(\Omega^{-1}(M),N)}.$

Suprisingly

######  Proposition 1.9.

$\mathcal{R}$ is a relation on $\operatorname{\underline{CM}}(A)$.

Thus we may consider the quotient category
$\mathcal{D}_{A}=\operatorname{\underline{CM}}(A)/\mathcal{R}$. Clearly
$\mathcal{D}_{A}$ is a Hom-finite additive category. Surprisingly the
following result holds

######  Theorem 1.10.

Let $(A,\mathfrak{m})$ be a Henselian Gorenstein local ring and let $M$ and
$N$ be MCM $A$-modules. Then the following holds

  1. (1)

$M\cong N$ in $\mathcal{D}_{A}$ if and only if $M\cong N$ in
$\operatorname{\underline{CM}}(A)$.

  2. (2)

$M$ is indecomposable in $\mathcal{D}_{A}$ if and only if $M$ is
indecomposable in $\operatorname{\underline{CM}}(A)$

  3. (3)

$\mathcal{D}_{A}$ is a Krull-Remak-Schmidt (KRS) category.

The main application of $T$-split sequences was to study Weak Brauer-Thrall-II
for associated graded modules for a large class of rings. Note that in [Putrn]
the concept was introduced only for $\mathfrak{m}$-adic filtration, but for
general $I(\neq\mathfrak{m})$-adic filtrations that method will not work (see
[Putrn, Remark 3.2]).

In this article we extend the results in [Putrn] to a large family of
filtrations. Let $(A,\mathfrak{m})$ be an analytically unramified Cohen-
Macaulay local ring of dimension $d\geq 1$ and let $I$ be an
$\mathfrak{m}$-primary ideal. Let $\mathcal{F}=\\{I_{n}\\}_{n\in\mathbb{Z}}$
where $I_{1}=\overline{I}$ and $I_{n}=\overline{I^{n}}$ for $n\gg 0$ be an
$I$-admissible filtration. Let $M$ be an MCM $A$-module.