Introduction to Logic
Ch. 3 Symbolizing Everyday Language
§3.2 Terms
A term is an expression that either (a) names or describes some object, or (b) generates a name or a description for some object whenever we replace the expression’s variables with names or with descriptions. Thus “x + y” both contains terms, namely, x and y, because these variables can be replaced with specific numerals, and also, the whole expression “x + y” itself is a term, because after its variables are substituted, it expresses the value 5.
§3.3 Predicates
Predication can be expressed as a relation. In this text, we use lower-case letters for variables and upper-case letters for relations. We would write “For every x, x is red or x is not red” as: For every x, Rx ∨ –Rx. Predicates can be either one-place, two-place, or n-place, depending on the number of terms the predicate relates.
§3.4 Quantifiers
The variables in our propositions can be quantified. If the variable applies to all such things, it is universally quantified. The sentence “Everyone is a miser” could be expressed “For all x, x is a miser” and rendered symbolically [in Suppes’ text] as: (x)(x is a miser). If however the variable applies to some or to just one such thing, it is existentially quantified. The sentence “something is greater than zero” could be expressed “there is an x such that x is greater than 0” and symbolically rendered as: (∃x)(x > 0). More quantifiers can be added, as in (∃x)(∃y)(∃z)(x + y = z + 2). To symbolize common nouns, we can use relational predicates and quantifiers. First consider an example with universal quantification, “All freshmen are intelligent”. It should be written with the conditional as: (x)(Fx → Ix), meaning “For all x, if x is a freshman then x is intelligent”. But the structure is different for existential quantification. “Some freshmen are intelligent” should be rendered with the conjunction as: (∃x)(Fx & Ix).
§3.5 Bound and Free variables
Atomic formulas are predicates followed or flanked by the appropriate number of terms as arguments. A formula more generally is either an atomic formula or a more complex formula built by adding or being combined by operators (–, &, ∨, →, ↔) or quantifiers ([the universal quantifier has no symbol before the variable here], ∃). The scope of the quantifier is the smallest formula following it, when that formula has no parentheses. Or it is whatever lies within the left-most parenthesis following the quantifier(s) and its right- sided partner. A variable in a formula is bound when it falls within the scope of the quantifier that uses it, and it is free otherwise. A sentence is a formula with no free variables in it.
Ch. 9 Sets
§9.1 Introduction
and
§9.2 Membership
A set is any kind of a collection of entities of any sort, and the members are said to “belong to” the set. This membership relation is symbolized ∈, and the set members are listed between braces, {}. If two sets have the same members, then those two sets are identical. This is the principle of extensionality for sets. There is an empty set, which has no members, and it is here symbolized Λ. Set {{1,2}} is not identical with set {1,2}, because the first set has one member, namely, {1,2}, and the second has these two members: 1,2. Most sets do not include themselves as members. And the membership relation is not symmetric, so from A ∈ B it does not follow that B ∈ A. The order of the members does not matter, so {1,3,5}={1,5,3}. And we do not count an element of a set twice, so {1,1,3,5}={1,3,5}. Also, the relation of set membership is not transitive. So from A∈B and B∈C, it does not follow that A∈C. For example, 2∈{1,2} and {1,2}∈{{1,2},{3,4}}. However, 2∉{{1,2},{3,4}}. We can understand properties in terms of set membership by saying that a thing has a given property if and only if it belongs to the set of things having this property. And finally, we can express the principle of the identity of indiscernibles in terms of set membership by saying that if y belongs to every set to which x belongs, then y=x.
§9.3 Inclusion
Set inclusion is different from set membership. To say one set is included in another is to say that all the terms belonging to the first also belong to the second. However, to say that one set is a member of another set is to say that the first set as a singular whole is one of the terms in the other set. We symbolize set inclusion with the ⊆ symbol. And if all the members of one set are included in a second, but not all of the second are included in the first, then we call the first a proper subset of the second, and we symbolize it with ⊂. We can distinguish set identity, set membership, and set inclusion with these examples, respectively: “Elizabeth II = the present Queen of England,” “Elizabeth II ∈ the class of women,” and “The class of women ⊆ the class of human beings”, noting that despite this symbolic distinction, in everyday language the symbols (=, ∈, and ⊆) in these sentences can all be substituted with the same word, “is”. We can also distinguish set identity, membership, and inclusion using the concepts of symmetry and transitivity. (a) Identity ≠ inclusion, because identity is symmetric but inclusion is not. (b) Inclusion ≠ membership, because inclusion is transitive, but membership is not. And (c) identity ≠ membership, because identity is both symmetric and transitive, but membership is neither.
§9.4 The Empty Set
The empty set has no members. It is a subset of all other sets, even if it is not explicitly specified as a member. And the empty set is the only set that can be a subset of the empty set.
§9.5 Operations on Sets
Certain operations can be performed on sets. If we find all the members shared in common between two sets, we are finding their intersection (∩):
(x)(x ∈ A ∩ B ↔ x ∈ A & x ∈ B)
When two intersecting sets share no members in common, that is, when they are mutually exclusive sets, their intersection is the empty set. The set containing all the members in total from two sets is their union (∪):
(x)(x ∈ A ∪ B ↔ x ∈ A ∨ x ∈ B)
All the members in set A that are not in set B is the difference (∼) of A and B.
(x)(x ∈ A ∼ B ↔ x ∈ A & x ∉ B)
These operations can be iterated.
§9.6 Domains and Individuals
A domain of individuals (also called a domain of discourse) is a specific set. For example, in sociology, if we speak of the set of albinos, we implicitly mean only those albinos within the specific set (within the domain) of humans. We use the symbol “V” to denote a domain. Suppose we have a domain V and a set A. The complement of A relative to the domain are all those items in the domain that are not in A. We symbolize it either as V∼A or just ∼A.
§9.7 Translating Everyday Language
Formulations of the sort “All ... are ...” as in “All Americans are philosophers” can be translated into set notation as A ⊆ P. In this and in the other cases, either both blanks would be filled by common nouns or the first with a common noun and the second with an adjective. When the second blank is filled by an adjective, we need to convert it to a set name. So “All Americans are mortal” would be translated as “The class of Americans are included in the class of mortal beings” or A ⊆ M. “Some ... are ...” formulations, like, “Some Americans are philosophers”, can be translated to A ∩ P ≠ Λ. (Here Λ is the empty set.) Note, from the “Some S are P” formulations, we can infer that their intersection is not an empty set. However, for “All S are P” formulations, their intersection can in fact be an empty set. We translate “No ... are ...” formulations, like “No Americans are philosophers” as A ∩ P = Λ. And “Some ... are not ...” formulations, like “Some Americans are not philosophers”, are translated A ∩ ∼P ≠ Λ. More complicated expressions need more complicated interpretations. “All Americans are clean and strong” could be A ⊆ C ∩ S. “Fools and drunk men are truth tellers” could be (F ∪ D) ⊆ T. “Some Frenchmen drink wine” could be F ∩ W ≠ Λ. “Some Americans drink both coffee and milk” could be A ∩ C ∩ M ≠ Λ. And “Some Americans who drink tea do not drink either coffee or milk” could be (A ∩ T) ∩ ∼(C ∪ M) ≠ Λ.
§9.8 Venn Diagrams
We may depict sets and their relations and properties using Venn diagrams. A rectangle signifies the domain of individuals. Inside it we draw circles to represent sets. These circles may overlap to designate intersections. We can shade regions to mean there are no members there. An x-shaped cross signifies that a particular region has at least one member. However, if an x-shaped cross is linked by a line to another cross, that means at least one of the crosses’ connected regions is non-empty (and thus some, but not all, of the linked cross regions can be empty, despite them having a cross marking). When statements about the set-relations are logically consistent, then a crossed region that is also shaded as empty is really empty, because the shading dominates the crossing. However, if the statements are inconsistent, then this inconsistency might be apparent in a dually shaded and crossed region that should still retain its member despite the shading. Syllogistic inferences can be tested by constructing a diagram for the premises, and then we see if the conclusion is compatible with what is depicted.
Two mutually exclusive sets.
A ∩ B = Λ
All A are B.
A ⊆ B
A ⊆ B (all A are B) and B ∩ C = Λ, (i.e., no B are C)
A ∩ B = Λ
A ⊆ B; “for to say that A is a subset of B means that no part of A lies outside B” (197).
A ∩ B = Λ and A ⊆ B.
Some A are B: A ∩ B ≠ Λ. [x means the regions is not empty.]
Some A are either B or C: A ∩ (B ∪ C) ≠ Λ
A ∪ B ≠ Λ (Something is either A or B)
A ∪ ~C ≠ Λ (Something is either A or not C)
A ∩ C ≠ Λ (Some A are C)
C ⊆ B (All C are B)
Checking syllogisms.
(1) No B are C
(2) All A are B
(3) Therefore no Aare C
[Since all the shared regions between A and C are shaded, it is a valid inference.]
§9.9 Elementary Principles About Operations on Sets
There are a number of tautological equivalences that can be useful when making proofs about sets. Here is a list [note that Λ is the empty set and V is the domain of discourse]:
As we can see, the list expresses a number of properties, like identity, commutativity, distributivity, associativity, excluded middle, non-contradiction, idempotency, absorption, and De Morgan’s laws.
Ch. 10. Relations
§10.1 Ordered Couples
An ordered couple is two objects given in a fixed order. We list the items in a series, separated by commas and placed between angle brackets, for example: ⟨x, y⟩. Two ordered couples are identical just when the first member of one is identical with the first member of the other, and the second member of one is identical with the second member of the other:
⟨x, y⟩ = ⟨u, v⟩ ↔ (x = u & y = v)
We can have ordered triples, quadruples, and so on. Generally speaking, we can have any-numbered ordered n-tuples. We define them all on the basis of ordered couples. An ordered triple, for example, would be:
⟨x, y, z⟩ = ⟨⟨x, y⟩, z⟩
and an ordered n-tuple:
⟨x1, x2, ..., xn⟩ = ⟨⟨x1, x2, ..., xn-1⟩, xn⟩
In sets, the repetition of members does not add new members, but in ordered n-tuples it does. So {1,2,2}={1,2}, but ⟨1,2,2⟩≠⟨1,2⟩. S is a finite sequence only if S is an ordered n-tuple, for example: ⟨Socrates, Plato, Democritus, Aristotle⟩. A Cartesian product is all the possible ordered pairs made by taking each element from one set and pairing it with each member of another. So if A={1,2} and B={Gandhi,Nehru} then
A × B = {⟨1, Gandhi⟩, ⟨1, Nehru⟩, ⟨2, Gandhi⟩, ⟨2, Nehru⟩}
§10.2 Definition of Relations
The order of the terms in a relation is often important. So we cannot just think of a predicate taking more than one term as relating members of some set. For, that set needs to have a fixed order. For example, if the relation is love, then it matters who loves whom, as the feeling is not always mutual. We designate such ordered n-tuples with angle brackets: ⟨x, y⟩. The set that can be substituted for the first term is the domain, for the second term, the counterdomain, and the union of both the domain and the counterdomain is the field.
(I) A binary relation is a set of ordered couples.
According to this definition the relation of loving is the set of ordered couples ⟨x, y⟩ such that x loves y. The relation of being less than is the set of all ordered couples ⟨x, y⟩ of numbers such that, for some positive number z,
x + z = y.
The obvious extension of (I) is that a relation which holds among three things is a set of ordered triples, and a relation which holds among n things is a set of ordered n-tuples.
A relation is called ‘n-ary’ if its members are n-tuples. For the special cases n = 2 and n = 3 we use special names, speaking of ‘binary’ and ‘ternary’ relations.
Since a relation is a set of ordered n-tuples, we can also use the “∈” notation to indicate that certain things stand in a given relation. Thus we can write:
⟨John, Mary⟩ ∈ L, instead of:
John L Mary
to indicate that John loves Mary. Similarly we can write:
⟨George, Mary, Elizabeth⟩ ∈ P,
instead of :
P(George, Mary, Elizabeth)
to indicate, let us say, that George and Mary are the parents of Elizabeth.
It is necessary to remember that an ordered couple is not a relation, but the set consisting of the ordered couple is. For instance,
⟨Thomas Aquinas, 4⟩ is not a relation;
{⟨Thomas Aquinas, 4⟩} is a relation;
{{⟨Thomas Aquinas, 4⟩}} is not a relation.
The last example of the three is not a relation because the only member of the set is itself a set, which is not an ordered couple.
(quoting Suppes 211)
If R is a binary relation, then the domain of R – in symbols: D(R) – is the set of all things x such that, for some y, ⟨x, y⟩ ∈ R. Thus if M is the | relation which consists of all couples ⟨x, y⟩ such that x is the mother of y, then the domain of M is the set of all women who are not childless. If
R1 = {⟨Λ, Plato⟩, ⟨Jane Austen, 101⟩, ⟨the youngest bride in Tibet, Richelieu⟩},
then
D(R1) = {Λ, Jane Austen, the youngest bride in Tibet}.
The counterdomain (or converse domain) of a binary relation R (in symbols : C(R)) is the set of all things y such that, for some x, ⟨x, y⟩ ∈ R. The counterdomain of the relation M considered just above is the set of all people – since everyone has a mother. If B is the relation which consists of all couples ⟨x, y⟩ such that x is the brother of y, then the domain of B is the set of all men who have at least one brother or sister, and the counterdomain is the set of all people who have at least one brother. We have for the relation R1 defined above:
C(R1) = {Plato, 101, Richelieu}.
The field of a binary relation R (in symbols: F(R)) is the union of its domain and its counterdomain. Thus z belongs to the field of a binary relation R if and only if either ⟨x, z⟩ ∈ R for some x or ⟨z, y⟩ ∈ R for some y. The field of the relation B considered just above is the set of all people who belong to families containing at least two children, at least one of which is male. As another example,
F(R1) = {Λ, Jane Austen, the youngest bride in Tibet, Plato, 101, Richelieu}.
(quoting Suppes 212)
§10.3 Properties of Binary Relations
There are a number of sorts of binary relations. If a relation that relates things to themselves holds for all things, then it is reflexive, and if it holds for no things, then it is irreflexive.
A (binary) relation R is reflexive in the set A if for every x in A, xRx (i.e., ⟨x, x⟩ ∈ R):
R reflexive in A ↔ (x)(x ∈ A → xRx).
A relation R is irreflexive in the set A if, for every x in A it is not the case that xRx:
R irreflexive in A ↔ (x)(x ∈ A → –(xRx)).
When there is a two-place relation, if the order of the relation can be switched for all substitutions, then it is symmetric. If for all substitutions it cannot be switched and still be true, then it is asymmetric.
A relation R is symmetric in the set A if for every x and y in A, whenever xRy, then yRx:
R symmetric in A ↔ (x)(y)[x ∈ A & y ∈ A & xRy → yRx].
A relation R is asymmetric in the set A if, for every x and y in A, whenever xRy, then it is not the case yRx:
R asymmetric in A ↔ (x)(y)[x ∈ A & y ∈ A & xRy → –(yRx)].
Now ≤ is not symmetric, because although 3 ≤ 3 and 3 ≤ 3, that invertibility does not hold for 2 ≤ 3. It is also not antisymmetric, because although the invertibility does not hold in most cases, it does for 3 ≤ 3. However, it is always symmetric under the condition that both terms are equal to one another. It is thus antisymmetric.
A relation R is antisymmetric in the set A if for every x and y in A, whenever xRy and yRx, then x=y:
R antisymmetric in A ↔ (x)(y)[x ∈ A & y ∈ A & xRy & yRx → x=y].
A relation can also be neither symmetric, asymmetric, nor antisymmetric. One example is the love relation. It is not symmetric, because not every person loves the people who love them. It is also not asymmetric, because there are many cases of mutual love. It is furthermore not antisymmetric, because it is not the case that the only people who are in love are those who love themselves.
A relation is transitive if it carries over through a middle term.
A relation R is transitive in the set A if, for every x, y, and z in A, whenever xRy and yRz, then xRz:
R transitive in A ↔ (x)(y)(z)[x ∈ A & y ∈ A & z ∈ A & xRy & yRz → xRz].
A relation is intransitive if for no things that it relates does the relation of a first item to a second one along with and the second one to a third imply that the relation holds as well for the first to the third. Another idea is the difference between intransitive and non-transitive.
A relation R is intransitive in the set A if for every x, y, and z in A, whenever xRy and yRz, then it is not the case that xRz:
R intransitive in
A ↔ (x)(y)(z)[x ∈ A & y ∈ A & z ∈ A & xRy & yRz → –(xRz)].
Note that a relation can be non-transitive without being intransitive, because for some relations, there is transitivity between some triplets of terms but not between others.
A relation is connected if it relates any member to any other member.
A relation R is connected in the set A if for every x and y in A, whenever x ≠ y, then xRy or yRx:
R connected in A ↔ (x)(y)(x ∈ A & y ∈ A & x ≠ y → xRy ∨ yRx).
A relation is strongly connected if it holds for any member with any other member and as well with any member and itself.
A relation R is strongly connected in the set A if for every x and y in A, either xRy or yRx:
R strongly connected in A ↔ (x)(y)(x ∈ A & y ∈ A → xRy ∨ yRx).
§10.4 Equivalence Relations
A relation is equivalent if it is reflexive (it holds for some object in relation to itself), symmetric (when it holds for one object to a second, it also holds from the second to the first), and transitive (when it holds for one object to a second, and a second to a third, it as well holds for the first object to the third one). Within a set of members, certain groupings can be formed on the basis of equivalent relations holding among all the members of a particular subgrouping. These are equivalence classes. Forming such classes can allow us to reduce a large set of data to a more manageable size, when the differences between the members within an equivalence class are irrelevant to the particular analysis being conducted.
A relation which is reflexive, symmetric, and transitive in the set A is an equivalence relation in A. The relation of identity is an equivalence relation.
(218)
§10.5 Ordering Relations
There are a variety of what are called “ordering relations.” A relation is:
quasi-ordering only if it is both reflexive and transitive;
partial ordering only if is reflexive, antisymmetric, and transitive;
simple ordering only if it is reflexive, antisymmetric, transitive, and connected;
strict partial ordering only if it is asymmetric and transitive;
strict simple ordering only if it is asymmetric, transitive, and connected;
weak ordering only if it is transitive and strongly connected.
§10.6 Operations on Relations
Relations can be understood as those subsets they produce when they relate members of some set.
Universal Relation. We find every possible coupling of the members of one set with those same members. The resulting set is that of the universal relation. All other relations as sets will be subsets of the universal relation’s set. Formally:
If V is any domain of individuals, then by the universal relation over V we mean the set of all ordered couples (x, y) where x ∈ V and y ∈ V, that is, the Cartesian product V × V.
(Suppes 225)
Empty set relation. It is the relation whose corresponding set is empty.
The empty set Λ is the relation which never holds. If R, for instance, is the relation which holds between x and y if and only if x is the mother of y, and y is the mother of x, then R = Λ, for no one is his own grandmother.
(225)
With these notions in mind, we can then see how we apply the normal operations on sets to our relations as sets.
Intersection of relations.
if R and S are relations, then R ∩ S is the relation which consists of the intersection of R and S: i.e., x(R ∩ S)y if and only if both xRy and xSy.
(Suppes 225)
Union of relations.
R ∪ S is the union of R and S: x(R ∪ S)y if and only if either xRy or xSy.
(Suppes 225)
Difference of Relations.
R ~ S is the relation such that x(R ~ S)y if and only if xRy and not xSy.
(Suppes 225)
Subrelation.
If R ⊆ S we call R a subrelation of S. Thus brotherhood is a subrelation of siblinghood; for whenever x is a brother of y, then x is a sibling of y. Every relation is a subrelation of the universal relation over its own field.
(Suppes 226)
There are also operations for binary relations that are not based on these set operators.
Converse of a relation.
The converse of a relation R
is the relation such that, for all x and y, xRy if and only if yRx. Thus the converse of a relation is obtained simply by reversing the order of all the ordered couples which constitute it.
(Suppes 226)
Relative product of two relations. This operation combines two separate relations by finding ones where the second member of one couple (in the first relation) is the same as the first member of the second couple (in the other relation). From these pairings of couples, you make a new couple that takes the first member of the first couple and the second member of the second couple. Being an aunt is an example, with you and your aunt being the end-terms of separate relations (you being the child of your parent, and your parent being the sibling of your aunt), with your parent being the middle term that gets excluded.
If R and S are binary relations, then by the relative product of R and S (in symbols: R/S) we mean the relation which holds between x and y if and only if there exists a z such that R holds between x and z, and S holds between z and y. Symbolically,
x R/S y ↔ (∃z) (xRz & zSy).
If xPy means that x is a parent of y, and xSy means that x is a sister of y, then x(S/P)y means that there is a z such that x is a sister of z and z is a parent of y, and hence such that x is an aunt of y.
(Suppes 226)
Furthermore, the relative product relation can be a reiteration of the same relation.
If xPy when x is a parent of y, then x(P/P)y if and only if x is a grandparent of y; x[(P/P)/P]y if and only if x is a great-grandparent of y; and so on.
(Suppes 226)
Ch. 11. Functions
§11.1 Definition
A function is a binary relation that relates to each element of its domain a unique element of its counterdomain:
A function R is a binary relation such that if xRy and xRz then y = z.
Consider the following cases of binary relations:
R1 = {<1, 2>, <Madison, Pinckney>}
R2 = {<1, 2>, <1, 3>, <Plato, Aristotle>}
R1 is a function, but R2 is not, because in R2, the number 1 is related to two members of the counterdomain, namely, 2 and 3, and thus the member of the domain is not related to a unique member of the counterdomain. We often used lowercase letters to symbolize functions, and they normally take the form f(x) = [something]. The domain of a function is called the domain of definition and the counterdomain, the range of values. A function is sometimes said to map its domain onto its range, and thus a function is also called a mapping. And when x is an element of the domain of f, then f(x) is the image of x. A binary operation on the set A is a function whose domain is A × A and whose range is a subset of A. For example, N = the positive integers and + is the binary operation of addition applied to positive integers. In this case, + is a binary operation from N × N to N. The range of + is N ~ {1}, as no two positive integers add up to one.
§11.2 Operations on Functions
The converse of a function has for its pairings of outcomes the same as those of the function except with the order of the couples’ members inverted. Note two things. {1} A function can assign many different members of the domain to the same member of the counterdomain. {2} A function cannot assign the same member of the domain to more than one member of the counter domain. Thus the converse of a function may not itself be a function, if the original function assigned more than one member of the domain to the same member of the counterdomain. However, when the converse of a function is in fact itself a function then we call it the inverse and we note it with a superscript ‘–1’. When solving for an inverse function, there are two important principles:
For every x in the domain of f
(I) f–1(f(x)) = x,
and for every x in the range of f
(II) f(f–1(x)) = x.
And a simple, but in some cases flawed, strategy for solving for the inverse has three phases: (i) Substitute ‘f–1(x)’ for ‘x’; (ii) Apply (II);(iii) Solve the resulting equation for ‘f–1(x)’.
Suppes, Patrick. Introduction to Logic. New York: Van Nostrand Reinhold / Litton Educational, 1957.
.
.jpeg)
