# 1.10: Logical Implication

$$\newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} }$$

$$\newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}}$$

$$\newcommand{\id}{\mathrm{id}}$$ $$\newcommand{\Span}{\mathrm{span}}$$

( \newcommand{\kernel}{\mathrm{null}\,}\) $$\newcommand{\range}{\mathrm{range}\,}$$

$$\newcommand{\RealPart}{\mathrm{Re}}$$ $$\newcommand{\ImaginaryPart}{\mathrm{Im}}$$

$$\newcommand{\Argument}{\mathrm{Arg}}$$ $$\newcommand{\norm}[1]{\| #1 \|}$$

$$\newcommand{\inner}[2]{\langle #1, #2 \rangle}$$

$$\newcommand{\Span}{\mathrm{span}}$$

$$\newcommand{\id}{\mathrm{id}}$$

$$\newcommand{\Span}{\mathrm{span}}$$

$$\newcommand{\kernel}{\mathrm{null}\,}$$

$$\newcommand{\range}{\mathrm{range}\,}$$

$$\newcommand{\RealPart}{\mathrm{Re}}$$

$$\newcommand{\ImaginaryPart}{\mathrm{Im}}$$

$$\newcommand{\Argument}{\mathrm{Arg}}$$

$$\newcommand{\norm}[1]{\| #1 \|}$$

$$\newcommand{\inner}[2]{\langle #1, #2 \rangle}$$

$$\newcommand{\Span}{\mathrm{span}}$$ $$\newcommand{\AA}{\unicode[.8,0]{x212B}}$$

$$\newcommand{\vectorA}[1]{\vec{#1}} % arrow$$

$$\newcommand{\vectorAt}[1]{\vec{\text{#1}}} % arrow$$

$$\newcommand{\vectorB}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} }$$

$$\newcommand{\vectorC}[1]{\textbf{#1}}$$

$$\newcommand{\vectorD}[1]{\overrightarrow{#1}}$$

$$\newcommand{\vectorDt}[1]{\overrightarrow{\text{#1}}}$$

$$\newcommand{\vectE}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash{\mathbf {#1}}}}$$

$$\newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} }$$

$$\newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}}$$

$$\newcommand{\avec}{\mathbf a}$$ $$\newcommand{\bvec}{\mathbf b}$$ $$\newcommand{\cvec}{\mathbf c}$$ $$\newcommand{\dvec}{\mathbf d}$$ $$\newcommand{\dtil}{\widetilde{\mathbf d}}$$ $$\newcommand{\evec}{\mathbf e}$$ $$\newcommand{\fvec}{\mathbf f}$$ $$\newcommand{\nvec}{\mathbf n}$$ $$\newcommand{\pvec}{\mathbf p}$$ $$\newcommand{\qvec}{\mathbf q}$$ $$\newcommand{\svec}{\mathbf s}$$ $$\newcommand{\tvec}{\mathbf t}$$ $$\newcommand{\uvec}{\mathbf u}$$ $$\newcommand{\vvec}{\mathbf v}$$ $$\newcommand{\wvec}{\mathbf w}$$ $$\newcommand{\xvec}{\mathbf x}$$ $$\newcommand{\yvec}{\mathbf y}$$ $$\newcommand{\zvec}{\mathbf z}$$ $$\newcommand{\rvec}{\mathbf r}$$ $$\newcommand{\mvec}{\mathbf m}$$ $$\newcommand{\zerovec}{\mathbf 0}$$ $$\newcommand{\onevec}{\mathbf 1}$$ $$\newcommand{\real}{\mathbb R}$$ $$\newcommand{\twovec}[2]{\left[\begin{array}{r}#1 \\ #2 \end{array}\right]}$$ $$\newcommand{\ctwovec}[2]{\left[\begin{array}{c}#1 \\ #2 \end{array}\right]}$$ $$\newcommand{\threevec}[3]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \end{array}\right]}$$ $$\newcommand{\cthreevec}[3]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \end{array}\right]}$$ $$\newcommand{\fourvec}[4]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \\ #4 \end{array}\right]}$$ $$\newcommand{\cfourvec}[4]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \\ #4 \end{array}\right]}$$ $$\newcommand{\fivevec}[5]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \\ #4 \\ #5 \\ \end{array}\right]}$$ $$\newcommand{\cfivevec}[5]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \\ #4 \\ #5 \\ \end{array}\right]}$$ $$\newcommand{\mattwo}[4]{\left[\begin{array}{rr}#1 \amp #2 \\ #3 \amp #4 \\ \end{array}\right]}$$ $$\newcommand{\laspan}[1]{\text{Span}\{#1\}}$$ $$\newcommand{\bcal}{\cal B}$$ $$\newcommand{\ccal}{\cal C}$$ $$\newcommand{\scal}{\cal S}$$ $$\newcommand{\wcal}{\cal W}$$ $$\newcommand{\ecal}{\cal E}$$ $$\newcommand{\coords}[2]{\left\{#1\right\}_{#2}}$$ $$\newcommand{\gray}[1]{\color{gray}{#1}}$$ $$\newcommand{\lgray}[1]{\color{lightgray}{#1}}$$ $$\newcommand{\rank}{\operatorname{rank}}$$ $$\newcommand{\row}{\text{Row}}$$ $$\newcommand{\col}{\text{Col}}$$ $$\renewcommand{\row}{\text{Row}}$$ $$\newcommand{\nul}{\text{Nul}}$$ $$\newcommand{\var}{\text{Var}}$$ $$\newcommand{\corr}{\text{corr}}$$ $$\newcommand{\len}[1]{\left|#1\right|}$$ $$\newcommand{\bbar}{\overline{\bvec}}$$ $$\newcommand{\bhat}{\widehat{\bvec}}$$ $$\newcommand{\bperp}{\bvec^\perp}$$ $$\newcommand{\xhat}{\widehat{\xvec}}$$ $$\newcommand{\vhat}{\widehat{\vvec}}$$ $$\newcommand{\uhat}{\widehat{\uvec}}$$ $$\newcommand{\what}{\widehat{\wvec}}$$ $$\newcommand{\Sighat}{\widehat{\Sigma}}$$ $$\newcommand{\lt}{<}$$ $$\newcommand{\gt}{>}$$ $$\newcommand{\amp}{&}$$ $$\definecolor{fillinmathshade}{gray}{0.9}$$

At first glance it seems that a large portion of mathematics can be broken down into answering questions of the form: If I know this statement is true, is it necessarily the case that this other statement is true? In this section we will formalize that question.

Definition 1.9.1. Suppose that $$\Delta$$ and $$\Gamma$$ are sets of $$\mathcal{L}$$-formulas. We will say that $$\Delta$$ logically implies $$\Gamma$$ and write $$\Delta \models \Gamma$$ if for every $$\mathcal{L}$$-structure $$\mathfrak{A}$$, if $$\mathfrak{A} \models \Delta$$, then $$\mathfrak{A} \models \Gamma$$.

This definition is a little bit tricky. It says that if $$\Delta$$ is true in $$\mathfrak{A}$$, then $$\Gamma$$ is true in $$\mathfrak{A}$$. Remember, for $$\Delta$$ to be true in $$\mathfrak{A}$$, it must be the case that $$\mathfrak{A} \models \Delta \left[ s \right]$$ for every assignment function $$s$$. See Exercise 4.

If $$\Gamma = \{ \gamma \}$$ is a set consisting of a single formula, we will write $$\Delta \models \gamma$$ rather than the official $$\Delta \models \{ \gamma \}$$.

Definition 1.9.2. An $$\mathcal{L}$$-formula $$\phi$$ is said to be valid if $$\emptyset \models \phi$$, in other words, if $$\phi$$ is true in every $$\mathcal{L}$$-structure with every assignment function $$s$$. In this case, we will write $$\models \phi$$.

Chaff: It doesn't seem like it would be easy to check whether $$\Delta \models \Gamma$$. To do so directly would mean that we would have to examine every possible $$\mathcal{L}$$-structure and every possible assignment function $$s\, of which there will be many. I'm also sure that you've noticed that this double turnstyle symbol, \(\models$$, is getting a lot of use. Just remember that if there is a structure on the left, $$\mathfrak{A} \models \sigma$$, we are discussing truth in a single structure. If there is a set of sentences on the left, $$\Gamma \models \sigma$$, then we are discussing logical implication.

Example 1.9.3. Let $$\mathcal{L}$$ be the language consisting of a single binary relation symbol, $$P$$, and let $$\sigma$$ be the sentence $$\left( \exists y \forall x P \left( x, y \right) \right) \rightarrow \left( \forall x \exists y P \left( x, y \right) \right)$$. We show that $$\sigma$$ is valid.

So let $$\mathfrak{A}$$ be any $$\mathcal{L}$$-structure and let $$s : Vars \rightarrow A$$ be any assignment function. We must show that

$\mathfrak{A} \models \left[ \left( \exists y \forall x P \left( x, y \right) \right) \rightarrow \left( \forall x \exists y P \left( x, y \right) \right) \right] \left[ s \right].$

Assume that $$\mathfrak{A} \models \left( \exists y \forall x P \left( x, y \right) \right) \left[ s \right]$$, we know that there is an element of the universe, $$A$$, such that $$\mathfrak{A} \models \forall x P \left( x, y \right) \left[s \left[ y | a \right] \right]$$. And so, again by the definition of satisfaction, we know that if $$b$$ is any element of $$A$$, $$\mathfrak{A} \models P \left( x, y \right) \left[ \left( s \left[ y | a \right] \right) \left[ x | b \right] \right]$$. If we chase through the definition of satisfaction (Definition 1.7.4) and of the various assignment functions, this means that for our one fixed $$a$$, the ordered pair $$\left( b, a \right) \in P^\mathfrak{A}$$ for any choice of $$b \in A$$.

We have to prove that $$\mathfrak{A} \models \left( \forall x \exists y P \left( x, y \right) \right) \left[ s \right]$$. As the statement of interest is universal, we must show that, if $$c$$ is an arbitrary element of $$A$$, $$\mathfrak{A} \models \exists y P \left( x, y \right) \left[ s \left[ x | c \right] \right]$$, which means that we must produce an element of the universe, $$d$$, such that $$\mathfrak{A} \models P \left( x, y \right) \left[ \left( s \left[ x | c \right] \right) \left[ y | d \right] \right]$$. Again, from the definition of satisfaction this means that we must find a $$d \in A$$ such that $$\left( c, d \right) \in P^\mathfrak{A}$$. Fortunately, we have such a $$d$$ in hand, namely $$a$$. As we know, $$\left( c, a \right) \in P^\mathfrak{A}$$, we have shown $$\mathfrak{A} \models \left( \forall x \exists y P \left( x, y \right) \right) \left[ s \right]$$, and we are finished.

## Exercises

1. Show that $$\{ \alpha, \alpha \rightarrow \beta \} \models \beta$$ for any formulas $$\alpha$$ and $$\beta$$. Translate this result into everyday English. Or Norwegian, if you prefer.
2. Show that the formula $$x = x$$ is valid. Show that the formula $$x = y$$ is not valid. What can you prove about the formula $$\neg x = y$$ in terms of validity?
3. Suppose that $$\phi$$ is an $$\mathcal{L}$$-formula and $$x$$ is a variable. Prove that $$\phi$$ is valid if and only if $$\left( \forall x \right) \left( \phi \right)$$ is valid. Thus, if $$\phi$$ has free variables $$x$$, $$y$$, and $$z$$, $$\phi$$ will be valid if and only if $$\forall x \forall y \forall z \phi$$ is valid. The sentence $$\forall x \forall y \forall z \phi$$ is called the universal closure of $$\phi$$.
4. (a) Assume that $$\models \left( \phi \rightarrow \psi \right)$$. Show that $$\phi \models \psi$$.
(b) Suppose that $$\phi$$ is $$x < y$$ and $$\psi$$ is $$z < w$$. Show that $$\phi \models \psi$$ but $$\not\models \left( \phi \rightarrow \psi \right)$$. (The slash through $$\models$$ means "does not logically imply.")

[This exercise shows that the two possible ways to define logical equivalence are not equivalent. The strong form of the definition says that $$\phi$$ and $$\psi$$ are logically equivalent if $$\models \left( \phi \rightarrow \psi \right)$$ and $$\models \left( \psi \rightarrow \phi \right)$$. The weak form of the definition states that $$\phi$$ and $$\psi$$ are logically equivalent if $$\phi \models \psi$$ and $$\psi \models \phi$$.]

This page titled 1.10: Logical Implication is shared under a CC BY-NC-SA 4.0 license and was authored, remixed, and/or curated by Christopher Leary and Lars Kristiansen (OpenSUNY) via source content that was edited to the style and standards of the LibreTexts platform.