Material conditional#Definitions

{{Redirect|Logical conditional|other related meanings|Conditional statement (disambiguation){{!}}Conditional statement}}

{{distinguish|Material inference|Material implication (rule of inference)}}

{{Infobox logical connective

| title = Material conditional

| other titles = IMPLY

| Venn diagram = Venn1011.svg

| wikifunction = Z10329

| definition = $x \to y$

| truth table = $(1011)$

| logic gate = IMPLY_ANSI.svg

| DNF = $\overline{x} + y$

| CNF = $\overline{x} + y$

| Zhegalkin = $1 \oplus x \oplus xy$

| 0-preserving = no

| 1-preserving = yes

| monotone = no

| affine = no

| self-dual = no

}}

The material conditional (also known as material implication) is a binary operation commonly used in logic. When the conditional symbol $\to$ is interpreted as material implication, a formula $P \to Q$ is true unless $P$ is true and $Q$ is false.

Material implication is used in all the basic systems of classical logic as well as some nonclassical logics. It is assumed as a model of correct conditional reasoning within mathematics and serves as the basis for commands in many programming languages. However, many logics replace material implication with other operators such as the strict conditional and the variably strict conditional. Due to the paradoxes of material implication and related problems, material implication is not generally considered a viable analysis of conditional sentences in natural language.

Notation

In logic and related fields, the material conditional is customarily notated with an infix operator $\to$ .{{sfn|Hilbert|1918}} The material conditional is also notated using the infixes $\supset$ and $\Rightarrow$ .{{sfn|Mendelson|2015}} In the prefixed Polish notation, conditionals are notated as $Cpq$ . In a conditional formula $p\to q$ , the subformula $p$ is referred to as the antecedent and $q$ is termed the consequent of the conditional. Conditional statements may be nested such that the antecedent or the consequent may themselves be conditional statements, as in the formula $(p\to q)\to(r\to s)$ .

History

In Arithmetices Principia: Nova Methodo Exposita (1889), Peano expressed the proposition "If $A$ , then $B$ " as $A$ Ɔ $B$ with the symbol Ɔ, which is the opposite of C.{{sfn|Van Heijenoort|1967}} He also expressed the proposition $A\supset B$ as $A$ Ɔ $B$ .Note that the horseshoe symbol Ɔ has been flipped to become a subset symbol ⊂.{{sfn|Nahas|2022|page=VI}}{{sfn|Allegranza|2015}} Hilbert expressed the proposition "If A, then B" as $A\to B$ in 1918.{{sfn|Hilbert|1918}} Russell followed Peano in his Principia Mathematica (1910–1913), in which he expressed the proposition "If A, then B" as $A\supset B$ . Following Russell, Gentzen expressed the proposition "If A, then B" as $A\supset B$ . Heyting expressed the proposition "If A, then B" as $A\supset B$ at first but later came to express it as $A\to B$ with a right-pointing arrow. Bourbaki expressed the proposition "If A, then B" as $A \to B$ in 1954.{{sfn|Bourbaki|1954|page=14}}

Semantics

=Truth table=

From a classical semantic perspective, material implication is the binary truth functional operator which returns "true" unless its first argument is true and its second argument is false. This semantics can be shown graphically in the following truth table:

One can also consider the equivalence $A \to B \equiv \neg (A \land \neg B) \equiv \neg A \lor B$ .

The conditionals $(A \to B)$ where the antecedent $A$ is false, are called "vacuous truths".

Examples are ...

... with $B$ false: "If Marie Curie is a sister of Galileo Galilei, then Galileo Galilei is a brother of Marie Curie."
... with $B$ true: "If Marie Curie is a sister of Galileo Galilei, then Marie Curie has a sibling."

=Analytic tableaux=

Formulas over the set of connectives $\{\to, \bot\}$ The well-formed formulas are:

Each propositional variable is a formula.
" $\bot$ " is a formula.
If $A$ and $B$ are formulas, so is $(A \to B)$ .
Nothing else is a formula. are called f-implicational.{{sfn|Franco|Goldsmith|Schlipf|Speckenmeyer|1999}} In classical logic the other connectives, such as $\neg$ (negation), $\land$ (conjunction), $\lor$ (disjunction) and $\leftrightarrow$ (equivalence), can be defined in terms of $\to$ and $\bot$ (falsity):f-implicational formulas cannot express all valid formulas in minimal (MPC) or intuitionistic (IPC) propositional logic — in particular, $\lor$ (disjunction) cannot be defined within it. In contrast, $\{\to, \lor, \bot \}$ is a complete basis for MPC / IPC: from these, all other connectives (e.g., $\land, \neg, \leftrightarrow, \bot$ ) can be defined.

$\begin{align}
\neg A & \quad \overset{\text{def}}{=} \quad A \to \bot \\
A \land B & \quad \overset{\text{def}}{=} \quad (A \to (B \to \bot)) \to \bot \\
A \lor B & \quad \overset{\text{def}}{=} \quad (A \to \bot) \to B \\
A \leftrightarrow B & \quad \overset{\text{def}}{=} \quad \{(A \to B) \to [(B \to A) \to \bot]\} \to \bot \\
\end{align}$

The validity of f-implicational formulas can be semantically established by the method of analytic tableaux. The logical rules are

style="border: none; border-spacing: 1px; border-collapse: separate;"
style="vertical-align: top;" \| $\frac{\boldsymbol{\mathsf{T}}(A \to B)}{\boldsymbol{\mathsf{F}}(A) \quad \mid \quad \boldsymbol{\mathsf{T}}(B)}$	valign="top" \| $\frac{\boldsymbol{\mathsf{F}}(A \to B)}{\begin{array}{c} \boldsymbol{\mathsf{T}}(A) \\ \boldsymbol{\mathsf{F}}(B)\end{array}}$
colspan="2" \| $\boldsymbol{\mathsf{T}}(\bot)$ : Close the branch (contradiction) $\boldsymbol{\mathsf{F}}(\bot)$ : Do nothing (since it just asserts no contradiction)

{{collapse top

| title=Example: proof of $p \to \neg \neg p\quad$ , by method of analytic tableaux

| bg=#ffffff | fg=#000000

}}


F[p → ((p → ⊥) → ⊥)]
|
T[p]
F[(p → ⊥) → ⊥]
|
T[p → ⊥]
F[⊥]
┌────────┴────────┐
F[p]              T[⊥]
|                 |
CONTRADICTION     CONTRADICTION
(T[p], F[p])      (⊥ is true)

{{collapse top

| title=Example: proof of $\neg \neg p \to p\quad$ , by method of analytic tableaux

| bg=#ffffff | fg=#000000

}}


F[((p → ⊥) → ⊥) → p]
|
T[(p → ⊥) → ⊥]
F[p]
┌────────┴────────┐
F[p → ⊥]          T[⊥]
|                 |
T[p]            CONTRADICTION (⊥ is true)
F[⊥]
|
CONTRADICTION (T[p], F[p])

Hilbert-style proofs can be found here or here.

{{collapse top

| title=Example: proof of $(p \to q) \to ((q \to r) \to (p \to r))$ , by method of analytic tableaux

| bg=#ffffff | fg=#000000

}}


1. F[(p → q) → ((q → r) → (p → r))]
|                       // from 1
2. T[p → q]
3. F[(q → r) → (p → r)]
|                       // from 3
4. T[q → r]
5. F[p → r]
|                       // from 5
6. T[p]
7. F[r]
┌────────┴────────┐              // from 2
8a. F[p]          8b. T[q]
X        ┌────────┴────────┐     // from 4
9a. F[q]          9b. T[r]
X                 X

A Hilbert-style proof can be found here.

Syntactical properties

The semantic definition by truth tables does not permit the examination of structurally identical propositional forms in various logical systems, where different properties may be demonstrated. The language considered here is restricted to f-implicational formulas.

Consider the following (candidate) natural deduction rules.

class="wikitable"

|valign="top"| Implication Introduction ( $\to$ I)

If assuming $A$ one can derive $B$ , then one can conclude $A \to B$ .

$\frac{\begin{array}{c}
[A] \\
\vdots \\
B
\end{array}}{A \to B}$ ( $\to$ I)

$[A]$ is an assumption that is discharged when applying the rule.

|valign="top"| Implication Elimination ( $\to$ E)

This rule corresponds to modus ponens.

$\frac{A \to B \quad A}{B}$ ( $\to$ E)

$\frac{A \quad A \to B}{B}$ ( $\to$ E)

valign="top"| Double Negation Elimination (

\neg\neg

$\frac{\begin{array}{c}
(A \to \bot) \to \bot \\
\end{array}}{A}$ ( $\neg\neg$ E)

|valign="top"| Falsum Elimination ( $\bot$ E)

From falsum ( $\bot$ ) one can derive any formula.
(ex falso quodlibet)

$\frac{\bot}{A}$ ( $\bot$ E)

Minimal logic: By limiting the natural deduction rules to Implication Introduction ( $\to$ I) and Implication Elimination ( $\to$ E), one obtains (the implicational fragment of) minimal logic (as defined by Johansson).{{sfn|Johansson|1937}}

{{collapse top

| title=Proof of $P \to \neg \neg P\quad$ , within minimal logic

| bg=#ffffff | fg=#000000

}}

1.{{spaces|1}}

|[ P ]

|{{spaces|1}}// Assume

2.{{spaces|1}}

|[ P → ⊥ ]

|{{spaces|1}}// Assume

3.{{spaces|1}}

|⊥

|{{spaces|1}}// $\to$ E (1, 2)

4.{{spaces|1}}

|(P → ⊥) → ⊥)

|{{spaces|1}}// $\to$ I (2, 3), discharging 2

5.{{spaces|1}}

|P → ((P → ⊥) → ⊥)

|{{spaces|1}}// $\to$ I (1, 4), discharging 1

Intuitionistic logic: By adding Falsum Elimination ( $\bot$ E) as a rule, one obtains (the implicational fragment of) intuitionistic logic.

:The statement $P \to \neg \neg P$ is valid (already in minimal logic), unlike the reverse implication which would entail the law of excluded middle.

Classical logic: If Double Negation Elimination ( $\neg\neg$ E) is also permitted,{{refn|name="RAA"|Instead of $\neg\neg$ E one can add reductio ad absurdum as a rule to obtain (full) classical logic:{{sfn|Prawitz|1965|p=21}}{{sfn|Ayala-Rincón|de Moura|2017|pp=17-24}}

: $\frac{\begin{array}{c}
[A \to \bot] \\
\vdots \\
\bot
\end{array}}{A}$ (RAA)}} the system defines (full!) classical logic.{{sfn|Prawitz|1965|p=21}}{{sfn|Ayala-Rincón|de Moura|2017|pp=17-24}}{{sfn|Tennant|1990|p=48}}

A selection of theorems (classical logic)

In classical logic material implication validates the following:

{{collapse top

| title=Contraposition: $(\neg Q \to \neg P) \to (P \to Q)$

| bg=#ffffff | fg=#000000

}}

1.{{spaces|1}}

|[ (Q → ⊥) → (P → ⊥) ]

|{{spaces|1}}// Assume (to discharge at 9)

2.{{spaces|1}}

|[ P ]

|{{spaces|1}}// Assume (to discharge at 8)

3.{{spaces|1}}

|[ Q → ⊥ ]

|{{spaces|1}}// Assume (to discharge at 6))

4.{{spaces|1}}

|P → ⊥

|{{spaces|1}}// $\to$ E (1, 3)

5.{{spaces|1}}

|⊥

|{{spaces|1}}// $\to$ E (2, 4)

6.{{spaces|1}}

|(Q → ⊥) → ⊥

|{{spaces|1}}// $\to$ I (3, 5) (discharging 3)

7.{{spaces|1}}

|{{spaces|1}}// $\neg\neg$ E (6)

8.{{spaces|1}}

|P → Q

|{{spaces|1}}// $\to$ I (2, 7) (discharging 2)

9.{{spaces|1}}

|((Q → ⊥) → (P → ⊥)) → (P → Q)

|{{spaces|1}}// $\to$ I (1, 8) (discharging 1)

{{collapse top

| title=Peirce's law: $((P \to Q) \to P) \to P$

| bg=#ffffff | fg=#000000

}}

1.{{spaces|1}}

|[ (P → Q) → P ]

|{{spaces|1}}// Assume (to discharge at 11)

2.{{spaces|1}}

|[ P → ⊥ ]

|{{spaces|1}}// Assume (to discharge at 9)

3.{{spaces|1}}

|[ P ]

|{{spaces|1}}// Assume (to discharge at 6)

4.{{spaces|1}}

|⊥

|{{spaces|1}}// $\to$ E (2, 3)

5.{{spaces|1}}

|{{spaces|1}}// $\bot$ E (4)

6.{{spaces|1}}

|P → Q

|{{spaces|1}}// $\to$ I (3, 5) (discharging 3)

7.{{spaces|1}}

|{{spaces|1}}// $\to$ E (1, 6)

8.{{spaces|1}}

|⊥

|{{spaces|1}}// $\to$ E (2, 7)

9.{{spaces|1}}

|(P → ⊥) → ⊥

|{{spaces|1}}// $\to$ I (2, 8) (discharging 2)

10.{{spaces|1}}

|{{spaces|1}}// $\neg \neg$ E (9)

11.{{spaces|1}}

|((P → Q) → P) → P

|{{spaces|1}}// $\to$ I (1, 10) (discharging 1)

{{collapse top

| title=Vacuous conditional (IPC): $\neg P \to (P \to Q)$

| bg=#ffffff | fg=#000000

}}

1.{{spaces|1}}

| $[ P \to \bot ]$

|{{spaces|1}}// Assume

2.{{spaces|1}}

| $[ P ]$

|{{spaces|1}}// Assume

3.{{spaces|1}}

| $\bot$

|{{spaces|1}}// $\to$ E (1, 2)

4.{{spaces|1}}

| $Q$

|{{spaces|1}}// $\bot$ E (3)

5.{{spaces|1}}

| $P \to Q$

|{{spaces|1}}// $\to$ I (2, 4) (discharging 2)

6.{{spaces|1}}

| $( P \to \bot ) \to ( P \to Q )$

|{{spaces|1}}// $\to$ I (1, 5) (discharging 1)

Import-export: $P \to (Q \to R) \equiv (P \land Q) \to R$
Negated conditionals: $\neg(P \to Q) \equiv P \land \neg Q$
Or-and-if: $P \to Q \equiv \neg P \lor Q$
Commutativity of antecedents: $\big(P \to (Q \to R)\big) \equiv \big(Q \to (P \to R)\big)$
Left distributivity: $\big(R \to (P \to Q)\big) \equiv \big((R \to P) \to (R \to Q)\big)$

Similarly, on classical interpretations of the other connectives, material implication validates the following entailments:

Antecedent strengthening: $P \to Q \models (P \land R) \to Q$
Transitivity: $(P \to Q) \land (Q \to R) \models P \to R$
Simplification of disjunctive antecedents: $(P \lor Q) \to R \models (P \to R) \land (Q \to R)$

Tautologies involving material implication include:

Reflexivity: $\models P \to P$
Totality: $\models (P \to Q) \lor (Q \to P)$
Conditional excluded middle: $\models (P \to Q) \lor (P \to \neg Q)$

Discrepancies with natural language

Material implication does not closely match the usage of conditional sentences in natural language. For example, even though material conditionals with false antecedents are vacuously true, the natural language statement "If 8 is odd, then 3 is prime" is typically judged false. Similarly, any material conditional with a true consequent is itself true, but speakers typically reject sentences such as "If I have a penny in my pocket, then Paris is in France". These classic problems have been called the paradoxes of material implication.{{sfn|Edgington|2008}} In addition to the paradoxes, a variety of other arguments have been given against a material implication analysis. For instance, counterfactual conditionals would all be vacuously true on such an account, when in fact some are false.{{refn|For example, "If Janis Joplin were alive today, she would drive a Mercedes-Benz", see {{harvtxt|Starr|2019}}}}

In the mid-20th century, a number of researchers including H. P. Grice and Frank Jackson proposed that pragmatic principles could explain the discrepancies between natural language conditionals and the material conditional. On their accounts, conditionals denote material implication but end up conveying additional information when they interact with conversational norms such as Grice's maxims.{{sfn|Edgington|2008}}{{sfn|Gillies|2017}} Recent work in formal semantics and philosophy of language has generally eschewed material implication as an analysis for natural-language conditionals.{{sfn|Gillies|2017}} In particular, such work has often rejected the assumption that natural-language conditionals are truth functional in the sense that the truth value of "If P, then Q" is determined solely by the truth values of P and Q.{{sfn|Edgington|2008}} Thus semantic analyses of conditionals typically propose alternative interpretations built on foundations such as modal logic, relevance logic, probability theory, and causal models.{{sfn|Gillies|2017}}{{sfn|Edgington|2008}}{{sfn|Von Fintel|2011}}

Similar discrepancies have been observed by psychologists studying conditional reasoning, for instance, by the notorious Wason selection task study, where less than 10% of participants reasoned according to the material conditional. Some researchers have interpreted this result as a failure of the participants to conform to normative laws of reasoning, while others interpret the participants as reasoning normatively according to nonclassical laws.{{sfn|Oaksford |Chater|1994}}{{sfn|Stenning|van Lambalgen|2004}}{{sfn|Von Sydow|2006}}

=Conditionals=

Notes

Bibliography

{{Cite web |url=https://math.stackexchange.com/a/1146502/186330 |title=elementary set theory – Is there any connection between the symbol ⊃ when it means implication and its meaning as superset? |access-date=2022-08-10 |first=Mauro |last=Allegranza |date=2015-02-13 |website=Mathematics Stack Exchange |publisher=Stack Exchange Inc |language=en |at=Answer}}

{{Cite book |last1=Ayala-Rincón |first1=Mauricio |last2=de Moura |first2=Flávio L. C. |title=Applied Logic for Computer Scientists |date=2017 |publisher=Springer |series=Undergraduate Topics in Computer Science |isbn=978-3-319-51651-6 |doi=10.1007/978-3-319-51653-0 |url=https://link.springer.com/book/10.1007/978-3-319-51653-0 }}

{{cite book |last=Bourbaki |first=N. |title=Théorie des ensembles |date=1954 |publisher=Hermann & Cie, Éditeurs |location=Paris |page=14}}

{{cite encyclopedia |first=Dorothy |last=Edgington |editor=Edward N. Zalta |year=2008 |title=Conditionals |encyclopedia=The Stanford Encyclopedia of Philosophy |edition=Winter 2008 |url=http://plato.stanford.edu/archives/win2008/entries/conditionals/}}

{{cite encyclopedia|last=Von Fintel|first=Kai |editor-last1=von Heusinger |editor-first1= Klaus | editor-last2= Maienborn |editor-first2= Claudia | editor-first3=Paul |editor-last3=Portner |encyclopedia=Semantics: An international handbook of meaning |title=Conditionals |url=http://mit.edu/fintel/fintel-2011-hsk-conditionals.pdf |year=2011 |pages=1515–1538 |publisher= de Gruyter Mouton |doi=10.1515/9783110255072.1515|hdl=1721.1/95781 |isbn=978-3-11-018523-2 |hdl-access=free }}

{{cite journal | doi=10.1016/S0166-218X(99)00038-4 | volume=96-97 | title=An algorithm for the class of pure implicational formulas | journal=Discrete Applied Mathematics | pages=89–106 | year=1999 | last1=Franco | first1=John | last2=Goldsmith | first2=Judy | last3=Schlipf | first3=John | last4=Speckenmeyer | first4=Ewald | last5=Swaminathan | first5=R.P. | doi-access=free}}

{{cite encyclopedia |last=Gillies|first=Thony |editor-last1=Hale |editor-first1=B. | editor-last2=Wright |editor-first2=C. | editor-last3=Miller |editor-first3=A. |encyclopedia=A Companion to the Philosophy of Language |title=Conditionals |url=http://www.thonygillies.org/wp-content/uploads/2015/11/gillies-conditionals-handbook.pdf |year=2017 |pages=401–436 |publisher=Wiley Blackwell |doi=10.1002/9781118972090.ch17|isbn=9781118972090 }}

{{Cite book |editor-first=Jean |editor-last=Van Heijenoort |title=From Frege to Gödel: A Source Book in Mathematical Logic, 1879–1931 |year=1967 |publisher=Harvard University Press |isbn=0-674-32449-8 |pages=84–87}}

{{cite book |last=Hilbert |first=D. |title=Prinzipien der Mathematik (Lecture Notes edited by Bernays, P.) |date=1918}}

{{cite journal|last= Johansson|first=Ingebrigt|author-link=Ingebrigt Johansson|year=1937|title=Der Minimalkalkül, ein reduzierter intuitionistischer Formalismus|url=http://www.numdam.org/item/CM_1937__4__119_0|journal=Compositio Mathematica|volume=4|pages=119–136|language=de}}

{{Cite book | last =Mendelson | first =Elliott | author-link =Elliott Mendelson |title=Introduction to Mathematical Logic | year=2015 | edition=6th | location=Boca Raton | publisher=CRC Press/Taylor & Francis Group (A Chapman & Hall Book) | isbn=978-1-4822-3778-8 | page=2 }}

{{Cite web |url=https://github.com/mdnahas/Peano_Book/blob/46e27bdb5aed51c078ad99e5a78d134fd2a0c3ca/Peano.pdf |title=English Translation of 'Arithmetices Principia, Nova Methodo Exposita' |access-date=2022-08-10 |first=Michael |last=Nahas |date=25 Apr 2022 |publisher=GitHub}}

{{cite journal |last1=Oaksford |first1=M. |last2=Chater |first2=N. |year=1994 |title=A rational analysis of the selection task as optimal data selection |journal=Psychological Review |volume=101 |issue=4 |pages=608–631 |doi=10.1037/0033-295X.101.4.608 |citeseerx=10.1.1.174.4085 |s2cid=2912209 }}

{{cite book | last = Prawitz | first = Dag | author-link = Dag Prawitz | year = 1965 | title = Natural Deduction: A Proof-Theoretic Study | series = Acta Universitatis Stockholmiensis; Stockholm Studies in Philosophy, 3 | publisher = Almqvist & Wiksell | location = Stockholm, Göteborg, Uppsala | oclc = 912927896 }}

{{cite encyclopedia |last=Starr |first=Will |editor-last1=Zalta |editor-first1=Edward N. |encyclopedia=The Stanford Encyclopedia of Philosophy |title=Counterfactuals |year=2019 |url=https://plato.stanford.edu/archives/fall2019/entries/counterfactuals}}

{{cite journal |last1=Stenning |first1=K. |last2=van Lambalgen |first2=M. |year=2004 |title=A little logic goes a long way: basing experiment on semantic theory in the cognitive science of conditional reasoning |journal=Cognitive Science |volume=28 |issue=4 |pages=481–530 |doi=10.1016/j.cogsci.2004.02.002 |citeseerx=10.1.1.13.1854 }}

{{cite thesis |last=Von Sydow |first=M. |title=Towards a Flexible Bayesian and Deontic Logic of Testing Descriptive and Prescriptive Rules |year=2006 |location=Göttingen |publisher=Göttingen University Press |doi=10.53846/goediss-161 |s2cid=246924881 |url=https://ediss.uni-goettingen.de/handle/11858/00-1735-0000-0006-AC29-9|type=doctoralThesis |doi-access=free }}

{{cite book | last = Tennant | first = Neil | title = Natural Logic | publisher = Edinburgh University Press | year = 1990 | orig-year = 1978 | edition = 1st, repr. with corrections | isbn = 0852245793 }}

External links

{{cite SEP |url-id=conditionals |title=Conditionals |last=Edgington |first=Dorothy}}

Category:Logical connectives

Category:Conditionals

Category:Logical consequence

Category:Semantics

style="border: none; border-spacing: 1px; border-collapse: separate;"
style="vertical-align: top;" \| $\frac{\boldsymbol{\mathsf{T}}(A \to B)}{\boldsymbol{\mathsf{F}}(A) \quad \mid \quad \boldsymbol{\mathsf{T}}(B)}$	valign="top" \| $\frac{\boldsymbol{\mathsf{F}}(A \to B)}{\begin{array}{c} \boldsymbol{\mathsf{T}}(A) \\ \boldsymbol{\mathsf{F}}(B)\end{array}}$
colspan="2" \| $\boldsymbol{\mathsf{T}}(\bot)$ : Close the branch (contradiction) $\boldsymbol{\mathsf{F}}(\bot)$ : Do nothing (since it just asserts no contradiction)

Material conditional#Definitions

Notation

History

Semantics

=Truth table=

=Analytic tableaux=

Syntactical properties

A selection of theorems (classical logic)

Discrepancies with natural language

See also

=Conditionals=

Notes

Bibliography

Further reading

External links