[current]376pt680pt

# Logic families

Hajnal Andréka and Zalán Gyenis and István Németi∗ and Ildikó Sain∗ Alfréd
Rényi Institute of Mathematics, BudapestJagiellonian University, Kraków

###### Abstract

A logic family is a bunch of logics that belong together in some way. First-
order logic is one of the examples. Logics organized into a structure occur in
abstract model theory, institution theory and in algebraic logic. Logic
families play a role in adopting methods for investigating sentential logics
to first-order like logics. We thoroughly discuss the notion of logic families
as defined in the recent Universal Algebraic Logic book.

Keywords: Logics, general logics, universal algebraic logic, abstract
algebraic logic, abstract model theory, institutions, Lindenbaum–Tarski
formula algebra, tautological congruence, conditionally free algebra, free
product of algebras.

##  1 Introduction

This paper is about a notion of a family of logics. A family of logics is a
bunch of logics that belong together in some way. A typical example is first-
order logic. One defines first-order logic by first specifying the similarity
type and after this one defines first-order logic of that similarity type.
Thus, the similarity type is a parameter in defining first-order logic. The
present paper contains a thorough classical style discussion of a notion of
logic families which focuses on the set of atomic formulas being a parameter.

Several notions for logic families occur in the logic literature, e.g., [4],
[11], [20], [1]. In all these, one relies on a general notion of logics, and
then a logic family is a class of such logics organized into some structure.
Before talking about the motivation for logic families, let us begin with
saying some words about their constituents. Below we list some situations
which call for a general notion of a logic.

—– Often, one says that one property of a logic follows from another one. For
example, it is widely known that there are close connections between Craig’s
interpolation theorem, Robinson’s consistency theorem and Beth’s definability
theorem in first-order logic (e.g., one can prove one theorem from the other).
However, it is just three facts of mathematics that these properties hold for
first-order logic, one needs to give meaning to statements concerning their
relationship.

—– The starting point of algebraic logic is the discovery that in many cases,
a natural logical property corresponds in some way to a natural algebraic
property [25]. For making such correspondences meaningful, one needs a general
notion of logics.

—– The main aim of abstract model theory was to find a useful extension of
first-order logic: one which is stronger while manageable and expressive [4].
For such an endeavour one needs a general notion of logics among which one
wants to select a good one.

—– In computing theory, especially in formal specification theory, there was
an explosion of formal logical systems used, and so there was a need for a
uniform treatment of specification concepts. Institution Theory was created to
fulfill this need, but it reaches much further, it is an axiomatic treatment
of classical and non-classical model theories.111See Goguen-Burstall [16],
Diaconescu [11], [12].

As seen from the above examples, even those logicians for whom first-order
logic is the one and only may use a general notion of logics in order to make
ideas about first-order logic meaningful. Let us return to logic families.

In Abstract Model Theory, families of logics are used for doing away with
variables.222See [4]. Papers using the framework of Abstract Model Theory are,
e.g., [23], [21]. Institution Theory relies on a general notion of logics
$\langle F,M,\vDash\rangle$ where $F$ is the set of formulas, $M$ is the class
of models and $\vDash$ is the validity relation between them. An institution
is a class of such logics organized into a category $\operatorname{Sig}$.
Thus, the notion of logic family is central in Institution Theory.333See [11],
[26], [28]. Abstract Algebraic Logic and Universal Algebraic Logic are two
branches of Algebraic Logic that deal with general notions of logic. Both grew
out of, and was influenced by, Alfred Tarski’s work. The first one
concentrates on sentential logics while the second concentrates more on
predicate-like logics. However, their methods are very similar to each
other.444See Blok-Pigozzi [8], Font [14], Font-Jansana [15], and [1]. One
benefit of logic families in these branches is aesthetic: the cardinality of
the set of formulas often shows up in theorems about logics, but this
cardinality has no significant meaning. By using logic families instead of
logics, the corresponding theorems can do away with these cardinalities.
Besides this, there are theorems in which the use of logic families is
essential. For example, [1, Theorem 4.3.44] says that a logic family has the
weak Beth definability property if and only if in its counterpart category the
class of maximal elements generates the whole category by limits. In the
counterpart category, all members of the logic family are taken into account
and being maximal here cannot be expressed by using single logics instead of
the whole family.

The recent book Universal Algebraic Logic [1] aims at presenting the most
important theorems and methods of Universal Algebraic Logic. The key feature
of logics treated in Abstract Algebraic Logic is that they are
substitutional555The word structural is used in Abstract Algebraic Logic, see,
e.g., [8], [10], [14]. which means that the atomic formulas do not carry any
other information than how many of them are there. First-order logic, clearly,
is not substitutional. Yet, most of the methods of Abstract Algebraic Logic
can be applied to first-order logic, after some modifications. Two moves are
crucial in these modifications. One move is generalizing the notion of being
substitutional to being conditionally substitutional, the other move is
refining the notion of a logic family666This notion is called “general logic”
in [1], [2], Font-Jansana [15], Hoogland [20]. that is used in Abstract
Algebraic Logic. Thanks to these two moves, the algebraic methodology á la [1]
can be directly applied to first-order logic. Thus the definition of a logic
family in [1] is important in moving from sentential logics to predicate-like
ones. It may deserve a thorough investigation.

The content of this paper is an addition to [1] while it is self-contained. We
expand and explain some features of the definition of logic families. We carry
on a classical style discussion of [1, Definition 3.3.27]: we simplify it, we
present several equivalent statements for the items occurring in it, we
present weaker and stronger statements for these items; we show that under
some hypotheses, some of the distinct statements become equivalent etc. We
hope that these investigations give insight concerning the definition of a
logic family.

The structure of the paper is as follows.

In section 2, we briefly introduce our formal notion of a logic alongside with
some of its basic properties we will need in the paper. We also introduce
classical propositional and first-order logics in this framework.

In section 3, we define two characteristic subclasses of logics. In the first
class, atomic formulas can be replaced (substituted) with any other formulas
without affecting meaning, in the second class, this can be done only with
formulas satisfying some conditions. Propositional logics usually fall into
the first class, while classical first-order logic is a typical example of the
second class.

Section 4 is the main part of the paper, it contains a detailed discussion of
the notion of logic families. Subsection 4.1 recalls the definition of a logic
family from [1], with slight modifications. This definition contains five
items (1)–(5). Of these, condition (4) is about union of signatures, it is the
one that needs most explanation. Subsection 4.1 contains a discussion of items
(1)-(3) and (5). Subsection 4.2 discusses condition (4) in the general case.
For showing the intuition behind (4), we present three consequently weaker
conditions (4a), (4b) and (4). Of these, (4a) is practically useless because
it almost never is satisfied (though, it reflects the intuition best), while
condition (4b) is equivalent to the condition used in [1, Def.3.3.27]. Theorem
4.3 lists six conditions of different characters all of which are equivalent
to (4b). Theorem 4.7 lists seven conditions that are equivalent to (4) and
analogous to the ones that characterize (4b). These theorems shed light on why
our (4) is weaker than (4b) of [1]. Subsection 4.3 investigates
characterizations that hold only for conditionally substitutional logic
families. These give a hint for why condition (4) may be more useful in the
definition than (4b). At the end of the subsection it is shown that the notion
of logic families is not restrictive among conditionally substitutional
logics: each conditionally substitutional logic is a member of some
conditionally substitutional logic family, while there is a logic that is
member of no logic family at all (Theorem 4.15).

Section 5 is also an important part of the paper. In this section we prove
that both classical propositional and first-order logics are members of
natural logic families. It may come as a surprise that the systems of finite-
variable fragments of first-order logic as defined in this subsection do not
satisfy condition (4) (Theorem 5.4).

##  2 Logics in a general setting

In this section, we briefly introduce the formal notion of a logic alongside
with some of its basic properties we will need in the paper. We also introduce
classical propositional and first-order logics in this framework.

###  2.1 Definition of a logic and two examples

In this subsection, we recall a general notion of logic from [1] and we cast
classical propositional and first-order logics as examples. Similar but
different definitions of a logic (or, formal system) can be found in, e.g.,
Blok-Pigozzi [8], Henkin-Monk-Tarski [19, section 5.6], Tarski-Givant [27,
section 1.6]. Reasons for defining such a notion can be found in the
introduction. What we define below is called in [1] a compositional logic
having connectives, see [1, Defs. 3.1.3, 3.3.1, 3.3.2]. There are some
differences though, we mention these in the discussion. For the intuition
behind the definition of a logic below we refer to [1, Sec. 3.1] and also to
the two examples that follow the definition.

######  2.1 Definition (logic).

By a logic we understand a tuple $\mathcal{L}=\langle
F,M,\operatorname{mng},\vDash\rangle$, where (i)–(iv) below hold.

  1. (i)

$F$, called the set of formulas, is the universe of a term-algebra777For the
definition of term-algebra see, e.g., [1, Def. 2.4.1]
$\mathfrak{F}(P,\operatorname{Cn})$, which is an absolutely free algebra over
$P$ in the type of $\operatorname{Cn}$. The domain of the type
$\operatorname{Cn}$ is called the set of logical connectives and $P$ is called
the set of atomic formulas. We also denote the set of logical connectives with
$\operatorname{Cn}$, and the algebra $\mathfrak{F}$ is many times referred to
as the formula algebra of $\mathcal{L}$.

  2. (ii)

$M$ is a class, called the class of models.

  3. (iii)

$\vDash\;\subseteq M\times F$ is a relation between models and formulas. It is
called the validity relation. We use the notation $\mathfrak{M}\vDash\varphi$
instead of $\langle\mathfrak{M},\varphi\rangle\in\;\vDash$.

  4. (iv)

$\operatorname{mng}$ is called the meaning function. It is a function with
domain $M\times F$ (we write $\operatorname{mng}_{\mathfrak{M}}(\varphi)$ in
place of $\operatorname{mng}(\mathfrak{M},\varphi)$) such that

     * •

$(\forall\varphi,\psi\in F)\;(\forall\mathfrak{M}\in
M)\;\big{(}\operatorname{mng}_{\mathfrak{M}}(\varphi)=\operatorname{mng}_{\mathfrak{M}}(\psi)\text{
and }\mathfrak{M}\vDash\varphi\big{)}\Longrightarrow\mathfrak{M}\vDash\psi$.

     * •

We assume _compositionality_ , that is, $\operatorname{mng}_{\mathfrak{M}}$ is
a homomorphism from the formula algebra $\mathfrak{F}$ to some algebra of type
$\operatorname{Cn}$.

$\square$

Many well-known logics can be cast in our framework, [1] contains numerous
examples. Throughout this paper we illustrate our definitions with two
examples only: classical propositional logic and first-order logic.

######  2.2 Example (Classical propositional logic
$\mathcal{C}\mathcal{P}\mathcal{L}$).

We define classical propositional logic $\mathcal{C}\mathcal{P}\mathcal{L}$ as
follows.

  * •

The set of logical connectives is $\\{\wedge,\neg,\bot\\}$, where $\wedge$ is
binary, $\neg$ is unary and $\bot$ is a constant; and $P$ is an arbitrary set
(of atomic propositions) containing no proper term written up with these
connectives888For the name proper term see the next subsection.. Then the set
$F_{C}$ of formulas is the universe of the corresponding term-algebra.

  * •

The models, elements of $M_{C}$, are functions $\mathfrak{M}:P\to\\{0,1\\}$
assigning $0$ (false) and $1$ (true) to each atomic proposition $p\in P$.

  * •

We extend any model $\mathfrak{M}:P\to\\{0,1\\}$ to the set of all formulas by

$\mathfrak{M}(\bot)=0,\quad\mathfrak{M}(\neg\varphi)=1-\mathfrak{M}(\varphi),\quad\mathfrak{M}(\varphi\wedge\psi)=\mathfrak{M}(\varphi)\cdot\mathfrak{M}(\psi).$
(1)

We let the meaning of a formula $\varphi$ in a model $\mathfrak{M}$ be
$\mathfrak{M}(\varphi)$, i.e.,
$\operatorname{mng}_{C}(\mathfrak{M},\varphi)=\mathfrak{M}(\varphi)$.

  * •

A formula is valid in a model iff its meaning is “true”, i.e.,
$\mathfrak{M}\vDash_{C}\varphi\Longleftrightarrow\mathfrak{M}(\varphi)=1$.

Thus classical propositional logic $\mathcal{C}\mathcal{P}\mathcal{L}$ in our
formalism is

$\mbox{$\mathcal{C}\mathcal{P}\mathcal{L}$}=\langle
F_{C},M_{C},\operatorname{mng}_{C},\vDash_{C}\rangle.$

Next we turn to first-order logic, one of the key examples of our framework.

######  2.3 Example (First-order logic
$\mbox{$\mathcal{F}\mathcal{O}\mathcal{L}$}=\mbox{$\mathcal{F}\mathcal{O}\mathcal{L}$}_{t}(V)$).

We formalize first-order logic of a non-empty relational similarity type $t$
using variables $V$ in the standard way, as follows. The set $P_{t}(V)$ of
atomic formulas is

$P_{t}(V)=\\{r(v_{1},\ldots,v_{{n}}):\;r\in\operatorname{dom}(t),\;t(r)=n,\;v_{1},\dots,v_{n}\in
V\\}.$ (2)

The set $F_{t}(V)$ of formulas is generated by $P_{t}(V)$ using the
connectives $\\{\wedge,\neg,\bot,\exists v,v=w:v,w\in V\\}$, where $\wedge$ is
binary, $\neg,\exists v$ are unary, and $v=w$ and $\bot$ are constants. Models
$\mathfrak{M}=\langle M,r^{\mathfrak{M}}\rangle_{r\in\operatorname{dom}(t)}$
and satisfaction $\vDash^{t}$ are defined in the usual manner see, e.g.,
Chang-Keisler [9, section 1.3], or Enderton [13, sections 2.0–2.3]. Finally,

$\displaystyle\operatorname{mng}_{\mathfrak{M}}(\varphi)=\\{h\in{}^{V}M:\mathfrak{M}\vDash\varphi[h]\\},$
(3)

where ${}^{V}M$ denotes the set of all functions from $V$ to $M$, and
$\mathfrak{M}\vDash\varphi[h]$ denotes that $\varphi$ is true in
$\mathfrak{M}$ under the evaluation $h$ of the variables. We define

$\displaystyle\mbox{$\mathcal{F}\mathcal{O}\mathcal{L}$}_{t}(V)=\langle
F_{t}(V),M_{t},\operatorname{mng}^{t},\vDash^{t}\rangle.$ (4)

We note that the pair $\langle t,V\rangle$ and the set $P_{t}(V)$ of atomic
formulas determine each other. _Classical first order logic_ is
$\mbox{$\mathcal{F}\mathcal{O}\mathcal{L}$}_{t}(V)$ where the set $V$ of
variables is infinite. When $V$ is finite,
$\mbox{$\mathcal{F}\mathcal{O}\mathcal{L}$}_{t}(V)$ is called a _finite-
variable fragment of first-order logic_. We will see that these finite-
variable fragments have properties different from those of classical first-
order logic and so they will serve as insightful counterexamples to statements
about the latter.

###  2.2 Some basic properties of logics

In this subsection, we briefly recall some basic definitions connected to
logics and some basic results that we will use in the paper. Let $\mathcal{L}$
be a logic in the sense of Definition 2.1. The sets of connectives, atomic
formulas, formulas, models etc of $\mathcal{L}$ will be denoted by
$\operatorname{Cn}(\mathcal{L}),P(\mathcal{L}),F(\mathcal{L}),M(\mathcal{L})$
etc. Sometimes we write $\operatorname{Cn}_{\mathcal{L}},P_{\mathcal{L}}$ etc.
or we omit reference to $\mathcal{L}$ when it is clear from context.

Recall from Definition 2.1 that the _formula algebra_ $\mathfrak{F}$ of
$\mathcal{L}$ is the term-algebra over $P$ of similarity type
$\operatorname{Cn}$. This means that the universe of $\mathfrak{F}$ is the set
of terms constructed by the logical connectives from the atomic formulas,
e.g., $\neg p$ is a term if $\neg$ is a unary connective and $p$ is an atomic
formula. The operations of the term-algebra are the natural ones imitating
this construction, e.g., there is a unary operation in $\mathfrak{F}$ denoted
by $\neg$. Note that the operations of the formula algebra are denoted by the
connectives.

In the definition of a logic we require that $\mathfrak{F}$ is an absolutely
free algebra over $P$. This means that any function $f:P\to A$ where $A$ is
the universe of an algebra $\mathfrak{A}$ of similarity type
$\operatorname{Cn}$ can be extended to a homomorphism
$\bar{f}:\mathfrak{F}\to\mathfrak{A}$. However, the term-algebra
$\mathfrak{F}$ is an absolutely free algebra over $P$ if and only if no
element of $P$ is a “proper” term written up by $\operatorname{Cn}$ from other
elements of $P$, i.e., if $p\notin\mbox{\sf
Trm}_{\operatorname{Cn}}(P\smallsetminus\\{p\\})$, for all $p\in P$. We will
refer to this property briefly as $P$ does not contain proper terms by
$\operatorname{Cn}$. Similarly, we need that $P$ and $\operatorname{Cn}$ are
determined by $\mathfrak{F}$, this holds when $\mathfrak{F}$ is an absolutely
free algebra over $P$. This is why the condition that no element of $P$ is a
proper term by $\operatorname{Cn}$ occurs at some places in the paper.

Define a congruence relation $\sim_{\mathcal{L}}$ on the formula algebra
$\mathfrak{F}$ by

$(\forall\varphi,\psi\in
F)\big{(}\varphi\sim_{\mathcal{L}}\psi\Longleftrightarrow(\forall\mathfrak{M}\in
M)\operatorname{mng}_{\mathfrak{M}}(\varphi)=\operatorname{mng}_{\mathfrak{M}}(\psi)\big{)},$
(5)

that is,
$\sim_{\mathcal{L}}\;=\;\bigcap\\{\ker(\operatorname{mng}_{\mathfrak{M}}):\;\mathfrak{M}\in
M\\}$, where $\ker(f)$ denotes the _kernel_ of the function $f:A\to B$, i.e.,
$\ker(f)=\\{\langle a,b\rangle:a,b\in A,f(a)=f(b)\\}$. $\sim_{\mathcal{L}}$ is
called the _tautological congruence_ relation of $\mathcal{L}$. It is a
congruence relation because all the meaning functions are homomorphisms. Two
formulas are related by the tautological congruence iff their meanings
coincide in all models, i.e., if no model can distinguish them based on their
meanings.

The quotient algebra $\mathfrak{F}/\\!\\!\sim_{\mathcal{L}}$ of $\mathfrak{F}$
factorized by $\sim_{\mathcal{L}}$ is called the _tautological formula
algebra_ , or the _Lindenbaum–Tarski algebra of $\mathcal{L}$_. In many
logics, e.g., in $\mathcal{C}\mathcal{P}\mathcal{L}$ and
$\mathcal{F}\mathcal{O}\mathcal{L}$, the tautological congruence relation
corresponds to the set of formulas valid in all models. In more detail,
coincidence of meanings of formulas and the validity relation are
interdefinable in these logics. For example,
$\operatorname{mng}_{\mathfrak{M}}(\varphi)=\operatorname{mng}_{\mathfrak{M}}(\psi)$
holds iff $\mathfrak{M}\vDash\varphi\leftrightarrow\psi$ in
$\mathcal{C}\mathcal{P}\mathcal{L}$.999In general logic, this property of a
logic is called the filter property see, e.g., [1, Def. 3.3.18].

In any logic, there are certain properties that hold for all formulas in place
of the atomic ones. For example in $\mathcal{F}\mathcal{O}\mathcal{L}$, the
formula $\forall x[\exists yR(x)\to R(x)]$ does not hold for all formulas in
place of $R(x)$, but $R(x)\to R(x)$ does. This motivates the following
definition.

A function $s:P\to F$ is called a formula-substitution, or just a
_substitution_. Since $s$ extends uniquely to a homomorphism
$\bar{s}:\mathfrak{F}\to\mathfrak{F}$, all homomorphisms
$h:\mathfrak{F}\to\mathfrak{F}$ are also called substitutions. The
_substitution-invariant part_ of $\sim_{\mathcal{L}}$ is defined as

$\mbox{\sf si}(\sim_{\mathcal{L}})\ =\ \\{\langle\varphi,\psi\rangle:(\forall
h:\mathfrak{F}\to\mathfrak{F})\ \langle h(\varphi),h(\psi)\rangle\in\
\sim_{\mathcal{L}}\\}.$ (6)

For a model $\mathfrak{M}\in M$, the algebra
$\operatorname{mng}_{\mathfrak{M}}(\mathfrak{F})$ is called the _concept
algebra_ or the _meaning algebra_ of $\mathfrak{M}$. The name concept algebra
reflects that the meanings of formulas in $\mathfrak{M}$ can be considered to
be the concepts of $\mathfrak{M}$ expressible in $\mathcal{L}$. Let
$\mbox{Mng}(\mathcal{L})$ and $\operatorname{Alg}_{m}(\mathcal{L})$ denote the
classes of all meaning functions and all meaning algebras, respectively:

$\mbox{Mng}(\mathcal{L})=\\{\operatorname{mng}_{\mathfrak{M}}:\mathfrak{M}\in
M\\}\quad\mbox{ and
}\quad\operatorname{Alg}_{m}(\mathcal{L})=\big{\\{}\operatorname{mng}_{\mathfrak{M}}(\mathfrak{F}):\;\mathfrak{M}\in
M\big{\\}}.$ (7)

Both $\mbox{Mng}(\mathcal{L})$ and $\operatorname{Alg}_{m}(\mathcal{L})$ are
counterparts of models. Usually, but not always,
$\operatorname{mng}_{\mathfrak{M}}$ has all the information about the model,
i.e., if $\mathfrak{M},\mathfrak{N}$ are distinct, then
$\operatorname{mng}_{\mathfrak{M}}$ and $\operatorname{mng}_{\mathfrak{N}}$
are also distinct. A concept algebra retains all information the meaning
function has, except that the information about which formula is atomic is
“forgotten” (deliberately).

Theorem 2.4 below connects the notions introduced so far. In the theorem, just
as in the paper, two notions related to that of the term-algebra will be
extensively used: the notions of free algebras and conditionally free
algebras. In the following, we omit reference to the similarity type since
this can be determined by the algebra. Let $\mathfrak{F}(X)$ denote the term-
algebra of some similarity type over a set $X$, let $\mathsf{K}$ be a class of
algebras of the same similarity type and let $S\subseteq F\times F$ be a
binary relation over the universe $F$ of $\mathfrak{F}(X)$. Let
$\operatorname{Hom}(\mathfrak{F},\mathsf{K})$ denote the class of all
homomorphisms from $\mathfrak{F}$ to members of $\mathsf{K}$, and let

$\displaystyle\operatorname{Hom}(\mathfrak{F},\mathsf{K},S)=\\{h\in\operatorname{Hom}(\mathfrak{F},\mathsf{K}):S\subseteq\ker(h)\\}.$
(8)

The _$X$ -freely generated $\mathsf{K}$-free algebra_
$\mathfrak{Fr}(\mathsf{K},X)$ is defined as

$\displaystyle\mathfrak{Fr}(\mathsf{K},X)=\mathfrak{F}(X)/\mbox{\sf
Cr}(\mathsf{K},X),\text{ where }\mbox{\sf
Cr}(\mathsf{K},X)=\bigcap\\{\ker(h):h\in\operatorname{Hom}(\mathfrak{F}(X),\mathsf{K})\\}.$
(9)

Similarly, let

$\displaystyle\mbox{\sf
Cr}(\mathsf{K},X,S)=\bigcap\\{\ker(h):h\in\operatorname{Hom}(\mathfrak{F}(X),\mathsf{K},S)\\}$
(10)

and the _$X$ -freely generated conditionally $\mathsf{K}$-free algebra with
conditions $S$_ is defined as

$\displaystyle\mathfrak{Fr}(\mathsf{K},X,S)=\mathfrak{F}(X)/\mbox{\sf
Cr}(\mathsf{K},X,S).$ (11)

For a class $\mathsf{K}$ of similar algebras, let $\mathbf{SP}\mathsf{K}$ and
$\mathbf{HSP}\mathsf{K}$ denote the classes of algebras obtained from elements
of $\mathsf{K}$ by the algebraic constructions of products and subalgebras,
and the algebraic constructions of products, subalgebras and homomorphisms,
respectively. The term-algebra and the free algebra are special cases of the
conditionally free algebra, namely
$\mathfrak{Fr}(\mathsf{K},X)=\mathfrak{Fr}(\mathsf{K},X,\emptyset)$ and
$\mathfrak{F}(X)=\mathfrak{Fr}(\mathsf{M},X)$ where $\mathsf{M}$ is the class
of all algebras of the similarity type of $\mathfrak{F}(X)$. We will use that
$\mathfrak{Fr}(\mathsf{K},X)=\mathfrak{Fr}(\mathbf{HSP}\mathsf{K},X)$ and
$\mathfrak{Fr}(\mathsf{K},X,S)=\mathfrak{Fr}(\mathbf{SP}\mathsf{K},X,S)$. For
more about the conditionally free algebras see [19, 0.4.65].

Theorem 2.4 below states that the tautological formula algebra of any logic is
the $P$-freely generated $\sim_{\mathcal{L}}$-conditionally
$\operatorname{Alg}_{m}(\mathcal{L})$-free algebra,101010In [1, Cor. 3.3.16]
this is stated only for conditionally substitutional logics, but the statement
holds for all logics. and the formula algebra factored by the substitution-
invariant part of $\sim_{\mathcal{L}}$ is the $P$-freely generated
$\operatorname{Alg}_{m}(\mathcal{L})$-free algebra. For $\varphi,\psi\in F$,
let $[\varphi=\psi]$ denote the equation in the language of
$\operatorname{Alg}_{m}(\mathcal{L})$ where the elements of $P$ are the
algebraic variables. Theorem 2.4(iii) states that the substitution-invariant
part of $\sim_{\mathcal{L}}$ is the equational theory of
$\operatorname{Alg}_{m}(\mathcal{L})$ such that the atomic formulas are the
algebraic variables. Thus, the equational theory of the concept algebras can
be recovered from the tautological congruence by syntactical means, in any
logic.

######  2.4 Theorem.

Let $\mathcal{L}$ be any logic in the sense of Definition 2.1. Then (i)-(iii)
below hold.

  1. (i)

$\mathfrak{F}(\mathcal{L})/\\!\sim_{\mathcal{L}}=\mathfrak{Fr}(\operatorname{Alg}_{m}(\mathcal{L}),P(\mathcal{L}),\sim_{\mathcal{L}})$

  2. (ii)

$\mathfrak{F}(\mathcal{L})/\mbox{\sf
si}(\sim_{\mathcal{L}})=\mathfrak{Fr}(\operatorname{Alg}_{m}(\mathcal{L}),P(\mathcal{L}))$

  3. (iii)

$\mbox{\sf
si}(\sim_{\mathcal{L}})=\\{\langle\varphi,\psi\rangle:\operatorname{Alg}_{m}(\mathcal{L})\vDash[\varphi=\psi]\\}$

Proof . (i) We show that $\sim_{\mathcal{L}}$ equals $\mbox{\sf
Cr}(\operatorname{Alg}_{m}(\mathcal{L}),P(\mathcal{L}),\sim_{\mathcal{L}})$,
that is,

$\bigcap\\{\ker(\operatorname{mng}_{\mathfrak{M}}):\;\mathfrak{M}\in
M(\mathcal{L})\\}\ =\
\bigcap\\{\ker(h):\;h\in\operatorname{Hom}(\mathfrak{F}(\mathcal{L}),\operatorname{Alg}_{m}(\mathcal{L}),\sim_{\mathcal{L}})\\}\,.$
(12)

For
$h\in\operatorname{Hom}(\mathfrak{F}(\mathcal{L}),\operatorname{Alg}_{m}(\mathcal{L}),\sim_{\mathcal{L}})$,
we have $\sim_{\mathcal{L}}\;\subseteq\ker(h)$, therefore $\sim_{\mathcal{L}}$
is a subset of the intersection in the right-hand side of (12), i.e.,
$\sim_{\mathcal{L}}$ $\subseteq$ $\mbox{\sf
Cr}(\operatorname{Alg}_{m}(\mathcal{L}),P(\mathcal{L}),\sim_{\mathcal{L}})$.
For the inclusion $\supseteq$ note that for each $\mathfrak{M}\in
M(\mathcal{L})$ we have
$\sim_{\mathcal{L}}\;\subseteq\ker(\operatorname{mng}_{\mathfrak{M}})$, hence

$\displaystyle\operatorname{mng}_{\mathfrak{M}}\ \in\
\operatorname{Hom}(\mathfrak{F}(\mathcal{L}),\operatorname{Alg}_{m}(\mathcal{L}),\sim_{\mathcal{L}}),$
(13)

and thus $\mbox{\sf
Cr}(\operatorname{Alg}_{m}(\mathcal{L}),P(\mathcal{L}),\sim_{\mathcal{L}})$
$\subseteq$ $\sim_{\mathcal{L}}$.

(ii) Here we need to prove $\mbox{\sf si}(\sim_{\mathcal{L}})\ =\ \mbox{\sf
Cr}(\operatorname{Alg}_{m}(\mathcal{L}),P(\mathcal{L}))$, that is,

$\displaystyle\begin{split}\\{\langle\varphi,\psi\rangle:\;\forall
h\in\operatorname{Hom}(\mathfrak{F},\mathfrak{F})\;&(\forall\mathfrak{M}\in
M)\;\operatorname{mng}_{\mathfrak{M}}(h(\varphi))=\operatorname{mng}_{\mathfrak{M}}(h(\psi))\\}\\\
&=\ \
\bigcap\\{\ker(k):\;k\in\operatorname{Hom}(\mathfrak{F},\operatorname{Alg}_{m}(\mathcal{L}))\\}\,.\end{split}$
(14)

Take any
$k\in\operatorname{Hom}(\mathfrak{F},\operatorname{Alg}_{m}(\mathcal{L}))$,
that is, $k:\mathfrak{F}\to\operatorname{mng}_{\mathfrak{M}}(\mathfrak{F})$
for some $\mathfrak{M}\in M$. To prove (14) it is enough to show that there is
a homomorphism $h:\mathfrak{F}\to\mathfrak{F}$ such that
$k=\operatorname{mng}_{\mathfrak{M}}\circ\;h$. To obtain such $h$, note that
for each $p\in P(\mathcal{L})$ there is $\psi_{p}\in F$ such that
$k(p)=\operatorname{mng}_{\mathfrak{M}}(\psi_{p})$. Let $h$ be the homomorphic
extension of the mapping $p\mapsto\psi_{p}$.

${\mathfrak{F}}$${\operatorname{mng}_{\mathfrak{M}}(\mathfrak{F})}$${\mathfrak{F}}$$\scriptstyle{k}$$\scriptstyle{h}$$\scriptstyle{\operatorname{mng}_{\mathfrak{M}}}$

(iii) Let $\mathfrak{A}=\operatorname{mng}_{\mathfrak{M}}(\mathfrak{F})$ for
some $\mathfrak{M}\in M$. By definition, $\mathfrak{A}\vDash[\varphi=\psi]$
holds iff for all evaluations (homomorphism) $e:\mathfrak{F}\to\mathfrak{A}$
we have $\mathfrak{A}\vDash[\varphi=\psi][e]$, that is, the equality holds in
$\mathfrak{A}$ under the evaluation $e$. Part (ii) of this proof shows that
$e=\operatorname{mng}_{\mathfrak{M}}\circ\;h$ for some homomorphism
$h:\mathfrak{F}\to\mathfrak{F}$. Conversely, for each
$h:\mathfrak{F}\to\mathfrak{F}$ the homomorphism
$\operatorname{mng}_{\mathfrak{M}}\circ\;h$ gives rise to an evaluation over
$\mathfrak{A}$. Therefore,

$\displaystyle\mathfrak{A}\vDash[\varphi=\psi]\ \ \text{ iff }\ \ (\forall
h:\mathfrak{F}\to\mathfrak{F})\ \langle
h(\varphi),h(\psi)\rangle\in\ker(\operatorname{mng}_{\mathfrak{M}}).$ (15)

To complete the proof recall that

$\displaystyle\langle\varphi,\psi\rangle\in\mbox{\sf si}(\sim_{\mathcal{L}})\
\ \text{ iff }\ \ (\forall\mathfrak{M}\in M)(\forall
h:\mathfrak{F}\to\mathfrak{F})\
\langle\varphi,\psi\rangle\in\ker(\operatorname{mng}_{\mathfrak{M}}\circ\;h)\,.$
(16)

$\blacksquare$

Recall the notion of a deductive system from [8], [14], [7]. A deductive
system $\vdash$ is called _2-dimensional_ when $H\vdash\Phi$ implies
$H\cup\\{\Phi\\}\subseteq F\times F$. We will deal only with 2-dimensional
deductive systems in this paper, so we will omit the adjective 2-dimensional.
When $\vdash$ is a deductive system and $\Sigma\subseteq F\times F$, we say
that $\Sigma$ is _closed_ under $\vdash$ when
$\langle\tau,\sigma\rangle\in\Sigma$ whenever
$H\vdash\langle\tau,\sigma\rangle$ and $H\subseteq\Sigma$. The _$\vdash$
-closure_ of $\Sigma$ is defined as the smallest set containing $\Sigma$ and
closed under $\vdash$. We call a deductive system _sound_ if
$\ker(\operatorname{mng}_{\mathfrak{M}})$ is closed under $\vdash$, for all
models $\mathfrak{M}\in M$. A deductive system is called _substitutional_ when
$H\vdash\langle\tau,\sigma\rangle$ implies $f(H)\vdash\langle
f\tau,f\sigma\rangle$ for all $f:\mathfrak{F}\to\mathfrak{F}$. Define
$\vdash_{\mathcal{L}}$ as follows. For all $H\subseteq F\times F$ and
$\tau,\sigma\in F$,

$\displaystyle\begin{split}H\ \vdash_{\mathcal{L}}\ \langle\tau,\sigma\rangle\
\ \Leftrightarrow\ \ (\forall
f&:\mathfrak{F}\to\mathfrak{F})(\forall\mathfrak{M}\in M)\\\
&\big{[}f(H)\subseteq\ker(\operatorname{mng}_{\mathfrak{M}})\mbox{
$\Rightarrow$ }\langle
f\tau,f\sigma\rangle\in\ker(\operatorname{mng}_{\mathfrak{M}})\big{]},\end{split}$
(17)

where $f(H)=\\{\langle f(\varphi),f(\psi)\rangle:\langle\varphi,\psi\rangle\in
H\\}$.

The following theorem says that each logic $\mathcal{L}$ contains a largest
substitutional and sound, but not necessarily finitary, (2-dimensional)
deductive system in it. This deductive system is $\vdash_{\mathcal{L}}$
defined above and it corresponds to the infinitary quasi-equational theory of
$\operatorname{Alg}_{m}(\mathcal{L})$ such that the atomic formulas are
considered as algebraic variables.

######  2.5 Theorem.

Let $\mathcal{L}$ be any logic in the sense of Definition 2.1. Then (i)-(ii)
below hold.

  1. (i)

$\vdash_{\mathcal{L}}$ is the largest substitutional and sound deductive
system in $\mathcal{L}$.

  2. (ii)

$\vdash_{\mathcal{L}}$ corresponds to the infinitary quasi-equational theory
of $\operatorname{Alg}_{m}(\mathcal{L})$, i.e., for all $H\subseteq F\times F$
and $\varphi,\psi\in F$ we have

$\displaystyle H\vdash_{\mathcal{L}}\langle\varphi,\psi\rangle\quad\mbox{ iff
}\quad\operatorname{Alg}_{m}(\mathcal{L})\vDash\wedge H\to[\varphi=\psi].$
(18)

Proof . (i) $\vdash_{\mathcal{L}}$ is sound, if
$\ker(\operatorname{mng}_{\mathfrak{M}})$ is closed under
$\vdash_{\mathcal{L}}$ for all models $\mathfrak{M}$, that is, for
$H\subseteq\ker(\operatorname{mng}_{\mathfrak{M}})$ if
$H\vdash_{\mathcal{L}}\langle\tau,\sigma\rangle$, then
$\langle\tau,\sigma\rangle\in\ker(\operatorname{mng}_{\mathfrak{M}})$. This
follows from (17) with $f$ being the identity mapping. The composition $f\circ
g$ of two homomorphisms $f,g:\mathfrak{F}\to\mathfrak{F}$ is a homomorphism,
which yields substitutionality of $\vdash_{\mathcal{L}}$.

By way of contradiction, suppose that $\vdash$ is a substitutional and sound
deductive system in $\mathcal{L}$, and $\vdash_{\mathcal{L}}\subsetneq\vdash$.
Then there are $H\subseteq F\times F$ and $\tau,\sigma\in F$ such that
$H\vdash\langle\tau,\sigma\rangle$, but
$H\nvdash_{\mathcal{L}}\langle\tau,\sigma\rangle$. The latter implies that
there are $f:\mathfrak{F}\to\mathfrak{F}$ and $\mathfrak{M}\in M$ so that
$f(H)\subseteq\ker(\operatorname{mng}_{\mathfrak{M}})$ but $\langle
f(\tau),f(\sigma)\rangle\notin\ker(\operatorname{mng}_{\mathfrak{M}})$.
Substitutionality of $\vdash$ ensures $f(H)\vdash\langle
f(\tau),f(\sigma)\rangle$. By assumption,
$f(H)\subseteq\ker(\operatorname{mng}_{\mathfrak{M}})$. Soundness of $\vdash$
implies $\langle
f(\tau),f(\sigma)\rangle\in\ker(\operatorname{mng}_{\mathfrak{M}})$, yielding
a contradiction. Therefore, $\vdash_{\mathcal{L}}$ is the largest among the
substitutional and sound deductive systems in $\mathcal{L}$.

(ii) The proof of Theorem 2.4(iii), in particular (15) shows that

$\displaystyle\begin{split}\operatorname{Alg}_{m}(\mathcal{L})\vDash\wedge
H\to&[\varphi=\psi]\ \ \Leftrightarrow\ \ (\forall
f:\mathfrak{F}\to\mathfrak{F})(\forall\mathfrak{M}\in M)\\\
&\big{[}f(H)\subseteq\ker(\operatorname{mng}_{\mathfrak{M}})\mbox{
$\Rightarrow$ }\langle
f\tau,f\sigma\rangle\in\ker(\operatorname{mng}_{\mathfrak{M}})\big{]}.\end{split}$
(19)

The right-hand side of (19) is the definition of
$H\vdash_{\mathcal{L}}\langle\tau,\sigma\rangle$. $\blacksquare$

We finish this subsection with defining the notions of isomorphism between
logics and reduct of a logic. In the next two definitions, let
$\mathcal{L}^{P}=\langle F^{P},M^{P},\operatorname{mng}^{P},\vDash^{P}\rangle$
and $\mathcal{L}^{Q}=\langle
F^{Q},M^{Q},\operatorname{mng}^{Q},\vDash^{Q}\rangle$ be logics with atomic
formulas $P,Q$ and formula algebras $\mathfrak{F}^{P},\mathfrak{F}^{Q}$
respectively..

######  2.6 Definition (isomorphism between logics).

An _isomorphism_ between $\mathcal{L}^{P}$ and $\mathcal{L}^{Q}$ is a pair
$f^{F},f^{M}$ of bijections such that

  1. (a)

$f^{F}$ is an isomorphism from $\mathfrak{F}^{P}$ onto $\mathfrak{F}^{Q}$,

  2. (b)

$f^{M}$ is a bijection between $M^{P}$ and $M^{Q}$, and

  3. (c)

for all $\varphi\in F^{P}$ and $\mathfrak{M}\in M^{P}$

$\displaystyle\operatorname{mng}^{P}_{\mathfrak{M}}(\varphi)$
$\displaystyle=\operatorname{mng}^{Q}_{f^{M}(\mathfrak{M})}\bigl{(}f^{F}(\varphi)\bigr{)},$
(20) $\displaystyle\mathfrak{M}\vDash^{P}\varphi\quad$
$\displaystyle\Longleftrightarrow\quad
f^{M}(\mathfrak{M})\vDash^{Q}f^{F}(\varphi).$ (21)

We say that a bijection $f:P\to Q$ _induces an isomorphism_ between
$\mathcal{L}^{P}$ and $\mathcal{L}^{Q}$ if there is an isomorphism
$f^{F},f^{M}$ between $\mathcal{L}^{P}$ and $\mathcal{L}^{Q}$ such that
$f^{F}$ extends $f$. We say that $\mathcal{L}^{P}$ is an isomorphic copy of
$\mathcal{L}^{Q}$ if there is an isomorphism between them. $\square$

Note that isomorphic logics have the same class of meaning algebras, this is
immediate from the definition of an isomorphism.

######  2.7 Definition (reduct and conservative extension of a logic).

We say that $\mathcal{L}^{P}$ is a _reduct_ of $\mathcal{L}^{Q}$ if there is a
function $f^{M}$ such that

  1. (a)

$P\subseteq Q$ and $\mathfrak{F}^{P}$ is a subalgebra of $\mathfrak{F}^{Q}$,

  2. (b)

$f^{M}$ maps $M^{Q}$ onto $M^{P}$, and

  3. (c)

for all $\varphi\in F^{P}$ and $\mathfrak{M}\in M^{Q}$

$\displaystyle\operatorname{mng}^{Q}_{\mathfrak{M}}(\varphi)$
$\displaystyle=\operatorname{mng}^{P}_{f^{M}(\mathfrak{M})}(\varphi),$ (22)
$\displaystyle\mathfrak{M}\vDash^{Q}\varphi\quad$
$\displaystyle\Longleftrightarrow\quad
f^{M}(\mathfrak{M})\vDash^{P}(\varphi).$ (23)

We say that $\mathcal{L}^{Q}$ is a _conservative extension_ of
$\mathcal{L}^{P}$ when $\mathcal{L}^{P}$ is a reduct of $\mathcal{L}^{Q}$. We
will often omit the adjective “conservative”. $\square$

The following proposition says that the tautological congruence of a reduct is
the natural restriction of that of the extension, and thus the tautological
formula algebra of a reduct is naturally embeddable in the tautological
formula algebra of the extension.

######  2.8 Proposition.

Assume that $\mathcal{L}^{P}$ is a reduct of $\mathcal{L}^{Q}$. Then (i)-(ii)
below hold.

  1. (i)

$\sim^{P}=\ \sim^{Q}\cap\ (F^{P}\times F^{P})$

  2. (ii)

$f:\mathfrak{F}^{P}/\\!\sim^{P}\to\mathfrak{F}^{Q}/\\!\sim^{Q}$ is an
embedding, where $f(\varphi/\\!\sim^{P})=\varphi/\\!\sim^{Q}$ for all
$\varphi\in F^{P}$.

Proof . For proving (i), let $\varphi,\psi\in F^{P}$. Assume that
$(\varphi,\psi)\notin\ \sim^{P}$. Then there is $\mathfrak{M}\in M^{P}$ such
that
$\operatorname{mng}_{\mathfrak{M}}(\varphi)\neq\operatorname{mng}_{\mathfrak{M}}(\psi)$.
There is $\mathfrak{N}\in M^{Q}$ such that
$\operatorname{mng}_{\mathfrak{M}}=\operatorname{mng}_{\mathfrak{N}}\upharpoonright
F^{P}$ since $\mathcal{L}^{P}$ is a reduct of $\mathcal{L}^{Q}$. Thus
$\operatorname{mng}_{\mathfrak{N}}(\varphi)\neq\operatorname{mng}_{\mathfrak{N}}(\psi)$
and therefore $(\varphi,\psi)\notin\ \sim^{Q}$. The other direction is
completely analogous: assume that $(\varphi,\psi)\notin\ \sim^{Q}$. Then there
is $\mathfrak{N}\in M^{Q}$ such that
$\operatorname{mng}_{\mathfrak{N}}(\varphi)\neq\operatorname{mng}_{\mathfrak{N}}(\psi)$.
Let $\mathfrak{M}\in M^{P}$ be such that
$\operatorname{mng}_{\mathfrak{M}}=\operatorname{mng}_{\mathfrak{N}}\upharpoonright
F^{P}$, there is such $\mathfrak{M}$ since $\mathcal{L}^{P}$ is a reduct of
$\mathcal{L}^{Q}$. Thus
$\operatorname{mng}_{\mathfrak{M}}(\varphi)\neq\operatorname{mng}_{\mathfrak{M}}(\psi)$
and therefore $(\varphi,\psi)\notin\ \sim^{P}$. This proves (i). Now, (ii) is
a direct consequence of (i). $\blacksquare$

##  3 Propositional- and predicate-like logics

In this section, we define two characteristic subclasses of logics. In the
first class, atomic formulas can be replaced (substituted) with any other
formulas without affecting meaning, in the second class, this can be done only
with formulas satisfying some conditions. Propositional logics usually fall
into the first class, while classical first-order logic is a typical example
of the second class.

The substitution property formalizes a “total (or unconditional) freedom” of
the propositional variables and is as follows.

######  3.1 Definition (substitution property).

We say that $\mathcal{L}$ has the _substitution property_ 111111This is called
semantical substitution property in [1, 3.3.10]. The syntactic substitution
property of [1, 3.3.9] corresponds to the tautological congruence being
substitutional, see Proposition 3.3. or that $\mathcal{L}$ is _substitutional_
if for any $s:P\to F$ and any model $\mathfrak{M}\in M$ there is a model
$\mathfrak{N}\in M$ such that for all $p\in P$ we have

$\operatorname{mng}_{\mathfrak{N}}(p)=\operatorname{mng}_{\mathfrak{M}}(s(p)).$
(24)

The model $\mathfrak{N}$ is called the _substituted version_ of $\mathfrak{M}$
along substitution $s$. $\square$

The following is proved in [1, 3.3.11].

######  3.2 Claim (equivalent forms of being substitutional).

The following are equivalent.

  1. (i)

$\mathcal{L}$ is substitutional.

  2. (ii)

$Mng_{\mathcal{L}}$ is the class of all homomorphisms from the formula algebra
$\mathfrak{F}$ to members of $\operatorname{Alg}_{m}(\mathcal{L})$, i.e.,

$Mng_{\mathcal{L}}=\operatorname{Hom}(\mathfrak{F},\operatorname{Alg}_{m}(\mathcal{L})).$
(25)

  3. (iii)

There is a class $\mathsf{K}$ of algebras such that $\mbox{Mng}_{\mathcal{L}}$
is the class of all homomorphisms from the formula algebra to members of
$\mathsf{K}$, i.e.,

$Mng_{\mathcal{L}}=\operatorname{Hom}(\mathfrak{F},\mathsf{K})\quad\mbox{ for
some }\mathsf{K}.$ (26)

The substitution property implies that the tautological congruence relation is
substitutional, i.e., it is its own substitutional part.

######  3.3 Proposition (syntactic substitution).

If $\mathcal{L}$ has the substitution property, then $\mbox{\sf
si}(\sim_{\mathcal{L}})=\ \sim_{\mathcal{L}}$.

Proof . Assuming that $\langle\varphi,\psi\rangle\in\;\sim_{\mathcal{L}}$ and
$h:\mathfrak{F}\to\mathfrak{F}$ is a substitution, we have to show that
$\langle h(\varphi),h(\psi)\rangle\in\;\sim_{\mathcal{L}}$. Let
$\mathfrak{M}\in M$ be a model, then
$h\circ\operatorname{mng}_{\mathfrak{M}}=\operatorname{mng}_{\mathfrak{N}}$
for some model $\mathfrak{N}$, by 3.2(ii). Then
$\langle\varphi,\psi\rangle\in\ker(\operatorname{mng}_{\mathfrak{N}})$ by
$\langle\varphi,\psi\rangle\in\;\sim_{\mathcal{L}}$, so $\langle
h(\varphi),h(\psi)\rangle\in\ker(\operatorname{mng}_{\mathfrak{M}})$. Since
$\mathfrak{M}\in M$ was chosen arbitrarily, this means that
$\langle\varphi,\psi\rangle\in\;\sim_{\mathcal{L}}$. $\blacksquare$

######  3.4 Example.

Classical propositional logic $\mathcal{C}\mathcal{P}\mathcal{L}$ is
substitutional (cf. [1, 3.3.13]).

Proof . For any set $P$ of propositional variables and any homomorphism
$h:\mathfrak{F}^{P}\to\mathbf{2}$, the mapping $\mathfrak{M}=h\upharpoonright
P$ is a model in $\mathcal{L}_{C}^{P}$. As $P$ generates $\mathfrak{F}^{P}$,
the extension $\operatorname{mng}_{\mathfrak{M}}$ of $\mathfrak{M}$ to
$\mathfrak{F}^{P}$ coincides with $h$. Thus, any homomorphism
$h:\mathfrak{F}^{P}\to\mathbf{2}$ is a meaning function of some model.
Applying Claim 3.2(ii) finishes the proof. $\blacksquare$

######  3.5 Example.

First-order logic $\mbox{$\mathcal{F}\mathcal{O}\mathcal{L}$}_{t}(V)$ is not
substitutional, whenever $t$ is nonempty and $|V|>1$.

Proof . An easy counterexample is the following. Let $r$ be any relation
symbol, and $x,y\in V$ be distinct variables. In the example below we assume
that $r$ is unary, the case $t(r)>1$ is completely analogous. We have

$\displaystyle\vDash$ $\displaystyle r(x)\;\longleftrightarrow\;\exists
y(x=y\;\wedge r(y))$ (27) $\displaystyle\not\vDash$ $\displaystyle
r(y)\;\longleftrightarrow\;\exists y(x=y\;\wedge r(y)).$ (28)

Therefore the substitution that maps $r(x)$ to $r(y)$ and $r(y)$ to $r(y)$
does not preserve the tautological congruence. Applying Proposition 3.3
finishes the proof. $\blacksquare$

######  3.6 Remark.

Let us discuss the cases $|V|\leq 1$ concerning 3.5.

  * •

If $V=\emptyset$, then $P_{t}(\emptyset)$ is empty for any similarity type
$t$. The set of formulas $F_{t}(V)$ is generated by $\bot$ and the $\wedge$,
$\neg$. This is because we did not allow nullary relation symbols. The logic
$\mbox{$\mathcal{F}\mathcal{O}\mathcal{L}$}_{t}(\emptyset)$ is therefore
classical propositional logic without propositional letters, and is
substitutional by 3.4. We note that if nullary relations were allowed, then
$\mbox{$\mathcal{F}\mathcal{O}\mathcal{L}$}_{t}(\emptyset)$ would be the same
as propositional logic $\mathcal{C}\mathcal{P}\mathcal{L}$.

  * •

If $|V|=1$, then $\mbox{$\mathcal{F}\mathcal{O}\mathcal{L}$}_{t}(V)$ is
basically the same as modal logic $S5$, which is substitutional (see [1,
Example 3.2.5]).

Though first-order logic is not substitutional, it has an analogous and just
as useful substitution property. Namely, an atomic formula
$r(v_{1},\dots,v_{n})$ represents any formula with free variables
$v_{1},\dots,v_{n}$ in the sense that we can substitute $r(v_{1},\dots,v_{n})$
with any formula with free variables $v_{1},\dots,v_{n}$ in a model, and we
get another model. In first-order logic as formalized in Example 2.3, there is
another feature coded in the set of atomic formulas. Though an atomic formula
$r(v_{1},\dots,v_{n})$ can take the meaning of that of any formula
$\varphi(v_{1},\dots,v_{n})$ with free variables $v_{1},\dots,v_{n}$, there
are connections between the meanings of $r(v_{1},...,v_{n})$ and the same
relation symbol followed by a different sequence of variables, say,
$r(v_{2},v_{1},\dots,v_{n})$. Namely the meaning of $r(v_{2},v_{1},...,v_{n})$
is determined as soon as we know the meaning of $r(v_{1},v_{2},\dots,v_{n})$.
Luckily, in $\mbox{$\mathcal{F}\mathcal{O}\mathcal{L}$}_{t}(V)$ with $V$
infinite, all these connections can be expressed in the language, and so they
are present in the tautological congruence. The following weaker substitution
property, conditional substitutional property, is intended to capture this
feature of a logic.

######  3.7 Definition (conditional substitution property).

We say that the logic $\mathcal{L}$ has the _conditional substitution
property_ , or that $\mathcal{L}$ is _conditionally substitutional_ , if for
any homomorphism $s:\mathfrak{F}\to\mathfrak{F}$ and any model
$\mathfrak{M}\in M$,

$\sim_{\mathcal{L}}\;\subseteq\;\ker(\operatorname{mng}_{\mathfrak{M}}\circ\;s)\quad\Longrightarrow\quad(\exists\mathfrak{N}\in
M)(\forall p\in P)\
\operatorname{mng}_{\mathfrak{N}}(p)=\operatorname{mng}_{\mathfrak{M}}(s(p)).$
(29)

The model $\mathfrak{N}$ is called the _substituted version_ of $\mathfrak{M}$
along the substitution $s$. $\square$

The following is proved in [1, 3.3.15],

######  3.8 Claim (equivalent forms of being conditionally substitutional).

The following are equivalent.

  1. (i)

$\mathcal{L}$ is conditionally substitutional.

  2. (ii)

$\mbox{Mng}_{\mathcal{L}}=\operatorname{Hom}(\mathfrak{F},\operatorname{Alg}_{m}(\mathcal{L}),\sim_{\mathcal{L}}).$

  3. (iii)

$\mbox{Mng}_{\mathcal{L}}=\operatorname{Hom}(\mathfrak{F},\mathsf{K},S)$ for
some $\mathsf{K}\mbox{ and }S$.

######  3.9 Theorem.

For an infinite set $V$ of variables, first-order logic
$\mbox{$\mathcal{F}\mathcal{O}\mathcal{L}$}_{t}(V)$ is conditionally
substitutional.

Proof . Let us introduce some notation. We fix a one-to-one enumeration
$v=\langle v_{i}:\;i\in|V|\rangle$ of the variables, i.e.,
$V=\\{v_{i}:i\in|V|\\}$. For a relation symbol $r$ of arity $n$ we write

$S(r)=\big{\\{}\big{\langle}r(v_{0},\ldots,v_{n-1}),\ \exists
v_{j}r(v_{0},\ldots,v_{n-1})\big{\rangle}:\;j\geq n\big{\\}}.$ (30)

For $r(v_{i_{0}},\ldots,v_{i_{n-1}})$ let
$r^{*}(v_{i_{0}},\ldots,v_{i_{n-1}})$ denote the formula

$\exists v_{j_{0}}\cdots\exists
v_{j_{n-1}}\big{[}\bigwedge_{k<n}v_{i_{k}}=v_{j_{k}}\;\wedge\exists
v_{0}\cdots\exists v_{n-1}(\bigwedge_{k<n}v_{k}=v_{j_{k}}\;\wedge
r(v_{0},\ldots,v_{n-1}))\big{]}$ (31)

where the variables $v_{j_{0}}$, $\ldots$, $v_{j_{n-1}}$ are the first in the
enumeration that are not among $v_{0}$,$\ldots$, $v_{n-1}$, $v_{i_{0}}$,
$\ldots$, $v_{i_{n-1}}$. Write

$E(r)=\big{\\{}\big{\langle}r(v_{i_{0}},\ldots,v_{i_{n-1}}),\
r^{*}(v_{i_{0}},\ldots,v_{i_{n-1}})\big{\rangle}:\;v_{i_{0}},\ldots,v_{i_{n-1}}\in
V\big{\\}}.$ (32)

Note that in the definition of $E(r)$ we used that there are infinitely many
variables available. Finally, for a similarity type $t$ let us write

$D(t)=\bigcup\big{\\{}S(r)\cup E(r):\;r\in\operatorname{dom}(t)\big{\\}}.$
(33)

The set $S(r)$ expresses that the relation $r(v_{0},\ldots,v_{n-1})$ depends
only on the variables $v_{0}$, $\ldots$, $v_{n-1}$, while $E(r)$ expresses
that the meaning of $r(v_{0},\ldots,v_{n-1})$ determines the meaning of
$r(v_{i_{0}},\ldots,v_{i_{n-1}})$ for any sequence of variables.

By rules of first-order logic for any similarity type $t$, the set $D(t)$ is a
subset of the tautological congruence of
$\mbox{$\mathcal{F}\mathcal{O}\mathcal{L}$}_{t}(V)$.

Let $\mathcal{L}$ denote $\mbox{$\mathcal{F}\mathcal{O}\mathcal{L}$}_{t}(V)$
and $\mathfrak{F}$ denote the formula algebra of $\mathcal{L}$. We are going
to show that the class of meaning functions of $\mathcal{L}$ is the class of
homomorphisms from $\mathfrak{F}$ to $\operatorname{Alg}_{m}(\mathcal{L})$
whose kernels contain $D(t)$:

$\mbox{Mng}_{\mathcal{L}}=\operatorname{Hom}(\mathfrak{F},\operatorname{Alg}_{m}(\mathcal{L}),D(t)).$
(34)

The inclusion $\subseteq$ in (34) is clear by
$D(t)\subseteq\,\sim_{\mathcal{L}}$. To prove the other direction, let
$h:\mathfrak{F}\to\mathfrak{A}\in\operatorname{Alg}_{m}(\mathcal{L})$ be such
that $D(t)\subseteq\ker(h)$, we want to show that
$h\in\mbox{Mng}_{\mathcal{L}}$. Let $\mathfrak{M}\in M_{t}$ be such that
$\mathfrak{A}=\operatorname{mng}_{\mathfrak{M}}(\mathfrak{F})$. Let us define
the model $\mathfrak{N}=\langle
M,r^{\mathfrak{N}}\rangle_{r\in\operatorname{dom}(t)}$ as follows: for
$r\in\operatorname{dom}(t)$, $t(r)=n$ write

$r^{\mathfrak{N}}=\big{\\{}\langle e(v_{0}),\ldots,e(v_{n-1})\rangle:\;e\in
h(r(v_{0},\ldots,v_{n-1}))\big{\\}}.$ (35)

We claim that $h=\operatorname{mng}_{\mathfrak{N}}$. For this it is enough to
check that

$\operatorname{mng}_{\mathfrak{N}}(p)=h(p)$ (36)

holds for each $p\in P_{t}(V)$ since $P_{t}(V)$ generates $\mathfrak{F}$.
Before proceeding, we introduce a property of $\mathfrak{A}$. For $a\in A$ let

$\displaystyle\Delta(a)=\\{x\in V:(\exists x)^{\mathfrak{A}}(a)\neq a\\}.$
(37)

We say that $a\in A$ is _regular in $\mathfrak{A}$_ iff $e\in a$ depends only
on its behaviour on $\Delta(a)$, i.e.,

$\displaystyle e\in a\mbox{ iff }e^{\prime}\in a\quad\mbox{ for all
$e,e^{\prime}\in{}^{V}M$ such that}\ \
e\upharpoonright\Delta(a)=e^{\prime}\upharpoonright\Delta(a).$ (38)

Now, it is not difficult to prove that

all elements of $\mathfrak{A}$ are regular. (39)

To prove (36), let $r\in\operatorname{dom}(t)$ and $n=t(r)$. Take first
$p=r(v_{0},\dots,v_{n-1})$ and let $e:V\to N$. Note that
$S(t)\subseteq\ker(h)$ means that

$\Delta(h(p))\subseteq\\{v_{0},\dots,v_{n-1}\\}.$ (40)

Now,

$\displaystyle e\in\operatorname{mng}_{\mathfrak{N}}(p)$ $\displaystyle\text{
iff }\langle e(v_{0}),\ldots,e(v_{n-1})\rangle\in r^{\mathfrak{N}}$
$\displaystyle(\text{by def. of}\operatorname{mng}_{\mathfrak{M}})$
$\displaystyle\text{ iff }\langle e(v_{0}),\ldots,e(v_{n-1})\rangle=\langle
e^{\prime}(v_{0}),\ldots,e^{\prime}(v_{n-1})\rangle$
$\displaystyle\qquad\quad\text{ for some }e^{\prime}\in h(p)$
$\displaystyle(\text{by def. of }r^{\mathfrak{N}})$ $\displaystyle\text{ iff
}e\in h(p)$ $\displaystyle(\text{by}\eqref{reg},\eqref{dp}).$

We have shown that $\operatorname{mng}_{\mathfrak{N}}(p)=h(p)$ for
$p=r(v_{0},\dots,v_{n-1})$. Take now $q=r(v_{i_{0}},\dots,v_{i_{n-1}})$. Then
$q^{*}$ is a formula depending only on $p$, so
$\operatorname{mng}_{\mathfrak{N}}(q^{*})=h(q^{*})$ by
$\operatorname{mng}_{\mathfrak{N}}(p)=h(p)$, since both
$\operatorname{mng}_{\mathfrak{N}}$ and $h$ are homomorphisms. We have
$\operatorname{mng}_{\mathfrak{N}}(q)=\operatorname{mng}_{\mathfrak{N}}(q^{*})$
by $E(t)\subseteq\,\sim_{\mathcal{L}}$ and also $h(q)=h(q^{*})$ by
$E(t)\subseteq\ker(h)$. Hence, $\operatorname{mng}_{\mathfrak{N}}(q)=h(q)$. We
have show that $\operatorname{mng}_{\mathfrak{N}}$ and $h$ agree on
$P_{t}(V)$, so $\operatorname{mng}_{\mathfrak{N}}=h$, i.e.,
$h\in\mbox{Mng}_{\mathcal{L}}$ and we are done with proving (34).

Finally, (34) implies that $\mbox{$\mathcal{F}\mathcal{O}\mathcal{L}$}_{t}(V)$
is conditionally substitutional, by 3.8(iii). $\blacksquare$

One of the key steps of the proof was to show that if $V$ is infinite, then
every formula of $\mbox{$\mathcal{F}\mathcal{O}\mathcal{L}$}_{t}(V)$ is
equivalent to a restricted formula (this is expressed by the sets $E(r)$ in
(32)). Let us make this idea more precise. For a similarity type $t$ consider
the following set

$P_{t}^{r}(V)=\big{\\{}r(v_{0},\ldots,v_{n-1}):\;r\in\operatorname{dom}(t),\
t(r)=n\big{\\}},$ (41)

called the set of restricted atomic formulas. The set of _restricted formulas_
$F_{t}^{r}(V)$ is generated by $P_{t}^{r}(V)$ using the first-order
connectives $\wedge$, $\neg$, $\bot$, $\exists v_{i}$ and $v_{i}=v_{j}$ (for
$i,j<|V|$). Applying an inductive argument using the construction in (31) we
get that any formula in $F_{t}(V)$ is equivalent to a restricted formula in
$F_{t}^{r}(V)$, provided $V$ is infinite.

However, if $|V|=\alpha$ is finite and there is a relation symbol of arity
$\alpha$, then not every formula is equivalent to a restricted one. For
example, in the case $V=\\{v_{0},v_{1}\\}$, the non-restricted atomic formula
$r(v_{1},v_{0})$ is not equivalent to any restricted formula (as permutation
of variables cannot be expressed by quantification and identities without
reference to an extra variable), see, e.g., the proof of 3.10 below.

We note that it is not the arity of the relation what matters but whether the
atomic formula uses up all the variables available. As an illustration, below
we show how to express $r(v_{1},v_{0},v_{0})$ with a restricted formula, when
$V=\\{v_{0},v_{1},v_{2}\\}$ (thus, we have $3$ variables, and $r$ is ternary;
but $r$ does not use all the $3$ variables).

$\displaystyle r(v_{1},v_{0},v_{0})$ $\displaystyle\Longleftrightarrow$
$\displaystyle\exists v_{2}(v_{2}=v_{0}\wedge r(v_{1},v_{2},v_{2}))$
$\displaystyle\Longleftrightarrow$ $\displaystyle\exists
v_{2}(v_{2}=v_{0}\wedge\exists v_{0}(v_{0}=v_{1}\wedge r(v_{0},v_{2},v_{2})))$
$\displaystyle\Longleftrightarrow$ $\displaystyle\exists
v_{2}(v_{2}=v_{0}\wedge\exists v_{0}(v_{0}=v_{1}\wedge\exists
v_{1}(v_{1}=v_{2}\wedge r(v_{0},v_{1},v_{1})))).$

The assumption that there are infinitely many variables available was crucial
in Thm.3.9. We have seen in 3.5 that
$\mbox{$\mathcal{F}\mathcal{O}\mathcal{L}$}_{t}(V)$ is not substitutional (for
$|V|>1$). The next claim shows that
$\mbox{$\mathcal{F}\mathcal{O}\mathcal{L}$}_{t}(V)$ with a _finite_ and at
least two-element set $V$ of variables is not even conditionally
substitutional. We note that 3.10 below follows, for complex enough $t$, also
from Theorems 4.13, 5.2 and 5.4.

######  3.10 Example.

If $2\leq|V|<\omega$ and $t$ has at least one $|V|$-ary relation symbol then
$\mbox{$\mathcal{F}\mathcal{O}\mathcal{L}$}_{t}(V)$ is not conditionally
substitutional.

Proof . We exhibit a model $\mathfrak{M}$ and a homomorphism
$h:\mathfrak{F}\to\operatorname{mng}_{\mathfrak{M}}(\mathfrak{F})$ such that
the kernels of $\operatorname{mng}_{\mathfrak{M}}$ and $h$ coincide, but $h$
is not the meaning function for any model $\mathfrak{N}$. By 3.8(ii) this
shows that $\mbox{$\mathcal{F}\mathcal{O}\mathcal{L}$}_{t}(V)$ is not
conditionally substitutional. We present the example for $|V|=2$ and when $t$
has two binary relation symbols, $R$ and $S$. The model $\mathfrak{M}$ is
defined as follows.

$\displaystyle M$ $\displaystyle=$ $\displaystyle\\{0,1,2,3,4\\},$ (42)
$\displaystyle R^{\mathfrak{M}}$ $\displaystyle=$ $\displaystyle\\{\langle
u,v\rangle:v=u+1\mbox{ mod }5\\},$ (43) $\displaystyle S^{\mathfrak{M}}$
$\displaystyle=$ $\displaystyle\\{\langle u,v\rangle:v=u+2\mbox{ mod }5\\}.$
(44)

Then

$\operatorname{mng}_{\mathfrak{M}}(R(v_{1},v_{0}))=\\{\langle
u,v\rangle:v=u+4\mbox{ mod }5\\}$ (45)

and

$\operatorname{mng}_{\mathfrak{M}}(S(v_{1},v_{0}))=\\{\langle
u,v\rangle:v=u+3\mbox{ mod }5\\}.$ (46)

Define the homomorphism $h$ so that $h$ agrees with
$\operatorname{mng}_{\mathfrak{M}}$ on $R(v_{0},v_{1})$ and $S(v_{0},v_{1})$,
but $h(R(v_{1},v_{0}))=\operatorname{mng}_{\mathfrak{M}}(S(v_{1},v_{0}))$ and
$h(S(v_{1},v_{0}))=\operatorname{mng}_{\mathfrak{M}}(R(v_{1},v_{0}))$. Let
$\mathfrak{A}$ denote the concept algebra of $\mathfrak{M}$, i.e.,
$\mathfrak{A}=\operatorname{mng}_{\mathfrak{M}}(\mathfrak{F})$. It is not hard
to check that there is an automorphism $\alpha$ of $\mathfrak{A}$ which leaves
$\operatorname{mng}_{\mathfrak{M}}(R(v_{0},v_{1}))$ and
$\operatorname{mng}_{\mathfrak{M}}(S(v_{0},v_{1}))$ fixed and interchanges
$\operatorname{mng}_{\mathfrak{M}}(R(v_{1},v_{0}))$ and
$\operatorname{mng}_{\mathfrak{M}}(S(v_{1},v_{0}))$. Then
$h=\alpha\circ\operatorname{mng}_{\mathfrak{M}}$ since both are homomorphisms
and they agree on the atomic formulas. So,
$\ker(h)=\ker(\operatorname{mng}_{\mathfrak{M}})$ but $h$ is not the meaning
function of any model $\mathfrak{N}$. $\blacksquare$

Let us now move on to the main topic of the paper.

##  4 Logic as a scheme – logic families

In section 2.1, our example logics were defined in a way that there was a
parameter $P$ which stood for the set of atomic formulas. This parameter was
either an arbitrary set (e.g., in the case of classical propositional logic
$\mathcal{C}\mathcal{P}\mathcal{L}$) or was given by a similarity type as in
the case of first-order logic
$\mbox{$\mathcal{F}\mathcal{O}\mathcal{L}$}_{t}(V)$. Thus, in first-order
logic the parameter $P$ had further structure, not all sets could be
considered to be the set of atomic formulas. In the next definition we capture
the aspect of a logic where the set of atomic formulas is a parameter — we
define what could be called a _logic scheme_ , reflecting that the parameter
$P$ can vary but the rest of the definition is of the same pattern. Schemes of
logics are called _general logic_ s in [1] and [3]. In the present paper we
use the terminology logic family.

In subsection 4.1, we define the notions of logic family and pre-family of
logics, and we discuss the conditions in the definition. In subsection 4.2, we
begin discussing the least natural condition in a logic family, that which
concerns union of signatures. In subsection 4.3, we discuss this condition in
the special case of conditionally substitutional pre-families and we show that
each conditionally substitutional logic is a member of a logic family.

###  4.1 Logic families and discussion of logic pre-families

In what follows we give the definition of a logic family. This definition
basically is the same as [1, 3.3.27], but there are differences which we
mention in the discussion that follows. Of the conditions given in the
definition, conditions (4) and (5) are specific for first-order-like logics,
they are not present in the families of logics as specified so far for
propositional-like logics. In this subsection we discuss condition (5) and in
the next subsections we discuss condition (4).

######  4.1 Definition (Logic family, logic pre-family).

A _logic family_ is a family
$\mathbf{L}=\langle\mathcal{L}^{P}:\;P\in\operatorname{Sig}\rangle$, where
$\operatorname{Sig}$ is a class of sets, $\mathcal{L}^{P}$is a logic in the
sense of Definition 2.1 for each $P\in\operatorname{Sig}$, and conditions
(1)–(5) below are satisfied for any sets $P,Q\in\operatorname{Sig}$.

  1. (1)

$P$ is the set of atomic formulas of $\mathcal{L}^{P}$.

  2. (2)

$\operatorname{Cn}(\mathcal{L}^{P})=\operatorname{Cn}(\mathcal{L}^{Q})$.

  3. (3)

If $P\subseteq Q$, then $\mathcal{L}^{P}$ is a reduct of $\mathcal{L}^{Q}$.

  4. (4)

If $P$ is the disjoint union of $P_{i}\in\operatorname{Sig}$, $i\in I$, then
the tautological formula algebra of $\mathcal{L}^{P}$ is the conditionally
$\operatorname{Alg}_{m}(\mathcal{L}^{P})$-free algebra, with conditions the
union of the tautological congruences of $\mathcal{L}^{P_{i}}$, i.e.,

$\mathfrak{F}^{P}/\\!\sim^{P}\ =\
\mathfrak{Fr}(\operatorname{Alg}_{m}(\mathcal{L}^{P}),\;P,\;\cup_{i\in
I}\sim^{P_{i}}).$ (47)

  5. (5)

The class of signatures is big enough in the following sense.

    1. (a)

For any $P\in\operatorname{Sig}$ and set $H$, there is a
$P^{\prime}\in\operatorname{Sig}$ such that $P^{\prime}$ is disjoint from $H$
and $\mathcal{L}^{P^{\prime}}$ is an isomorphic copy of $\mathcal{L}^{P}$.

    2. (b)

For sets $P_{i}$, $i\in I$ from $\operatorname{Sig}$, where $I$ is nonempty,
there exist $P_{i}^{\prime}\in\operatorname{Sig}$ such that $P^{\prime}_{i}$,
$i\in I$ are pairwise disjoint, $\mathcal{L}^{P_{i}^{\prime}}$ is an
isomorphic copy of $\mathcal{L}^{P_{i}}$ and the union $\cup_{i\in
I}P_{i}^{\prime}$ belongs to $\operatorname{Sig}$.

    3. (c)

$\operatorname{Sig}$ contains at least one nonempty set.

For a class $\mathbf{L}$ as above, $\sim^{P}$ denotes the tautological
congruence relation of its member logic $\mathcal{L}^{P}$. We write

$\operatorname{Alg}_{m}(\mathbf{L})=\bigcup_{P\in\operatorname{Sig}}\operatorname{Alg}_{m}(\mathcal{L}^{P}).$
(48)

A _pre-family of logics_ is a system of logics which satisfies (1)–(3) and
(5), i.e., it may not satisfy (4). A system $\mathbf{L}$ of logics is called
_substitutional_ when all its members are substitutional, and likewise
$\mathbf{L}$ is called _conditionally substitutional_ when all logics in it
are such. $\square$

We begin discussing Definition 4.1. First we clarify that by a family
$\mathbf{L}=\langle\mathcal{L}^{P}:\;P\in\operatorname{Sig}\rangle$ we mean a
function with domain $\operatorname{Sig}$ such that this function assigns
$\mathcal{L}^{P}$ to a member $P\in\operatorname{Sig}$.121212This function is
a class-function, since $\operatorname{Sig}$ is a proper class in logic
families, as we will see soon. Thus, we can write $\mathbf{L}(P)$ in place of
$\mathcal{L}^{P}$. Condition (1) expresses that the parameter
$P\in\operatorname{Sig}$ stands for the set of atomic formulas in the
individual logics of the family. Condition (2) is in harmony with the aim that
the members of a family of logics differ only in the set of atomic formulas.
In this, a family of logics differs from the systems of logics treated in
combining logics131313For this field see, e.g., Gabbay [18], Beziau-Coniglio
[6]., where the emphasis is in changing the set of connectives of a logic.

#### Discussion of condition (3) concerning reducts.

Condition (3) requires that the subset relation in $\operatorname{Sig}$ be
reflected in the assigned logics as being a reduct. This condition is quite
extensively used in [1] (e.g., Thms. [1, 4.1.5, 4.2.20, 4.3.6]; cf. Remark [1,
3.3.30]). It expresses that when we add new atomic formulas to a logic in the
family, meaning and validity of old formulas are not changed: the logic with
the extended set of atomic formulas is a conservative extension, see
Proposition 2.8. This expresses a kind of uniformity of logics in the family.

In [1, Definition 3.3.27], a weaker condition is used. Namely, in place of
$\mathcal{L}^{P}$ being a reduct of $\mathcal{L}^{Q}$ when $P\subseteq Q$,
only $\mathcal{L}^{P}$ being a _sublogic_ of $\mathcal{L}^{Q}$ is required,
which means

$\\{\operatorname{mng}^{P}_{\mathfrak{M}}:\mathfrak{M}\in
M^{P}\\}=\\{\operatorname{mng}^{Q}_{\mathfrak{M}}\upharpoonright
F^{P}:\;\mathfrak{M}\in M^{Q}\\}.$ (49)

The difference is that in being a sublogic, only the meaning functions are
used, validity is not mentioned. Further, in principle, several models may
have the same meaning functions, which may prevent the existence of the reduct
function $f^{M}:M^{Q}\to M^{P}$ with the required properties. However, the two
notions coincide in most cases, because usually the meaning functions
determine models and validity in the following sense.

######  4.2 Definition (referential transparency, meaning-determined).

Let $\mathbf{L}=\langle\mathcal{L}^{P}:P\in\operatorname{Sig}\rangle$ be a
system of logics.

  1. (i)

We say that $\mathbf{L}$ is _referentially transparent_ if for all
$\mathfrak{A}\in\operatorname{Alg}_{m}(\mathbf{L})$ there is $T\subseteq A$
such that the following hold for all $P\in\operatorname{Sig}$ and
$\mathfrak{M}\in M^{P}$:

$\displaystyle\operatorname{mng}_{\mathfrak{M}}(\mathfrak{F}^{P})\subseteq\mathfrak{A}\
\Rightarrow\ (\forall\varphi\in
F^{P})[\mathfrak{M}\vDash\varphi\Leftrightarrow\operatorname{mng}_{\mathfrak{M}}(\varphi)\in
T].$ (50)

  2. (ii)

We say that a logic $\mathcal{L}$ is _model-slim_ , if
$\operatorname{mng}_{\mathfrak{M}}=\operatorname{mng}_{\mathfrak{N}}$ implies
that $\mathfrak{M}=\mathfrak{N}$, for all models $\mathfrak{M},\mathfrak{N}\in
M$. We say that $\mathbf{L}$ is model-slim if $\mathcal{L}^{P}$ is model-slim
for all $P\in\operatorname{Sig}$.

  3. (iii)

We say that $\mathbf{L}$ is _meaning-determined_ if it is both referentially
transparent and model-slim. $\square$

Referential transparency of $\mathbf{L}$ expresses that the meaning functions
determine validity of formulas uniformly in all logics of the system. Most
logic families are referentially transparent. In particular, both
$\mathbf{L}_{C}$ and $\mathbf{L}_{FOL}$ defined in section 5 are transparent.
More generally, all logic families with the filter property as defined in [1,
3.3.27] are transparent. Similarly, most logics are model-slim, too.

In [1, Definition 3.3.27], we require a condition similar to (3) about
isomorphisms:

  1. (6)

Any bijection $f:P\to Q$ that extends to a bijection between the tautological
formula algebras of $\mathcal{L}^{P}$ and $\mathcal{L}^{Q}$ induces an
isomorphism between $\mathcal{L}^{P}$ and $\mathcal{L}^{Q}$.

Condition (6) expresses that the tautological formula-algebras of the logics
in the system determine their logics, up to isomorphism. In a meaning-
determined system of logics, isomorphism between member-logics is equivalent
to a simpler statement, namely

$f^{F}:\mathfrak{F}^{P}\to\mathfrak{F}^{Q}\mbox{ induces an isomorphism\quad
iff \quad}\mbox{Mng}^{P}=\\{g\circ f^{F}:g\in\mbox{Mng}^{Q}\\}.$ (51)

Let us say that $f^{F}$ induces a meaning-isomorphism between
$\mathcal{L}^{P}$ and $\mathcal{L}^{Q}$ iff $\mbox{Mng}^{P}=\\{g\circ
f^{F}:g\in\mbox{Mng}^{Q}\\}$. Thus, inducing a meaning-isomorphism is weaker
than inducing an isomorphism, but they are equivalent in meaning-determined
families of logics. Let us formulate the corresponding weaker form of (6) as:

  1. (6a)

Any bijection $f:P\to Q$ that extends to a bijection between the tautological
formula algebras of $\mathcal{L}^{P}$ and $\mathcal{L}^{Q}$ induces a meaning-
isomorphism between $\mathcal{L}^{P}$ and $\mathcal{L}^{Q}$.

We omitted condition (6) in this paper, because (6a) follows from conditions
(1)-(5) used in this paper, in the case of conditionally substitutional logic
families. See Theorem 4.14. At the same time, in [1], condition (6) above is
used only in case of conditionally substitutional logics, and only in the form
of (6a) because in all properties discussed in [1], of isomorphisms only their
meaning-isomorphism parts are used. Therefore, all theorems proved in [1] for
logic families are true for the present slightly weaker notion of a logic
family, too.

#### Discussion of condition (5) on signatures.

In substitutional logics, the natural thing is that $\operatorname{Sig}$ is
the class of all sets not containing proper terms, or all infinite such sets.
The role of $\operatorname{Sig}$ is more important in first-order like logics.

Condition (5)a ensures a flexibility in renaming atomic formulas so that the
logic remains unchanged. Condition (5)a rules out, e.g.,
$\operatorname{Sig}=\\{\\{p_{i}:i<\alpha\\}:\alpha\mbox{ is an ordinal}\\}$.
In the latter, there are no disjoint sets at all, so neither (5)a nor (5)b is
satisfied.

Condition (5)b is the requirement that certain signatures can be merged. In
propositional logics usually $P\cup Q\in\operatorname{Sig}$ for
$P,Q\in\operatorname{Sig}$ since there the parameter $P$ can be any set.
However, not every logic has this feature: in first-order logic, for example,
it might happen that a relation symbol appears with different ranks in
different similarity types. In such case one might not want to have the union
of the two signatures as a signature. The problem can be dissolved by taking
isomorphic copies, that is, “renaming” the atomic formulas. This is exactly
what (5)b expresses: after appropriate “renamings” the union of the signatures
will be a signature.

In formulating (5)b, the condition that $I$ is nonempty cannot be omitted,
because without this condition (5)b would imply that the empty set is always
in $\operatorname{Sig}$ but we do not want to require this. Indeed, if
$I=\emptyset$, then $\bigcup\\{P_{i}:i\in I\\}=\bigcup\emptyset=\emptyset$.

An important feature of $\operatorname{Sig}$ is that it contains arbitrarily
large elements. Indeed, let $I$ be a arbitrary non-empty set and let
$P\in\operatorname{Sig}$ be nonempty. Such $P$ is provided by (5)c. For $i\in
I$ let $P_{i}=P$. By (5)b there are pairwise disjoint
$P_{i}^{\prime}\in\operatorname{Sig}$ for $i\in I$ such that the union
$\cup_{i\in I}P_{i}^{\prime}$ belongs to $\operatorname{Sig}$. This union must
be as large as $I$.

Condition (5)c is included to ensure arbitrarily large elements of
$\operatorname{Sig}$. Without (5)c, we would have two completely different
cases: one in which $\operatorname{Sig}\subseteq\\{\emptyset\\}$ and one in
which $\operatorname{Sig}$ has arbitrarily large elements. Item (5)c is a
natural assumption even though it could be omitted.
$\operatorname{Sig}=\\{\emptyset\\}$ is possible even in the first-order logic
case when the set of variables is empty. (Cf. Remark 3.6.) The reason we added
(5)c to the definition is to avoid adding the line “assuming
$\operatorname{Sig}\neq\\{\emptyset\\}$” to numerous statements about logic
families.

We note that in many cases, $\operatorname{Sig}$ is closed under taking
subsets. However, this is not always a feature of $\operatorname{Sig}$.
Consider classical first-order logic $\mathcal{F}\mathcal{O}\mathcal{L}$
(Definition 2.3). Given a similarity type $t$, $P_{t}$ consists of atomic
formulas of the form $r(v_{1},\ldots,v_{{t(r)}})$ for a relation symbol $r$.
Not every subset of $P_{t}$ is of form $P_{t^{\prime}}$ for some $t^{\prime}$
because if $r$ is of rank $n$, then the atomic formulas $r(v_{1},\dots,v_{n})$
have to be in $P_{t}$ for all choices $v_{1},\dots,v_{n}\in V$. For example,
the singleton $\\{r(v_{1},\ldots,v_{{t(r)}})\\}$ is not of form
$P_{t^{\prime}}$ for any $t$ when $|V|\geq 2$.

#### General logics as defined earlier.

We finish this subsection with making a comparison with the formerly used
notion of a logic family that got refined in [1, 3.3.27]. The notion of a
logic family has formerly been defined in a somewhat different way in [2,
Def.3.2.16], [3, Def.39], [7, Def.22], [15, p.63]. All these definitions are
basically equivalent with each other, for substitutional logics. Let us recall
that definition for comparison with the one presented in this paper. In [2,
Def.3.2.16] a general logic is defined to be an indexed family

$\mathbf{L}=\langle\mathcal{L}^{P}:\;P\text{ is a set}\rangle$ (52)

where $\mathcal{L}^{P}$ is a logic in the sense of Def.2.1 and the following
further stipulations hold.

  1. (i)

$P$ is the set of atomic formulas of $\mathcal{L}^{P}$.

  2. (ii)

$\operatorname{Cn}(\mathcal{L}^{P})=\operatorname{Cn}(\mathcal{L}^{Q})$.

  3. (iii)

Any bijection $f:P\to Q$ induces an isomorphism between $\mathcal{L}^{P}$ and
$\mathcal{L}^{Q}$.

  4. (iv)

For $P\subseteq Q$, the logic $\mathcal{L}^{P}$ is a sublogic of
$\mathcal{L}^{Q}$.

The main striking difference is that $\mathbf{L}$ is defined on the class all
sets rather than on a distinguished class $\operatorname{Sig}$. Items (i),
(ii) and (iv) are respectively the same as (1), (2) and (3) from Definition
4.1.141414For simplicity, assume here that all logics discussed are meaning-
determined. Condition (5) automatically holds by (iii) and
$\operatorname{Sig}$ being all sets. We will see that (4) always holds for
substitutional logic families (Corollary 4.6). Therefore, any substitutional
general logic in the old sense is a logic family in the new sense, too.

###  4.2 Discussion of condition (4) in the general case

In this subsection, we formulate a stronger version (4b) of (4) and we
characterize both by giving several equivalent statements shedding light to
different aspects of the intuition behind (4). These equivalent statements
prove to be quite useful later, e.g., in showing that (4b) is indeed stronger
than (4).

We turn to discussing condition (4) which concerns union of signatures. This
is the condition that is most restrictive and needs most explanation. This
condition is not needed in all investigations. For example, it is not used in
investigations connected to completeness of logics, but it is heavily used in
investigations connected to compactness and definability issues. See, e.g.,
[1, Sec. 4.3, 4.4] and [17, 24]. For the rest of this subsection, assume that
$P_{i},P\in\operatorname{Sig}$ for $i\in I$ and $P=\bigcup\\{P_{i}:i\in I\\}$.

The intuition behind (4) is that the logic belonging to the union $P$ does not
introduce any new relation between the atomic formulas. A bold formulation of
this intuition would be

$\sim^{P}\ \ =\ \ \cup_{i\in I}\sim^{P_{i}}.$ (4a)

So why is (4) more complicated than this?

The reason is that (4a) holds in very few logics, it does not hold even in
classical propositional logic $\mathcal{C}\mathcal{P}\mathcal{L}$. Let us take
two disjoint sets $Q$ and $R$ from $\operatorname{Sig}$. The tautological
congruence $\sim^{Q\cup R}$ might not even be generated in
$\mathfrak{F}^{Q\cup R}$ by the union of $\sim^{Q}$ and $\sim^{R}$. For
instance, in classical propositional logic if $Q=\\{q\\}$ and $R=\\{r\\}$,
then the formula $(q\to r)\vee(r\to q)$ is a tautology, i.e., it is
$\sim^{Q\cup R}$ equivalent to $\top$. On the other hand, it is not generated
by tautologies using the propositional letters $q$ or $r$ only. Thus,

$\sim^{Q\cup R}\ \neq\ \operatorname{Cg}^{\mathfrak{F}^{Q\cup
R}}(\sim^{Q}\cup\sim^{R}).$ (53)

In the above, and later in the paper, $\operatorname{Cg}^{\mathfrak{A}}(X)$
denotes the _congruence relation of $\mathfrak{A}$ generated by_ $X\subseteq
A\times A$, i.e., $\operatorname{Cg}^{\mathfrak{A}}(X)$ is the least
congruence of $\mathfrak{A}$ which contains $X$.

This example explains why our requirement in (4) is not even that the
tautological congruence of the logic belonging to the union $P=\cup P_{i}$ is
generated as a congruence by the union of the tautological congruences of the
logics belonging to the $P_{i}$’s.

In place of (4a), we need to say that $\mathcal{L}^{P}$ does not introduce any
connection between the atomic formulas of different parts that is not
compulsory for all formulas in $\mathcal{L}^{P}$. There are several ways of
expressing what we mean by compulsory connections. One way is to say that
$\langle\tau,\sigma\rangle$ is compulsory when it holds for all formulas in
place of the atomic ones. A connection $\langle\tau,\sigma\rangle\in
F^{P}\times F^{P}$ holds for all formulas in $\mathcal{L}^{P}$ when
$(h\tau,h\sigma)\in\ \sim^{P}$ for all substitutions
$h:\mathfrak{F}^{P}\to\mathfrak{F}^{P}$. Thus, the set of compulsory
connections in this sense is just the substitution-invariant part $\mbox{\sf
si}(\sim^{P})$ of $\sim^{P}$. The next condition (4b) expresses that in the
logic belonging to the union of the signatures only such compulsory
connections hold between atomic formulas coming from different signatures of
the union. That is, (4b) says that $\sim^{P}$ is generated as a congruence by
$\cup_{i\in I}\sim^{P_{i}}\cup\,\mbox{\sf si}(\sim^{P})$ in
$\mathfrak{F}^{P}$,

$\sim^{P}=\operatorname{Cg}^{\mathfrak{F}^{P}}(\cup_{i\in
I}\sim^{P_{i}}\cup\,\mbox{\sf si}(\sim^{P})).$ (4b)

Theorem 4.3 below lists some statements equivalent to (4b). Among others, it
states that (4b) is equivalent to condition (6) in the definition of a general
logic in [1, Definition 3.3.27].

Condition (4) in the definition of a logic family in the present paper is
somewhat weaker than (4b) above, see Theorem 4.10. Our reason for using in
this paper the weaker condition is that it turns out that the weaker (4)
suffices in almost all situations, in particular, in the proofs in [1] we
always use the weaker (4) in place of the stronger (4b). Further, Theorem 4.13
may suggest that (4) is more useful than (4b) in logic families.

Before stating Theorem 4.3, we recall condition (6) from [1, Definition
3.3.27]. The condition says that $\sim^{P}$ and $\cup_{i\in I}\sim^{P_{i}}$
generate the same congruences in the $P$-freely generated
$\operatorname{Alg}_{m}(\mathcal{L}^{P})$-free algebra
$\mathfrak{Fr}(\operatorname{Alg}_{m}(\mathcal{L}^{P}),P)$. We need to clarify
this condition, because $\sim^{P}$ and $\cup_{i\in I}\sim^{P_{i}}$ are not
binary relations on
$\mathfrak{Fr}(\operatorname{Alg}_{m}(\mathcal{L}^{P}),P)$, they are binary
relations on the formula algebra $\mathfrak{F}^{P}$.

The most natural way of transferring a binary relation $R$ on an algebra to
its homomorphic image, say by $f$, is to define $f(R)=\\{\langle
f(a),f(b)\rangle:\langle a,b\rangle\in R\\}$. Using this, the tautological
congruences of the formula algebras can be transferred to congruences of the
$\operatorname{Alg}_{m}(\mathcal{L})$-free algebra as follows.

For any $Q\in\operatorname{Sig}$ let
$\mu^{Q}:\mathfrak{F}^{Q}\to\mathfrak{Fr}(\operatorname{Alg}_{m}(\mathcal{L}^{Q}),Q)$
be the homomorphic extension of the identity mapping $id:Q\to Q$, i.e.,
$\mu^{Q}(\tau)=\tau/C$, where
$\mathfrak{Fr}(\operatorname{Alg}_{m}(\mathcal{L}^{Q}),Q)$ is the factor-
algebra of $\mathfrak{F}^{Q}$ by the congruence $C$. Define $\backsim^{Q}$ as
the $\mu^{Q}$-image of $\sim^{Q}$, that is,

$\backsim^{Q}=\\{\langle\mu^{Q}(\varphi),\mu^{Q}(\psi)\rangle:\;\varphi\sim^{Q}\psi\\}.$
(54)

Observe the difference between the symbols $\sim$ and $\backsim$. The
surjective homomorphic image of a congruence is not necessarily a congruence,
as transitivity can be violated.151515In general, surjective homomorphic
images of congruences are only tolerance relations: reflexive, symmetric and
compatible. However, in the present case $\backsim^{Q}$ is a congruence,
because the kernel of $\mu^{Q}$ is contained in $\sim^{Q}$ as $\sim^{Q}$ is
defined by the intersection of kernels of meaning homomorphisms, which are
homomorphisms from the free algebra to members of
$\operatorname{Alg}_{m}(\mathcal{L}^{Q})$. Indeed, an alternative way would be
to define $\backsim^{Q}$ as follows. As
$\mathfrak{Fr}(\operatorname{Alg}_{m}(\mathcal{L}^{Q}),Q)$ has the universal
mapping property with respect to the class
$\operatorname{Alg}_{m}(\mathcal{L}^{Q})$, for any model $\mathfrak{M}\in
M^{Q}$ there is a homomorphism
$m_{\mathfrak{M}}^{Q}:\mathfrak{Fr}(\operatorname{Alg}_{m}(\mathcal{L}^{Q}),Q)\to\operatorname{mng}_{\mathfrak{M}}^{Q}(\mathfrak{F}^{Q})$
such that
$m_{\mathfrak{M}}^{Q}\circ\mu^{Q}=\operatorname{mng}_{\mathfrak{M}}^{Q}$,
i.e., the diagram below commutes.

${\mathfrak{F}^{Q}}$${\mathfrak{Fr}(\operatorname{Alg}_{m}(\mathcal{L}^{Q}),Q)}$${\operatorname{mng}_{\mathfrak{M}}^{Q}(\mathfrak{F}^{Q})}$$\scriptstyle{\mu^{Q}}$$\scriptstyle{\operatorname{mng}_{\mathfrak{M}}^{Q}}$$\scriptstyle{m_{\mathfrak{M}}^{Q}}$

It is not hard to check that

$\mu^{Q}(\varphi)\backsim^{Q}\mu^{Q}(\psi)\;\text{ if and only if
}\;(\forall\mathfrak{M}\in
M^{Q})\;m^{Q}_{\mathfrak{M}}(\mu^{Q}(\varphi))=m^{Q}_{\mathfrak{M}}(\mu^{Q}(\psi)),$
(55)

that is, $\backsim^{Q}$ is $\bigcap_{\mathfrak{M}\in
M^{Q}}\ker(m_{\mathfrak{M}}^{Q})$. Notice that $\varphi\sim^{R}\psi$ if and
only if $\mu^{R}(\varphi)\backsim^{R}\mu^{R}(\psi)$.

We turn to characterizing conditions (4b) and (4). By characterizing we mean
listing equivalent conditions that highlight different aspects. The notion of
a $\mathsf{K}$-free product of algebras will be used in the characterizations.
A free product is a special conditionally free algebra, see [19, end of
0.4.65], it is introduced in [22]. Let $\mathsf{K}$ be a class of similar
algebras and let $\mathfrak{A}_{i}$ for $i\in I$ be algebras. An algebra
$\mathfrak{A}$ is the _$\mathsf{K}$ -free product of
$\langle\mathfrak{A}_{i}:i\in I\rangle$_ if the following three conditions
hold: (a) $\mathfrak{A}_{i}$ is a subalgebra of $\mathfrak{A}$, for all $i\in
I$, (b) $\mathfrak{A}$ is generated by the union of the universes of
$\mathfrak{A}_{i},i\in I$ and (c) for any $\mathfrak{B}\in\mathsf{K}$ any
family of homomorphisms $f_{i}:\mathfrak{A}_{i}\to\mathfrak{B}$ can be
extended to a homomorphism $f:\mathfrak{A}\to\mathfrak{B}$ such that
$f\supseteq\cup\\{f_{i}:i\in I\\}$. It can be checked that $\mathfrak{A}$ is
unique up to isomorphism when $\mathfrak{A}\in\mathsf{K}$ is required.

We begin with characterizing the stronger condition. The following theorem
lists some conditions equivalent to (4b). In it, (i) is the same as (4b) and
(ii) is the same as (6) in [1, 3.3.27]. Note that (i) is a condition that is
formulated in terms of syntactic-oriented notions, without the use of
$\operatorname{Alg}_{m}(\mathcal{L})$.

######  4.3 Theorem (characterization of (4b)).

Let $\mathbf{L}=\langle\mathcal{L}^{P}:\;P\in\operatorname{Sig}\rangle$ be a
pre-family of logics. Let $P_{i}\in\operatorname{Sig}$ be sets for $i\in I$
such that the union $P=\bigcup_{i\in I}P_{i}$ belongs to $\operatorname{Sig}$.
Conditions (i)-(iv) below are equivalent. Further, (i) holding for all
$P_{i}\in\operatorname{Sig}$ such that $\cup_{i\in
I}P_{i}\in\operatorname{Sig}$ is equivalent to (v) holding for all such
$P_{i},i\in I$, and to (vi) holding for all such $P_{i},i\in I$.

  1. (i)

$\sim^{P}=\operatorname{Cg}^{\mathfrak{F}^{P}}(\cup_{i\in
I}\sim^{P_{i}}\cup\,\mbox{\sf si}(\sim^{P}))$.

  2. (ii)

$\operatorname{Cg}^{\mathfrak{Fr}(\operatorname{Alg}_{m}(\mathcal{L}^{P}),P)}(\backsim^{P})\
=\
\operatorname{Cg}^{\mathfrak{Fr}(\operatorname{Alg}_{m}(\mathcal{L}^{P}),P)}(\cup_{i\in
I}\backsim^{P_{i}})$.

  3. (iii)

$\big{(}\forall
h\in\operatorname{Hom}(\mathfrak{F}^{P},\mathbf{HSP}\operatorname{Alg}_{m}(\mathcal{L}^{P}))\big{)}\big{(}\;\cup\\!\sim^{P_{i}}\subseteq\ker(h)\
\;\Longrightarrow\;\ \sim^{P}\subseteq\ker(h)\;\big{)}$.

  4. (iv)

$\mathfrak{F}^{P}/\\!\sim^{P}$ is an
$\mathbf{HSP}\operatorname{Alg}_{m}(\mathcal{L}^{P})$-free product of the
$\mathfrak{F}^{P_{i}}/\\!\sim^{P_{i}}$ for $i\in I$.

  5. (v)

$\big{(}\forall
h\in\operatorname{Hom}(\mathfrak{F}^{P},\mathbf{HSP}\operatorname{Alg}_{m}(\mathbf{L}))\big{)}\big{(}\;\cup\\!\sim^{P_{i}}\subseteq\ker(h)\
\;\Longrightarrow\;\ \sim^{P}\subseteq\ker(h)\;\big{)}$.

  6. (vi)

$\mathfrak{F}^{P}/\\!\sim^{P}$ is an
$\mathbf{HSP}\operatorname{Alg}_{m}(\mathbf{L})$-free product of the
$\mathfrak{F}^{P_{i}}/\\!\sim^{P_{i}}$ for $i\in I$.

Proof . Note first that $\cup_{i\in I}\sim^{P_{i}}\subseteq\ \sim^{P}$ by
Proposition 2.8(i) and Definition 4.1(3), and thus $\cup_{i\in
I}\backsim^{P_{i}}\subseteq\ \backsim^{P}$. We start with a general lemma that
we will make use of in this proof and also in the proof of Theorem 4.7 below.

######  4.4 Lemma.

For any class $\mathsf{K}$ of similar algebras, (a) and (b) below are
equivalent.

  1. (a)

$\big{(}\forall
h\in\operatorname{Hom}(\mathfrak{F}^{P},\mathsf{K})\big{)}\big{(}\;\cup\\!\sim^{P_{i}}\subseteq\ker(h)\
\;\Longrightarrow\;\ \sim^{P}\subseteq\ker(h)\;\big{)}$.

  2. (b)

$\mathfrak{F}^{P}/\\!\sim^{P}$ is a $\mathsf{K}$-free product of the
$\mathfrak{F}^{P_{i}}/\sim^{P_{i}}$ for $i\in I$.

Proof of Lemma 4.4. Proof of (a)$\Rightarrow$(b): By Proposition 2.8(i),
$\mathfrak{F}^{P_{i}}/\\!\sim^{P_{i}}$ for $i\in I$ can be considered as
subalgebras of $\mathfrak{F}^{P}/\\!\sim^{P}$ that generate
$\mathfrak{F}^{P}/\\!\sim^{P}$. Take any $\mathfrak{B}\in\mathsf{K}$ and
homomorphisms $f_{i}:\mathfrak{F}^{P_{i}}/\\!\sim^{P_{i}}\;\to\mathfrak{B}$.
Let $q_{i}:\mathfrak{F}^{P_{i}}\to\mathfrak{F}^{P_{i}}/\\!\sim^{P_{i}}$ be the
quotient mappings. By the universal mapping property of $\mathfrak{F}^{P_{i}}$
there are $h_{i}:\mathfrak{F}^{P_{i}}\to\mathfrak{B}$ such that
$h_{i}=f_{i}\circ q_{i}$ for $i\in I$.

${\mathfrak{F}^{P_{i}}}$${\mathfrak{F}^{P_{i}}/\\!\sim^{P_{i}}}$${\mathfrak{B}}$$\scriptstyle{h_{i}}$$\scriptstyle{q_{i}}$$\scriptstyle{f_{i}}$${\mathfrak{F}^{P}}$${\mathfrak{F}^{P}/\\!\sim^{P}}$${\mathfrak{B}}$$\scriptstyle{h}$$\scriptstyle{q}$$\scriptstyle{f}$

Let $h:\mathfrak{F}^{P}\to\mathfrak{B}$ be the homomorphic extension of
$\cup_{i\in I}h_{i}$. As $\sim^{P_{i}}\subseteq\ker(h_{i})$ for each $i\in I$,
it follows that $\cup_{i\in I}\sim^{P_{i}}\subseteq\ker(h)$. By (a),
$\ker(q)=\;\sim^{P}\subseteq\ker(h)$. Thus, there is
$f:\mathfrak{F}^{P}/\\!\sim^{P}\to\mathfrak{B}$ such that $f\circ q=h$.
Clearly $\cup\\{f_{i}:i\in I\\}\subseteq f$.

Proof of (b)$\Rightarrow$(a): Take any
$h:\mathfrak{F}^{P}\to\mathfrak{A}\in\mathsf{K}$ and suppose $\cup_{i\in
I}\sim^{P_{i}}\subseteq\ker(h)$. Write $h_{i}=h\upharpoonright F^{P}_{i}$,
$h_{i}:\mathfrak{F}^{P_{i}}\to\mathfrak{A}$. Clearly
$\sim^{P_{i}}\subseteq\ker(h_{i})$, and thus (by the second isomorphism
theorem, see e.g. [5, Thm. 3.5]) there are surjective homomorphisms
$f_{i}:\mathfrak{F}^{P_{i}}/\\!\sim^{P_{i}}\to\mathfrak{A}$. Using (b) and
properties of the free product, there is a surjective
$f:\mathfrak{F}^{P}/\\!\sim^{P}\to\mathfrak{A}$ such that
$f\supseteq\cup\\{f_{i}:i\in I\\}$. If
$q:\mathfrak{F}^{P}\to\mathfrak{F}^{P}/\\!\sim^{P}$ is the quotient mapping,
then $f\circ q=h$, showing that $\sim^{P}\subseteq\ker(h)$. $\blacksquare$

Let us continue the proof of Theorem 4.3. The equivalences
(iii)$\Leftrightarrow$(iv) and (v)$\Leftrightarrow$(vi) follow from Lemma 4.4
with $\mathsf{K}$ being $\mathbf{HSP}\operatorname{Alg}_{m}(\mathcal{L}^{P})$
in the first equivalence, and $\mathbf{HSP}\operatorname{Alg}_{m}(\mathbf{L})$
in the second. In what follows, we write
$\mathsf{K}=\operatorname{Alg}_{m}(\mathcal{L}^{P})$ and
$\mathfrak{Fr}^{P}=\mathfrak{Fr}(\operatorname{Alg}_{m}(\mathcal{L}^{P}),P)$.

Proof of (ii)$\Rightarrow$(iii): Let
$h:\mathfrak{F}^{P}\to\mathfrak{A}\in\mathbf{HSP}\mathsf{K}$ be a homomorphism
and write $\mu:\mathfrak{F}^{P}\to\mathfrak{Fr}^{P}$ for the quotient mapping
(cf. the lines above (54)). $\mathfrak{Fr}^{P}$ has the universal mapping
property with respect to the class $\mathbf{HSP}\mathsf{K}$, thus there is
$f:\mathfrak{Fr}^{P}\to\mathfrak{A}$ such that $h=f\circ\mu$. Now, if
$\cup_{i\in I}\sim^{P_{i}}\subseteq\ker(h)$, then
$\operatorname{Cg}^{\mathfrak{Fr}^{P}}(\cup_{i\in
I}\backsim^{P_{i}})\subseteq\ker(f)$. By (ii) then
$\backsim^{P}\subseteq\ker(f)$ and thus $\sim^{P}\subseteq\ker(h)$.

Proof of (i)$\Rightarrow$(ii): We prove the following more general statement.
Suppose $\Psi\subseteq\Pi$ are binary relations over an algebra $\mathfrak{A}$
and $\Sigma$ is a congruence of $\mathfrak{A}$. Let
$q:\mathfrak{A}\to\mathfrak{A}/\Sigma$ be the quotient mapping. Then

$\displaystyle\operatorname{Cg}^{\mathfrak{A}}(\Pi)=\operatorname{Cg}^{\mathfrak{A}}(\Psi\cup\Sigma)\qquad\Rightarrow\qquad\operatorname{Cg}^{\mathfrak{A}/\Sigma}(q(\Pi))=\operatorname{Cg}^{\mathfrak{A}/\Sigma}(q(\Psi)).$
(56)

From Theorem 2.4(ii) we know that $\mathfrak{Fr}^{P}$ equals
$\mathfrak{F}^{P}/\mbox{\sf si}(\sim^{P})$, therefore applying (56) with
$\mathfrak{A}=\mathfrak{F}^{P}$, $\Pi=\;\sim^{P}$, $\Sigma=\mbox{\sf
si}(\sim^{P})$, and $\Psi=\cup_{i\in I}\sim^{P_{i}}$ yields the proof of
(i)$\Rightarrow$(ii). Let us prove (56). Assume that
$\operatorname{Cg}^{\mathfrak{A}}(\Pi)=\operatorname{Cg}^{\mathfrak{A}}(\Psi\cup\Sigma)$
holds. The inclusion
$\operatorname{Cg}^{\mathfrak{A}/\Sigma}(q(\Pi))\supseteq\operatorname{Cg}^{\mathfrak{A}/\Sigma}(q(\Psi))$
is straightforward from the assumption $\Psi\subseteq\Pi$. For the converse
inclusion pick $x,y\in A$ and assume $\langle
x/\Sigma,y/\Sigma\rangle\in\operatorname{Cg}^{\mathfrak{A}/\Sigma}(q(\Pi))$.
Then $\langle x,y\rangle\in\operatorname{Cg}^{\mathfrak{A}}(\Pi)$ and thus
$\langle x,y\rangle\in\operatorname{Cg}^{\mathfrak{A}}(\Psi\cup\Sigma)$.
Universal algebra shows (see e.g. [5, Exercise 3.9/2])

$\displaystyle
q\big{(}\operatorname{Cg}^{\mathfrak{A}}(\Psi\cup\Sigma)\big{)}\ =\
\operatorname{Cg}^{\mathfrak{A}/\Sigma}(q(\Psi)).$ (57)

Therefore $\langle
x/\Sigma,y/\Sigma\rangle\in\operatorname{Cg}^{\mathfrak{A}/\Sigma}(q(\Psi))$
as desired.

Proof of (iv)$\Rightarrow$(i): As we noted at the very beginning of this
proof, $\cup_{i\in I}\sim^{P_{i}}\subseteq\;\sim^{P}$, and by definition
$\mbox{\sf si}(\sim^{P})\subseteq\;\sim^{P}$. Hence, the inclusion $\supseteq$
in (i) is straightforward. To prove the reverse inclusion, take an arbitrary
congruence $\vartheta\supseteq\cup_{i\in I}\sim^{P_{i}}\cup\,\mbox{\sf
si}(\sim^{P})$. We need to show that $\sim^{P}\subseteq\vartheta$. Using that
$\mbox{\sf si}(\sim^{P_{i}})\subseteq\vartheta$, by the second isomorphism
theorem, $\mathfrak{F}^{P}/\vartheta$ is a homomorphic image of
$\mathfrak{F}^{P}/\mbox{\sf si}(\sim^{P})$, which latter algebra is the free
algebra $\mathfrak{Fr}^{P}$ (by Theorem 2.4(ii)). In particular,
$\mathfrak{F}^{P}/\vartheta$ belongs to $\mathbf{HSP}\mathsf{K}$. Similarly,
using that $\sim^{P_{i}}\subseteq\vartheta$ for $i\in I$, there are surjective
homomorphisms
$f_{i}:\mathfrak{F}^{P_{i}}/\\!\sim^{P_{i}}\to\mathfrak{F}^{P}/\vartheta$. Let
$f:\mathfrak{F}^{P}/\\!\sim^{P}\to\mathfrak{F}^{P}/\vartheta$ be the
homomorphism from the free product property satisfying
$f\supseteq\cup\\{f_{i}:i\in I\\}$. As the
$\mathfrak{F}^{P_{i}}/\\!\sim^{P_{i}}$, taken as subalgebras, generate
$\mathfrak{F}^{P}/\\!\sim^{P}$ (by the free product property), $f$ must be
surjective. Therefore, $\sim^{P}\subseteq\vartheta$, as desired.

${\mathfrak{F}^{P}}$${\mathfrak{F}^{P}/\vartheta}$${\mathfrak{F}^{P}/\mbox{\sf
si}(\sim^{P})}$$\scriptstyle{q}$$\scriptstyle{\mu}$${\mathfrak{F}^{P_{i}}}$${\mathfrak{F}^{P}/\vartheta}$${\mathfrak{F}^{P_{i}}/\\!\sim^{P_{i}}}$$\scriptstyle{q}$$\scriptstyle{\mu_{i}}$$\scriptstyle{f_{i}}$

Finally, that (iii) holding for all $P_{i}\in\operatorname{Sig}$ such that
$P=\cup P_{i}\in\operatorname{Sig}$ is equivalent to (v) holding for all such
$P_{i}$, $i\in I$ follows from the lemma below with the choice
$\mathbf{T}=\mathbf{HSP}$.

######  4.5 Lemma.

Let $\mathbf{T}\in\\{\mathbf{SP},\mathbf{HSP}\\}$ be a class operator. The
following are equivalent.

  1. (a)

For every $P_{i}\in\operatorname{Sig}$ for $i\in I$ such that $P=\cup_{i\in
I}P_{i}\in\operatorname{Sig}$,

$\displaystyle\big{(}\forall
h\in\operatorname{Hom}(\mathfrak{F}^{P},\mathbf{T}\operatorname{Alg}_{m}(\mathcal{L}^{P}))\big{)}\big{(}\;\cup\\!\sim^{P_{i}}\subseteq\ker(h)\
\;\Longrightarrow\;\ \sim^{P}\subseteq\ker(h)\;\big{)}$ (58)

  2. (b)

For every $P_{i}\in\operatorname{Sig}$ for $i\in I$ such that $P=\cup_{i\in
I}P_{i}\in\operatorname{Sig}$,

$\displaystyle\big{(}\forall
h\in\operatorname{Hom}(\mathfrak{F}^{P},\mathbf{T}\operatorname{Alg}_{m}(\mathbf{L}))\big{)}\big{(}\;\cup\\!\sim^{P_{i}}\subseteq\ker(h)\
\;\Longrightarrow\;\ \sim^{P}\subseteq\ker(h)\;\big{)}$ (59)

Proof of Lemma 4.5. The direction (b)$\Rightarrow$(a) is immediate from
$\operatorname{Alg}_{m}(\mathcal{L}^{P})\subseteq\operatorname{Alg}_{m}(\mathbf{L})$.
Conversely, for the (a)$\Rightarrow$(b) direction, let
$h:\mathfrak{F}^{P}\to\mathfrak{A}\in\mathbf{T}\operatorname{Alg}_{m}(\mathbf{L})$
be such that $\cup_{i\in I}\sim^{P_{i}}\subseteq\ker(h)$. There are
$Q_{j}^{\prime\prime}\in\operatorname{Sig}$ and
$\mathfrak{A}_{j}\in\operatorname{Alg}_{m}(\mathcal{L}^{Q_{j}^{\prime\prime}})$
for $j\in J$ such that $\mathfrak{A}\in\mathbf{T}\\{\mathfrak{A}_{j}:j\in
J\\}$. Without loss of generality we can assume that $I=J$. By Def. 4.1(5),
for each $i\in I$ there are
$P_{i}^{\prime},Q_{i}^{\prime}\in\operatorname{Sig}$ such that
$P_{i}^{\prime}\cup Q_{i}^{\prime}\in\operatorname{Sig}$ and
$P_{i}^{\prime},Q_{i}^{\prime}$ are isomorphic copies respectively of $P_{i}$
and $Q_{i}^{\prime\prime}$. Apply 4.1(5) again to $P_{i}^{\prime}\cup
Q_{i}^{\prime}$ to get $Q_{i}\in\operatorname{Sig}$ such that $\cup_{i\in
I}Q_{i}\in\operatorname{Sig}$ and $Q_{i}$ contains an isomorphic copy of
$P_{i}$ and $Q_{i}^{\prime\prime}$. To simplify notation we do not denote the
isomorphisms between these respective logics, but instead we can assume that
for $i\in I$,

$\displaystyle Q_{i}\in\operatorname{Sig},\quad P_{i}\subseteq Q_{i},\quad
Q=\cup_{i\in
I}Q_{i}\in\operatorname{Sig},\quad\mathfrak{A}\in\mathbf{T}\operatorname{Alg}_{m}(\mathcal{L}^{Q}).$
(60)

Let $h_{i}=h\upharpoonright F^{P_{i}}:\mathfrak{F}^{P_{i}}\to\mathfrak{A}$. By
assumption, $\sim^{P_{i}}\subseteq\ker(h_{i})$. As $P_{i}\subseteq Q_{i}$ and
$\mathfrak{F}^{Q_{i}}$ is an absolutely free algebra, there are
$k_{i}:\mathfrak{F}^{Q_{i}}\to\mathfrak{A}$ such that
$\sim^{Q_{i}}\subseteq\ker(k_{i})$ and $k_{i}\upharpoonright F^{P_{i}}=h_{i}$
for $i\in I$. Let $k:\mathfrak{F}^{Q}\to\mathfrak{A}$ be such that
$k\supseteq\cup\\{k_{i}:i\in I\\}$. Then

$\displaystyle
k:\mathfrak{F}^{Q}\to\mathbf{T}\operatorname{Alg}_{m}(\mathcal{L}^{Q}),\text{
and }\cup_{i\in I}\sim^{Q_{i}}\subseteq\ker(k),$ (61)

and we assumed that (a) holds whenever $Q_{i}\in\operatorname{Sig}$ are such
that $\cup Q_{i}\in\operatorname{Sig}$. Therefore, $\sim^{Q}\subseteq\ker(k)$.
Notice that $k\upharpoonright F^{P}=h$, and by Proposition 2.8,
$\sim^{P}=\sim^{Q}\upharpoonright F^{P}$. Hence, $\sim^{P}\subseteq\ker(h)$.
$\blacksquare$

The proof of Theorem 4.3 is completed. $\blacksquare$

Theorem 4.3(i) yields that condition (4) is not needed in the substitutional
case.

######  4.6 Corollary.

Substitutional pre-families of logics are always families of logics with the
stronger condition (4b).

Proof . That $\sim^{P}=\mbox{\sf si}(\sim^{P})$ when $\mathcal{L}^{P}$ is
substitutional, by Proposition 3.3, together with that $\cup_{i\in
I}\sim^{P_{i}}\subseteq\ \sim^{P}$, by Proposition 2.8(i) and Definition
4.1(3), immediately imply (4b). $\blacksquare$

We turn to formulating some conditions equivalent to the weaker condition (4).
Recall the notion of the largest sound and substitutional deductive system
$\vdash_{\mathcal{L}}$ belonging to a logic $\mathcal{L}$, from above Theorem
2.5. Note that (i) is analogous to Theorem 4.3(i) and (ii) is equivalent to
(4) by Theorem 2.4(i).

######  4.7 Theorem (characterization of (4)).

Let $\mathbf{L}=\langle\mathcal{L}^{P}:\;P\in\operatorname{Sig}\rangle$ be a
pre-family of logics. Let $P_{i}\in\operatorname{Sig}$ be sets for $i\in I$
such that the union $P=\bigcup_{i\in I}P_{i}$ belongs to $\operatorname{Sig}$.
Conditions (i)-(vi) are equivalent. Further, (i) holding for all
$P_{i}\in\operatorname{Sig}$ such that $\cup_{i\in
I}P_{i}\in\operatorname{Sig}$ is equivalent to (vii) holding for all such
$P_{i},i\in I$, and to (viii) holding for all such $P_{i},i\in I$.

  1. (i)

$\sim^{P}$ is the $\vdash_{\mathcal{L}^{P}}$-closure of $\cup_{i\in
I}\sim^{P_{i}}$.

  2. (ii)

$\mathfrak{Fr}(\operatorname{Alg}_{m}(\mathcal{L}^{P}),\;P,\;\cup\\!\sim^{P_{i}})\
=\ \mathfrak{Fr}(\operatorname{Alg}_{m}(\mathcal{L}^{P}),\;P,\;\sim^{\cup
P_{i}})$.

  3. (iii)

$\big{(}\forall
h\in\operatorname{Hom}(\mathfrak{F}^{P},\operatorname{Alg}_{m}(\mathcal{L}^{P}))\big{)}\big{(}\;\cup\\!\sim^{P_{i}}\subseteq\ker(h)\
\;\Longrightarrow\;\ \sim^{P}\subseteq\ker(h)\;\big{)}$.

  4. (iv)

$\big{(}\forall
h\in\operatorname{Hom}(\mathfrak{F}^{P},\mathbf{SP}\operatorname{Alg}_{m}(\mathcal{L}^{P}))\big{)}\big{(}\;\cup\\!\sim^{P_{i}}\subseteq\ker(h)\
\;\Longrightarrow\;\ \sim^{P}\subseteq\ker(h)\;\big{)}$.

  5. (v)

$\mathfrak{F}^{P}/\\!\sim^{P}$ is an
$\operatorname{Alg}_{m}(\mathcal{L}^{P})$-free product of the
$\mathfrak{F}^{P_{i}}/\\!\sim^{P_{i}}$ for $i\in I$.

  6. (vi)

$\mathfrak{F}^{P}/\\!\sim^{P}$ is an
$\mathbf{SP}\operatorname{Alg}_{m}(\mathcal{L}^{P})$-free product of the
$\mathfrak{F}^{P_{i}}/\\!\sim^{P_{i}}$ for $i\in I$.

  7. (vii)

$\big{(}\forall
h\in\operatorname{Hom}(\mathfrak{F}^{P},\mathbf{SP}\operatorname{Alg}_{m}(\mathbf{L}))\big{)}\big{(}\;\cup\\!\sim^{P_{i}}\subseteq\ker(h)\
\;\Longrightarrow\;\ \sim^{P}\subseteq\ker(h)\;\big{)}$.

  8. (viii)

$\mathfrak{F}^{P}/\\!\sim^{P}$ is an
$\mathbf{SP}\operatorname{Alg}_{m}(\mathbf{L})$-free product of the
$\mathfrak{F}^{P_{i}}/\\!\sim^{P_{i}}$ for $i\in I$.

Proof . Note first that $\cup_{i\in I}\sim^{P_{i}}\subseteq\ \sim^{P}$ by
Proposition 2.8(i) and Definition 4.1(3).

Proof of (i)$\Leftrightarrow$(iii): Let
$h:\mathfrak{F}^{P}\to\mathfrak{A}\in\operatorname{Alg}_{m}(\mathcal{L}^{P})$
be a homomorphism. We claim first that $\ker(h)$ is
$\vdash_{\mathcal{L}^{P}}$-closed.

######  4.8 Claim.

$\ker(h)$ is $\vdash_{\mathcal{L}^{P}}$-closed for every
$h:\mathfrak{F}^{P}\to\mathfrak{A}\in\operatorname{Alg}_{m}(\mathcal{L}^{P})$.

Proof of Claim 4.8. Recall that $\vdash_{\mathcal{L}^{P}}$-closedness of
$\ker(h)$ means that if $H\subseteq\ker(h)$ and
$H\vdash_{\mathcal{L}^{P}}\langle\tau,\sigma\rangle$, i.e.

$\displaystyle(\forall
f:\mathfrak{F}^{P}\to\mathfrak{F}^{P})(\forall\mathfrak{N}\in
M^{P})\big{[}f(H)\subseteq\ker(\operatorname{mng}_{\mathfrak{N}})\Rightarrow\langle
f\tau,f\sigma\rangle\in\ker(\operatorname{mng}_{\mathfrak{N}})\big{]},$ (62)

then $\langle\tau,\sigma\rangle\in\ker(h)$. Let $\mathfrak{M}\in M^{P}$ be
such that $\mathfrak{A}=\operatorname{mng}_{\mathfrak{M}}(\mathfrak{F}^{P})$.
There is a homomorphism $s:\mathfrak{F}\to\mathfrak{F}$ such that
$h=\operatorname{mng}_{\mathfrak{M}}\circ\;s$. To obtain such $s$, note that
for each $p\in P$ there is $\psi_{p}\in F^{P}$ such that
$h(p)=\operatorname{mng}_{\mathfrak{M}}(\psi_{p})$. Take then $s$ to be the
homomorphic extension of the mapping $p\mapsto\psi_{p}$.

${\mathfrak{F}^{P}}$${\operatorname{mng}_{\mathfrak{M}}(\mathfrak{F}^{P})}$${\mathfrak{F}^{P}}$$\scriptstyle{h}$$\scriptstyle{s}$$\scriptstyle{\operatorname{mng}_{\mathfrak{M}}}$

Let now $H\subseteq\ker(h)$ and assume
$H\vdash_{\mathcal{L}^{P}}\langle\tau,\sigma\rangle$. Then (62) with $f=s$ and
$\mathfrak{N}=\mathfrak{M}$ gives

$\displaystyle
s(H)\subseteq\ker(\operatorname{mng}_{\mathfrak{M}})\quad\Rightarrow\quad\langle
s\tau,s\sigma\rangle\in\ker(\operatorname{mng}_{\mathfrak{M}}),$

that is,

$\displaystyle H\subseteq\ker(\operatorname{mng}_{\mathfrak{M}}\circ
s)\Rightarrow\langle\tau,\sigma\rangle\in\ker(\operatorname{mng}_{\mathfrak{M}}\circ
s).$

As $\operatorname{mng}_{\mathfrak{M}}\circ s$ equals $h$, and
$H\subseteq\ker(h)$ by assumption, we get
$\langle\tau,\sigma\rangle\in\ker(h)$. $\blacksquare$

Let us continue proving the equivalence (i)$\Leftrightarrow$(iii). Assume (i)
and let $h:\mathfrak{F}^{P}\to\operatorname{Alg}_{m}(\mathcal{L}^{P})$ be such
that $\cup\sim^{P_{i}}\subseteq\ker(h)$. As $\ker(h)$ is
$\vdash_{\mathcal{L}^{P}}$-closed, by Claim 4.8, and $\sim^{P}$ is the
smallest $\vdash_{\mathcal{L}^{P}}$-closed set containing $\cup\sim^{P_{i}}$,
we get $\sim^{P}\subseteq\ker(h)$. For the converse direction, assume (iii)
holds. It is enough to show that

$\displaystyle\cup\sim^{P_{i}}\
\vdash_{\mathcal{L}^{P}}\;\langle\tau,\sigma\rangle\quad\text{ for each
}\langle\tau,\sigma\rangle\in\;\sim^{P}.$ (63)

Indeed, if $\cup\\!\sim^{P_{i}}\;\subseteq\Sigma$ is closed, then (63) ensures
that $\sim^{P}\subseteq\Sigma$. To prove (63), let
$\langle\tau,\sigma\rangle\in\sim^{P}$ and take arbitrary
$f:\mathfrak{F}^{P}\to\mathfrak{F}^{P}$ and $\mathfrak{M}\in M^{P}$. We need
to check that

$\displaystyle\text{if }\
\cup\sim^{P_{i}}\subseteq\ker(\operatorname{mng}_{\mathfrak{M}}\circ f),\text{
then }\
\langle\tau,\sigma\rangle\in\ker(\operatorname{mng}_{\mathfrak{M}}\circ f).$
(64)

But $\operatorname{mng}_{\mathfrak{M}}\circ f$ is a homomorphism from
$\mathfrak{F}^{P}$ into $\operatorname{Alg}_{m}(\mathcal{L}^{P})$, and thus
(64) is ensured by (iii).

To prove the rest of the equivalences we make use of the following lemma.

######  4.9 Lemma.

For any class $\mathsf{K}$ of similar algebras, (a) and (b) below are
equivalent.

  1. (a)

$\mathfrak{Fr}(\mathsf{K},\;P,\;\cup\\!\sim^{P_{i}})\ =\
\mathfrak{Fr}(\mathsf{K},\;P,\;\sim^{\cup P_{i}})$.

  2. (b)

$\big{(}\forall
h\in\operatorname{Hom}(\mathfrak{F}^{P},\mathsf{K})\big{)}\big{(}\;\cup\\!\sim^{P_{i}}\subseteq\ker(h)\
\;\Longleftrightarrow\;\ \sim^{P}\subseteq\ker(h)\;\big{)}$.

Proof of Lemma 4.9. (b) is equivalent to
$\operatorname{Hom}(\mathsf{K},P,\cup\sim^{P_{i}})=\operatorname{Hom}(\mathsf{K},P,\sim^{P})$,
while (a) is equivalent to $\mbox{\sf
Cr}(\mathsf{K},P,\cup\sim^{P_{i}})=\mbox{\sf Cr}(\mathsf{K},P,\sim^{P})$. The
statement follows from that
$\mathfrak{Fr}(\mathsf{K},P,S)=\mathfrak{F}^{P}/\mbox{\sf Cr}(\mathsf{K},P,S)$
and $\mbox{\sf
Cr}(\mathsf{K},P,S)=\cap\\{\ker(h):\;h\in\operatorname{Hom}(\mathsf{K},P,S)\\}$.
$\blacksquare$

With the choice $\mathsf{K}=\operatorname{Alg}_{m}(\mathcal{L}^{P})$, Lemma
4.9 gives (ii)$\Leftrightarrow$(iii) and Lemma 4.4 gives
(iii)$\Leftrightarrow$(v). Recall that
$\mathfrak{Fr}(\mathsf{K},X,S)=\mathfrak{Fr}(\mathbf{SP}\mathsf{K},X,S)$ (see
e.g. [1, 2.5] or [19, 0.4.65]). Hence, by letting
$\mathsf{K}=\mathbf{SP}\operatorname{Alg}_{m}(\mathcal{L}^{P})$, Lemma 4.9
yields (ii)$\Leftrightarrow$(iv) while Lemma 4.4 gives
(iv)$\Leftrightarrow$(vi). The equivalence (vii)$\Leftrightarrow$(viii)
follows from Lemma 4.4 with
$\mathsf{K}=\mathbf{SP}\operatorname{Alg}_{m}(\mathbf{L})$. Lemma 4.5 with
$\mathbf{T}=\mathbf{SP}$ infers the equivalence (vi)$\Leftrightarrow$(vii).
$\blacksquare$

Comparing Theorems 4.3(iii) and 4.7(iii) immediately yields that (4b) implies
(4). The following theorem states that (4) is indeed weaker than (4b). We will
see later that the natural pre-family formed from
$\mbox{$\mathcal{F}\mathcal{O}\mathcal{L}$}_{t}(V)$ when $2\leq|V|<\omega$
does not satisfy even condition (4), see Theorem 5.4. These show that the
conditions (4a), (4b), (4) are strictly weaker in this order, and (4) is still
not vacuous. Thus we have

$\displaystyle\qquad(4a)\qquad\underset{\not\\!\Leftarrow}{\Rightarrow}\qquad(4b)\qquad\underset{\not\\!\Leftarrow}{\Rightarrow}\qquad(4)\qquad.$
(65)

######  4.10 Theorem ((4) is weaker than (4b)).

There is a conditionally substitutional pre-family of logics which satisfies
(4) but which does not satisfy (4b).

Proof . For any sets $I,J$ let $P(I,J)=\\{N_{i}:i\in I\\}\cup\\{D_{j}:j\in
J\\}$ and let $\operatorname{Sig}=\\{P(I,J):I,J\mbox{ are sets}\\}$. Let
$\operatorname{Cn}$ consist of one unary connective $\neg$. Let $\mathfrak{B}$
be the algebra with universe $B=\\{T,F,D\\}$ and with unary operation
$\neg^{\mathfrak{B}}$ interchanging $T$ and $F$ and leaving $D$ fixed. For
sets $I,J$, let $\mbox{Mng}(I,J)$ be the set of all homomorphisms
$f:\mathfrak{F}(I,J)\to\mathfrak{B}$ such that $f(D_{j})=D$ for all $j\in J$.
For sets $I,J$ we define the logic $\mathcal{L}(I,J)$ such that its set of
atomic formulas is $P(I,J)$, its only connective is $\neg$ and the class of
its meaning functions is $\mbox{Mng}(I,J)$. The class of models of
$\mathcal{L}(I,J)$ is defined to be $\mbox{Mng}(I,J)$ and the validity
relation is defined so that $\mathsf{M}\vDash\varphi$ iff
$M(\varphi)\in\\{T,D\\}$. This finishes the definition of the logics
$\mathcal{L}(I,J)$ for all $I,J$. Intuitively, there are two kinds of atomic
formulas in $\mathcal{L}(I,J)$, the “normal” $N_{i}$s for which the negation
$\neg$ can have its “normal” meaning, and the “dialectic” $D_{j}$s whose
intended meaning is that their negations are themselves. Let

$\displaystyle\mathbf{L}=\langle\mathcal{L}(I,J):P(I,J)\in\operatorname{Sig}\rangle.$
(66)

First we show that $\mathbf{L}$ is a conditionally substitutional pre-family
of logics. Clearly,
$\operatorname{Alg}_{m}(\mathcal{L}(I,J))=\\{\mathfrak{B}\\}$ and
$\mbox{Mng}(\mathcal{L}(I,J))=\\{f\in\operatorname{Hom}(\mathfrak{F}(I,J),\mathfrak{B}):S(I,J)\subseteq\ker(f)\\}$
where $S(I,J)=\\{\langle D_{j},\neg D_{j}\rangle:j\in J\\}$. Thus,
$\mathcal{L}(I,J)$ is a conditionally substitutional logic, for each pair of
sets $I,J$, by Claim 3.8(iii).

Conditions (1)-(2) in the definition of a family of logics are clearly
satisfied by $\mathbf{L}$. To check (3), notice first that $P(I,J)\subseteq
P(I^{\prime},J^{\prime})$ exactly when $I\subseteq I^{\prime}$ and $J\subseteq
J^{\prime}$, and it is clear that $\mathcal{L}(I,J)$ is the natural
restriction of $\mathcal{L}(I^{\prime},J^{\prime})$ in the latter case. For
(5), notice first that a bijection $b:P(I,J)\to P(I^{\prime},J^{\prime})$
extends to an isomorphism between the corresponding logics if and only if $b$
takes $I$ to $I^{\prime}$ and $J$ to $J^{\prime}$. Notice also that
$\operatorname{Sig}$ is closed under taking arbitrary unions and under taking
subsets. From these, it is easy to check that $\mathbf{L}$ satisfies (5).
Therefore, $\mathbf{L}$ is a pre-family of logics.

To show that $\mathbf{L}$ satisfies (4), first we check what $\sim^{P}$ is.
Let $P=P(I,J)$. Let $\omega$ denote the set of nonnegative integers and let
$\neg^{k}p$ denote $p$ preceded by $k$ copies of $\neg$, for $k\in\omega$ and
$p\in P$. Now, it is easy to check that

$\displaystyle\sim^{P}=\\{\langle\neg^{k}N_{i},\neg^{k+2n}N_{i}\rangle:k,n\in\omega,i\in
I\\}\cup\\{\langle\neg^{k}D_{j},\neg^{n}D_{q}\rangle:k,n\in\omega,j,q\in
J\\}.$ (67)

See Figure 1. Let $h:\mathfrak{F}^{P}\to\mathfrak{B}$. Then
$\sim^{P}\subseteq\ker(h)$ iff $h(D_{j})=D$ for all $j\in J$. This shows that
Theorem 4.7(iii) holds, thus $\mathbf{L}$ satisfies (4).

To show that $\mathbf{L}$ does not satisfy (4b), we use Theorem 4.3(iii). Let
$\mathfrak{A}$ be the homomorphic image of $\mathfrak{B}$ via the homomorphism
taking $D$ to $a$ and taking $T$ as well as $F$ to $b$ where $a,b$ are
distinct. Thus, in $\mathfrak{A}$, both $a$ and $b$ are fixed points of the
unary operation. Clearly, $\mathfrak{A}\in\mathbf{HSP}\\{\mathfrak{B}\\}$ and
$\sim^{P}\subseteq\ker(h)$ for a homomorphism
$h:\mathfrak{F}^{P}\to\mathfrak{A}$ iff $h(D_{j})=h(D_{q})$ for all $j,q\in
J$. Let $P_{i}=\\{D_{i}\\}$ for $i=1,2$, let $Q=\\{D_{1},D_{2}\\}$ and let
$h:\mathfrak{F}^{Q}\to\mathfrak{A}$ be such that $h(D_{1})=a$ and
$h(D_{2})=b$. Then $\sim^{P_{i}}\subseteq\ker(h)$ for $i=1,2$, but $\sim^{Q}$
is not a subset of $\ker(h)$ by $a\neq b$, showing that Theorem 4.3(iii)
fails. $\blacksquare$

$D$$F$$T$$a$$b$$\mathfrak{B}$$\mathfrak{A}$$\mathfrak{Fr}(\\{\mathfrak{B}\\},P(I,J))$$N_{i}$$\cdot$$\cdot$$\cdot$$\cdot$$\cdot$$\cdot$$\cdot$$\cdot$$\cdot$$\cdot$$\cdot$$\cdot$$\cdot$$\cdot$$D_{j}$$\cdot$$\cdot$$\cdot$$\cdot$$\cdot$$\cdot$$\cdot$$\cdot$$\cdot$$\cdot$$\cdot$$\cdot$$\cdot$$\cdot$$\mathfrak{Fr}(\\{\mathfrak{B}\\},P(I,J),S(I,J))$$N_{i}$$\cdot$$\cdot$$\cdot$$\cdot$$\cdot$$\cdot$$\cdot$$\cdot$$\cdot$$\cdot$$\cdot$$\cdot$$\cdot$$\cdot$$D_{j}=D_{q}$$\cdot$
Figure 1: Illustration of the algebras $\mathfrak{A}$, $\mathfrak{B}$, and the
free and conditionally free algebras
$\mathfrak{Fr}(\\{\mathfrak{B}\\},P(I,J))$, and
$\mathfrak{Fr}(\\{\mathfrak{B}\\},P(I,J),S(I,J))$.

###  4.3 Condition (4) in conditionally substitutional pre-families

In this subsection, we discuss (4) in the special case when $\mathbf{L}$ is
conditionally substitutional. We show close connections of (4) with the
defining relations of the logics and with the patchwork property of models. We
close with showing existence and non-existence of logic families containing
given logics.

The intuition behind condition (4) is expressed quite nicely in a
conditionally substitutional pre-family of logics. Recall from Claim 3.8(iii)
that $\mbox{Mng}_{\mathcal{L}}$ in a conditionally substitutional logic can be
specified by a condition $S$. Theorem 4.11 states that (4) is equivalent to
saying that the logic belonging to the union of the signatures is specified by
the union of these conditions. Note that Theorem 4.11(i) is just condition
(4).

######  4.11 Theorem (defining relations and (4)).

Let $\mathbf{L}=\langle\mathcal{L}^{P}:\;P\in\operatorname{Sig}\rangle$ be a
conditionally substitutional pre-family of logics. Let
$P_{i}\in\operatorname{Sig}$ be sets for $i\in I$ such that the union
$P=\bigcup_{i\in I}P_{i}$ belongs to $\operatorname{Sig}$. The following
conditions are equivalent.

  1. (i)

$\mathfrak{F}^{P}/\\!\sim^{P}\ =\
\mathfrak{Fr}(\operatorname{Alg}_{m}(\mathcal{L}^{P}),\;P,\;\cup\\!\sim^{P_{i}})$.

  2. (ii)

$\mathfrak{F}^{P}/\\!\sim^{P}\ =\
\mathfrak{Fr}(\operatorname{Alg}_{m}(\mathcal{L}^{P}),\;P,\;\cup S_{i})$
whenever
$\mathfrak{F}^{P_{i}}/\\!\sim^{P_{i}}=\mathfrak{Fr}(\operatorname{Alg}_{m}(\mathcal{L}^{P_{i}}),\;P_{i},\;S_{i})$
for all $i\in I$.

Proof . We start with the general observation that for any class $\mathsf{K}$
of similar algebras, set $P$ and binary relations $R,S\subseteq F^{P}\times
F^{P}$,

$\displaystyle\mathfrak{Fr}(\mathsf{K},P,R)=\mathfrak{Fr}(\mathsf{K},P,S)$
$\displaystyle\quad\Leftrightarrow\quad\mbox{\sf Cr}(\mathsf{K},P,R)=\mbox{\sf
Cr}(\mathsf{K},P,S)$
$\displaystyle\quad\Leftrightarrow\quad\operatorname{Hom}(\mathsf{K},P,R)=\operatorname{Hom}(\mathsf{K},P,S)$
$\displaystyle\quad\Leftrightarrow\quad\big{(}\forall
h\in\operatorname{Hom}(\mathfrak{F}^{P},\mathsf{K})\big{)}\big{(}R\subseteq\ker(h)\
\Leftrightarrow\ S\subseteq\ker(h)\big{)}$

Consider now the following three statements.

  1. (A)

$(\forall h:\mathfrak{F}^{P}\to\operatorname{Alg}_{m}(\mathcal{L}^{P}))\
\big{(}\sim^{P}\subseteq\ker(h)\ \Leftrightarrow\
\cup\sim^{P_{i}}\subseteq\ker(h)\big{)}$.

  2. (B)

$(\forall
h:\mathfrak{F}^{P_{i}}\to\operatorname{Alg}_{m}(\mathcal{L}^{P_{i}}))\
\big{(}\sim^{P_{i}}\subseteq\ker(h)\ \Leftrightarrow\
S_{i}\subseteq\ker(h)\big{)}$ for all $i\in I$.

  3. (C)

$(\forall h:\mathfrak{F}^{P}\to\operatorname{Alg}_{m}(\mathcal{L}^{P}))\
\big{(}\sim^{P}\subseteq\ker(h)\ \Leftrightarrow\ \cup
S_{i}\subseteq\ker(h)\big{)}$.

Then (i) is equivalent to (A); and (ii) is equivalent to (B)$\Rightarrow$(C).
Take any $h:\mathfrak{F}^{P}\to\operatorname{Alg}_{m}(\mathcal{L}^{P})$, and
for $i\in I$, write $h_{i}=h\upharpoonright
F^{P_{i}}:\mathfrak{F}^{P_{i}}\to\operatorname{Alg}_{m}(\mathcal{L}^{P_{i}})$.

Proof of (i)$\Rightarrow$(ii): Suppose (A) and (B) hold. Then

$\displaystyle\sim^{P}\subseteq\ker(h)\quad$
$\displaystyle\overset{(A)}{\Longleftrightarrow}\quad\cup\sim^{P_{i}}\subseteq\ker(h)\quad\overset{}{\Longleftrightarrow}\quad(\forall
i\in I)\ \sim^{P_{i}}\subseteq\ker(h_{i})$
$\displaystyle\overset{(B)}{\Longleftrightarrow}\quad(\forall i\in I)\
S_{i}\subseteq\ker(h_{i})\quad\overset{}{\Longleftrightarrow}\quad\cup
S_{i}\subseteq\ker(h),$

therefore (C) holds. In this direction we did not use that $\mathbf{L}$ is
conditionally substitutional.

Proof of (ii)$\Rightarrow$(i): By Claim 3.8(iii), for each $P_{i}$,
$\mbox{Mng}^{P_{i}}$ can be specified by a condition $S_{i}$, that is,
$\mbox{Mng}^{P_{i}}=\operatorname{Hom}(\mathfrak{F}^{P_{i}},\operatorname{Alg}_{m}(\mathcal{L}^{P_{i}}),S_{i})$.
By the same claim,
$\mbox{Mng}^{P_{i}}=\operatorname{Hom}(\mathfrak{F}^{P_{i}},\operatorname{Alg}_{m}(\mathcal{L}^{P_{i}}),\sim^{P_{i}})$,
consequently, (B) holds for the $S_{i}$’s. As we assumed (ii) and (B) holds it
follows that (C) holds as well. Then

$\displaystyle\sim^{P}\subseteq\ker(h)\quad$
$\displaystyle\overset{(C)}{\Longleftrightarrow}\quad\cup
S_{i}\subseteq\ker(h)\quad\overset{}{\Longleftrightarrow}\quad(\forall i\in
I)\ S_{i}\subseteq\ker(h_{i})$
$\displaystyle\overset{(B)}{\Longleftrightarrow}\quad(\forall i\in I)\
\sim^{P_{i}}\subseteq\ker(h_{i})\quad\overset{}{\Longleftrightarrow}\quad\cup\sim^{P_{i}}\subseteq\ker(h),$

therefore (A) holds. $\blacksquare$

We turn to connections with the quite intuitive patchwork property of models,
see, e.g., [1, Def. 4.3.14].

######  4.12 Definition (patchwork property).

Let $\mathbf{L}=\langle\mathcal{L}^{P}:\;P\in\operatorname{Sig}\rangle$ be a
class of logics. $\mathbf{L}$ has the _patchwork property of models_ if the
following holds. Let $P_{i}\in\operatorname{Sig}$ for $i\in I$ be such that
$P=\cup_{i}P_{i}\in\operatorname{Sig}$. Let $\mathfrak{M}_{i}\in M^{P_{i}}$ be
models such that for any $i,j\in I$ whenever $F^{P_{i}\cap
P_{j}}\neq\emptyset$, then

$\operatorname{mng}_{\mathfrak{M}_{i}}^{P_{i}}\upharpoonright F^{P_{i}\cap
P_{j}}=\operatorname{mng}_{\mathfrak{M}_{j}}^{P_{j}}\upharpoonright
F^{P_{i}\cap P_{j}}.$ (68)

Then there is $\mathfrak{M}\in M^{P}$ such that

$\operatorname{mng}_{\mathfrak{M}}^{P}\upharpoonright
F^{P_{i}}\;=\;\operatorname{mng}_{\mathfrak{M}_{i}}^{P_{i}}$ (69)

for all $i\in I$. $\square$

The next theorem says that in conditionally substitutional pre-families of
logics, the patchwork property implies (4) but the patchwork property and (4b)
remain independent of each other. These facts suggest that it may be better to
have (4) in the definition of a logic family than (4b).

######  4.13 Theorem (the patchwork property and (4)).

Suppose $\mathbf{L}=\langle\mathcal{L}^{P}:\;P\in\operatorname{Sig}\rangle$ is
a conditionally substitutional pre-family of logics. Then (i)-(iii) below
hold.

  1. (i)

$\mathbf{L}$ satisfies (4) if it has the patchwork property of models.

  2. (ii)

(4b) is not implied by the patchwork property.

  3. (iii)

(4b) does not imply the patchwork property.

Proof . Proof of (i): Assume the patchwork property, we show (4) by checking
the equivalent condition Theorem 4.7(iv). Take signatures
$P_{i}\in\operatorname{Sig}$ for $i\in I$ such that
$P=\cup_{i}P_{i}\in\operatorname{Sig}$. Take any homomorphism
$h:\mathfrak{F}^{P}\to\mathfrak{A}$ for some
$\mathfrak{A}\in\operatorname{Alg}_{m}(\mathcal{L}^{P})$ such that
$\sim^{P_{i}}\subseteq\ker(h)$ holds for $i\in I$. By the conditional
substitution property, the homomorphisms $h\upharpoonright F^{P_{i}}$ are
meaning homomorphisms $\operatorname{mng}_{\mathfrak{M}_{i}}^{P_{i}}$ for some
models $\mathfrak{M}_{i}\in M^{P_{i}}$. Clearly, (68) holds for $i,j\in I$.
Therefore, by the patchwork property of models, there is $\mathfrak{M}\in
M^{P}$ that fulfills (69). But then $h=\operatorname{mng}_{\mathfrak{M}}^{P}$,
implying $\sim^{P}\subseteq\ker(h)$.

Proof of (ii): The conditionally substitutional pre-family of logics
$\mathbf{L}=\langle\mathcal{L}(I,J):P(I,J)\in\operatorname{Sig}\rangle$ from
Theorem 4.10 does not satisfy (4b) but has the patchwork property of models.

Proof of (iii): As substitutionality implies (4b) by Corollary 4.6, it is
enough to construct a substitutional pre-family of logics $\mathbf{L}$ that
lacks the patchwork property.

Let $\mathsf{K}$ be a class of similar algebras that does not have the
amalgamation property.161616For the definition of the amalgamation property,
see e.g. [1, Def. 4.4.17].  For example, let
$\mathfrak{B}_{1}=\langle\\{0\\},\cap\rangle$ and
$\mathfrak{B}_{2}=\langle\\{0,1\\},\cap\rangle$ be the $\cap$-reducts of the
one and two element Boolean set algebras respectively, and take
$K=\\{\mathfrak{B}_{1},\mathfrak{B}_{2}\\}$. The V-formation in Figure 2
cannot be completed to an amalgamation diagram in $K$, showing that $K$ fails
to have the amalgamation property.

$\mathfrak{B}_{1}$$\mathfrak{B}_{2}$$\mathfrak{B}_{2}$ Figure 2: The
embeddings of $\mathfrak{B}_{1}$ into $\mathfrak{B}_{2}$ showing the failure
of the amalgamation property in $K$.

Let $\operatorname{Cn}$ be the similarity type of the algebras in
$\mathsf{K}$, and $\operatorname{Sig}$ be the class of all sets $P$ not
containing proper $\operatorname{Cn}$-type terms. For $P\in\operatorname{Sig}$
we let $\mbox{Mng}^{P}=\operatorname{Hom}(\mathfrak{F}^{P},\mathsf{K})$. The
class of models $M^{P}$ is defined to be $\mbox{Mng}^{P}$, and the validity
relation is defined so that $\mathfrak{M}\vDash\varphi$ always holds. This way
we defined the logic $\mathcal{L}^{P}$. Let
$\mathbf{L}=\langle\mathcal{L}^{P}:\;P\in\operatorname{Sig}\rangle$. That
$\mathbf{L}$ is a pre-family of logics is straightforward. By Claim 3.2,
$\mathbf{L}$ is substitutional, and thus it is conditionally substitutional,
as well. It remained to check that $\mathbf{L}$ does not have the patchwork
property. For, take
$\mathfrak{A}_{0},\mathfrak{A}_{1},\mathfrak{A}_{3}\in\mathsf{K}$ such that
$\mathfrak{A}_{0}\subseteq\mathfrak{A}_{1}$,
$\mathfrak{A}_{0}\subseteq\mathfrak{A}_{2}$, but there is no
$\mathfrak{A}\in\mathsf{K}$ and embeddings
$e_{i}:\mathfrak{A}_{i}\to\mathfrak{A}$ ($i=1,2$) with
$e_{1}(\mathfrak{A}_{0})=e_{2}(\mathfrak{A}_{0})$. Such algebras exist because
$\mathsf{K}$ lacks the amalgamation property. Now,
$A_{1},A_{2}\in\operatorname{Sig}$ and $A_{1}\cup A_{2}\in\operatorname{Sig}$
as well. For $i=1,2$, let $m_{i}:\mathfrak{F}^{A_{i}}\to\mathfrak{A}_{i}$ be
the homomorphic extension of the identity mapping $A_{i}\to A_{i}$. Each
$m_{i}$ is a meaning function, and

$\displaystyle m_{1}\upharpoonright F^{A_{1}\cap A_{2}}=m_{2}\upharpoonright
F^{A_{1}\cap A_{2}},$ (70)

because $A_{1}\cap A_{2}=A_{0}$. On the other hand, there cannot exist
$m:\mathfrak{F}^{A_{1}\cup A_{2}}\to\mathsf{K}$ with

$\displaystyle m\upharpoonright\mathfrak{F}^{A_{1}}=m_{1},\text{ and
}m\upharpoonright\mathfrak{F}^{A_{2}}=m_{2},$ (71)

because in this case $\mathfrak{A}=m(\mathfrak{F}^{A_{1}\cup A_{2}})$ would be
an amalgam in $\mathsf{K}$. $\blacksquare$

The next theorem says that in conditionally substitutional families of logic,
the tautological formula algebras determine the logics themselves, up to
meaning-isomorphisms. The proof of this theorem uses condition (4) quite
inherently.

######  4.14 Theorem (renaming atomic formulas and (4)).

Assume that $\mathbf{L}=\langle\mathcal{L}(P):P\in\operatorname{Sig}\rangle$
is a conditionally substitutional family of logics. Then $\mathbf{L}$
satisfies (6a), i.e., any bijection $b:P\to Q$ that extends to a bijection
between the tautological formula algebras of $\mathcal{L}^{P}$ and
$\mathcal{L}^{Q}$ induces a meaning-isomorphism between $\mathcal{L}^{P}$ and
$\mathcal{L}^{Q}$, whenever $P,Q\in\operatorname{Sig}$.

Proof . Assume that $b:P\to Q$ is a bijection between
$P,Q\in\operatorname{Sig}$ that extends to an isomorphism $k$ between the
tautological formula algebras. Let
$P^{\prime},Q^{\prime}\in\operatorname{Sig}$ be such that
$\mathcal{L}(P^{\prime})$ and $\mathcal{L}(Q^{\prime})$ are isomorphic copies
of $\mathcal{L}(P)$ and $\mathcal{L}(Q)$ respectively, say, via the
isomorphisms $i$ and $j$ and such that $R=P^{\prime}\cup
Q^{\prime}\in\operatorname{Sig}$ and $P^{\prime}$ and $Q^{\prime}$ are
disjoint. There are such $P^{\prime},Q^{\prime}$ by condition (5)b. Assume
that $f\in\mbox{Mng}^{P}$, we will show that
$g=f\circ{(\overline{b})}^{-1}\in\mbox{Mng}^{Q}$, where
$\overline{b}:\mathfrak{F}^{P}\to\mathfrak{F}^{Q}$ is the extension of $b$ to
$\mathfrak{F}^{P}$.

Let $f^{\prime}=f\circ i$, then $f^{\prime}\in\mbox{Mng}^{P^{\prime}}$ since
$i$ is an isomorphism between $\mathcal{L}(P)$ and $\mathcal{L}(P^{\prime})$.
Thus $\sim_{P^{\prime}}\subseteq\ker(f^{\prime})$. By $P^{\prime}\subseteq R$
and condition (3), $f^{\prime}$ is the restriction of some
$f^{\prime\prime}\in\mbox{Mng}^{R}$. Let
$f^{\prime\prime}:\mathfrak{F}^{R}\to\mathfrak{A}\in\operatorname{Alg}_{m}(\mathcal{L}^{R})$.

Let now turn to $g$. Since $\sim^{P}\in\ker(f)$ by $f\in\mbox{Mng}^{P}$, and
$b$ extends to an isomorphism between the tautological formula algebras, we
have that $\sim^{Q}\subseteq\ker(g)$. For details, see Figure 3. Let
$g^{\prime}=g\circ j$, then $\sim^{Q^{\prime}}\subseteq\ker(g^{\prime})$ since
$j$ is an isomorphism, and
$g^{\prime}:\mathfrak{F}^{Q^{\prime}}\to\mathfrak{A}$ because the ranges of
$f$ and $g$ coincide.

Define $h$ on $R$ such that $h$ is $f^{\prime\prime}$ on $P^{\prime}$ and $h$
is $g^{\prime}$ on $Q^{\prime}$. Let us denote also by $h$ the extension to
$\mathfrak{F}^{R}$. Then
$h:\mathfrak{F}^{R}\to\mathfrak{A}\in\operatorname{Alg}_{m}(\mathcal{L}^{R})$
such that $\ker(h)\supseteq\;\sim^{P^{\prime}}\cup\sim^{Q^{\prime}}$. Then
$\ker(h)\supseteq\;\sim^{R}$ by condition (4) and Theorem 4.7(iii). Thus,
$h\in\mbox{Mng}^{R}$ since $\mathcal{L}(R)$ is conditionally substitutional.
Thus the restriction of $h$ to $F(Q^{\prime})$ is in
$\mbox{Mng}^{Q^{\prime}}$, so $g\in\mbox{Mng}^{Q}$ since $j$ is an isomorphism
between $\mathcal{L}(Q)$ and $\mathcal{L}(Q^{\prime})$. We have seen that
$\mbox{Mng}^{P}\subseteq\\{g\circ\overline{b}:g\in\mbox{Mng}^{Q}\\}$. Now,
$\mbox{Mng}^{Q}\subseteq\\{g\circ(\overline{b}^{-1}):g\in\mbox{Mng}^{P}\\}$
can be proved the same way, so
$\mbox{Mng}^{P}=\\{g\circ\overline{b}:g\in\mbox{Mng}^{Q}\\}$. $\blacksquare$

$R=P\cup
Q^{\prime}$$\mathfrak{F}^{P^{\prime}}$$\mathfrak{F}^{Q^{\prime}}$$\mathfrak{F}^{P}$$\mathfrak{F}^{Q}$$\mathfrak{F}^{P}/_{\sim^{P}}$$\mathfrak{F}^{Q}/_{\sim^{Q}}$$\bullet$$i$$j$$\varepsilon^{P}$$\varepsilon^{Q}$$\overline{b}$$k$$\mbox{Mng}^{P}\ni
f$$g$$\subseteq\mathfrak{A}\in\operatorname{Alg}_{m}(\mathcal{L}^{P})$$\ker(g)\supseteq\;\sim^{Q}$

$\subseteq$

$\supseteq$

Figure 3: Illustration for the proof of Theorem 4.14.

We close the section by investigating how restrictive the notion of logic
families is.

######  4.15 Proposition (existence of logic families).

The following statements are true.

  1. (i)

Each substitutional meaning-determined logic is a member of a substitutional
logic family with class of signatures being all sets not containing proper
terms by the connectives.

  2. (ii)

Each conditionally substitutional logic is a member of some conditionally
substitutional logic family.

  3. (iii)

There is a logic which is not a member of any logic family, but each logic is
a member of a pre-family of logics.

Proof . Proof of (i): Let $\mathcal{L}$ be a substitutional meaning-determined
logic with $\operatorname{Cn}$ as connectives. Let $\operatorname{Sig}$ be the
class of all sets not containing proper terms written up by
$\operatorname{Cn}$. For all $P\in\operatorname{Sig}$ let $\mathcal{L}^{P}$ be
“the substitutional meaning-determined logic” with $P$ as atomic formulas,
$\operatorname{Cn}$ as connectives, with
$\mbox{Mng}(\mathcal{L}^{P})=\operatorname{Hom}(\mathfrak{F}^{P},\operatorname{Alg}_{m}(\mathcal{L}))$
and with validity inherited from $\mathcal{L}$. It is easy to check that
$\mathbf{L}$ is a substitutional pre-family of logics, by using that
$\mathcal{L}^{P}$ is an isomorphic copy of $\mathcal{L}^{Q}$ iff $P$ and $Q$
have the same cardinality. Then $\mathbf{L}$ is a family of logics by
Corollary 4.6. Clearly, $\mathcal{L}$ is a member of this family.

Proof of (ii): Let $\mathcal{L}=\langle F,M,\operatorname{mng},\vDash\rangle$
be a conditionally substitutional logic. The idea is that we make $\mathbf{L}$
to consist of all unions of disjoint (almost) isomorphic copies of
$\mathcal{L}$. Let $\operatorname{Sig}=\\{P\times I:I\mbox{ is a set and
}P\cap\operatorname{Cn}=\emptyset\\}$. Assume $Q=P\times
I\in\operatorname{Sig}$. Let us define $\mathcal{L}^{Q}=\langle
F^{Q},M^{Q},\operatorname{mng}^{Q},\vDash^{Q}\rangle$ such that its set of
atomic formulas is $Q$, its set of connectives is that of $\mathcal{L}$, and
meaning and validity are defined as follows. The models are those
$I$-sequences of models of $\mathcal{L}$ whose meaning functions go to a
common $\mathfrak{A}\in\operatorname{Alg}_{m}(\mathcal{L})$, i.e.,
$M^{Q}=\\{\langle\mathfrak{M},\mathfrak{A}\rangle\in{}^{I}M\times\operatorname{Alg}_{m}(\mathcal{L}):(\forall
i\in
I)\operatorname{mng}_{\mathfrak{M}_{i}}(\mathfrak{F})\subseteq\mathfrak{A}\\}$.
For an $\langle\mathfrak{M},\mathfrak{A}\rangle\in M^{Q}$ the meaning function
is then $h:\mathfrak{F}^{Q}\to\mathfrak{A}$ such that $h(\langle
p,i\rangle)=\operatorname{mng}(\mathfrak{M}_{i},p)$ for all $\langle
p,i\rangle\in Q$. Validity is defined as
$\langle\mathfrak{M},\mathfrak{A}\rangle\vDash\varphi$ if and only if
$\varphi\in F^{(P\times\\{i\\})}$ for some $i\in I$ and
$\mathfrak{M}_{i}\vDash\varphi^{\prime}$ where $\varphi^{\prime}$ is $\varphi$
such that we replace $p\in P$ with $\langle p,i\rangle$ in it, for each $p\in
P$. This defines $\mathbf{L}$. Conditions (1),(2) are clearly satisfied and it
is not difficult to check that (3) is also satisfied. Each bijection $b:I\to
J$ induces an isomorphism between $\mathcal{L}^{P\times I}$ and
$\mathcal{L}^{P\times J}$, so condition (5) is satisfied. Hence, $\mathbf{L}$
is a pre-family of logics. It is not difficult to check that
$\mbox{Mng}(\mathcal{L}^{P\times I})=\operatorname{Hom}(\mathfrak{F}^{P\times
I},\operatorname{Alg}_{m}(\mathcal{L}),S(I))$ where $S(I)=\bigcup\\{\
h_{i}(\sim_{\mathcal{L}}):i\in I\\}$ where
$h_{i}:\mathfrak{F}^{P}\to\mathfrak{F}^{P\times\\{i\\}}$ is the isomorphism
induced by $h(p)=\langle p,i\rangle$ for all $p\in P$. Here, one uses that
$\mathcal{L}$ is conditionally substitutional together with Claim 3.8. Thus,
$\mathbf{L}$ is a conditionally substitutional pre-family of logics. It
satisfies condition (4) by Theorem 4.11(ii). Though, strictly speaking,
$\mathcal{L}$ is not a member of this family, it is easy to change
$\mathbf{L}$ so that this will hold. Namely, $\mathcal{L}^{P\times\\{i\\}}$
may not be isomorphic to $\mathcal{L}$ because the models of the former are
$\\{\langle\mathfrak{M},\mathfrak{A}\rangle\in
M\times\operatorname{Alg}_{m}(\mathcal{L}):\operatorname{ran}(\operatorname{mng}_{\mathfrak{M}})\subseteq\mathfrak{A}\\}$,
thus each model of $\mathcal{L}$ may appear in $\mathcal{L}^{P\times\\{i\\}}$
in several copies. However, $P\times\\{i\\}$ are minimal elements of
$\operatorname{Sig}$, so we can replace their classes of models with $M$
itself.

Proof of (iii): Let $\mathcal{L}=\langle F,M,\operatorname{mng},\vDash\rangle$
be such that $|P|\geq 2$ and
$\operatorname{Alg}_{m}(\mathcal{L})=\\{\mathfrak{A}\\}$ where $\mathfrak{A}$
is the $\operatorname{Cn}$-free algebra freely generated by $a\in A$ and
$\operatorname{mng}(\mathfrak{M},p)=a$ for all $p\in P$. Assume that
$\mathcal{L}=\mathbf{L}(P)$ for some logic family $\mathbf{L}$. We will derive
a contradiction. There is $Q\in\operatorname{Sig}$ disjoint from $P$ such that
$\mathcal{L}^{Q}$ is an isomorphic copy of $\mathcal{L}$, by (5)a. There are
$P^{\prime},Q^{\prime}\in\operatorname{Sig}$ such that $R=P^{\prime}\cup
Q^{\prime}\in\operatorname{Sig}$ and $\mathcal{L}^{P^{\prime}}$ and
$\mathcal{L}^{Q^{\prime}}$ are isomorphic copies of $\mathcal{L}^{P}$ and
$\mathcal{L}^{Q}$ respectively, by (5)b. Then
$\operatorname{mng}^{P^{\prime}}(\mathfrak{M},p)=\operatorname{mng}^{Q^{\prime}}(\mathfrak{N},q)=a$
for all models $\mathfrak{M},\mathfrak{N}$ of
$\mathcal{L}^{P^{\prime}},\mathcal{L}^{Q^{\prime}}$ respectively, and for all
$p\in P^{\prime}$ and $q\in Q^{\prime}$, since $\mathcal{L}^{P^{\prime}}$ and
$\mathcal{L}^{Q^{\prime}}$ are isomorphic copies of $\mathcal{L}$. By (3),
then the same holds for $\mathcal{L}^{R}$, i.e.,
$\operatorname{mng}^{R}(\mathfrak{M},p)=a$ for all models $\mathfrak{M}$ of
$\mathcal{L}^{R}$ and $p\in R=P^{\prime}\cup Q^{\prime}$. This means that
$P^{\prime}\times Q^{\prime}\subseteq\sim^{R}$. Notice now that only “trivial”
quasi-equations are true in $\mathfrak{A}$ because it is a free algebra,
therefore $P^{\prime}\times Q^{\prime}$ is not a subset of the
$\vdash_{\mathcal{L}^{R}}$-closure of $P^{\prime}\times P^{\prime}\cup
Q^{\prime}\times Q^{\prime}$. Therefore, Theorem 4.7(i) does not hold, i.e.,
$\mathbf{L}$ cannot satisfy (4), a contradiction. $\blacksquare$

##  5 The key examples as logic families

In this section, we show that both of our key examples, classical
propositional logic and first-order logic, fit in the scheme of logic family.
By this we mean that their definitions suggest natural systems of logics, and
we show that these systems are indeed logic families. We also show that the
systems formed of the finite-variable fragments of the first-order logic are
not all logic families, although they have the patchwork property of models.

Let $\mbox{$\mathcal{C}\mathcal{P}\mathcal{L}$}(P)$ denote classical
propositional logic with atomic formulas $P$, see Example 2.2.

######  5.1 Theorem.

For classical propositional logic, the class

$\mathbf{L}_{C}=\langle\mbox{$\mathcal{C}\mathcal{P}\mathcal{L}$}(P)\;:\;P\text{
is a set not containing proper terms by }\\{\wedge,\neg,\bot\\}\rangle$ (72)

is a logic family in the sense of Def.4.1.

Proof . Let $\operatorname{Sig}$ be the class of all nonempty sets $P$ which
do not contain proper terms written up by $\\{\wedge,\neg,\bot\\}$. Items (1),
(2) of 4.1 are straightforward. For (3), it is easy to check that
$\mbox{$\mathcal{C}\mathcal{P}\mathcal{L}$}(P)$ is a reduct of
$\mbox{$\mathcal{C}\mathcal{P}\mathcal{L}$}(Q)$ whenever $P\subseteq Q$.

As for (5), any bijection $f:P\to Q$ for sets $P$ and $Q$ induces an
isomorphism between the corresponding logics
$\mbox{$\mathcal{C}\mathcal{P}\mathcal{L}$}(P)$ and
$\mbox{$\mathcal{C}\mathcal{P}\mathcal{L}$}(Q)$: $f^{F}$ is the homomorphic
extension of $f$ to $f^{F}:\mathfrak{F}^{P}\to\mathfrak{F}^{Q}$, and for a