Read an Excerpt
ABSTRACT SETS AND FINITE ORDINALS
An Introduction to the Study of Set Theory
By G.B. KEENE Dover Publications, Inc.
Copyright © 2014 Dover Publications, Inc.
All rights reserved.
ISBN: 978-0-486-15500-5
CHAPTER 1
THE BASIC LOGICAL CONCEPTS
1.1. Introduction
THE symbolism of elementary logic is both simple and efficient. By its means elegant and powerful logical calculi can be set up for the purpose of formalizing a scientific theory. But familiarity with the techniques involved in setting up these logical calculi is not essential to an understanding of the present text. All that is required is an understanding of the meaning and interrelation of the following symbols:
~, •, v, [contains], [equivalent to], (x)φ, ([there exists]x)φ, ε
All of them translate straightforwardly into a familiar word or phrase of ordinary speech. But they are not mere shorthand symbols. For each differs from its counterpart in ordinary speech in virtue of the fact that it is precisely defined; whereas the words of ordinary speech are not. We shall formulate, explain and illustrate the definition of each in turn. In doing so we shall make use of the two groups of letters: x,y,z,w, and: P,Q,R,S, which we call variables. They are variables in the sense that they keep a place open in a formula, just as the x in x2 keeps a place open for any number we may wish to put there. The type of entity that may be put in place of our variables will be called the range of values of those variables. In fact the range of values of the variables x,y,z,w, is any individual object of any kind, and the range of values of the variables P,Q,R,S, is any proposition. Finally we shall use the notation T, to mean any true proposition, and F to mean any false proposition, and we shall refer to the symbols listed above as logical constants.
1.2. The Logical Constants
1.21. "Member of"
When the Greek letter ε occurs between two variables as in:
x ε y
the range of values of the variable y is, thereby, confined to classes. Thus if the value John Doe is given to the variable x and the value mortals to the variable y, the result is the formula:
John Doe ε mortals
which may be read:
"John Doe is a member of the class Mortals"
Again if we write Nn as the name of the class Natural Numbers, then the formula:
(I)
x ε Nn
gives rise to the following formulae, each of which represents a true statement:
(II)
0 ε Nn 1 ε Nn 2 ε Nn ... etc.
Any formula of the type (I) above will be called a propositional function, where this term is intended to mean: an expression which becomes a proposition (true or false) when values are assigned (suitably) to all the variables (of the sort: x,y,z) occurring in it. The propositional function is the most important among the various types of formula with which we shall be concerned in Part II. The word formula, however, will be used to refer quite generally to: either a propositional variable (e.g. P,Q etc.) standing alone, or a propositional function, or any combination of these properly constructed by means of the logical constants or, finally, a symbolized proposition (e.g. (II) above). In this connection we shall, for convenience, use the phrase "formula which represents a true (false) proposition" in the following way. A formula may represent a true (false) proposition either directly (as in the case of a symbolized proposition), or indirectly (as in the case of a formula containing variables which is assumed, for the sake of a particular argument, to give rise to some particular but unspecified true (false) proposition, by a suitable assignment of values to the variables).
1.22. "Not"
We use the sign "~" (read "tilde") immediately to the left of a formula. It is defined by a matrix which shows whether a formula having this sign as its first symbol, represents a true or a false proposition. The matrix shows this by reference to the formula to which the sign is adjoined:
P ~P
T F
F T
Thus if the sign occurs against a formula representing a true proposition, the result is a formula representing a false proposition (and vice versa); so that if it occurs against a propositional variable P which has a true proposition as its intended value, the result will be a formula representing a false proposition (and vice versa). Similarly, if it occurs against a propositional function having a true proposition as its intended value, the result will be a formula representing a false proposition (and vice versa). For example, if G is used to name the class of Greeks, then the formula:
x ε G
gives rise to the false proposition:
(III)
Mz ε G
if we are using Mz to name, say, Mozart. Therefore, by the above matrix, if we substitute (III) for P in the formula ~P, the result is a formula representing a true proposition, namely:
~(Mz ε G)
(i.e. "Mozart is not a Greek")
Again, if we substitute ~(0 ε Nn) for P in the formula ~P, the result is the following true symbolized proposition:
~(~(0 ε Nn))
(i.e. "0 is not not a member of the class Natural Numbers").
1.23. "And"
We use the sign · (read "dot") between formulae, and it is defined by the following matrix:
P Q P•Q
T T T
F T F
T F F
F F F
The matrix shows that if dot occurs between two formulae each of which represents a true proposition, the result is a formula representing a true proposition. In every other possible case the result is shown to be a formula representing a false proposition. For example, using the same name symbols as before, if we substitute (0 ε Nn) for P, and (Mz ε G) for Q in the formula P · Q then by the above matrix the result is the false proposition:
(0 ε Nn) (Mz ε G)
(i.e. "0 is a number and Mozart is a Greek")
On the other hand, by substituting (0 ε Nn) for P and ~(Mz ε G) for Q, we have as a result, the true proposition:
(0 ε Nn) • ~(Mz ε G)
(i.e. "0 is a number and Mozart is not a Greek")
1.24. "Or"
We use the sign v (read "vel") between formulae, and it is defined by the following matrix:
P Q P v Q
T T T
F T T
T F T
F F F
The matrix shows that if vel occurs between two formulae each of which represents a false proposition, the result is a formula representing a false proposition. In every other possible case the result is shown to be a formula representing a true proposition. For example, if we substitute (0 ε Nn) for P and (Mz ε G) for Q in the formula P v Q, then by the above matrix, the result is the true proposition:
(0 ε Nn) v (Mz ε G)
(i.e. "0 is a number or Mozart is a Greek")
Alternatively, substituting ~(0 ε Nn) for P and (Mz ε G) for Q we have as a result the false proposition:
~(0 ε Nn) v (Mz ε G)
(i.e. "0 is not a number or Mozart is a Greek")
1.25. "If ... then ..."
We use the sign [contains] (read "hook") between formulae and adopt it as an abbreviation for another expression—one involving constants whose matrices have already been given. The definition not being, in this case, a definition by matrix, the symbol "=df" is used (meaning "is a definitional abbreviation for"):
P [contains] Q =df ~(P · ~Q)
In other words, any proposition of the form "If ... then - - -" is rendered in logic by a formula of the form P [contains] Q, regardless of any relationship of meaning that may hold between the component propositions "..." and "- - -" in it. Clearly, this definition of the phrase is a very wide one. For, under it, the following propositions are true propositions:
(Mz ε G) [contains] (0 ε Nn)
(i.e. "If Mozart is a Greek then 0 is a number")
(Mz ε G) [contains] ~(0 ε Nn)
(i.e. "If Mozart is a Greek then 0 is not a number")
(Pl ε G) [contains] (0 ε Nn)
(i.e. "If Plato is a Greek then 0 is a number")
Surprising as these results may seem, they do not detract from the usefulness of the definition in logic. These results are, in fact, surprising only when the definition is misunderstood as an attempt to express the full meaning of the phrase "if ... then - - -" as normally used. But any case of its normal use such as occurs in the proposition: "If he is a citizen then he is a voter" is covered by the definition, i.e.:
(x ε C) [contains] (x ε V)
We can therefore safely give, as a negative defence of this definition, that the phrase "if ... then - - -" never occurs in ordinary speech without our defining conditions being satisfied; even if, in ordinary occurrences of the phrase, other conditions happen to be satisfied as well.
1.26. Equivalence
We use the sign [equivalent to] (read "three bars") between formulae and, as in the case of the hook sign, adopt it as a means of abbreviation. It is defined as follows:
P [equivalent to] Q-df (P [contains] Q) · (Q [contains] P)
By the definition of hook and the matrices for dot and for tilde, this definition entails that if three bars occurs between two formulae, each of which represents a true proposition, or between a pair representing false propositions, the result is a formula representing a true proposition. In the remaining two cases the result is a formula representing a false proposition. This can be seen from the following table:
P Q
P [equivalent to] Q
~ (P · ~Q) · ~ (P · ~Q)
T T T F F T T F F
F T T F F F F T T
T F F T T F T F F
T F T F T T T F T
1 c a 3 2 d b
Column 3 is calculated as follows: column (a) consists of the values which we are directed (by the tilde matrix) to assign to ~Q, taking each of the possible values of Q in turn. Column (b) gives the result of proceeding in the same way for ~P. Column (c) consists of the values which we are directed (by the dot matrix) to assign to (P · ~Q), taking each of the possible values of its components in turn (as given in column (a) and the column for P). Column (d) gives the analogous result for (Q · ~ P). Column (1) consists of the values which we are directed (by the tilde matrix) to assign to ~(P · ~Q), taking each of the possible values in column (c) in turn. Column (2) gives the analogous result for ~(Q · ~P). Column (3) consists of the values which we are directed (by the dot matrix) to assign to the entire formula, taking each of the possible pairs of values of its two main components in turn (as given in columns (1) and (2)). As our final result, column (3) shows that only when P and Q are either both true or both false, is P equivalent to Q according to our definition. In short the formula P [equivalent to] Q means "P is true if and only if Q is true".
Again, we have such superficially surprising results as that the following propositions are true propositions:
(Pl ε G) [equivalent to] (0 ε Nn)
(i.e. "Plato is a Greek, if and only if 0 is a number")
(Mz ε G) [equivalent to] ~(0 ε Nn)
(i.e. "Mozart is a Greek, if and only if 0 is not a number") For reasons analogous to those given above, these results do not detract from the value of this definition in logic.
It should, however, be noted in this connection that if we have a proposition, say P, from which we are able to deduce another proposition, say Q, and vice versa, the two propositions are equivalent in a stronger sense than that defined above. This follows from the fact that if Q is deducible from P we have a case of "If ... then - - -" where the phrase is being used in an important way, which is also stronger in meaning than the sign "[contains]". For in such a case, we are able to claim not merely:
~(P · ~Q)
but that given that P is true, it is a matter of logic that Q is not false. Analogously, where P and Q are mutually deducible from one another, we are able to claim not merely:
~(P · ~Q) · ~(Q · ~P)
but that given that P is true, it is a matter of logic that Q is not false, and vice versa. Thus the sign "[contains]" can be read as logically entails in case that we have been able to show how Q can be deduced from P; and the sign "[equivalent to]" can be read as logically entail one another, in case that we have been able to show how Q can be deduced from P and how P can be deduced from Q.
Since the proof of a theorem of the form "If ... then - - -" consists in showing how the second component proposition "- - -", can be deduced from the first "...", such a theorem, when proved, is a very much stronger claim than:
(...)[contains](---) or ~((...) · ~(---))
It is, in fact, the claim that "..." logically entails "---". This, then, is the interpretation to be given to the sign "[contains]" in the context of a proof.
1.27. "All"
We use the sign "(x)", (read "for all x") immediately to the left of a propositional function, to mean that the result of substituting any (no matter which suitable) value for the variable x in that propositional function, will be a true proposition. For example, if we use G as before and Ml for the class of mortals, we can construct the propositional function:
(x ε G) [contains] (x ε Ml)
Now the range of values of the variable in this function is all human beings. For only with such values could we obtain a true or false (as opposed to a meaningless) proposition from this propositional function. Thus the following are in the range of values concerned:
Plato Socrates Mozart
If we substitute each of these values in turn for the variable x in the above propositional function, we have the following three propositions:
(Pl ε G) [contains] (Pl ε Ml)
(St ε G) [contains] (St ε Ml)
(Mz ε G) [contains] (Mz ε Ml)
From the well-known nationalities of these individuals of the past and the definition of the sign "[contains]", it follows that each of these propositions is true. The claim that any such proposition is true, namely the proposition:
"All Greeks are mortal"
is formulated in logic by prefixing the sign "(x)" to the propositional function from which they were obtained, thus:
(IV)
(x)[(x ε G) [contains] (x ε Ml)]
Notice that we bracket off the propositional function before prefixing the sign "(x)". This is necessary in order to distinguish between (IV) and, say,
(x)(x ε G) [contains] (Mz ε Ml)
(i.e. "If Everything is a Greek then Mozart is a mortal")
Now (IV) will be true as long as the propositional function:
(x ε G) · ~(x ε Ml)
does not give rise to any true proposition, for (IV) is the same proposition as:
(V)
(x)~[(x ε G) · ~(x ε Ml)]
by the definition of the sign "[contains]". Thus, if there is at least one Greek who is not mortal (IV) and (V) will represent a false proposition. In that case the assertion that there is not at least one Greek who is not mortal, is the same assertion as that all Greeks are mortal. We make use of this fact in our definition of the word "some".
1.28. "some"
We use the sign "([there exists]x)" (read "for some x") immediately to the left of a propositional function, to mean that there exists at least one value in the range of appropriate values of the variable x in that propositional function, which gives rise to a true proposition when substituted for x. For example, if we use Pr to name the class of prime numbers we can construct the propositional function:
(x ε Nn) · (x ε Pr)
Here, the following individuals are in the range of values concerned:
1
2
3
4
... etc.
If we substitute each of these in turn for the variable x in the above propositional function, we have the following propositions:
(1 ε Nn) · (1 ε Pr)
(2 ε Nn) · (2 ε Pr)
(3 ε Nn) · (3 ε Pr)
(4 ε Nn) · (4 ε Pr)
From the definition of "prime number" and the definition of "·", it follows that the first three of these propositions are true and the last one, false. The claim that at least one such proposition is true, namely the proposition:
"Some numbers are prime numbers"
(Continues...)
Excerpted from ABSTRACT SETS AND FINITE ORDINALS by G.B. KEENE. Copyright © 2014 Dover Publications, Inc.. Excerpted by permission of Dover Publications, Inc..
All rights reserved. No part of this excerpt may be reproduced or reprinted without permission in writing from the publisher.
Excerpts are provided by Dial-A-Book Inc. solely for the personal use of visitors to this web site.
