In logic, entailment (or logical implication) is a relation between sets of formulae such that, if A and B are sets of formulae of a formal language, then A entails B if and only if every model (or interpretation) that makes all the members of A true, makes at least one of the members of B true. Another way of stating this is to say that the class K of models of A is a (possibly improper) subclass of the class K' of models of some subset B' of B—i.e. K⊆K'. Alternatively, we can say that A entails B if and only if, for every subset B' of B, the class of models of A is a subclass of the union of the classes of each B'. This article includes a list of works cited or a list of external links, but its sources remain unclear because it lacks in-text citations. ... In pragmatics (linguistics), entailment is the relationship between two sentences where the truth of one (A) requires the truth of the other (B). ... Logic (from Classical Greek λόγος logos; meaning word, thought, idea, argument, account, reason, or principle) is the study of the principles and criteria of valid inference and demonstration. ... In logical calculus of mathematics, the logical conditional (also known as the material implication, sometimes material conditional) is a binary logical operator connecting two statements, if p then q where p is a hypothesis (or antecedent) and q is a conclusion (or consequent). ...

In symbols,

states that the set A of sentences entails the set B of sentences. Notice that entailment is a semantic relation. Often it is stated less generally for B a single formula rather than a set of formulæ. In our definition, this is equivalent to the case when B is a singleton consisting of a sole formula.

Example 1. Let the set A of sentences include 'All horses are animals' and 'All stallions are horses', and the set B of sentences include 'All stallions are animals'. Then , i.e. A entails B, holds.

Example 2. Put and . Then A does not entail B, since the empty model is a model of A, but it is not a model of B - i.e. it is not the case that all models of A are models of B. In first-order logic the empty domain is the empty set having no members. ...

In Venn diagram form, looks like this: A Venn diagram of sets A, B, and C Venn diagrams are illustrations used in the branch of mathematics known as set theory. ...

Image File history File links Venn_A_subset_B.svg‎ Venn diagram for A is a subset of B. Modification of Image:Venn A intersect B.svg based on w:en:Image:Venn A subset B.png File links The following pages on the English Wikipedia link to this file (pages on other...

If for a non-empty finite set of formulae with n>1, we say that the disjunction is valid. In particular, if X = {φ} is a singleton, then φ is said to be valid. If X is an infinite set of first-order formulae, then there is some finite subset X' of X such that the disjunction of the members of X' is valid. This is a consequence of the compactness property of first-order languages. In psychology a conclusion is said to be valid, if and only if, it is based on true premises. ... The compactness theorem is a basic fact in symbolic logic and model theory and asserts that a set (possibly infinite) of first-order sentences is satisfiable, i. ...

Relationship between entailment and deduction

Ideally, entailment and deduction would be extensionally equivalent. However, this is not always the case. In such a case, it is useful to break the equivalence down into its two parts: Look up deduction in Wiktionary, the free dictionary. ... In mathematics, an equivalence relation on a set X is a binary relation on X that is reflexive, symmetric and transitive, i. ...

A deductive system S is complete for a language L if and only if implies : that is, if all valid arguments are deducible (or provable), where denotes the deducibility relation for the system S. In psychology a conclusion is said to be valid, if and only if, it is based on true premises. ...

A deductive system S is sound for a language L if and only if implies : that is, if no invalid arguments are provable. (This article discusses the soundess notion of informal logic. ...

Many introductory textbooks (e.g. Mendelson's "Introduction to Mathematical Logic") that introduce first-order logic, include a complete and sound inference system for the first-order logic. In contrast, second-order logic - which allows quantification over predicates - does not have a complete and sound inference system with respect to a full Henkin (or standard) semantics. In mathematical logic, second-order logic is an extension of first-order logic, which itself is an extension of propositional logic. ...

A related topic that sometimes causes confusion is Gödel's incompleteness theorem, which states that there are sentences of certain theories that cannot be proved by the underlying deductive system for the theory, even though such sentences are true in the standard interpretation of the theory. This holds even if the underlying deductive system is complete in the above sense. It is a consequence of the existence of nonstandard interpretations of theories. In mathematical logic, Gödels incompleteness theorems are two celebrated theorems proven by Kurt Gödel in 1931. ...

Relationship with Material Implication

In many cases, entailment corresponds to material implication (denoted by ) in the following way. In classical logic, if and only if there are some finite subsets of A and of B such that . There is also the deduction theorem that holds in classical logic. In logical calculus of mathematics, the logical conditional (also known as the material implication, sometimes material conditional) is a binary logical operator connecting two statements, if p then q where p is a hypothesis (or antecedent) and q is a conclusion (or consequent). ... In mathematical logic, the deduction theorem states that if a formula F is deducible from E then the implication E → F is demonstrable (i. ...

See also

• Inference
• Entailment Analysis