A topic in the Open Knowledge Graph — a free, open map of 15,290 topics and the order to learn them in.
A set of formulas Γ entails a formula φ (written Γ ⊨ φ) if every interpretation that makes all formulas in Γ true also makes φ true. This semantic notion of consequence is central to understanding what it means for one set of premises to logically justify a conclusion.
Distinguish between entailment (semantic, truth-based) and derivability (syntactic, proof-based). Work with small concrete examples showing when entailment holds and when counterexamples exist.
The notion of logical consequence makes precise what it means for a conclusion to *follow from* premises. You already understand logical equivalence — when two formulas are true in exactly the same models. Entailment is a directed version of this: Γ ⊨ φ says the premises in Γ *force* φ to be true, in the sense that φ holds in every interpretation where all of Γ holds. If any interpretation satisfies all of Γ but falsifies φ, that interpretation is a *counterexample*, and the entailment fails.
The definition is entirely semantic — it quantifies over all interpretations with no reference to proofs. To verify Γ ⊨ φ, you consider every possible assignment of truth values to propositional atoms, restrict attention to those satisfying every formula in Γ, and check that φ is satisfied in all of them. For finite sets Γ in propositional logic, this is mechanically checkable via truth tables, though the procedure grows exponentially with the number of atoms.
A common confusion is between entailment and the material conditional. The formula A → B is a sentence in the object language — it may be true in some interpretations and false in others. The entailment {A} ⊨ B is a metalevel claim about all interpretations simultaneously. They are related: {A} ⊨ B if and only if A → B is a *tautology* (true in every interpretation). But "A → B is true in this particular interpretation" is a much weaker statement than "A entails B." Confusing these two levels — the object language and the metalanguage — is one of the most persistent sources of error in logic.
Entailment (⊨) must also be distinguished from syntactic derivability (⊢), which asks whether φ can be derived from Γ using a fixed set of proof rules. These are conceptually independent notions: a proof system is *sound* if Γ ⊢ φ implies Γ ⊨ φ (every derivable formula is a genuine semantic consequence), and *complete* if Γ ⊨ φ implies Γ ⊢ φ (every semantic consequence is provable). Soundness and completeness together establish that for standard logical systems, the semantic and syntactic notions coincide — a profound alignment that is far from obvious a priori.
Understanding entailment also illuminates what makes an argument *invalid*. A deductive argument is valid precisely when the premises entail the conclusion — when there is no interpretation making all premises true and the conclusion false. Finding such a counterexample is the formal version of what informal logicians call "showing the argument is invalid." This connection between model-theoretic semantics and practical argumentation is what gives logical consequence its central role in both formal logic and everyday reasoning.