Editing Natural deduction (section)

===Gentzen's tree notation===

[[Gerhard Gentzen|Gentzen]], who invented natural deduction, had his own notation style for arguments. This will be exemplified by a simple argument below. Let's say we have a simple example argument in [[Propositional calculus|propositional logic]], such as, "if it's raining then it's cloudly; it is raining; therefore it's cloudy". (This is in [[modus ponens]].) Representing this as a list of propositions, as is common, we would have:

:<math>1) ~ P \to Q</math>
:<math>2) ~ P</math>
:<math>\therefore ~ Q</math>

In Gentzen's notation,{{sfn|Pelletier|Hazen|2024}} this would be written like this:

:<math>\frac{P \to Q, P}{Q}</math>

The premises are shown above a line, called the '''inference line''',{{sfn|von Plato|2013|pp=9,32,121}}{{sfn|Sutcliffe}} separated by a '''comma''', which indicates ''combination'' of premises.{{sfn|Restall|2018}} The conclusion is written below the inference line.{{sfn|von Plato|2013|pp=9,32,121}} The inference line represents ''syntactic consequence'',{{sfn|von Plato|2013|pp=9,32,121}} sometimes called ''deductive consequence'',{{sfn|Magnus|Button|Trueman|Zach|2023|loc=CHAPTER 20, Proof-theoretic concepts|p=142}}{{sfn|Paseau|Leek}} which is also symbolized with ⊢.{{sfn|Paseau|Leek}} So the above can also be written in one line as <math>P \to Q, P \vdash Q</math>. (The turnstile, for syntactic consequence, is of lower [[Order of operations|precedence]] than the comma, which represents premise combination, which in turn is of lower precedence than the arrow, used for material implication; so no parentheses are needed to interpret this formula.){{sfn|Restall|2018}}

Syntactic consequence is contrasted with ''semantic consequence'',{{sfn|Paseau|Pregel|2023}} which is symbolized with ⊧.{{sfn|Magnus|Button|Trueman|Zach|2023|loc=12.5 The double turnstile|p=82}}{{sfn|Paseau|Leek}} In this case, the conclusion follows ''syntactically'' because natural deduction is a [[Propositional_calculus#Syntactic_proof_systems|syntactic proof system]], which assumes [[inference rules]] [[Postulate|as primitives]].

Gentzen's style will be used in much of this article. Gentzen's discharging annotations used to internalise hypothetical judgments can be avoided by representing proofs as a tree of [[sequent]]s ''Γ ⊢A'' instead of a tree of judgments that A (is true).