1 Introduction and definition
The relation of logical friendliness, introduced in the propositional context in [Reference Makinson and Beziau15], has a very straightforward definition as a
$\forall \exists $
version of the fundamental
$\forall \forall $
notion of consequence. The
$\forall \forall $
formulation is expressed as follows, where
$\Gamma $
is any set of formulae of classical propositional logic,
$\phi $
is a formula of the same, and
$\models $
is the satisfaction relation between valuations and sets of sentences:
-
$ \Gamma \vdash \phi $
iff for every classical valuation v on propositional variables occurring in formulae of
$\Gamma $
, if
$v \models \Gamma $
then
$v' \models \phi $
for every extension
$v'$
of v to cover any remaining variables in
$\phi $
.
Friendliness is defined by replacing the universal quantifier in that definition by an existential one:
-
$ \Gamma $
is said to be friendly to
$\phi $
iff for every classical valuation v on propositional variables occurring in formulae of
$\Gamma $
, if
$v \models \Gamma $
then
$v' \models \phi $
for some extension
$v'$
of v to cover any remaining variables in
$\phi $
.
So defined, friendliness has a number of interesting features, examined in detail in [Reference Makinson and Beziau15]. But if we seek to extend it to the first-order context, options arise due to the greater complexity of first-order models compared to propositional valuations. Instead of just one natural
$\forall \forall $
formulation of classical consequence, there are several. Let L be a predicate language (in the sense of a vocabulary of non-logical symbols) with equality (taken as a predicate having the fixed interpretation of ‘true identity’ in all models), function, relation, and constant symbols. As usual in the presence of equality, we can treat function and individual constant symbols as additional predicate letters, so we may assume the language is purely relational for simplicity. Let
$\Gamma $
be a set of sentences and
$\phi $
a sentence from
$L$
. Write
$L_{\Gamma }$
for the language of
$\Gamma $
,
$L_{\Gamma ,\phi }$
for the language of
$\Gamma \cup \{\phi \}$
, and
$\models $
for the satisfaction relation between models and sets of sentences. Then each of the four bulleted conditions characterizes
$ \Gamma \vdash \phi $
.
For every model
$\mathfrak {A}$
for the language
$L_{\Gamma }$
, if
$\mathfrak {A}\models \Gamma $
then:
-
•
$\mathfrak {A}'\models \phi $
for every model
$\mathfrak {A}'$
that expands
$\mathfrak {A}$
to the language
$L_{\Gamma , \phi }$
. -
•
$\mathfrak {A}" \models \phi $
for every model
$\mathfrak {A}"$
that expands to the language
$L_{\Gamma , \phi }$
some model
$\mathfrak {A}'$
for
$L_{\Gamma }$
that is isomorphic to
$\mathfrak {A}$
. -
•
$\mathfrak {A}" \models \phi $
for every model
$\mathfrak {A}"$
that expands to the language
$L_{\Gamma , \phi }$
some model
$\mathfrak {A}'$
for
$L_{\Gamma }$
within which
$\mathfrak {A}$
can be elementarily embedded. -
•
$\mathfrak {A}" \models \phi $
for every model
$\mathfrak {A}"$
that expands to the language
$L_{\Gamma , \phi }$
some model
$\mathfrak {A}'$
for
$L_{\Gamma }$
to which
$\mathfrak {A}$
is elementary equivalent.
Each of these
$\forall \forall $
formulations of consequence gives rise to a corresponding
$\forall \exists $
notion of friendliness, obtained by replacing the universal quantifier by an existential one.
For every model
$\mathfrak {A}$
for the language
$L_{\Gamma }$
, if
$\mathfrak {A}\models \Gamma $
then:
-
•
$\mathfrak {A}'\models \phi $
for some model
$\mathfrak {A}'$
that expands
$\mathfrak {A}$
to the language
$L_{\Gamma , \phi }$
. -
•
$\mathfrak {A}" \models \phi $
for some model
$\mathfrak {A}"$
that expands to the language
$L_{\Gamma , \phi }$
some model
$\mathfrak {A}'$
for
$L_{\Gamma }$
that is isomorphic to
$\mathfrak {A}$
. -
•
$\mathfrak {A}" \models \phi $
for some model
$\mathfrak {A}"$
that expands to the language
$L_{\Gamma , \phi }$
some model
$\mathfrak {A}'$
for
$L_{\Gamma }$
within which
$\mathfrak {A}$
can be elementarily embedded. -
•
$\mathfrak {A}" \models \phi $
for some model
$\mathfrak {A}"$
that expands to the language
$L_{\Gamma , \phi }$
some model
$\mathfrak {A}'$
for
$L_{\Gamma }$
to which
$\mathfrak {A}$
is elementary equivalent.
Clearly, these are in increasing order of generality, but they are not all distinct. As will be shown in the Appendix to this paper, the first is equivalent to the second while the third is equivalent to the fourth, leaving two distinct notions. We will work with the more general one, which turns out to be better behaved and exhibit greater continuity with the propositional case. We prefer, however, to define it in the third rather than the fourth manner, because that formulation facilitates our proofs using Robinson diagrams (Propositions 4 and 7).
Definition 1. Let
$\Gamma $
be a set of sentences and
$\phi $
a sentence of first-order logic. We say that
$\Gamma $
is friendly to
$\phi $
(in symbols,
) iff for every model
$\mathfrak {A}$
for the language
$L_{\Gamma }$
, if
$\mathfrak {A} \models \Gamma $
then
$\mathfrak {A}"\models \phi $
for some model
$\mathfrak {A}"$
that expands (to the language
$L_{\Gamma , \phi }$
) some model
$\mathfrak {A}'$
for
$L_{\Gamma }$
within which
$\mathfrak {A}$
can be elementarily embedded.
For memory, we recall the definitions and usual notations for elementary embedding and expansion. If
$\mathfrak {A}$
and
$\mathfrak {B}$
are structures for any language
$L_{\Gamma } $
, we write
$\mathfrak {A}\preceq _{L_{\Gamma }}\mathfrak {B}$
to mean that there is an injection
$f: A\longrightarrow B$
such that for any formula
$\psi $
of the language
$L_{\Gamma }$
,
$\mathfrak {A}\models \psi [\overline {a}]$
iff
$\mathfrak {B}\models \psi [f(\overline {a})]$
(this is an elementary embedding with respect to the language
$L_{\Gamma } $
). Given a structure
$\mathfrak {A}$
for a language L, an expansion of
$\mathfrak {A}$
to a language
$L' \supseteq L$
is any model
$\mathfrak {A}'$
for
$L'$
with the same domain as
$\mathfrak {A} $
, interpreting the symbols of L as in
$\mathfrak {A}$
, and specifying interpretations for the new predicate symbols in
$L'$
.
Using this notation, Definition 1 can be reformulated briefly as follows:
Definition 1 (Equivalent formulation).
Let
$\Gamma $
be a set of sentences and
$\phi $
a sentence from L. We say that
$\Gamma $
is friendly to
$\phi $
(in symbols,
) iff for every model
$\mathfrak {A} \models \Gamma $
for the language
$L_{\Gamma }$
, there is a model
$\mathfrak {A}'$
for the same language such that
$\mathfrak {A}\preceq _{L_{\Gamma }} \mathfrak {A}'$
and, furthermore,
$\mathfrak {A}'$
can be expanded to a model
$\mathfrak {A}"$
for the language
$L_{\Gamma , \phi }$
for which
$\mathfrak {A}"\models \phi $
.
We end this introduction with three remarks that may help the reader appreciate the boundaries of the definition.
Example 1. A simple example taken from [Reference Kossak12], where it is used for a different purpose, shows that
is not a trivial relation. Suppose
$(G, +)$
is a six-element group. Then
$\text {Th}(G, +)$
, the complete first-order theory of the structure
$(G, +)$
, is not friendly to the sentence
$\phi _{\text {Field}}$
, the conjunction of the axioms for fields. This is because every elementary extension of
$(G, +)$
still has exactly six elements, and all finite fields are of order
$p^n$
for some
$n\geq 1$
and p prime. Similarly, considering now infinite structures, the complete first-order theory of
$(\mathbb {Z}, +)$
is not friendly to
$\phi _{\text {Field}}$
as we have that
$\phi _{\text {Field}} \vdash (1+1=0) \vee \exists x (x+x=1)$
but
$(1+1=0) \vee \exists x (x+x=1)$
is false in the structure
$(\mathbb {Z}, +)$
.
1.1 Upper bound to generality
If we seek to increase the generality of the definition of friendliness further, by replacing the notion of expansion by a more general relation that also allows the addition of new elements to the domain, then the desired relationship to classical consequence breaks down: the
$\forall \forall $
counterpart of such a definition no longer coincides with classical consequence. This is shown in the Appendix.
1.2 Irregularities
While Definition 1 provides the most regular notion of friendliness in the first-order context that we have been able to construct, it will be shown in the text that it is still not as regular as is the corresponding relation in the propositional context. Specifically, both compactness and interpolation fail (although a Beth property holds). Such irregularities diminish when the language does not contain equality, as will be shown in the Appendix.
2 Continuities with the propositional case
This section extends to the first-order context a number of properties established in [Reference Makinson and Beziau15] for the propositional one and introduces some properties new to the first-order context. Properties that do not extend to the first-order context are considered in Section 3.
The first proposition (supraclassicality) is trivial but worth stating as it is repeatedly applied:
Proposition 2 (Supraclassicality).
$\Gamma \vdash \phi $
only if
.
Proof. Suppose that
$\Gamma \vdash \phi $
. Consider a model
$\mathfrak {A} \models \Gamma $
for the language
$L_{\Gamma }$
. Then any model
$\mathfrak {A}'$
for the same language such that
$\mathfrak {A}\preceq _{L_{\Gamma }} \mathfrak {A}'$
is a model of
$\Gamma $
so, since
$\Gamma \vdash \phi $
, in whatever way one expands
$\mathfrak {A}'$
to a model
$\mathfrak {A}"$
for the language
$L_{\Gamma , \phi }$
we must have
$\mathfrak {A}"\models \phi $
.
Next we identify four contexts in which
reduces to
$\vdash $
. In some of them, we use Robinson diagrams. The reader can consult [Reference Hodges9] for an exposition of the technique. For any structure
$\mathfrak {B}$
for a language L, we will let
$\text {eldiag}(\mathfrak {B})$
denote the elementary diagram of the structure
$\mathfrak {B}$
. Importantly,
$\text {eldiag}(\mathfrak {B})$
is a theory in the language resulting from adding to L new constants for all the elements in the domain of
$\mathfrak {B}$
and containing all the first-order sentences true in the expansion
$\mathfrak {B}'$
of
$\mathfrak {B}$
where each constant has been interpreted as its corresponding element in the domain of
$\mathfrak {B}$
. The useful feature of
$\text {eldiag}(\mathfrak {B})$
is that whenever a model satisfies it,
$\mathfrak {B}$
can be elementarily embedded into its restriction to language L [Reference Hodges9, lemma 2.5.3].
Proposition 3 (First Reduction Case).
If
$L_{\phi } \subseteq L_{\Gamma }$
, then
iff
$\Gamma \vdash \phi $
.
Proof. Right to left holds directly by supraclassicality. Left to right: Suppose that
and
$\mathfrak {A}\models \Gamma $
where
$\mathfrak {A}$
is a model for the language
$L_{\Gamma , \phi }$
; we need to show that
$\mathfrak {A} \models \phi $
. By the hypothesis, there is a model
$\mathfrak {A}'$
for the same language such that
$\mathfrak {A}\preceq _{L_{\Gamma }} \mathfrak {A}'$
and, furthermore,
$\mathfrak {A}'$
can be expanded to a model
$\mathfrak {A}"$
for the language
$L_{\Gamma ,\phi }$
for which
$\mathfrak {A}"\models \phi $
. However, since
$L_{\phi } \subseteq L_{\Gamma }$
,
$\mathfrak {A}"=\mathfrak {A}'$
, so
$\mathfrak {A}'\models \phi $
and since
$\mathfrak {A}\preceq _{L_{\Gamma }} \mathfrak {A}'$
, also
$\mathfrak {A} \models \phi $
as desired.
Proposition 4 (Second Reduction Case).
Let
$\Gamma $
be a consistent and complete theory in a language
$L_{\Gamma }$
. Then for any sentence
$\phi $
of L,
iff
$\Gamma \not \vdash \neg \phi $
.
Proof. Let
. Since
$\Gamma $
is consistent, we have a model
$\mathfrak {A} \models \Gamma $
for the language
$L_{\Gamma }$
, but given that
, there is a model
$\mathfrak {A}'$
for the same language such that
$\mathfrak {A}\preceq _{L_{\Gamma }} \mathfrak {A}'$
and, furthermore,
$\mathfrak {A}'$
can be expanded to a model
$\mathfrak {A}"$
for the language
$L_{\Gamma ,\phi }$
for which
$\mathfrak {A}"\models \phi $
. But if
$\Gamma \vdash \neg \phi $
, then each of
$\mathfrak {A}, \mathfrak {A}', \mathfrak {A}" \models \neg \phi $
. Consequently,
$\Gamma \not \vdash \neg \phi $
.
For the converse, assume that
$\Gamma \not \vdash \neg \phi $
. Then we have a model
$\mathfrak {B}$
for the language
$L_{\Gamma ,\phi }$
such that
$\mathfrak {B}\models \Gamma $
and
$\mathfrak {B}\not \models \neg \phi $
, i.e.,
$\mathfrak {B} \models \phi $
, and clearly,
$(\mathfrak {B}\upharpoonright L_{\Gamma })\models \Gamma $
. We need to show that
. Let
$\mathfrak {A}$
be a model for the language
$L_{\Gamma }$
with
$\mathfrak {A}\models \Gamma $
. We need to find a model
$\mathfrak {A}'$
for the same language such that
$\mathfrak {A}\preceq _{L_{\Gamma }} \mathfrak {A}'$
and an expansion
$\mathfrak {A}"$
of
$\mathfrak {A}'$
to the language
$L_{\Gamma , \phi }$
for which
$\mathfrak {A}"\models \phi $
. To find a suitable
$\mathfrak {A}'$
, first observe that
$\mathfrak {B} \equiv _{L_{\Gamma }} \mathfrak {A}$
(the structures are elementarily equivalent in the language
$L_{\Gamma }$
) since
$\Gamma $
is complete. This implies that
$\text {Th}_{L_{\Gamma }}(\mathfrak {A}) \cup \{\phi \} = \text {Th}_{L_{\Gamma }}(\mathfrak {B}) \cup \{\phi \}$
is consistent. By a routine compactness argument using Robinson diagrams, there is a model
$\mathfrak {A}'$
with the properties that we need. We briefly sketch the argument. All we need to do is show that
$\text {eldiag}(\mathfrak {A}) \cup \{\phi \}$
is consistent and therefore has a model
$\mathfrak {C}$
for then we can let
$\mathfrak {A}" = (\mathfrak {C} \upharpoonright L_{\Gamma ,\phi })$
and
$\mathfrak {A}' = (\mathfrak {C} \upharpoonright L_{\Gamma })$
. Suppose otherwise, that is, for some finite
$T \subseteq \text {eldiag}(\mathfrak {A})$
, the theory
$T \cup \{\phi \}$
is not consistent. Then
$\phi \vdash \neg \bigwedge T$
, but then since the diagram constants in T are all new to
$L_{\Gamma , \phi }$
,
$\phi \vdash \forall \overline {x}\neg \bigwedge T^*$
by [Reference Hodges9, lemma 2.3.2] where
$T^*$
is the result of replacing in every sentence in T the new constants by new variables. But then
$\mathfrak {B}\models \forall \overline {x}\neg \bigwedge T^*$
and since
$\mathfrak {A} \equiv _{L_{\Gamma }} \mathfrak {B}$
, we have that
$\mathfrak {A}\models \forall \overline {x}\neg \bigwedge T^*$
which is a contradiction since
$\mathfrak {A}\models \exists \overline {x} \bigwedge T^*$
.
The following two reduction cases concern the case where
$\Gamma$
is empty and may appear less interesting in themselves, but turn out to be useful in proving results on recursive enumerability (Proposition 19 and Remark 21).
Proposition 5 (Third Reduction Case).
For any sentence
$\phi $
of L not involving the equality symbol,
iff
$\phi $
is satisfiable.
Proof. Left to right holds by Proposition 2. For the converse, suppose that
$\phi $
is satisfiable, so there is a model
$\mathfrak {A}$
in the language
$L_{\phi }$
with
$\mathfrak {A} \models \phi $
. Since
$\phi $
is equality-free, Lemma [Reference Bridge5, lemma 2.24] tells us that there is an infinite model
$\mathfrak {A}"$
with
$|A"|> |A|$
with
$\mathfrak {A}" \models \phi $
. Choose
$\mathfrak {A}'$
to be the restriction of
$\mathfrak {A}"$
to the empty language. Since
$\mathfrak {A, A}'$
are both models for the empty language without negation, they are elementary equivalent;
$\mathfrak {A}'$
extends to
$\mathfrak {A}"$
; and
$\mathfrak {A}" \models \phi $
. Thus the right-hand side of the proposition holds.
Proposition 6 (Fourth Reduction Case).
For any sentence
$\phi $
of L not involving any other predicate than the equality symbol ‘
$=$
’,
iff
$\vdash \phi $
.
Proof. We start by observing that
$\phi $
has models of all sizes only if
. Suppose first that
$\phi $
has models of all sizes. Then let
$\mathfrak {A}$
be a model for the empty language, so that
$\mathfrak {A}$
may be identified with a set. But then surely it can be expanded to a model of
$\phi $
by the hypothesis that
$\phi $
has models of all sizes. Now we claim that
iff
$\phi $
has models of all finite sizes. If
then any finite set can be expanded to a model of
$\phi $
because any elementary extension of a structure of n elements satisfies a first-order formula saying ‘there are n elements’. Hence,
$\phi $
has models of all finite cardinalities. If the latter, on the other hand, given any finite set we can find a model of
$\phi $
of the same cardinality as the original set and when seen as a model in the empty language it will be trivially isomorphic to the original set. Moreover, by the compactness theorem, any formula
$\phi $
has models of all cardinalities if it has models of all finite cardinalities. (If
$\phi $
has models of all finite cardinalities then the theory T formed by
$\phi $
and the set of sentences ‘there are at least n elements’ for every n, is finitely satisfiable and by compactness, satisfiable in an infinite model, so, using the Löwenheim–Skolem theorem, in models of any infinite cardinality.) Assume that
$\phi $
has models of all finite sizes. Since the language only has equality this means that
$\phi $
is true in all finite models, as they are just sets. Suppose for contradiction that
$\nvdash \phi $
, that is,
$\neg \phi $
has a model, but then by [Reference Ash2, theorem 1] it must have a finite model, which by hypothesis must also be a model of
$\phi $
. Thus
$\phi $
has models of all finite sizes iff
$\vdash \phi $
.
A simple consequence of Proposition 6 is that, in contrast to the propositional case [Reference Makinson and Beziau15], here we do not always get
if
$\phi $
is consistent. In particular, if
$\phi $
is any pure equality sentence such that
$\not \vdash \phi $
we will also have
.
Proposition 7 (Characterization in terms of consistency).
Let
$\Gamma $
be a set of sentences and
$\phi $
a sentence from L. Then the following are equivalent:
-
(i)
. -
(ii)
$\phi $
is consistent with every set
$\Delta $
of sentences in the language
$L_{\Gamma }$
that is consistent with
$\Gamma $
.
Proof.
$(i) \implies (ii)$
: Suppose
and
$\Delta $
is a set of sentences in the language
$L_{\Gamma }$
consistent with
$\Gamma $
, so that there is a model
$\mathfrak {A} \models \Gamma \cup \Delta $
for the language
$L_{\Gamma }$
. But then, since
, there is a model
$\mathfrak {A}'$
for the same language such that
$\mathfrak {A}\preceq _{L_{\Gamma }} \mathfrak {A}'$
(and thus
$\mathfrak {A}'\models \Delta $
) and
$\mathfrak {A}'$
can be expanded to a model
$\mathfrak {A}"$
for the language
$L_{\Gamma ,\phi }$
for which
$\mathfrak {A}"\models \phi $
. Consequently,
$\phi $
is consistent with
$ \Delta $
.
$(ii) \implies (i)$
: Assume that
, that is, there is a model
$\mathfrak {A} $
for the language
$L_{\Gamma }$
such that
$\mathfrak {A} \models \Gamma $
and for any
$\mathfrak {A}'$
with
$\mathfrak {A}\preceq _{L_{\Gamma }} \mathfrak {A}'$
, any expansion
$\mathfrak {A}"$
of
$\mathfrak {A}'$
to the language
$L_{\Gamma ,\phi }$
is such that
$\mathfrak {A}" \not \models \phi $
, i.e.,
$\mathfrak {A}" \models \neg \phi $
. Take now
$\Delta =\text {Th}_{L_{\Gamma }}(\mathfrak {A})$
(the complete first-order theory of
$\mathfrak {A}$
in
$L_{\Gamma }$
). We show that
$\phi $
is not consistent with
$\Delta $
(clearly
$\Delta $
is consistent with
$\Gamma $
by construction). Suppose for a contradiction that
$\Delta \cup \{\phi \}$
is consistent; then one can show using Robinson diagrams as before that there is a model
$\mathfrak {A}" \models \phi $
for the language
$L_{\Gamma ,\phi }$
such that
$\mathfrak {A}\preceq _{L_{\Gamma }} (\mathfrak {A}"\upharpoonright L_{\Gamma })$
(where
$(\mathfrak {A}"\upharpoonright L_{\Gamma })$
is the restriction of
$\mathfrak {A}"$
to the language
$L_{\Gamma }$
). Choosing
$\mathfrak {A}'$
as
$\mathfrak {A}"$
restricted to
$L_{\Gamma }$
, and noting that
$\mathfrak {A}"$
is an expansion of
$\mathfrak {A}'$
to the language
$L_{\gamma , \phi }$
we also have
$\mathfrak {A}"$
does not satisfy
$\phi $
, giving the desired contradiction.
The characterization in terms of consistency can then be refined as follows, with the same verifications as in [Reference Makinson and Beziau15]. Observe that those verifications made use of Craig’s interpolation [Reference Craig6] for classical consequence and hence needed the presence of a falsum or verum connective in the language (in the presence of equality these are definable).
Proposition 8 (Refinement).
Let
$\Gamma $
be a set of sentences and
$\phi $
a sentence from L. Then the following are equivalent:
-
(i)
. -
(ii)
$\Gamma \vdash \psi $
for every sentence
$\psi $
of the language
$L_{\Gamma }$
with
$\phi \vdash \psi $
. -
(iii)
$\Gamma \vdash \psi $
for every sentence
$\psi $
of the language
$L_{\Gamma } \cap L_{\phi }$
with
$\phi \vdash \psi $
.
Remark 9. The characterization in terms of consistency and its refinements all fail for the variation of Definition 1 where
$\mathfrak {A}' = \mathfrak {A}$
(although the direction
$(i) \implies (ii)$
in the characterization in terms of consistency still holds). This corresponding friendliness relation is denoted by
in the Appendix. If one works in a language
$L^-$
without equality, it is possible to use the counterexample in [Reference Makinson and Beziau15, p. 6] to see this (there
$\Gamma $
is the set of all first-order consequences of
$\forall x Px$
and
$\phi $
is the sentence
$\exists x \exists y (Rxy \wedge \neg Ryx)$
). If on the other hand, we are working in full L, that example no longer does the trick because
$\exists x \exists y (Rxy \wedge \neg Ryx)$
is not consistent with
$\exists x \forall y(x=y)$
while
$\forall x Px$
is, and we need to appeal to a more subtle one. The answer is given using non-resplendent structures. (For the theory of resplendent structures the reader can consult [Reference Barwise and Schilpf4, Reference Hodges9, Reference Kossak12].) A structure
$\mathfrak {A}$
is resplendent if all existential second-order formulas, that is, formulas of the form
$\exists R \phi (R)$
where
$\phi $
is a first-order formula, that are true in some elementary extensions of
$\mathfrak {A}$
, are already true in
$\mathfrak {A}$
. We will borrow the following nice example from [Reference Kossak12]:
$\text {Th}(\mathbb {Z}, +, \times )$
, the complete theory of the structure
$(\mathbb {Z}, +, \times )$
, is not friendly to the sentence
$$ \begin{align*}\phi(I) := \exists x I(x) \wedge \exists x \neg I(x) \wedge \forall x \forall y (x+1=y \rightarrow (I(x) \leftrightarrow I(y))),\end{align*} $$
as the structure
$(\mathbb {Z}, +, \times )$
does not have any proper subset of its universe closed under successors and predecessors. On the other hand, every set of sentences of the language of
$\text {Th}(\mathbb {Z}, +, \times )$
consistent with
$\text {Th}(\mathbb {Z}, +, \times )$
is also consistent with
$\phi (I)$
as one can see by taking any proper elementary extension of
$(\mathbb {Z}, +, \times )$
.
Remark 10. However, if one restricts attention to resplendent models only, the version of
introduced in Definition 1 and
, which simply states the existence of an expansion, become equivalent. Clearly, if
in the second sense, then
in the sense of Definition 1 (any model is trivially an elementary extension of itself). On the other hand if
in the sense of Definition 1 then, for any resplendent model of
$\Gamma $
, if the elementary extension that witnesses this fact can be expanded to a model of
$\phi $
, then, by resplendence, the original model already can be expanded in such a way. A useful feature of resplendent structures is that any model can be elementarily embedded in a resplendent structure of the same cardinality [Reference Barwise and Schilpf4, claim (i), p. 534]. Now let us show that if
when considering all models then
when restricting to resplendent models. Assume the sense of Definition 1 again that
and take a model
$\mathfrak {A}\models \Gamma $
witnessing this fact, so no elementary extension of it can be expanded to a model of
$\phi $
. But then there must be a resplendent elementary extension
$\mathfrak {B}$
of
$\mathfrak {A}$
such that the same occurs (for otherwise,
$\mathfrak {B}$
itself could already be expanded to a model of
$\phi $
contradicting our choice of
$\mathfrak {A}$
). Hence, if the
relation is defined on resplendent models alone, one can make
$\mathfrak {A} = \mathfrak {A}'$
in Definition 1 without loss of generality.
Remark 11.
is roughly the complement of a relation that was articulated by de Bouvère [Reference de Bouvère7] in the context of the theory of definition, to serve as a tool for showing the non-definability of a predicate P in a first-order theory. To bring out the connection, we state a certain instance of de Bouvère’s Lemma 1 in our notation. Let
$\Delta $
be a first-order theory and P a predicate of its language
$L=L_{\Delta }$
. Write
$L\setminus P$
for that language less P. Then a sufficient condition for P to be undefinable in
$Cn_{L\setminus P}(\Delta )$
(where this is the set of consequences of
$\Delta $
in the language
$L\setminus P$
) is that there is a model of
$Cn_{L\setminus P}(\Delta )$
for the language
$L\setminus P$
that cannot be extended to a model of
$\Delta $
by giving an interpretation of P. In the case that
$\Delta $
is a singleton
$\{\phi \}$
the condition becomes: there is a model of
$Cn_{L\setminus P}(\phi )$
that cannot be extended to a model of
$\phi $
by giving an interpretation of P; in other words, it requires that
. In this way, a special case of de Bouvère’s condition (the one where
$\Delta $
is a singleton) requires that a certain pair is not in the relation
.
Next we mention some more properties that carry over from the propositional case:
Proposition 12. Let
$\Gamma , \Delta $
be sets of sentences and
$\phi , \psi $
sentences from L. Then:
-
(i) (Right weakening) :
only if
. -
(ii) (Singleton cumulative transitivity) : Whenever
and
we have that
. -
(iii) (Local left strengthening) : Suppose that
$L_{\Delta } \subseteq L_{\Gamma }$
. Then
only if
. -
(iv) (Local left equivalence) : Suppose that
$L_{\Delta } \subseteq L_{\Gamma }$
. Then
and
$\Gamma \dashv \vdash \Delta $
only if
. -
(v) (Local monotony) : Suppose that
$L_{\Delta } \subseteq L_{\Gamma }$
,
and
$\Gamma \subseteq \Delta $
only if
. -
(vi) (Local disjunction in the premisses) : Suppose
$L_{\psi } \subseteq L_{\Gamma ,\phi } $
and
$L_{\phi } \subseteq L_{\Gamma ,\psi } $
. Then
and
together imply
. -
(vii) (Proof by exhaustion):
and
together imply
.
Proof. (i) follows from the definition, while (iv) and (v) are immediate consequences of (iii) and (vii) is immediate from (vi). The verifications for the remainder are essentially the same as for the propositional case, as set out in [Reference Makinson and Beziau15], but we run through them for the reader’s convenience. Suppose that
and
. Take any model
$\mathfrak {A} \models \Gamma $
for the language
$L_{\Gamma }$
. By hypothesis, there is a model
$\mathfrak {A}'$
for the same language such that both
$\mathfrak {A}\preceq _{L_{\Gamma }} \mathfrak {A}'$
and
$\mathfrak {A}'$
can be expanded to a model
$\mathfrak {A}"$
for the language
$L_{\Gamma ,\phi }$
for which
$\mathfrak {A}"\models \phi $
. But now, by hypothesis again, one may find
$\mathfrak {A}"'$
with
$\mathfrak {A}"\preceq _{L_{\Gamma ,\phi }} \mathfrak {A}"'$
(and hence
$\mathfrak {A}\preceq _{L_{\Gamma }} (\mathfrak {A}"'\upharpoonright L_{\Gamma }$
)) such that
$ \mathfrak {A}"'$
(and hence
$(\mathfrak {A}"'\upharpoonright L_{\Gamma }$
)) can be expanded to a model
$ \mathfrak {A}"" \models \psi $
.
(iii): Assume that
$L_{\Delta } \subseteq L_{\Gamma }$
and
. Take any model
$\mathfrak {A} \models \Delta $
for the language
$L_{\Delta }$
. By hypothesis, since
$ \Delta \vdash \Gamma $
, any expansion
$\mathfrak {A}' $
of
$\mathfrak {A}$
to
$L_{\Gamma }$
must be such that
$\mathfrak {A}' \models \Gamma $
. But then, since
, we have that there is a model
$\mathfrak {A}"$
for the same language such that
$\mathfrak {A}'\preceq _{L_{\Gamma }} \mathfrak {A}"$
and, furthermore,
$\mathfrak {A}"$
can be expanded to a model
$\mathfrak {A}"'$
for the language
$L_{\Gamma ,\phi }$
for which
$\mathfrak {A}"'\models \phi $
. So
$\mathfrak {A} = (\mathfrak {A}' \upharpoonright L_{\Delta }) \preceq _{L_{\Delta }} ( \mathfrak {A}"\upharpoonright L_{\Delta })$
, and we have that
as desired.
(vi): Suppose that
, so there is a model
$\mathfrak {A}$
for the language
$L_{\Gamma ,\phi ,\psi }$
such that
$\mathfrak {A}\models \Gamma $
and
$\mathfrak {A}\models \phi \vee \psi $
such that there is no model
$\mathfrak {A}'$
for
$L_{\Gamma ,\phi ,\psi }$
such that both
$\mathfrak {A}\preceq _{L_{\Gamma ,\phi ,\psi }} \mathfrak {A}'$
and
$\mathfrak {A}'$
can be expanded to a model
$\mathfrak {A}"$
for the language
$L_{\Gamma ,\phi ,\psi ,\chi }$
for which
$\mathfrak {A}"\models \chi $
. By the hypotheses,
$L_{\Gamma ,\phi ,\psi } = L_{\Gamma ,\phi } = L_{\Gamma , \psi }$
, so either
$\mathfrak {A}\models \phi $
or
$ \mathfrak {A}\models \psi $
, and thus either
or
as desired.
3 First-order discontinuities
We know from [Reference Makinson and Beziau15] that compactness holds in quite a strong form in the propositional context. But it fails in the first-order case because we are requiring, in Definition 1 of first-order friendliness, that the model
$\mathfrak {A}"$
has the same domain as the model
$\mathfrak {A}'$
(which in turn is elementarily equivalent to
$\mathfrak {A}$
). This permits the construction of a counterexample to compactness as follows.
Proposition 13 (Compactness fails for
).
There is a set
$\Gamma $
of sentences such that
but for no finite set
$\Gamma _0\subseteq \Gamma $
do we have that
.
Proof. Consider the first-order theory and sentence
$$ \begin{align*}\Gamma := \{\text{`there are at least } n \text{ elements'} \ | \ n> 0 \}\end{align*} $$
$$ \begin{align*} \phi := \text{`the relation } R \text{ is an injective but not surjective total mapping on the domain'}. \end{align*} $$
It is easy to see that
: any model
$\mathfrak {A}\models \Gamma $
has to be infinite, so it can clearly be expanded to a model of
$\phi $
(which simply restates Dedekind’s definition of infinity). Assume that
$\Gamma _0\subseteq \Gamma $
is finite, and suppose for a contradiction that
, so there is a model
$\mathfrak {A}'$
for the language
$L_{\Gamma _0}$
such that
$\mathfrak {A}\preceq _{L_{\Gamma _0}} \mathfrak {A}'$
(observe that since
$\mathfrak {A}$
is finite and we are assuming that the language contains equality,
$\mathfrak {A}'$
must be the same size) and, furthermore,
$\mathfrak {A}'$
can be expanded to a model
$\mathfrak {A}"$
for the language
$L_{\Gamma _0,\phi }$
for which
$\mathfrak {A}"\models \phi $
, but this is a contradiction as it would imply that
$\mathfrak {A}'$
is infinite.
Remark 14. The argument for Proposition 13 works equally well for the variant of Definition 1 where
$\mathfrak {A} = \mathfrak {A}'$
. On the other hand it does not work when the language lacks equality; indeed, in that case we have a quite trivial (and rather uninteresting) form of compactness. Let
$\phi $
be a sentence and
$\Gamma $
a set of sentences in a language
$L^-$
where the superscript means that the language does not contain equality. If
, either
$\phi $
is inconsistent or not. If the first,
$\Gamma $
itself must be inconsistent, so by compactness for
$\vdash $
, there is a finite subset
$\Gamma _0\subseteq \Gamma $
that is inconsistent. Trivially,
in this case. If, on the other hand,
$\phi $
is consistent we have that
. To see this take any model
$\mathfrak {A}$
of
$\emptyset $
, that is, any set A, since
$\emptyset $
is a theory in the empty language, and consider a model
$\mathfrak {B}\models \phi $
. Either
$|B| \leq |A|$
or
$|A| \leq |B|$
. If the former, then by a known result of first-order logic without equality [Reference Bridge5, lemma 2.24] or [Reference Ackermann1, chap. IV, sec. 1] (stated more generally in [Reference Badia, Caicedo and Noguera3, lemma 3]), there is a model
$\mathfrak {A}" \models \phi $
such that
$|B| \leq |A"| =|A|$
. Hence, letting the set
$A"$
be considered as a model
$\mathfrak {A}'$
for
$\emptyset $
we have that it is a trivial (since the language is empty) elementary extension of
$\mathfrak {A}$
, so we are done. If, on the other hand, we have the latter possibility, then there is an injection from A into B, and hence letting
$\mathfrak {A}'= A$
and
$\mathfrak {A}"=\mathfrak {B}$
we get the models needed to witness
. Incidentally, this is a simple and naturally arising example of proof by cases using an undecidable criterion (whether
$\phi $
is consistent or not) for the two cases (cf.[Reference Kleene11]).
We can also construct a counter-example to interpolation.
Proposition 15 (Interpolation fails for the relation
).
There is a set of sentences
$\Gamma $
and sentence
$\phi $
such that
, but there is no interpolant
$\psi $
in the language
$L_{\Gamma } \cap L_{\phi }$
such that
and
.
Proof. Consider the theory
$\Gamma $
and sentence
$\phi $
in the proof of Proposition 13. We know that
and
$\Gamma $
is consistent. However, if there is an interpolant
$\psi $
which uses equality in the language
$L_{\Gamma } \cap L_{\phi }$
(which is just the pure language of equality) such that
and
, this means that
$\psi $
only has infinite models. To see this, suppose that
and
$\mathfrak {A} \models \psi $
where
$\mathfrak {A}$
is a model for the pure language of equality. It follows that there is a model
$\mathfrak {A}'$
for the same language such that
$\mathfrak {A}\preceq _{L_{\psi }} \mathfrak {A}'$
and that, furthermore,
$\mathfrak {A}'$
can be expanded to a model
$\mathfrak {A}"$
for the language
$L_{\psi ,\phi }$
for which
$\mathfrak {A}"\models \phi $
, and hence
$\mathfrak {A}'$
has to be infinite (and then
$\mathfrak {A}$
is infinite too as the pure-equality sentences ‘there are at least n elements’ are all true in
$\mathfrak {A}'$
and thus in
$\mathfrak {A}$
since
$\mathfrak {A}\preceq _{L_{\psi }} \mathfrak {A}'$
). Since
$\Gamma $
is consistent and
, then
$\psi $
clearly has a model, and hence we obtain a contradiction with [Reference Ash2, theorem 1] which implies that
$\psi $
has a finite model since it is a sentence in the pure language of equality.
Remark 16. This counterexample to interpolation also works for the variant of Definition 1 where
$\mathfrak {A} = \mathfrak {A}'$
. We note that if the language lacks equality but has a zero-ary
$\bot $
connective, then the counter-example in Proposition 15 is no longer available and in fact interpolation then holds in a rather trivial way, as can be shown by essentially the same kind of argument as in Remark 14 (putting
$\bot $
in place of
$\Gamma _0$
in the case that
$\Gamma $
is inconsistent, and putting
$\top $
in place of the empty set when
$\phi $
is consistent).
We have seen the failure of interpolation, so what about the Beth definability theorem? As it is well-known, interpolation gives Beth definability in first-order logic (the other direction is false [Reference Jensen10] in general when considering abstract logics in the sense of Lindström [Reference Lindström13]). Thus even though we have disproved the former it is still reasonable to wonder about the latter—and it comes out true.
Proposition 17 (Beth definability property for
).
Let P be an n-ary predicate symbol not in language L (with or without equality),
$\Gamma $
a set of sentences where
$L_{\Gamma } = L \cup \{P\}$
and
$\mathfrak {A}$
a model for L. Then the following are equivalent:
-
(i) If
$(\mathfrak {A}, B) \models \Gamma $
and
$(\mathfrak {A}, C) \models \Gamma $
(where
$(\mathfrak {A}, B), (\mathfrak {A}, C)$
are the expansions of
$\mathfrak {A}$
obtained by interpreting the predicate P as the n-ary relations B and C, respectively), then
$B=C$
. -
(ii) There is a formula
$\psi (\overline {x})$
of L such that -
(iii) There is a formula
$\psi (\overline {x})$
of L such that
$$ \begin{align*}\Gamma \vdash \forall \overline{x} (\psi (\overline{x}) \leftrightarrow P (\overline{x})).\end{align*} $$
Proof. (i) is equivalent to (iii) by the Beth definability theorem, and (iii) is equivalent to (ii) as an immediate consequence of Proposition 3 (which does not depend on the presence of equality in the language).
Remark 18. The argument for the Beth definability property works as well for the variant of Definition 1 where
$\mathfrak {A} = \mathfrak {A}'$
. On the other hand, for both definitions, if in the version of Beth definability that we have given for
we weaken the requirement to
$L_{\Gamma } \subseteq L \cup \{P\}$
, the implication
$(ii) \implies (iii)$
fails. This is because if P does not appear in
$\Gamma $
then
$(ii)$
holds trivially for any formula
$\psi $
of L whilst
$(iii)$
holds only when
$\Gamma $
is inconsistent.
4 Non-axiomatizability
Even though Proposition 13 implies that there can be no strongly complete (and sound) finitary axiomatization of
(as the existence of such an axiomatization would imply compactness for the consequence relation), it still makes sense to ask whether a weakly complete finitary axiomatization exists. It turns out that for predicate calculus this is not possible either. In Proposition 19 and its Corollary it is assumed that the language has countably many predicates and function letters of whatever arities are needed for the Church–Turing theorem to hold.
In what follows, as in the usual predicate calculus, we always assume that we have as rich a vocabulary as necessary, that is, we have a countable list of predicate and function symbols of whatever arity we might wish.
Proposition 19. The set of formulas
$\phi $
in predicate calculus without equality for which
is not recursively enumerable.
Proof. First recall that the set of validities of predicate calculus without equality is not recursive by the Church–Turing theorem [Reference Kleene11, theorem 54 of sec. 76]. Thus the set of formulas without equality that are satisfiable cannot be recursively enumerable since the set of validities is recursively enumerable. We then use Proposition 5 to get the result.
Corollary 20. The set of formulas
$\phi $
in predicate calculus with equality for which
is not recursively enumerable.
Proof. Clearly, any effective enumeration of the formulae
$\phi $
with equality such that
, can be transformed into an effective enumeration of those among them that lack equality, contrary to Proposition 19.
Remark 21. It is natural to ask what happens if we have an empty vocabulary and the pure language of equality. In this case, we have recursive enumerability thanks to Proposition 6.
5 Open questions
There are many directions for further research. One could look for other relations between models that make sense as specifications of the relation between
$\mathfrak {A}$
and
$\mathfrak {A}'$
; back-and-forth equivalence is mentioned in the Appendix as a possibility. In the context of equality-free logic, one might also consider variants using the relation of weak isomorphism from [Reference Badia, Caicedo and Noguera3]. Finally, one might go beyond the context of classical logic to explore intuitionistic or modal contexts, in which further specifications of the relation between
$\mathfrak {A}$
and
$\mathfrak {A}'$
are suggested by bisimulation and similar notions.
Appendix
A fairly general format for variants of Definition 1 in first-order contexts is as follows:
-
Say that a set
$\Gamma $
of sentences is friendly
$^{\mathbf {R}}_{\mathbf {S}}$
(in symbols
) to a formula
$\phi $
iff for every model
$\mathfrak {A}$
for the language
$L_{\Gamma }$
, if
$\mathfrak {A}$
satisfies
$\Gamma $
then there are models
$\mathfrak {A}'$
,
$\mathfrak {A}"$
for languages
$L_{\Gamma }$
,
$L_{\Gamma , \phi }$
, respectively with
$(\mathfrak {A}, \mathfrak {A}') \in {\mathbf R}$
,
$(\mathfrak {A}', \mathfrak {A}") \in \mathbf {S}$
and
$\mathfrak {A}"$
satisfies both
$\Gamma $
and
$\phi $
.
Our guiding idea is that R is some kind of relation of being ‘…is essentially the same as …’, and S one of ‘…can be enlarged to …’. Various definitions emerge from different ways of specifying the two relations. There are at least four interesting ways of filling in for R, and another three for S. We choose R to cover relations at least as strong as elementary equivalence bearing in mind the remark of Angus Macintyre that in the model theory of first-order logic ‘elementary equivalence is the most fundamental concept […] It is the analogue of isomorphism in algebra’ [Reference Macintyre and Barwise14, p. 140]. Here are some options for R:
$(\mathfrak {A}, \mathfrak {A}') \in {\mathbf {R}}$
iff:
-
R
$_1$
:
$\mathfrak {A} = \mathfrak {A}'$
. -
R
$_2$
:
$\mathfrak {A} $
is isomorphic to
$\mathfrak {A}'$
. -
R
$_3$
:
$\mathfrak {A} $
can be elementarily embedded into
$\mathfrak {A}'$
. -
R
$_4$
:
$\mathfrak {A} $
is elementarily equivalent to
$\mathfrak {A}'$
.
Clearly each option
${\mathbf {R}}_i$
implies
${\mathbf {R}}_{i+1}$
. Our Definition 1 uses
${\mathbf {R}}_3$
. Another example, which we have not discussed, is back-and-forth equivalence in terms of Ehrenfeucht–Fraïssé games [Reference Hodges9, corollary 3.3.3] but for simplicity we will leave it out of our analysis, which is by no means complete.
As regards ways of filling S, the situation is more subtle. One could think of S as a being described by a triple
$\langle D_i, C, P_j \rangle $
where
$i,j \in \{1,2\}$
where:
-
$D_1$
says that
$A' = A"$
.
-
$D_2$
says that
$A' \subseteq A"$
.
-
C says that for every constant symbol occurring in
$\Gamma $
, its value in
$\mathfrak {A}"$
is the same as its value in
$\mathfrak {A}'$
. -
$P_1$
says that for every predicate symbol occurring in
$\Gamma $
, its value in
$\mathfrak {A}"$
is the same as its value in
$\mathfrak {A}'$
.
-
$P_2$
says that for every predicate symbol occurring in
$\Gamma $
, its value in
$\mathfrak {A}"$
intersected with the appropriate power of
$A'$
, is the same as its value in
$\mathfrak {A}'$
.
Clearly,
$D_1$
implies
$D_2$
and when
$D_1$
holds then
$P_1$
is equivalent to
$P_2$
. So we get three ways of filling in for S:
$\langle D_1, C, P_1 \rangle $
is equivalent to
$\langle D_1, C, P_2 \rangle $
which in turn implies
$\langle D_2, C, P_1 \rangle $
which implies
$\langle D_2, C, P_2 \rangle $
. That is, we are left with three possibilities:
-
S
$_1$
given by
$\langle D_1, C, P_1 \rangle $
, -
S
$_2$
given by
$\langle D_2, C, P_1 \rangle $
, and -
S
$_3$
given by
$\langle D_2, C, P_2 \rangle $
.
Definition 1 uses specification S
$_1$
, the strongest in this list, so the relation defined is
while a variant of it that is mentioned from time to time in the main text is
.
Remark 22. Before continuing, we reflect on the three options S
$_i$
. Clearly, S
$_1$
tells us that
$\mathfrak {A}' = (\mathfrak {A}" \upharpoonright L_{\Gamma })$
. In contrast, S
$_2$
tells us that
$\mathfrak {A}' \subseteq (\mathfrak {A}" \upharpoonright L_{\Gamma })$
, that is,
$\mathfrak {A}'$
is a submodel of
$(\mathfrak {A}" \upharpoonright L_{\Gamma })$
and, furthermore, it is a pure submodel [Reference Hodges9, p. 528] in the equality-free language
$L_{\Gamma }^-$
in the sense that any primitive positive existential formula of
$L_{\Gamma }^-$
(i.e., formula of the form
$\exists \overline {y} \phi (\overline {y})$
where
$\phi (\overline {y})$
is a conjunction of atomic formulas, excluding identities) that is satisfied in
$(\mathfrak {A}" \upharpoonright L_{\Gamma })$
by a sequence of elements from
$\mathfrak {A}'$
must be satisfied in
$\mathfrak {A}'$
(equivalently, all negations of existential primitive positive formulas satisfied in
$\mathfrak {A}'$
are satisfied in
$(\mathfrak {A}" \upharpoonright L_{\Gamma })$
). On the other hand, S
$_3$
only tells us that
$\mathfrak {A}' \subseteq (\mathfrak {A}" \upharpoonright L_{\Gamma })$
.
Proposition 23. Let R
$_i$
(
$i\in \{1,2,3, 4\}$
) and S
$_j$
(
$j\in \{1,2,3\}$
) be as above. Then:
-
(i)
for
$j \in \{1,2,3\}$
,
, and -
(ii)
for
$i \in \{1,2,3,4\}$
.
Proof. (i): Clearly, all left-in-right inclusions hold since each
${\mathbf {R}}_i \subseteq {\mathbf {R}}_{i+1}$
. The converse inclusion
is easy to see because we can isomorphically copy
$\mathfrak {A}"$
as an expansion of
$\mathfrak {A}$
itself. Now we wish to show that
. Suppose that
; we want to show that
(which is just what we have called
until now). Let then
$\mathfrak {A} \models \Gamma $
be an arbitrary model for
$L_{\Gamma }$
, so by the assumption
, there is a model
$\mathfrak {A}'\equiv _{L_{\Gamma }} \mathfrak {A}$
which can be expanded to a model
$\mathfrak {A}"$
for the language
$L_{\Gamma , \phi }$
with
$\mathfrak {A}"\models \phi $
. In order to establish that
it suffices to show that
$\text {eldiag}(\mathfrak {A}) \cup \{\phi \}$
is consistent. Suppose otherwise, that is, for some finite
$T \subseteq \text {eldiag}(\mathfrak {A})$
, the theory
$T \cup \{\phi \}$
is not consistent. Then
$\phi \vdash \neg \bigwedge T$
, but then since the diagram constants in T are all new to
$L_{\Gamma , \phi }$
,
$\phi \vdash \forall \overline {x}\neg \bigwedge T^*$
by [Reference Hodges9, Lemma 2.3.2] where
$T^*$
is the result of replacing in every sentence in T the new constants by new variables. Then
$\mathfrak {A}"\models \forall \overline {x}\neg \bigwedge T^*$
so
$\mathfrak {A}'\models \forall \overline {x}\neg \bigwedge T^*$
and since
$\mathfrak {A}' \equiv _{L_{\Gamma }} \mathfrak {A}$
, we have that
$\mathfrak {A}\models \forall \overline {x}\neg \bigwedge T^*$
. On the other hand, since
$(\mathfrak {A}, \overline {a}) \models T \subseteq \text {eldiag}(\mathfrak {A})$
(where
$\overline {a}$
is a list of fresh names for the elements of
$\mathfrak {A}$
), we have
$\mathfrak {A}\models \exists \overline {x} \bigwedge T^*$
, giving us a contradiction.
(ii): This is immediate by the observations in Remark 22 on the connections between S
$_1$
, S
$_2$
, and S
$_3$
.
Thus it would be possible to reformulate Definition 1 equivalently with the attractively symmetric R
$_4$
in place of the non-symmetric R
$_3$
. As mentioned in the Introduction, the reason is that our proofs using Robinson diagrams (for Propositions 4 and 7) are more easily carried out in terms of R
$_3$
than R
$_4$
.
However, some of the relations that we have just introduced are, in a certain respect, anomalous. For, as mentioned in the Introduction, in both propositional and first-order contexts the friendliness relation is motivated by the idea that it is a
$\forall \exists $
counterpart of a
$\forall \forall $
definition of classical consequence. However, in the first-order context, it turns out that for the relations
(
$j=2, 3$
), the
$\forall \forall $
counterpart of the
$\forall \exists $
relation of
is not classical consequence. To be precise:
Proposition 24. For each choice of
${\mathbf {R}}_i$
(
$1\leq i \leq 4$
), the following two conditions are equivalent for every sentence
$\phi $
and set
$\Gamma $
of sentences:
-
(1)
$\Gamma \vdash \phi $
. -
(2) For every model
$\mathfrak {A}$
for the language
$L_{\Gamma }$
, if
$\mathfrak {A}$
satisfies
$\Gamma $
then
$\mathfrak {A}"$
satisfies both
$\Gamma $
and
$\phi $
for all models
$\mathfrak {A}'$
,
$\mathfrak {A}"$
for languages
$L_{\Gamma }$
,
$L_{\Gamma , \phi }$
, respectively with
$(\mathfrak {A}, \mathfrak {A}') \in {\mathbf {R}}_i$
,
$(\mathfrak {A}', \mathfrak {A}") \in \mathbf {S}_j$
for
$j=1$
.
On the other hand, the implication
$(1)\implies (2)$
fails for all
${\mathbf {R}}_i$
(
$1\leq i \leq 4$
), when
${2\leq j \leq 3}$
.
Proof. We will split this proof in cases, depending on what
is.
For the case
, assume that (1) and consider a model
$\mathfrak {A}$
for the language
$L_{\Gamma }$
such that
$\mathfrak {A} \models \Gamma $
. Furthermore, suppose that
$(\mathfrak {A}, \mathfrak {A}') \in {\mathbf {R}}_3$
and
$(\mathfrak {A}', \mathfrak {A}") \in \mathbf {S}_1$
. Since
$(\mathfrak {A}, \mathfrak {A}') \in {\mathbf {R}}_3$
, also
$\mathfrak {A}' \models \Gamma $
and thus
$\mathfrak {A}" \models \Gamma $
since
$(\mathfrak {A}', \mathfrak {A}") \in \mathbf {S}_1$
. This immediately entails that
$\mathfrak {A}" \models \phi $
by the assumption (1). Conversely, assuming (2), we may let
$\mathfrak {A}'$
,
$\mathfrak {A}"$
be
$\mathfrak {A}$
and any expansion of
$\mathfrak {A}$
to
$L_{\Gamma , \phi }$
, respectively, to get that
$\Gamma \vdash \phi $
. Cases
are established similarly to
.
For the second part of the proposition, let us do the case of
as an example. Let the vocabulary of the language be empty and consider a model
$\mathfrak {A}=\mathfrak {A}'$
(in this case just a set) of size
$7$
(any finite number will do the trick). Then let
$\mathfrak {A}"$
be simply an infinite model. Now the sentence
$\phi $
that says there are at most seven objects is true in
$\mathfrak {A}$
but false in
$\mathfrak {A}"$
. Trivially
$\phi \vdash \phi $
, so this shows that (1) does not imply (2).
Table 1 collects the main facts about the properties of those of the friendliness relations that we have defined, that are not anomalous in the sense described above. Almost all of the verifications have already been carried out in the text, as specified in the table, with the remainder in Remark 25.
Table 1 Summary of properties of friendliness and sub-friendliness
Table 2 Summary of properties for languages with
$\bot $
but without equality
Remark 25. Supraclassicality (Proposition 2) trivially holds for all the inference relations just defined because we can always take
$\mathfrak {A}=\mathfrak {A}'=\mathfrak {A}"$
. Furthermore, for
we get the first reduction case but not the second. For the First Reduction Case we simply use Proposition 23(i) and Proposition 3 itself. For the Second Reduction Case, we have that
only if
$\Gamma \not \vdash \neg \phi $
, but not the converse. If
, then by Proposition 23(i) and Proposition 4,
$\Gamma \not \vdash \neg \phi $
. To give a counterexample for the converse let
$\Gamma $
be ‘true arithmetic’, that is, the theory of the structure of the natural numbers
$\mathbb {N}$
.
$\Gamma $
is complete and has a model
$\mathfrak {A}$
with a non-standard number c. Let
$\phi $
be the sentence that says ‘f is a non-surjective injection from the elements that come before c in the order
$<$
into themselves’. Since c is a non-standard number it must have infinitely many elements that come before it in
$\mathfrak {A}$
and hence
$\mathfrak {A}$
can be expanded to a model of
$\phi $
. This tells us that
$\Gamma \not \vdash \neg \phi $
. On the other hand, clearly the standard model of arithmetic (a model of
$\Gamma $
by definition) cannot be expanded to a model of
$\phi $
, and thus
.
Now let us conclude with some remarks on equality-free logic with a falsum constant
$\bot $
. Naturally, the expressive power of these languages is reduced at the level of classes of models that one can axiomatize, but from the point of view of theories one can introduce equality by special axioms as a congruence relation on the vocabulary in question. In various places of the present paper (including Proposition 23) we used the method of diagrams, but in the equality-free context one has to be more careful [Reference Dellunde8]. Since the diagram in this setting does not contain equality formulas anymore, we cannot guarantee the construction of an embedding as we cannot define the obvious injective mapping. Thus it makes sense to replace the notion of elementary embedding in the above discussion (including Definition 1) by that of an ‘elementary mapping’ in the style of [Reference Dellunde8, proposition 2.8]. Once this modification is carried out, Table 2 collects the main facts that we are aware of for variants of Definition 1 in an equality-free context with the presence of falsum
$\bot $
, as well as one open question denoted by a question mark (observe that in this case the counterexample in Remark 25 does not do the trick as it uses equality). The only thing we omit in Table 2 is the information in Proposition 19. We put as references the corresponding results for the original version of Definition 1 because the proofs are essentially a verbatim repetition of what is already presented.
On this topic of equality-free logic we wish to leave two questions to be tackled in further research (as they do not seem to be easily answerable by the methods in the present paper):
Problem 26. When equality is available, does Definition 1 yield the same result (in terms of logical properties) with ‘elementary mapping’ (in the sense of equality-free logic) in place of ‘elementary embedding’?
Acknowledgements
We are deeply indebted to an anonymous reviewer who provided very detailed and helpful comments identifying a number of problems in earlier versions of the article.
Funding
Badia is supported by the Australian Research Council grant DE220100544.
Open access
