Logic: From Aristotle to Gödel — The Architecture of Valid Inference

Every argument tries to convince us of something on the strength of something else: from certain premises, a conclusion is drawn. But what makes that move legitimate? Why does “all men are mortal; Socrates is a man; therefore Socrates is mortal” strike us as impeccable, while “some swans are white; this animal is a swan; therefore this animal is white” does not? The answer to that question — what makes a piece of reasoning hold — is the business of logic, one of philosophy’s oldest and most technically demanding disciplines. Born as a reflection on the art of demonstration and debate, logic has traveled twenty-five centuries to become, in the twentieth, a formal science capable of clarifying — and also of exposing the limits of — mathematical reason itself.

1. What logic is: validity, truth, and form

Logic studies the conditions under which a conclusion follows from premises — not the particular content of this or that argument, but its form. An argument is valid when it is impossible for its premises to be true and its conclusion false at the same time. Validity is not the same as truth: an argument can be valid while having false premises (“every fish flies; the whale is a fish; therefore the whale flies” is a valid form, even though both premises are false), and an argument can have true premises and a true conclusion without being valid, if the conclusion does not actually follow from them. When an argument is valid and its premises are true, it is said to be sound.

This distinction between validity and truth is what allows logic to study the logical form of arguments independently of their content: “all A are B; all B are C; therefore all A are C” is valid whatever meaning we assign to A, B, and C. It is this formal character — the fact that the terms can be replaced by variables without any loss of validity — that sets logic apart from any particular science.

The tradition also distinguishes deductive from inductive arguments. In a deductive argument, the conclusion is meant to follow necessarily from the premises — there is no middle ground between validity and invalidity. In an inductive argument, the conclusion is presented as probable or reasonable in light of the premises, but not as necessary: however much evidence accumulates in favor of “every raven is black,” the conclusion remains, in principle, refutable by a single counterexample. Formal logic, as it developed from Aristotle to Gödel, concerned itself chiefly with deduction; the systematic study of induction — its justification and its problems — belongs more properly to epistemology and philosophy of science, even though so-called “inductive logic” (associated above all with Rudolf Carnap) has sought to formalize it in probabilistic terms.

Finally, it is worth distinguishing formal logic, which studies validity through symbolic systems and their syntactic and semantic properties, from informal logic, a more recent field (consolidated from the second half of the twentieth century onward) that analyzes natural-language argumentation, fallacies, and argumentation schemes as they actually occur in everyday, legal, or scientific discourse — without necessarily translating them into a symbolic calculus.

2. Aristotle and the birth of syllogistic

Logic as an autonomous discipline begins with Aristotle, whose logical treatises were gathered by ancient editors under the title Organon (“instrument”) — a set of works (Categories, On Interpretation, Prior Analytics, Posterior Analytics, Topics, and Sophistical Refutations) conceived not as a branch of philosophy alongside physics or ethics, but as the methodological tool that every science requires.

The core of Aristotelian logic is the theory of the categorical proposition — statements that affirm or deny a predicate of a subject, with universal or particular quantity. The scholastic tradition would later classify these propositions into four types, labeled by the letters A (universal affirmative: “every S is P”), E (universal negative: “no S is P”), I (particular affirmative: “some S is P”), and O (particular negative: “some S is not P”). The logical relations among these four forms — contradiction, contrariety, subcontrariety, and subalternation — would later be systematized in what came to be called the square of opposition, a diagram that organizes the valid inferences between them.

On this basis, Aristotle builds the syllogism: an argument made up of two categorical premises and a conclusion, organized around a middle term that appears in both premises but not in the conclusion, and that is what links the conclusion’s two terms. Depending on the position of the middle term within the premises, three syllogistic figures are distinguished; and depending on the combination of A, E, I, O propositions within each figure, one obtains the different moods, only some of which are valid. Medieval logicians such as Peter of Spain and William of Sherwood coined, for pedagogical purposes, mnemonic names for the valid moods — Barbara, Celarent, Darii, Ferio, among others — whose very vowels encode the sequence of A, E, I, O propositions in the argument.

Syllogistic is a logic of terms: its object is the relations among classes of things (S, P, M), not among whole propositions. This feature sharply distinguishes it from the logic the Stoics would develop a few decades later, and it is also the very point that Frege’s logic, two millennia afterward, would come to supersede.

3. The Stoics’ propositional logic

While the Aristotelian school analyzed the internal structure of propositions, the Stoic school — chiefly in the work of Chrysippus, third head of the Stoa and, according to ancient tradition, the author of hundreds of treatises now almost entirely lost — developed something different: a logic that takes whole propositions, not terms, as its basic units, joined by connectives such as “if… then,” “and,” and “or.” It is, in substance, the first systematic propositional logic in history.

According to the testimony of Diogenes Laërtius and Sextus Empiricus, the Stoic logicians identified five inference schemas regarded as indemonstrable — valid in themselves, requiring no proof — which served as the basis for evaluating any other propositional argument. In terms later logic would make familiar, these correspond to forms such as: if the first, then the second; but the first; therefore the second (what the Latin scholastic tradition would call modus ponens); if the first, then the second; but not the second; therefore not the first (modus tollens); and further variants involving the negation of conjunctions and the affirmation or denial of disjunctions.

A famous episode in this logic is the controversy over the truth conditions of the conditional (“if… then”), waged between the Megarian philosophers Philo of Megara and Diodorus Cronus: Philo defended a purely extensional criterion (the conditional is false only when the antecedent is true and the consequent false — a position close to the modern material conditional), while Diodorus demanded a stronger modal condition, tied to the impossibility of the antecedent ever being true while the consequent is false at any time. Chrysippus, in turn, proposed an even more demanding criterion, grounded in a kind of logical incompatibility between the antecedent and the negation of the consequent. This ancient debate strikingly anticipates twentieth-century discussions about whether material implication adequately captures the conditional of natural language.

4. Medieval logic: consequences and disputes over terms

During the Latin Middle Ages, Aristotelian logic — known in part through Boethius’s translations and commentaries — was reworked by generations of scholastic masters. Peter Abelard, in the early twelfth century, devoted much of his Dialectica to the analysis of hypothetical syllogisms and of consequences (consequentiae) — the conditions under which one proposition can be said validly to “follow” from another — while also intervening decisively in the dispute over universals, which carries its own logical and semantic stakes: for Abelard, general terms (“man,” “animal”) name neither separate things (as a certain Platonism held) nor mere empty sounds (as Roscelin’s extreme nominalism held), but correspond to concepts the intellect forms out of the resemblance among particular things. (On Abelard’s logic and ethics, see the dedicated article Peter Abelard: Logic, Universals, Ethics, and Intention.)

In the centuries that followed, logicians such as Peter of Spain and, later, William of Ockham developed the theory of suppositio — a sophisticated analysis of how general terms “refer” to different things depending on the propositional context in which they occur (for instance, whether a common term like “man” is being used to refer to all men, to one specific man, or to the word “man” itself) — giving late medieval “terminist” logic a degree of semantic sophistication that would only be recovered, in different terms, by twentieth-century philosophy of language.

5. The Fregean revolution

After more than two thousand years of Aristotelian syllogistic’s dominance, Gottlob Frege carried out, in the slim treatise Begriffsschrift (“concept-script,” 1879), the deepest transformation logic had ever undergone. Instead of analyzing propositions according to the subject-predicate pattern inherited from Aristotle, Frege proposed analyzing them according to the mathematical model of function and argument: just as “the square root of x” is a function that, applied to the argument 9, yields the value 3, a sentence like “Socrates is wise” can be analyzed as the function “___ is wise” applied to the argument “Socrates.”

This reformulation allowed Frege to introduce quantification — the possibility of expressing statements such as “for all x” and “there exists at least one x” by means of variables bound to a function — in a far more powerful way than the old distinction between universal and particular propositions permitted. (Frege used his own two-dimensional notation for this; the symbols now in common use, ∀ and ∃, came later, introduced respectively by Giuseppe Peano and Gerhard Gentzen.) With quantifiers, variables, and the possibility of nesting functions within functions, the new predicate logic could express logical relations — such as “every number has a successor” or “for every x there is a y such that y is greater than x” — that syllogistic simply lacked the resources to capture. This instrument became the technical foundation of Frege’s entire logicist project: the attempt to show that arithmetic is reducible to pure logic, laid out in The Foundations of Arithmetic (1884) and in the Basic Laws of Arithmetic (1893–1903) — a project that would be shaken by the paradox Bertrand Russell communicated to him by letter in 1902, whose implications for the foundations of mathematics are discussed at greater length in this site’s article on the philosophy of mathematics. (To this project Frege also attached, in the field of philosophy of language, the celebrated distinction between sense and reference, set out in “On Sense and Reference,” 1892 — a topic that lies beyond the scope of this article.)

6. Russell, the paradox, and the theory of types

Frege’s logical system, despite its technical brilliance, contained a fatal flaw, discovered by Bertrand Russell: if it is legitimate to form the set of all sets that are not members of themselves, then that set is a member of itself if and only if it is not a member of itself — a bare contradiction, now known as Russell’s paradox. The discovery, communicated to Frege just as the second volume of the Basic Laws of Arithmetic was going to press, revealed that naive set theory (and the logic underlying it) was inconsistent.

Russell’s response was the theory of types: a stratified hierarchy in which individuals, sets of individuals, sets of sets, and so on occupy distinct levels, and a set can only have as members entities of a type strictly lower than its own — ruling out, by syntactic construction, the self-reference that generated the paradox. This architecture was put to work in the service of the same Fregean logicist project — reducing mathematics to logic — in the monumental work Russell wrote with Alfred North Whitehead, the Principia Mathematica (three volumes, 1910–1913), one of the most ambitious undertakings in the history of logic, in which hundreds of pages are devoted to formally proving propositions such as “1 + 1 = 2.”

7. Propositional and first-order predicate logic

Out of the work of Frege and Russell arose what is now taught as the core of contemporary formal logic: propositional logic and first-order predicate logic. Propositional logic takes whole propositions as its units and combines them by means of connectives — negation (¬), conjunction (∧), disjunction (∨), the conditional (→), and the biconditional (↔) — whose truth value can be computed mechanically from the truth values of their components by means of truth tables, a device popularized in the 1920s (associated chiefly with Wittgenstein and Emil Post) and taught today as the first tool in any introductory logic course.

First-order predicate logic adds to this apparatus the Fregean quantifiers and variables that can serve as arguments of predicates, allowing one to express not just relations among propositions but their very internal structure — who does what to whom, for all x or for some x. Within this framework, an argument is valid when there is no interpretation whatsoever (no “model,” in the technical sense) that makes the premises true and the conclusion false — the notion of logical consequence that Alfred Tarski would come to make semantically precise in the 1930s. This propositional-and-predicate system became, over the course of the twentieth century, a kind of lingua franca shared by analytic philosophy, mathematics, and, later, computer science.

8. Modal logic: necessity, possibility, and possible worlds

A limitation noticed early on in Frege and Russell’s logic is that it draws no distinction between merely factual truths and necessary ones — nothing in the Principia Mathematica naturally expresses that something could not fail to be the case, as opposed to simply being the case. Dissatisfied above all with the so-called “paradoxes of material implication” (which arise from defining the conditional purely in terms of truth values), the American logician C. I. Lewis proposed, beginning in the 1910s and systematized together with C. H. Langford in Symbolic Logic (1932), a family of modal logic systems with primitive operators for necessity (□) and possibility (◇), grounded in the notion of strict implication — stronger than material implication — giving rise to the systems now known as S1 through S5.

Modal logic would only find a rigorous and widely accepted semantics decades later, in the work Saul Kripke published while still a student, between the late 1950s and early 1960s. Possible-worlds semantics (or Kripke semantics) interprets “necessarily p” as “p is true in every possible world accessible from the actual world,” and “possibly p” as “p is true in at least one such world.” By varying the properties of the accessibility relation among worlds (reflexivity, symmetry, transitivity), this semantics makes it possible to distinguish precisely among the various modal systems Lewis had proposed and to explain why some are stronger than others. This technical tool would later prove indispensable outside modal logic strictly speaking as well — as in Kripke’s own analysis, in Naming and Necessity (1970/1980), of the necessity attaching to proper names and natural kinds.

9. Gödel and the limits of formalization

The dream of reducing all of mathematics — and with it, all rigorous deductive reasoning — to a complete, mechanically checkable formal system suffered its most severe blow in 1931, when Kurt Gödel published his two Incompleteness Theorems. The first proves that any consistent formal system powerful enough to express elementary arithmetic necessarily contains true propositions that can be neither proved nor refuted within that same system; the second, that no such system can prove its own consistency using only its own resources.

It is worth setting this result beside another, earlier one, of the opposite sign: Gödel himself had shown, in his doctoral dissertation (1929), that first-order predicate logic is complete — every logically valid formula is provable within the system. The contrast is revealing: pure first-order logic, taken by itself, is complete; but as soon as one adds to it even a minimal amount of arithmetic — the theory of natural numbers — completeness becomes impossible. The 1931 theorems struck directly at David Hilbert’s formalist program, which sought to justify all of mathematics by finitary, mechanically verifiable means, and they pointed to something of broader philosophical significance: no formal system, however rich, can capture at once the whole of arithmetical truth and a demonstration of its own consistency from within. There is, then, an intrinsic limit to formalization — not a contingent flaw, correctable by some more ingenious system, but a structural feature of any sufficiently expressive system.

10. Logic, epistemology, philosophy of language, and non-classical logics

Logic has never been a purely technical exercise, isolated from the rest of philosophy. Its relation to epistemology is close: asking under what conditions a belief is justified on the basis of another is, to a large extent, asking under what conditions an argument is valid or, in the inductive case, sufficiently well supported. Its relation to philosophy of language runs equally deep: from Frege’s function-argument analysis, through Russell’s theory of definite descriptions, to Kripke’s possible-worlds semantics, the great advances of twentieth-century logic were, almost without exception, simultaneous advances in understanding how language connects with the world and with thought.

Finally, it is worth noting that classical logic — bivalent, governed by the law of excluded middle — is not the only coherent option. Intuitionistic logic, formalized by Arend Heyting on the basis of the ideas of the mathematician L. E. J. Brouwer, rejects the law of excluded middle for propositions that admit no constructive proof, requiring every existence claim to come accompanied by an effective method for constructing the object claimed to exist. Paraconsistent logics, developed above all in the work of the Brazilian logician Newton da Costa and, later, by Graham Priest, in turn abandon the principle that a contradiction implies any proposition whatsoever (so-called ex falso quodlibet), allowing formal systems that can tolerate certain localized contradictions without the entire logical structure collapsing. These alternatives do not replace classical logic, but they show that the very notion of “valid inference” — the problem this article began with — remains, even today, a living territory of philosophical inquiry.

References

ARISTOTLE. Organon (Categories, On Interpretation, Prior Analytics, Posterior Analytics, Topics, Sophistical Refutations).

FREGE, Gottlob. Begriffsschrift. Halle: Louis Nebert, 1879.

FREGE, Gottlob. Die Grundlagen der Arithmetik [The Foundations of Arithmetic]. Breslau: Wilhelm Koebner, 1884.

WHITEHEAD, Alfred North; RUSSELL, Bertrand. Principia Mathematica. 3 vols. Cambridge: Cambridge University Press, 1910–1913.

LEWIS, Clarence Irving; LANGFORD, Cooper Harold. Symbolic Logic. New York: The Century Co., 1932.

GÖDEL, Kurt. “Über formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme I”. Monatshefte für Mathematik und Physik, 38, 1931.

KRIPKE, Saul. “A Completeness Theorem in Modal Logic”. Journal of Symbolic Logic, 24, 1959.

KRIPKE, Saul. Naming and Necessity. Cambridge, MA: Harvard University Press, 1980.

KNEALE, William; KNEALE, Martha. The Development of Logic. Oxford: Clarendon Press, 1962.

BOCHEŃSKI, I. M. A History of Formal Logic. Notre Dame: University of Notre Dame Press, 1961.

LONG, A. A.; SEDLEY, D. N. The Hellenistic Philosophers. Cambridge: Cambridge University Press, 1987.

← Articles