Mathematical Logic from beginning

http://wormholetravel.net/math.html

Our ignorance of the past applies to medieval and Renaissance logic even more than to ancient logic. With respect to ancient logic, historians have at least checked all available material and although our knowledge of it is inadequate,  his is due to the destruction of our sources rather than to lack of interest — or effort by historians. With respect of the history of post-ancient logic, however, many manuscripts are known to exist which even today have not been read, let alone translated and produced in critical editions. In such a situation it is not surprising that post-ancient logic had practically no influence on the first formulators of math logic. Most of the work that was done would belong to what is now known as the philosophy of logic.

The nineteenth and early twentieth centuries are called the period of transition ion because they were considered as such by the innovators of math logic. Even today most logicians would probably consider this designation correct. Yet the inanition was probably not as smooth and neat as this label might suggest. We know that a number of supposedly original discoveries of this period were only discoveries. For example, logicians of this period, without having any knowl­edge of Stoic logic, rediscovered much of the content of Stoic logic.

A rebirth of logical inquiry took place in the nineteenth and the early twentieth century due to the development within maths of strange and surprising doctrines. The progress of maths confronted mathematicians with new and profound logical problems, for which the traditional logic was of no help. The rise of a geometry different from Euclid's was a real surprise, and neither mathematicians nor philosophers were quite sure what to make of it. The same holds true both for the discovery of different sizes of the infinitive and the logical inconsisten­cy of some axiomatic systems with seemingly innocuous axioms. The latter occurred in set theory. Non-Euclidean geometry and set theory both contained numerous statements which are counter-intuitive. Are these statements really true? One's doubts about the soundness of reasoning in these areas increased with the appearance of paradoxes. The dogmas of the past were inadequate and a new approach was needed. This new approach was to use math methods. It resulted in the new discipline: mathematical logic.

The new birth of logic was not due to one man or even to thinkers in one country. The contributors are numerous and their interrelations complex. Hence, we must abandon the historical style of the previous text. There the simplicity of the story was somewhat forgivable because of the paucity of evidence or primary researchers. Now, however, the sources of evidence are rich, and we shall never reach our goal if we continue to indulge in the luxury of history. Suffice it to say that the awakening of logic began with George Boole (1815-1864) and Augustus De Morgan (1806-1871). The most important early work was that of Gottlob Frege (1848-1925). From then on the development was very rapid. The work of Schroder (1841-1902), Charles Peirce (1839-1914) and Giuseppe Peano (1858-1932) paved the way for the great systematization of Principia Mathematica due to Whitehead (1861-1947) and Russell. Subsequently, the new area of what was later called metalogic developed.

There were essentially two methods of maths which transformed logic into a new discipline. The first was the algebraic method, in which relations between math entities are reflected in the relationships which hold between the symbols for these entities. Thus, new relationships between math entities can be discov­ered by manipulation of the symbols in accordance with certain rules. The sec­ond was the axiomatic method. What is meant here by the phrase "axiomatic method" is not the method that Euclid used, but a revision of that method based on various insights and discoveries made since his time. To distinguish it from Euclid's it is often called the formal axiomatic method.

In order to describe the method we need to make clear the important distinc­tion between a language and a metalanguage. We can use language, of course, to talk of many things: shoes, ships, kings, etc. We can also use language to talk about another language. We can use English to study, say, Japanese grammar. In such a situation we shall say that English is the metalanguage and Japanese the object language, that is, English is used to talk about Japanese and Japanese is the object of talk in English. Similarly, were we to study English grammar in

Japanese, English would be the object language, Japanese the metalanguage, and we would use Japanese names of English expressions. The distinction be­tween language and metalanguage (and, of course, metalanguage and meta-metalanguage, etc.) is subtle, and it isn't usually important outside of logic and philosophy.

We may summarize the distinction between object language and metalan­guage. In the object language we use the symbols, words, sentences, etc., of the object language but do not mention them; in the metalanguage we use the sym­bols, words, sentences, etc., of the metalanguage to mention the expression of the object language but we make no use of the expressions of the object language. The same distinction can be applied to other areas. For example, we have logic and metalogic, maths and metamaths etc. An example of a metageometric prob­lem is the problem of showing that Euclid's fifth postulate is independent of his other postulates. This problem is not about points, lines, triangles, etc. (as in the other  language); but rather about the logical relationship of the fifth postulate to the other postulates.

We are now in a position to describe a formal axiomatic system. The basis of it often called the primitive basis — consists of four things:

 1.     A List of Symbols. This list must include all the symbols which are to be used in the system.

 2.     Formation Rules. The formation rules indicate the ways in which symbols may be legally combined to produce formulas.

 3.     A List of Initial Formulas. This list consists of the formulas with which we start to operate. It can be finite or infinite. When the initial formulas are interpreted, they will become true axioms for the system.

 4.     List of Transformation Rules. These are the rules which when applied to the axioms, produce new formulas called theorems. The guiding motive is that when the system becomes interpreted, the rules will correspond with logical rules of inference.

A formal system has some analogy with a natural language. The symbols correspond to the letters of the alphabet, punctuation marks, numerals and so forth.

The transformation rules correspond to the grammatical rules of a natural language. The transformation rules correspond to various operations any speaker can perform on the language. When we apply our transformation rules to the initial formular, the result is a theorem. The exhibition of the application of the rules is a proof. More explicitly, a proof is a finite sequence of formulas, such that each formula is an initial formula or follows from an earlier formula by the application of a transformation rule. The last line of the proof is a theorem. We require that  the transformation rules be such that it is merely a mechanical procedure to determine whether or not a given sequence of formulas is a proof. What is required is that no ingenuity or special insight be needed; in other words, that it be mechanical.

Primary Logic: The Prepositional Calculus

This area of logic is called primary because other parts of logic presuppose it. For example, Aristotle's theory of reduction depends on a calculus of proposition which he never made explicit. Since primary logic has its historical roots in the Stoic logicians, it is, perhaps, appropriate that we begin with one of their examples:

Either the first or the second or the third      Either A or В or С

Not the first         Not A

Not the second     Not B

Therefore the third        Therefore С

We may turn an argument form into an argument by substituting sentences for the dummy letters. Our only requirement is that we substitute the same sentence throughout for the same dummy letter. From our present logical point of view we treat propositions as unanalyzed, thus making no attempt to discern their logical structure. From our unanalyzed propositions we may build compound ones. We use the symbol "V" — suggested by the Latin word "vel" - to indicate the sense of the word "or". A sentence in this form is called a disjunction (or alternation). Using the now-familiar device of a truth table, a modern device whose historical origins go back to the Stoics — we may define "V" exactly. In a similar way we may use the symbol "—" for the word " not"  .  called the negation of P. The symbols "—" and "V" are examples of truth functions; the former is a singularly function (since it operates on one proposition), the latter a binary  function. A truth function then is a function of one or more prepositional variables such that the assignment of a set of truth values (that is, either truth or false­hood) to each propositional variable determines a unique assignment of a truth value for the function. There are four possible singularly truth functions and sixteen possible binary ones. It is not necessary to consider ternary, etc., truth functions because all truth functions of more than two variables may be expressed in terms of binary truth functions. An "if..., then — " proposition is called a conditional, the proposition replacing "..." is called the antecedent, and that replacing the "—" is called the consequent. The conditional is equivalent to denying that the antecedent is true and the consequent is false. Following a long-standing convention, we use "Ͻ" as the special symbol for the conditional. There is another truth function which is so useful as to deserve a special name: p ≡ q, which may be read "p, if and only if, q", ≡  is called biconditional.

The purpose of our introduction of special symbols is to facilitate logical analysis. To each valid argument there corresponds a true conditional statement in which the antecedent is a conjunction of the premises and the consequent is the conclusion. To capture the notion of logically true for the propositional calculus, we shall define a propositional form to be a tautology if, and only if, its truth table contains only "T"s. In the propositional calculus all logical truths are tautologies and all tautologies are logical truths. A proposition will also be said to be a tau­tology if its propositional form is a tautology. We are now in a position to give an equivalent definition of a valid argument: An argument in the propositional cal­culus is valid if, and only if, its corresponding proposition is a tautology.

General Logic: The Predicate Calculus

There are many different types of arguments which cannot be accounted for by the propositional calculus so as to include arguments whose validity depends not only on the external relationship of propositions but also on the internal I construction of the propositions themselves. Simple illustrations of such 1 arguments would include Aristotelian syllogisms. We also want our new logic to have a notation which fits in with the propositional calculus and, further, we want to keep the algebraic feature that manipulation of symbols according to certain rules leads to the expression of new logical relationships.

Our new expanded logic is sometimes called the first-order (or restricted) calculus of propositional functions, sometimes the first-order (or restricted) functional calculus, and sometimes the first-order (or restricted) predicate calculus. The central notion to be explained is that of a propositional function or predicate. Let there be fixed some nonempty domain of discourse, that is, some set of objects which our logic will be about. Examples might include the set of physical objects, the set of living animals, or the set of natural numbers. The members of the domain of discourse will be called individuals. An n-place propositional function (or «n-place predicate) is a function of n individual variables, where the domain the definition is the domain of discourse and the domain of values is a set of propositions. Hence, when each variable in a propositional function (predicate) has assigned to it an individual, the result is a proposition. A one-place propositional function or predicate is a property, a two-place propositional function or predicate — a binary relation, a three-place propositional function or predicate — a ternary relation and so on. Sometimes we wish to express particular or universal propositions (as in the case of the syllogism). We may do this by making use of quantifiers, that is, operators which make particular or universal propositions out of predicates. We shall use two operators: "ヨ " which is called the existential quantifier, and " ∀  " which is called the universal quantifier. The formula 

"( Ǝx) A(x)" is read "there exists an x, A of x" or "for some x, A of x". It means that there is at least one individual in the domain of discourse which has the property represented by "A". The formula" (  ∀  x)A(x) " is read "for all x, A of x" or "given any x, A of x". It means that every individual in the domain of discourse has the property represented by "A". The order in which the quantifiers occur is important.

As the first step toward defining validity for the predicate calculus, we might raise the question whether the technique of a truth table might be extended from the prepositional calculus to the predicate calculus. The answer is "yes". But the technique, while possible, does not give us a mechanical test of validity as was in the case in the prepositional calculus. Nevertheless, truth tables will enable us to define what we mean by validity in the predicate calculus.

Set- Theoretic Logic: Higher-Order Predicate Calculi

Once the notion of quantification is understood, it is natural to introduce I Medicate variables and to extend its use to them. A logic which contains quantification over only one domain — the individuals — is called a first-order (or restricted) predicate calculus. A logic which contains quantification with two types variables — individual variables and predicate variables for individuals — is called a second-order predicate calculus. The higher-order predicate calculi are each isomorphic with various fragments of set theory. In fact, it seems likely that that theory as originally proposed by Cantor was meant to embody somewhat the same theoretical structure as is found in w-order logic. In the latter, of course, (here are individuals, properties of individuals, properties of properties of individuals ...