by Corry Shores

[**Search Blog Here**. Index-tags are found on the bottom of the left column.]

[Logic & Semantics, Entry Directory]

[Patrick Suppes, entry directory]

[Suppes,* Introduction to Logic*, entry directory]

[The following collects the brief summaries for certain sections of Patrick Suppes’ *Introduction to Logic*, and in some cases Suppes’ examples are replicated too. All the following is Suppes’ work, boiled down for quick reference or review.]

The entry directory without the brief summaries can be found here:

Collected Brief Summaries of

Patrick Suppes

* Introduction to Logic*

Ch. 3 Symbolizing Everyday Language

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.

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.

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 *& *I**x*).

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

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*.

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.

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.

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.

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*)* ≠* Λ.

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(allAareB) andB∩C= Λ, (i.e., noBareC)

A∩B= Λ

A⊆B; “for to say thatAis a subset ofBmeans that no part ofAlies outsideB” (197).

A∩B= Λ andA⊆B.

Some

AareB:A∩B≠ Λ. [x means the regions is not empty.]

Some

Aare eitherBorC:A∩ (B∪C) ≠ Λ

A∪B≠ Λ (Something is eitherAorB)A∪ ~C≠ Λ (Something is eitherAor notC)

A∩C≠ Λ (SomeAareC)C⊆B(AllCareB)

Checking syllogisms.

(1) No

BareC(2) AllAareB

(3) Therefore noAareC[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

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:

⟨

x,_{1}x, ...,_{2}x⟩ = ⟨⟨_{n}x,_{1}x, ...,_{2}x⟩,_{n-1}x⟩_{n}

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⟩}

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

lovingis the set of ordered couples ⟨x,y⟩ such thatxlovesy. The relation ofbeing less thanis the set of all ordered couples ⟨x,y⟩ of numbers such that, for some positive numberz,

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

nthings is a set of orderedn-tuples.

A relation is called ‘

n-ary’ if its members aren-tuples. For the special casesn= 2 andn= 3 we use special names, speaking of ‘binary’ and ‘ternary’ relations.Since a relation is a

setof orderedn-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

LMaryto 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

Ris a binary relation, then the domain ofR –in symbols:D(R) – is the set of all thingsxsuch that, for somey, ⟨x,y⟩ ∈R. Thus ifMis the | relation which consists of all couples ⟨x,y⟩ such thatxis the mother ofy, then the domain ofMis the set of all women who are not childless. If

R_{1 }= {⟨Λ, Plato⟩, ⟨Jane Austen, 101⟩, ⟨the youngest bride in Tibet, Richelieu⟩},then

D(R_{1}) = {Λ, Jane Austen, the youngest bride in Tibet}.The

counterdomain(orconverse domain) of a binary relationR(in symbols :C(R)) is the set of all thingsysuch that, for somex, ⟨x,y⟩ ∈R. The counterdomain of the relationMconsidered just above is the set of all people – since everyone has a mother. IfBis the relation which consists of all couples ⟨x,y⟩ such thatxis the brother ofy, then the domain ofBis 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 relationR_{1 }defined above:

C(R_{1}) = {Plato, 101, Richelieu}.The

fieldof a binary relationR(in symbols:F(R)) is the union of its domain and its counterdomain. Thuszbelongs to the field of a binary relationRif and only if either ⟨x,z⟩ ∈Rfor somexor ⟨z,y⟩ ∈Rfor somey. The field of the relationBconsidered 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(R_{1}) = {Λ, 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

Risreflexive in the set Aif for everyxinA,xRx(i.e., ⟨x,x⟩ ∈R):

Rreflexive inA↔ (x)(x∈A→xRx).

A relation

Risirreflexive in the set Aif, for everyxinAit is not the case thatxRx:

Rirreflexive inA↔ (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

Rissymmetric in the set Aif for everyxandyinA, wheneverxRy, thenyRx:

Rsymmetric inA↔ (x)(y)[x∈A&y∈A&xRy→yRx].A relation

Risasymmetric in the set Aif, for everyxandyinA, wheneverxRy, then it is not the caseyRx:

Rasymmetric inA↔ (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

Risantisymmetric in the set Aif for everyxandyinA, wheneverxRyandyRx, thenx=y:

Rantisymmetric inA↔ (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

Ristransitive in the set Aif, for everyx,y, andzinA, wheneverxRyandyRz, thenxRz:

Rtransitive inA↔ (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

Risintransitive in the set Aif for everyx,y, andzinA, wheneverxRyandyRz, then it is not the case thatxRz:

Rintransitive 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

Risconnected in the set Aif for everyxandyinA, wheneverx≠y, thenxRyoryRx:

Rconnected inA↔(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

Ris strongly connected in the setAif for everyxandyinA, eitherxRyoryRx:

Rstrongly connected inA↔(x)(y)(x∈A&y∈A→xRy∨yRx).

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 relationin A. The relation of identity is an equivalence relation.(218)

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.

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

Vis any domain of individuals, then by the universal relation overVwe mean the set of all ordered couples (x,y) wherex∈Vandy∈V, that is, the Cartesian productV×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 betweenxandyif and only ifxis the mother ofy, andyis the mother ofx, thenR= Λ, 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

RandSare relations, thenR∩Sis the relation which consists of the intersection ofRandS: i.e.,x(R∩S)yif and only if bothxRyandxSy.(Suppes 225)

*Union of relations*.

R∪Sis the union ofRandS:x(R∪S)yif and only if eitherxRyorxSy.(Suppes 225)

*Difference of Relations*.

R~Sis the relation such thatx(R~S)yif and only ifxRyand notxSy.(Suppes 225)

*Subrelation*.

If

R⊆Swe callRa subrelation ofS. Thus brotherhood is a subrelation of siblinghood; for wheneverxis a brother ofy, thenxis a sibling ofy. 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

xandy,xRyif and only ifyRx. 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

RandSare binary relations, then by the relative product ofRandS(in symbols:R/S) we mean the relation which holds betweenxandyif and only if there exists azsuch thatRholds betweenxandz, andSholds betweenzandy. Symbolically,

xR/S y↔ (∃z) (xRz&zSy).If

xPymeans thatxis a parent ofy, andxSymeans thatxis a sister ofy, thenx(S/P)ymeans that there is azsuch thatxis a sister ofzandzis a parent ofy, and hence such thatxis an aunt ofy.(Suppes 226)

Furthermore, the relative product relation can be a reiteration of the same relation.

If

xPywhenxis a parent ofy, thenx(P/P)yif and only ifxis a grandparent ofy;x[(P/P)/P]yif and only ifxis a great-grandparent ofy; and so on.(Suppes 226)

Ch. 11. Functions

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:

*R*_{1 }= {<1, 2>, <Madison, Pinckney>}

*R*_{2 }= {<1, 2>, <1, 3>, <Plato, Aristotle>}

*R*_{1 }is a function, but *R*_{2 }is not, because in *R*_{2}, 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.

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.

.

.

## No comments:

## Post a Comment