«1. Peirce’s Method for Teaching Logic Peirce’s existential graphs (EGs) are the simplest, most elegant, and easiest-to-learn system of logic ever ...»
• To simplify the coreference nodes in an area a is to perform the following operations as often as they
1. If a coreference node in a contains two or more bound labels with the same identifier, erase all but one of them.
2. If two coreference nodes in a each contain a bound label with the same identifier, they are merged: erase one of the coreference nodes, move all its bound labels to the other, and remove any duplicates according to operation 1.
3. If a defining node d in a has a bound label in a coreference node c in a and c also contains a bound label b that is not bound to d, then the defining node d is erased, the label in c that was bound to d is erased, and every other label that was bound to d is replaced with a copy of b.
For an example of simplification, see the discussion of the EGs for an African man in the paragraph just before Figure 5. For an example of a join followed by a simplification, see Peirce’s conversion of Figure 12 to Figure 13 and its translation to EGIF in step 3 of the proof following Figure 16. Any coreference node that contains a single bound label may be erased by the rule of deiteration, because it is a copy of a defining node.
That erasure, which is performed by a rule of inference, is not considered one of the simplification rules.
The basic constraint on erasing or inserting nodes is that no operation may leave or insert a bound label outside the scope of its defining label. Following are further conditions for Peirce’s first and second
permissions; no more conditions are needed for the third permission:
1. (i) In a negative area, no node that contains a bound label may be inserted in an area that is not in the scope of its defining label. No defining node may be inserted in an area that is in the scope of another defining label that has the same identifier.
(e) In a positive area, no defining node that has one or more bound labels may be erased, unless all the nodes that contain those bound labels are erased in the same operation.
2. (i) If a defining node is iterated, the copy must be converted to a coreference node that contains a single bound label with the same identifier. A defining node that is enclosed in a negation, however, may remain unchanged when the negation is copied; but to avoid possible conflicts with future operations, the identifier of that defining label and all its bound labels should be replaced with an identifier that is not otherwise used.
(e) Any nodes that could have been derived by rule 2i may be erased. (Whether or not a node had previously been derived by 2i is irrelevant.) Peirce’s meticulous attention to the smallest steps of reasoning enabled him to prove the soundness of every rule. Fr ege (1879) assumed nine unprovable and nonobvious axioms. Whitehead and Russell (1910) assumed five axiom schemata, of which one was redundant, but nobody discovered the redundancy until
1926. For EGs, only one axiom is necessary: a blank sheet of assertion, from which all the axioms and rules of inference by Frege, Whitehead, and Russell can be proved by Peirce’s rules. As an example, Frege’s first axiom, a⊃(b⊃a), can be proved in five steps by Peirce’s rules.
In EGIF, the propositions a and b are represented as relations with zero arguments: (a) and (b). Following are
the five steps of the proof:
1. By rule 3i, Insert a double negation around the blank: ~[ ~[ ]]
2. By 3i, insert a double negation around the previous one: ~[ ~[ ~[ ~[ ]]]]
3. By 1i, insert (a): ~[ (a) ~[ ~[ ~[ ]]]]
4. By 2i, iterate (a): ~[ (a) ~[ ~[ ~[ (a) ]]]]
5. By 1i, insert (b): ~[ (a) ~[ ~[ (b) ~[ (a) ]]]] The theorem to be proved contains five symbols, and each step of the proof inserts one symbol into its proper place in the final result.
Frege’s two rules of inference were modus ponens and universal instantiation. Following is a proof of modus
ponens, which derives q from a statement p and an implication p⊃q:
Proof in EGIF:
0. Starting graphs: (p) ~[ (p) ~[ (q) ]]
1. By 2e, erase the nested copy of (p): (p) ~[ ~[ (q) ]]
2. By 1e, erase (p): ~[ ~[ (q) ]]
3. By 3e, erase the double negation: (q) The rule of universal instantiation allows any term t to be substituted for a universally quantified variable in a statement of the form (∀x)P(x) to derive P(t). In EGs, the term t would be represented by a graph of the form —t, in which t represents some monadic relation defined by a graph attached to the line of identity. The universal quantifier ∀ corresponds to ~∃~, which is represented by a line whose outermost part occurs in a negative area. Since a graph has no variables, there is no notion of substitution. Instead, the following proof performs the equivalent operation by connecting the two lines.
The proof in EGIF is more complex because of the need to relabel identifiers:
0. Starting graphs: [*y] (t ?y) ~[ [*x] ~[ (P ?x) ]]
1. By 2i, iterate [*y] and change the defining label *y to a bound label ?y in the copy:
[*y] (t ?y) ~[ [?y] [*x] ~[ (P ?x) ]]
2. By 1i, insert the coreference [?x ?y]:
[*y] (t ?y) ~[ [?y] [*x] [?x ?y] ~[ (P ?x) ]]
3. Relabel *x and ?x to ?y, simplify [?y ?y] to [?y], and deiterate copies of [?y]:
[*y] (t ?y) ~[ ~[ (P ?y) ]]
4. By 3e, erase the double negation: [*y] (t ?y) (P ?y) In the Principia Mathematica, Whitehead and Russell proved the following theorem, which Leibniz called the Praeclarum Theorema (Splendid Theorem). It is one of the last and most complex theorems in
propositional logic in the Principia, and the proof required a total of 43 steps:
((p⊃r) ∧ (q⊃s)) ⊃ ((p∧q) ⊃ (r∧s)) With Peirce’s rules, this theorem can be proved in just seven steps starting with a blank sheet of paper. Each step inserts or erases one graph, and the final graph is the statement of the theorem.
After only four steps, the graph looks almost like the desired conclusion, except for a missing copy of s in the innermost area. Since that area is positive, the only way to get s in there is by iterating some graph that
contains s and erasing the parts that are not needed. Following is the EGIF version of the proof:
1. By 3i, draw a double negation around the blank: ~[ ~[ ] ]
2. By 1i, insert the hypothesis in the negative area:
~[ ~[(p) ~[(r)]] ~[(q) ~[(s)]] ~[ ] ]
3. By 2i, iterate the left part of the hypothesis into the conclusion:
~[ ~[(p) ~[(r)]] ~[(q) ~[(s)]] ~[ ~[(p) ~[(r)]] ] ]
4. By 1i, insert (q):
~[ ~[(p) ~[(r)]] ~[(q) ~[(s)]] ~[ ~[(p) (q) ~[(r)]] ] ]
5. By 2i, iterate the right part of the hypothesis into the innermost area:
~[ ~[(p) ~[(r)]] ~[(q) ~[(s)]] ~[ ~[(p) (q) ~[(r)] ~[(q) ~[(s)]] ] ] ]
6. By 2e, deiterate (q):
~[ ~[(p) ~[(r)]] ~[(q) ~[(s)]] ~[ ~[(p) (q) ~[(r)] ~[ ~[(s)]] ] ] ]
7. By 3e, erase the double negation to generate the conclusion:
~[ ~[(p) ~[(r)]] ~[(q) ~[(s)]] ~[ ~[(p) (q) ~[(r)] (s)] ] ] This proof illustrates the usual pattern for deriving a theorem by Peirce’s rules. The first step draws a double negation around the blank. The second step inserts the hypothesis into the negative area. The remaining steps copy parts of the hypothesis into the conclusion, or they perform other operations on the parts that have been copied. When people prove theorems, they look ahead to the desired conclusion and try to make the current graph look as similar to the conclusion as possible. With a method for measuring graph similarity, that heuristic can also be implemented in computer systems.
4. Peirce’s Model Theory In his first publication on model theory, Tarski (1933) quoted Aristotle as a precedent. The medieval Scholastics developed Aristotle’s insights further, and Ockham (1323) presented a model-theoretic analysis of Latin semantics. Although Ockham wasn’t as formal as Tarski, he covered the Latin equivalents of the Boolean connectives, the existential quantifier (aliquis), the universal quantifier (omnis), and even modal, temporal, and causal terms. Peirce owned a copy of Ockham’s book and lectured on it at Harvard. He used model-theoretic arguments to justify the rules of inference for all his versions of logic, including truth tables for Boolean logic. But his most explicit development of model theory was the method of endoporeutic, which is an “outside-in” method for determining the truth value of an existential graph. In the following
excerpt from MS 514, Peirce mentions endoporeutic:
The rule of interpretation which necessarily follows from the diagrammatization is that the interpretation is “endoporeutic” (or proceeds inwardly) that is to say a ligature denotes “something” or “anything not” according as its outermost part lies on an unshaded or a shaded area respectively.
Peirce had defined logic as “the formal science of the conditions of the truth of representations” (CP 2.220).
To see the similarity to Tarski’s approach, compare the following quotations:
• Peirce (1869): “All that the formal logician has to say is, that if facts capable of expression in such and such forms of words are true, another fact whose expression is related in a certain way to the expression of these others is also true.... The proposition ‘If A, then B’ may conveniently be regarded as equivalent to ‘Every case of the truth of A is a case of the truth of B.’”
• Tarski (1936): “In terms of these concepts [of model], we can define the concept of logical consequence as follows: The sentence X follows logically from the sentences of the class K if and only if every model of the class K is also a model of the class X.” Although Peirce’s method is logically equivalent to Tarski’s, the proof of equivalence was not discovered until Hilpinen (1982) showed that Peirce’s endoporeutic is a variation of game-theoretical semantics (Hintikka 1973). For their introduction to model theory, Barwise and Etchemendy (1993) chose the title Tarski’s World, but what they presented was a version of the game-theoretical method.
In modern terminology, endoporeutic can be defined as a two-person zero-sum perfect-information game, of the same genre as board games like chess, checkers, and tic-tac-toe. Unlike those games, which frequently end in a draw, every finite EG determines a game that must end in a win for one of the players in a finite number of moves. In fact, Henkin (1961), the first modern logician to rediscover the game-theoretical method, showed that it could evaluate the denotation of some infinitely long formulas in a finite number of steps. Peirce also considered the possibility of infinite EGs: “A graph with an endless nest of seps [ovals] is essentially of doubtful meaning, except in special cases” (CP 4.494). Although Peirce left no record of those special cases, they are undoubtedly the ones for which endoporeutic terminates in a finite number of steps.
The version of endoporeutic presented here is based on Peirce’s writings, supplemented with ideas adapted from Hintikka (1973), Hilpinen (1982), and Pietarinen (2006).
In the game of endoporeutic, one player, whom Peirce called Graphist, proposes a graph g that is claimed to be true, and another player, called Grapheus, is a skeptic or devil’s advocate who tries to show that g is false.
The game begins with some state of affairs, which could be represented by a Tarski-style model M=(D,R), in which D is a set of individuals and R is a collection of relations defined over D. The model M, like any Tarski-style model, can be represented as a relational graph (an EG with no negations): each individual in D is represented by a line of identity; each n-tuple of each relation r in R is represented by a copy of the string that names r with n pegs attached to n lines of identity. The game proceeds according to the following recursive procedure with Graphist as the initial proposer and Grapheus as the initial skeptic. During the game, they switch sides as they peel off each negation.
1. If g contains no negations, then the game is over, and the winner is determined by one of the
following three conditions:
• If g is an empty graph, it is true because it says nothing false. The current proposer wins.
• Else if there is a mapping (graph homomorphism) of g to M, the current proposer wins. The mapping need not be an isomorphism, since multiple lines of identity in g may map to the same line in M. Each relation node in g must map to a relation node in M with the same name.
• Else the current skeptic wins.
2. Else if g consists of just a single negation, the graph inside the oval becomes the new g, and the shading of each area in g is reversed. Then the two players switch sides: the proposer becomes the new skeptic, the skeptic becomes the new proposer, and the game continues with the new g and the new roles for both players.
3. Else if g consists of two or more negations, the skeptic chooses any one of the negations as the new g, and the game continues.
4. Else g consists of two or more parts: a subgraph g0, which is a relational graph with no negations, and one or more negations: g1,...,gn. The graph g0 may contain some lines of identity that are joined to
lines inside one or more of the negations. There are now two possibilities:
• If there is no mapping of g0 to M, the game is over, and the skeptic wins.
• Else one or more mappings are possible, and the proposer may choose any one. That choice maps every line of identity x in g0 to some line y in M. If x is joined to any line z in any negation gi, then z must remain mapped to y for the duration of the game. Then the subgraph g0 is erased, leaving g as a conjunction of one or more negations, and the game continues.
Since each pass through this procedure reduces the size of g, any game that starts with a finite graph must terminate in a finite number of moves. Since none of the ending conditions results in a draw, either Graphist, the original proposer, or Grapheus, the original skeptic, must have a winning strategy for any g and model M.
If Graphist has a winning strategy, g is true of M. If Grapheus has a winning strategy, g is false of M.