Tuesday, February 12, 2013

51. The Theory of Deduction - Primative ideas



Harold R. (Hal) Foster’s Prince Valiant
© Respective copyright/trademark holders.
THE THEORY OF DEDUCTION.

THE purpose of the present section is to set forth the first stage of the deduction of pure mathematics from its logical foundations. This first stage is necessarily concerned with deduction itself, i.e. with the principles by which conclusions are inferred from premises. If it is our purpose to make all our assumptions explicit, and to effect the deduction of all our other propositions from these assumptions, it is obvious that the first assumptions we need are those that are required to make deduction possible. Symbolic logic is often regarded as consisting of two coordinate parts, the theory of classes and the theory of propositions. But from our point of view these two parts are not coordinate; for in the theory of classes we deduce one proposition from another by means of principles belonging to the theory of propositions, whereas in the theory of propositions we nowhere require the theory of classes. Hence, in a deductive system, the theory of propositions necessarily precedes the theory of classes. But the subject to be treated in what follows is not quite properly described as the theory of propositions. It is in fact the theory of how one proposition can be inferred from another. Now in order that one proposition may be inferred from another, it is necessary that the two should have that relation which makes the one a consequence of the other. When a proposition q is a consequence of a proposition p, we say that p implies q. Thus deduction depends upon the relation of implication, and every deductive system must contain among its premises as many of the properties of implication as are necessary to legitimate the ordinary procedure of deduction. In the present section, certain propositions will be stated as premises, and it will be shown that they are sufficient for all common forms of inference. It will not be shown that they are all necessary, and it is possible that the number of them might be diminished. All that is affirmed concerning the premises is (1) that they are true, (2) that they are sufficient for the theory of deduction, (3) that we do not know how to diminish their number. But with regard to (2), there must always be some element of doubt, since it is hard to be sure that one never uses some principle unconsciously. The habit of being rigidly guided by formal symbolic rules is a safeguard against unconscious assumptions; but even this safeguard is not always adequate.

*1. PRIMITIVE IDEAS AND PROPOSITIONS.

Since all definitions of terms are effected by means of other terms, every system of definitions which is not circular must start from a certain apparatus of undefined terms. It is to some extent optional what ideas we take as undefined in mathematics; the motives guiding our choice will be (1) to make the number of undefined ideas as small as possible, (2) as between two systems in which the number is equal, to choose the one which seems the simpler and easier. We know no way of proving that such and such a system of undefined ideas contains as few as will give such and such
results*1. Hence we can only say that such and such ideas are undefined in such and such a system, not that they are indefinable. Following Peano, we shall call the undefined ideas and the undemonstrated propositions primitive ideas and primitive propositions respectively. The primitive ideas are explained by means of descriptions intended to point out to the reader what is meant; but the explanations do not constitute definitions, because they really involve the ideas they explain. In the present number, we shall first enumerate the primitive ideas required in this section; then we shall define implication; and then we shall enunciate the primitive propositions required in this section. Every definition or proposition in the work has a number, for purposes of reference. Following Peano, we use numbers having a decimal as well as an integral part, in order to be able to insert new propositions between any two. A change in the integral part of the number will be used to correspond to a new chapter. Definitions will generally have numbers whose decimal part is less than .1, and will be usually put at the beginning of chapters. In references, the integral parts of the numbers of propositions will be distinguished by being preceded by a star; thus "*1'01" will mean the definition or proposition so numbered, and "1" will mean the chapter in which propositions have numbers whose integral part is 1, i.e. the present chapter. Chapters will generally be called "numbers."

PRIMITIVE IDEAS.

(1) Elementary propositions. By an "elementary" proposition we mean one which does not involve any variables, or, in other language, one which does not involve such words as "all," "some," "the" or equivalents for such words. A proposition such as "this is red," where "this" is something given in sensation, will be elementary. Any combination of given elementary propositions by means of negation, disjunction or conjunction (see below) will be elementary. In the primitive propositions of the present number, and therefore in the deductions from these primitive propositions in *2-*5, the letters p, q, r, s will be used to denote elementary propositions.

(2) Elementary propositional functions. By an "elementary propositional function" we shall mean an expression containing an undetermined constituent, i.e. a variable, or several such constituents, and such that, when the undetermined constituent or constituents are determined, i.e. when values are assigned to the variable or variables, the resulting value of the expression in question is an elementary proposition. Thus if p is an undetermined elementary proposition, "not-p" is an elementary propositional function.

We shall show in *9 how to extend the results of this and the following numbers (*1-*5) to propositions which are not elementary.

(3) Assertion. Any proposition may be either asserted or merely considered. If I say "Caesar died," I assert the proposition "Caesar died," if I say "'Caesar died' is a proposition," I make a different assertion, and "Caesar died" is no longer asserted, but merely considered. Similarly in a hypothetical proposition, e.g. "if a = b, then b = a," we have two un-asserted propositions, namely "a = b" and "b = a," while what is asserted is that the first of these implies the second. In language, we indicate when a proposition is merely considered by "if so-and-so" or "that so-and-so" or merely by inverted commas. In symbols, if p is a proposition, p by itself will stand for the un-asserted proposition, while the asserted proposition will be designated by

" . p."

The sign " " is called the assertion-sign*2; it may be read "it is true that" (although philosophically this is not exactly what it means). The dots after the assertion-sign indicate its range; that is to say, everything following is asserted until we reach either an equal number of dots preceding a sign of implication or the end of the sentence. Thus " : p . . q" means " it is true that p implies q," whereas " . p . . q" means "p is true; therefore q is true." The first of these does not necessarily involve the truth either of p or of q, while the second involves the truth of both.

(4) Assertion of a propositional function. Besides the assertion of definite propositions, we need what we shall call "assertion of a propositional function." The general notion of asserting any propositional function is not used until *9, but we use at once the notion of asserting various special elementary propositional functions. Let φx be a propositional function whose argument is x; then we may assert φx without assigning a value to x. This is done, for example, when the law of identity is asserted in the form " A is A." Here A is left undetermined, because, however A may be determined, the result will be true. Thus when we assert φx, leaving x undetermined, we are asserting an ambiguous value of our function. This is only legitimate if, however the ambiguity may be determined, the result will be true. Thus take, as an illustration, the primitive proposition *1.2 below, namely

" : p v p . . p,"

i.e. "'p or p' implies p." Here p may be any elementary proposition: by leaving p undetermined, we obtain an assertion which can be applied to any particular elementary proposition. Such assertions are like the particular enunciations in Euclid: when it is said "let ABC be an isosceles triangle; then the angles at the base will be equal," what is said applies to any isosceles triangle; it is stated concerning one triangle, but not concerning a definite one. All the assertions in the present work, with a very few exceptions, assert propositional functions, not definite propositions.

As a matter of fact, no constant elementary proposition will occur in the present work, or can occur in any work which employs only logical ideas. The ideas and propositions of logic are all general: an assertion (for example) which is
 true of Socrates but not of Plato, will not belong to logic*3, and if an assertion which is true of both is to occur in logic, it must not be made concerning either, but concerning a variable x. In order to obtain, in logic, a definite proposition instead of a propositional function, it is necessary to take some propositional function and assert that it is true always or sometimes, i.e. with all possible values of the variable or with some possible value. Thus, giving the name "individual" to whatever there is that is neither a proposition nor a function, the proposition "every individual is identical with itself" or the proposition "there are individuals" will be a proposition belonging to logic. But these propositions are not elementary.

(5) Negation. If p is any proposition, the proposition "not-p," or "p is false," will be represented by "~p." For the present, p must be an elementary proposition.

(6) Disjunction. If p and q are any propositions, the proposition "p or q," i.e. "either p is true or q is true," where the alternatives are to be not mutually exclusive, will be represented by

"p v q."

This is called the disjunction or the logical sum of p and q. Thus "~ p v q" will mean "p is false or q is true"; ~(p v q) will mean "it is false that either p or q is true," which is equivalent to "p and q are both false"; “~(p v ~q) will mean "it is false that either p is false or q is false," which is equivalent to "p and q are both true "; and so on. For the present, p and q must be elementary propositions.

The above are all the primitive ideas required in the theory of deduction. Other primitive ideas will be introduced in Section B.

Definition of Implication. When a proposition q follows from a proposition p, so that if p is true, q must also be true, we say that p implies q. The idea of implication, in the form in which we require it, can be defined. The meaning to be given to implication in what follows may at first sight appear somewhat artificial; but although there are other legitimate meanings, the one here adopted is very much more convenient for our purposes than any of its rivals. The essential property that we require of implication is this: "What is implied by a true proposition is true." It is in virtue of this property that implication yields proofs. But this property by no means determines whether anything, and if so what, is implied by a false proposition. What it does determine is that, if p implies q, then it cannot be the case that p is true and q is false, i.e. it must be the case that either p is false or q is true. The most convenient interpretation of implication is to say, conversely, that if either p is false or q is true, then "p implies q" is to be true. Hence "p implies q" is to be defined to mean: "Either p is false or q is true." Hence we put:

*1.01. p q . = . ~p v q  Df.

Here the letters "Df" stand for "definition." They and the sign of equality together are to be regarded as forming one
symbol, standing for " is defined to mean*4." Whatever comes to the left of the sign of equality is defined to mean the same as what comes to the right of it. Definition is not among the primitive ideas, because definitions are concerned solely with the symbolism, not with what is symbolized; they are introduced for practical convenience, and are theoretically unnecessary.

In virtue of the above definition, when "p q" holds, then either p is false or q is true; hence if p is true, q must be true. Thus the above definition preserves the essential characteristic of implication; it gives, in fact, the most general meaning compatible with the preservation of this characteristic.

 

*1 The recognized methods of proving independence are not applicable, without reserve, to fundamentals. Cf. Principles of Mathematics, ~ 17. What is there said concerning primitive propositions applies with even greater force to primitive ideas.

*2 We have adopted both the idea and the symbol of assertion from Frege. t Cf. Principles of Mathematics, ~ 38.

*3 When we say that a proposition "belongs to logic," we mean that it can be expressed in terms of the primitive ideas of logic. We do not mean that logic applies to it, for that would of course be true of any proposition.

*4 The sign of equality not followed by the letters "Df" will have a different meaning, to be defined later.

Artist Unknown (tribe unknown) mask  © Respective copyright holders

Pencils: Jack Kirby Inks: Mike Royer   TM © Respective copyright/trademark holders.


Here our authors are laying the foundation of our logical system. Although this is all covered thoroughly in the introduction, they begin again taking baby steps, but using expanded, and language I find more accessible. The aspect of this language that appeals to me so much is the seeming repetition of thought expressed for ever greater degrees of fine distinctions. The text is a recipe for a specific line of symbolic rules we may use to go forward in reasoning undistracted by subconscious reasoning that may lead to error.



TM © Respective copyright/trademark holders


Script: Elliot Maggin Artwork: Kurt Schaffenberger    TM © Respective copyright/trademark holders.




Harold R. (Hal) Foster’s Prince Valiant  © Respective copyright/trademark holders.
 

Wednesday, February 6, 2013

49. Supplimental post Expanding #2-3



Harold R. (Hal) Foster’s Prince Valiant
© Respective copyright/trademark holders.
 
Bertrand Russell was masterful in using expressive language to make complex subject matter very clear to a careful reader. In the introductory chapters Russell uses repetition to structure the subject and impress the importance of each element introduced, and to aid in our learning. In retrospect I realize my error in condensing the earlier posts, and if the material is not clearly understood from reading them, I hope these supplemental posts are useful.



  Script:  Wm M Marston  Pencils and Inks: Harry G. Peter 
Wonder Woman™ © Respective copyright/trademark holders.
 
Assertion-sign. The sign "," called the "assertion-sign," means that what follows is asserted. It is required for distinguishing a complete proposition, which we assert, from any subordinate propositions contained in it but not asserted. In ordinary written language a sentence contained between full stops denotes an asserted proposition, and if it is false the book is in error. The sign

" prefixed to a proposition serves this same purpose in our symbolism. For example, if " (p p)" occurs, it is to be taken as a complete assertion convicting the authors of error unless the proposition "p p" is true (as it is). Also a proposition stated in symbols without this sign "" prefixed is not asserted, and is merely put forward for consideration, or as a subordinate part of an asserted proposition.

 

Inference. The process of inference is as follows: a proposition "p" is asserted, and a proposition "p implies q" is asserted, and then as a sequel the proposition "q" is asserted. The trust in inference is the belief that if the two former assertions are not in error, the final assertion is not in error. Accordingly whenever, in symbols, where p and q have of course special determinations,

" p" and " (p q)"

have occurred, then " q" will occur if it is desired to put it on record. The process of the inference cannot be reduced to symbols. Its sole record is the occurrence of " q." It is of course convenient, even at the risk of repetition, to write " p" and " (p q)" in close juxtaposition before proceeding to "q" as the result of an inference. When this is to be done, for the sake of drawing attention to the inference which is being made, we shall write instead

p q,"

which is to be considered as a mere abbreviation of the threefold statement

"p" and " (p q)" and " q."

Thus " p q" may be read "p, therefore q," being in fact the same abbreviation, essentially, as this is; for "p, therefore q" does not explicitly state, what is part of its meaning, that p implies q. An inference is the dropping of a true premise; it is the dissolution of an implication.

The use of dots. Dots on the line of the symbols have two uses, one to bracket off propositions, the other to indicate the logical product of two propositions. Dots immediately preceded or followed by "v" or "" or "≡" or "" or by "(x)," "(x,y)," "(x,y,z)"… or "(x), "('x,y)," "(x,y,z)"... or "[(ιx) )(φx) ]" or "[Ry]" or analogous expressions, serve to bracket off a proposition; dots occurring otherwise serve to mark a logical product. The general principle is that a larger number of dots indicates an outside bracket, a smaller number indicates an inside bracket. The exact rule as to the scope of the bracket indicated by dots is arrived at by dividing the occurrences of dots into three groups which we will name I, II, and III. Group I consists of dots adjoining a sign of implication () or of equivalence (≡) or of disjunction (v) or of equality by definition (= Df). Group II consists of dots following brackets indicative of an apparent variable, such as (x) or (x, y) or (x) or (x, y) or [(ιx) )(φx)] or analogous expressions*. Group III consists of dots which stand between propositions in order to indicate a logical product. Group I is of greater force than Group II, and Group II than Group III. The scope of the bracket indicated by any collection of dots extends backwards or forwards beyond any smaller number of dots, or any equal number from a group of less force, until we reach either the end of the asserted proposition or a greater number of dots or an equal number belonging to a group of equal or superior force. Dots indicating a logical product have a scope which works both backwards and forwards; other dots only work away from the adjacent sign of disjunction, implication, or equivalence, or forward from the adjacent symbol of one of the other kinds enumerated in Group II.

Some examples will serve to illustrate the use of dots.

"p v q . . q v p" means the proposition "'p or q' implies 'q or p."' When we assert this proposition, instead of merely considering it, we write

" : p v q . . q v p,"

where the two dots after the assertion-sign show that what is asserted is the whole of what follows the assertion-sign, since there are not as many as two dots anywhere else. If we had written "p: v: q . . q v p," that would mean the proposition "either p is true, or q implies 'q or p."' If we wished to assert this, we should have to put three dots after the assertion-sign. If we had written "p v q . . q : v : p," that would mean the proposition "either ‘p or q’ implies q, or p is true." The forms "p . v . q . . q v p" and "p v q . . q . v . p" have no meaning.

"p q . : q r . . p r" will mean "if p implies q, then if q implies r, p implies r." If we wish to assert this (which is true) we write

" :. p q : q r.”  

Again "p q . . q . r : . p r" will mean "if 'p implies q' implies 'q implies r,' then p implies r." This is in general untrue. (Observe that "p q" is sometimes most conveniently read as "p implies q," and sometimes as "if p, then q.") "p q . q r. . p r " will mean "if p implies q, and q implies r, then p implies r." In this formula, the first dot indicates a logical product; hence the scope of the second dot extends backwards to the beginning of the proposition. " p q: q r . . p r" will mean "p implies q; and if q implies r, then p implies r." (This is not true in general.) Here the two dots indicate a logical product; since two dots do not occur anywhere else, the scope of these two dots extends backwards to the beginning of the proposition, and forwards to the end.

"p v q . :. p . v . q r : . p v r" will mean "if either p or q is true, then if either p or 'q implies r' is true, it follows that either p or r is true." If this is to be asserted, we must put four dots after the assertion-sign, thus:

" :: p v q . ) :. p . v . q r : . p v r."

(This proposition is proved in the body of the work; it is *2.75.) If we wish to assert (what is equivalent to the above) the proposition: "if either p or q is true, and either p or 'q implies r' is true, then either p or r is true," we write "

:. p v q : p v q r : . p v r."

Here the first pair of dots indicates a logical product, while the second pair does not. Thus the scope of the second pair of dots passes over the first pair, and back until we reach the three dots after the assertion-sign. Other uses of dots follow the same principles, and will be explained as they are introduced. In reading a proposition, the dots should be noticed first, as they show its structure. In a proposition containing several signs of implication or equivalence, the one with the greatest number of dots before or after it is the principal one: everything that goes before this one is stated by the proposition to imply or be equivalent to everything that comes after it.

* The meaning of these expressions will be explained later, and examples of the use of dots in connection with them are given in post 12.




Script: Bill Mantlo  Pencils: Sal Buscema  Inks: Joe Sinnott  The LeaderÔ © Respective copyright/trademark holders.



Harold R. (Hal) Foster’s Prince Valiant
© Respective copyright/trademark holders.
 

50. Mathematical Logic; summary of part 1


Harold R. (Hal) Foster’s Prince Valiant
© Respective copyright/trademark holders.

PART I. MATHEMATICAL LOGIC.
SUMMARY OF PART I.
 In this Part, we shall deal with such topics as belong traditionally to symbolic logic, or deserve to belong to it in virtue of their generality. We shall, that is to say, establish such properties of propositions, propositional functions, classes and relations as are likely to be required in any mathematical reasoning, and not merely in this or that branch of mathematics.
The subjects treated in Part I may be viewed in two aspects: (1) as a deductive chain depending on the primitive propositions, (2) as a formal calculus. Taking the first view first: We begin, in *1, with certain axioms as to deduction of one proposition or asserted propositional function from another. From these primitive propositions, in Section A, we deduce various propositions which are all concerned with four ways of obtaining new propositions from given propositions, namely negation, disjunction, joint assertion and implication, of which the last two can be defined in terms of the first two. Throughout this first section, although, as will be shown at the beginning of Section B, our propositions, symbolically unchanged, will apply to any propositions as values of our variables, yet it will be supposed that our variable propositions are all what we shall call elementary propositions, i.e. such as contain no reference, explicit or implicit, to any totality. This restriction is imposed on account of the distinction between different types of propositions, explained beginning in post 26. Its importance and purpose, however, are purely philosophical, and so long as only mathematical purposes are considered, it is unnecessary to remember this preliminary restriction to elementary propositions, which is symbolically removed at the beginning of the next section.
Section B deals, to begin with, with the relations of propositions containing apparent variables (i.e. involving the notions of "all" or "some") to each other and to propositions not containing apparent variables. We show that, where propositions containing apparent variables are concerned, we can define negation, disjunction, joint assertion and implication in such a way that their properties shall be exactly analogous to the properties of the corresponding ideas as applied to elementary propositions. We show also that formal implication, i.e. "(x). φx ψx" considered as a relation of φx to ψx, has many properties analogous to those of material implication, i.e. "p q" considered as a relation of p and q. We then consider predicative functions and the axiom of reducibility, which are vital in the employment of functions as apparent variables. An example of such employment is afforded by identity, which is the next topic considered in Section B. Finally, this section deals with descriptions, i.e. phrases of the form "the so-and-so" (in the singular). It is shown that the appearance of a grammatical subject "the so-and-so" is deceptive, and that such propositions, fully stated, contain no such subject, but contain instead an apparent variable.
Section C deals with classes, and with relations in so far as they are analogous to classes. Classes and relations, like descriptions, are shown to be "incomplete symbols" (cf. post 39.), and it is shown that a proposition which is grammatically about a class is to be regarded as really concerned with a propositional function and an apparent variable whose values are predicative propositional functions (with a similar result for relations). The remainder of Section C deals with the calculus of classes, and with the calculus of relations in so far as it is analogous to that of classes.
Section D deals with those properties of relations which have no analogues for classes. In this section, a number of ideas and notations are introduced which are constantly needed throughout the rest of the work. Most of the properties of relations which have analogues in the theory of classes are comparatively unimportant, while those that have no such analogues are of the very greatest utility. It is partly for this reason that emphasis on the calculus-aspect of symbolic logic has proved a hindrance, hitherto, to the proper development of the theory of relations.
Section E, finally, extends the notions of the addition and multiplication of classes or relations to cases where the summands or factors are not individually given, but are given as the members of some class. The advantage obtained by this extension is that it enables us to deal with an infinite number of summands or factors.
Considered as a formal calculus, mathematical logic has three analogous branches, namely (1) the calculus of propositions, (2) the calculus of classes, (3) the calculus of relations. Of these, (1) is dealt with in Section A, while (2) and (3), in so far as they are analogous, are dealt with in Section C. We have, for each of the three, the four analogous ideas of negation, addition, multiplication, and implication or inclusion. Of these, negation is analogous to the negative in ordinary algebra, and implication or inclusion is analogous to the relation " less than or equal to " in ordinary algebra. But the analogy must not be pressed, as it has important limitations. The sum of two propositions is their disjunction, the sum of two classes is the class of terms belonging to one or other, the sum of two relations is the relation consisting in the fact that one or other of the two relations holds. The sum of a class of classes is the class of all terms belonging to some one or other of the classes, and the sum of a class of relations is the relation consisting in the fact that some one relation of the class holds. The product of two propositions is their joint assertion, the product of two classes is their common part, the product of two relations is the relation consisting in the fact that both the relations hold. The product of a class of classes is the part common to all of them, and the product of a class of relations is the relation consisting in the fact that all relations of the class in question hold. The inclusion of one class in another consists in the fact that all members of the one are members of the other, while the inclusion of one relation in another consists in the fact that every pair of terms which has the one relation also has the other relation. It is then shown that the properties of negation, addition, multiplication and inclusion are exactly analogous for classes and relations, and are, with certain exceptions, analogous to the properties of negation, addition, multiplication and implication for propositions. (The exceptions arise chiefly from the fact that "p implies q" is itself a proposition, and can therefore imply and be implied, while " is contained in β," where and β are classes, is not a class, and can therefore neither contain nor be contained in another class γ.) But classes have certain properties not possessed by propositions: these arise from the fact that classes have not a two-fold division corresponding to the division of propositions into true and false, but a threefold division, namely into (1) the universal class, which contains the whole of a certain type, (2) the null-class, which has no members, (3) all other classes, which neither contain nothing nor contain everything of the appropriate type. The resulting properties of classes, which are not analogous to properties of propositions, are dealt with in *24. And just as classes have properties not analogous to any properties of propositions, so relations have properties not analogous to any properties of classes, though all the properties of classes have analogues among relations. The special properties of relations are much more numerous and important than the properties belonging to classes but not to propositions. These special properties of relations therefore occupy a whole section, namely section D.
Artist unknown (Tlingit) Raven Clan Totem Pole   TM © Respective copyright/trademark holders.
Bill Overgard’s Rudy TM © Respective copyright/trademark holders.

As we move into a consideration of mathematical logic we find no less complexity than in our study so far, but the subject is easier to comprehend. Up to this point the authors were treating material that is purely metaphysical in nature. If we have maintained an understanding of the work and the notational expression to this point, no doubt continuing with actual subjects to apply our knowledge to learning shall be easier and more satisfying.

The text we are studying is the first edition Principia Mathematica; however, the second edition contains a number of revisions. After considering carefully how to proceed here, I’ve decided to present the original text, and at a point I will present the revisions as they become relevant. My reasoning is that the revisions are mainly simplifications in reasoning and notation, but do not negate or contradict the original text. Further I feel it is valuable to read these aspects because it is valuable to understand them so that questions they speak to in the system do not trouble us down the line.

Bill Watterson’s Calvin and Hobbes TM © Respective copyright/trademark holders.


Douglas Kramer (Kwakiutl) Head of a Bear ink on paperboard 1965  TM © Respective copyright/trademark holders.
Harold R. (Hal) Foster’s Prince Valiant
© Respective copyright/trademark holders.