\( \newcommand{\matr}[1] {\mathbf{#1}} \newcommand{\vertbar} {\rule[-1ex]{0.5pt}{2.5ex}} \newcommand{\horzbar} {\rule[.5ex]{2.5ex}{0.5pt}} \)
deepdream of
          a sidewalk
Show Answer
\( \newcommand{\cat}[1] {\mathrm{#1}} \newcommand{\catobj}[1] {\operatorname{Obj}(\mathrm{#1})} \newcommand{\cathom}[1] {\operatorname{Hom}_{\cat{#1}}} \newcommand{\multiBetaReduction}[0] {\twoheadrightarrow_{\beta}} \newcommand{\betaReduction}[0] {\rightarrow_{\beta}} \newcommand{\betaEq}[0] {=_{\beta}} \newcommand{\string}[1] {\texttt{"}\mathtt{#1}\texttt{"}} \newcommand{\symbolq}[1] {\texttt{`}\mathtt{#1}\texttt{'}} \)
Math and science::Theory of Computation::Modal theory

\( \mathcal{L} \)-formula implication

We wish to introduce an idea of implication between sets of \( \mathcal{L} \)-formula.

First, we must generalize the idea of truth/satisfaction that was introduced for \( \mathcal{L} \)-formula.

The idea of truth/satisfaction is recapped on the back side.

Model

Let \( \mathcal{L} \) be a first-order language. Let \( \mathfrak{U} \) be an \( \mathcal{L} \)-structure for \( \mathcal{L} \) and let \( \phi \) be an \( \mathcal{L} \)-formula of \( \mathcal{L} \).

If \( \mathfrak{U} \vDash \phi[s] \) for every [what?], then we say that \( \mathfrak{U} \) is a model of \( \phi \) (or \( \mathfrak{U} \) models \( \phi \)). We write \( \mathfrak{U} \vDash \phi \).

Extendion to sets of \( \mathcal{L} \)-formula: if \( \mathfrak{U} \) is a model for every \( \mathcal{L} \)-formula in a set of \( \mathcal{L} \)-formulas, \( \Phi \), then we say \( \mathfrak{U} \) is a model of \( \Phi \), and we write \( \mathfrak{U} \vDash \Phi \).

If we compare two sets of \( \mathcal{L} \)-formula we arrive at a type of implication.

Logical implication, under a structure

Let \( \Delta \) and \( \Gamma \) be two sets of \( \mathcal{L} \)-formulas from the same language \( \mathcal{L} \). Let \( \mathfrak{U} \) be an \( \mathcal{L} \)-structure for \( \mathcal{L} \).

If \( \mathfrak{U} \vDash \Delta \) implies \( \mathfrak{U} \vDash \Gamma \), we say that \( \Delta \) logically implies \( \Gamma \) under \( \mathfrak{U} \).

In other words, if whenever all the [what?] are satisfied by \( \mathfrak{U} \) so too are the [what?].

Finally, we remove the dependency on a specific structure.

Logical implication

Let \( \Delta \) and \( \Gamma \) be two sets of \( \mathcal{L} \)-formulas from the same language \( \mathcal{L} \).

If [what?] for any [what?] of \( \mathcal{L} \), then we say that \( \Delta \) logically implies \( \Gamma \). We write this as \( \Delta \vDash \Gamma \).