1 Semantics with syntactic relation
Besides algebraic semantics and closely related matrix models, Kripke semantics constitute the traditional form of interpretation for most non-classical logics. Originating in the field of modal logic, its variously modified versions expanded to other areas, such as intuitionistic or relevance logics. The general idea behind Kripke structures is to define relation(s) based on some non-empty domain, elements of which are often referred to as ‘worlds’. Valuations of such structures (frames) are relativized to worlds, and thus, truth is defined in two variants: locally—in a particular world, and globally—in all worlds. If we exclude the quite well-known neighborhood structures (they share one of the basic ideas of possible-world semantics: truth being relativized to members of the domain), it seems that the only mainstream non-algebraic rivals of (generalized or modified) Kripke models are plain valuations—either classical, or many-valued.
Another route has been set by Richard Epstein [3–5]. Having very specific goal in mind, he introduced new types of models by enhancing a standard valuation with a binary relation. Unlike Kripke, he chose not to define his relation on some arbitrary domain, but on the fixed set of formulas. Thus he obtained semantics which enabled him to interpret intensional connective (he focused solely on non-material implication). His main philosophical motivation was to formalize the notion of content relation. For this reason, he imposed various specific conditions on his relation. He indicated two main classes of logics: dependence logics and relatedness logics. Epstein’s ideas have been picked up by other researchers, to name a few, [Reference Iseminger7, Reference Walton17, Reference Walton18] for philosophical exploration of Epstein logics, [11–13] for overall analysis of Epstein’s logics, [Reference Carnielli1, Reference Del Cerro and Lugardon2] for proof-theoretical investigations into Epstein’s logics, [Reference Paoli15] for alternative semantics for first degree relatedness logic and [Reference Paoli16] for constructive proof of completeness (the original one was given using the standard Henkin method; see [Reference Epstein5]).
Epstein has outlined a research program in which his semantics are conjectured to be an adequate interpretation for other non-classical logics. Following his plan, he has used his semantics to obtain paraconsistent logic [Reference Epstein6].
Recently, Epstein semantics were generalized [Reference Jarmużek and Kaczkowski8] in a twofold way. First of all, no restrictions have been put on a relation. Secondly, new connective has been introduced: a special type of conjunction which was interpreted analogously as Epstein implication. These simple generalizations opened new perspective on Epstein semantics: it can be treated analogously as Kripke semantics, abstracting from specific applications to relatedness and dependence. This way, both philosophical and mathematical potential of Epstein semantics becomes even wider and Epstein program—easier to achieve. Following the observation from [Reference Jarmużek and Kaczkowski8], further philosophical applications of Epstein semantics have emerged. It has been used in connexive logic [Reference Malinowski and Palczewski14] and deontic logic [Reference Jarmużek and Klonowski9].
Mathematical aspects of Epstein semantics remain vastly unexplored.Footnote 1 The goal of this paper is to add some technical sophistication to meta-theory of Epstein semantics by introducing new model-theoretic constructions and applying them to prove some theorems about Epstein semantics. We will focus on the extended language from [Reference Jarmużek and Kaczkowski8].
2 Language and semantics
Let
$\Phi =\{p_0,p_1,p_2,...\}$
be the set of propositional letters. We introduce one unary connective: the negation
$\neg $
and binary connectives:
$\lor ,\wedge ,\to ,\leftrightarrow ,\vartriangle ,\looparrowright $
. The set of connectives will be denoted by
$\textsf {con}$
. The set of formulas
$\mathsf {FOR}$
is the least set such that:
-
•
$\Phi \subseteq \mathsf {FOR}$
, -
•
$\varphi \in \mathsf {FOR}$
implies
$\neg \varphi \in \mathsf {FOR}$
, -
•
$\varphi ,\psi \in \mathsf {FOR}$
implies
$\varphi \ast \psi \in \mathsf {FOR}$
where
$\ast \in \textsf {con}\setminus \{\neg \}$
.
A generalized Epstein model is an ordered pair
$\mathfrak {M}=\langle v,\mathcal {R}\rangle $
, where
$v:\Phi \longrightarrow \{0,1\}$
is a standard valuation and
$\mathcal {R}\subseteq \mathsf {FOR}\times \mathsf {FOR}$
is a binary relation defined on the set of formulas. The domain of
$\mathfrak {M}$
is fixed in each case; it is the set of formulas
$\mathsf {FOR}$
. This is an important remark because—unlike in the case of first order or modal logic—we are not impelled to the notion of a class when talking about objects the elements of which are models. Actually, the set of all models is
$\{0,1\}^\Phi \times \mathcal {P}(\mathsf {FOR}\times \mathsf {FOR})$
. That is why we can use the term ‘set of models’ without being involved in set-theoretical paradoxes. Let
$\varphi \in \mathsf {FOR}$
,
$\mathfrak {M}=\langle v,\mathcal {R}\rangle $
. We say that
$\varphi $
is true in
$\mathfrak {M}$
, symbolically
$\mathfrak {M}\vDash \varphi $
iff:
-
•
$v(\varphi )=1$
for
$\varphi \in \Phi $
, -
•
$\mathfrak {M}\nvDash \psi $
for
$\varphi =\neg \psi $
, -
•
$\mathfrak {M}\vDash \psi $
and
$\mathfrak {M}\vDash \chi $
for
$\varphi =\psi \wedge \chi $
, -
•
$\mathfrak {M}\vDash \psi $
or
$\mathfrak {M}\vDash \chi $
for
$\varphi =\psi \lor \chi $
, -
•
$\mathfrak {M}\nvDash \psi $
or
$\mathfrak {M}\vDash \chi $
for
$\varphi =\psi \to \chi $
, -
•
$\mathfrak {M}\vDash \psi $
iff
$\mathfrak {M}\vDash \chi $
for
$\varphi =\psi \leftrightarrow \chi $
, -
•
$[\mathfrak {M}\vDash \psi $
and
$\mathfrak {M}\vDash \chi ]$
and
$\langle \psi ,\chi \rangle \in \mathcal {R}$
for
$\varphi =\psi \vartriangle \chi $
, -
•
$[\mathfrak {M}\nvDash \psi $
or
$\mathfrak {M}\vDash \chi ]$
and
$\langle \psi ,\chi \rangle \in \mathcal {R}$
for
$\varphi =\psi \looparrowright \chi $
.
The last two connectives will be called intensional conjunction and intensional implication respectively. Notice that in order for an intensional conjunction/implication to be true, the standard condition for the classical conjunction/implication has to be fulfilled, as well as both conjuncts/the antecedent and the consequent have to remain related by relation
$\mathcal {R}$
. The intended reading of those formulas differs from the philosophical interpretation, e.g.,
$\varphi \looparrowright \psi $
may be read as ‘
$\varphi $
causes
$\psi $
’, if one wants to analyze causality,
$\varphi \vartriangle \psi $
as ‘
$\varphi $
and (then)
$\psi $
’, if we want to use conjunction in a manner that respects temporal succession (see [Reference Jarmużek and Kaczkowski8]). A possible spectrum of applications seems to be much wider—the general idea being that Epstein semantics provide the framework within which behavior of some connectives mirrors the intensional character of the words like ‘if…, then’ or ‘and’ from natural language.
When for some
$\varphi ,\psi \in \mathsf {FOR}$
,
$\langle \varphi ,\psi \rangle \in \mathcal {R}$
we will often write shortly
$\varphi \mathcal {R}\psi $
. Let
$\Sigma \subseteq \mathsf {FOR}$
. We say that
$\mathfrak {M}\vDash \Sigma $
iff for any
$\sigma \in \Sigma $
we have
$\mathfrak {M}\vDash \sigma $
. By
$\mathsf {M}$
we will denote the set of all generalized Epstein models (shortly: models). The symbol
$\vDash \varphi $
will mean that for any
$\mathfrak {M}\in \mathsf {M}$
we have
$\mathfrak {M}\vDash \varphi $
. Let
$\mathsf {K}\subseteq \mathsf {M}$
be a set of models. We say that
$\Sigma \subseteq \mathsf {FOR}$
is satisfiable in
$\mathsf {K}$
iff there is
$\mathfrak {M}\in \mathsf {K}$
such that
$\mathfrak {M}\vDash \Sigma $
; if
$\mathsf {K} = \mathsf {M}$
we will simply say that
$\Sigma $
is satisfiable.
We shall also specify the notion of definability of models which is crucial in the main theorem we prove in the latter parts of the paper.
Definition 2.1 (Definability)
Let
$\Gamma \subseteq \mathsf {FOR}$
, and let
$\mathsf {K}$
be some set of models. We say that
$\Gamma $
defines
$\mathsf {K}$
when for any model
$\mathfrak {M}=\langle v,\mathcal {R}\rangle $
the following holds:
$\mathfrak {M}\vDash \Gamma $
iff
$\mathfrak {M}\in \mathsf {K}$
. We say that a set of models
$\mathsf {K}$
is definable iff there is some
$\Gamma \subseteq \mathsf {FOR}$
that defines
$\mathsf {K}$
.
Since we will use induction on the complexity of formulas in latter proofs, let us state the definition of the formula-complexity function.
Definition 2.2. Let
$\mathbb {N}$
be the set of natural numbers. The formula-complexity function
$c:\mathsf {FOR}\longrightarrow \mathbb {N}$
is given by the following conditions:
$$ \begin{align*} c(\varphi)&=1\text{ iff }\varphi\in\Phi,\\ c(\neg\varphi)&=1+c(\varphi),\\ c(\varphi\ast\psi)&=1+c(\varphi)+c(\psi),\text{ where }\ast=\lor,\wedge,\to,\leftrightarrow,\looparrowright,\vartriangle. \end{align*} $$
Later on, we will not state the induction hypothesis explicitly in our proofs. When referring to induction hypothesis in inductive step which shows that the result holds for
$\varphi $
, we will assume that the hypothesis says that the result holds for any
$\psi $
such that
$c(\psi )<c(\varphi )$
.
3 Reducts and inexpressibility of connectives
It is a common practice in classical or modal logic to restrict its presentation to a chosen set of connectives and treat the remaining ones as secondary notions by means of certain definitions, e.g.,
$\{\neg ,\wedge \}$
plus
$\Box $
if one is concerned with modal logic. In this section we will show why we need to maintain all the connectives introduced in the previous section in case of JarmuŻek–Kaczkowski logic (contrary to what is stated in their paper; see Fact 3.1.5. [Reference Jarmużek and Kaczkowski8, p. 57]). It will be achieved by means of a reduct—our first model-theoretic construct. We shall start from some conventions. Let
$a\subseteq \textsf {con}$
be some set of connectives. By
$\mathsf {FOR}^a$
we will denote the set of formulas generated from
$\Phi $
and a. In this sense,
$\mathsf {FOR}^{\textsf {con}}$
is just
$\mathsf {FOR}$
. Now, let us define the notion of a reduct.
Definition 3.3 (Reduct)
Let
$\mathfrak {M}=\langle v,\mathcal {R}\rangle $
, and
$a\subseteq \textsf {con}$
. We say that
$\mathfrak {M}^a=\langle v',\mathcal {R}'\rangle $
is a reduct of
$\mathfrak {M}$
to a iff
$v=v'$
and
$\mathcal {R}'=\mathcal {R}\setminus \{\langle \varphi ,\psi \rangle \in \mathsf {FOR}^2:\varphi \notin \mathsf {FOR}^a\,\,or\,\,\psi \notin \mathsf {FOR}^a\}$
.
We can prove the following reduct lemma, which will be used in the proof of inexpressibility.
Lemma 3.4 (Reduct lemma)
Let
$a\subseteq \textsf {con}$
,
$\mathfrak {M}=\langle v,\mathcal {R}\rangle $
and
$\mathfrak {M}^a=\langle v',\mathcal {R}'\rangle $
be its reduct to a. For any
$\varphi \in \mathsf {FOR}^a$
we have
$\mathfrak {M}\vDash \varphi $
iff
$\mathfrak {M}^a\vDash \varphi $
.
Proof. The result obviously holds for propositional letters since
$v=v'$
. In case of connectives of a that are among the set
$\textsf {con}\setminus \{\looparrowright ,\vartriangle \}$
the result is an immediate consequence of inductive hypothesis. Now, let us assume that
$\looparrowright \in a$
. Let
$\varphi =\psi \looparrowright \chi \in \mathsf {FOR}^a$
. Assume
$\mathfrak {M}\vDash \psi \looparrowright \chi $
. Hence
$\psi \mathcal {R}\chi $
and
$\mathfrak {M}\nvDash \psi $
or
$\mathfrak {M}\vDash \chi $
. Both
$\psi ,\chi \in \mathsf {FOR}^a$
, so
$\psi \mathcal {R}'\chi $
. Furthermore, by inductive hypothesis we know that
$\mathfrak {M}^a\nvDash \psi $
or
$\mathfrak {M}^a\vDash \chi $
. This means that
$\mathfrak {M}^a\vDash \psi \looparrowright \chi $
. For the other direction, assume
$\mathfrak {M}^a\vDash \psi \looparrowright \chi $
. Hence
$\psi \mathcal {R}'\chi $
and
$\mathfrak {M}^a\nvDash \psi $
or
$\mathfrak {M}^a\vDash \chi $
. By inductive hypothesis,
$\mathfrak {M}\nvDash \psi $
or
$\mathfrak {M}\vDash \chi $
. Obviously,
$\mathcal {R}'\subseteq \mathcal {R}$
, so
$\psi \mathcal {R}\chi $
, which means
$\mathfrak {M}\vDash \psi \looparrowright \chi $
. Let
$\varphi =\psi \vartriangle \chi \in \mathsf {FOR}^a$
. Assume
$\mathfrak {M}\vDash \psi \vartriangle \chi $
. Hence
$\mathfrak {M}\vDash \psi $
,
$\mathfrak {M}\vDash \chi $
and
$\psi \mathcal {R}\chi $
. By inductive hypothesis,
$\mathfrak {M}^a\vDash \psi $
and
$\mathfrak {M}^a\vDash \chi $
. We also know that
$\psi ,\chi \in \mathsf {FOR}^a$
, so
$\psi \mathcal {R}'\chi $
. This means that
$\mathfrak {M}^a\vDash \psi \vartriangle \chi $
. For the other direction, assume that
$\mathfrak {M}^a\vDash \psi \vartriangle \chi $
. Hence
$\mathfrak {M}^a\vDash \psi $
,
$\mathfrak {M}^a\vDash \chi $
and
$\psi \mathcal {R}'\chi $
. By inductive hypothesis,
$\mathfrak {M}\vDash \psi $
and
$\mathfrak {M}\vDash \chi $
. We also know that
$\psi \mathcal {R}\chi $
, since
$\mathcal {R}'\subseteq \mathcal {R}$
. This means that
$\mathfrak {M}\vDash \psi \vartriangle \chi $
.□
Definition 3.5. Let
$a\subseteq \textsf {con}$
. We say that a is
$\textsf {con}$
-expressible iff for any
$\varphi \in \mathsf {FOR}$
there is
$\psi \in \mathsf {FOR}^a$
such that
$\vDash \varphi \leftrightarrow \psi $
.
In the light of the remark from the beginning of this section, we can say that we can restrict ourselves to some proper subset of
$\textsf {con}$
, only when this subset is
$\textsf {con}$
-expressible. Now we will show that such subset does not exist.
Theorem 3.6 (Inexpressibility)
Let
$a\subseteq \textsf {con}$
. a is
$\textsf {con}$
-expressible iff
$a=\textsf {con}$
.
Proof. The right to left direction is trivially true. For the left to right assume that
$a\neq \textsf {con}$
. Then there is
$\ast \in \textsf {con}$
such that
$\ast \notin a$
. Either 1)
$\ast =\neg $
or 2)
$\ast $
is one of the binary connectives. Assume that
$\ast =\neg $
. Let
$\varphi =\neg p_0\looparrowright \neg p_0\in \mathsf {FOR}$
. Assume for reductio that a is
$\textsf {con}$
-expressible. Let
$\psi \in \mathsf {FOR}^a$
be such that
$\vDash \varphi \leftrightarrow \psi $
. Let
$\mathfrak {M}=\langle v,\mathcal {R}\rangle $
be such that
$\mathcal {R}=\{\langle \neg p_0,\neg p_0\rangle \}$
. Obviously,
$\mathfrak {M}\vDash \varphi $
. Hence, by the assumption we have
$\mathfrak {M}\vDash \psi $
. Let
$\mathfrak {M}^a=\langle v',\mathcal {R}'\rangle $
be a reduct of
$\mathfrak {M}$
to a, i.e.,
$v=v'$
and
$\mathcal {R}'=\emptyset $
, because
$\neg p_0\notin \mathsf {FOR}^a$
. By Lemma 3.4 we obtain:
$\mathfrak {M}^a\vDash \psi $
. But
$\mathfrak {M}^a\nvDash \varphi $
. Contradiction, so a is not
$\textsf {con}$
-expressible. Now, assume that
$\ast $
is a binary connective. Let
$\varphi =(p_0\ast p_0)\looparrowright (p_0\ast p_0)$
. Let
$\mathfrak {M}=\langle v,\mathcal {R}\rangle $
be such that
$\mathcal {R}=\{\langle p_0\ast p_0, p_0\ast p_0\rangle \}$
. Assume further that a is
$\textsf {con}$
-expressible. Let
$\psi \in \mathsf {FOR}^a$
be such that
$\vDash \varphi \leftrightarrow \psi $
. We know that
$\mathfrak {M}\vDash \varphi $
. Hence also
$\mathfrak {M}\vDash \psi $
. Let
$\mathfrak {M}^a=\langle v',\mathcal {R}'\rangle $
be such that
$v=v'$
and
$\mathcal {R}'=\emptyset $
. By Lemma 3.4,
$\mathfrak {M}^a\vDash \psi $
. But
$\mathfrak {M}^a\nvDash \varphi $
. Contradiction, so a is not
$\textsf {con}$
-expressible.□
To sum up the theorem just proven, it can be said that the only set of connectives that is capable of expressing
$\textsf {con}$
is the set
$\textsf {con}$
itself. Or in other words: any proper subset of
$\textsf {con}$
is
$\textsf {con}$
-inexpressible. Observe that in the face of Theorem 3.6, Fact 3.1.5. from [Reference Jarmużek and Kaczkowski8] is false.Footnote
2
4 Ultramodels and compactness
Before moving to the next definition, we shall quickly recall the notion of an ultrafilter. Let W be a non-empty set. By
$\mathcal {P}(W)$
we shall denote the power set of W.
$F\subseteq \mathcal {P}(W)$
is a filter over W if the following conditions are fulfilled: i)
$W\in F$
, ii)
$X,Y\in F$
implies
$X\cap Y\in F$
, and iii) if
$X\in F$
and
$X\subseteq Y\subseteq W$
, then
$Y\in F$
. Filter F over W is said to be proper iff
$F\neq \mathcal {P}(W)$
. An ultrafilter U over W is a proper filter that meets the following stipulation: for any
$X\subseteq W$
we have
$X\in U$
iff
$W\setminus X\notin U$
.
Let
$A\subseteq \mathcal {P}(W)$
. We say that A has the finite intersection property iff the intersection of any finite number of elements of A is non-empty. The filter generated by A is the set
$\bigcap \{F\subseteq \mathcal {P}(W): A\subseteq F\,\,\text {and}\,\,F\,\, \text {is a filter over}\,\,W\}$
. It can be easily proven that such set is indeed a filter. We shall also recall the well-known fact about ultrafilters often referred to as the ultrafilter theorem.
Theorem 4.7. If
$A\subseteq \mathcal {P}(W)$
has the finite intersection property, then it can be extended to an ultrafilter.
Now we shall introduce the construction which is inspired by the well-known ultraproduct.
Definition 4.8 (Ultramodel)
Let
$(\mathfrak {M}_i)_{i\in I}$
be a non-empty family of models where for each
$i\in I \mathfrak {M}_i=\langle v_i,\mathcal {R}_i\rangle $
, U an ultrafilter over I. We define the ultramodel of
$(\mathfrak {M}_i)_{i\in I}$
modulo U to be
$\underset {i\in I}{\mu }\mathfrak {M}_i/U=\langle v,\mathcal {R}\rangle $
, where:
$$ \begin{align*} &\text{for any } \varphi\in\Phi \text{ define: } v(\varphi)=1\text{ iff } \{i\in I: v_i(\varphi)=1\}\in U,\\ &\text{for any } \varphi,\psi\in\mathsf{FOR} \text{ define: } \varphi\mathcal{R}\psi\text{ iff }\{i\in I: \varphi\mathcal{R}_i\psi\}\in U. \end{align*} $$
Since there is no product of any domain within our construction, we named it simply ‘ultramodel’. We obtain the result completely analogous to Łoś’s theorem.
Lemma 4.9 (Ultramodel lemma)
Let I be the non-empty set and U an ultrafilter over I. For any
$\varphi \in \mathsf {FOR}$
,
$\mathfrak {M}_i=\langle v_i,\mathcal {R}_i\rangle $
$$\begin{align*}\underset{i\in I}{\mu}\mathfrak{M}_i/U\vDash\varphi \,\,\text{iff}\,\, \{i\in I:\mathfrak{M}_i\vDash\varphi\}\in U.\end{align*}$$
Proof. Let I be a non-empty set and U an ultrafilter over I. Let
$(\mathfrak {M}_i)_{i\in I}$
be a family of models where
$\mathfrak {M}_i=\langle v_i,\mathcal {R}_i\rangle $
for each
$i\in I$
.
$\underset {i\in I}{\mu }\mathfrak {M}_i/U=\langle v,\mathcal {R}\rangle $
. Let
$\varphi \in \mathsf {FOR}$
be an arbitrary formula. For the base case assume
$\varphi \in \Phi $
.
$\underset {i\in I}{\mu }\mathfrak {M}_i/U\vDash \varphi $
iff
$v(\varphi )=1$
iff
$\{i\in I: v_i(\varphi )=1\}\in U$
iff
$\{i\in I: \mathfrak {M}_i\vDash \varphi \}\in U$
. Now assume that
$\varphi =\neg \psi $
.
$\underset {i\in I}{\mu }\mathfrak {M}_i/U\vDash \neg \psi $
iff
$\underset {i\in I}{\mu }\mathfrak {M}_i/U\nvDash \psi $
iff (from hypothesis)
$\{i\in I: \mathfrak {M}_i\vDash \psi \}\notin U$
iff
$I\setminus \{i\in I: \mathfrak {M}_i\vDash \psi \}\in U$
iff
$\{i\in I: \mathfrak {M}_i\nvDash \psi \}\in U$
iff
$\{i\in I: \mathfrak {M}_i\vDash \neg \psi \}\in U$
. Assume that
$\varphi =\psi \lor \chi $
.
$\underset {i\in I}{\mu }\mathfrak {M}_i/U\vDash \psi \lor \chi $
iff
$\underset {i\in I}{\mu }\mathfrak {M}_i/U\vDash \psi $
or
$\underset {i\in I}{\mu }\mathfrak {M}_i/U\vDash \chi $
iff (from hypothesis)
$\{i\in I: \mathfrak {M}_i\vDash \psi \}\in U$
or
$\{i\in I: \mathfrak {M}_i\vDash \chi \}\in U$
. In either case
$\{i\in I: \mathfrak {M}_i\vDash \psi \}\cup \{i\in I: \mathfrak {M}_i\vDash \chi \}\in U$
, which means
$\{i\in I: \mathfrak {M}_i\vDash \psi \lor \chi \}\in U$
. For the other direction, assume that
$\{i\in I: \mathfrak {M}_i\vDash \psi \lor \chi \}\in U$
. This means that
$\{i\in I: \mathfrak {M}_i\nvDash \psi \,\,\text {and}\,\,\mathfrak {M}_i\nvDash \chi \}\notin U$
. This means that
$\{i\in I: \mathfrak {M}_i\nvDash \psi \}\cap \{i\in I: \mathfrak {M}_i\nvDash \chi \}\notin U$
. So
$\{i\in I: \mathfrak {M}_i\nvDash \psi \}\notin U$
or
$\{i\in I: \mathfrak {M}_i\nvDash \chi \}\notin U$
. This means that
$\{i\in I: \mathfrak {M}_i\vDash \psi \}\in U$
or
$\{i\in I: \mathfrak {M}_i\vDash \chi \}\in U$
. By hypothesis:
$\underset {i\in I}{\mu }\mathfrak {M}_i/U\vDash \psi $
or
$\underset {i\in I}{\mu }\mathfrak {M}_i/U\vDash \chi $
, which means
$\underset {i\in I}{\mu }\mathfrak {M}_i/U\vDash \psi \lor \chi $
. The remaining Boolean cases are analogous. Let
$\varphi =\psi \vartriangle \chi $
. Assume
$\underset {i\in I}{\mu }\mathfrak {M}_i/U\vDash \psi \vartriangle \chi $
.
$\underset {i\in I}{\mu }\mathfrak {M}_i/U\vDash \psi $
and
$\underset {i\in I}{\mu }\mathfrak {M}_i/U\vDash \chi $
and
$\psi \mathcal {R}\chi $
. From the earlier results we know that
$\{i\in I:\mathfrak {M}_i\vDash \psi \,\,\text {and}\,\,\mathfrak {M}_i\vDash \chi \}\in U$
and
$\{i\in I: \psi \mathcal {R}_i\chi \}\in U$
. But then intersection of those two sets belongs to U, meaning
$\{i\in I: \mathfrak {M}_i\vDash \psi \vartriangle \chi \}\in U$
. For the other direction, assume
$\{i\in I: \mathfrak {M}_i\vDash \psi \vartriangle \chi \}\in U$
. Note that:
$\{i\in \ I:\mathfrak {M}_i\vDash \psi \vartriangle \chi \}\subseteq \{i\in I:\mathfrak {M}_i\vDash \psi \,\,\text {and}\,\,\mathfrak {M}_i\vDash \chi \}\subseteq I$
and
$\{i\in \ I:\mathfrak {M}_i\vDash \psi \vartriangle \chi \}\subseteq \{i\in I: \psi \mathcal {R}_i\chi \}\subseteq I$
. So,
$\{i\in I:\mathfrak {M}_i\vDash \psi \,\,\text {and}\,\,\mathfrak {M}_i\vDash \chi \}\in U$
and
$\{i\in I: \psi \mathcal {R}_i\chi \}\in U$
. Hence
$\underset {i\in I}{\mu }\mathfrak {M}_i/U\vDash \psi $
and
$\underset {i\in I}{\mu }\mathfrak {M}_i/U\vDash \chi $
and
$\psi \mathcal {R}\chi $
, which means
$\underset {i\in I}{\mu }\mathfrak {M}_i/U\vDash \psi \vartriangle \chi $
. Let
$\varphi =\psi \looparrowright \chi $
. Assume that
$\underset {i\in I}{\mu }\mathfrak {M}_i/U\vDash \psi \looparrowright \chi $
. This means that
$\underset {i\in I}{\mu }\mathfrak {M}_i/U\vDash \psi \to \chi $
and
$\psi \mathcal {R}\chi $
. We know that
$\{i\in I:\mathfrak {M}_i\vDash \psi \to \chi \}\in U$
from previous results for Boolean connectives and
$\{i\in I:\psi \mathcal {R}_i\chi \}\in U$
. Hence the intersection of those sets is in U meaning that
$\{i\in I:\mathfrak {M}_i\vDash \psi \looparrowright \chi \}\in U$
. For the other direction assume that
$\{i\in I:\mathfrak {M}_i\vDash \psi \looparrowright \chi \}\in U$
. Hence both
$\{i\in I:\mathfrak {M}_i\vDash \psi \to \chi \}\in U$
and
$\{i\in I:\psi \mathcal {R}_i\chi \}\in U$
since
$\{i\in I:\mathfrak {M}_i\vDash \psi \looparrowright \chi \}\subseteq \{i\in I:\mathfrak {M}_i\vDash \psi \to \chi \}$
and
$\{i\in I:\mathfrak {M}_i\vDash \psi \looparrowright \chi \}\subseteq \{i\in I:\psi \mathcal {R}_i\chi \}$
. From the previous results we also know that
$\underset {i\in I}{\mu }\mathfrak {M}_i/U\vDash \psi \to \chi $
and
$\psi \mathcal {R}\chi $
meaning
$\underset {i\in I}{\mu }\mathfrak {M}_i/U\vDash \psi \looparrowright \chi $
.□
An important remark about our construction which differentiates it from the ultraproduct construction is that an ultramodel of identical models (analogous to an ultrapower in terms of an ultraproduct) always comes down to a single component (does not produce any new entity)Footnote 3 , i.e.:
Proposition 4.10. Let
$(\mathfrak {M}_i)_{i\in I}$
be such that for each
$k,l\in I$
we have
$\mathfrak {M}_k=\mathfrak {M}_l$
and let U be an ultrafilter over I. Then
$\underset {i\in I}{\mu }\mathfrak {M}_i/U= \mathfrak {M}_j$
where j is an arbitrary index from I.
Proof. For the proof, it is enough to observe the following: either
$\{i\in I: v(\varphi )= 1\} = I$
, or
$\{i\in I: v(\varphi )= 1\} = \emptyset $
depending whether
$v_j(\varphi ) =1$
or
$v_j(\varphi )= 0$
for any
$\varphi \in \Phi $
. Similarly
$\{i\in I: \varphi \mathcal {R}_i\psi \} = I$
if
$\varphi \mathcal {R}_j\psi $
and
$\{i\in I: \varphi \mathcal {R}_i\psi \} = \emptyset $
if
$\langle \varphi ,\psi \rangle \notin \mathcal {R}_j$
. For
$v_j(\varphi ) =1$
iff
$\{i\in I: v(\varphi )= 1\} = I\in U$
for any
$\varphi \in \Phi $
and
$\varphi \mathcal {R}_i\psi $
iff
$\{i\in I: \varphi \mathcal {R}_i\psi \} = I\in U$
for any
$\varphi ,\psi \in \mathsf {FOR}$
.□
Now, we can move on to prove the next theorem. Compactness has been also proven in [Reference Jarmużek and Kaczkowski8]. However, our method will be completely different than the one employed by the authors.
Theorem 4.11 (Compactness)
Let
$\Sigma \subseteq \mathsf {FOR}$
. If all finite subsets of
$\Sigma $
are satisfiable, then
$\Sigma $
is satisfiable.
Proof. Let I be the set of all finite subsets of
$\Sigma $
. For each
$i\in I$
let
$\mathfrak {M}_i$
be the model satisfying i. Let
$E=\{\widehat {\sigma }:\sigma \in \Sigma \}$
, where for each
$\sigma \in \Sigma $
we have
$\widehat {\sigma }=\{i\in I:\sigma \in i\}$
. E has the finite intersection property since for any
$\sigma _0,\ldots ,\sigma _n\in \Sigma \{\sigma _0,\ldots ,\sigma _n\}\in \widehat {\sigma _0}\cap \cdots \cap \widehat {\sigma _n}$
. By Fact 4.7 E can be extended to an ultrafilter. Let U be such ultrafilter. For any
$\sigma \in \Sigma $
,
$\widehat {\sigma }\in U$
and
$\widehat {\sigma }\subseteq \{i\in I:\mathfrak {M}_i\vDash \sigma \}$
. So
$\{i\in I:\mathfrak {M}_i\vDash \sigma \}\in U$
. By Lemma 4.9 we know that
$\underset {i\in I}{\mu }\mathfrak {M}_i/U\vDash \sigma $
for any
$\sigma \in \Sigma $
. Hence
$\underset {i\in I}{\mu }\mathfrak {M}_i/U\vDash \Sigma $
.□
5
$\textsf {S}$
-sets and (un)definability
Our last model-theoretic notion is the
$\textsf {S}$
-set construction, which ascribes the whole set of models to a single generalized Epstein model.
Definition 5.12 (The
$\textsf {S}$
-set)
Let
$\mathfrak {M}=\langle v,\mathcal {R}\rangle $
be a model. We define the set
$\Omega ^{\mathfrak {M}}=\{\langle \varphi ,\psi \rangle : \mathfrak {M}\nvDash \varphi \to \psi \}$
. We define the
$\textsf {S}$
-set of
$\mathfrak {M}$
as follows:
$$\begin{align*}\textsf{S}^{\mathfrak{M}}=\{\langle v',\mathcal{R}'\rangle: v'=v,\,\,\mathcal{R}\setminus\Omega^{\mathfrak{M}}\subseteq\mathcal{R}'\subseteq\mathcal{R}\cup\Omega^{\mathfrak{M}}\}.\end{align*}$$
If we were to define the
$\textsf {S}$
construction as an operation, it would be
$O:\mathsf {M}\longrightarrow \mathcal {P}(\mathsf {M})$
where
$O(\mathfrak {M})=\textsf {S}^{\mathfrak {M}}$
for any
$\mathfrak {M}=\langle v,\mathcal {R}\rangle \in \mathsf {M}$
.
In order to prove Theorem 5.16, we shall first state some definitions and prove some lemmas. Let us start with the definition of model equivalence.
Definition 5.13. Let
$\mathfrak {M}$
be a model. By
$\mathsf {Th}(\mathfrak {M})$
we understand the theory of
$\mathfrak {M}$
, i.e.,
$\mathsf {Th}(\mathfrak {M})=\{\varphi \in \mathsf {FOR}:\mathfrak {M}\vDash \varphi \}$
. Given the models
$\mathfrak {M}=\langle v,\mathcal {R}\rangle $
,
$\mathfrak {N}=\langle v',\mathcal {R}'\rangle $
let
$\mathfrak {M}\approx \mathfrak {N}$
iff
$\mathsf {Th}(\mathfrak {M})=\mathsf {Th}(\mathfrak {N})$
. Obviously,
$\approx $
is an equivalence relation, hence for arbitrary model by
$|\mathfrak {M}|_\approx $
we shall denote the equivalence class:
$\{\mathfrak {N}:\mathfrak {M}\approx \mathfrak {N}\}$
.
Lemma 5.14 (
$\textsf {S}$
-lemma)
For any
$\mathfrak {M}=\langle v, \mathcal {R}\rangle $
we have
$\textsf {S}^{\mathfrak {M}}=|\mathfrak {M}|_\approx $
.
Proof. Let
$\mathfrak {M}=\langle v,\mathcal {R}\rangle $
. For the left to right inclusion assume
$\mathfrak {N}=\langle v',\mathcal {R}'\rangle \in \textsf {S}^{\mathfrak {M}}$
. We will show that for any
$\varphi \in \mathsf {FOR}$
we have
$\mathfrak {M}\vDash \varphi $
iff
$\mathfrak {N}\vDash \varphi $
, which means
$\mathfrak {M}\approx \mathfrak {N}$
. For the base case assume that
$\varphi $
is atomic:
$\varphi \in \Phi $
. By Definition 5.12 we know that
$v'=v$
, so we get the result immediately. Assume further that
$\varphi =\neg \psi $
.
$\mathfrak {M}\vDash \neg \psi $
iff
$\mathfrak {M}\nvDash \psi $
iff (from hypothesis)
$\mathfrak {N}\nvDash \psi $
iff
$\mathfrak {N}\vDash \neg \psi $
. For
$\varphi =\psi \wedge \chi $
we have the following:
$\mathfrak {M}\vDash \psi \wedge \chi $
iff
$\mathfrak {M}\vDash \psi $
and
$\mathfrak {M}\vDash \chi $
iff (from hypothesis)
$\mathfrak {N}\vDash \psi $
and
$\mathfrak {N}\vDash \chi $
iff
$\mathfrak {N}\vDash \psi \wedge \chi $
. The proof for the rest of the Boolean connectives goes in a similar way. Now assume that
$\varphi =\psi \looparrowright \chi $
. Assume further that
$\mathfrak {M}\vDash \psi \looparrowright \chi $
. Hence
$\mathfrak {M}\nvDash \psi $
or
$\mathfrak {M}\vDash \chi $
. By inductive hypothesis, we obtain that also
$\mathfrak {N}\nvDash \psi $
or
$\mathfrak {N}\vDash \chi $
. We also know that
$\langle \psi ,\chi \rangle \in \mathcal {R}$
. Since it is not the case that
$\mathfrak {M}\nvDash \psi \to \chi $
, we know by Definition 5.12 that
$\langle \psi ,\chi \rangle \notin \Omega ^{\mathfrak {M}}$
. Then
$\langle \psi ,\chi \rangle \in \mathcal {R}\setminus \Omega ^{\mathfrak {M}}$
and
$\mathcal {R}\setminus \Omega ^{\mathfrak {M}}\subseteq \mathcal {R}'$
, so
$\langle \psi ,\chi \rangle \in \mathcal {R}'$
, which means
$\mathfrak {N}\vDash \psi \looparrowright \chi $
. For the other direction, assume that
$\mathfrak {N}\vDash \psi \looparrowright \chi $
. This means that
$\mathfrak {N}\nvDash \psi $
or
$\mathfrak {N}\vDash \chi $
. From inductive hypothesis we get
$\mathfrak {M}\nvDash \psi $
or
$\mathfrak {M}\vDash \chi $
. Also
$\langle \psi ,\chi \rangle \in \mathcal {R}'$
. Since
$\mathcal {R}'\subseteq \mathcal {R}\cup \Omega ^{\mathfrak {M}}$
we know that
$\langle \psi ,\chi \rangle \in \mathcal {R}\cup \Omega ^{\mathfrak {M}}$
. But again
$\mathfrak {M}\vDash \psi \to \chi $
, so
$\langle \psi ,\chi \rangle \notin \Omega ^{\mathfrak {M}}$
, which means
$\langle \psi ,\chi \rangle \in \mathcal {R}$
. This means that
$\mathfrak {M}\vDash \psi \looparrowright \chi $
. Now let
$\varphi =\psi \vartriangle \chi $
. Assume
$\mathfrak {M}\vDash \psi \vartriangle \chi $
. Hence
$\mathfrak {M}\vDash \psi $
and
$\mathfrak {M}\vDash \chi $
. By inductive hypothesis
$\mathfrak {N}\vDash \psi $
and
$\mathfrak {N}\vDash \chi $
. We also know that
$\langle \psi ,\chi \rangle \in \mathcal {R}$
. Since
$\mathfrak {M}\vDash \psi \wedge \chi $
, it is not the case that
$\mathfrak {M}\nvDash \psi \to \chi $
. Hence
$\langle \psi ,\chi \rangle \notin \Omega ^{\mathfrak {M}}$
. Then
$\langle \psi ,\chi \rangle \in \mathcal {R}\setminus \Omega ^{\mathfrak {M}}$
and
$\mathcal {R}\setminus \Omega ^{\mathfrak {M}}\subseteq \mathcal {R}'$
, so
$\langle \psi ,\chi \rangle \in \mathcal {R}'$
which means
$\mathfrak {N}\vDash \psi \vartriangle \chi $
. For the other direction, assume that
$\mathfrak {N}\vDash \psi \vartriangle \chi $
. This means that
$\mathfrak {N}\vDash \psi $
and
$\mathfrak {N}\vDash \chi $
. From inductive hypothesis we get
$\mathfrak {M}\vDash \psi $
and
$\mathfrak {M}\vDash \chi $
. Also
$\langle \psi ,\chi \rangle \in \mathcal {R}'$
. Since
$\mathcal {R}'\subseteq \mathcal {R}\cup \Omega ^{\mathfrak {M}}$
, we know that
$\langle \psi ,\chi \rangle \in \mathcal {R}\cup \Omega ^{\mathfrak {M}}$
. But again
$\mathfrak {M}\vDash \varphi \wedge \psi $
, so also
$\mathfrak {M}\vDash \varphi \to \psi $
. Then
$\langle \psi ,\chi \rangle \notin \Omega ^{\mathfrak {M}}$
which means
$\langle \psi ,\chi \rangle \in \mathcal {R}$
. This means that
$\mathfrak {M}\vDash \psi \vartriangle \chi $
.
Now, for the right to left inclusion assume
$\mathfrak {N}=\langle v',\mathcal {R}'\rangle \notin \textsf {S}^{\mathfrak {M}}$
. Then at least one of the following holds: i)
$v\neq v'$
, ii)
$\mathcal {R}\setminus \Omega ^{\mathfrak {M}}\nsubseteq \mathcal {R}'$
or iii)
$\mathcal {R}'\nsubseteq \mathcal {R}\cup \Omega ^{\mathfrak {M}}$
. If i) holds, then we immediately know that
$\mathfrak {M}\not \approx \mathfrak {N}$
. If ii) is true, then there is
$\langle \varphi ,\psi \rangle \in \mathcal {R}\setminus \Omega ^{\mathfrak {M}}$
such that
$\langle \varphi ,\psi \rangle \notin \mathcal {R}'$
. We already know that
$\mathfrak {N}\nvDash \varphi \looparrowright \psi $
. But since
$\langle \varphi ,\psi \rangle \notin \Omega ^{\mathfrak {M}}$
, we know that
$\mathfrak {M}\vDash \varphi \to \psi $
. We also know that
$\langle \varphi ,\psi \rangle \in \mathcal {R}$
, so
$\mathfrak {M}\vDash \varphi \looparrowright \psi $
. The desired result holds:
$\mathfrak {M}\not \approx \mathfrak {N}$
. Finally, let us consider iii). There is
$\langle \varphi ,\psi \rangle \in \mathcal {R}'$
such that
$\langle \varphi ,\psi \rangle \notin \mathcal {R}\cup \Omega ^{\mathfrak {M}}$
. Since
$\langle \varphi ,\psi \rangle \notin \Omega ^{\mathfrak {M}}$
, we know that
$\mathfrak {M}\vDash \varphi \to \psi $
. We also know that
$\mathfrak {M}\nvDash \varphi \looparrowright \psi $
, for
$\langle \varphi ,\psi \rangle \notin \mathcal {R}$
. Either
$\mathfrak {N}\nvDash \varphi \to \psi $
or
$\mathfrak {N}\vDash \varphi \to \psi $
. If the first one holds we obtain the result:
$\mathfrak {M}\not \approx \mathfrak {N}$
. If the second one holds, then
$\mathfrak {N}\vDash \varphi \looparrowright \psi $
, which also means that
$\mathfrak {M}\not \approx \mathfrak {N}$
.□
We say that a set of models
$\mathsf {K}$
is closed under
$\textsf {S}$
-sets when the following holds for
$\mathfrak {M}=\langle v,\mathcal {R}\rangle $
,
$\mathfrak {N}=\langle v',\mathcal {R}'\rangle $
:
$$\begin{align*}\text{if}\,\,\mathfrak{M}\in\mathsf{K}\,\, \text{and}\,\, \mathfrak{N}\in\textsf{S}^{\mathfrak{M}},\,\, \text{then}\,\, \mathfrak{N}\in\mathsf{K}.\end{align*}$$
$\mathsf {K}$
is closed under ultramodels when for any non-empty I and any ultrafilter U over I we have:
$$\begin{align*}\text{if}\,\,\forall_{i\in I} \mathfrak{M}_i\in\mathsf{K},\,\,\text{then}\,\,\underset{i\in I}{\mu}\mathfrak{M}_i/U\in\mathsf{K}.\end{align*}$$
Let
$\mathsf {K}$
be a set of models. By
$\overline {\mathsf {K}}$
we shall denote
$\mathsf {K}$
’s complementation, that is:
$\{\mathfrak {M}=\langle v,\mathcal {R}\rangle :\mathfrak {M}\notin \mathsf {K}\}$
. Note that the following is true about closure under
$\textsf {S}$
-sets:
Proposition 5.15. Let
$\mathsf {K}$
be a set of models.
$\mathsf {K}$
is closed under
$\textsf {S}$
-sets iff
$\overline {\mathsf {K}}$
is.
Proof. Assume that
$\mathsf {K}$
is closed under
$\textsf {S}$
-sets but
$\overline {\mathsf {K}}$
is not. Then there is
$\mathfrak {M}\in \overline {\mathsf {K}}$
and
$\mathfrak {N}\notin \overline {\mathsf {K}}$
such that
$\mathfrak {N}\in \textsf {S}^{\mathfrak {M}}$
. Hence
$\mathfrak {N}\in \mathsf {K}$
and
$\mathfrak {N}\approx \mathfrak {M}$
so
$\mathfrak {M}\in \textsf {S}^{\mathfrak {N}}$
, which means
$\mathfrak {M}\in \mathsf {K}$
—contradiction.□
Now we are ready to state and prove our main theorem:
Theorem 5.16. Let
$\mathsf {K}$
be a set of models.
$\mathsf {K}$
is definable iff
$\mathsf {K}$
is closed under S-sets and ultramodels.
Proof. For the left to right direction, let
$\mathsf {K}$
be a definable set of models. Let
$\Gamma \subseteq \mathsf {FOR}$
define
$\mathsf {K}$
. Assume
$\mathfrak {M}\in \mathsf {K}$
and
$\mathfrak {N}\in \textsf {S}^{\mathfrak {M}}$
.
$\mathfrak {M}\vDash \Gamma $
. But also
$\mathfrak {N}\vDash \Gamma $
by Lemma 5.14, so
$\mathfrak {N}\in \mathsf {K}$
. Now assume that for each
$i\in I \mathfrak {M}_i\in \mathsf {K}$
for some non-empty I. Let U be an ultrafilter over I. Since for each
$\gamma \in \Gamma $
we have
$\{i\in I:\mathfrak {M}_i\vDash \gamma \}=I$
, we know from Lemma 4.9 that
$\underset {i\in I}{\mu }\mathfrak {M}_i/U\vDash \Gamma $
. Hence
$\underset {i\in I}{\mu }\mathfrak {M}_i/U\in \mathsf {K}$
.
For the right to left, assume that
$\mathsf {K}$
is closed under
$\textsf {S}$
-sets and ultramodels. Let
$\Gamma =\{\varphi \in \mathsf {FOR}:\,\,\text {for all}\,\,\mathfrak {N}\in \mathsf {K}\,\,\mathfrak {N}\vDash \varphi \}$
. We will show that
$\Gamma $
defines
$\mathsf {K}$
. Obviously,
$\mathfrak {M}\in \mathsf {K}$
implies
$\mathfrak {M}\vDash \Gamma $
. For the opposite direction, let
$\mathfrak {M}=\langle v,\mathcal {R}\rangle $
be an arbitrary model such that
$\mathfrak {M}\vDash \Gamma $
. Each finite subset of
$\mathsf {Th}(\mathfrak {M})$
is satisfiable in
$\mathsf {K}$
. For otherwise there would be finite
$\Sigma _0=\{\sigma _0,\ldots ,\sigma _n\}$
such that for each
$\mathfrak {N}\in \mathsf {K}$
we would have
$\mathfrak {N}\nvDash \Sigma _0$
. This would mean that
$\neg \sigma _0\lor \cdots \lor \neg \sigma _n\in \Gamma $
and so
$\mathfrak {M}\vDash \neg \sigma _0\lor \cdots \lor \neg \sigma _n$
. Contradiction. Let I be the set of all finite subsets of
$\mathsf {Th}(\mathfrak {M})$
. For each
$i\in I$
let
$\mathfrak {M}_i$
be the model satisfying i. Let
$E=\{\widehat {\sigma }:\sigma \in \mathsf {Th}(\mathfrak {M})\}$
, where for each
$\sigma \in \mathsf {Th}(\mathfrak {M}) \widehat {\sigma }=\{i\in I:\sigma \in i\}$
. E has the finite intersection property since for any
$\sigma _0,\ldots ,\sigma _n\in \mathsf {Th}(\mathfrak {M}) \{\sigma _0,\ldots ,\sigma _n\}\in \widehat {\sigma _0}\cap \cdots \cap \widehat {\sigma _n}$
. By Fact 4.7 E can be extended to an ultrafilter. Let U be such ultrafilter. For any
$\sigma \in \mathsf {Th}(\mathfrak {M}) \widehat {\sigma }\in U$
and
$\widehat {\sigma }\subseteq \{i\in I:\mathfrak {M}_i\vDash \sigma \}$
. So
$\{i\in I:\mathfrak {M}_i\vDash \sigma \}\in U$
. By Lemma 4.9 we know that
$\underset {i\in I}{\mu }\mathfrak {M}_i/U\vDash \sigma $
for any
$\sigma \in \mathsf {Th}(\mathfrak {M})$
. Hence
$\underset {i\in I}{\mu }\mathfrak {M}_i/U\vDash \mathsf {Th}(\mathfrak {M})$
. By Lemma 5.14 we know that
$\mathfrak {M}\in \S ^{\underset {i\in I}{\mu }\mathfrak {M}_i/U}$
. Moreover,
$\underset {i\in I}{\mu }\mathfrak {M}_i/U\in \mathsf {K}$
so
$\mathfrak {M}\in \mathsf {K}$
.□
As a corollary of the definability theorem, compactness and Fact 5.15, we can state the following:
Corollary 5.17. Let
$\mathsf {K}$
be a set of models.
$\mathsf {K}$
is definable by a single formula iff
$\mathsf {K}$
is closed under
$\textsf {S}$
-sets and ultramodels and
$\overline {\mathsf {K}}$
is closed under ultramodels.
Proof. Let
$\mathsf {K}$
be a set of models defined by a single formula. Let
$\varphi \in \mathsf {FOR}$
be such formula. By Theorem 5.16 we know that
$\mathsf {K}$
is closed under
$\textsf {S}$
-sets and ultramodels. In order to show that
$\overline {\mathsf {K}}$
is closed under ultramodels, it is easy to notice that
$\overline {\mathsf {K}}$
is defined by
$\neg \varphi $
. For otherwise there would be
$\mathfrak {M}\in \overline {\mathsf {K}}$
such that
$\mathfrak {M}\vDash \varphi $
or
$\mathfrak {M}\in \mathsf {K}$
such that
$\mathfrak {M}\vDash \neg \varphi $
. Both disjuncts immediately lead to contradiction with the assumption that
$\varphi $
defines
$\mathsf {K}$
. Hence
$\neg \varphi $
defines
$\overline {\mathsf {K}}$
. This enables us to state that
$\overline {\mathsf {K}}$
is also closed under
$\textsf {S}$
-sets (which we knew already) and ultramodels. For the other direction, let
$\mathsf {K}$
be closed under
$\textsf {S}$
-sets and ultramodels and
$\overline {\mathsf {K}}$
be closed under ultramodels. By Fact 5.15,
$\overline {\mathsf {K}}$
is also closed under
$\textsf {S}$
-sets, so from 5.16 we know that both
$\mathsf {K}$
and
$\overline {\mathsf {K}}$
are definable. Let
$\Gamma \subseteq \mathsf {FOR}$
define
$\mathsf {K}$
and
$\Sigma \subseteq \mathsf {FOR}$
define
$\overline {\mathsf {K}}$
. We know that there is no model
$\mathfrak {M}=\langle v,\mathcal {R}\rangle $
such that
$\mathfrak {M}\vDash \Gamma \cup \Sigma $
because this would mean that
$\mathfrak {M}$
belongs to
$\mathsf {K}$
as well as
$\overline {\mathsf {K}}$
, which is impossible. For this reason,
$\Gamma \cup \Sigma $
is not satisfiable. By compactness, there is a finite subset
$\Delta \subseteq \Gamma \cup \Sigma $
such that
$\Delta $
is not satisfiable. We know that there are finite
$\Gamma _0\subseteq \Gamma $
,
$\Sigma _0\subseteq \Sigma $
such that
$\Delta =\Gamma _0\cup \Sigma _0$
. If one of those sets is empty, then either
$\mathsf {K}=\mathsf {M}$
or
$\overline {\mathsf {K}}=\mathsf {M}$
which means that the defining formula is
$p_0\lor \neg p_0$
for
$\mathsf {M}$
. Let us now assume that both
$\Gamma _0$
and
$\Sigma _0$
are non-empty. Let
$\Gamma _0=\{\gamma _0,\ldots ,\gamma _k\}$
,
$\Sigma _0=\{\sigma _0,\ldots ,\sigma _j\}$
. We know that
$\gamma _0\wedge \cdots \wedge \gamma _k\vDash \neg \sigma _0\lor \cdots \lor \neg \sigma _j$
. Let
$\varphi =\gamma _0\wedge \cdots \wedge \gamma _k$
. We conclude that
$\varphi $
defines
$\mathsf {K}$
.□
Up to this point, the reader may have an impression that the notion of an
$\textsf {S}$
-set seems to be some ad hoc construction introduced only to prove definability theorem 5.16. To prove him wrong, let us present some more concrete application. We will use
$\textsf {S}$
-lemma 5.14 to prove undefinability of some naturally emerging set of models, e.g., models with symmetric relation.
Proposition 5.18. Let
$\mathsf {M}^s$
be the set of symmetric models, i.e.,
$\mathsf {M}^s=\{\langle v,\mathcal {R}\rangle :\varphi \mathcal {R}\psi \Longrightarrow \psi \mathcal {R}\varphi \}$
.
$\mathsf {M}^s$
is not definable.
Proof. Assume that
$\mathsf {M}^s$
is definable. Let
$\Gamma \subseteq \mathsf {FOR}$
define
$\mathsf {M}^s$
. Let
$\mathfrak {M}=\langle v,\mathcal {R}\rangle $
, where
$v(p_0)=0$
and for each
$\varphi \in \Phi $
such that
$\varphi \neq p_0$
we have
$v(\varphi )=1$
. Let
$\mathcal {R}=\{\langle p_0,p_1\rangle ,\langle p_1, p_0\rangle \}$
.
$\mathcal {R}$
is symmetric so
$\mathfrak {M}\in \mathsf {M}^s$
. This means that
$\mathfrak {M}\vDash \Gamma $
. Observe that
$\langle p_1,p_0\rangle \in \Omega ^{\mathfrak {M}}$
since
$\mathfrak {M}\nvDash p_1\to p_0$
. Let
$\mathfrak {N}=\langle v',\mathcal {R}'\rangle $
where
$v'=v$
and
$\mathcal {R}'=\{\langle p_0,p_1\rangle \}$
. Notice that
$\mathcal {R}'=\mathcal {R}\setminus \Omega ^{\mathfrak {M}}$
so
$\mathfrak {N}\in \textsf {S}^{\mathfrak {M}}$
which by 5.14 means
$\mathfrak {M}\approx \mathfrak {N}$
. This means that
$\mathfrak {N}\vDash \Gamma $
. But
$\mathcal {R}'$
is not symmetric, so
$\mathfrak {N}\notin \mathsf {M}^s$
! Contradiction.
$\mathsf {M}^s$
is not definable.□
6 Conclusion
The main results of the paper are 1) the inexpressibility of connectives by any of its proper subsets, 2) purely model-theoretic proof of compactness and 3) (un)definability theorems. Those results were achieved by means of the three novel constructions introduced in the paper: reducts, ultramodels and
$\textsf {S}$
-sets. The author believes that the potential of the
$\textsf {S}$
-set construction reaches beyond the theorems just proven. These investigations will be subject of the future work.
