# Generalised Epstein Semantics Characterization, Interpolation,
Undefinability, and (In)Completeness

Krzysztof Aleksander Krawczyk

Abstract

This paper is a continuation of investigations concerning Epstein semantics
from [17]. The main tool of the present paper is the model-theoretic $\SS$-set
construction introduced in [17]. We use it to prove several results: 1) that
each Epstein model has uncountably many equivalent Epstein models, 2) that the
logic of generalised Epstein models is the $\SS$-set invariant fragment of
$\mathsf{CPL}$ (analogon of the celebrated van Benthem characterization
theorem for modal logic), 3) that several sets of Epstein models are
undefinable, 4) that logics of undefinable sets of relations can be finitely
axiomatised. We also use other techniques to prove: 5) that there is
uncountably many extensions of the logic of generalised Epstein models and,
following the well-known phenomenon of Kripke-incompleteness in modal logics,
we show that 6) there is uncountably many Epstein-incomplete logics. Finally,
we prove that 7) the logic of generalised Epstein models has the interpolation
property.

##  1 Introduction

In a series of publications [6, 7, 8, 9], Richard Epstein has introduced a
conceptually simple semantics for non-classical logics. His models are two-
element tuples containing standard boolean valuation of propositional
variables and a binary relation defined on the set of formulas. Epstein’s
motivations were mainly philosophical: he wanted to formalise the content-
relationship between propositions. However, he extended his research of the
so-called relatedness and dependence logics to purely mathematical form. Also,
he argued that his semantics can serve as adequate interpretations for other
non-classical logics, and can be used as a tool for analysing other, different
from the content-relationship, philosophical problems. This perspective has
been known as the Epstein programme, see [14, 15, 16]. Epstein’s ideas
inspired other researchers in the late seventies [24, 25], and studies on
Epstein semantics and related topics have been carried out up till nineties
[11, 4, 20, 18, 19]. More recently, Epstein ideas have been picked up in [12].
Despite some technical deficiencies111Statement marked as fact has been proven
to be false, see [17], the paper contains a two-folded generalisation of
Epstein ideas: relations of the models do not have to meet any conditions, and
additional Epstein-style connectives can be introduced. These simple
generalisations open a new perspective on the Epstein programme: it can be
extended and carried out with greater impetus.

The current work, being a continuation of [17], shares a common perspective
and ambition with the cited paper: to approach Epstein semantics from a purely
technical perspective, and thus, to establish it as a branch of mathematical
logic. In the current paper we investigate, exploit and modify the $\SS$-set
construction introduced in [17] for generalised Epstein semantics. We prove
that the cardinality of an $\SS$-set is always uncountable. Also, by means of
a translation into $\mathsf{CPL}$, we prove an analogon of the well-known van
Benthem characterization theorem for modal logic, which states that
generalised Epstein logic is an $\SS$-set invariant fragment of
$\mathsf{CPL}$. Later on, we prove completeness theorems for undefinable sets
of Epstein models and relations. Both undefinability of a given set of
relations/models, as well as completeness theorems are proven by means of an
$\SS$–set construction. In the latter case, the construction is modified to
enable us to obtain the set of all equivalent models from purely syntactical
entities. What is interesting, undefinable sets of structures turn out to be
axiomatisable (we do not need to add special rules). Axiomatisation is
achieved by means of special implicational formulas which have the form
$...\to(\varphi\ast^{\mathcal{E}}\psi)\lor\neg(\varphi\ast\psi)$, where
$\ast^{\mathcal{E}}$ stands for an Epstein-style connective. Also, we show
that there are uncountably many extensions of the system $\mathcal{F}$.
Analogously to the celebrated Blok’s theorem on the degree of incompleteness
of modal logic, we show that the number of Epstein-incomplete logics (the ones
that do not have adequate sets of Epstein relations) is $2^{\aleph_{0}}$. We
close the paper with the proof of the interpolation theorem for $\mathcal{F}$.

##  2 Preliminaries

We shall stick to the language introduced in [12]. Let
$\Phi=\\{p_{0},p_{1},p_{2},...\\}$ be the set of propositional letters. We
have one unary connective: negation $\neg$ and binary connectives:
$\lor,\wedge,\to,\leftrightarrow,\vartriangle,\looparrowright$. The set of
formulas $\mathsf{FOR}$ is built in a standard inductive way. We will use
$\top$ and $\bot$ as abbreviations for $p_{0}\lor\neg p_{0}$ and
$\neg(p_{0}\lor\neg p_{0})$ respectively. A substitution is any function
$\sigma:\mathsf{FOR}\longrightarrow\mathsf{FOR}$ which is an endomorphism of
the absolutely free formula algebra with domain $\mathsf{FOR}$. The set of all
substitutions will be denoted by $\mathsf{Subst}$.

An Epstein model is an ordered pair: $\mathfrak{M}=\langle
v,\mathfrak{R}\rangle$, where $v:\Phi\longrightarrow\\{0,1\\}$ is a standard
valuation and $\mathfrak{R}\subseteq\mathsf{FOR}\times\mathsf{FOR}$ is a
binary relation defined on the set of formulas. By $\mathsf{M}$ we will denote
the set of all models222We can use the word ‘set’ without committing to a
‘class’ since $\mathsf{M}=\\{\langle v,\mathfrak{R}\rangle:v\in
2^{\Phi},\mathfrak{R}\subseteq\mathsf{FOR}^{2}\\}$. The set of all relations
is $\mathcal{P}(\mathsf{FOR}^{2})$. Let $\varphi\in\mathsf{FOR}$,
$\mathfrak{M}=\langle v,\mathfrak{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\varphi,\psi\rangle\in\mathfrak{R}$ for
$\varphi=\psi\vartriangle\chi$,

  * •

($\mathfrak{M}\nvDash\psi$ or $\mathfrak{M}\vDash\chi$) and
$\langle\varphi,\psi\rangle\in\mathfrak{R}$ for
$\varphi=\psi\looparrowright\chi$.

Let $\mathfrak{M}\in\mathsf{M}$, $\Sigma\subseteq\mathsf{FOR}$. We will write
$\mathfrak{M}\vDash\Sigma$ to indicate that for any $\varphi\in\Sigma$:
$\mathfrak{M}\vDash\varphi$. Let $\mathsf{K}\subseteq\mathsf{M}$.
$\mathsf{K}\vDash\varphi$ means that for any $\mathfrak{M}\in\mathsf{K}$ we
have $\mathfrak{M}\vDash\varphi$. As it is usually done, we will also
understand $\vDash$ as a consequence relation. We say $\Sigma\vDash\varphi$
iff for any $\mathfrak{M}\in\mathsf{M}$ we have $\mathfrak{M}\vDash\Sigma$
implies $\mathfrak{M}\vDash\varphi$. We say that $\mathfrak{R}\vDash\varphi$
iff for any $v$: $\langle v,\mathfrak{R}\rangle\vDash\varphi$. Similarly
$\mathfrak{R}\vDash\Sigma$ iff for any $\sigma\in\Sigma$:
$\mathfrak{R}\vDash\sigma$. Let
$\mathsf{R}\subseteq\mathcal{P}(\mathsf{FOR}^{2})$ be the set of relations. We
say that $\mathsf{R}\vDash\varphi$ iff for any $\mathfrak{R}\in\mathsf{R}$ we
have $\mathfrak{R}\vDash\varphi$. Let $\Sigma\subseteq\mathsf{FOR}$,
$\varphi\in\mathsf{FOR}$ and $\mathsf{R}$ be some set of relations. We say
that $\Sigma\vDash_{\mathsf{R}}\varphi$ iff for any
$\mathfrak{R}\in\mathsf{R}$, any $\mathfrak{M}=\langle v,\mathfrak{R}\rangle$:
$\mathfrak{M}\vDash\Sigma$ implies $\mathfrak{M}\vDash\varphi$. One can see an
analogy between Epstein relations and the so called frames in modal logic.
Note an important difference though: unlike frames, Epstein relations do not
necessarily have theories that are closed under substitutions. To give an
example, let $\mathfrak{R}=\\{\langle p,p\rangle\\}$. It is easy to see that
$\mathfrak{R}\vDash p\looparrowright p$ but $\mathfrak{R}\nvDash
q\looparrowright q$. The difference between the theory of a single model and a
single relation theory is that the first one is complete in the sense that for
any $\varphi\in\mathsf{FOR}$: $\mathfrak{M}\vDash\varphi$ or
$\mathfrak{M}\vDash\neg\varphi$, while it is not the case for the latter. Any
propositional letter gives an immediate example: both $\mathfrak{R}\nvDash p$
and $\mathfrak{R}\nvDash\neg p$, for any $\mathfrak{R}$.

In [12] the consequence relation $\vDash$ has been called $\mathcal{F}$. The
authors constructed an adequate tableau deductive system for this consequence
relation. Here, we will focus on axiomatic system. Let $\mathsf{CPL}$ be the
set of all classical tautologies. Define $\mathcal{F}$ to be the least set
closed under uniform substitution and modus ponens (MP) $\\{p,p\to q\\}/q$
containing $\mathsf{CPL}$ and two additional axioms:

  1. 1.

$(p\looparrowright q)\to(p\to q)$

  2. 2.

$(p\vartriangle q)\leftrightarrow(p\looparrowright q)\wedge(p\wedge q)$

Let $\Lambda\subseteq\mathsf{FOR}$. By $\mathcal{F}\Lambda$ we will denote
least sets of formulas that contain $\mathcal{F}$ and $\Lambda$ which are
closed under uniform substitution and MP. Later on, we will refer to such sets
as logics. When $\Lambda=\\{\varphi\\}$ we will write $\mathcal{F}\varphi$ to
simplify notation.

Analogously to the semantic consequence relation, we define the syntactic
notion of derivability. Let $\Sigma\cup\\{\varphi\\}\subseteq\mathsf{FOR}$. We
say that $\varphi$ is derivable (provable) from $\Sigma$ (shortly
$\Sigma\vdash\varphi$) iff there is a standard Hilbert proof of $\varphi$ from
$\Sigma$, i.e. finite sequence of formulas whose last element is $\varphi$ and
all elements are either members of $\Sigma\cup\mathcal{F}$, or are obtained
from previous ones by means of MP. It is easy to see that for any
$\Lambda\subseteq\mathsf{FOR}$ we have $\varphi\in\mathcal{F}\Lambda$ iff
$\\{\sigma(\psi):\psi\in\Lambda,\sigma\in\mathsf{Subst}\\}\vdash\varphi$.

It is an exercise to check that $\vdash=\vDash$. $\subseteq$ is
straightforward. For $\supseteq$ let $\Sigma^{+}$ be a maximally consistent
set333Textbook Lindenbaum lemma can be used to show that each consistent set
can be extended to a maximally consistent one.. Let $\mathfrak{M}=\langle
v,\mathfrak{R}\rangle$ be such that for any $\psi\in\Phi$: $v(\psi)=1$ iff
$\psi\in\Sigma^{+}$; and $\langle\varphi,\chi\rangle\in\mathfrak{R}$ iff
$\varphi\looparrowright\chi\in\Sigma^{+}$. Inductive proof on the complexity
of formulas shows that $\mathfrak{M}\vDash\Sigma^{+}$. Base case and formulas
built with boolean connectives are obvious. Let
$\varphi\looparrowright\chi\in\Sigma^{+}$. Then, by MP and axiom 1), also
$\varphi\to\chi\in\Sigma^{+}$. Hence $\mathfrak{M}\vDash\varphi\to\chi$ and
$\langle\varphi,\chi\rangle\in\mathfrak{R}$ which gives us
$\mathfrak{M}\vDash\varphi\looparrowright\chi$. Now assume that
$\varphi\vartriangle\chi\in\Sigma^{+}$. Hence $\varphi\wedge\chi\in\Sigma^{+}$
and $\varphi\looparrowright\chi\in\Sigma^{+}$ which means
$\mathfrak{M}\vDash\varphi\wedge\chi$ and
$\langle\varphi,\chi\rangle\in\mathfrak{R}$, so
$\mathfrak{M}\vDash\varphi\looparrowright\chi$.

##  3 $\SS$–set basic definitions

In this section, we recall the notion of an $\SS$–set introduced in [17] and
prove that each Epstein model has uncountably many equivalent Epstein models.

Given a model $\mathfrak{M}=\langle v,\mathfrak{R}\rangle$, we define the
theory of $\mathfrak{M}$ to be the set:
$\mathsf{Th}(\mathfrak{M})=\\{\varphi\in\mathsf{FOR}:\mathfrak{M}\vDash\varphi\\}$.
Now let us define the relation of a theoretical equivalence.

######  Definition 3.1 (Theoretical equivalence).

Given the models $\mathfrak{M}=\langle v,\mathfrak{R}\rangle$,
$\mathfrak{N}=\langle v^{\prime},\mathfrak{R}^{\prime}\rangle$ we say that
$\mathfrak{M}$ and $\mathfrak{N}$ are theoretically equivalent, symbolically:
$\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}\in\mathsf{M}:\mathfrak{M}\approx\mathfrak{N}\\}$.

In [17], we have already introduced the $\SS$-set construction which enables
us to generate the whole equivalence class of a given model with respect to
relation $\approx$. Let us remind the construction. Let $\mathfrak{M}=\langle
v,\mathfrak{R}\rangle$. The Omega set of $\mathfrak{M}$ is
$\Omega^{\mathfrak{M}}=\\{\langle\varphi,\psi\rangle:\mathfrak{M}\nvDash\varphi\to\psi\\}$.
Having specified the Omega set of $\mathfrak{M}$ we define the $\SS$-set of
$\mathfrak{M}$ to be $\SS^{\mathfrak{M}}=\\{\langle
v^{\prime},\mathfrak{R}^{\prime}\rangle:v^{\prime}=v\,\,and\,\,\mathfrak{R}\setminus\Omega^{\mathfrak{M}}\subseteq\mathfrak{R}^{\prime}\subseteq\mathfrak{R}\cup\Omega^{\mathfrak{M}}\\}$.
Let us recall that the following holds:

######  Lemma 3.2 (Krawczyk, 2021).

For any $\mathfrak{M}=\langle v,\mathfrak{R}\rangle$ and $\mathfrak{N}=\langle
v^{\prime},\mathfrak{R}^{\prime}\rangle$, we have:
$\mathfrak{N}\in\SS^{\mathfrak{M}}$ iff $\mathfrak{N}\approx\mathfrak{M}$.
Hence $\SS^{\mathfrak{M}}=|\mathfrak{M}|_{\approx}$.

Now, we shall prove that for any model $\mathfrak{M}=\langle
v,\mathfrak{R}\rangle$, its $\SS$-set $\SS^{\mathfrak{M}}$ is always
uncountable:

######  Theorem 3.3.

For any $\mathfrak{M}=\langle v,\mathfrak{R}\rangle$ the cardinality of
$\SS^{\mathfrak{M}}$ is $2^{\aleph_{0}}$.

###### Proof.

First note that for any $\mathfrak{M}\in\mathsf{M}$, $\SS^{\mathfrak{M}}$ is
equinumerous with omega’s powerset: $\mathcal{P}(\Omega^{\mathfrak{M}})$. The
mapping $X\mapsto\langle v,(\mathfrak{R}\setminus\Omega^{\mathfrak{M}})\cup
X\rangle$ is a bijection from $\mathcal{P}(\Omega^{\mathfrak{M}})$ onto
$\SS^{\mathfrak{M}}$. It is easy to observe that $\Omega^{\mathfrak{M}}$ is
countably infinite. Define $\neg^{0}\top:=\top$ and
$\neg^{n+1}\top:=\neg\neg^{n}\top$. For any natural number $n$,
$\mathfrak{M}\nvDash\neg^{2n}\top\to\bot$, so $\Omega^{\mathfrak{M}}$ is
infinite. Language is countable and thus $\Omega^{\mathfrak{M}}$ is of
cardinality $\aleph_{0}$ and thus the cardinality of
$\mathcal{P}(\Omega^{\mathfrak{M}})$ is $2^{\aleph_{0}}$. ∎

Theorem 3.3 yields an immediate corollary: that each model has uncountably
many theoretically equivalent models.

##  4 The van Benthem characterization analogon

The well-known van Benthem characterization theorem [22, 1] states that modal
languages are the bisimulation invariant fragment of modal logic. The notion
of a standard translation plays a crucial role in proving this theorem.
Standard translation maps modal formulas into first order formulas of the
corresponding first order language in a natural way: it reflects the truth
conditions of a given modal formula. Modal operators naturally correspond to
quantifiers, so first order logic is the obvious target of the standard
translation mapping. Note though, that in the case of generalised Epstein
logic, such a mapping does not seem that obvious. There are no connectives
which necessarily impose using quantifiers to express their truth conditions.
Nonetheless, the use of atomic first order sentences comes quite naturally
i.e.
$St(\varphi\looparrowright\psi)=St(\varphi\to\psi)\wedge\mathcal{R}(\varphi,\psi)$,
where $\mathcal{R}$ is the binary relational symbol corresponding to
$\mathfrak{R}$. However, an atomic first order sentence
$\mathcal{R}(\varphi,\psi)$ can be treated as an atomic expression of
classical propositional logic. If we were to decode such a sentence by
indexing it with a pair of related elements, it would have the following form:
$p_{\langle\varphi,\psi\rangle}$. Now we can define the corresponding
classical propositional language. Let $\mathsf{At}$ be the set
$\Phi\cup\Phi^{\mathcal{R}}$, where
$\Phi^{\mathcal{R}}=\\{p_{\langle\varphi,\psi\rangle}:\varphi,\psi\in\mathsf{FOR}\\}$.
One can easily see that $\Phi^{\mathcal{R}}$ is countable, so our extended
language remains countable. The set of $\mathsf{CPL}$ formulas
$\mathsf{FOR}^{\ast}$ is the set generated from $\mathsf{At}$ and connectives:
$\neg,\wedge,\lor,\to,\leftrightarrow$. It is also important to notice that
with each Epstein model $\mathfrak{M}=\langle v,\mathfrak{R}\rangle$ we can
associate a valuation444The idea of treating Epstein models as valuations can
be found in [13] $V^{\mathfrak{M}}:\mathsf{At}\longrightarrow\\{0,1\\}$ which
is defined in the following way: for any $p_{n}\in\Phi$:
$V^{\mathfrak{M}}(p_{n})=1$ iff $v(p_{n})=1$ and for any
$p_{\langle\varphi,\psi\rangle}\in\Phi^{\mathcal{R}}$ we have
$V^{\mathfrak{M}}(p_{\langle\varphi,\psi\rangle})=1$ iff
$\langle\varphi,\psi\rangle\in\mathfrak{R}$. The valuation $V^{\mathfrak{M}}$
can be naturally extended to the set $\mathsf{FOR}^{\ast}$. This way, we can
say that the formula of $\mathsf{CPL}$ is true in a model iff the
corresponding valuation ascribes it the truth value ‘$1$’: for any
$A\in\mathsf{FOR}^{\ast}$, $\mathfrak{M}\models_{\mathsf{CPL}}A$ iff
$V^{\mathfrak{M}}(A)=1$. In fact, we can also define truth conditions for
$\mathsf{CPL}$ formulas for Epstein model $\mathfrak{M}=\langle
v,\mathfrak{R}\rangle$ without even mentioning valuations. We say that
$\mathfrak{M}\models_{\mathsf{CPL}}p_{n}$ iff $v(p_{n})=1$ and
$\mathfrak{M}\models_{\mathsf{CPL}}p_{\langle\varphi,\psi\rangle}$ iff
$\langle\varphi,\psi\rangle\in\mathfrak{R}$. Definition can be extended to
arbitrary formulas in a standard way. For $A\in\mathsf{FOR}^{\ast}$, we will
write $\models_{\mathsf{CPL}}A$ to indicate the fact that for any
$\mathfrak{M}=\langle v,\mathfrak{R}\rangle$ we have
$\mathfrak{M}\models_{\mathsf{CPL}}A$. Now we are ready to define the standard
translation for the language of Epstein logic.
$St:\mathsf{FOR}\longrightarrow\mathsf{FOR}^{\ast}$.

  * •

$St(p_{n})=p_{n}$,

  * •

$St(\neg\varphi)=\neg St(\varphi)$,

  * •

$St(\varphi\ast\psi)=St(\varphi)\ast St(\psi)$, for
$\ast\in\\{\lor,\wedge,\to,\leftrightarrow\\}$.

  * •

$St(\varphi\looparrowright\psi)=St(\varphi\to\psi)\wedge
p_{\langle\varphi,\psi\rangle}$

  * •

$St(\varphi\vartriangle\psi)=St(\varphi\wedge\psi)\wedge
p_{\langle\varphi,\psi\rangle}$.

Obviously, the following holds for any $\mathfrak{M}=\langle
v,\mathfrak{R}\rangle$: $\mathfrak{M}\vDash\varphi$ iff
$\mathfrak{M}\models_{\mathsf{CPL}}St(\varphi)$. Now we can ask the following
question: when is a formula of $\mathsf{CPL}$ equivalent to a standard
translation of some Epstein formula? The answer is given by the
characterization theorem. We say that a formula $A$ of $\mathsf{FOR}^{\ast}$
is $\SS$-set invariant iff for any $\mathfrak{M}=\langle
v,\mathfrak{R}\rangle$, $\mathfrak{N}=\langle
v^{\prime},\mathfrak{R}^{\prime}\rangle$,
$\mathfrak{M}\models_{\mathsf{CPL}}A$ and $\mathfrak{N}\in\SS^{\mathfrak{M}}$
implies $\mathfrak{N}\models_{\mathsf{CPL}}A$. In order to prove our version
of characterization theorem, we will use the standard techniques from [1].

######  Theorem 4.1.

Let $A\in\mathsf{FOR}^{\ast}$. There is $\varphi\in\mathsf{FOR}$ such that
$\models_{\mathsf{CPL}}A\leftrightarrow St(\varphi)$ iff $A$ is $\SS$-set
invariant.

###### Proof.

The left to right direction follows from the $\SS$-set Lemma 6.6 and from the
previously mentioned fact that for any $\mathfrak{M}=\langle
v,\mathfrak{R}\rangle$: $\mathfrak{M}\vDash\varphi$ iff
$\mathfrak{M}\models_{\mathsf{CPL}}St(\varphi)$. For the right to left, assume
that $A\in\mathsf{FOR}^{\ast}$ is $\SS$-set invariant. Let
$RC(A)=\\{B:B=St(\psi)\,\,for\,\,some\,\,\psi\in\mathsf{FOR}\,\,and\,\,A\models_{\mathsf{CPL}}B\\}$.
If $A$ is inconsistent, then $A$ is equivalent to $St(p_{0}\wedge\neg p_{0})$.
Assume then, that $A$ is consistent. This means that $RC(A)$ is consistent.
Let $\mathfrak{M}=\langle v,\mathfrak{R}\rangle$ be such that
$\mathfrak{M}\models_{\mathsf{CPL}}RC(A)$. Let
$T(\mathfrak{M})=\\{B:B=St(\psi)\,\,for\,\,some\,\,\psi\in\mathsf{FOR}\,\,and\,\,\mathfrak{M}\models_{\mathsf{CPL}}B\\}$.
$T(\mathfrak{M})\cup\\{A\\}$ is consistent. If it was not, then
$A\not\models_{\mathsf{CPL}}X$ for some $X=\\{C_{1},...,C_{n}\\}\subseteq
T(\mathfrak{M})$. This would mean that $\neg C_{1}\lor...\lor\neg C_{n}\in
RC(A)$ and also $\neg C_{1}\lor...\lor\neg C_{n}\in T(\mathfrak{M})$ which
leads to a contradiction. Let $\mathfrak{N}=\langle
v^{\prime},\mathfrak{R}^{\prime}\rangle$ be such that
$\mathfrak{N}\models_{\mathsf{CPL}}T(\mathfrak{M})\cup\\{A\\}$. Since
$\mathfrak{N}\models_{\mathsf{CPL}}T(\mathfrak{M})$, we know that
$\mathfrak{N}\approx\mathfrak{M}$. This means that
$\mathfrak{M}\in\SS^{\mathfrak{N}}$. We assumed that $A$ is $\SS$-set
invariant so $\mathfrak{M}\models_{\mathsf{CPL}}A$. This means that
$RC(A)\models_{\mathsf{CPL}}A$. By compactness of $\mathsf{CPL}$, we obtain
$\models_{\mathsf{CPL}}B_{1}\wedge...\wedge B_{n}\leftrightarrow A$, where
$\\{B_{1},...,B_{n}\\}\subseteq RC(A)$. Each $B_{i}=St(\psi_{i})$, so
$\models_{\mathsf{CPL}}A\leftrightarrow St(\psi_{1}\wedge...\wedge\psi_{n})$.
∎

##  5 Epstein incompleteness

It was a significant breakthrough in the theory of modal logic when examples
of Kripke-incomplete logics (the ones with no adequate class of Kripke frames)
were found [21, 10, 23]. This discoveries culminated in a shocking Blok’s
result [2] where uncountably many normal modal logics with no adequate classes
of Kripke frames were proven to exist. We will prove an analogous theorem for
Epstein relations. However, to make the reasoning clear, we shall proceed step
by step. First we will give an example of Epstein-incomplete logic (logic with
no adequate set of Epstein relations). Then we will show that there are
continuum many axiomatic extensions of $\mathcal{F}$. Finally, we will combine
both techniques to prove that there are uncountably many Epstein incomplete
axiomatic extensions of $\mathcal{F}$.

Following the preliminary section, by a logic we understand a set of formulas
containing $\mathcal{F}$, closed under uniform substitution and Modus Ponens.
A logic $\lambda$ is Epstein complete iff there is a set
$X\subseteq\mathcal{P}(\mathsf{FOR}^{2})$ of Epstein relations such that
$\lambda=\\{\varphi:X\vDash\varphi\\}$. Otherwise, a logic is said to be
Epstein-incomplete.

We start with an example of Epstein-incomplete logic. Let
$\alpha:=p\to(q\looparrowright p)$.

######  Lemma 5.1.

For any Epstein relation $\mathfrak{R}$ such that
$\mathfrak{R}\vDash\\{\sigma(\alpha):\sigma\in\mathsf{Subst}\\}$ we also have
$\mathfrak{R}\vDash p\looparrowright p$.

###### Proof.

Assume that $\mathfrak{R}\nvDash p\looparrowright p$. Hence it must be the
case that $\langle p,p\rangle\notin\mathfrak{R}$. Take substitution $\sigma$
s.t. $\sigma(q)=p$ and for the remaining propositional letters $\varphi\neq
q$, $\sigma(\varphi)=\varphi$. Then $\sigma(\alpha)=p\to(p\looparrowright p)$.
Take valuation $v$ s.t. for any propositional letter $\varphi$,
$v(\varphi)=1$. Then $\langle v,\mathfrak{R}\rangle\nvDash
p\to(p\looparrowright p)$, so $\mathfrak{R}\nvDash p\to(p\looparrowright p)$.
Hence $\mathfrak{R}\nvDash\\{\sigma(\alpha):\sigma\in\mathsf{Subst}\\}$. ∎

######  Lemma 5.2.

$p\looparrowright p\notin\mathcal{F}\alpha$.

###### Proof.

It is enough to show that $\\{\sigma(\alpha):\sigma\in\mathsf{Subst}\\}\nvDash
p\looparrowright p$. Let $\mathfrak{M}=\langle v,\mathfrak{R}\rangle$ where
$\mathfrak{R}=\mathsf{FOR}^{2}\setminus\\{\langle p,p\rangle\\}$ and
$v(\varphi)=0$ for each propositional letter $\varphi$. Let
$\psi\in\mathsf{FOR}$ be any formula s.t. $\psi\neq p$. Assume
$\mathfrak{M}\vDash\psi$. Hence also $\chi\to\psi$ for any
$\chi\in\mathsf{FOR}$. Also $\langle\chi,\psi\rangle\in\mathfrak{R}$, so
$\mathfrak{M}\vDash\psi\to(\chi\looparrowright\psi)$. If, on the other hand,
$\psi=p$, then $\mathfrak{M}\nvDash p$, so also $\mathfrak{M}\vDash
p\to(p\looparrowright p)$. This gives us
$\mathfrak{M}\vDash\\{\sigma(\alpha):\sigma\in\mathsf{Subst}\\}$. But
obviously $\mathfrak{M}\nvDash p\looparrowright p$, so
$\\{\sigma(\alpha):\sigma\in\mathsf{Subst}\\}\nvDash p\looparrowright p$ which
gives the result. ∎

######  Theorem 5.3.

$\mathcal{F}\alpha$ is Epstein incomplete.

###### Proof.

Assume that there is a set of relations $\mathsf{R}$ such that
$\mathcal{F}\alpha=\\{\varphi:\forall\mathfrak{R}\in\mathsf{R}\,\,\,\mathfrak{R}\vDash\varphi\\}$.
Then by Lemma 5.1 $p\looparrowright p\in\mathcal{F}\alpha$. But by Lemma 5.2
$p\looparrowright p\notin\mathcal{F}\alpha$. Contradiction, so
$\mathcal{F}\alpha$ is Epstein incomplete. ∎

Knowing how to construct an Epstein-incomplete logic, we can move on to prove
that there are uncountably many axiomatic extensions of $\mathcal{F}$.

######  Theorem 5.4.

There are $2^{\aleph_{0}}$ extensions of $\mathcal{F}$.

###### Proof.

Let $p^{0}:=p$. Define $p^{n+1}:=p\to p^{n}$. Now let $K=\\{p\looparrowright
p^{n}:n\in\omega\\}$. Hence elements of $K$ are of the form
$p\looparrowright(p\to p)(=p\looparrowright p^{1})$,
$p\looparrowright(p\to(p\to p))(=p\looparrowright p^{2})$, and so on. Let
$S\subseteq\omega$. Let $K_{S}=\\{p\looparrowright p^{k}:k\in S\\}$. Hence
$K_{S}\subseteq K$. To prove the theorem, we will show that for each two non-
empty subsets of natural numbers $S,T$ such that $S\neq T$ we have
$\mathcal{F}K_{S}\neq\mathcal{F}K_{T}$. Let $S,T$ be such subsets. Without the
loss of generality assume that $n\in S\setminus T$. Let $\mathfrak{M}=\langle
v,\mathfrak{R}\rangle$ be such that
$\mathfrak{R}=(\mathsf{FOR}\times\mathsf{FOR})\setminus\\{\langle
p,p^{n}\rangle\\}$. Let $k\neq n$. It is obvious that
$\mathfrak{M}\vDash\sigma(p^{k})$ for any $\sigma\in\mathsf{Subst}$, since
$p^{k}$ is a tautology. Also $\langle\sigma(p),\sigma(p^{k})\rangle\in R$
since otherwise we would get $n=k$, contradiction. Thus
$\mathfrak{M}\vDash\sigma(p\looparrowright p^{k})$. Thus we have shown that
$\mathfrak{M}\vDash\\{\sigma(p\looparrowright p^{k}):k\neq
n,\sigma\in\mathsf{Subst}\\}$ and thus obviously
$\mathfrak{M}\vDash\\{\sigma(\psi):\psi\in K_{T}\\}$, since
$\\{\sigma(\psi):\psi\in K_{T}\\}\subseteq\\{\sigma(p\looparrowright
p^{k}):k\neq n,\sigma\in\mathsf{Subst}\\}$. But also $\mathfrak{M}\nvDash
p\looparrowright p^{n}$, so $\\{\sigma(\psi):\psi\in K_{T}\\}\nvDash
p\looparrowright p^{n}$ which means $\mathcal{F}K_{T}\neq\mathcal{F}K_{S}$. ∎

Now we will combine previous techniques to show that there are uncountably
many extensions of $\mathcal{F}$ which are Epstein incomplete. First we
construct a sequence of formulas similar to the one from the proof of Theorem
5.4

$\displaystyle p^{0}$ $\displaystyle:=q\looparrowright p$ $\displaystyle
p^{n+1}$ $\displaystyle:=p\to p^{n}$

We have $p^{1}=p\to(q\looparrowright p)$ and $p_{2}$ is
$p\to(p\to(q\looparrowright p))$ etc. Now we define a set of formulas
$K:=\\{q\looparrowright p^{n}:1\leq n\in\omega\\}$.

######  Lemma 5.5.

For any $n\in\omega\setminus\\{0\\}$, any Epstein relation $\mathfrak{R}$, if
$\mathfrak{R}\vDash\\{\sigma(q\looparrowright
p^{n}):\sigma\in\mathsf{Subst}\\}$, then $\mathfrak{R}\vDash p\looparrowright
p$.

###### Proof.

Let $\sigma$ be a substitution such that $\sigma(q)=p$ and for the rest of
propositional letters $\sigma(\varphi)=\varphi$. Hence
$\sigma(q\looparrowright p^{n})$ is of the form
$p\looparrowright\underbrace{(p\to(p\to...}_{\text{n times}}(p\looparrowright
p)...)$. Let $\mathfrak{R}\vDash\sigma(q\looparrowright p^{n})$. Obviously, it
must be the case that $\langle p,\sigma(p^{n})\rangle\in\mathfrak{R}$. Assume
that $\langle p,p\rangle\notin\mathfrak{R}$. Let $v(p)=1$. Obviously $\langle
v,\mathfrak{R}\rangle\nvDash p\looparrowright p$, hence $\langle
v,\mathfrak{R}\rangle\nvDash p\to(p\looparrowright p)$, and $\langle
v,\mathfrak{R}\rangle\nvDash p\to(p\to(p\looparrowright p))$, and so on. Thus
$\langle v,\mathfrak{R}\rangle\nvDash\sigma(p^{n})$ for any $n\in\omega$.
Hence also $\langle v,\mathfrak{R}\rangle\nvDash
p\looparrowright\sigma(p^{n})$ for any $n\in\omega$ which gives us
contradiction. Hence $\langle p,p\rangle\in\mathfrak{R}$ and for this reason
$\mathfrak{R}\vDash p\looparrowright p$. ∎

######  Lemma 5.6.

Let $S$ be a non-empty subset of $\omega$. Then $\\{\sigma(q\looparrowright
p^{n}):n\in S,\sigma\in\mathsf{Subst}\\}\nvDash p\looparrowright p$.

###### Proof.

Let $\mathfrak{M}=\langle v,\mathfrak{R}\rangle$ be such that
$\mathfrak{R}=\mathsf{FOR}\times\mathsf{FOR}\setminus\\{\langle p,p\rangle\\}$
and $v(p)=0$. Let $\psi\in\mathsf{FOR}$ and $\psi\neq p$. For any
$\varphi\in\mathsf{FOR}$, we have $\langle
v,\mathfrak{R}\rangle\vDash\varphi\to(\psi\looparrowright\varphi)$. To see
that assume $\langle v,\mathfrak{R}\rangle\vDash\varphi$. Hence also $\langle
v,\mathfrak{R}\rangle\vDash\psi\to\varphi$ and since
$\langle\psi,\varphi\rangle\in\mathfrak{R}$, we get $\langle
v,\mathfrak{R}\rangle\vDash\psi\looparrowright\varphi$. Straightforward
inductive step shows that we get for any $n\in\omega$, $\langle
v,\mathfrak{R}\rangle\vDash\varphi\to\varphi^{n}$ and since
$\langle\psi,\varphi^{n}\rangle\in\mathfrak{R}$ it is also the case that
$\langle v,\mathfrak{R}\rangle\vDash\psi\looparrowright\varphi^{n}$. Now let
$\psi=p$. If $\varphi\neq p$, the reasoning from the previous case applies
since then $\langle p,\varphi\rangle\in\mathfrak{R}$. Now let $\varphi=p$.
Then for each formula of the form $p\to(p\to...(p\looparrowright p)...)$ we
have $\mathfrak{M}\vDash p\to(p\to...(p\looparrowright p)...)$ since $\langle
v,\mathfrak{R}\rangle\nvDash p$. Observe that $p$ is not a formula of the
above form – see definition of $\varphi^{n}$. Thus we also have $\langle
p,p\to(p\to...(p\looparrowright p)...)\rangle\in\mathfrak{R}$ which means
$\mathfrak{M}\vDash p\looparrowright(p\to(p\to...(p\looparrowright p)...)$.
Thus we got $\mathfrak{M}\vDash\\{\sigma(p\looparrowright
p^{n}):n\in\omega,\sigma\in\mathsf{Subst}\\}$ and since $S\subseteq\omega$
also $\mathfrak{M}\vDash\\{\sigma(p\looparrowright p^{n}):n\in
S,\sigma\in\mathsf{Subst}\\}$. But also $\mathfrak{M}\nvDash p\looparrowright
p$ since $\langle p,p\rangle\notin\mathfrak{R}$ which proves the lemma. ∎

######  Lemma 5.7.

Let $S$ and $T$ be a non-empty subsets of $\omega\setminus\\{0\\}$ such that
$S\neq T$. Then $\mathcal{F}\Lambda_{S}\neq\mathcal{F}\Lambda_{T}$.

###### Proof.

Without the loss of generality, assume that there is $k\in S\setminus T$. Let
$\mathfrak{M}=\langle v,\mathfrak{R}\rangle$ be such that
$\mathfrak{R}=\mathsf{FOR}\times\mathsf{FOR}\setminus\\{\langle
q,p^{k}\rangle\\}$ and for any propositional letter $\varphi$, $v(\varphi)=0$.
Observe that for any $n\neq k$, any $\sigma\in\mathsf{Subst}$,
$\mathfrak{M}\vDash\sigma(q\looparrowright p^{n})$. To see that let $n\neq k$
and $\sigma\in\mathsf{Subst}$. We will consider several cases.

If $\sigma(q)=q$, then $\mathfrak{M}\nvDash\sigma(q)$ and so
$\mathfrak{M}\vDash\sigma(q\to p^{n})$. It is obvious that
$\sigma(p^{n})\neq(p^{k})$ so
$\langle\sigma(q),\sigma(p^{n})\rangle\in\mathfrak{R}$ and thus
$\mathfrak{M}\vDash\sigma(q\looparrowright p^{n})$.

Let $\sigma(q)\neq q$. Then $\langle\sigma(q),\sigma(p)\rangle\in\mathfrak{R}$
and thus $\mathfrak{M}\vDash\sigma(p^{n})$. Also
$\mathfrak{M}\vDash\sigma(q)\to\sigma(p^{n})$ and
$\langle\sigma(q),\sigma(p^{n})\rangle\in\mathfrak{R}$, so
$\mathfrak{M}\vDash\sigma(q)\looparrowright\sigma(p^{n})$.

We have shown that $\mathfrak{M}\vDash\\{\sigma(q\looparrowright p^{n})$ for
each $1\leq n\neq k$ and thus also
$\mathfrak{M}\vDash\\{\sigma(\varphi):\varphi\in
K_{T},\sigma\in\mathsf{Subst}\\}$. Obviously $\mathfrak{M}\nvDash
q\looparrowright p^{k}$, which means that $q\looparrowright
p^{k}\notin\mathcal{F}K_{T}$. We conclude that
$\mathcal{F}K_{S}\neq\mathcal{F}K_{T}$. ∎

Now we can prove the theorem.

######  Theorem 5.8.

There are $2^{\aleph_{0}}$ Epstein incomplete extensions of $\mathcal{F}$.

###### Proof.

For any non-empty $S\subseteq\omega\setminus\\{0\\}$, we have
$p\looparrowright p\notin\mathcal{F}K_{S}$ by lemma 5.6. Also for each Epstein
relation $\mathfrak{R}$ s.t. $\mathfrak{R}\vDash\mathcal{F}K_{S}$ we have
$\mathfrak{R}\vDash p\looparrowright p$ by lemma 5.5, so $\mathcal{F}K_{S}$ is
Epstein incomplete for each $\emptyset\neq S\subseteq\omega\setminus\\{0\\}$.
By Lemma 5.7 we have uncountably many such logics. ∎

##  6 The two conditions: undefinability and strong completeness

In order to show the power of our methods, we choose to analyze two exemplary
conditions: symmetry and the one that may be called predecessor – negation
elimination. Both of them, among some others, are imposed by Epstein on the
models of his relatedness logics [8].

  * (s)

: Symmetry: for any $\varphi,\psi$: if $\varphi\mathfrak{R}\psi$, then
$\psi\mathfrak{R}\varphi$,

  * (n)

: for any $\varphi,\psi$: if $\neg\varphi\mathfrak{R}\psi$ then
$\varphi\mathfrak{R}\psi$.

The first condition is a standard first order property (expressible in a
language with a single binary relation symbol), while the second one concerns
the composition of a given formula and thus, forces us to treat logical
connectives of our sentential language as operational symbols in
metalanguage555Observe that $\neg$ in the (n) condition – perceived as a
generally quantified first order sentence – should be treated as a unary
operation on variable $\varphi$ and not as the logical connective of first
order logic!. These properties are in a way representative for Epstein
relations, showing that besides some standard properties, they allow us to
force some conditions which concern the very structure of formulas.

Observe that both of these conditions are undefinable. We will apply the
technique already used in [17] to prove its undefinablity.

######  Definition 6.1.

Let $\mathsf{K}$ be some set of Epstein models, $\Gamma\subseteq\mathsf{FOR}$.
We say that $\Gamma$ defines $\mathsf{K}$ when the following holds: for any
Epstein model $\mathfrak{M}$, $\mathfrak{M}\vDash\Gamma$ iff
$\mathfrak{M}\in\mathsf{K}$. We say that the set of models $\mathsf{K}$ is
definable iff there is $\Gamma\subseteq\mathsf{FOR}$ such that $\Gamma$
defines $\mathsf{K}$. Analogously, we define the definability of a given set
of Epstein relations.

######  Proposition 6.2.

Let $\mathsf{M}^{s}$ be the set of symmetric models, $\mathsf{M}^{n}$ be the
set of models with (n)-relations i.e. $\mathsf{M}^{s}=\\{\langle
v,\mathfrak{R}\rangle:\mathfrak{R}\,\,\text{is symmetric}\\}$,
$\mathsf{M}^{n}=\\{\langle
v,\mathfrak{R}\rangle:\neg\varphi\mathfrak{R}\psi\Longrightarrow\varphi\mathfrak{R}\psi\\}$.
Both $\mathsf{M}^{s}$ and $\mathsf{M}^{n}$ are not definable.

###### Proof.

Assume that $\mathsf{M}^{s}$ is definable666The case for symmetric models has
been proven already in [17]. We decide to include the proof here for the sake
of self-containment.. Let $\Gamma\subseteq\mathsf{FOR}$ define
$\mathsf{M}^{s}$. Let $\mathfrak{M}=\langle v,\mathfrak{R}\rangle$, where
$v(p)=0$ and for each $\varphi\in\Phi$ such that $\varphi\neq p$ we have
$v(\varphi)=1$. Let $\mathfrak{R}=\\{\langle p,q\rangle,\langle
q,p\rangle\\}$. $\mathfrak{R}$ is symmetric so
$\mathfrak{M}\in\mathsf{M}^{s}$. This means that $\mathfrak{M}\vDash\Gamma$.
Observe that $\langle q,p\rangle\in\Omega^{\mathfrak{M}}$. Let
$\mathfrak{N}=\langle v^{\prime},\mathfrak{R}^{\prime}\rangle$ where
$v^{\prime}=v$ and $\mathfrak{R}^{\prime}=\\{\langle p,q\rangle\\}$. Notice
that $\mathfrak{R}^{\prime}=\mathfrak{R}\setminus\Omega^{\mathfrak{M}}$ so
$\mathfrak{M}\approx\mathfrak{N}$ by (3.2). This means that
$\mathfrak{N}\vDash\Gamma$. But $\mathfrak{R}^{\prime}$ is not symmetric, so
$\mathfrak{N}\notin\mathsf{M}^{s}$! Contradiction. $\mathsf{M}^{s}$ is not
definable.

Assume now that $\mathsf{M}^{n}$ is definable. Let $\Sigma$ define
$\mathsf{M}^{n}$. Let $\mathfrak{M}=\langle v,\mathfrak{R}\rangle$ where
$\mathfrak{R}=\\{\langle\neg p,q\rangle,\langle p,q\rangle\\}$, $v(p)=1$ and
for any $\varphi\in\Phi$ such that $p\neq\varphi$ we have $v(\varphi)=0$.
Model’s relation $\mathfrak{R}$ meets the (n) condition so
$\mathfrak{M}\in\mathsf{M}^{n}$. This means that $\mathfrak{M}\vDash\Sigma$.
Let $\mathfrak{N}=\langle v^{\prime},\mathfrak{R}^{\prime}\rangle$ be such
that $v=v^{\prime}$ and $\mathfrak{R}^{\prime}=\\{\langle\neg p,q\rangle\\}$.
It is easy to see that
$\mathfrak{R}^{\prime}=\mathfrak{R}\setminus\Omega^{\mathfrak{M}}$. So
$\mathfrak{N}\vDash\Sigma$ by (3.2). But $\mathfrak{N}\notin\mathsf{M}^{n}$.
Contradiction. ∎

######  Proposition 6.3.

Let $\mathsf{R}^{s}$ be the set of all symmetric relations, $\mathsf{R}^{n}$
the set of all relations fulfilling $n$ condition. Both $\mathsf{R}^{s}$ and
$\mathsf{R}^{n}$ are undefinable.

###### Proof.

For symmetry assume that $\mathsf{R}^{s}$ is definable. Let $\Gamma$ define
$\mathsf{R}^{s}$. Let $\mathfrak{R}=\\{\langle p,q\rangle,\langle
q,p\rangle\\}$. $\mathfrak{R}$ is symmetric, so $\mathfrak{R}\vDash\Gamma$.
This means that for any $v$, any $\mathfrak{M}=\langle v,\mathfrak{R}\rangle$
we have $\mathfrak{M}\vDash\Gamma$. Let $v^{\prime}$ be arbitrary and
$\mathfrak{M}^{\prime}=\langle v^{\prime},\mathfrak{R}\rangle$. Obviously
$\mathfrak{M}^{\prime}\nvDash\top\to\bot$. Let
$\mathfrak{R}^{\prime}=\mathfrak{R}\cup\\{\langle\top,\bot\rangle\\}$. It is
easy to see that $\langle\top,\bot\rangle\in\Omega^{\mathfrak{M}^{\prime}}$
(actually, $\langle\top,\bot\rangle$ is in $\Omega^{\mathfrak{M}}$ for any
$\mathfrak{M}$), so
$\mathfrak{R}^{\prime}\subseteq\mathfrak{R}\cup\Omega^{\mathfrak{M}^{\prime}}$.
Also
$\mathfrak{R}\setminus\Omega^{\mathfrak{M}^{\prime}}\subseteq\mathfrak{R}^{\prime}$.
Let $\mathfrak{M}^{\prime\prime}=\langle
v^{\prime},\mathfrak{R}^{\prime}\rangle$. Valuation is the same, so
$\mathfrak{M}^{\prime\prime}\in\SS^{\mathfrak{M}^{\prime}}$, hence
$\mathfrak{M}^{\prime\prime}\vDash\Gamma$. Note that $v^{\prime}$ was
arbitrary hence $\mathfrak{R}^{\prime}\vDash\Gamma$. But
$\langle\bot,\top\rangle\notin\mathfrak{R}^{\prime}$, so
$\mathfrak{R}^{\prime}$ is not symmetric! Contradiction.

Assume that $\mathsf{R}^{n}$ is definable. Let $\Delta$ define
$\mathsf{R}^{n}$. Let $\mathfrak{R}=\\{\langle\neg p,q\rangle,\langle
p,q\rangle\\}$. Obviously $\mathfrak{R}\in\mathsf{R}^{n}$. This means that
$\mathfrak{R}\vDash\Delta$. Let $v$ be arbitrary valuation. We know that
$\mathfrak{M}=\langle v,\mathfrak{R}\rangle\vDash\Delta$ and also that
$\mathfrak{M}\nvDash\neg\bot\to\bot$. This means that
$\langle\neg\bot,\bot\rangle\in\Omega^{\mathfrak{M}}$. Let
$\mathfrak{N}=\langle v^{\prime},\mathfrak{R}^{\prime}\rangle$ where
$v^{\prime}=v$ and
$\mathfrak{R}^{\prime}=\mathfrak{R}\cup\\{\langle\neg\bot,\bot\rangle\\}$. It
is easy to see that
$\mathfrak{R}\setminus\Omega^{\mathfrak{M}}\subseteq\mathfrak{R}^{\prime}\subseteq\mathfrak{R}\cup\Omega^{\mathfrak{M}}$,
so $\mathfrak{N}\vDash\Delta$. But $v=v^{\prime}$ was arbitrary hence
$\mathfrak{R}^{\prime}\vDash\Delta$. But
$\langle\bot,\bot\rangle\notin\mathfrak{R}^{\prime}$ so
$\mathfrak{R}^{\prime}\notin\mathfrak{R}^{n}$. Contradiction. ∎

######  Proposition 6.4.

$\mathsf{M}^{s}\cap\mathsf{M}^{n}$ and $\mathsf{R}^{s}\cap\mathsf{R}^{n}$ are
undefinable.

###### Proof.

Assume that $\mathsf{M}^{s}\cap\mathsf{M}^{n}$ is definable. Let $\Gamma$
define $\mathsf{M}^{s}\cap\mathsf{M}^{n}$. Let $\mathfrak{M}=\langle
v,\mathfrak{R}\rangle$, where $\mathfrak{R}=\emptyset$. Empty relation is both
symmetric and meets the (n) condition, so
$\mathfrak{M}\in\mathsf{M}^{s}\cap\mathsf{M}^{n}$. This means
$\mathfrak{M}\vDash\Gamma$. Let $\mathfrak{N}=\langle
v,\mathfrak{R}^{\prime}\rangle$ where
$\mathfrak{R}^{\prime}=\langle\top,\bot\rangle$. Obviously
$\mathfrak{R}^{\prime}\subseteq\mathfrak{R}\cup\Omega^{\mathfrak{M}}$, so
$\mathfrak{N}\vDash\Gamma$. But
$\mathfrak{N}\notin\mathsf{M}^{s}\cap\mathsf{M}^{n}$, since $\mathfrak{N}$ is
not symmetric.

To show that $\mathsf{R}^{s}\cap\mathsf{R}^{n}$ is undefinable we reason in
the same manner, assuming that $\mathsf{R}^{s}\cap\mathsf{R}^{n}$ is definable
by some set of formulas $\Sigma$. We notice that
$\mathfrak{R}=\emptyset\in\mathsf{R}^{s}\cap\mathsf{R}^{n}$. We use (3.2) to
show that $\mathfrak{R}^{\prime}=\langle\top,\bot\rangle$ satisfies the
defining set of formulas $\Sigma$ which immediately leads us to contradiction.
∎

###  6.1 The $\SS$ set – syntactical version

In order to obtain $\SS^{\mathfrak{M}}$ we have to know the structure of a
model $\mathfrak{M}$. It can be the case, though, that we do not know the
structure of a given model $\mathfrak{M}$, but we want to construct the set
$|\mathfrak{M}|_{\approx}$ knowing only its theory. Now we shall introduce the
way of obtaining $|\mathfrak{M}|_{\approx}$ from the theory of $\mathfrak{M}$.
Assume that we know the theory $\mathsf{Th}(\mathfrak{M})$ of some model
$\mathfrak{M}$.

######  Definition 6.5.

We define two relations in the following way:

$\displaystyle\mathfrak{R}^{\mathsf{Th}(\mathfrak{M})}_{\mathsf{min}}$
$\displaystyle=\\{\langle\varphi,\psi\rangle:\varphi\looparrowright\psi\in\mathsf{Th}(\mathfrak{M})\\},$
$\displaystyle\mathfrak{R}^{\mathsf{Th}(\mathfrak{M})}_{\mathsf{max}}$
$\displaystyle=\\{\langle\varphi,\psi\rangle:\varphi\looparrowright\psi\in\mathsf{Th}(\mathfrak{M})\,\,or\,\,\varphi\to\psi\notin\mathsf{Th}(\mathfrak{M})\\}.$

We also define the valuation
$v^{\mathsf{Th}(\mathfrak{M})}=\Phi\longrightarrow\\{0,1\\}$ which fulfils the
following conditions: $v^{\mathsf{Th}(\mathfrak{M})}(\varphi)=1$ iff
$\varphi\in\mathsf{Th}(\mathfrak{M})$, for any $\varphi\in\Phi$. Now we define
the $\SS^{\mathsf{Th}(\mathfrak{M})}$ set, the set of models similar to
$\mathfrak{M}$:

$\SS^{\mathsf{Th}(\mathfrak{M})}=\\{\mathfrak{N}=\langle
v^{\prime},\mathfrak{R}^{\prime}\rangle:v^{\prime}=v^{\mathsf{Th}(\mathfrak{M})}\,\,\&\,\,\mathfrak{R}^{\mathsf{Th}(\mathfrak{M})}_{\mathsf{min}}\subseteq\mathfrak{R}^{\prime}\subseteq\mathfrak{R}^{\mathsf{Th}(\mathfrak{M})}_{\mathsf{max}}\\}$

######  Lemma 6.6.

For any $\mathfrak{M}=\langle v,\mathfrak{R}\rangle$ the following equality
holds:

$\SS^{\mathsf{Th}(\mathfrak{M})}=\\{\mathfrak{N}=\langle
v^{\prime},\mathfrak{R}^{\prime}\rangle:\mathsf{Th}(\mathfrak{M})=\mathsf{Th}(\mathfrak{N})\\}$

###### Proof.

Let $\mathfrak{M}=\langle v,\mathfrak{R}\rangle$ be arbitrary. To prove the
left to right inclusion, let $\mathfrak{N}=\langle
v^{\prime},\mathfrak{R}^{\prime}\rangle\in\SS^{\mathsf{Th}(\mathfrak{M})}$.
First, we will show that for any $\varphi\in\mathsf{Th}(\mathfrak{M})$ we have
$\mathfrak{N}\vDash\varphi$. Assume that
$\varphi\in\mathsf{Th}(\mathfrak{M})$. Let $\varphi\in\Phi$. By (6.5) we know
that $v^{\mathsf{Th}(\mathfrak{M})}=v^{\prime}$, hence
$\mathfrak{N}\vDash\varphi$. Let $\varphi=\neg\psi$.
$\neg\psi\in\mathsf{Th}(\mathfrak{M})$ iff
$\psi\notin\mathsf{Th}(\mathfrak{M})$. By inductive hypothesis
$\mathfrak{N}\nvDash\psi$, which means $\mathfrak{N}\vDash\neg\psi$. Let
$\varphi=\psi\lor\chi$. $\psi\lor\chi\in\mathsf{Th}(\mathfrak{M})$ iff
$\psi\in\mathsf{Th}(\mathfrak{M})$ or $\chi\in\mathsf{Th}(\mathfrak{M})$. By
inductive hypothesis $\mathfrak{N}\vDash\psi$ or $\mathfrak{N}\vDash\chi$, so
$\mathfrak{N}\vDash\psi\lor\chi$. The proof for the rest of boolean cases goes
in a similar manner. Assume that $\varphi=\psi\looparrowright\chi$.
$\psi\looparrowright\chi\in\mathsf{Th}(\mathfrak{M})$, so
$\psi\notin\mathsf{Th}(\mathfrak{M})$ or $\chi\in\mathsf{Th}(\mathfrak{M})$,
which by inductive hypothesis gives us $\mathfrak{N}\nvDash\psi$ or
$\mathfrak{N}\vDash\chi$. By (6.5) we know that
$\langle\psi,\chi\rangle\in\mathfrak{R}^{\mathsf{Th}(\mathfrak{M})}_{\mathsf{min}}$
and
$\mathfrak{R}^{\mathsf{Th}(\mathfrak{M})}_{\mathsf{min}}\subseteq\mathfrak{R}^{\prime}$,
which means that $\langle\psi,\chi\rangle\in\mathfrak{R}^{\prime}$. So
$\mathfrak{N}\vDash\psi\looparrowright\chi$. Let
$\varphi=\psi\vartriangle\chi$.
$\psi\vartriangle\chi\in\mathsf{Th}(\mathfrak{M})$ means
$\psi\in\mathsf{Th}(\mathfrak{M})$ and $\chi\in\mathsf{Th}(\mathfrak{M})$. By
inductive hypothesis we obtain $\mathfrak{N}\vDash\psi$ and
$\mathfrak{N}\vDash\chi$. We also know that
$\psi\looparrowright\chi\in\mathsf{Th}(\mathfrak{M})$, since
$\mathfrak{M}\vDash\psi\vartriangle\chi$ implies
$\mathfrak{M}\vDash\psi\looparrowright\chi$. This means that
$\langle\psi,\chi\rangle\in\mathfrak{R}^{\mathsf{Th}(\mathfrak{M})}_{\mathsf{min}}$.
We know that
$\mathfrak{R}^{\mathsf{Th}(\mathfrak{M})}_{\mathsf{min}}\subseteq\mathfrak{R}^{\prime}$,
so $\mathfrak{N}\vDash\psi\vartriangle\chi$. This way, we have shown that
$\mathfrak{N}\vDash\mathsf{Th}(\mathfrak{M})$.

To show the opposite inclusion, assume that $\mathfrak{N}=\langle
v^{\prime},\mathfrak{R}^{\prime}\rangle\notin\SS^{\mathsf{Th}(\mathfrak{M})}$.
Hence at least one of the following must hold 1) $v^{\prime}\neq
v^{\mathsf{Th}(\mathfrak{M})}$ or 2)
$\mathfrak{R}^{\mathsf{Th}(\mathfrak{M})}_{\mathsf{min}}\nsubseteq\mathfrak{R}^{\prime}$
or 3)
$\mathfrak{R}^{\prime}\nsubseteq\mathfrak{R}^{\mathsf{Th}(\mathfrak{M})}_{\mathsf{max}}$.
Let 1) hold. This means that for some $\varphi\in\Phi$ we have
$\mathfrak{N}\vDash\varphi$ and $\varphi\notin\mathsf{Th}(\mathfrak{M})$ or
$\mathfrak{N}\nvDash\varphi$ and $\varphi\in\mathsf{Th}(\mathfrak{M})$. In
both cases we get $\mathsf{Th}(\mathfrak{N})\neq\mathsf{Th}(\mathfrak{M})$.
Suppose 2) is the case. This means that there is
$\langle\varphi,\psi\rangle\in\mathsf{FOR}\times\mathsf{FOR}$ such that
$\varphi\looparrowright\psi\in\mathsf{Th}(\mathfrak{M})$ and
$\langle\varphi,\psi\rangle\notin\mathfrak{R}^{\prime}$. This means that
$\mathfrak{N}\nvDash\varphi\looparrowright\psi$, so
$\mathsf{Th}(\mathfrak{N})\neq\mathsf{Th}(\mathfrak{M})$. Finally assume that
3) holds. This means that there is
$\langle\varphi,\psi\rangle\in\mathfrak{R}^{\prime}$ such that
$\varphi\looparrowright\psi\notin\mathsf{Th}(\mathfrak{M})$ and
$\varphi\to\psi\in\mathsf{Th}(\mathfrak{M})$. Now we have two possibilities:
either $\mathfrak{N}\nvDash\varphi\to\psi$ or
$\mathfrak{N}\vDash\varphi\to\psi$. If the first disjunct is true, then
$\mathsf{Th}(\mathfrak{M})\neq\mathsf{Th}(\mathfrak{N})$ follows immediately.
Thus, assume the second disjunct holds. This way, we obtain
$\mathfrak{N}\vDash\varphi\looparrowright\psi$. But
$\varphi\looparrowright\psi\notin\mathsf{Th}(\mathfrak{M})$, so again
$\mathsf{Th}(\mathfrak{M})\neq\mathsf{Th}(\mathfrak{N})$. ∎

###  6.2 Axiomatic systems for undefinable sets of Epstein structures

Despite the undefinability results stated in facts (6.2) and (6.3), we claim
that it is possible to give an adequate axiomatic systems which generate the
consequence relations of $\mathsf{R}^{n}$, $\mathsf{R}^{s}$ and
$\mathsf{R}^{s}\cap\mathsf{R}^{n}$. To make the notions already introduced in
the preliminary section a little more precise, we shall start from recalling
some textbook definitions of Hilbert-style proof, (maximal) consistency and so
on. By $\mathsf{CPL}$ we mean all classical tautologies in the language of
Epstein logic.

  1. 1.

$\mathsf{CPL}$

  2. 2.

$(p\looparrowright q)\to(p\to q)$

  3. 3.

$(p\looparrowright q)\wedge(p\wedge q)\leftrightarrow(p\vartriangle q)$

again, the rules of the system are Modus Ponens and substitution.
$\mathcal{F}\subseteq\mathsf{FOR}$ is the least set of formulas closed under
MP and substitution. Let $\Lambda\subseteq\mathsf{FOR}$. $\mathcal{F}\Lambda$
is the least set of formulas containing $\mathcal{F}\cup\Lambda$ which is
closed under the two above-mentioned rules.

######  Definition 6.7 ($\mathcal{F}\Lambda$-proof).

Let $\Sigma\subseteq\mathsf{FOR}$, $\varphi\in\mathsf{FOR}$. We will define
the notion of a proof in a standard way for normal Epstein axiomatic systems.
The $\mathcal{F}\Lambda$-proof of a formula $\varphi$ from the set of premises
$\Sigma$ is a sequence $\psi_{1},...,\psi_{n}$, where $\psi_{n}=\varphi$, and
for each $i\in\\{1,...,n\\}$, $\psi_{i}$ fulfils at least one of the
following:

$\displaystyle\psi_{i}\in\mathcal{F}\Lambda\cup\Sigma,or$ (1)
$\displaystyle\text{there are }j,k<i,\text{ such that
}\psi_{j}=\psi_{k}\to\psi_{i}.$ (2)

When there is an $\mathcal{F}\Lambda$-proof of $\varphi$ from $\Sigma$
($\varphi$ is provable from $\Sigma$), we will write
$\Sigma\vdash_{\mathcal{F}\Lambda}\varphi$. Observe that
$\emptyset\vdash_{\mathcal{F}\Lambda}\varphi$ means $\varphi\in\mathcal{F}$.
By theses of $\mathcal{F}\Lambda$ we mean elements of $\mathcal{F}$. We will
shortly write $\vdash_{\mathcal{F}\Lambda}\varphi$ instead
$\emptyset\vdash_{\mathcal{F}\Lambda}\varphi$.

######  Definition 6.8 (Maximal consistent set).

Let $\Gamma$ be a set of formulas. $\Gamma$ is $\mathcal{F}\Lambda$-consistent
iff $\Gamma\nvdash_{\mathcal{F}\Lambda}\bot$; otherwise, it is inconsistent.
$\Gamma$ is $\mathcal{F}\Lambda$-maximally consistent set
($\mathcal{F}\Lambda$-mcs) iff it is $\mathcal{F}\Lambda$-consistent and all
of its proper extensions are inconsistent.

Using the well-known Lindenbaum construction, we can prove the following:

######  Lemma 6.9.

(Lindenbaum’s Lemma)
Any $\mathcal{F}\Lambda$-consistent set of formulas $\Sigma$ can be extended
to $\mathcal{F}$-maximal consistent set ($\mathcal{F}\Lambda$-mcs).

Each maximally consistent set enjoys some standard properties:

######  Proposition 6.10.

The following hold for any $\mathcal{F}\Lambda-mcs$ $\Sigma^{+}$:

$\displaystyle\text{if }\vdash_{\mathcal{F}\Lambda}\varphi$
$\displaystyle\text{ then }\varphi\in\Sigma^{+},$
$\displaystyle\neg\varphi\in\Sigma^{+}$ $\displaystyle\text{ iff
}\varphi\notin\Sigma^{+},$ $\displaystyle\varphi\lor\psi\in\Sigma^{+}$
$\displaystyle\text{ iff }\varphi\in\Sigma^{+}\text{ or }\psi\in\Sigma^{+},$
$\displaystyle\varphi,\psi\in\Sigma^{+}$ $\displaystyle\text{ iff
}\varphi\wedge\psi\in\Sigma^{+},$ $\displaystyle\varphi\to\psi\in\Sigma^{+}$
$\displaystyle\text{ iff }\varphi\notin\Sigma^{+}\text{ or
}\psi\in\Sigma^{+},$ $\displaystyle\varphi\leftrightarrow\psi$
$\displaystyle\text{ iff }\varphi\in\Sigma^{+}\text{ if and only if
}\psi\in\Sigma^{+},$ $\displaystyle\text{if }\varphi\in\Sigma^{+}\text{ and
}\vdash_{\mathcal{F}\Lambda}\varphi\to\psi,$ $\displaystyle\text{ then
}\psi\in\Sigma^{+}.$

Each fact can be easily proven from the construction of $\mathcal{F}\Lambda-
mcs$ and the fact that $\mathcal{F}\Lambda$ is closed under classical logic.

######  Proposition 6.11 (Set of all models for a given mcs).

Let $\mathcal{F}\Lambda$ be Epstein logic and let $\Sigma^{+}$ be
$\mathcal{F}\Lambda-mcs$. The exact set of Epstein models which verify
$\Sigma^{+}$ is $\SS^{\Sigma^{+}}=\\{\langle
v,\mathfrak{R}\rangle:v=v^{\Sigma^{+}},\,\,\mathfrak{R}^{\Sigma^{+}}_{\mathsf{min}}\subseteq\mathfrak{R}\subseteq\mathfrak{R}^{\Sigma^{+}}_{\mathsf{max}}\\}$,
where $v^{\Sigma^{+}}$, $\mathfrak{R}^{\Sigma^{+}}_{\mathsf{min}}$,
$\mathfrak{R}^{\Sigma^{+}}_{\mathsf{max}}$ are defined in an analogous way as
it is done in (6.5).

Using the fact (6.10), the proof can be given in a similar way as in case of
lemma $\eqref{lm: S lemma}$.

Before we move on, we need to recall some results from [13]. Klonowki’s thesis
concerns generalised Epstein logics with even more Epstein-style connectives
than [12]. He studies the language with basic boolean connectives
$\neg,\lor,\wedge,\to,\leftrightarrow$ and Epstein style ones:
$\lor^{\mathcal{E}},\wedge^{\mathcal{E}},\to^{\mathcal{E}},\leftrightarrow^{\mathcal{E}}$
interpreted in the standard Epstein way: $\langle
v,\mathfrak{R}\rangle\vDash\varphi\ast^{\mathcal{E}}\psi$ iff $\langle
v,\mathfrak{R}\rangle\vDash\varphi\ast\psi$ and
$\langle\varphi,\psi\rangle\in\mathfrak{R}$. As Klonowski observes, a language
this rich is capable of expressing Epstein relation in the sense that:
$\langle\varphi,\psi\rangle\in\mathfrak{R}$ iff
$\mathfrak{R}\vDash(\varphi\to^{\mathcal{E}}\psi)\lor(\varphi\lor^{\mathcal{E}}\psi)$.
Define
$\varphi\mathcal{R}\psi:=(\varphi\to^{\mathcal{E}}\psi)\lor(\varphi\lor^{\mathcal{E}}\psi)$
[13]. This way, axiomatization becomes trivial: basic system is $\mathsf{CPL}$
with axioms of the form $(p\ast^{\mathcal{E}}q)\leftrightarrow(p\ast
q)\wedge(p\mathcal{R}q)$, for each
$\ast\in\\{\lor,\wedge,\to,\leftrightarrow\\}$. Obviously Modus Ponens and
substitution are added as only rules. The cases under consideration are
equally trivial: for symmetric relations, we add $p\mathcal{R}q\to
q\mathcal{R}p$. The reader sees immediately how it goes for the other cases –
it is a matter of rewriting the condition. Thus we claim that weaker Epstein-
type languages are more interesting: precisely the interesting ones are those
which are not capable of expressing the relation – just like the one we are
currently investigating.

To make things precise, we show that $\mathsf{FOR}$ is indeed incapable of
expressing the relation. Say that $\mathsf{FOR}$ expresses Epstein relations
iff for any $\mathfrak{R}\subseteq\mathsf{FOR}^{2}$, any
$\varphi,\psi\in\mathsf{FOR}$, there is $\chi\in\mathsf{FOR}$, s.t.
$\langle\varphi,\psi\rangle\in\mathfrak{R}$ iff $\mathfrak{R}\vDash\chi$.

Now we can prove the:

######  Proposition 6.12 ($\mathfrak{R}$ inexpressibility).

$\mathsf{FOR}$ does not express Epstein relations.

###### Proof.

Let $\mathfrak{R}_{0}=\\{\langle\top,\bot\rangle\\}$. Assume that there is
$\chi\in\mathsf{FOR}$ such that for any
$\mathfrak{R}\subseteq\mathsf{FOR}^{2}$, $\mathfrak{R}\vDash\chi$ iff
$\langle\top,\bot\rangle\in\mathfrak{R}$. Let $v$ be a valuation. By
assumption, $\mathfrak{R}_{0}\vDash\chi$, so also $\langle
v,\mathfrak{R}_{0}\rangle\vDash\chi$. It is immediate to observe that $\langle
v,\emptyset\rangle\in\SS^{\langle v,\mathfrak{R}_{0}\rangle}$. Thus $\langle
v,\emptyset\rangle\vDash\chi$. But $v$ is arbitrary, so $\emptyset\vDash\chi$
which means that $\langle\top,\bot\rangle\in\emptyset$ – contradiction. ∎

To conclude our digression, we claim that in the face of the undefinability of
our two properties and inexpressibility of the Epstein relation in our
language, the task of providing adequate axiomatization for chosen sets of
relations becomes a non-trivial endeavour.

###  6.3 Logic of symmetric relations $\mathcal{F}S$

In order to obtain the logical system $\mathcal{F}S$, we simply enrich
$\mathcal{F}$ with additional axiom:

$(s)\,\,(p\looparrowright q)\to((q\looparrowright p)\lor\neg(q\to p))$

######  Theorem 6.13.

The logic $\mathcal{F}S$ is sound with respect to the set of symmetric Epstein
relations $\mathfrak{R}^{s}$.

###### Proof.

To prove soundness, let $\mathfrak{R}\in\mathsf{R}^{s}$. Let $v$ be arbitrary
valuation and let $\mathfrak{M}=\langle v,\mathfrak{R}\rangle$. Assume
$\mathfrak{M}\vDash\varphi\looparrowright\psi$. Hence
$\varphi\mathfrak{R}\psi$. We know that $\mathfrak{R}$ is symmetric so also
$\psi\mathfrak{R}\varphi$. Assume now that $\mathfrak{M}\vDash\psi\to\varphi$.
This means that $\mathfrak{M}\vDash\psi\looparrowright\varphi$. ∎

######  Theorem 6.14.

If $\Sigma\vDash_{\mathsf{R}^{s}}\varphi$, then
$\Sigma\vdash_{\mathcal{F}S}\varphi$.

###### Proof.

Assume $\Sigma\nvdash_{\mathcal{F}S}\varphi$. Hence
$\Sigma\cup\\{\neg\varphi\\}$ is $\mathcal{F}S$-consistent. Let $\Sigma^{+}$
be the $\mathcal{F}S$-mcs extension of $\Sigma\cup\\{\neg\varphi\\}$. Let
$\mathfrak{M}=\langle v^{\Sigma^{+}},\mathfrak{R}\rangle$,
$\mathfrak{R}=\mathfrak{R}^{\Sigma^{+}}_{\mathsf{min}}\cup S$ where
$S=\\{\langle\psi,\varphi\rangle:\varphi\looparrowright\psi\in\Sigma^{+}\\}$.
To finish the proof, we have to show that 1) $\mathfrak{R}$ is symmetric and
2) that $\mathfrak{M}$ is the model for $\Sigma^{+}$ i.e.
$\mathfrak{M}\vDash\Sigma^{+}$. For 1) assume that $\varphi\mathfrak{R}\psi$.
Hence $\langle\varphi,\psi\rangle\in\mathfrak{R}^{\Sigma^{+}}_{\mathsf{min}}$
or $\langle\varphi,\psi\rangle\in S$. If the first disjunct is true, then
$\varphi\looparrowright\psi\in\Sigma^{+}$ meaning that
$\langle\psi,\varphi\rangle\in S$ and so $\psi\mathfrak{R}\varphi$. If it is
the case that $\langle\varphi,\psi\rangle\in S$, then
$\psi\looparrowright\varphi\in\Sigma^{+}$. This means
$\langle\psi,\varphi\rangle\in\mathfrak{R}^{\Sigma^{+}}_{\mathsf{min}}$.
Notice that in order to prove 2), by fact (6.11), it is enough to show that
$\mathfrak{R}\subseteq\mathfrak{R}^{\Sigma^{+}}_{\mathsf{max}}$. Assume, then,
that $\langle\varphi,\psi\rangle\in\mathfrak{R}$. This means that either 1)
$\langle\varphi,\psi\rangle\in\mathfrak{R}^{\Sigma^{+}}_{\mathsf{min}}$ or 2)
$\langle\varphi,\psi\rangle\in S$. If 1) is the case, then
$\varphi\looparrowright\psi\in\Sigma^{+}$, hence also
$\langle\varphi,\psi\rangle\in\mathfrak{R}^{\Sigma^{+}}_{\mathsf{max}}$. If 2)
is the case, then $\psi\looparrowright\varphi\in\Sigma^{+}$. But also by axiom
$(s)$ and properties of $\Sigma^{+}$,
$\varphi\looparrowright\psi\in\Sigma^{+}$ or $\varphi\to\psi\notin\Sigma^{+}$.
This means that
$\langle\varphi,\psi\rangle\in\mathfrak{R}^{\Sigma^{+}}_{\mathsf{max}}$. This
way, we have shown that
$\mathfrak{R}\subseteq\mathfrak{R}^{\Sigma^{+}}_{\mathsf{max}}$. We conclude
that $\mathfrak{M}\vDash\Sigma^{+}$. ∎

###  6.4 Logic of $\mathsf{R}^{n}$, the system $\mathcal{F}N$

In order to obtain the logical system $\mathcal{F}N$, we add the following two
axioms to the system $\mathcal{F}$ ($N:=\\{n1,\,\,n2\\}$):

$(n1)\,\,(\neg p\looparrowright q)\to((p\looparrowright q)\lor\neg(p\to q))$
$(n2)\,\,((\neg\neg p\looparrowright q)\wedge\neg(\neg p\to
q))\to(p\looparrowright q)$

######  Theorem 6.15 (Soundness of $\mathcal{F}N$).

The logic $\mathcal{F}N$ is sound with respect to $\mathsf{R}^{n}$ – the set
of relations fulfilling the (n) condition.

###### Proof.

Let $\mathfrak{R}\in\mathsf{R}^{n}$. Let $v$ be arbitrary valuation and
$\varphi,\psi$ be arbitrary formulas. Let $\mathfrak{M}=\langle
v,\mathfrak{R}\rangle$. In order to prove validity of $(n1)$ assume that
$\mathfrak{M}\vDash\neg\varphi\looparrowright\psi$. This means that
$\neg\varphi\mathfrak{R}\psi$. So also $\varphi\mathfrak{R}\psi$. Assume
further that $\mathfrak{M}\vDash\varphi\to\psi$. This means
$\mathfrak{M}\vDash\varphi\looparrowright\psi$. For $(n2)$ assume that
$\mathfrak{M}\vDash(\neg\neg\varphi\looparrowright\psi)\wedge\neg(\neg\varphi\to\psi)$.
This means that $\neg\neg\varphi\mathfrak{R}\psi$,
$\neg\varphi\mathfrak{R}\psi$ and also $\varphi\mathfrak{R}\psi$. Since
$\mathfrak{M}\vDash\neg(\neg\varphi\to\psi)$, we know that
$\mathfrak{M}\nvDash\varphi$ and $\mathfrak{M}\nvDash\psi$, which means that
$\mathfrak{M}\vDash\varphi\to\psi$. We conclude that
$\mathfrak{M}\vDash\varphi\looparrowright\psi$. ∎

######  Theorem 6.16 (Strong completeness).

The logic $\mathcal{F}N$ is strongly complete with respect to $\mathsf{R}^{n}$
i.e. $\Sigma\vDash_{\mathsf{R}^{n}}\varphi$ implies
$\Sigma\vdash_{\mathcal{F}N}\varphi$ for any
$\Sigma\cup\\{\varphi\\}\subseteq\mathsf{FOR}$.

###### Proof.

Let $\Sigma\subseteq\mathsf{FOR}$ and $\varphi\in\mathsf{FOR}$. Assume that
$\Sigma\nvdash_{\mathcal{F}N}\varphi$. This means that
$\Sigma\cup\\{\neg\varphi\\}$ is $\mathcal{F}N$-consistent set. Hence it can
be extended to maximally $\mathcal{F}N$-consistent set. Let $\Sigma^{+}$ be
such set. Let $\mathfrak{M}=\langle v^{\Sigma^{+}},\mathfrak{R}\rangle$ be
such that $\mathfrak{R}=\mathfrak{R}^{\Sigma^{+}}_{\mathsf{min}}\cup N$, where
$N=\\{\langle\varphi,\psi\rangle:\neg\varphi\looparrowright\psi\in\Sigma^{+}\\}$.
To show that $\mathfrak{M}\vDash\Sigma^{+}$ we have to show that
$\mathfrak{R}\subseteq\mathfrak{R}^{\Sigma^{+}}_{\mathsf{max}}$. Assume that
$\langle\varphi,\psi\rangle\in\mathfrak{R}$. If
$\langle\varphi,\psi\rangle\in\mathfrak{R}^{\Sigma^{+}}_{\mathsf{min}}$, then
obviously
$\langle\varphi,\psi\rangle\in\mathfrak{R}^{\Sigma^{+}}_{\mathsf{max}}$.
Assume that $\langle\varphi,\psi\rangle\in N$. This means that
$\neg\varphi\looparrowright\psi\in\Sigma^{+}$. By $(n1)$ and maximality of
$\Sigma^{+}$, we obtain $\varphi\looparrowright\psi\in\Sigma^{+}$ or
$\varphi\to\psi\notin\Sigma^{+}$. Hence by definition (6.5) we know that
$\langle\varphi,\psi\rangle\in\mathfrak{R}^{\Sigma^{+}}_{\mathsf{max}}$. This
way, we have proven
$\mathfrak{R}\subseteq\mathfrak{R}^{\Sigma^{+}}_{\mathsf{max}}$, which means
that $\mathfrak{M}\vDash\Sigma^{+}$. Now, we have to show that
$\mathfrak{R}\in\mathfrak{R}^{n}$ which means that
$\neg\varphi\mathfrak{R}\psi$ implies $\varphi\mathfrak{R}\psi$. Assume that
$\neg\varphi\mathfrak{R}\psi$. Hence
$\langle\neg\varphi,\psi\rangle\in\mathfrak{R}^{\Sigma^{+}}_{\mathsf{min}}$ or
$\langle\neg\varphi,\psi\rangle\in N$. In the first case
$\neg\varphi\looparrowright\psi\in\Sigma^{+}$. So
$\langle\varphi,\psi\rangle\in N$, which means that $\varphi\mathfrak{R}\psi$.
If the second disjunct is true, then $\neg\neg\varphi\to\psi\in\Sigma^{+}$.
Either $\neg\varphi\looparrowright\psi\in\Sigma^{+}$, or
$\neg\varphi\looparrowright\psi\notin\Sigma^{+}$. If the first disjunct is
true, then $\langle\varphi,\psi\rangle\in N$ which finishes the proof. Assume
then, that $\neg\varphi\looparrowright\psi\notin\Sigma^{+}$. By axiom $(n1)$,
maximality and Modus Ponens we obtain
$\neg\varphi\looparrowright\psi\in\Sigma^{+}$ or
$\neg(\neg\varphi\to\psi)\in\Sigma^{+}$. Hence
$\neg(\neg\varphi\to\psi)\in\Sigma^{+}$. By $(n2)$ we obtain
$\varphi\looparrowright\psi\in\Sigma^{+}$. This means that
$\langle\varphi,\psi\rangle\in\mathfrak{R}^{\Sigma^{+}}_{\mathsf{min}}$, so
$\varphi\mathfrak{R}\psi$. ∎

###  6.5 The $\mathcal{F}SN$ system – the logic of $\mathsf{R}^{sn}$

By the set of relations $\mathsf{R}^{sn}$, we mean the
$\mathsf{R}^{s}\cap\mathsf{R}^{n}$.

In order to obtain the logic $\mathcal{F}SN$ we combine the axioms of
$\mathcal{F}S$ together with those of $\mathcal{F}N$ and add the following two
schemas:

$(sn)\,\,(\neg(p\to q)\wedge(\neg p\looparrowright q))\to(q\looparrowright p)$
$(ns)\,\,(\neg(\neg p\to q)\wedge(q\looparrowright\neg p))\to(p\looparrowright
q)$

######  Theorem 6.17 (Soundness of $\mathcal{F}SN$).

$\mathcal{F}SN$ is sound with respect to $\mathsf{R}^{sn}$.

###### Proof.

Let $\mathfrak{R}\subseteq\mathsf{R}^{sn}$, let $v$ be arbitrary valuation and
let $\mathfrak{M}=\langle v,\mathfrak{R}\rangle$. Assume that
$\mathfrak{M}\vDash\neg(\varphi\to\psi)\wedge(\neg\varphi\looparrowright\psi)$.
Hence $\mathfrak{M}\vDash\varphi$ and $\mathfrak{M}\nvDash\psi$, which implies
$\mathfrak{M}\nvDash\psi$ or $\mathfrak{M}\vDash\varphi$. We also know that
$\neg\varphi\mathfrak{R}\psi$. Since $\mathfrak{R}\in\mathfrak{R}^{n}$, we
know that $\varphi\mathfrak{R}\psi$. Also $\psi\mathfrak{R}\varphi$ since
$\mathfrak{R}\in\mathfrak{R}^{s}$. This way, we obtain
$\mathfrak{M}\vDash\psi\looparrowright\varphi$. For $(ns)$ assume
$\mathfrak{M}\vDash\neg(\neg\varphi\to\psi)\wedge(\psi\looparrowright\neg\varphi)$.
This way, we get $\mathfrak{M}\nvDash\varphi$ or $\mathfrak{M}\vDash\psi$ and
$\psi\mathfrak{R}\neg\varphi$. Hence $\neg\varphi\mathfrak{R}\psi$ by symmetry
and $\varphi\mathfrak{R}\psi$ by the (n) condition. We conclude that
$\mathfrak{M}\vdash\varphi\looparrowright\psi$. ∎

######  Theorem 6.18 (Strong completeness of $\mathcal{F}SN$).

$\Sigma\vDash_{\mathsf{R}^{sn}}\varphi$ implies
$\Sigma\vdash_{\mathcal{F}SN}\varphi$, for any $\Sigma\subseteq\mathsf{FOR}$,
any $\varphi\in\mathsf{FOR}$.

###### Proof.

Let $\Sigma\cup\\{\varphi\\}\subseteq\mathsf{FOR}$. Assume that
$\Sigma\nvdash_{\mathcal{F}SN}\varphi$. This means
$\Sigma\cup\\{\neg\varphi\\}$ is $\mathcal{F}SN$-consistent. Let $\Sigma^{+}$
be its maximally $\mathcal{F}SN$-consistent extension. Let
$\mathfrak{M}=\langle v^{\Sigma^{+}},\mathfrak{R}\rangle$,
$\mathfrak{R}=\mathfrak{R}^{\Sigma^{+}}_{\mathsf{min}}\cup S\cup N$, where $S$
and $N$ are as above. We have already shown that
$S,N\subseteq\mathfrak{R}^{\Sigma^{+}}_{\mathsf{max}}$ so the only thing left
is to prove that $\mathfrak{R}\in\mathsf{R}^{sn}$. First to show that
$\mathfrak{R}$ is symmetric assume that $\varphi\mathfrak{R}\psi$. If
$\langle\varphi,\psi\rangle\in\mathfrak{R}^{\Sigma^{+}}_{\mathsf{min}}$, then
$\langle\psi,\varphi\rangle\in S$. If $\langle\varphi,\psi\rangle\in S$, then
$\langle\psi,\varphi\rangle\in\mathfrak{R}^{\Sigma^{+}}_{\mathsf{min}}$.
Assume then that $\langle\varphi,\psi\rangle\in N$. Hence
$\neg\varphi\looparrowright\psi\in\Sigma^{+}$. By axiom $(n1)$, this means
that $\varphi\looparrowright\psi\in\Sigma^{+}$ or
$\varphi\to\psi\notin\Sigma^{+}$. If
$\varphi\looparrowright\psi\in\Sigma^{+}$, then $\langle\psi,\varphi\rangle\in
S$. Let us then consider the case where $\varphi\to\psi\notin\Sigma^{+}$. By
axiom $(sn)$ we get $\psi\looparrowright\varphi\in\Sigma^{+}$ which means that
$\langle\psi,\varphi\rangle\in\mathfrak{R}^{\Sigma^{+}}_{\mathsf{min}}$.

To show that $\neg\varphi\mathfrak{R}\psi$ implies $\varphi\mathfrak{R}\psi$
assume that $\neg\varphi\mathfrak{R}\psi$. If
$\langle\neg\varphi,\psi\rangle\in\mathfrak{R}^{\Sigma^{+}}_{\mathsf{min}}$,
then $\langle\varphi,\psi\rangle\in N$ by axiom $(n1)$. If
$\langle\neg\varphi,\psi\rangle\in N$, then
$\langle\varphi,\psi\rangle\in\mathfrak{R}^{\Sigma^{+}}_{\mathsf{min}}\cup N$
by previous result for $\mathcal{F}N$. Assume that
$\langle\neg\varphi,\psi\rangle\in S$. This means that
$\psi\looparrowright\neg\varphi\in\Sigma^{+}$. Either
$\neg\varphi\looparrowright\psi\in\Sigma^{+}$, or
$\neg\varphi\to\psi\notin\Sigma^{+}$ by axiom $(s)$. If the former is the
case, then $\langle\varphi,\psi\rangle\in N$. Hence assume the latter. By
axiom $(ns)$ we obtain $\varphi\looparrowright\psi\in\Sigma^{+}$, which means
that $\langle\varphi,\psi\rangle\in\mathfrak{R}^{\Sigma^{+}}_{\mathsf{min}}$.
∎

##  7 Interpolation

We close our study of Epstein semantics with the proof of the interpolation
theorem for $\mathcal{F}$. We will use the methods close to the ones that can
be found in [3, 5]. Let us start with a formulation of the theorem.

######  Theorem 7.1 (Interpolation).

If $\varphi\to\psi\in\mathcal{F}$ then there is $\chi$ such that
$\mathsf{Var}(\chi)\subseteq\mathsf{Var}(\varphi)\cap\mathsf{Var}(\psi)$ and
$\varphi\to\chi\in\mathcal{F}$, $\chi\to\psi\in\mathcal{F}$.

We shall refer to formulas like $\chi$ in the above formulated interpolation
theorem as interpolants (of $\varphi$ and $\psi$). Before moving directly to
the proof, we shall first introduce some useful definitions.

######  Definition 7.2 (Realisable pairs).

Let $\Gamma,\Sigma\subseteq\mathsf{FOR}$. The pair
$\langle\Gamma,\Sigma\rangle$ will be called realisable iff there is
$\mathfrak{M}\in\mathsf{M}$ such that $\mathfrak{M}\vDash\varphi$ for any
$\varphi\in\Gamma$ and $\mathfrak{M}\nvDash\psi$ for any $\psi\in\Sigma$.

It is easy to observe that by 7.2, $\varphi\to\psi\notin\mathcal{F}$ is
equivalent to $\langle\\{\varphi\\},\\{\psi\\}\rangle$ being realisable. We
shall also introduce the notion of a separable pair.

######  Definition 7.3 (Separable pairs).

We say that a pair $\langle\Gamma,\Sigma\rangle$ is separable iff there is
$\chi$ such that
$\mathsf{Var}(\chi)\subseteq\mathsf{Var}(\Gamma)\cap\mathsf{Var}(\Sigma)$ and
both $\langle\Gamma,\\{\chi\\}\rangle$ and $\langle\\{\chi\\},\Sigma\rangle$
are not realisable. In such cases, we say that $\\{\chi\\}$ separates
$\langle\Gamma,\Sigma\rangle$.

Now we can start the proof of theorem 7.1.

###### Proof.

Assume that $\varphi\to\psi$ does not have an interpolant. We will prove that
the pair
$t_{0}=\langle\Gamma_{0},\Sigma_{0}\rangle=\langle\\{\varphi\\},\\{\psi\\}\rangle$
is realisable. By our assumption, we know that $t_{0}$ is not separable. We
shall construct a finite sequence of pairs starting from $t_{0}$. First let
$\varphi_{1},...,\varphi_{j}$ and $\psi_{1},...,\psi_{k}$ be an enumeration of
all $\varphi$’s proper subformulas and all $\psi$’s proper subformulas
respectively. Let $i<j$. We shall construct the first part of our sequence in
the following way:

$\displaystyle t_{i+1}$
$\displaystyle=\begin{cases}\langle\Gamma_{i}\cup\\{\varphi_{i+1}\\},\Sigma_{0}\rangle,&\text{if
}\langle\Gamma_{i}\cup\\{\varphi_{i+1}\\},\Sigma_{0}\rangle\text{ is not
separable};\\\
\langle\Gamma_{i}\cup\\{\neg\varphi_{i+1}\\},\Sigma_{0}\rangle,&\text{if
}\langle\Gamma_{i}\cup\\{\varphi_{i+1}\\},\Sigma_{0}\rangle\text{ is
separable}\end{cases}$

First observe that each $t_{i}$, $i\leq j$ is not separable. We already
mentioned that $t_{0}$ is not separable (otherwise it would have an
interpolant). Assume that $t_{i+1}$ is separable. Then by the construction,
both $\langle\Gamma_{i}\cup\\{\varphi_{i+1}\\},\Sigma_{0}\rangle$ and
$\langle\Gamma_{i}\cup\\{\neg\varphi_{i+1}\\},\Sigma_{0}\rangle$ are
separable. This means that there are $\chi_{1},\chi_{2}$, such that
$\mathsf{Var}(\chi_{1})\subseteq\mathsf{Var}(\Gamma\cup\\{\varphi_{i+1}\\})\cap\mathsf{Var}(\Sigma_{0})$,
$\mathsf{Var}(\chi_{2})\subseteq\mathsf{Var}(\Gamma\cup\\{\neg\varphi_{i+1}\\})\cap\mathsf{Var}(\Sigma_{0})$
and all the pairs:
$\langle\Gamma_{i}\cup\\{\varphi_{i+1}\\},\\{\chi_{1}\\}\rangle$,
$\langle\\{\chi_{1}\\},\Sigma_{0}\rangle$,
$\langle\Gamma_{i}\cup\\{\neg\varphi_{i+1}\\},\\{\chi_{2}\\}\rangle$ and
$\langle\\{\chi_{2}\\},\Sigma_{0}\rangle$ are not realisable. Note that for
any $i\leq j$, $\mathsf{Var}(\Gamma_{i})=\mathsf{Var}(\Gamma_{0})$, since at
each step of the construction we add only $\varphi$’s subformulas. For this
reason,
$\mathsf{Var}(\chi_{1}\lor\chi_{2})\subseteq\mathsf{Var}(\Gamma_{i})\cap\mathsf{Var}(\Sigma_{0})$.
Both $\langle\Gamma_{i},\\{\chi_{1}\lor\chi_{2}\\}\rangle$ and
$\langle\\{\chi_{1}\lor\chi_{2}\\},\Sigma_{0}\rangle$ are not realisable,
because otherwise we obtain contradiction with the assumption that $t_{i+1}$
is separable. Hence $t_{i}$ is separable, which proves the first observation
by contraposition.

Now we move on to the second part of our sequence where $m<k$:

$\displaystyle t_{j+m+1}$
$\displaystyle=\begin{cases}\langle\Gamma_{j},\Sigma_{m}\cup\\{\psi_{m}\\}\rangle,&\text{if
}\langle\Gamma_{j},\Sigma_{m}\cup\\{\psi_{m}\\}\rangle\text{ is not
separable};\\\
\langle\Gamma_{j},\Sigma_{m}\cup\\{\neg\psi_{m}\\}\rangle,&\text{if
}\langle\Gamma_{j},\Sigma_{m}\cup\\{\psi_{m}\\}\rangle\text{ is
separable}\end{cases}$

Analogously, we will prove that for any $m\leq k$, $t_{j+m}$ is not separable.
Let $t_{j+m+1}$ be separable. Hence there are $\chi_{1},\chi_{2}$, such that
$\mathsf{Var}(\chi_{1})\subseteq\mathsf{Var}(\Gamma_{j})\cap\mathsf{Var}(\Sigma_{m}\cup\\{\psi_{m+1}\\})$,
$\mathsf{Var}(\chi_{2})\subseteq\mathsf{Var}(\Gamma_{j}\\})\cap\mathsf{Var}(\Sigma_{m}\cup\\{\neg\psi_{m+1}\\})$
and all the pairs: $\langle\Gamma_{j},\\{\chi_{1}\\}\rangle$,
$\langle\\{\chi_{1}\\},\Sigma_{m}\cup\\{\psi_{m+1}\\}\rangle$,
$\langle\Gamma_{j},\\{\chi_{2}\\}\rangle$ and
$\langle\\{\chi_{2}\\},\Sigma_{m}\cup\\{\neg\psi_{m+1}\\}\rangle$ are not
realisable. In this case $\\{\chi_{1}\wedge\chi_{2}\\}$ separates
$\langle\Gamma_{j},\Sigma_{m}\rangle$ which gives us the desired result.

Now, we are going to prove that $t_{j+k}=\langle\Gamma_{j},\Sigma_{k}\rangle$
is realisable. We will define the model $\mathfrak{M}=\langle
v,\mathfrak{R}\rangle$ in the following way:

$\displaystyle v(p)=1\text{ iff }$ $\displaystyle p\in\Gamma_{j}\text{ or
}\neg p\in\Sigma_{k}$
$\displaystyle\langle\varphi,\psi\rangle\in\mathfrak{R}\text{ iff }$ at least
one of the followin is true: $\displaystyle\text{either
}\varphi\looparrowright\psi\in\Gamma_{j},$ (a) $\displaystyle\text{or
}\varphi\vartriangle\psi\in\Gamma_{j},$ (b) $\displaystyle\text{or
}\neg(\varphi\looparrowright\psi)\in\Sigma_{k},$ (c) $\displaystyle\text{or
}\neg(\varphi\vartriangle\psi)\in\Sigma_{k},$ (d)

We will prove that:

  1. 1.

for any $\chi\in\Gamma_{j}$, $\mathfrak{M}\vDash\chi$ iff $\chi\in\Gamma_{j}$,

  2. 2.

for any $\sigma\in\Sigma_{k}$, $\mathfrak{M}\nvDash\sigma$ iff
$\sigma\in\Sigma_{k}$

We shall start with 1. Assume that $\chi=p\in\mathsf{Var}$. If
$p\in\Gamma_{j}$, then by definition $\mathfrak{M}\vDash p$. Let
$\mathfrak{M}\vDash p$. $p\in\Gamma_{j}$ gives us the result immediately, so
assume $\neg p\in\Sigma_{k}$. By our construction either $p\in\Gamma_{j}$ or
$\neg p\in\Gamma_{j}$. If $\neg p\in\Gamma_{j}$, then $\\{\neg p\\}$ separates
$\langle\Gamma_{j},\Sigma_{k}\rangle$ which gives us contradiction, hence
$p\in\Gamma_{j}$. Let $\chi=\gamma\wedge\delta$. Assume that
$\gamma\wedge\delta\in\Gamma_{j}$. Hence $\gamma\in\Gamma_{j}$ or
$\neg\gamma\in\Gamma_{j}$ and similarly $\delta\in\Gamma_{j}$ or
$\neg\delta\in\Gamma_{j}$. If $\neg\gamma\in\Gamma_{j}$, then it is easy to
see that $\\{\bot\\}$ separates $\langle\Gamma_{j},\Sigma_{k}\rangle$, which
leads to contradiction. The case when $\neg\delta\in\Sigma_{k}$ is analogous.
Hence both $\gamma\in\Gamma_{j}$ and $\delta\in\Gamma_{j}$, so by inductive
hypothesis $\mathfrak{M}\vDash\gamma$ and $\mathfrak{M}\vDash\delta$, which
means $\mathfrak{M}\vDash\gamma\wedge\delta$. Assume now that
$\mathfrak{M}\vDash\gamma\wedge\delta$. Obviously $\mathfrak{M}\vDash\gamma$
and $\mathfrak{M}\vDash\delta$, so by inductive hypothesis
$\gamma\in\Gamma_{j}$, $\delta\in\Gamma_{j}$. If
$\neg(\gamma\wedge\delta)\in\Gamma_{j}$, then it is easy to see that
$\\{\bot\\}$ separates $\langle\Gamma_{j},\Sigma_{k}\rangle$, so
$\gamma\wedge\delta\in\Gamma_{j}$. The rest of the boolean cases are treated
similarly, so we move on to Epstein connectives. Let
$\chi=\gamma\looparrowright\delta$. If
$\mathfrak{M}\vDash\gamma\looparrowright\delta$, then
$\langle\gamma,\delta\rangle\in\mathfrak{R}$ which means that one of the four
cases from the definition is true. The first case a immediately leads to the
desired result. Assume b. Assume for reductio that
$\gamma\looparrowright\delta\notin\Gamma_{j}$, which means
$\neg(\gamma\looparrowright\delta)\in\Gamma_{j}$. Then $\\{\bot\\}$ separates
$\langle\Gamma_{j},\Sigma_{k}\rangle$, because there is no
$\mathfrak{M}^{\prime}\in\mathsf{M}$, such that
$\mathfrak{M}^{\prime}\vDash\gamma\vartriangle\delta$ and
$\mathfrak{M}^{\prime}\vDash\neg(\gamma\looparrowright\delta)$. Contradiction,
so it must be the case that $\gamma\looparrowright\delta\in\Gamma_{j}$.
Similarly, assume c and $\neg(\gamma\looparrowright\delta)\in\Gamma_{j}$. then
it can easily be seen that $\\{\neg(\gamma\looparrowright\delta)\\}$ separates
$\langle\Gamma_{j},\Sigma_{k}\rangle$, so
$\gamma\looparrowright\delta\in\Gamma_{j}$. Assume d holds and
$\neg(\gamma\looparrowright\delta)\in\Gamma_{j}$. Then it can be easily
observed that $\\{\neg(\gamma\looparrowright\delta)\\}$, as well as
$\\{\neg(\gamma\vartriangle\delta)\\}$ separates
$\langle\Gamma_{j},\Sigma_{k}\rangle$, so
$\gamma\looparrowright\delta\in\Gamma_{j}$.

For the other direction assume $\gamma\looparrowright\delta\in\Gamma_{j}$.
Hence we already know that $\langle\gamma,\delta\rangle\in\Gamma_{j}$. If both
$\gamma\in\Gamma_{j}$ and $\delta\notin\Gamma_{j}$, then it is easy to see
that $\\{\bot\\}$ separates $\langle\Gamma_{j},\Sigma_{k}\rangle$. For this
reason it is the case that $\gamma\notin\Gamma_{j}$ or $\delta\in\Gamma_{j}$.
By inductive hypothesis, we get $\mathfrak{M}\vDash\gamma$ and
$\mathfrak{M}\vDash\delta$. This immediately leads to
$\mathfrak{M}\vDash\gamma\looparrowright\delta$.

Assume now that $\chi=\gamma\vartriangle\delta$. If
$\mathfrak{M}\vDash\gamma\vartriangle\delta$, then
$\langle\gamma,\delta\rangle\in\mathfrak{R}$, so again we have four cases to
consider. We can say already that b gives us the result immediately. Also we
have $\mathfrak{M}\vDash\gamma$ and $\mathfrak{M}\vDash\delta$. By hypothesis:
$\gamma\in\Gamma_{j}$ and $\delta\in\Gamma_{j}$. Assume a. If
$\gamma\vartriangle\delta\notin\Gamma_{j}$, then we obtain the contradiction,
since $\\{\bot\\}$ separates $\langle\Gamma_{j},\Sigma_{k}\rangle$. Now assume
c or d. If $\gamma\vartriangle\delta\notin\Gamma_{j}$, then in both cases
$\\{\neg(\gamma\vartriangle\delta)\\}$ separates
$\langle\Gamma_{j},\Sigma_{k}\rangle$, so we obtain
$\gamma\vartriangle\delta\in\Gamma_{j}$. For the other direction assume
$\gamma\vartriangle\delta\in\Gamma_{j}$. Hence
$\langle\gamma,\delta\rangle\in\mathfrak{R}$. It is also easy to observe that
it must be the case that $\gamma\in\Gamma_{j}$ and $\delta\in\Gamma_{j}$
(otherwise we get the separation by $\\{\bot\\}$), so by inductive hypothesis
we get $\mathfrak{M}\vDash\gamma\vartriangle\delta$.

For 2. assume that $\mathfrak{M}\nvDash p$. Hence by definition of
$\mathfrak{M}$, we have $\neg p\notin\Sigma_{k}$, which means
$p\in\Sigma_{k}$. Assume $p\in\Sigma_{k}$. If $p\in\Gamma_{j}$, then $\\{p\\}$
separates $\langle\Gamma_{j},\Sigma_{k}\rangle$, so $p\notin\Gamma_{j}$. Also
$\neg p\notin\Sigma_{k}$, so $\mathfrak{M}\nvDash p$. We shall skip the
boolean cases and move to Epstein connectives right away. Let
$\chi=\gamma\looparrowright\delta$. Assume that
$\mathfrak{M}\nvDash\gamma\looparrowright\delta$. Hence we have two
possibilities: either i)$\langle\gamma,\delta\rangle\notin\mathfrak{R}$ or
ii)$\mathfrak{M}\vDash\gamma$ and $\mathfrak{M}\nvDash\delta$. By i) we get
that neither of the conditions a–d holds, so c gives us
$\neg(\gamma\looparrowright\delta)\notin\Sigma_{k}$ which means
$\gamma\looparrowright\delta\in\Sigma_{k}$. Assume ii) holds. Hence by
inductive hypothesis $\neg\gamma\in\Sigma_{k}$ and $\delta\in\Sigma_{k}$. If
$\gamma\looparrowright\delta\notin\Sigma_{k}$, then
$\neg(\gamma\looparrowright\delta)\in\Sigma_{k}$. But in such case it is easy
to see that $\\{\neg\bot\\}$ separates $\langle\Gamma_{j},\Sigma_{k}\rangle$,
because there is no $\mathfrak{M}^{\prime}$ such that
$\mathfrak{M}^{\prime}\vDash\gamma\looparrowright\delta$ and
$\mathfrak{M}^{\prime}\vDash\gamma$, $\mathfrak{M}^{\prime}\nvDash\delta$. For
this reason we obtain $\gamma\looparrowright\delta\in\Sigma_{k}$.

For the other direction assume $\gamma\looparrowright\delta\in\Sigma_{k}$.
Assume now that a holds. Then obviously $\\{\gamma\looparrowright\delta\\}$
separates $\langle\Gamma_{j},\Sigma_{k}\rangle$. So a does not hold. For
similar reasons, it must be the case that b does not hold. It is obvious that
c cannot be true. If d holds, then it also must be the case that
$\\{\neg\bot\\}$ separates $\langle\Gamma_{j},\Sigma_{k}\rangle$, since there
is no $\mathfrak{M}^{\prime}\in\mathsf{M}$ such that
$\mathfrak{M}^{\prime}\vDash\gamma\vartriangle\delta$ and
$\mathfrak{M}^{\prime}\nvDash\gamma\looparrowright\delta$. Hence d is not
true, so $\langle\gamma,\delta\rangle\notin\mathfrak{R}$ which means
$\mathfrak{M}\nvDash\gamma\looparrowright\delta$.

Let $\chi=\gamma\vartriangle\delta$. Assume
$\mathfrak{M}\nvDash\gamma\vartriangle\delta$. Hence either
i)$\langle\gamma,\delta\rangle\notin\mathfrak{R}$, or
ii)$\mathfrak{M}\nvDash\gamma$ or $\mathfrak{M}\nvDash\delta$. Again, i) gives
us the result immediately, so assume ii). By inductive hypothesis we get
$\gamma\in\Sigma_{k}$ or $\delta\in\Sigma_{k}$. Assume for reductio that
$\neg(\gamma\vartriangle\delta)\in\Sigma_{k}$. There is no model
$\mathfrak{M}^{\prime}$ such that $\mathfrak{M}\vDash\gamma\vartriangle\delta$
and ($\mathfrak{M}\nvDash\gamma$ or $\mathfrak{M}\nvDash\delta$), so
$\\{\neg\bot\\}$ separates $\langle\Gamma_{j},\Sigma_{k}\rangle$ –
contradiction. Hence $\gamma\vartriangle\delta\in\Sigma_{k}$. For the other
direction assume $\gamma\vartriangle\delta\in\Sigma_{k}$. Obviously d does not
hold. If c holds, then it can be easily checked that it must be the case that
$\gamma\in\Sigma_{k}$ or $\delta\in\Sigma_{k}$ (otherwise we get separation by
$\\{\neg\bot\\}$). Hence $\mathfrak{M}\nvDash\gamma$ or
$\mathfrak{M}\nvDash\delta$ which by inductive hypothesis leads to
$\mathfrak{M}\nvDash\gamma\vartriangle\delta$. When b holds, then
$\\{\gamma\vartriangle\delta\\}$ separates
$\langle\Gamma_{j},\Sigma_{k}\rangle$, so b cannot be true. Assume a. Assume
further that $\neg\gamma\in\Sigma_{k}$ and $\neg\delta\in\Sigma_{k}$. But then
$\\{\gamma\looparrowright\delta\\}$ separates
$\langle\Gamma_{j},\Sigma_{k}\rangle$(to see that observe that for no
$\mathfrak{M}^{\prime}$:
$\mathfrak{M}^{\prime}\vDash\gamma\looparrowright\delta$,
$\mathfrak{M}^{\prime}\vDash\gamma,\mathfrak{M}^{\prime}\vDash\delta$ and
$\mathfrak{M}^{\prime}\nvDash\gamma\vartriangle\delta$). It must be the case
then that $\gamma\in\Sigma_{k}$ or $\delta\in\Sigma_{k}$ which by inductive
hypothesis means either $\mathfrak{M}\nvDash\gamma$ or
$\mathfrak{M}\nvDash\delta$, so $\mathfrak{M}\nvDash\gamma\vartriangle\delta$.

This way, we have proven that $t_{j+m+1}$ is realisable which means that
$\mathfrak{M}\vDash\varphi$ and $\mathfrak{M}\nvDash\psi$. This ends the
proof. ∎

We finish with two additional remarks.

######  Remark 7.4.

Observe that the relation in model $\mathfrak{M}$ from the proof of theorem
7.1 could be defined in a following way:
$\langle\varphi,\psi\rangle\in\mathfrak{R}$ iff
$\neg(\varphi\looparrowright\psi)\notin\Gamma_{j}$ or
$\neg(\varphi\vartriangle\psi)\notin\Sigma_{k}$ or
$\varphi\looparrowright\psi\notin\Gamma_{j}$ or
$\varphi\vartriangle\psi\notin\Sigma_{k}$. Note that, although the change seem
to be purely cosmetic, thus defined relation can be radically different from
the one defined in the previous part! To see that, let
$\langle\Gamma_{j},\Sigma_{k}\rangle=\langle\\{p\\},\\{q\\}\rangle$. According
to the first definition $\mathfrak{R}=\emptyset$, whilst the current one gives
us $\mathfrak{R}=\mathsf{FOR}\times\mathsf{FOR}$. Actually, the same could be
done with the definition of $v$.

One may also wonder if the analogous result of interpolation theorem could be
obtained for Epstein implication.

######  Remark 7.5.

The interpolation theorem holds trivially for Epstein implication, that is
$\varphi\looparrowright\psi\in\mathcal{F}$ implies existence of $\chi$, such
that $\mathsf{Var}(\chi)\subseteq\mathsf{Var}(\varphi)\cap\mathsf{Var}(\psi)$,
$\varphi\looparrowright\chi\in\mathcal{F}$ and
$\chi\looparrowright\psi\in\mathcal{F}$.

###### Proof.

Let $\mathfrak{R}=\emptyset$ and $v$ be arbitrary. Observe that for any
$\varphi,\psi\in\mathsf{FOR}$, we have $\langle
v,\mathfrak{R}\rangle\nvDash\varphi\looparrowright\psi$. For this reason
$\varphi\looparrowright\psi\notin\mathcal{F}$. ∎

##  8 Conclusion

In the paper, we have used model-theoretic (mainly the $\SS$–set) techniques
to obtain some results on generalised Epstein semantics. We hope that our work
is a step towards building a serious theory of Epstein semantics. We showed
that each Epstein model has uncountably many equivalent models. We have also
proven that the logic of Epstein structures is the $\SS$-set invariant
fragment of $\mathsf{CPL}$. Additionally, we isolated continuum many
extensions of $\mathcal{F}$ which are Epstein-incomplete. We have presented a
strategy for proving completeness with respect to undefinable sets of Epstein
relations. What is important, is that we did not have to incorporate any extra
rules to the system $\mathcal{F}$ to achieve the result – we have simply
enriched $\mathcal{F}$ with extra axioms. What also seems worth mentioning, is
that providing the axiom system for the intersection of $\mathsf{R}^{s}$ and
$\mathsf{R}^{n}$, was not just a matter of combining the system $\mathcal{F}S$
and $\mathcal{F}N$. To obtain completeness, we had to include additional
axioms. Both undefinability and completeness were proven by means of the
$\SS$-set construction.

## References

  * [1] P. Blackburn, M. De Rijke, and Y. Venema.  Modal Logic.  (Cambridge Tracts in Theoretical Computer Science)Cambridge Univeristy Press, 2001.
  * [2] W. J. Blok.  The lattice of modal logics: an algebraic investigation.  ournal of Symbolic Logic, 45:221–236, 1980.
  * [3] G. S. Boolos, J. P. Burgess, and R. C. Jeffrey.  Computability and Logic (5th edition).  Cambridge University Press, New York, 2007.
  * [4] W. Carnielli.  Methods of proofs of relatedness and dependence logic.  Reports on Mathematical Logic, 21:35–46, 1987.
  * [5] A. Chagrov and M. Zakharyaschev.  Modal Logic.  Oxford University Press, London, 1999.
  * [6] R. L. Epstein.  Relatedness and implication.  Philosophical Studies, 36(2):137–173, 1979.
  * [7] R. L. Epstein.  The algebra of dependence logic.  Reports on Mathematical Logic, 21:19–34, 1987.
  * [8] R. L. Epstein.  The Semantic Foundations of Logic. Vol.1: Propositional Logics.  Nijhoff International Philosophy Series, Vol. 35. Dordrecht: Springer, 1990.
  * [9] R. L. Epstein.  Paraconsistent logics with simple semantics.  Logique et Analyse, 48:71–86, 2005.
  * [10] K. Fine.  An incomplete logic containing s4.  Theoria, 40(1):23–29, 1974.
  * [11] G. Iseminger.  Relatedness logic and entailment.  The Journal of Non-Classical Logic, 3(1):5–23, 1986.
  * [12] T. Jarmuzek and B. Kaczkowski.  On some logic with a relation imposed on formulae: Tableau system f.  Bulletin of the Section of Logic, 43(1):53–72, 2014.
  * [13] M. Klonowski.  Aksjomatyzacja logik wiazacych.  PhD Thesis, Torun, 2020.
  * [14] S. Krajewski.  On relatedness logic of Richard L. Epstein.  Bulletin of the Section of Logic, 11(1):24–40, 1982.
  * [15] S. Krajewski.  Relatedness logic.  Reports on Mathematical Logic, 20:7–14, 1986.
  * [16] S. Krajewski.  One or many logics? The Journal of Non-Classical Logic, 8(1):7–33, 1991.
  * [17] K. A. Krawczyk.  Three model-theoretic constructions for generalised Epstein models.  Review of Symbolic Logic, 15(4):1023–1032, 2022.
  * [18] F. Paoli.  Semantics for first degree relatedness logic.  Reports on Mathematical Logic, 27:81–94, 1993.
  * [19] F. Paoli.  S is constructively complete.  Reports on Mathematical Logic, 30:31–47, 1996.
  * [20] L. F. Del Cerro and V. Lugardon.  Sequents for dependence logics.  Logique et Analyse, 133/134:57–71, 1991.
  * [21] S. K. Thomason.  An incompleteness theorem in modal logic.  Theoria, 40(1):30–34, 1974.
  * [22] J. van Benthem.  Modal Correspondence Theory.  PhD Thesis, Univeristy of Amsterdam, 1976.
  * [23] J. van Bethem.  Two simple incomplete logics.  Theoria, 44(1):25–37, 1978.
  * [24] D. N. Walton.  Philosophical basis of relatedness logic.  Philosophical Studies, 36(2):115–136, 1979.
  * [25] D. N. Walton.  Relatedness in intensional action chains.  Philosophical Studies, 36(2):175–223, 1979.

Krzysztof Aleksander Krawczyk
Department of Logic
Jagiellonian University in Krakow, Poland
<EMAIL_ADDRESS>


* (11) T. Kakuda, K. Nishiwaki, K. -y. Oda and R. Watanabe, “Universal extra dimensions after Higgs discovery,” Phys. Rev. D 88 (2013) 035007 [arXiv:1305.1686 [hep-ph]].
  * (12) T. Flacke, K. Kong and S. C. Park, “126 GeV Higgs in Next-to-Minimal Universal Extra Dimensions,” arXiv:1309.7077 [hep-ph].
  * (13) T. Appelquist, H. -C. Cheng and B. A. Dobrescu, “Bounds on universal extra dimensions,” Phys. Rev. D 64 (2001) 035002 [hep-ph/0012100].
  * (14) H. C. Cheng, K. T. Matchev and M. Schmaltz, “Radiative corrections to Kaluza-Klein masses,” Phys. Rev. D 66 (2002) 036005 [hep-ph/0204342].
  * (15) I. Antoniadis, “A Possible new dimension at a few TeV,” Phys. Lett. B 246 (1990) 377.
  * (16) F. del Aguila, M. Perez-Victoria and J. Santiago, “Bulk fields with general brane kinetic terms,” JHEP 0302 (2003) 051 [hep-th/0302023].
  * (17) F. del Aguila, M. Perez-Victoria and J. Santiago, “Bulk fields with brane terms,” Eur. Phys. J. C 33 (2004) S773 [hep-ph/0310352].
  * (18) F. del Aguila, M. Perez-Victoria and J. Santiago, “Effective description of brane terms in extra dimensions,” JHEP 0610 (2006) 056 [hep-ph/0601222].
  * (19) Y. Fujimoto, T. Nagasawa, K. Nishiwaki and M. Sakamoto, “Quark mass hierarchy and mixing via geometry of extra dimension with point interactions,” PTEP 2013 (2013) 023B07 [arXiv:1209.5150 [hep-ph]].
  * (20) Y. Fujimoto, K. Nishiwaki and M. Sakamoto, “CP phase from twisted Higgs VEV in extra dimension,” arXiv:1301.7253 [hep-ph].
  * (21) A. Datta, K. Nishiwaki and S. Niyogi, “Non-minimal Universal Extra Dimensions: The Strongly Interacting Sector at the Large Hadron Collider,” JHEP 1211 (2012) 154 [arXiv:1206.3987 [hep-ph]].
  * (22) A. Datta, U. K. Dey, A. Shaw and A. Raychaudhuri, “Universal Extra-Dimensional Models with Boundary Localized Kinetic Terms: Probing at the LHC,” Phys. Rev. D 87 (2013) 076002 [arXiv:1205.4334 [hep-ph]].
  * (23) A. Datta, A. Raychaudhuri and A. Shaw, “LHC limits on KK-parity non-conservation in the strong sector of universal extra-dimension models,” arXiv:1310.2021 [hep-ph].
  * (24) D. Choudhury, A. Datta and K. Ghosh, “Deciphering Universal Extra Dimension from the top quark signals at the CERN LHC,” JHEP 1008 (2010) 051 [arXiv:0911.4064 [hep-ph]].
  * (25) J. A. Aguilar-Saavedra, “Identifying top partners at LHC,” JHEP 0911, 030 (2009) [arXiv:0907.3155 [hep-ph]].
  * (26) G. Cacciapaglia, A. Deandrea, D. Harada and Y. Okada, “Bounds and Decays of New Heavy Vector-like Top Partners,” JHEP 1011, 159 (2010) [arXiv:1007.2933 [hep-ph]].
  * (27) G. Cacciapaglia, A. Deandrea, L. Panizzi, N. Gaur, D. Harada and Y. Okada, “Heavy Vector-like Top Partners at the LHC and flavour constraints,” JHEP 1203, 070 (2012) [arXiv:1108.6329 [hep-ph]].
  * (28) J. Berger, J. Hubisz and M. Perelstein, “A Fermionic Top Partner: Naturalness and the LHC,” JHEP 1207 (2012) 016 [arXiv:1205.0013 [hep-ph]].
  * (29) A. De Simone, O. Matsedonskyi, R. Rattazzi and A. Wulzer, “A First Top Partner Hunter’s Guide,” JHEP 1304 (2013) 004 [arXiv:1211.5663 [hep-ph]].
  * (30) J. Kearney, A. Pierce and J. Thaler, “Top Partner Probes of Extended Higgs Sectors,” JHEP 1308 (2013) 130 [arXiv:1304.4233 [hep-ph]].
  * (31) M. Buchkremer, G. Cacciapaglia, A. Deandrea and L. Panizzi, “Model Independent Framework for Searches of Top Partners,” Nucl. Phys. B 876 (2013) 376 [arXiv:1305.4172 [hep-ph]].
  * (32) J. A. Aguilar-Saavedra, R. Benbrik, S. Heinemeyer and M. Perez-Victoria, “A handbook of vector-like quarks: mixing and single production,” Phys. Rev. D 88, 094010 (2013) [arXiv:1306.0572 [hep-ph]].
  * (33) F. del Aguila, M. Perez-Victoria and J. Santiago, “Some consequences of brane kinetic terms for bulk fermions,” hep-ph/0305119.
  * (34) F. del Aguila, M. Perez-Victoria and J. Santiago, “Physics of brane kinetic terms,” Acta Phys. Polon. B 34 (2003) 5511 [hep-ph/0310353].
  * (35) T. Flacke, A. Menon and D. J. Phalen, “Non-minimal universal extra dimensions,” Phys. Rev. D 79 (2009) 056009 [arXiv:0811.1598 [hep-ph]].
  * (36) P. Bandyopadhyay, B. Bhattacherjee and A. Datta, “Search for Higgs bosons of the Universal Extra Dimensions at the Large Hadron Collider,” JHEP 1003 (2010) 048 [arXiv:0909.3108 [hep-ph]].
  * (37) S. Chatrchyan et al. [CMS Collaboration], “Search for the standard model Higgs boson produced in association with a top-quark pair in $pp$ collisions at the LHC,” JHEP 1305 (2013) 145 [arXiv:1303.0763 [hep-ex]].
  * (38) CMS Collaboration, “Search for ttH production in events where $H$ decays to photons at 8 TeV collisions”, CMS-PAS-HIG-13-015.
  * (39) ATLAS collaboration, “Search for $ttH$ production in the $H\to\gamma\gamma$ channel at $\sqrt{s}=8$ TeV with the ATLAS detector”, ATLAS-CONF-2013-080.
  * (40) K. Nishiwaki, S. Niyogi and A. Shivaji, “$ttH$ Anomalous Coupling in Double Higgs Production,” arXiv:1309.6907 [hep-ph].
  * (41) S. Alekhin, A. Djouadi and S. Moch, “The top quark and Higgs boson masses and the stability of the electroweak vacuum,” Phys. Lett. B 716 (2012) 214 [arXiv:1207.0980 [hep-ph]].
  * (42) CDF [Tevatron Electroweak Working Group and D0 Collaborations], “Combination of CDF and DO results on the mass of the top quark using up to 8.7 fb-1 at the Tevatron,” arXiv:1305.3929 [hep-ex].
  * (43) Diploma thesis by D. Gerstenlauer, “Flavor Physics in Universal Extra Dimension Models with Brane Kinetic Localized Terms,” Universität Würzburg, May 2011.
  * (44) R Aaij et al. [LHCb Collaboration], “Observation of $D^{0}-\overline{D}^{0}$ oscillations,” Phys. Rev. Lett. 110 (2013) 101802 [arXiv:1211.1230 [hep-ex]].
  * (45) M. Bona et al. [UTfit Collaboration], “Model-independent constraints on $\Delta$ F=2 operators and the scale of new physics,” JHEP 0803, 049 (2008) [arXiv:0707.0636 [hep-ph]].
  * (46) M. E. Peskin and T. Takeuchi, “A New constraint on a strongly interacting Higgs sector,” Phys. Rev. Lett. 65 (1990) 964.
  * (47) M. E. Peskin and T. Takeuchi, “Estimation of oblique electroweak corrections,” Phys. Rev. D 46 (1992) 381.
  * (48) T. Appelquist and H. -U. Yee, “Universal extra dimensions and the Higgs boson mass,” Phys. Rev. D 67 (2003) 055002 [hep-ph/0211023].
  * (49) T. Flacke, D. Hooper and J. March-Russell, “Improved bounds on universal extra dimensions and consequences for LKP dark matter,” Phys. Rev. D 73 (2006) 095002 [Erratum-ibid. D 74 (2006) 019902] [hep-ph/0509352].
  * (50) I. Gogoladze and C. Macesanu, “Precision electroweak constraints on Universal Extra Dimensions revisited,” Phys. Rev. D 74 (2006) 093012 [hep-ph/0605207].
  * (51) M. Baak, M. Goebel, J. Haller, A. Hoecker, D. Ludwig, K. Moenig, M. Schott and J. Stelzer, “Updated Status of the Global Electroweak Fit and Constraints on New Physics,” Eur. Phys. J. C 72 (2012) 2003 [arXiv:1107.0975 [hep-ph]].
  * (52) T. Flacke, K. Kong and S. C. Park, “Phenomenology of Universal Extra Dimensions with Bulk-Masses and Brane-Localized Terms,” JHEP 1305 (2013) 111 [arXiv:1303.0872 [hep-ph]].
  * (53) T. G. Rizzo and J. D. Wells, “Electroweak precision measurements and collider probes of the standard model with large extra dimensions,” Phys. Rev. D 61 (2000) 016007 [hep-ph/9906234].
  * (54) H. Davoudiasl, J. L. Hewett and T. G. Rizzo, “Bulk gauge fields in the Randall-Sundrum model,” Phys. Lett. B 473 (2000) 43 [hep-ph/9911262].
  * (55) C. Csaki, J. Erlich and J. Terning, “The Effective Lagrangian in the Randall-Sundrum model and electroweak physics,” Phys. Rev. D 66 (2002) 064021 [hep-ph/0203034].
  * (56) M. S. Carena, E. Ponton, T. M. P. Tait and C. E. M Wagner, “Opaque branes in warped backgrounds,” Phys. Rev. D 67 (2003) 096006 [hep-ph/0212307].
  * (57) T. Flacke and C. Pasold, “Constraints on split-UED from Electroweak Precision Tests,” Phys. Rev. D 85, 126007 (2012) [arXiv:1111.7250 [hep-ph]].
  * (58) M. Baak, M. Goebel, J. Haller, A. Hoecker, D. Kennedy, R. Kogler, K. Moenig and M. Schott et al., “The Electroweak Fit of the Standard Model after the Discovery of a New Boson at the LHC,” Eur. Phys. J. C 72, 2205 (2012) [arXiv:1209.2716 [hep-ph]].
  * (59) T. Flacke, A. Menon and Z. Sullivan, “Constraints on UED from $W^{\prime}$ searches,” Phys. Rev. D 86 (2012) 093006 [arXiv:1207.4472 [hep-ph]].
  * (60) S. Chatrchyan et al. [CMS Collaboration], “Search for charge-asymmetric production of $W$ ’ bosons in top pair + jet events from $pp$ collisions at $\sqrt{s}=7$ TeV,” Phys. Lett. B 717 (2012) 351 [arXiv:1206.3921 [hep-ex]].
  * (61) R. Kelley, L. Randall and B. Shuve, “Early (and Later) LHC Search Strategies for Broad Dimuon Resonances,” JHEP 1102 (2011) 014 [arXiv:1011.0728 [hep-ph]].
  * (62) J. Alwall, M. Herquet, F. Maltoni, O. Mattelaer and T. Stelzer, “MadGraph 5 : Going Beyond,” JHEP 1106 (2011) 128 [arXiv:1106.0522 [hep-ph]].
  * (63) N. D. Christensen and C. Duhr, “FeynRules - Feynman rules made easy,” Comput. Phys. Commun. 180 (2009) 1614 [arXiv:0806.4194 [hep-ph]].
  * (64) C. Degrande, C. Duhr, B. Fuks, D. Grellscheid, O. Mattelaer and T. Reiter, “UFO - The Universal FeynRules Output,” Comput. Phys. Commun. 183 (2012) 1201 [arXiv:1108.2040 [hep-ph]].
  * (65) P. de Aquino, W. Link, F. Maltoni, O. Mattelaer and T. Stelzer, “ALOHA: Automatic Libraries Of Helicity Amplitudes for Feynman Diagram Computations,” Comput. Phys. Commun. 183 (2012) 2254 [arXiv:1108.2041 [hep-ph]].
  * (66) G. Aad et al. [ATLAS Collaboration], “Search for direct third-generation squark pair production in final states with missing transverse momentum and two b-jets in $\sqrt{s}$=8 TeV $pp$ collisions with the ATLAS detector,” arXiv:1308.2631 [hep-ex].
  * (67) S. Chatrchyan et al. [CMS Collaboration], “Search for top-squark pair production in the single-lepton final state in $pp$ collisions at $\sqrt{s}=8$ TeV,” arXiv:1308.1586 [hep-ex].
  * (68) A. Altheimer, S. Arora, L. Asquith, G. Brooijmans, J. Butterworth, M. Campanelli, B. Chapleau and A. E. Cholakian et al., “Jet Substructure at the Tevatron and LHC: New results, new tools, new benchmarks,” J. Phys. G 39 (2012) 063001 [arXiv:1201.0008 [hep-ph]].
  * (69) M. Dasgupta, A. Fregoso, S. Marzani and G. P. Salam, “Towards an understanding of jet substructure,” JHEP 1309 (2013) 029 [arXiv:1307.0007 [hep-ph]].
  * (70) D. E. Kaplan, K. Rehermann, M. D. Schwartz and B. Tweedie, “Top Tagging: A Method for Identifying Boosted Hadronically Decaying Top Quarks,” Phys. Rev. Lett. 101 (2008) 142001 [arXiv:0806.0848 [hep-ph]].
  * (71) [CMS Collaboration], “A Cambridge-Aachen (C-A) based Jet Algorithm for boosted top-jet tagging,” CMS-PAS-JME-09-001.
  * (72) T. Plehn and M. Spannowsky, “Top Tagging,” J. Phys. G 39 (2012) 083001 [arXiv:1112.4441 [hep-ph]].
  * (73) S. Schaetzel and M. Spannowsky, “Tagging highly boosted top quarks,” arXiv:1308.0540 [hep-ph].
  * (74) J. M. Butterworth, A. R. Davison, M. Rubin and G. P. Salam, “Jet substructure as a new Higgs search channel at the LHC,” Phys. Rev. Lett. 100 (2008) 242001 [arXiv:0802.2470 [hep-ph]].
  * (75) D. Binosi and L. Theussl, “JaxoDraw: A Graphical user interface for drawing Feynman diagrams,” Comput. Phys. Commun. 161 (2004) 76 [hep-ph/0309015].
  * (76) J. A. M. Vermaseren, “Axodraw,” Comput. Phys. Commun. 83 (1994) 45.
  * (77) P. M. Nadolsky, H. -L. Lai, Q. -H. Cao, J. Huston, J. Pumplin, D. Stump, W. -K. Tung and C. -P. Yuan, “Implications of CTEQ global analysis for collider observables,” Phys. Rev. D 78 (2008) 013004 [arXiv:0802.0007 [hep-ph]].
  * (78) A. Djouadi, J. L. Kneur and G. Moultaka, “Higgs boson production in association with scalar top quarks at proton colliders,” Phys. Rev. Lett. 80 (1998) 1830 [hep-ph/9711244].
  * (79) A. Djouadi, “The Anatomy of electro-weak symmetry breaking. II. The Higgs bosons in the minimal supersymmetric model,” Phys. Rept. 459 (2008) 1 [hep-ph/0503173] and references therein.
  * (80) W. Beenakker, S. Dittmaier, M. Kramer, B. Plumper, M. Spira and P. M. Zerwas, “Higgs radiation off top quarks at the Tevatron and the LHC,” Phys. Rev. Lett. 87 (2001) 201805 [hep-ph/0107081].
  * (81) A. Djouadi, “The Anatomy of electro-weak symmetry breaking. I: The Higgs boson in the standard model,” Phys. Rept. 457 (2008) 1 [hep-ph/0503172] and references therein.
  * (82) S. Chatrchyan et al. [CMS Collaboration], “Search for heavy, top-like quark pair production in the dilepton final state in $pp$ collisions at $\sqrt{s}=7$ TeV,” Phys. Lett. B 716 (2012) 103 [arXiv:1203.5410 [hep-ex]].
  * (83) G. Aad et al. [ATLAS Collaboration], “Search for pair production of heavy top-like quarks decaying to a high-pT $W$ boson and a $b$ quark in the lepton plus jets final state at $\sqrt{s}$=7 TeV with the ATLAS detector,” Phys. Lett. B 718 (2013) 1284 [arXiv:1210.5468 [hep-ex]].
  * (84) [ATLAS Collaboration], “Search for pair production of heavy top-like quarks decaying to a high-$p_{T}$ $W$ boson and a $b$ quark in the lepton plus jets final state in $pp$ collisions at $\sqrt{s}=8$ TeV with the ATLAS detector”, ATLAS-CONF-2013-060.
  * (85) Y. Adachi, N. Kurahashi, C. S. Lim and N. Maru, “$D^{0}-\bar{D}^{0}$ Mixing in Gauge-Higgs Unification,” JHEP 1201, 047 (2012) [arXiv:1103.5980 [hep-ph]].