abstract-logics.tex

% Part: first-order-logic
% Chapter: lindstrom
% Section: abstract-logics

\documentclass[../../../include/open-logic-section]{subfiles}

\begin{document}

\olfileid{mod}{lin}{alg}
\olsection{Abstract Logics}

\begin{defn}
An \emph{abstract logic} is a pair $\tuple{L, \models_L}$, where $L$
is a function that assigns to each !!{language}~$\Lang{L}$ a set
$L(\Lang{L})$ of !!{sentence}s, and $\models_L$ is a relation between
!!{structure}s for the !!{language}~$\Lang{L}$ and !!{element}s of
$L(\Lang{L})$. In particular, $\tuple{F, \models}$ is ordinary
first-order logic, i.e., $F$ is the function assigning to the
!!{language}~$\Lang{L}$ the set of first-order !!{sentence}s built from
the constants in $\Lang{L}$, and $\models$ is the satisfaction relation
of first-order logic.
\end{defn}

Notice that we are still employing the same notion of !!{structure}
for a given !!{language} as for first-order logic, but we do not
presuppose that !!{sentence}s are build up from the basic symbols in
$\Lang{L}$ in the usual way, nor that the relation $\models_L$ is
recursively defined in the same way as for first-order logic. So for
instance the definition, being completely general, is intended to
capture the case where !!{sentence}s in $\tuple{L,\models_L}$ contain
infinitely long conjunctions or disjunction, or quantifiers other than
$\lexists$ and $\lforall$ (e.g., ``there are infinitely many~$x$ such
that \dots''), or perhaps infinitely long quantifier prefixes. To
emphasize that ``!!{sentence}s'' in $L(\Lang{L})$ need not be ordinary
!!{sentence}s of first-order logic, in this chapter we use !!{variable}s $!E$,
$!F$,~\dots to range over them, and reserve $!A$, $!B$,~\dots for
ordinary first-order !!{formula}s.

\begin{defn}
Let $\Mod(L){!E}$ denote the class $\Setabs{\Struct{M}}{\Struct{M}
  \models_L !E}$. If the !!{language} needs to be made explicit, we
write $\Mod[L](L){!E}$. Two !!{structure}s $\Struct{M}$ and
$\Struct{N}$ for $\Lang{L}$ are \emph{elementarily equivalent in}
$\tuple{L, \models_L}$, written $\Struct{M} \elemequiv[L] \Struct{N}$, if
the same !!{sentence}s from $L(\Lang{L})$ are true in each.
\end{defn}

\begin{defn}
An abstract logic $\tuple{L,\models_L}$ for the !!{language} $\Lang{L}$
is \emph{normal} if it satisfies the following properties:
\begin{enumerate}
\item (\emph{$L$-Monotonicity}) For !!{language}s $\Lang{L}$ and
  $\Lang{L'}$, if $\Lang{L} \subseteq \Lang{L'}$, then
  $L(\Lang{L}) \subseteq L(\Lang{L'})$.
\item (\emph{Expansion Property}) For each $!E \in L(\Lang{L})$
  there is a \emph{finite} subset $\Lang{L'}$ of $\Lang{L}$ such that
  the relation $\Struct{M} \models_L !E$ depends only on the
  reduct of $\Struct{M}$ to $\Lang{L'}$; i.e., if $\Struct{M}$ and
  $\Struct{N}$ have the same reduct to $\Lang{L'}$ then $\Struct{M}
  \models_L !E$ if and only if $\Struct{N} \models_L !E$.
\item (\emph{Isomorphism Property}) If $\Struct{M} \models_L !E$
  and $\Struct{M} \simeq \Struct{N}$ then also $\Struct{N} \models_L
  !E$.
\item (\emph{Renaming Property}) The relation $\models_L$ is preserved
  under renaming: if the !!{language} $\Lang{L}'$ is obtained from
  $\Lang{L}$ by replacing each symbol $P$ by a symbol $P'$ of the same
  arity and each constant $c$ by a distinct constant $c'$, then for
  each !!{structure}~$\Struct{M}$ and !!{sentence}~$!E$, $\Struct{M}
  \models_L !E$ if and only if $\Struct{M}' \models_L !E'$,
  where $\Struct{M}'$ is the $\Lang{L}'$-!!{structure} corresponding
  to $\Lang{L}$ and $!E' \in L(\Lang{L}')$.
\item (\emph{Boolean Property}) The abstract logic $\tuple{L,
  \models_L}$ is closed under the Boolean connectives in the sense
  that for each $!E \in L(\Lang{L})$ there is a~$!F \in
  L(\Lang{L})$ such that $\Struct{M} \models_L !F$ if and only if
  $\Struct{M} \not\models_L !E$, and for each $!E$ and $!F$
  there is a $!G$ such that $\Mod(L){!G} = \Mod(L){!E} \cap
  \Mod(L){!F}$.  Similarly for atomic !!{formula}s and the other
  connectives.
\item (\emph{Quantifier Property}) For each constant $c$ in $\Lang{L}$
  and $!E \in L(\Lang{L})$ there is a $!F \in L(\Lang{L})$ such
  that
  \[
  \Mod[L'](L){!F} = \Setabs{\Struct{M}}{\Expan{M}{a} \in
  \Mod[L](L){!E} \text{ for some } a \in \Domain{M}},
  \]
  where $\Lang{L'} = \Lang{L} \setminus \{c\}$ and $\Expan{M}{a}$
  is the expansion of $\Struct{M}$ to $\Lang{L}$ assigning $a$
  to~$c$.
\item (\emph{Relativization Property}) Given !!a{sentence} $!E \in
  L(\Lang{L})$ and symbols $R$, $c_1$, \dots, $c_n$ not in $\Lang{L}$,
  there is !!a{sentence} $!F \in L(\Lang{L} \cup \{R,c_1,\ldots,c_n\})$
  called the \emph{relativization} of $!E$ to $\Atom{R}{x, c_1, \dots c_n}$,
  such that for each !!{structure}~$\Struct{M}$:
  \[
  \Expan{M}{X, b_1, \ldots, b_n} \models_L !F \text{ if and
    only if } \Struct{N} \models_L !E,
  \]
  where $\Struct{N}$ is the substructure of $\Struct{M}$ with !!{domain}
  $\Domain{N} = \Setabs{a\in \Domain{M}}{\Assign{R}{M}(a, b_1, \dots, b_n)}$
  (see \olref[bas][sub]{rem:substructure}), and $\Expan{M}{X, b_1, \ldots,
    b_n}$ is the expansion of $\Struct{M}$ interpreting $R$, $c_1$,
  \dots, $c_n$ by $X$, $b_1,$ \dots, $b_n$, respectively (with $X
  \subseteq M^{n+1}$).
\end{enumerate}
\end{defn}
 
\begin{defn}
Given two abstract logics $\tuple{L_1, \models_{L_1}}$ and
$\tuple{L_2, \models_{L_2}}$ we say that the latter is \emph{at least
  as expressive} as the former, written $\tuple{L_1, \models_{L_1}}
\leq \tuple{L_2, \models_{L_2}}$, if for each !!{language} $\Lang{L}$
and !!{sentence} $!E \in L_1(\Lang{L})$ there is !!a{sentence} $!F
\in L_2(\Lang{L})$ such that $\Mod[L](L_1){!E} =
\Mod[L](L_2){!F}$. The logics $\tuple{L_1, \models_{L_1}}$ and
$\tuple{L_2, \models_{L_2}}$ are \emph{equivalent} if $\tuple{L_1,
  \models_{L_1}} \leq \tuple{L_2, \models_{L_2}}$ and $\tuple{L_2,
  \models_{L_2}} \leq \tuple{L_1, \models_{L_1}}$.
\end{defn}

\begin{rem}
  First-order logic, i.e., the abstract logic $\tuple{F, \models}$, is
  normal. In fact, the above properties are mostly straightforward for
  first-order logic. We just remark that the expansion property comes
  down to extensionality, and that the relativization of
  !!a{sentence} $!E$ to $\Atom{R}{x, c_1, \dots, c_n}$ is obtained by
  replacing each !!{subformula} $\lforall[x][!F]$ by
  $\lforall[x][(\Atom{R}{x, c_1, \dots, c_n} \lif \ !F)]$. Moreover,
  if $\tuple{L, \models_L}$ is normal, then
  $\tuple{F, \models} \leq \tuple{L, \models_{L}}$, as can be can
  shown by induction on first-order !!{formula}s. Accordingly, with no
  loss in generality, we can assume that every first-order
  !!{sentence} belongs to every normal logic.
\end{rem}

\end{document}