Condition for Logical Consequence

Theorem

Let $U = \left\{{P_1, P_2, \ldots, P_n}\right\}$ be a set of logical formulas.

Let $P$ be a logical formula.

Let $U \models P$ denote that $P$ is a logical consequence of $U$.

Then $U \models P$ iff:

$\models P_1 \land P_2 \land \cdots \land P_n \implies P$

where $\models$ in this context means "equals true in all interpretations".

That is, $U \models P$ iff $P_1 \land P_2 \land \cdots \land P_n \implies P$ is a tautology.

Proof

Sufficient Condition

Suppose that $U \models P$.

Then $P$ is true in every model of $U$.

So let $\mathcal M$ be an arbitrary model of $U$.

From Implication Properties, we have $q \vdash p \implies q$: "If something is true, anything implies it."

So as $P$ is true in every model of $U$, then $P_1 \land P_2 \land \cdots \land P_n \implies P$ is likewise true in every model of $U$.

Hence $\models P_1 \land P_2 \land \cdots \land P_n \implies P$.

Necessary Condition

Proof by induction:

For all $n \in \N^*$, let $P \left({n}\right)$ be the proposition: $U \models P$ iff $\models P_1 \land P_2 \land \cdots \land P_n \implies P$.

Suppose $U = \left\{{P_1}\right\}$.

From Model Defined by Implication, we have that if $\models P_1 \implies P$, then $P_1 \models P$.

By definition, then, if $\models P_1 \implies P$, then $U \models P$.

Then $P$ is true in every model of $U$.

Basis for the Induction

Suppose $U = \left\{{P_1, P_2}\right\}$.

We need to show that if $\models P_1 \land P_2 \implies P$ then $U \models P$.

From Model Defined by Implication, we have that if $\models P_1 \land P_2 \implies P$, then $P_1 \land P_2 \models P$.

Let $\mathcal M$ be such a model.

Then $\mathcal M \left({P_1 \land P_2}\right) = T \implies \mathcal M \left({P}\right) = T$.

By definition of conjunction, $\mathcal M \left({P_1}\right) = T$ and $\mathcal M \left({P_2}\right) = T$.

Hence by definition, $\mathcal M \models Q$.

Hence it follows that $\mathcal M \left({U}\right) = T \implies \mathcal M \left({P}\right) = T$.

By definition, then, if $\models P_1 \land P_2 \implies P$, then $U \models P$.

This is our basis for the induction.

Induction Hypothesis

Let $U = \left\{{P_1, P_2, \ldots, P_k}\right\}$.

Suppose we have that:

$\models P_1 \land P_2 \land \cdots \land P_k \implies P$, then $U \models P$.

We need to show that if $U = \left\{{P_1, P_2, \ldots, P_k, P_{k+1}}\right\}$, then:

$\models P_1 \land P_2 \land \cdots \land P_k \land P_{k+1} \implies P$, then $U \models P$.

Induction Step

This is our induction step:

Let $\models P_1 \land P_2 \land \cdots \land P_k \land P_{k+1} \implies P$.

Then $\models \left({P_1 \land P_2 \land \cdots \land P_k}\right) \land P_{k+1} \implies P$.

Let $Q = P_1 \land P_2 \land \cdots \land P_k$.

Thus we have that $\models Q \land P_{k+1} \implies P$.

Let $\mathcal M$ be such a model.

Then $\mathcal M \left({Q \land P_{k+1}}\right) = T \implies \mathcal M \left({P}\right) = T$.

By definition of conjunction, $\mathcal M \left({Q}\right) = T$ and $\mathcal M \left({P_{k+1}}\right) = T$.

Hence by definition, $\mathcal M \models Q$.

Hence it follows that $\mathcal M \left({U}\right) = T \implies \mathcal M \left({P}\right) = T$.

The result follows by the Principle of Mathematical Induction.

$\blacksquare$