The Analytic Atavar

Idiosyncratic Musings of a Retrograde Technophile

My Photo
Location: Chandler, Arizona, United States

Saturday, April 28, 2007

Liar, Liar, Logic Afire

Possibly the oldest logical paradox is what is today known as the Liar Paradox. The first appearance of the paradox is attributed by some to Epimenides of Knossos, a Cretan philosopher and poet, circa the 6th century B.C.E.. All of his works are lost and known only from quotations by other authors. The paradox is said to arise from a fragment of his poem Cretica, where Minos addresses Zeus thusly:

"They fashioned a tomb for thee, O holy and high one—
The Cretans, always liars, evil beasts, idle bellies!
But thou art not dead: thou livest and abidest forever,
For in thee we live and move and have our being."
From the bolded phrase, the question is whether the statement 'Cretans are always liars', when said by a Cretan, is true or false? If assumed true, then he, as a Cretan, is lying, and so his statement is false (because a lie), producing a contradiction. If assumed false, then he or some other Cretan has told the truth at some time, perhaps with this very statement, and there is no contradiction – hence, no paradox. It seems that neither Epimenides nor subsequent commentators regarded this fragment as paradoxical. In the context of the poem it is clear that Epimenides is referring to Cretans other than himself, so there is no self-reference and hence no logical problem. The bolded phrase was quoted by the poet Callimachus (ca. 305 - 240 B.C.E.) in his Hymn to Zeus, and there are references to this fragment in the New Testament. [Paul in Titus 1:12-13 : "12 One of themselves, even a prophet of their own, said, 'The Cretans are always liars, evil beasts, slow bellies.' 13 This witness is true." KJV. Paul does not appear to consider it paradoxical but instead believes it to be true.] None of the subsequent classical or medieval discussions of the Liar make reference to Epimenides, Callimachus, or Titus. An oblique reference to Epimenides appears in "The Logical Calculus", W. E. Johnson, Mind (New Series), vol. 1, no. 2 (April, 1892), pages 235-250, and the 'Epimenides Paradox' is explicitly so named in "Mathematical Logic as Based on the Theory of Types", Bertrand Russell, American Journal of Mathematics, vol. 30, no. 3 (July, 1908), pages 222-262. The association of Epimenides and the paradox seems of fairly recent origin.

The discovery of the Lair Paradox is generally attributed to Eubulides of Miletus, a Greek philosopher circa the 4th Century B.C.E. and student of Euclid of Megara, founder of the Megarian school of philosophy, based on a remark by Diogenes Laertius (c. 200 C.E.) in Lives of the Philosophers II.108. Eubulides reportedly asked: "A man says that he is lying. Is what he says true or false?". If assumed true, then the man is lying and therefore his statement is false (because a lie). If assumed false, then the man is not lying and his statement is therefore true. In either case a contradiction results, so this is truly a paradoxical statement, and accounts for the name. However Diogenes merely stated that Eubulides discussed the Liar, not that he discovered it. Aristotle does not mention it. Whenever and wherever its origin, the Liar Paradox was widely known in later antiquity. The Stoic logician Chrysippus (c. 279-206 B.C.E.), whose works are lost, wrote no less than 14 books on the Liar. Seneca (ca. 4 B.C.E. – 65 C.E.) in Epistle 45.10 mentioned the Liar Paradox. St. Augustine (354 - 430 C.E.) probably had the Liar in mind in Against the Academicians (III.13.29) when he referred to "… the most lying calumny, 'if it is true [it is] false, if it is false it is true'." Aulus Gellius's (c. 125 - after 180 C.E.) Attic Nights (XVIII.ii.10) and Cicero's (c.106 B.C.E. – 43 B.C.E.) Academica priora, II.xxix.95-xxx.97 both discuss it.

This paradox was widely discussed by medieval philosophers, who considered it but one of a number of the insolubilia (insolubles). The two most prominent schools of thought on the Liar were that it was a variant of an Aristotelian fallacy secundum quid et simpliciter [i.e., true in some limited respect but false on the whole], or that this paradox made necessary certain rules to restrict the possibility of self-reference, though there was no agreement on the set of rules [the restrictors]. In the Renaissance the paradox began to take its modern form, reformulated by eliminating any reference to 'lying', viz., the statement: "This statement is false." or explicitly labeling the statement:

X :    "The statement 'X' is false."(1)

It is not sufficient to restrict such self-reference to eliminate the Liar paradox, for it can also be reproduced by a series of non-self-referential statements such as:
X :    "The statement 'Y' is true."(2a)
Y :    "The statement 'X' is false."(2b)

These are perfectly reasonable statements, discussing the truth or falsity of other statements, of a type which we must make continuously in logic, but certain combinations or loops result in the equivalent of the Liar.

The modern resolution of the Liar came in the first part of the 20th Century, a form of restriction due to Tarski. Tarski "proved" that there cannot be a general 'truth' predicate in the logic itself, hence the concept of truth must lie outside the logic -- truth is a meta-concept, so that statements involving the truth of other statements are then meta-statements, on a higher level than the statement itself and discussable only in a meta-language. Separating logical propositions and statements involving their truth (or falsity) unto different levels prohibits any formulation of the Liar, avoiding the paradox. Unfortunately, this separation also results in a vicious infinite regress in truth value; for suppose there is some statement, P, assumed to be at level 0 and it is asserted that:

P1 :    "The statement 'P' is true."(3a)

(where P1 labels the meta-statement on the next level, i.e. level 1), specifying a relation between P and 'truth' in the meta-language. But to determine if P is true, we must determine if meta-statement P1 is true, that is, we must evaluate the meta-meta-statement (level 2 meta-statement):
P2 :    "The statement 'P1' is true."(3b)

To determine its truth, we must evaluate the meta-meta-meta-statement (level 3 meta-statement):
P3 :    "The statement 'P2' is true."(3c)

and so on, ad infinitum, ad nauseum, ad absurdum. Either truth is completely abandoned because it becomes infinitely remote, or we arbitrarily stop at some level, typically the very first. To avoid this infinite regress Tarski introduced his material criterion for the coordination of truth values, viz.:
" 'P' is true." if and only if P.    i.e.,    " 'P' is true." ≡ P(4a)
" 'P' is false." ≡ " '¬P' is true." ≡ ¬P(4b)

Note that both (4a) and (4b) violate the rule for separation of levels since the left side of the equivalence is a level 1 meta-statement whilst the right side is a normal, level 0 proposition. The material criterion dictates that all the meta-statements (3a et. al.), on different levels, have precisely the same logical value, collapsing the regress by violating the very rule of level separation which makes it necessary to begin with. Tarski's meta-level solution to the Liar Paradox has a distinctly ad hoc flavor: mixing levels is prohibited except when it is necessary as an application of the material criterion. This license might perhaps be acceptable if it truly resolved the Liar Paradox in all its forms, but it does not. Unfortunately Tarski's meta-separation fails in the case of multiple statements like (2a) and (2b) because a confusion of levels results. Statement X, asserting the truth of Y, must be on a higher level than Y, while Y, asserting the falsity of X, must be on a higher level than X, so there is no way to consistently assign levels to the two statements. The level of each statement is undeterminable, and the concept of meta-levels is unsatisfactory for this formulation of the Liar.

In an analysis in the complex logic, begin by restricting the values of distinction symbols to the formal constants {U, U~, U~V, V}, interpreted as true, false, undecidable, and imaginary respectively. This restriction of values reduces the complex algebra to a complex propositional logic. The statement " 'X' is true." can be represented by the expression [X = U] and " 'X' is false." by [X = U~], so the Liar paradox can be represented by the implicit definition X = [X = U~]. By a consequence (C10.5), [X = U~] = X~ (compare this result with (4b)), resulting in the reduced equation X = X~, having the solution set X = {U~V, V} as can be verified by substitution. It is also straightforward to demonstrate there are no other possible solutions. There is no contradiction, hence no paradox

So far, this appears to follow Bochvar's approach, with his 'paradoxical' logical value denotated by either U~V or V, to which Haack [1] raises the 'Strengthened Liar' paradox:

P :    'P' is false or paradoxical.(5a)

If the statement is true, then it is false or paradoxical, while if it is false or paradoxical, then it is true – a contradiction in either case, seeming to revive the paradox. This may be variously interpreted as one of the following statements:
P = [P = U~V](5b)
P = [P = U~][P = U~V](5c)
P = [P = U~][P = V](5d)

The first two (5b & 5c) both have the solution P = V, while (5d) has the solution P = U~V; thus the 'Strengthened Liar' paradox does not present any problem under any of the possible interpretations of statement (5a). Extending the spirit of Haack's criticism (as we must, to be thorough), consider the statement:
P :    'P' is imaginary.    or    P = [P = V](6a)

It could at this point be argued that (6a) is prima facia self-contradictory, since it is manifestly non-imaginary, being represented by real symbol tokens. Continuing the analysis however, by Theorem 4.1 any solution must have the form P = V or P = R1(R2V)~. Substituting:
[V = [V = V]] = [V = U] = V(6b)
[R1(R2V)~ = [R1(R2V)~ = V]] = [R1(R2V)~ = V] = V(6c)

There is no solution to (6a), seeming to revive Haack's criticism. However, this statement is not paradoxical, it simply has no solution which would make it true. A more thorough analysis is necessary to explain why this statement alone has no solution.

Begin by distinguishing between the logical value of a statement, P, and the logical value of its implicit definition, [P = [P = …]] – they are not necessarily the same. The self-reference introduces an additional relation between the statement and its asserted value. For (1), the value of the statement is P = {U~V, V}, while the value of its definition is [P = [P = U~]] = U for either solution. Similarly, for (5b-5d), the value of the statement is P = U~V or P = V, while the value of each of the definitions is U. We assume a definition true, solve for the value of the statement, and the existence of a solution justifies our initial assumption, rendering the definition true for those values. Consider the analogous but seldom mentioned case involving the other primitive formal constant, U:

P :    'P' is true.    or    P = [P = U](7)

This definition is true for any value of P, so the value of the statement is unrestricted and undetermined. Statement (7) is true as a definition, though the value of P is undetermined because any value is possible; statement (6a) is imaginary as a definition (see 6b & 6c above), and the value of P is undeterminable because no value is possible. We may regard both statements as definitions having the claimed value, i.e.:
[[P = [P = U]] = U] = U(8a)
[[P = [P = V]] = V] = U(8b)

but elsewise of no effect since they do not determine a value for the statement P. The two primitive formal constants have special status in the formal system, and this status is reflected in the symmetry of these self-referential statements and the fact that they both can be interpreted in the same manner.

The simple paradoxes can thus be regarded quite differently in the complex logic: because of the larger set of formal constants available, they are no longer paradoxical but instead have solutions which may be consistently interpreted as 'undecidable' or 'imaginary'. Because representation is possible directly in the logic, there is no need for meta-levels to avoid paradox. Because all definitions have solutions (except (6a)), there is no need to restrict self-reference, and the formalism is equally effective in dealing with multiple statements lacking self-reference. The fact that multiple solutions are possible in some cases simply means that these implicit definitions are incomplete, i.e., insufficient to completely determine a value. This viewpoint also clarifies some of the medieval conceptions and misconceptions. The secundum quid et simpliciter criticism is seen to have some basis, but in exactly the reverse sense from its medieval application: the statements are true (or imaginary in the sole case of (6a)), absolutely, as definitions, but not in certain respects, i.e., the value of the statements themselves. The notion that a statement can somehow be both true and false perhaps reflected a misunderstood and ill-expressed distinction between the value of an implicit definition and the value of the statement implicitly defined. A general criterion is provided for the restrictors, i.e., a non-real solution, but the need for any restriction is simultaneously removed. The Theory of Cassation is likewise given a formal criterion, that a statement is meaningless if its solution is 'imaginary' (because it then has no possible real import), but there is no need to classify all statements as meaningless to avoid paradox.

[1]    Haack, Susan, Philosophy of Logics, p. 140.

Labels: , ,

Thursday, April 26, 2007

Logical Complexity

For reasons unclear even to me, I have always been deeply fascinated by logic. I studied logic and set theory on my own in High School, and was exposed to Boolean algebra and logic design in college. I poured over Elements of Symbolic Logic by Hans Reichenbach and Introduction to Symbolic Logic and its Applications by Rudolf Carnap. I discovered Language, Truth and Logic by Alfred Jules Ayer, Philosophy of Logic by W.V. Quine, and Philosophy of Logics by Susan Haack. [I highly recommend each of these books.] My logic library today includes many other books, some good and others not so good, some in the old Aristotelian tradition, others in the modern symbolic mode, and still others in the Boolean mode peculiar to engineers..

Two books, however, generated a deep disquietude in me and their topics continue to do so to this day. The first, Gödel's Proof by Nagel and Newman, I discovered while in High School. I was amazed that such a result could be proved and shaken by its implications for mathematics, as is nearly everyone when they first encounter it. [Though perhaps the best known, most popular exposition of Gödel's Theorems, I do not recommend this book. It simplifies the topic so much that its derivations are defective and misleading, but perhaps later editions have improved - I refer here to the 1960 edition. I instead recommend reading Gödel in the original, On Formally Undecidable Propositions of Principia Mathematica and Related Systems, though it is much more difficult to follow.] Gödel's Theorems are the most famous and disquieting results of 20th Century logic, and like the uncertainty principle and relativity in physics, they are often cited as justification for some position in fields far outside their applicability.

The second book was the contentious Laws of Form (LoF) by G. Spencer Brown, another book I do not recommend. Opinions concerning Brown are decidably mixed and tend to the two extremes - either he is a visionary or a charlatan (see some of the reader comments in the reviews at the link). The book is short and obscure, with an eclectic notation not conducive to a thorough and clear exposition of logic. Brown's style is difficult and egotistical, but there was an idea behind it which I found fascinating, viz., the introduction of imaginary values to logic. Brown argued:

"The fact that imaginary values can be used to reason towards a real and certain answer, coupled with the fact that they are not so used in mathematical reasoning today, and also coupled with the fact that certain equations plainly can not be solved without the use of imaginary values, means that there must be mathematical statements (whose truth or untruth is in fact perfectly decidable) which can not be decided by the methods of reasoning to which we have hitherto restricted ourselves."
which is a viewpoint having great resonance with mathematicians and engineers who routinely employ the powerful methods of complex analysis to arrive at useful results. Unfortunately, Brown's development was defective. Though attempting to formulate an imaginary logic, Brown limited the possible logical values to only two formal constants, making it effectively a propositional logic; what is worse, one of these constants is not indicated by any symbol, but simply by a blank space; worse still, by identifying imaginary logical values with variations in time (an understandable error for an engineer familiar with logic circuits), Brown confused a possible interpretation with the formalism.

My first reading of LoF left me completely bewildered - it was unlike any logic I had ever read. There seemed to be something of value, if only I could grasp it. I was frustrated for years by my inability to understand, but kept returning. I only began making progress when I abandoned Brown's peculiar notation and translated his text into a more conventional notation. This enabled me to see the errors in his development, and to attempt to correct them, resulting in a complex logic which I detail in my manuscript Systema Logica [a .pdf summary of the Systema is available at the Yahoo Laws of Form Group files area, here]. Brown's simple exposition was the starting point – I only found it necessary to standardize the notation, reorganize and formalize it, and add the appropriate definition of the formal imaginary logical constant, V. Part of Brown's insight was that imaginary values are most easily introduced in a formalism with two primitive operations, only one of which, complementation, is needed to completely define the fundamental property of the imaginary constant. The resulting formal system is a multi-value, extensional, boolean equivalence algebra and an associated arithmetic, requiring two primitive logical operations, complementation, indicated by a postfix tilde "~", and concatenation of distinction symbols, representing disjunction, and two primitive relations, logical equality (not material equivalence) and derivability (instead of implication). Those familiar with Laws of Form may be disappointed, for this complex logic bears scant resemblance to Brown's extravagant and eccentric work – it is instead a retreat from his mystical visions and psychological speculations to more conventional and concrete realms. Lest I seem unduly critical of Brown, I wish to here acknowledge my debt and thanks for clarifying many concepts, including the clear distinction between axioms, postulates and initials, substitution and replacement, theorems and consequences, proof and demonstration, but most of all for pointing out a direction and providing a map which, however flawed, could be followed.

I already used some of these results in my solution of Dodgson's eight hitherto unsolved sorites [see here]. In articles that follow, I will use these methods to resolve the Liar Paradox, provide a different interpretation of Gödel's Theorems, and discuss their implications in the re-entrant forms Brown introduced in LoF.

What is most curious to me is that the two books most influential on my views are two which I do not encourage anyone else to read.

Labels: ,

Sunday, April 22, 2007

Quote of the Day

"I have found you an argument; I am not obliged to find you an understanding." -- Samuel Johnson