October 22, 2010 14:2  World Scientific Book - 9in x 6in  prelim

Publishers’ page

October 22, 2010 14:2  World Scientific Book - 9in x 6in  prelim

Publishers’ page

October 22, 2010 14:2  World Scientific Book - 9in x 6in  prelim

Publishers’ page

October 22, 2010 14:2  World Scientific Book - 9in x 6in  prelim

Publishers’ page

October 22, 2010 14:2  World Scientific Book - 9in x 6in  prelim

Contents

The History of Logic 1

A Logic – patterns of reasoning . . . . . . . . . . . . . . . . . . 2 A.1 Reductio ad absurdum . . . . . . . . . . . . . . . . . 2 A.2 Aristotle . . . . . . . . . . . . . . . . . . . . . . . . . 3 A.3 Other patterns and later developments . . . . . . . . 8

B Logic – a language about something . . . . . . . . . . . . . . 9 B.1 Early semantic observations and problems . . . . . . . 10 B.2 The Scholastic theory of supposition . . . . . . . . . . 11 B.3 Intension vs. extension . . . . . . . . . . . . . . . . . 11 B.4 Modalities . . . . . . . . . . . . . . . . . . . . . . . . 12

C Logic – a symbolic language . . . . . . . . . . . . . . . . . . . 14 C.1 The “universally characteristic language” . . . . . . . 15 C.2 Calculus of reason . . . . . . . . . . . . . . . . . . . . 15

D 19th and 20th Century – mathematization of logic . . . . . . 17 D.1 George Boole . . . . . . . . . . . . . . . . . . . . . . . 18 D.2 Gottlob Frege . . . . . . . . . . . . . . . . . . . . . . 22 D.3 Set theory . . . . . . . . . . . . . . . . . . . . . . . . 25 D.4 20th century logic . . . . . . . . . . . . . . . . . . . . 27

E Modern Symbolic Logic . . . . . . . . . . . . . . . . . . . . . . 30 E.1 Formal logical systems: syntax. . . . . . . . . . . . . . 31 E.2 Formal semantics . . . . . . . . . . . . . . . . . . . . 34 E.3 Computability and Decidability . . . . . . . . . . . . 38

F Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42 The Greek alphabet . . . . . . . . . . . . . . . . . . . . . . . . . 43

vi Introduction to Logic

Acknowledgments

Several lecturers have been using preliminary versions of this text and contributed valuable comments and corrections to its present, final form. I want to specifically thank Tore Langholm, Valentinas Kriaučiukas and Uwe Wolter.

The first part, on the history of logic, is to a high degree a compilation of various internet resources. I gratefully acknowledge the use of much detailed information from Encyclopedia Britannica (www.britannica.com),

Wikipedia (en.wikipedia.org), Leibnitiana (www.gwleibniz.com), Stan-

ford Encyclopedia (plato.stanford.edu), and apologize the owners of other sources which I might have inadverently left out. The arrangement, development and conclusions of this part, however, reflect only the author’s views and should not be attributed to other sources.

The history of logic 1

The History of Logic

Once upon a time, sitting on a rock in Egypt, Parmenides invented logic. Such a legend might have appealed to people believing in a (rather small) set of well-defined rules constituting the logic. This belief had permeated the main-stream thinking at least until the beginning of the 20th century. But even if this medieval story appears now implausible, it reflects the fact that Parmenides was the first philosopher who did not merely propose a vision of reality but who also supported it by an extended argument. He is reported to have had a Pythagorean teacher and, perhaps, his use of argument was inspired by the importance attached to mathematics in the Pythagorean tradition. Still, he never systematically formulated principles of argumentation and using arguments is not the same as studying them.

“Logical thinking” may be associated roughly with something like correct reasoning and the study of logic begins with the attempts to formulate the principles govering such reasoning. Now, correctness amounts to conformance to some prescribed rules. Identification of such rules, and the ways of verifying conformance to them, begins with Aristotle in the 5th century bc. He defined his logical discourse – a syllogism – as one “in which, certain things being stated something other than what is stated follows of necessity from their being so.” This intuition of necessary – unavoidable or mechanical – consequences, embodying the ideal of correctness, both lies at the origin of the discipline of logic and has since been the main force driving its development until the 20th century. However, in a quite interesting turn, its concluding chapter (or rather: the chapter at which we will conclude its description) did not establish any consensus about the mechanisms of the human thinking and the necessities founding its correctness. Instead, it provided a precise counterpart of the Aristotelian definition of a process in which, certain things being given, some other follow as their unavoidable, mechanical consequences. This is known as Turing machine and its physical realization is computer.

We will sketch logic’s development along the three, intimately connected axes which reflect its three main domains.

(1) The foremost seems to be the study of correct arguments, their meaning. Meaning, however, seems often very vague. One tries to capture it more precisely in order to formulate the rules for construction of correct arguments and for their manipulation which, given some correct arguments, allows one to arrive at new ones.

2 Introduction to Logic

(2) In order to construct precise and valid forms of arguments one has to determine their “building blocks”. One has to identify the basic terms, their kinds and means of combination.

(3) Finally, there is the question of how to represent these patterns. Although apparently of secondary importance, it is the answer to this question which puts purely symbolic manipulation in the focus. It can be considered the beginning of modern mathematical logic which led to the development of the devices for symbolic manipulation known as computers.

The first three sections sketch the development along the respective lines until Renaissance beginning, however, with the second point, Section A, following with the first, Section B, and concluding with the third, Section C. Then, Section D indicates the development in the modern era, with particular emphasis on the last two centuries. Section E sketches the basic aspects of modern mathematical logic and its relations to computers.

A. Logic – patterns of reasoning

A.1. Reductio ad absurdum

If Parmenides was only implicitly aware of the general rules underlying his arguments, the same perhaps is not true for his disciple Zeno of Elea (5th century bc). Parmenides taught that there is no real change in the world and that all things remain, eventually, the same one being. In the defense of this heavily criticized thesis, Zeno designed a series of ingenious arguments, known under the name “Zeno’s paradoxes”, which demonstrated that the contrary assumption must lead to absurdity. Some of the most known is the story of

Achilles and tortoise competing in a race

Tortoise, being a slower runner, starts some time t before Achilles. In this time t, the tortoise will go some way w_{1} towards the goal. Now Achilles starts running but in order to catch up with the tortoise he has to first run the way w_{1} which will take him some time t_{1} (less than t). In this time, tortoise will again walk some distance w_{2} away from the point w_{1} and closer to the goal. Then again, Achilles must first run the way w_{2} in order to catch the tortoise which, in the same time t_{2}, will walk some distance w_{3} away.

The history of logic 3

In short, Achilles will never catch the tortoise, which is obviously absurd. Roughly, this means that the thesis that the two are really changing their positions cannot be true.

It was only in the 19th century that mathematicians captured and expressed precisely what was wrong with this way of thinking. This, however, does not concern us as much as the fact that the same form of reasoning was applied by Zeno in many other stories: assuming a thesis T, he analyzed it arriving at a conclusion C; but C turns out to be absurd – therefore T cannot be true. This pattern has been given the name “reductio ad absurdum” and is still frequently used in both informal and formal arguments.

A.2. Aristotle

Various ways of arguing in political and philosophical debates were advanced by various thinkers. Sophists, often discredited by the “serious” philosophers, certainly deserve the credit for promoting the idea of a correct argument, irrespectively of its subject matter and goal. Horrified by the immorality of sophists’ arguing, Plato attempted to combat them by plunging into ethical and metaphysical discussions and claiming that these indeed had a strong methodological logic – the logic of discourse, “dialectic”. In terms of development of modern logic there is, however, close to nothing one can learn from that. The formulation of the principles for correct reasoning culminated in ancient Greece with Plato’s pupil Aristotle’s (384-322 bc) teaching of categorical forms and syllogisms.

A.2.1. Categorical forms

Most of Aristotle’s logic was concerned with specific kinds of judgments, later called “categorical propositions”, consisting of five building blocks:

(1) usually a quantifier (“every”, “some”, or “no”),

(2) a subject,

(3) a copula (“is”),

(4) perhaps a negation (“not”), and

(5) a predicate. Subject, copula and predicate were mandatory, the remaining two elements were optional. Propositions analyzable in this way fall into one of the following forms:

4 Introduction to Logic

quantifier subject copula (4) predicate
Every  A  is  B  : Universal affirmative
Every  A  is not B  : Universal negative
Some  A  is  B  : Particular affirmative
Some  A  is not B  : Particular negative
A  is  B  : Singular affirmative
A  is not B  : Singular negative

In the singular judgements A stands for an individual, e.g. “Socrates is (not) a man.” These two forms gained much less importance than the rest since in most contexts they can be seen as special cases of 3 and 4, respectively.

A.2.2. Conversions

Sometimes Aristotle adopted alternative but equivalent formulations. The universal negative judgment could also be formulated as “No A is B”, while the universal affirmative as “B belongs to every A” or “B is predicated of every A”.

Aristotle formulated several such rules, later known as the theory of conversion. To convert a proposition in this sense is to interchange its subject and predicate. Aristotle observed that universal negative and particular affirmative propositions can be validly converted in this way: if “some A is B”, then also “some B is A”, and if “no A is B”, then also “no B is A”. In later terminology, such propositions were said to be converted simply (simpliciter). But universal affirmative propositions cannot be converted in this way: if “every A is an B”, it does not follow that “every B is a A”. It does follow, however, that “some B is a A”. Such propositions, which can be converted by interchanging their subjects and predicates and, in addition, also replacing the universal quantifier “all” by the existential quantifier “some”, were later said to be converted accidentally (per accidens). Particular negative propositions cannot be converted at all: from the fact that some animal is not a dog, it does not follow that some dog is not an animal.

Below, the four figures of syllogism are presented. Aristotle used the laws of conversion to reduce other syllogisms to syllogisms in the first figure. Conversions represent thus the first form of essentially formal manipulation. They provide the rules for:

The history of logic 5

replacing occurrence of one (categorical) form of a statement by another – without affecting the proposition!

What does “affecting the proposition” mean is another subtle matter. The whole point of such a manipulation is that one changes the concrete appearance of a sentence, without changing its value. The intuition might have been that they essentially mean the same and are interchangeable. In a more abstract, and later formulation, one would say that “not to affect a proposition” is “not to change its truth value” – either both are false or both are true.

Two statements are equivalent if they have the same truth value.

This wasn’t exactly the point of Aristotle’s but we may ascribe him a lot of intuition in this direction. From now on, this will be a constantly recurring theme in logic. Looking at propositions as thus determining a truth value gives rise to some questions (and severe problems, as we will see.) Since we allow using some “placeholders” – variables – a proposition need not have a unique truth value. “All A are B” depends on what we substitute for A and B. In general, a proposition P may be:

(1) a tautology – P is always true, no matter what we choose to substitute for the “placeholders”; (e.g., “All A are A”. In particular, a proposition without any “placeholders”, e.g., “all animals are animals”, may be a tautology.)

(2) a contradiction – P is never true (e.g., “no A is A”);

(3) contingent – P is sometimes true and sometimes false; (“all A are B” is true, for instance, if we substitute “animals” for both A and B, while it is false if we substitute “birds” for A and “pigeons” for B).

A.2.3. Syllogisms

Aristotelian logic is best known for the theory of syllogisms which had remained practically unchanged and unchallenged for approximately 2000 years. In Prior Analytics, Aristotle defined a syllogism as a

discourse in which, certain things being stated something other than what is stated follows of necessity from their being so.

In spite of this very general definition, in practice he confined the term to arguments with only two premises and a single conclusion, each of which is a categorical proposition. The subject and predicate of the conclusion each occur in one of the premises, together with a third term (the middle)

6 Introduction to Logic

that is found in both premises but not in the conclusion. A syllogism thus argues that because S(ubject) and P (redicate) are related in certain ways to some M(iddle) term in the premises, they are related in a certain way to one another in the conclusion.

The predicate of the conclusion is called the major term, and the premise in which it occurs is called the major premise. The subject of the conclusion is called the minor term and the premise in which it occurs is called the minor premise. This way of describing major and minor terms conforms to Aristotle’s actual practice but was proposed as a definition only by the 6th century Greek commentator John Philoponus.

Aristotle distinguished three different “figures” of syllogisms, according to how the middle is related to the other two terms in the premises. He only mentioned the fourth possibility which was counted as a separate figure by later logicians. If one wants to prove syllogistically that S(ubject) is P (redicate), one finds a term M(iddle) such that the argument can fit into one of the following figures:

(I) “M is P ” and “S is M” – hence “S is P ”, or (II) “P is M” and “S is M” – hence “S is P ”, or (III) “M is P ” and “M is S” – hence “S is P ”, or (IV) “P is M” and “M is S” – hence “S is P ”.

Each of these figures can come in various “moods”, i.e., each categorical form can come with various quantifiers, yielding a large taxonomy of possible syllogisms. Since the Middle Ages, one has used the following abbreviations for the concerned quantifiers:

A : universal affirmative : all, every
E : universal negative : no
I : particular affirmative : some
O : particular negative : some is not, not every

The following is an example of a syllogism of figure I with the mood A-I-I. “Marshal” is here the middle term and “politician” the major term.

A: Every marshal is a politician.
I: Some soldiers are marshals.
I: Some soldiers are politicians.

(A.1)

The table below gives examples of syllogisms of all four figures with different moods. M is the middle term, P the major one and S the minor one.

The history of logic 7

figure I:  [M is P]  [S is M]  [S is P]
A-I-I Every [M is P] Some [S is M]  Some [S is P] Darii
A-A-A Every [M is P] Every [S is M]  Every [S is P] Barbara
figure II:  [P is M]  [S is M]  [S is P]
E-A-E  No [P is M] Every [S is M]  No [S is P] Cesare
figure III:  [M is P]  [M is S]  [S is P]
A-A-I Every [M is P] Every [M is S]  Some [S is P] Darapti
A-A-A Every [M is P] Every [M is S]  Every [S is P] –
figure IV:  [P is M]  [M is S]  [S is P]
E-A-O  No [P is M] Every [M is S] Some [S is not P] Fesapo

Four quantifiers, distributed arbitrarily among the three statements of a syllogism, give 64 different syllogisms of each figure and the total of 256 distinct syllogisms. Aristotle identified 19 among them which were universally correct or, as we would say today, valid. Validity of an argument means here that

no matter what concrete terms are substituted for the variables (P, M, S), if the premises are true then also the conclusion is guaranteed to be true.

For instance, the 5 examples above, with the special names in the last column, are valid. The names, given by the medieval scholars to the valid syllogisms, contained exactly three vowels identifying the mood. (The mnemonic aid did not extend further: Celarent and Cesare identify the same mood, so one had to simply remember that the former refers to figure I and the latter to figure II.)

Figure III with mood A-A-A does not yield a valid syllogism. To see this, we find a counterexample. Substituting women for M, female for P and human for S, the premises hold while the conclusion states that every human is female. Similarly, a counterexample can be found to every invalid syllogism.

Note that a correct application of a valid syllogism does not guarantee truth of the conclusion. (A.1) is such an application, but the conclusion need not be true. It may namely happen that a correct application uses a

8 Introduction to Logic

false assumption, for instance, in a country where the marshal title is not used in the military. In such cases the conclusion may accidentally happen to be true but no guarantees about that can be given. We see again that the main idea is truth preservation in the reasoning process. An obvious, yet nonetheless crucially important, assumption is:

The contradiction principle

For any proposition P it is never the case that both P and not-P are true.

This principle seemed (and to many still seems) intuitively obvious and irrefutable – if it were violated, there would be little point in constructing any “truth preserving” arguments. Although most logicians accept it, its status has been questioned and various logics, which do not obey this principle, have been proposed.

A.3. Other patterns and later developments

Aristotle’s syllogisms dominated logic until late Middle Ages. A lot of variations were invented, as well as ways of reducing some valid patterns to others (as in A.2.2). The claim that

all valid arguments can be obtained by conversion and, possibly, reductio ad absurdum from the three (four?) figures

has been challenged and discussed ad nauseum.

Early developments (already in Aristotle) attempted to extend the syllogisms to modalities, i.e., by considering instead of the categorical forms as above, the propositions of the form “it is possible/necessary that some A are B”. Early followers of Aristotle in the 4th/3th bc (Theophrastus of Eresus, Diodorus Cronus, the school of Megarians with Euclid) elaborated on the modal syllogisms and introduced another form of a proposition, the conditional

if (A is B) then (C is D).

These were further developed by Stoics who also made another significant step. One of great inventions of Aristotle were variables – the use of letters for arbitrary objects or terms. Now, instead of considering only patterns of terms where such variables are placeholders for objects, Stoics started to investigate logic with patterns of propositions. In such patterns, variables would stand for propositions instead of terms. For instance,

The history of logic 9

from two propositions: “the first” and “the second”, new propositions can be formed, e.g., “the first or the second”, “if the first then the second”, etc.

The terms “the first”, “the second” were used by Stoics as variables instead of single letters. The truth of such compound propositions may be determined from the truth of their constituents. We thus get new patterns of arguments. The Stoics gave the following list of five patterns

(i)  If 1 then 2;  but 1; therefore 2.
(ii)  If 1 then 2; but not 2; therefore not 1.
(iii) Not both 1 and 2;  but 1; therefore not 2.
(iv)  Either 1 or 2;  but 1; therefore not 2.
(v)  Either 1 or 2; but not 2; therefore 1.

(A.2)

Chrysippus, 3th bc, derived many other schemata and Stoics claimed that all valid arguments could be derived from these patterns. At the time, this approach seemed quite different from the Aristotelian and a lot of time went on discussions which is the right one. Stoic’s propositional patterns had fallen into oblivion for a long time, but they re-emerged as the basic tools of modern propositional logic. Medieval logic had been dominated by Aristotelian syllogisms, but its elaboratations did not contribute significantly to the theory of formal reasoning. However, Scholasticism developed very sophisticated semantic theories, which are addressed in the following section.

B. Logic – a language about something

The pattern of a valid argument is the first and through the centuries fundamental issue in the study of logic. But there were (and are) a lot of related issues. For instance, the two statements

(1) “all horses are animals”, and

(2) “all birds can fly”

are not exactly of the same form. More precisely, this depends on what a form is. The first says that one class (horses) is included in another (animals), while the second that all members of a class (birds) have some property (can fly). Is this grammatical difference essential or not? Or else, can it be covered by one and the same pattern or not? Can we replace a noun by an adjective in a valid pattern and still obtain a valid pattern

10 Introduction to Logic

or not? In fact, the first categorical form subsumes both above sentences, i.e., from the point of view of the logic of syllogisms, they are considered as having the same form.

Such questions indicate that forms of statements and patterns of reasoning require further analysis of “what can be plugged where” which, in turn, depends on which words or phrases can be considered as “having similar function”, perhaps even as “having the same meaning”. What are the objects referred to by various kinds of words? What are the objects referred to by the propositions?

B.1. Early semantic observations and problems

Certain teachings of the sophists and rhetoricians are significant for the early history of (this aspect of) logic. For example, Prodicus (5th bc) appears to have maintained that no two words can mean exactly the same thing. Accordingly, he devoted much attention to carefully distinguishing and defining the meanings of apparent synonyms, including many ethical terms. On the other hand, Protagoras (5ht bc) is reported to have been the first to distinguish different kinds of sentences – questions, answers, prayers, and injunctions. Further logical development addressed primarily propositions, “answers”, of which categorical propositions of Aristotle’s are the outstanding example. The categorical forms gave a highly sophisticated and very general schema for classifying various terms (possibly, with different grammatical status) as basic building blocks of arguments, i.e., as potential subjects or predicates.

Since logic studies statements, their form as well as patterns in which they enter valid arguments, one of the basic questions concerns the meaning of a proposition. As we indicated earlier, two propositions can be considered equivalent if they have the same truth value. This suggests another law, beside the contradiction principle, namely

The law of excluded middle (tertium non datur)

Each proposition P is either true or false.

There is surprisingly much to say against this apparently simple claim. There are modal statements (see B.4) which do not seem to have any definite truth value. Among many early counterexamples, there is the most famous one, which appeared in its usual version in the 4th century bc, and which is still disturbing and discussed by modern logicians:

The history of logic 11

The liar paradox

The sentence “This sentence is false” does not seem to have any content – it is false if and only if it is true!

Such paradoxes indicated the need for closer analysis of fundamental notions of the logical enterprise.

B.2. The Scholastic theory of supposition

The character and meaning of various “building blocks” of a logical language were thoroughly investigated by the Scholastics. Their theory of supposition was meant to answer the question:

To what does a given occurrence of a term refer in a given proposition?

Roughly, one distinguished three modes of supposition/reference:

(1) personal: In the sentence “Every horse is an animal”, the term “horse” refers to individual horses.

(2) simple: In the sentence “Horse is a species”, the term “horse” refers to a universal (the concept ‘horse’).

(3) material: In the sentence “Horse is a monosyllable”, the term “horse” refers to the spoken or written word.

The distinction between (1) and (2) reflects the fundamental duality of individuals and universals which had been one of the most debated issues in Scholasticism. The third point, apparently of little significance, marks an important development, namely, the increasing attention paid to the language and its mere syntax, which slowly becomes the object of study. Today, one often blurs the distinction between the first two suppositions, subsuming them under the category of ‘use’ and opposing to ‘mention’ which corresponds exactly to (3). Lacking the quotation marks, medieval writers could write, for instance, the example sentence (3) as “ Horse taken in the material supposition is a monosyllable.” Cumbersome as this may appear to an untrained reader, it disambiguated precisely references to language.

B.3. Intension vs. extension

Besides the supposition theory and its relatives, the logicians of the 14th century developed a sophisticated theory of connotation. The term “black”

12 Introduction to Logic

does not merely denote all black things – it also connotes the quality, blackness, which all such things possess. Connotation is also called “intension”

– saying “black” I intend blackness. Denotation is closer to “extension” – the collection of all the objects referred to by the term “black”. This has become one of the central distinctions in the later development of logic and in the discussions about the entities referred to by words. Its variants recur in most later theories, sometimes as if they were innovations. For instance, Frege opposes Sinn (sense, concept) to Bedeutung (reference), viewing both as constituting the meaning of a term. De Saussure distinguishes the signified (concept) from the referent (thing), and contrasts both with the signifier (sign). These later variants repeat the medieval understanding of a term which can be represented as follows:

\xymatrix{ & term \ar[dr]^{refers to} \ar[dl]_{intends} \\ intension \ar[rr]_{can be ascribed to} &  & extension}

The crux of many problems is that different intensions may refer to (denote) the same extension. The “Morning Star” and the “Evening Star” have different intensions and for centuries were considered to refer to two different stars. As it turned out, these are actually two appearances of one and the same planet Venus. The two terms have the same extension and the insight into this identity is a true discovery, completely different from the empty tautology that “Venus is Venus”.

Logic, trying to capture correctness of reasoning and conceptual constructions, might be expected to address the conceptual corner of the above triangle, the connotations or intensions. Indeed, this has been the predominant attitude and many attempts have been made to design a “universal language of thought” in which one could speak directly about the concepts and their interrelations. Unfortunately, the concept of concept is not obvious at all and such attempts never reached any universal consensus. One had to wait until a more tractable way of speaking of and modeling concepts become available. The emergence of modern mathematical logic coincides with the successful coupling of logical language with the precise statement of its meaning in terms of extension. Modern logic still has branches of intensional logic, but its main tools are of extensional nature.

B.4. Modalities

In chapter 9 of De Interpretatione, Aristotle discusses the assertion

The history of logic 13

There will be a sea battle tomorrow.

The problem is that, at the moment when it is made, it does not seem to have any definite truth value – whether it is true or false will become clear tomorrow but until then it is possible that it will be the one as well the other. This is another example (besides the liar paradox) indicating that adopting the principle of excluded middle, i.e., considering every proposition as having always only one of two possible truth values, may be insufficient.

Besides studying the syllogisms, medieval logicians, having developed the theory of supposition, incorporated into it modal factors. As necessity and possibility are the two basic modalities, their logical investigations reflected and augmented the underlying theological and ethical disputes about God’s omnipotence and human freedom. The most important developments in modal logic occurred in the face of such questions as:

(1) whether statements about future contingent events are now true or false (the question originating from Aristotle),

(2) whether humans can know in advance future contingent events, and (3) whether God can know such events.

One might distinguish the more onotological character of the first problem from the more epistemic flavour of the two latter, but in all three cases logical modality is linked with time. Thus, for instance, Peter Aureoli (12th/13th century) held that if something is B (for some predicate B) but could be not-B, i.e., is not necessarily B, then it might change, in the course of time, from being B to being not-B.

As in the case of categorical propositions, important issues here could hardly be settled before one had a clearer idea concerning the kinds of objects or states of affairs modalities are supposed to describe. In the late 13th century, the link between time and modality was severed by Duns Scotus who proposed a notion of possibility based purely on the notion of semantic consistency. “Possible” means here logically possible, that is, not involving contradiction. This conception was radically new and had a tremendous influence all the way down to the 20th century. Shortly afterward, Ockham developed an influential theory of modality and time which reconciled the claim that every proposition is either true or false with the claim that certain propositions about the future are genuinely contingent.

Duns Scotus’ ideas were revived in the 20th century, starting with the work of Jan Lukasiewicz who, pondering over Aristotle’s assertion about

14 Introduction to Logic

tomorrow’s sea battle, introduced 3-valued logic – a proposition may be true, or false, or else it may have a third, “undetermined” truth value. Also the “possible worlds” semantics of modalities, introduced by 19 years old Saul Kripke in 1959 (reflecting some ideas of Leibniz and reformulating some insights of Tarski and Jónsson), was based on Scotus’ combination of modality with consistency. Today, modal and many-valued logics form a dynamic and prolific field, applied and developed equally by philosophers, mathematicians and computer scientists.

C. Logic – a symbolic language

Logic’s preoccupation with concepts and reasoning begun gradually to put more and more severe demands on the appropriate and precise representation of the used terms. We saw that syllogisms used fixed forms of categorical statements with variables – A, B, etc. – representing arbitrary terms (or objects). Use of variables was indisputable contribution of Aristotle to the logical, and more generally mathematical notation. We also saw that Stoics introduced analogous variables standing for propositions. Such notational tricks facilitated more concise, more general and more precise statement of various logical facts.

Following the Scholastic discussions of connotation vs. denotation, logicians of the 16th century felt the increased need for a more general logical language. One of the goals was the development of an ideal logical language that would naturally express ideal thought and be more precise than natural language. An important motivation underlying such attempts was the idea of manipulation, in fact, symbolic or even mechanical manipulation of arguments represented in such a language. Aristotelian logic had seen itself as a tool for training “natural” abilities at reasoning. Now one would like to develop methods of thinking that would accelerate or improve human thought or even allow its replacement by mechanical devices.

Among the initial attempts was the work of Spanish soldier, priest and mystic Ramon Lull (1235-1315) who tried to symbolize concepts and derive propositions from various combinations of possibilities. He designed sophisticated mechanisms, known as “Lullian circles”, where simple facts, noted on the circumferences of various discs, could be combined by appropriately rotating the discs, providing answers to theological questions. The work of some of his followers, Juan Vives (1492-1540) and Johann Alsted (1588-1683) represents perhaps the first systematic effort at a logical symbolism.

The history of logic 15

Some philosophical ideas in this direction occurred in 17th century within Port-Royal – a group of anticlerical Jansenists located in Port-Royal outside Paris, whose most prominent member was Blaise Pascal (1623-1662). Elaborating on the Scholastical distinction between intension, or comprehension, and extension, Pascal introduced the distinction between real and nominal definitions. Real definitions aim at capturing the actual concept; they are descriptive and state the essential properties. “Man is a rational animal” attempts to give a real definition of the concept ‘man’, capturing man’s essence. Nominal definitions merely stipulate the conventions by which a linguistic term is to be used, referring to specific items. “By monoid we understand a set with a unary operation” is a nominal definition introducing the convention of using a particular word, “monoid”, for a given concept. The distinction nominal vs. real goes back to the discussions of the 14th century between the nominalism and realism with respect to the nature of universals. But Port-Royal’s distinction, accompanied by the emphasis put on usefulness of nominal definitions (in particular, in mathematics), resonated in wide circles, signaling a new step on the line marked earlier by the material supposition of the Scholastic theory – the use of language becomes more and more conscious and explicit. Although the Port-Royal logic itself contained no symbolism, the philosophical foundation for using symbols by nominal definitions was nevertheless laid.

C.1. The “universally characteristic language”

The goal of a universal language had already been suggested by Descartes (1596-1650) – firstly, as a uniform method for any scientific inquiry and then, for mathematics, as a “universal mathematics”. It had also been discussed extensively by the English philologist George Dalgarno (c. 1626-87) and, for mathematical language and communication, by the French algebraist François Viète (1540-1603). But it was Gottfried Leibniz (1646-1716), who gave this idea the most precise and systematic expression. His “lingua characteristica universalis” was an ideal that would, first, notationally represent concepts by displaying the more basic concepts of which they were composed, and second, represent (in the manner of graphs or pictures, “iconically”) the concept in a way that could be easily grasped by readers, no matter what their native tongue. Leibniz studied and was impressed by the Egyptian and Chinese picturelike symbols for concepts. Although we no longer use his notation, many items captured by it re-appear two centuries later in logical texts.

16 Introduction to Logic

C.2. Calculus of reason

Universal language seems a necessary precondition for another goal which Leibniz proposed for logic. A “calculus of reason” (calculus ratiocinator), based on appropriate symbolism, would

involve explicit manipulations of the symbols according to established rules by which either new truths could be discovered or proposed conclusions could be checked to see if they could indeed be derived from the premises.

Reasoning could then take place in the way large sums are done – mechanically or algorithmically – and thus not be subject to individual mistakes. Such derivations could be checked by others or performed by machines, a possibility that Leibniz seriously contemplated. Leibniz’ suggestion that machines could be constructed to draw valid inferences or to check the deductions of others was followed up in the 19th century by Charles Babbage, William Stanley Jevons, Charles Sanders Peirce and his student Allan Marquand.

The symbolic calculus that Leibniz devised was motivated by his view that most concepts were composite: they were collections or conjunctions of other more basic concepts. Symbols (letters, lines, or circles) were then used to stand for concepts and their relationships. This resulted in what is intensional rather than an extensional logic – one whose terms stand for properties or concepts rather than for the things having these properties. Leibniz’ basic notion of the truth of a judgment was that

the concepts making up the predicate are “included in” the concept of the subject.

For instance, the judgment ‘A zebra is striped and a mammal.’ is true because the concepts forming the predicate ‘striped-and-mammal’ are “included in” the concept (all possible predicates) of the subject ‘zebra’.

What Leibniz symbolized as A∞B, or what we would write today as A = B, was that all the concepts making up concept A also are contained in concept B, and vice versa.

Leibniz used two further notions to expand the basic logical calculus. In his notation, A⊕B∞C indicates that the concepts in A together with those in B wholly constitute those in C. Today, we might write this as A+B = C or A ∨ B = C – if we keep in mind that A, B, and C stood for concepts or properties, not for individual things nor sets thereof. Leibniz also used the

The history of logic 17

juxtaposition of terms, AB∞C (which we might write as A ∧ B = C) to signify that all the concepts in both A and B constitute the concept C.

A universal affirmative judgment, such as “Every A is B,” becomes in Leibniz’ notation A∞AB. This equation states that the concepts included in the concepts of both A and B are the same as those in A.

The syllogism Barbara:

Every A is B; every B is C; so every A is C, becomes the sequence of equations: A∞AB; B∞BC; so A∞AC.

Notice that this conclusion can be derived from the premises by two simple algebraic substitutions and the associativity of logical multiplication.

1. A ∞ AB  Every A is B
2. B ∞ BC  Every B is C
(1 + 2) A ∞ ABC
(1) A ∞ AC  therefore : Every A is C

(C.1)

As many early symbolic logics, including many developed in the 19th century, Leibniz’ system had difficulties with negative and particular statements (A.2.1). The treatment of propositional logic was limited and did not include any formalisation of relations nor of quantified statements. Only later Leibniz became keenly aware of the importance of relations and relational inferences. Although Leibniz might seem to deserve the credit for great originality in his symbolic logic – especially in his equational, algebraic logic – such insights were relatively common to mathematicians of the 17th and 18th centuries familiar with the traditional syllogistic logic. For instance, in 1685 Jakob Bernoulli published a pamphlet on the parallels of logic and algebra and gave some algebraic renderings of categorical statements. Later symbolic works of Lambert, Ploucquet, Euler, and even Boole – all apparently uninfluenced by Leibniz and Bernoulli – suggest the extent to which these ideas were apparent to the best mathematical minds of the day.

D. 19th and 20th Century – mathematization of logic

Leibniz’ system and calculus mark the appearance of a formalized, symbolic language which is prone to mathematical manipulation. A bit ironically, emergence of mathematical logic marks also this logic’s divorce, or at least separation, from philosophy. Of course, the discussions of logic have continued both among logicians and philosophers but from now on these groups form two increasingly distinct camps. Not all questions of philosophical

18 Introduction to Logic

logic are important for mathematicians and most of results of mathematical logic have rather technical character which is not always of interest for philosophers.

In this short presentation we have to ignore some developments which did take place between 17th and 19th century. It was only in the 19th century that the substantial contributions were made which created modern logic. Perhaps the most important among those in the first half of the 19th century, was the work of George Boole (1815-1864), based on purely extensional interpretation. It was a real break-through in the old dispute intensional vs. extensional. It did not settle the issue once and for all – for instance Frege, “the father of first-order logic” was still in favor of concepts and intensions; and in modern logic there is still a branch of intensional logic. However, Boole’s approach was so convincingly precise and intuitive that it was later taken up and become the basis of modern – extensional or set theoretical – semantics.

D.1. George Boole

Although various symbolic or extensional systems appeared earlier, Boole formulated the first logic which was both symbolic and extensional. Most significantly, it survived the test of time and is today known to every student of mathematics as well as of computer science or of analytical philosophy as the propositional logic (earlier also as logic or algebra of classes). Boole published two major works, The Mathematical Analysis of Logic in 1847 and An Investigation of the Laws of Thought in 1854. It was the first of these two works that had the deeper impact. It arose from two streams of influence: the English logic-textbook tradition and the rapid growth of sophisticated algebraic arguments in the early 19th century. German Carl Freidrich Gauss, Norwegian Niels Henrik Abel, French Évariste Galois were major figures in this theoretical appreciation of algebra at that time, represented also in Britain by Duncan Gregory and George Peacock. Such conceptions gradually evolved into abstract algebras of quaternions and vectors, into linear algebra, Galois theory and Boolean algebra itself.

Boole used variables – capital letters – for the extensions of terms, to which he referred as classes of “things”. This extensional perspective made the Boolean algebra a very intuitive and simple structure which, at the same time, captured many essential intuitions. The universal class – called “the Universe” – was represented by the numeral “1”, and the empty class by “0”. The juxtaposition of terms (for example, “AB”) created a term

The history of logic 19

referring to the intersection of two classes. The addition sign signified the non-overlapping union; that is, “A+B” referred to the entities in A or in B; in cases where the extensions of terms A and B overlapped, the expression was “undefined.” For designating a proper subclass of a class A, Boole used the notation “vA”. Finally, he used subtraction to indicate the removing of terms from classes. For example, “1 − A” indicates what one would obtain by removing the elements of A from the universal class – that is, the complement of A (relative to the universe, 1).

Boole offered a systematic, but not rigorously axiomatic, presentation. His basic equations included:

1A = A  0A = 0
0 + 1 = 1  A + 0 = A
AA = A  (idempotency)
A(BC) = (AB)C  (associativity)
AB = BA A + B = B + A (commutativity)
A(B + C) = AB + AC A + (BC) = (A + B)(A + C) (distributivity)

A universal affirmative judgment, such as “All A’s are B’s,” can be written using the proper subclass notation as A = vB. But Boole could write it also in two other ways: A = AB (as did Leibniz) or A(1 − B) = 0. These two interpretations greately facilitate derivation of syllogisms, as well as other propositional laws, by algebraic substitution. Assuming the distributivity A(B − C) = AB − AC, they are in fact equivalent:

AB = A  assumption
0 = A − AB −AB
0 = A(1 − B) distributivity

The derivation in the opposite direction (from 0 = A(1 − B) to A = AB) follows by repeating the steps in the opposite order with adding, instead of subtracting, AB to both sides in the middle. In words, the fact that all A’s are B’s and that there are no A’s which are not B’s are equivalent ways of stating the same, which equivalence could be included among Aristotle’s conversions, A.2.2. Derivations become now explicitly controlled by the applied axioms. For instance, derivation (C.1) becomes

A = AB  assumption
B = BC  assumption
A = A(BC) substitution BC for B
= (AB)C associativity
= AC  substitution A for AB

(D.1)

20 Introduction to Logic

In contrast to earlier symbolisms, Boole’s was extensively developed, exploring a large number of equations and techniques. It was convincingly applied to the interpretation of propositional logic – with terms standing for occasions or times rather than for concrete individual things. Seen in historical perspective, it was a remarkably smooth introduction of the new “algebraic” perspective which dominated most of the subsequent development. The Mathematical Analysis of Logic begins with a slogan that could serve as the motto of abstract algebra, as well as of much of formal logic:

the validity of the processes of analysis does not depend upon the interpretation of the symbols which are employed, but solely upon the laws of combination.

D.1.1. Further developments of Boole’s algebra; de Morgan

Boole’s approach was very appealing and quickly taken up by others. In the 1860s Peirce and Jevons proposed to replace Boole’s “+” with a simple inclusive union: the expression “A + B” was to be interpreted as the class of things in A, in B, or in both. This results in accepting the equation “1 + 1 = 1”, which is not true of the natural numbers. Although Boole accepted other laws which do not hold in the algebra of numbers (e.g., the idempotency of multiplication A^{2} = A), one might conjecture that his interpretation of + as disjoint union tried to avoid also 1 + 1 = 1.

At least equally important figure of British logic in the 19th century as Boole was Augustus de Morgan (1806-1871). Unlike most logicians in the United Kingdom, including Boole, de Morgan knew both the medieval logic and semantics, as well as the Continental, Leibnizian symbolic tradition of Lambert, Ploucquet, and Gergonne. His erudition and work left several lasting traces in the development of logic.

In the paper published in 1846 in the Cambrdige Philosophical Transactions, De Morgan introduced the enormously influential notion of

a possibly arbitrary and stipulated “universe of discourse”.

It replaced Boole’s original – and metaphysically a bit suspect – universe of “all things”, and has become an integral part of the logical semantics. The notion of a stipulated “universe of discourse” means that, instead of talking about “The Universe”, one can choose this universe depending on the context. “1” may sometimes stand for “the universe of all animals”, and in other contexts for a two-element set, say “the true” and “the false”. In the former case, the derivation (D.1) of A = AC from A = AB; B = BC

The history of logic 21

represents an instance of the Barbara syllogism “All A’s are B’s; all B’s are C’s; therefore all A’s are C’s”. In the latter case, the equations of Boolean algebra yield the laws of propositional logic where “A + B” corresponds to disjunction “A or B”, and juxtaposition “AB” to conjunction “A and B”. With this reading, the derivation (D.1) represents another reading of Barbara, namely: “If A implies B and B implies C, then A implies C”.

Negation of A is simply its complement 1 − A, and is obviously relative to the actual universe. (It is often written as \overline{A}.) De Morgan is known to all students of elementary logic primarily through the de Morgan laws:

\overline{AB} = \overline{A} + \overline{B} and dually
\overline{A} \overline{B} = \overline{A + B}.

Using these laws, as well as some additional, easy facts, like \overline{B}B = 0, \overline{\overline{B}} = B, we can derive the following reformulation of the reductio ad absurdum “If every A is B then every not-B is not-A”:

A = AB
A − AB = 0  −AB
A(1 − B) = 0  distributivity over −
A\overline{B} = 0  \overline{B} = 1 − B
\overline{A} + B = 1  deMorgan
\overline{B}(A + B) = \overline{B}  \overline{B}·
(\overline{B})(\overline{A}) + \overline{B}B = \overline{B}  distributivity
(\overline{B})(\overline{A}) + 0 = \overline{B}  \overline{B}B = 0
(\overline{B})(\overline{A}) = \overline{B}  X + 0 = X

I.e., if “Every A is B”, A = AB, than “every not-B is not-A”, \overline{B} = (\overline{B})(\overline{A}). Or: if “A implies B” then “if B is false (absurd) then so is A”.

A series of essays and papers on logic by de Morgan had been published from 1846 to 1862 under the title On the Syllogism. (The title indicates his devotion to the philosophical tradition of logic and reluctance to turn it into a mere branch of mathematics). The papers from 1850s are of considerable significance, containing the first extensive discussion of quantified relations since late medieval logic and Jung’s massive Logica hamburgensis of 1638.

Boole’s elegant theory had one serious defect, namely, its inability to deal with relational inferences. De Morgan’s first significant contribution to this field was made independently and almost simultaneously with the publication of Boole’s first major work. In 1847 de Morgan published his Formal Logic; or, the Calculus of Inference, Necessary and Probable. Although his symbolic system was clumsy and did not show the appreciation

22 Introduction to Logic

of abstract algebra that Boole’s did, it gave a treatment of relational arguments which was later refined by himself and others. His paper from 1859, On Syllogism IV and the Logic of Relations, started the sustained interest in the study of relations and their properties. De Morgan observed here that all valid syllogisms could be justified by the copula ‘is’ being a transitive and convertible (as he calls what today would be named “symmetric”) relation, i.e., one for which A ∼ B and B ∼ C implies A ∼ C and, whenever A ∼ B then also B ∼ A. Sometimes the mere transitivity suffices. The syllogism Barbara is valid for every transitive relation, e.g., if A is greater than B and B is greater than C then A is greater than C. In some other cases, also symmetry is needed as, for instance, to verify Cesare of figure II. It says that: if P ≁ M and S ∼ M then S ≁ P. For assuming otherwise, if S ∼ P then also P ∼ S by symmetry which, together with S ∼ M, implies by transitivity that P ∼ M.

De Morgan made the point, taken up later by Peirce and implicitly endorsed by Frege, that relational inferences are not just one type reasoning among others but are the core of mathematical and deductive inference and of all scientific reasoning. Consequently (though not correctly, but in the right spirit) one often attributes to de Morgan the observation that all of Aristotelian logic was helpless to show the validity of the inference,

All horses are animals; therefore,

every head of a horse is the head of an animal.

(D.2)

This limitation concerns likewise propositional logic of Boole and his followers. From today’s perspective, this can be seen more as the limitation of language, which does not provide means for expressing predication. Its appropriate (and significant) extension allows to incorporate analysis of relational arguments. Such an extension, which initially seemed to be a distinct, if not directly opposite approach, was proposed by the German Gottlob Frege, and is today known as first-order predicate logic.

D.2. Gottlob Frege

In 1879 the young Gottlob Frege (1848-1925) published perhaps the most influential book on symbolic logic in the 19th century, Begriffsschrift (“Conceptual Notation”) – the title taken from Trendelenburg’s translation of Leibniz’ notion of a characteristic language. Frege gives here a rigorous presentation of the role and use of quantifiers and predicates. Frege was apparently familiar with Trendelenburg’s discussion of Leibniz but was otherwise ignorant of the history of logic. He might have had a passing familiarity with the works of Boole and Lambert, but his book shows no trace of

The history of logic 23

the influence of Boole and little trace of the older German tradition of symbolic logic. Being a mathematician whose speciality, like Boole’s, had been calculus, he was well aware of the importance of functions. These form the basis of his notation for predicates and he does not seem to have been aware of the work of de Morgan and Peirce on relations or of older medieval treatments. Contemporary mathematical reviews of his work criticized him for his failure to acknowledge these earlier developments, while reviews written by philosophers chided him for various sins against reigning idealist conceptions. Also Frege’s logical notation was idiosyncratic and problematically two-dimensional, making his work hardly accessible and little read. Frege ignored the critiques of his notation and continued to publish all his later works using it, including his – also little-read – magnum opus, Grundgesetze der Arithmetik (1893-1903; “The Basic Laws of Arithmetic”).

Although notationally cumbersome, Frege’s system contained precise and adequate (in the sense, “adopted later”) treatment of several basic notions. The universal affirmative “All A’s are B’s” meant for Frege that the concept A implies the concept B, or that to be A implies also to be B. Moreover, this applies to arbitrary x which happens to be A. Thus the statement becomes: “∀x : A(x) → B(x)”, where the quantifier ∀x means “for all x” and the arrow “→” denotes implication. The analysis of this, and one other statement, can be represented as follows:

Every  horse  is an animal =
Every x which is a horse  is an animal
Every x  if it is a horse  then it is an animal
∀x :  H(x)  → A(x)
Some  animals  are horses =
Some x’s which are animals are horses
Some x’s  are animals  and are horses
∃x :  A(x)  ∧ H(x)

This was not the way Frege would write it but this was the way he would put it and think of it. The Barbara syllogism will be written today in first-order logic following exactly Frege’s analysis, though not his notation, as:

((∀x : A(x) → B(x)) ∧ (∀x : B(x) → C(x))) → (∀x : A(x) → C(x)). It can be read as: “If every x which is A is also B, and every x which is B is also C; then every x which is A is also C.” Judgments concerning

24 Introduction to Logic

individuals can be obtained from the universal ones by substitution. For instance:

Hugo is  Hugo is
a horse; and Every horse is an animal; So: an animal.
H(Hugo) ∧  (∀v : H(v) → A(v))
H(Hugo) → A(Hugo)  → A(Hugo)

(D.3)

The relational arguments, like (D.2) about horse-heads and animal-heads, can be derived after we have represented the involved statements as follows:

y is a head of some horse =

there is a horse and y is its head
there is an x which is a horse and y is the head of x
∃x :  H(x)  ∧ Hd(y, x)

y is a head of some animal =

∃x :  A(x)  ∧ Hd(y, x)

Now, the argument (D.2) will be given the form as in the first line and (very informal) treatement as in the following ones:

∀v(H(v) → A(v)) → ∀y(∃x(H(x) ∧ Hd(y, x)) → ∃z(A(z) ∧ Hd(y, z)))
assume horses are animals  and take an arbitrary y, e.g., a :
∀v(H(v) → A(v)) →  ∃x(H(x) ∧ Hd(a, x)) → ∃z(A(z) ∧ Hd(a, z))
assume horses are animals  and that there is a horse h whose head is a :
∀v(H(v) → A(v)) →  H(h) ∧ Hd(a, h) → ∃z(A(z) ∧ Hd(a, z))

but if horses are animals then h is an animal by (D.3), so A(h) ∧ Hd(a, h)

According to the last line, a is an animal-head and since a was an arbitrary horse-head, the claim follows.

In his first writings after the Begriffsschrift, Frege defended his own system and attacked bitterly Boolean methods, remaining apparently ignorant of the improvements by Peirce, Jevons, Schröder, and others. His main complaint against Booleans was the artificiality of their notation based on numerals and the failure to develop a genuinely logical notation.

In 1884 Frege published Die Grundlagen der Arithmetik (“The Foundations of Arithmetic”) and then several important papers on a series of mathematical and logical topics. After 1879 he developed his position that

all of mathematics could be derived from basic logical laws – a position later known as logicism in the philosophy of mathematics.

(D.4)

The history of logic 25

This view paralleled similar ideas about the reducibility of mathematics to set theory from roughly the same time. But Frege insisted on keeping them distinct and always stressed that his was an intensional logic of concepts, not of extensions and classes. His views are often marked by hostility to British extensional logic, like that of Boole, and to the general English-speaking tendencies toward nominalism and empiricism. In Britain, however, Frege’s work was much admired by Bertrand Russell who promoted Frege’s logicist research program – first in the Introduction to Mathematical Logic (1903), and then with Alfred North Whitehead, in Principia Mathematica (1910-13). Still, Russell did not use Frege’s notation and his development of relations and functions was much closer to Schröder’s and Peirce’s than to Frege’s. Frege’s hostility to British tradition did not prevent him from acknowledging the fundamental importance of Russell’s paradox, which Russell communicated to him in a letter in 1902. The paradox seemed to Frege a shattering blow to his goal of founding mathematics and science in an intensional logic and he expressed his worries in an appendix, hastily added to the second volume of Die Grundgesetze der Arithmetik, 1903, which was in press as Russell’s letter arrived.

It did not take long before also other mathematicians and logicians started to admire Frege’s care and rigour. His derivations were so scrupulous and precise that, although he did not formulate his theories axiomatically, he is sometimes regarded as a founder of the modern, axiomatic tradition in logic. His works had an enormous impact on the mathematical and philosophical logicians of the 20th century, especially, after their translation into English in the 1960s.

D.3. Set theory

As we have seen, the extensional view of concepts began gradually winning the stage with the advances of Boolean algebra. Set theory, founded by German Georg Cantor (1845-1918), addresses collections – of numbers, points and, in general, of arbitrary elements, also of other collections – and is thus genuinely extensional. Besides this difference from the traditional logic, oriented more towards the intensional pole of the opposition, the initial development of set theory was completely separate from logic. But already in the first half of the 20th century, symbolic logic developed primarily in interaction with the extensional principles of set theory. Eventually, even Frege’s analyses merged with the set theoretical approach to the semantics of logical formalism.

26 Introduction to Logic

Booleans had used the notion of a set or a class, but did develop tools for dealing with actually infinite classes. The conception of actual infinities, as opposed to merely potential, unlimited possibilities, was according to Aristotle a contradiction and most medieval philosophers shared this view. It was challenged in Renaissance, e.g., by Galileo, and then also by Leibniz. The problem had troubled 19th century mathematicians, like Carl Friedrich Gauss and the Bohemian priest Bernhard Bolzano, who devoted his Paradoxien des Unendlichen (1851; “Paradoxes of the Infinite”) to the difficulties posed by infinities. De Morgan and Peirce had given technically correct characterizations of infinite domains but these were not especially useful and went unnoticed in the German mathematical world. And the decisive development found place in this world.

Infinity – as the “infinitely small”, infinitesimal (coming from the infinitesimus which, in the Modern Latin of the 17th century, referred to the “infinite-th” element in a series) – entered the mathematical landscape with the integral and derivative calculus, introduced independently by Leibniz and Newton in the 1660s. Infinitesimals have been often severely criticized (e.g., by bishop Berkeley, as the “ghosts of departed quantities”) and only in the late 19th century obtained solid mathematical foundations in the work of the French baron Augustin-Louis Cauchy and German Karl Weierstraß. Building now on their discussions of the foundations of the infinitesimals, Germans Georg Cantor and Richard Dedekind developed methods for dealing with the infinite sets of the integers and points on the real number line. First Dedekind and then Cantor used Bolzano’s technique of measuring sets by one-to-one mappings. Defining two sets to be “equinumerous” iff they are in one-to-one correspondence,^{1} Dedekind gave in Was sind und was sollen die Zahlen? (1888; “What Are and Should Be the Numbers?”) a precise definition of an infinite set:

A set is infinite if and only if the whole set can be put into one-to-one correspondence with its proper subset.

This looks like a contradiction because, as long as we think of finite sets, it indeed is. But take the set of all natural numbers, ℕ = {0, 1, 2, 3, 4, ...} and remove from it 0 getting ℕ_{1} = {1, 2, 3, 4...}. The functions f : ℕ_{1} → ℕ, given by f(x) = x − 1, and f_{1} : ℕ → ℕ_{1}, given by f_{1}(x) = x + 1, are mutually inverse and establish a one-to-one correspondence between ℕ and its proper subset ℕ_{1}.

1The abbreviation “iff” stands for two-ways implication “if and only if”.

The history of logic 27

A set A is said to be “countable” iff it is equinumerous with ℕ. One of the main results of Cantor was demonstration that there are uncountable infinite sets, in fact, sets “arbitrarily infinite”. (For instance, the set ℝ of real numbers was shown by Cantor to be “genuinely larger” than ℕ.)

Cantor developed the basic outlines of a set theory, especially in his treatment of infinite sets and the real number line. But he did not worry much about rigorous foundations for such a theory nor about the precise conditions governing the concept of a set and the formation of sets. In particular, he did not give any axioms for his theory. The initial attempts to formulate explicitly precise principles, not to mention rigorous axiomatizations, of set theory faced serious difficulties posed by the paradoxes of Russell and the Italian mathematician Cesare Burali-Forti (1897). Some passages in Cantor’s writings suggest that he was aware of the potential problems, but he did not addressed them in a mathematical manner and, consequently, did not propose any technically satisfactory way of solving them. They were first overcome in the rigorous, axiomatic set theory – initially, by Ernst Zermelo in 1908, and in its final version of Ernst Zermelo and Abraham Fraenkel in 1922.

D.4. 20th century logic

The first half of the 20th century was the most active period in the history of logic. The late 19th century work of Frege, Peano and Cantor, as well as Peirce’s and Schröder’s extensions of Boole’s insights, had broken new ground and established new international communication channels. A new alliance – between logic and mathematics – emerged, gathering various lines of the late 19th century’s development. Common to them was the effort to use symbolic techniques, sometimes called “mathematical” and sometimes “formal”. Logic became increasingly mathematical in two senses. On the one hand, it attempted to use symbolic methods that had come to dominate mathematics, addressing the questions about

(1) the applications of the axiomatic method,

(2) a consistent theory of properties/relations (or sets),

(3) a logic of quantification.

On the other hand, it served the analysis and understanding of mathematics, becoming a tool in

(4) defining mathematical concepts,

(5) precisely characterizing mathematical systems, and

28 Introduction to Logic

(6) describing the nature of mathematical proof.

This later role of logic – as a meta-mathematical and eventually foundational tool – followed Frege’s logicism and dictated much of the development in the first decades of the 20th century.

D.4.1. Logicism

An outgrowth of the theory of Russell and Whitehead, and of most modern set theories, was a stronger articulation of logicism, according to which mathematical operations and objects are really purely logical constructions, (D.4). Consequently, the question what exactly pure logic is and whether, for example, set theory is really logic in a narrow sense has received increased attention. There seems little doubt that set theory is not only logic in the way in which, for example, Frege viewed it, i.e., as a formal theory of properties. Cantorian set theory engenders a large number of transfinite sets, i.e., nonphysical, nonperceived abstract objects. For this reason it has been regarded – by some as suspiciously, by others as endearingly – Platonistic. Still others, such as Quine, have only pragmatically endorsed set theory as a convenient – perhaps the only – way of organizing the whole world around us, especially if this world contains some elements of transfinite mathematics. The controversies about the status of infinite sets notwithstanding, it is thanks to them that, today, set theory as a foundation for various (or even all) mathematical disciplines is rather incontroversial. Mathematical theorems – whether in finitary discrete mathematics, or else in topology or analysis – can, at least in principle, be formulated and proven in the language of set theory.

But the first decades of the 20th century displayed a strong finitist Zeitgeist, comparable to the traditional scepticism against actual infinities, and embodied now in various criticisms of transfinite set theory. Already Kronecker in 19th century, opposing Weierstraß and Cantor, declared that God made only integers, while everything else – in particular, of infinitary character – is the work of man. The same spirit, if not technical development, was represented by the constructivism (known as intuitionism) of Dutch Brouwer and Heyting, or by formalism searching for a finitary representation of mathematics in Hilbert’s program, named so after the German mathematician David Hilbert (1862-1943). This program asked for an axiomatization of the whole of mathematics as a logical theory in order to prove formally that it is consistent. Even for those researchers who did not endorse this logicist program, logic’s goal was closely allied with techniques

The history of logic 29

and goals in mathematics, such as giving an account of formal systems or of the ideal nature of nonempirical proof. The logicist and formalist program stimulated much activity in the first decades of the 20th century. It waned, however, after Austrian Kurt Gödel demonstrated in 1931 that logic could not provide a foundation for mathematics nor even a complete account of its formal systems. Gödel proved namely a mathematical theorem which interpreted in natural language says something like:

Gödel’s (first) incompleteness theorem

Any logical theory, satisfying reasonable and rather weak conditions, cannot be consistent and, at the same time, prove all its logical consequences.

Thus mathematics can not be reduced to a provably complete and consistent logical theory. An interesting fact is that the proof of this theorem constructs a sentence analogous to the liar paradox. Gödel showed that in any formal theory satisfying his conditions, one can write the sentence “I am not provable in this theory”, which cannot be provable unless the theory is inconsistent.

In spite of this negative result, logic has remained closely allied with mathematical foundations and principles. In particular, it has become a mathematical discipline. Traditionally, its task has been understanding of valid arguments of all sorts, in particular, those formulated in natural language. It had developed the tools needed for describing concepts, propositions, and arguments and – especially, as the “logical patterns” or “forms” – for assessing argument’s quality. During the first decades of the 20th century, logic become gradually more and more occupied with the historically somewhat foreign role of analyzing arguments in only one field, mathematics. The philosophical and linguistic task of developing tools for analyzing arguments in some natural language, or else for analyzing propositions as they are actually (and perhaps necessarily) conceived by humans, was almost completely lost. This task was, to some extent, taken over by analytical philosophy and by scattered efforts attempting to reduce basic principles of other disciplines – such as physics, biology, and even music – to axioms, usually, in set theory or first-order logic. But even if they might have shown that it could be done, at least in principle, they were not very enlightening: one does not better or more usefully understand a bacteria, an atom or an animal by being told that it is a certain set or a (model of) certain axiomatic theory. Thus, such efforts, at their zenith in the 1950s

30 Introduction to Logic

and ’60s, had virtually disappeared in the ’70s. Logic has become a formal discipline with its relations to natural, human reasoning seriously severed. Instead, it found multiple applications in the field which originated from the same motivations and had been germinating underneath the developments of logic – the field of purely formal manipulations and mechanical reasoning, arising from the same finitist Zeitgeist of the first half of the 20th century: computer science. Its emergence from and dependence on logic will become even clearer after we have described the basic elements of modern, formal logic.

E. Modern Symbolic Logic

Already Aristotle and Euclid were aware of the notion of a rigorous logical theory, in the sense of a – possibly axiomatic – specification of its theorems. Then, in the 19th century, the crises in geometry could be credited with renewing the attention for very careful presentations of these theories and other aspects of formal systems.

Euclid designed his Elements around 10 axioms and postulates which one could not resist accepting as obvious (e.g., “an interval can be prolonged indefinitely”, “all right angles are equal”). From the assumption of their truth, he deduced some 465 theorems. The famous postulate of the parallels was

The fifth postulate

If a straight line falling on two straight lines makes the interior angles on the same side less than the two right angles, the two straight lines, if produced indefinitely, meet on that side on which the angles are less than the two right angles.

This postulate, even if reformulated, was somehow less intuitive and more complicated than others. Through hundreds of years mathematicians had unsuccessfully tried to derive it from the others until, in the 19th century, they started to reach the conclusion that it must be independent from the rest. This meant that one might as well drop it! That was done independently by the Russian Nicolai Lobachevsky in 1829 and the Hungarian János Bolayi in 1832. (Gauss, too, considered this move, but he never published his ideas on this subject.) What was left was a new axiomatic system. The big question about what this subset of axioms possibly described was answered by Lobachevsky and Bolayi who created its models, which satisfied all the axioms except the fifth – the first non-Euclidean ge-

The history of logic 31

ometries. This first exercise in what in the 20th century became “model theory”, can be considered the beginning of modern axiomatic approach. For the discovery of non-Euclidean geometries unveiled the importance of admitting the possibility of manipulating the axioms which, perhaps, are not given by God and intuition but may be chosen with some freedom.

E.1. Formal logical systems: syntax.

Although set theory and the type theory of Russell and Whitehead were considered to be logic for the purposes of the logicist program, a narrower sense of logic re-emerged in the mid-20th century as what is usually called the “underlying logic” of these systems. It does not make any existential assumptions (as to what kinds of mathematical objects do or do not exist) and concerns only rules for propositional connectives, quantifiers, and nonspecific terms for individuals and predicates. (An interesting issue is whether the privileged relation of identity, denoted “=”, is a part of logic: most researchers have assumed that it is.) In the early 20th century and especially after Alfred Tarski’s (1901-1983) work in the 1920s and ’30s, a formal logical system was regarded as being composed of three parts, all of which could be rigorously described:

(1) the syntax (or notation);

(2) the rules of inference (or the patterns of reasoning);

(3) the semantics (or the meaning of the syntactic symbols).

One of the fundamental contributions of Tarski was his analysis of the concept of ‘truth’ which, in the above three-fold setting is given a precise treatement as a particular

relation between syntax (linguistic expressions) and semantics (the world).

The Euclidean, and then non-Euclidean geometry were, as a matter of fact, built as axiomatic-deductive systems (point 2). The other two aspects of a formal system identified by Tarski were present too, but much less emphasized: notation was very informal, relying often on drawings; the semantics was rather intuitive and obvious. Tarski’s work initiated rigorous study of all three aspects.

E.1.1. The language

First, there is the notation:

32 Introduction to Logic

the rules of formation for terms and for well-formed formulas in the logical system.

A formal language is simply a set of words (well formed formulae, wff), that is, strings over some given alphabet (set of symbols) and is typically specified by the rules of formation. For instance:

• the alphabet Σ = {□, △, →, −, (,)}

• the rules for forming words of the language L: – □, △ ∈ L

– if A, B ∈ L then also −A ∈ L and (A → B) ∈ L.

This specification allows us to conclude that, for instance, △, −□, (△ → −□), −(□ → −△) all belong to L, while □△, () or □ → do not.

Previously, notation was often a haphazard affair in which it was unclear what could be formulated or asserted in a logical theory and whether expressions were finite or were schemata standing for infinitely long wffs. Now, the theory of notation itself became subject to exacting treatment, starting with the theory of strings of Tarski, and the work of the American Alonzo Church. Issues that arose out of notational questions include definability of one wff by another (addressed in Beth’s and Craig’s theorems, and in other results), creativity, and replaceability, as well as the expressive power and complexity of different logical languages (gathered, e.g., in Chomsky hierarchy).

E.1.2. Reasoning system

The second part of a logical system consists of

the axioms and rules of inference, or other ways of identifying what counts as a theorem.

This is what is usually meant by the logical “theory” proper: a (typically recursive) description of the theorems of the theory, including axioms and every wff derivable from axioms by admitted rules. Using the language L, one migh, for instance, define the following theory T:

Axioms: \begin{matrix}i) & □ \\ ii) & (△ → −□) \\ iii) & (A → − − A) \\ iv) & (− − A → A) \end{matrix}

The history of logic 33

Upper case letters denote variables for which we can substitute arbitrary formulae of our language L.

Rules: \begin{matrix}R1) & \frac{(A → B) ; (B → C)}{(A → C)} \\ R2) & \frac{(A → B) ; A}{B} \\ R3) & \frac{(A → B) ; −B}{−A} \end{matrix}

We can now perform symbolic derivations, starting with axioms and applying the rules, so that correctness can be checked mechanically. For instance:

\begin{aligned}& \begin{matrix}iii \\ (□ → − − □) \end{matrix} & \begin{matrix}i \\ □ \end{matrix} \\ R2 \\ & − − □ \end{aligned}  \begin{matrix}ii \\ (△ → −□) \end{matrix} R3 −△ iii (−△ → − − −△)

R2 − − −△

(E.1)

Thus, − − −△ is a theorem of our theory, and so is −△ which is obtained by the (left) subderivation ending with the application of rule R3.

A formal description of a language, together with a specification of a theory’s theorems (derivable propositions), are often called the “syntax” of the theory. This may be somewhat misleading when compared to the practice in linguistics, which would limit syntax to the narrower issue of grammaticality. The term “calculus” is sometimes chosen to emphasize the purely syntactic, uninterpreted nature of reasoning system.

E.1.3. Semantics

The last component of a logical system is the semantics for such a theory and language, a specification of

what the terms of a theory refer to, and how the basic operations and connectives are to be interpreted in a domain of discourse, including truth conditions for the formulae in this domain.

Consider, as an example the rule R1 from the theory T above. It is merely a “piece of text” and its symbols allow almost unlimited interpretations. We may, for instance, take A, B, C, ... to denote propositions and → an

34 Introduction to Logic

implication. (Note how rules R2 and R3 capture then Stoics’ patterns (i) and (ii) from (A.2), p. 9.) But we may likewise let A, B, C, ... stand for sets and → for set-inclusion. The following give then examples of applications of this rule under these two interpretations:

If it’s nice then we’ll leave
If we leave then we’ll see a movie
If it’s nice then we’ll see a movie

\begin{matrix}\{1, 2\} ⊆ \{1, 2, 3\} \\ \{1, 2, 3\} ⊆ \{1, 2, 3, 5\} \\ \{1, 2\} ⊆ \{1, 2, 3, 5\} \end{matrix}

The rule is “sound” with respect to these interpretations – when applied to these domains in the prescribed way, it represents a valid argument. In fact, R1 expresses transitivity of → and will be sound for every transitive relation interpreting →. This is just a more formal way of expressing de Morgan’s observation that the syllogism Barbara is valid for all transitive relations.

A specification of a domain of objects (de Morgan’s “universe of discourse”), and of the rules for interpreting the symbols of a logical language in this domain such that all the theorems of the logical theory are true is said to be a “model” of the theory. The two suggested interpretations are models of rule R1. (To make them models of the whole theory T would require more work, in particular, finding appropriate interpretation of □, △ and −, such that the axioms become true and all rules sound. For the propositional case, one could for instance let − denote negation, □ ‘true’ and △ ‘false’.)

If we chose to interpret the formulae of L as events and A → B as, say, “A is independet from B”, the rule would not be sound. Such an interpretation would not give a model of the theory or, what amounts to the same, if the theory were applied to this part of the world, we could not trust its results. The next subsection describes some further concepts arising with the formal semantics.

E.2. Formal semantics

Formal semantics, or model theory, relates the mere syntax to the whole of mathematics by connecting the syntactic expressions with potentially unlimited number of mathematical entities. It is more complex then the logical syntax alone and has a more complicated history, which often seems insufficiently understood. Certainly, Frege’s notion that propositions refer to (bedeuten) “the true” or “the false” – and this for complex propositions as a function of the truth values of simple propositions – counts as

The history of logic 35

semantics. This intuition underlies the ancient law of excluded middle and is likewise reflected in the use of letters for referring to the values 1 and 0, that started with Boole. Although modal propositions and paradoxes pose severe problems for this view, it dominates most of the logic, perhaps, because it provides a relatively simple and satisfactory model for a very significant portion of mathematical and natural discourse. Medieval theories of supposition formulated many useful semantic observations. In the 19th century, both Peirce and Schröder occasionally gave brief demonstrations of the independence of certain postulates using models in which some postulates were true, but not others. This was also the technique used by the inventors of non-Euclidean geometry.

The first significant and general result of a clearly model theoretic character is usually accepted to be a result discovered by Löwenheim in 1915 and strengthened by Skolem in the 1920s.

Löwenheim-Skolem theorem

A theory that has a model at all, has a countable model.

That is to say, if there exists some model of a theory (i.e., an application of it to some domain of objects), then there is sure to be one with a domain no larger than the natural numbers. This theorem is in some ways a shocking result, since it implies that any consistent formal theory of anything – no matter how hard it tries to address the phenomena unique to a field such as biology, physics, or even sets or just real numbers – can just as well be understood as being about natural numbers: it says nothing more about the actually intended field than it says about natural numbers.

E.2.1. Consistency

The second major result in formal semantics, Gödel’s completeness theorem of 1930 (see E.2.2 below), required even for its description, let alone its proof, more careful development of precise metalogical concepts about logical systems than existed earlier. One question for all logicians since Boole, and certainly since Frege, had been:

Is the theory consistent? In its purely syntactic analysis, this amounts to the question: Is a contradictory sentence (of the form “A and not-A”) derivable?

In most cases, the equivalent semantic counterpart of this is the question:

Does the theory have a model at all?

36 Introduction to Logic

For a logical theory, consistency means that a contradictory theorem cannot be derived in the theory. But since logic was intended to be a theory of necessarily true statements, the goal was stronger: a theory is Postconsistent (named after Emil Post) if every theorem is valid – that is, if no theorem is a contradictory or a contingent statement. (In nonclassical logical systems, one may define many other interestingly distinct notions of consistency; these notions were not distinguished until the 1930s.) Consistency was quickly acknowledged as a desired feature of formal systems. Earlier assumptions about consistency of various theories of propositional and first-order logic turned out to be correct. A proof of the consistency of propositional logic was first given by Post in 1921. Although the problem itself is rather simple, the original difficulties concerned the lack of precise syntactic and semantic means to characterize consistency. The first clear proof of the consistency of the first-order predicate logic is found in the book of David Hilbert and Wilhelm Ackermann, Gründzuge der theoretische Logik (“Principles of theoretical logic”) from 1928. Here, in addition to a precise formulation of consistency, the main problem was also a rigorous statement of first-order predicate logic as a formal theory.

Consistency of more complex systems proved elusive. Hilbert had observed that there was no proof that even the Peano postulates (for arithmetics) were consistent, while Zermelo was concerned with demonstrating that set theory was consistent. These questions received an answer that was not what was hoped for. Although Gerhard Gentzen (1909-1945) showed that Peano arithmetics is consistent, he needed for this purpose stronger assumptions than those of Peano arithmetics. Thus “true” consistency of arithmetics still depends on the consistency of the extended system used in the proof. This system, in turn, can not prove its own consistency and this is true about any system, satisfying some reasonably weak assumptions. This is the content of Gödel’s second incompleteness theorem, which put a definite end to the Hilbert’s program of using formal logic for proving the consistency of mathematics.

E.2.2. Completeness

In their book from 1928 Hilbert and Ackermann also posed the question of whether a logical system and, in particular, first-order predicate logic, was “complete”, i.e.,

whether every valid proposition – that is, every proposition that is true in all intended models – is provable in the theory.

The history of logic 37

In other words, does the formal theory describe all the noncontingent truths of its subject matter? Some idea of completeness had clearly accompanied Aristotle’s attempts to collect all human knowledge and, in particular, all valid arguments or, in geometry, Euclid’s attempts to derive all true theorems from a minimal set of axioms. Completness of a kind had also been a guiding principle of logicians since Boole – otherwise they would not have sought numerous axioms, risking their mutual dependence and even inconsistency. But all these earlier writers have lacked the semantic terminology to specify what their theory was about and wherein “aboutness” consists. In particular, they lacked the precise grasp of the “all truths” which they tried to capture. Even the language of Hilbert and Ackermann from 1928 is not perfectly clear by modern standards.

Post had shown the completeness of propositional logic in 1921 and Gödel proved the completeness of first-order predicate logic in his doctoral dissertation of 1930. In many ways, however, explicit consideration of issues in semantics, along with the development of many of the concepts now widely used in formal semantics and model theory, first appeared in a paper by Alfred Tarski, The Concept of Truth in Formalized Languages, which was published in Polish in 1933 and became widely known through its German translation of 1936. Introducing the idea of a sentence being “true in” a model, the paper marked the beginning of modern model theory. Even if the outlines of how to model propositional logic had been clear to the Booleans and to Frege, one of Tarski’s crucial contributions was an application of his general theory to the semantics of the first-order logic (now termed the set-theoretic, or Tarskian, interpretation). Relativity of truth to a model suggests choosing the models with some freedom (recall de Morgan’s stipulated universe of discourse). Specifying precisely the class of intended models for a theory allows then to ask about proposition’s “validity”, i.e., whether it is true in all intended models. Completeness amounts to the syntactic derivability of every valid propostion, and this definition applies now to propositional and first-order logic, as well as to any other logical system.

Although the specific theory of truth Tarski advocated has had a complex and debated legacy, his techniques and precise language for discussing semantic concepts – such as consistency, completeness, independence – having rapidly entered the literature in the late 1930s, remained in the center of the subsequent development of logic and analytic philosophy. This influence accelerated with the publication of his works in German and then in English, and with his move to the United States in 1939.

38 Introduction to Logic

E.3. Computability and Decidability

The underlying theme of the whole development we have sketched is the attempt to formalize logical reasoning, hopefully, to the level at which it can be performed mechanically. The idea of “mechanical reasoning” has been always present, if not always explicitly, in the logical investigations and could be almost taken as their primary, if only ideal, goal. Intuitively, “mechanical” involves some blind following of the rules and such a blind rule following is the essence of a symbolic system as described in E.1.2. This “mechanical blindness” follows from the fact the language and the rules are unambiguously defined. Consequently, correctness of the application of a rule to an actual formula can be verified mechanically. You can easily check that all applications of rules in the derivation (E.1) are correct and equally easily see that, for instance, \frac{(□→△) ; △}{□} is not a correct application of any rule from T.

Logic was supposed to capture correct reasoning and correctness amounts to conformance to some accepted rules. A symbolic reasoning system is an ultimately precise expression of this view of correctness which also makes its verification a purely mechanic procedure. Such a mechnism is possible because all legal moves and restrictions are expressed in the syntax: the language, axioms and rules. In other words, it is exactly the uninterpreted nature of symbolic systems which leads to mechanisation of reasoning. Naturally enough, once the symbolic systems were defined and one became familiar with them, i.e., in the beginning of the 20th century, the questions about mechanical computability were raised by the logicians. The answers led to the design and use of computers – devices for symbolic, that is, uninterpreted manipulation.

E.3.1. Computability

What does it mean that something can be computed mechanically?

In the 1930s this question acquired the ultimately precise, mathematical meaning. Developing the concepts from Hilbert’s school, in his Princeton lectures 1933-34 Gödel introduced the schemata for so called “recursive functions” working on natural numbers. Some time later Alonzo Church proposed the famous thesis

Church thesis

A function is (mechanically) computable if and only if it can be defined using only recursive functions.

The history of logic 39

This may sound astonishing – why just recursive function are to have such a special significance? The answer comes from the work of Alan Turing who introduced “devices” which came to be known as Turing machines. Although defined as conceptual entities, one could easily imagine that such devices could be actually built as physical machines performing exactly the operations suggested by Turing. The machines could, for instance, recognize whether a string had some specific form and, generally, compute functions. The functions which could be computed on Turing machines were shown to be exactly the recursive functions! Even more significant for us may be the fact that there is a well-defined sublogic of first-order logic in which proving a theorem amounts to computing a recursive function, that is, which can code all possible computer programs. This subset comprises the Horn formulae, namely, the conditional formulae of the form

If A_{1} and A_{2} and ... and A_{n} then C.  (E.2)

Such rules might be claimed to have more “psychological plausibility” than recursive functions. But they are computationally equivalent. With a few variations and additions, the formulae (E.2) give the syntax of an elegant programming language Prolog. Thus, in the wide field of logic, there is a small subdomain providing sufficient means to study the issues of computability. (Such connections are much deeper and more intricate but we cannot address them all here.)

Church thesis remains only a thesis, claiming that the informal and intuitive notion of mechanical computability is formalized exactly by the notion of recursive functions (or their equivalents, like Horn formulae or Turing machine). The fact that they are exactly the functions computable on the physical computer lends this thesis a lot of plausibility. Moreover, so far nobody has managed to introduce a notion of computability which would be intuitively acceptable, physically realizable and, at the same time, would exceed the capacities of Turing machines. A modern computer program, with all its tricks and sophistication is, as far as its power and possibilities are concerned, nothing more than a Turing machine, a set of Horn formulae. Thus, logical results, in particular the negative theorems stating the limitations of logical formalisms, determine also the ultimate limits of computers’ capabilities as exemplified below.

E.3.2. Decidability

By the 1930s almost all work in the foundations of mathematics and in symbolic logic was being done in a standard first-order predicate logic, often

40 Introduction to Logic

extended with axioms or axiom schemata of set-theory. This underlying logic consisted of a theory of classical truth functional connectives, such as “and”, “not” and “if … then” (propositional logic, as with Stoics or Boole) and first-order quantification permitting propositions that “all” and “at least one” individual satisfy a certain formula (Frege). Only gradually in the 1920s and ’30s did a conception of a “first-order” logic, and of more expressive alternatives, arise.

Formal theories can be classified according to their expressive or representational power, depending on their language (notation) and reasoning system (inference rules). Propositional logic allows merely manipulation of simple, propositional patterns, combined with operators like “or”, “and”, (A.2), p.9. First-order logic allows explicit reference to, and quantification over, individuals, such as numbers or sets, but not quantification over properties of these individuals. For instance, the statement “for all x: if x is man then x is human” is first-order. But the following one is second-order, involving quantification over properties P, R: “for every x and any properties P, R: if P implies R and x is P then x is R.”^{2} (Likewise, the fifth postulate of Euclid is not finitely axiomatizable in the first-order language but is rather a schema or second-order formulation.)

The question “why should one bother with less expressive formalisms, when more expressive ones are available?” should appear quite natural. The answer lies in the fact that increasing expressive power of a formalism clashes with another desired feature, namely:

decidability

there exists a finite mechanical procedure for determining whether a proposition is, or is not, a theorem of the theory.

The germ of this idea is present in the law of excluded middle claiming that every proposition is either true or false. But decidability adds to it the requirement which can be expressed only with the precise definition of a finite mechanical procedure, of computability. This is the requirement that not only the proposition must be true/provable or not: there must be a terminating algorithm which can be run (on a computer) to decide which is the case. (In E.1.2 we have shown that, for instance, −△ is a

2Note a vague analogy of the distinction between first-order quantification over individuals and second-order quantification over properties to the distinction between extensional and intensional aspects from B.3. Since in the extensional context, a property P is just a set of individuals (possessing P), the intensional or property-oriented language becomes higher-order, having to address not only individuals but also sets thereof.

Third-order language allows then to quantify over sets of sets of individuals, etc.

The history of logic 41

theorem of the theory T defined there. But if you were now to tell whether (− − △ → (−□ → □)) is a theorem, you might have hard time trying to find a derivation and even harder trying to prove that no derivation of this formula exists. Decidability of a theory means that there is a computer program capable to answer every such question.)

The decidability of propositional logic, through the use of truth tables, was known to Frege and Peirce; its proof is attributable to Jan Lukasiewicz and Emil Post independently in 1921. Löwenheim showed in 1915 that first-order predicate logic with only single-place predicates was decidable and that the full theory was decidable if the first-order predicate calculus with only two-place predicates was decidable. Further developments were made by Thoralf Skolem, Heinrich Behmann, Jacques Herbrand, and Willard Quine. Herbrand showed the existence of an algorithm which, if a theorem of the first-order predicate logic is valid, will determine it to be so; the difficulty, then, was in designing an algorithm that in a finite amount of time would determine that propositions were invalid. (We can easily imagine a machine which, starting with the specified axioms, generates all possible theorems by simply generating all possible derivations – sequences of correct rule applications. If the formula is provable, the machine will, sooner or later, find a proof. But if the formula is not provable, the machine will keep for ever since the number of proofs is, typically, infinite.) As early as the 1880s, Peirce seemed to be aware that the propositional logic was decidable but that the full first-order predicate logic with relations was undecidable. The fact that first-order predicate logic (in any general formulation) was undecidable was first shown definitively by Alan Turing and Alonzo Church independently in 1936. Together with Gödel’s (second) incompleteness theorem and the earlier Löwenheim-Skolem theorem, the Church-Turing theorem of the undecidability of the first-order predicate logic is one of the most important, even if “negative”, results of 20th century logic.

Many facts about the limits of computers arise as consequences of these negative results. For instance, it is not (and never will be!) possible to write a computer program which, given an arbitrary first-order theory T and some formula f, is guaranteed to terminate giving the answer “Yes” if f is a theorem of T and “No” if it is not. A more mundane example is the following. One can easily write a computer program which for some inputs does not terminate. It might be therefore desirable to have a program U which could take as input another program P (a piece of text just like “usual” input to any program) and description of its input d and decide

42 Introduction to Logic

whether P run on d would terminate or not. Such a program U, however, will never be written as the problem described is undecidable.

F. Summary

The idea of correct thinking is probably as old as thinking itself. With Aristotle there begins the process of explicit formulation of the rules, patterns of reasoning, conformance to which would guarantee correctness. This idea of correctness has been gradually made precise and unambiguous leading to the formulation of (the general schema for defining) symbolic languages, the rules of their manipulation and hence cirteria of correct “reasoning”. It is, however, far from obvious that the result indeed captures the natural reasoning as performed by humans. The need for precision led to complete separation of the reasoning aspect (syntactic manipulation) from its possible meaning. The completely uninterpreted nature of symbolic systems makes their relation to the real world highly problematic. Moreover, as one has arrived at the general schema of defining formal systems, no unique system has arosen as the right one and their variety seems surpassed only by the range of possible application domains. The discussions about which rules actually represent human thinking can probably continue indefinitely. In the meantime, and perhaps most significantly, this purely syntactic character of formal reasoning systems provided the basis for a precise definition of the old theme of logical investigations: the unavoidable consequence, which now appears co-extensional, if not synonymous, with the mechanical computability.

The question whether human mind and thinking can be reduced to such a mechanic computation and simulated by a computer is still discussed by the philosophers and cognitive scientists. Also, much successful research is driven by the idea, if not the explicit goal, of obtaining such a reduction. The “negative” results as those quoted at the end of the last section, established by human mind and demonstrating limitations of the power of logic and computers, suggest that human cognition may not be reducible to, and hence neither simulated by, mechanic computation. In particular, reduction to mechanic computability would imply that all human thinking could be expressed as applications of simple rules like (E.2) on p. 39. Its possibility has not been disproved but it certainly does not appear plausible. Yet, as computable functions correspond only to a small part of logic, even if this reduction turns out impossible, the question of reduction of thinking to logic at large would still remain open. Most researchers do not seem

The history of logic 43

to believe in such reductions and, indeed, one need not believe in them to study logic. In spite of its philosophical roots, and its apparently theoretical and abstract character, it turned out to be the fundamental tool in the development, and later in the use and managment, of the most practical and useful appliance of the 20th century – the computer.

The Greek alphabet

upper lower
A  α  alpha
B  β  beta
Γ  γ  gamma
Δ  δ  delta
E  ϵ  epsilon
Z  ζ  zeta
H  η  eta
Θ  θ  theta
I  ι  iota
K  κ  kappa
Λ  λ  lambda
M  μ  mu

upper lower
N  ν  nu
Ξ  ξ  xi
O  o  omicron
Π  π  pi
R  ρ  rho
Σ  σ  sigma
T  τ  tau
Y  υ  upsilon
Φ  ϕ  phi
X  χ  chi
Ψ  ψ  psi
Ω  ω  omega