Argument Validity and Logical Entailment

The core definition

A set of premises $\Gamma=\{\gamma_1,\dots,\gamma_n\}$ logically entails a conclusion $\varphi$, written $\Gamma\models\varphi$, iff every interpretation that makes all of $\gamma_1,\dots,\gamma_n$ true also makes $\varphi$ true. An argument is valid precisely when its premises entail its conclusion.

Equivalently (deduction theorem form):

$\gamma_1,\dots,\gamma_n\models\varphi \iff (\gamma_1\wedge\cdots\wedge\gamma_n)\to\varphi \text{ is a tautology.}$

Validity is about form, not about whether the sentences happen to be true in the real world. True premises and a true conclusion can still form an invalid argument; the question is whether the truth of the premises forces the conclusion.

Two ways to settle a validity question

The asymmetry is the whole game: to prove entailment you must rule out every counter-model, but to refute it you need only one. So when you suspect an argument is invalid, hunt directly for the counterexample.

For propositional logic an interpretation is a truth assignment to the atoms; for first-order logic it is a structure (a domain plus interpretations of the relation/function symbols), and a "counterexample" is a whole counter-structure.

Worked mini-example (propositional)

Does $\;p\to m,\; p\to f,\; m\wedge f\;\models\; p\;$? This is the affirming-the-consequent pattern. Try $p=F,\,m=T,\,f=T$:

• $p\to m = F\to T = T$,
• $p\to f = F\to T = T$,
• $m\wedge f = T$,
• conclusion $p = F$.

All three premises are true while the conclusion is false, so the entailment fails — the argument is invalid.

Entailment is directional

$\alpha\models\beta$ and $\beta\models\alpha$ are independent claims. To decide which way (if any) holds between two formulas, look for a counterexample in each direction separately; only if neither direction has one do the formulas entail each other (logical equivalence, $\alpha\equiv\beta$).

First-order counter-structures

In FOL, refuting $\Gamma\models\varphi$ means building one model of $\Gamma$ in which $\varphi$ fails. Two reliable tricks:

• Strict orders defeat "max/min" claims: $(\mathbb{Z},<)$ is transitive and antisymmetric, every element has a larger one ($\forall x\,\exists y\,x<y$), yet no single element is largest ($\neg\exists y\,\forall x\,x<y$).
• Kill an antecedent for free: an implication (or a $\forall x\,\exists y$ statement with a dead-end element) is vacuously true when its antecedent fails — handy for satisfying a hypothesis while breaking the conclusion.

Soundness vs validity

These are different notions; do not confuse them:

So a valid argument can have a false conclusion (if a premise is false), and an argument with a true conclusion can be invalid.

Pitfall: To refute an entailment you need one counterexample; to confirm it you must rule out all of them. Never declare $\Gamma\models\varphi$ from a single satisfying row — and when comparing two formulas, check both directions, because entailment is asymmetric.