Entailment Information & Entailment Links at HealthHaven.com

This article is about entailment in logic. For the historical legal practice of restricting the descent of property, see fee tail. For entailment as a term in pragmatics, see entailment (pragmatics).

In linguistics, entailment is the relationship between two sentences where the truth of one (A) requires the truth of the other (B). This relationship is generalized below.

As a tool or method to make progress, one might use the entailment concept. For example, if one recognizes that "were A true, B must be true as well", then one might usefully shift attention from some valid position (say A) to another (say B).

1 Introduction - entailment in logic
2 Relationship between entailment and deduction
3 Relationship with material implication
4 Philosophical Issues
5 Discussion
- 5.1 Example
6 Symbolization
7 Comparison with other conditional statements
8 Relational properties
9 See also
10 External links
11 Notes
12 References

[edit] Introduction - entailment in logic

[edit] 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:

A deductive system S is complete for a language L if and only if $A \models_L X$ implies $A \vdash_S X$ : that is, if all valid arguments are deducible (or provable), where $\vdash_S$ denotes the deducibility relation for the system S.

A deductive system S is sound for a language L if and only if $A \vdash_S X$ implies $A \models_L X$ : that is, if no invalid arguments are provable.

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.

[edit] Relationship with material implication

In many cases, entailment corresponds to material implication (denoted by $\supset$ ) in the following way. In classical logic, $A\models B$ if and only if there are some finite subsets $\{A_1,\dots,A_n\}$ of A and $\{B_1,\dots,B_m\}$ of B such that $\Phi\models A_1\land\dots\land A_n\supset B_1\lor\dots\lor B_m$ .^{[citation needed]} There is also the deduction theorem that holds in classical logic.

[edit] Philosophical Issues

The literature is ambiguous regarding precisely what 'logical implication' means. Sometimes it is taken to be a pretheoretic notion capable of definition in several ways, usually involving modality and stated something like "A set of sentences logically implies a sentence A if and only if it is impossible that all the members of the set be true while A false". Other times it is taken as the definition given in the introduction to this article, perhaps as a replacement for the pretheoretic notion itself. This often occurs in the sciences and mathematics; that is, intuitive notions get replaced by more precise, rigorously defined ones. E.g., in mathematics, many now take 'computable' in the sense of 'effectively calculable' to be 'computable' in the sense of Turing, Church, Godel, Herbrand, or Post.^[1]

It is impossible to state rigorously the definition of 'logical implication' as it is understood pretheoretically, but many have taken the Tarskian model-theoretic account as a replacement for it. Some, e.g. Etchemendy 1990, have argued that they do not coincide, not even if they happen to be coextensional (which Etchemendy believes they are not). This debate has received some recent attention.^[2]

It is often thought that a peculiar feature of logical implication is that a contradiction implies anything and that anything implies a validity. For example, 'Abraham Lincoln was president of the US' implies '2+2=4', and 'the white dot is black' implies 'the integer 25 is greater than the integer 30'. The peculiarity in these examples is oft-attributed to a lack of relevance between the two sentences. A formal notion of relevance has been characterized by relevant logic and applied to the notion of logical implication in the seminal work of Anderson and Belnap 1975. Another property they argue that implication should have is necessity. Thus A implies B only if it is necessary that A implies B. This feature of implication is lacking in the usual model-theoretic definition (i.e. the one given in the introduction).

Some logicians draw a firm distinction between the conditional connective (the syntactic sign " $\rightarrow$ "), and the implication relation (the formal object denoted by the double arrow symbol " $\Rightarrow$ "). These logicians use the phrase not p or q for the conditional connective and the term implies for the implication relation. Some explain the difference by saying that the conditional is the contemplated relation while the implication is the asserted relation. In most fields of mathematics, it is treated as a variation in the usage of the single sign " $\Rightarrow$ ", not requiring two separate signs. Not all of those who use the sign " $\rightarrow$ " for the conditional connective regard it as a sign that denotes any kind of object, but treat it as a so-called syncategorematic sign, that is, a sign with a purely syntactic function. For the sake of clarity and simplicity in the present introduction, it is convenient to use the two-sign notation, but allow the sign " $\rightarrow$ " to denote the boolean function that is associated with the truth table of the material conditional. These considerations result in the following scheme of notation.

$\begin{matrix} p \rightarrow q & \quad & \quad & p \Rightarrow q \\ \mbox{not}\ p \ \mbox{or}\ q & \quad & \quad & p \ \mbox{implies}\ q \end{matrix}$

[edit] Discussion

The usage of the terms logical implication and material implication varies from field to field and even across different contexts of discussion. One way to minimize the potential confusion is to begin with a focus on the various types of formal objects that are being discussed, of which there are only a few, taking up the variations in language as a secondary matter.

The main formal object under discussion is a logical operation on two logical values, typically the values of two propositions, that produces a value of false only in the case the first operand is true and the second operand is false:

Venn diagram of the material implication $A \rightarrow B$
which is the same as $\neg A \or B$
The left circle represents the statement A, the right circle the statement B.
The material implication is false only in the case, represented by the white area: when A is true, but B is false.

Venn diagram of the logical implication $A \Rightarrow B$
It tells that the material implication $A \rightarrow B$ is always true.
The left circle represents the statement A, the right circle the statement B.
The logical implication tells, that A without B is never the case.

In set theory there is the same difference between the operation $A^c \cup B$ and the relation $A \subseteq B$ meaning $A \cap B^c = \emptyset$ .

[edit] Example

On the way from $A \subseteq B$ to $A \cap B^c = \emptyset$ the difference between logical ( $\Rightarrow$ ) and material implication ( $\rightarrow$ ) can be seen in an easy calculation:

$A \subseteq B$

$\Leftrightarrow (x \in A \Rightarrow x \in B)$

$\Leftrightarrow \forall{x} (x \in A \rightarrow x \in B)$

$\Leftrightarrow \forall{x} (x \notin A \or x \in B)$

$\Leftrightarrow \neg \exists{x} (x \in A \and x \notin B)$

$\Leftrightarrow \neg \exists{x} (x \in A \cap B^c)$

$\Leftrightarrow (A \cap B^c = \emptyset)$

The operation $\rightarrow$ can be expressed by $\or$ and $\neg$ . The relation $\Rightarrow$ can be expressed by $\rightarrow$ and the universal quantifier $\forall$ .

[edit] Symbolization

A common exercise for an introductory logic text to include is symbolizations. These exercises give a student a sentence or paragraph of text in ordinary language which the student has to translate into the symbolic language. This is done by recognizing the ordinary language equivalents of the logical terms, which usually include the material conditional, disjunction, conjunction, negation, and (frequently) biconditional. More advanced logic books and later chapters of introductory volumes often add identity, Existential quantification, and Universal quantification.

Different phrases used to identify the material conditional in ordinary language include if, only if, given that, provided that, supposing that, implies, even if, and in case. Many of these phrases are indicators of the antecedent, but others indicate the consequent. It is important to identify the "direction of implication" correctly. For example, "A only if B" is captured by the statement

A → B,

but "A, if B" is correctly captured by the statement

B → A

When doing symbolization exercises, it is often required that the student give a scheme of abbreviation that shows which sentences are replaced by which statement letters. For example, an exercise reading "Kermit is a frog only if muppets are animals" yields the solution:

A → B
A—Kermit is a frog.
B—Muppets are animals.

Using the horseshoe "⊃" symbol for implication is falling out of favor due to its conflict with the superset symbol $\supset$ used by the Algebra of sets. A set interpretation of " $A \to B$ " is "{x| A(x) is true} $\subseteq$ {x| B(x) is true}".

[edit] Comparison with other conditional statements

The use of the operator is stipulated by logicians, and, as a result, can yield some unexpected truths. For example, any material conditional statement with a false antecedent is true. So the statement "2 is odd implies Paris is in America" is true. Similarly, any material conditional with a true consequent is true. So the statement, "If pigs fly, then Paris is in France" is true.

These unexpected truths arise because speakers of English (and other natural languages) are tempted to equivocate between the material conditional and the indicative conditional, or other conditional statements, like the counterfactual conditional and the material biconditional. This temptation can be lessened by reading conditional statements without using the words "if" and "then". The most common way to do this is to read A → B as "it is not the case that A and/or it is the case that B" or, more simply, "A is false and/or B is true". (This equivalent statement is captured in logical notation by $\neg A \vee B$ , using negation and disjunction.)

[edit] Relational properties

Implication, when taken as an operation over symbols, has two important properties that ally it to some well-known relations in mathematical discourse. These are:

it is reflexive: A → A = T (the tautology).
it is transitive: if A → B = T and B → C = T, then A → C = T.

One implication of these properties is that the two-sided relation, "A → B = T and B → A = T", defines an equivalence over possible inputs.

[edit] See also

[edit] External links

Entailment Analysis

[edit] Notes

^ Davis 1965
^ Goble 2001 See Chapter 6 for a good introduction.

[edit] References

Anderson, A.R.; Belnap, N.D., Jr. (1975), Entailment, 1, Princeton, NJ: Princeton
Brown, Frank Markham (2003), Boolean Reasoning: The Logic of Boolean Equations 1st edition, Kluwer Academic Publishers, Norwell, MA. 2nd edition, Dover Publications, Mineola, NY, 2003.
Edgington, Dorothy (2001), Conditionals, Blackwell in Lou Goble (ed.), The Blackwell Guide to Philosophical Logic.
Edgington, Dorothy (2006), Conditionals, http://plato.stanford.edu/entries/conditionals in Edward N. Zalta (ed.), The Stanford Encyclopedia of Philosophy.
Davis, Martin, (editor) (1965), The Undecidable, Basic Papers on Undecidable Propositions, Unsolvable Problems And Computable Functions, New York: Raven Press . Papers include those by Gödel, Church, Rosser, Kleene, and Post.
Goble, Lou (ed.) (2001), The Blackwell Guide to Philosophical Logic, Blackwell
Quine, W.V. (1982), Methods of Logic, Cambridge, MA: Harvard University Press (1st ed. 1950), (2nd ed. 1959), (3rd ed. 1972), (4th edition, 1982).