Chapter 2

Introduction to the

Rudimentary Concepts of Sets,

Syllogistic Logic,

and Quantification

§ 2.1 BASIC NOTATION AND CONCEPTS FOR SETS.

The theory of sets was developed by many different mathematicians, but reached a rigorous level by the nineteenth and early twentieth centuries through the work of Boole, Cantor, Zermelo, Fraenkel, Dedekind, Frege, Zorn, von Neumann, etc. It is the one of the basic building blocks and a foundation of higher level mathematics and gives the mathematician the power to communicate abstract ideas and thoughts succinctly, clearly, and in an organised manner. There are many different approaches to an introduction to sets. One approach is to intuitively introduce the subject; another is to rigorous introduce the subject axiomatically. We shall discuss the subject using a bit of both manners of introduction.

A set and an element are undefined concepts much that same way as point, line, and plane are in Euclidean geometry. However, we can intuit an understanding of a set by thinking about a well defined group or collection of well defined objects. Any object in the set is called an element of the set and is said to be a member of the set or the element belongs to the set. We say that a set consists of it elements or a set contains its elements. So, in terms of a hierarchy, we should consider the objects as secondary to the set - - the set is the grouping and the elements the individuals much as matter is made up of elements. However, for a set to be well defined must exist within a realm that has been specified. That specification of all possible elements to be discussed is called the universe (or domain of discourse). The universe is also an undefined concept in so far as we axiomatically allow for its existence (e.g.: a premise of our discussion of sets is always that a well defined universe has been specified). No discussion of sets can properly take place before the universe has been defined. If one discussed a set without specifying what the universe is, then ambiguity can enter into the discussion and the theory collapses.

Suppose a well defined universe has been defined.[1] Examples of sets are the set of all Morehouse students enrolled in 1996; the set of all real numbers greater than or equal to 5 but less than 8; the set consisting of the multiplicative identity (that is to say the set consisting of 1); the set of protons in a carbon atom; the set of rational numbers; the set of all U. S. presidents who served in the twentieth century; and, the set of pens produced by Parker pens on the fifth of January 2002 A.D.. Examples of aggregates that are not sets since there is ambiguity, inconsistency, opinion, subjectivity, or such nebulous understanding of the concept that rigor cannot be achieved include the “set” of all my hopes and dreams, the “set” of all good presidents who served in the twentieth century; the “set” of all numbers; the “set” of all sets; and, the “set” of all Morehouse men.

An example of the ambiguity that arises with the concept of set is when one forgets to specify a universe. Thus, when described, the “set” is not well defined because a full accounting of elements has not preceded the discussion. Let us say we are in an arithmetic class and the instructor asks us to describe the set of numbers between 1 and 4. Many children would say, “2 and 3.” Others might say, “2, 1.5, 2.5, and so forth.” Others might express the numbers as fractions. Very few would consider that , p, e, etc. could be in the ‘set.’ The ambiguity arises because the universe has not been specified and the term “number” is not a singular concept in this context (indeed, how many children would realise that is a number (albeit complex))? So we can see that specification of a universe is important. Note that the universe, since it is a collection of elements that will be discussed, is a set. It is in our context the “biggest” set (big, large, etc. are very dangerous words when applied to sets - -be careful the term is not well defined; but, it should be intuitively appealing and can do no harm so long as one realises that “big” like tall is subjective).

Now let us move on to some basic definitions. In general, we will use lower case English letters to signify elements, upper case English letters to signify sets, and U to signify the special set, the universe.

Let U be a pre-specified well defined universe. If a is an element of the set S, then we shall write a Î A. The negation of this statement is, “a is not an element of the set S, and we shall write a Ï S.[2] So, the symbol “Δ is read as “belongs to,” “is in,” or “is a member of.” It is standard notation to use braces to enclose elements to signify a set. So, if one wishes to refer to the set consisting of the elements one, two, and three, then one would write, {1, 2, 3}. Also, it is standard notation to write a set with braces, use a variable to denote a generalised element of a set, and then describe the set thereafter based on axioms or previous definitions. We shall see an example of that later.

Example: Let U = {1, 2, 3, 4, 5}. Let A = {1, 3, 5}. Thus, 1 Î A, 2 Ï A, etc. Note every element in A must be in the universe; so, for the sake of this particular universe one could not discuss standard multiplication since , but 6 Ï U so it does not exist.

There are some special standard sets and symbols for them to denote sets that we use often. The sets under discussion are formulated from the real line (are either points of the line or are generalisations of the line. You knowledge of high school geometry will, no doubt, be of use in making concrete these abstract ideas that follow. As previously stated in the text, one of the most basic of sets is called the natural numbers. It has been with us since antiquity, and we will denote it as or IN = {1, 2, 3, 4, . . .} where the set never ends and includes all the whole or counting numbers that the student learnt in kindergarten or before. We shall denote the set of natural numbers along with zero as the set ^* = _À = {0, 1, 2, 3, 4, . . .}.[3] We shall denote the set {1} as ₁, the set {1, 2} as ₂, the set {1, 2, 3} as ₃ , and so forth so that

_k = {1, 2, 3, 4, . . ., (k - 1), k}. This definition is known as a recursive definition since we are inductively defining a myriad of sets at once; the three dots signify that the enumeration of the elements continues.[4] Likewise, we shall denote the set {0, 1} as , the set {0, 1, 2} as ,

the set {0, 1, 2, 3} as , and so forth so that = {0, 1, 2, 3, . . ., (p - 1), p}.

Another of the most basic of sets is called the integers. It has been with us quite a long time (the people of India invented the symbol of zero and were really the first to use it and negative numbers (in fact the number system that we use is of course the Hindu-Arabic number system since the Hindus created it, the Arabs adopted it and brought it west); it should also be noted that the Mayans also invented a zero independent of the Hindus). We will denote the set of integers as , ZZ , or Z such that ZZ = {0, 1, -1, 2, -2, 3, -3, 4, -4, . . .}.

Generalising from the integers, we have the rational numbers. The rationals are denoted as or Q such that = {x | x = where a Î ZZ , b Î ZZ , Ù b ¹ 0 }. This statement is read as the rationals are the set consisting of elements x such that x is equal to a divided by b where a is an integer, b is an integer, and b is not zero. Thus, the symbol “|” in this context means such that. Indeed, as I type this opus I am getting very tired of writing the words, “such that,” (I suppose it is an occupational hazard, I think we mathematicians are a lazy lot so we have invented many symbols to create a short hand to ease the amount of words necessary to communicate). A more general symbol for such that is, “',” and will be used liberally from this point onward. Typically it is not used in the notation inside the braces for a set only as a free-standing symbol. However, it is not incorrect to use it. Therefore, it is technically correct to write

= {x ' x = where a Î ZZ , b Î ZZ , Ù b ¹ 0 }.

We can simplify the definition of the rationals so that it does not have to depend solely on the integers. Note the definition = {x : x = where a Î ZZ , b Î } is logically equivalent to the previous definition of the rationals and in this case the colon means such that (which is the third of the standard notations for such that).

Generalising from the rational numbers, we have the real numbers. However, this is axiomatically executable, but practically most difficult to do in a basic introduction to sets. Therefore, we shall consider the set of reals from a geometric standpoint. The set of real numbers are denoted as , IR , or R such that = {x | x is a point on the line}. One could also define the reals from a sequential (or decimal) perspective by defining the reals to be

= {x | x is a number where x is an integer followed by a decimal and then a sequence of digits where each digit belongs to the set {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}}. Yes, this is a rather cumbersome definition, but one can prove that the sequential definition and the geometric definitions are equivalent. One other way to write is by writing (-¥ , ¥). The symbols ¥ and -¥ are not numbers, they simply represent that the line goes on ad infinitum to the left in the case of -¥ and to the right in the case of ¥.

Note, gentle reader that I skipped another standard set; that is because in a basic introduction to sets it is oft easier to ‘jump’ up to the reals, then return back to describe another set. That set is, of course, the irrationals. By the very nature of its name one can understand that it is composed of elements that are not rational. But, recall our discussion of the need for defining a domain of discourse or a universe. To say what something is not presupposes that everything has been specified! Putting it another way saying that the irrationals are numbers that are not rational is wrong since is a number that is not rational; but, it is also not irrational. Thus, the set of irrational numbers will be denoted as II , I , or I such that II = {x | x Î , x Ï Q}. So, the irrationals are the set of all real numbers that are not rational.

Note that this is a definition of something such that it is defined by what it is not. This definition by negation is oft quite useful; but one must understand what the first thing is (a real number) and the second thing is (a rational number) in order to understand what the third thing is (an irrational number) by way of what it isn’t.

Constructing sets from this perspective leaves us with the feeling that all is known and specified previously, but consider people before they thought of these sets. Consider the man or woman who first thought of these sets. Is it not rather astonishing to think that such was not known nor conceived, but someone thought of these ideas first? A facile way of considering the wonderful experience it must have been is by specify a set that is not contained within the set of reals. Laying aside the important principle of consideration of the specification of a universe for the moment, let us look at the idea of set from a construction standpoint. Note that we did this by specifying IN then ZZ then Q then IR . We deviated from it when we specified II .

Let us do it again. Define C or C to be the complex numbers such that

C = { x | x = a + bi where a Î R , b Î R , Ù i = }. Note that the complex numbers are really the plane (the horizontal axis consists of all points corresponding to the real part of the complex number and the vertical axis consists of all points corresponding to the i (‘imaginary’) part). So, why do so many people call complex number imaginary numbers when they correspond to things not so imagined but real? Indeed, if one argues that the reals correspond to real things and the complex numbers are ‘not real’ then why are both simply concepts corresponding to geometric forms (which recall are axiomatically given [point, line, and plane]). So, how real are the reals and imaginary are the complex numbers? But, I digress.[5]

Let U = N. Specify A = {x | 5 < x £ 11} in list form. Note the solution to this would be

A = {6, 7, 8, 9, 10, 11} . However, let U = R . Specify A = {x | 5 < x £ 11} in list form. Note one cannot produce a solution to this since there is no way to list out all the elements.

So, we can use the same symbol for two sets that are different (even though they seem quite the same, the difference in the universes made radical difference in the sets). Let us consider another example.

Let U = R . Consider B = {x | 5 < x £ 11, where x Î }. Consider C = {x | 5 < x £ 11, where x Î }. Note 6 Î B; 6 Î C; but, Î C; whereas, Ï B. So, what does it mean for two sets to be the same?

Let U be a well defined universe, A, B, C, and D be sets of elements from the well defined universe. The statement A = B means that every element of A is in B and every element of B is in A. There is a weaker notion that equality of sets. That notion is the idea of subset. A set C is a subset of D if for each element x in C, x is in D. When C is a subset of D we say D is a superset of C. C is a subset of D is denoted as C Í D or D Ê C (the same notation means D is a superset of C).[6] There is another notion between the idea of subset and equality, which is the notion of proper subsethood. A set B is said to be a proper subset of C if B Í C and B ¹ C. Denote B is a proper subset of C as B Ì C.[7] In rather a circular manner (granted) we can return to the definition of equality of two sets and state that two set A and B are equal, A = B, if and only if A Í B Ù B Í A.

Let U = . Let A = {x | 5 < x £ 11}, B = {x | 5 < x £ 9}, C = {x | 7 £ x £ 11}, and

D = {x | 5 < x < 12}. Note the following: A = {6, 7, 8, 9, 10, 11}; B = {6, 7, 8, 9};

C = {7, 8, 9 , 10, 11}; and, D = {6, 7, 8, 9, 10, 11} .

Note every set is a subset of itself. Note every set is not a proper subset of itself. Note A = D. Note B Í A. Note B Í D. Note C Í A. Note C Í D. Please note B Ú C since 6 Î B and 6 Ï C.

Finally, please note C Ú B since 11 Î C and 11 Ï B.

There are ten basic axioms for set theory (see chapter 3), we shall introduce and use only one of them in this course. It is the axiom of null which states there exists a set with no elements, call it Æ. Note that Æ is a special symbol. Do not use {} or any other creative use of notation to reference Æ, just use Æ.

Now let us return to U = , A = {x | 5 < x £ 11}, B = {x | 5 < x £ 9},

C = {x | 7 £ x £ 11}, and D = {x | 5 < x < 12}.

Note that Æ Í A (indeed Æ Í B, Æ Í C, and Æ Í D)! Note this statement illustrates the reasonableness of the truth table for implication in chapter one of (F Þ T) is true since the statement every element of null is an element of the set A since there are no elements in null; hence, a counterexample cannot be constructed to challenge the validity of Æ Í A. It is an example of a vacuously true statement.

Next let us define the complement of a set A, usually denoted as A¢. It is the set of all elements in the universe that are not in A.[8] So, A¢ = {x | x Î U, but x Ï A} = {x | x Ï A} when it is understood the universe has been defined. Other symbols that mean the complement of the set A are A^C, `A, and U - A. The U - A symbol is quite representative since we are subtracting for the universe all elements that were in A. This notation gives rise to the concept of the relative complement of two sets. The set B relative complement to the set A, denoted as B – A or B \ A,

is the set of all elements of B that are not in A.

Let U = {x | 5 < x £ 11}, A = {x | 7 £ x £ 10}, B = {x | 5 < x < 8}, C = {x | 7 £ x < 8},

and D = {x | 5 < x £ 10}.

Note A¢ = {x | 5 < x < 7 Ú 10 < x £ 11}. Note that B - A = {x | 5 < x < 7}.

Note that A - B = {x | 8 £ x £ 10}.

Also note that ([y Î C Þ y Î B] so C Í B) Ù ([y Î C Þ y Î A] thus, C Í A)! Further notice the set C is very interesting - - it contains all the elements that are contained in both A and B. This set is called the intersection of the sets A and B and is denoted as A Ç B.

Now, suppose the two sets have no elements in common, then we say they are disjoint. It is symbolised by A Ç B = Æ.

Note that ([z Î A Þ z Î D] hence A Í D) Ù ([z Î B Þ z Î D] Þ B Í D). Further note that D is also quite fascinating - - it contains all the elements that are contained in A or B. This set is called the union of the sets A and B and is denoted as A È B.

Let U = R, A = {x | 7 £ x £ 10}, B = {x | 5 < x < 8}, C = {x | 7 £ x < 8}, and

D = {x | 5 < x £ 10}. Note that an alternate way of expressing subsets of the reals is with another form of notation.

A = [7, 10] and A is called an interval.

B = (5, 8) and B is called a segment.

C = [7, 8) whilst D = (5, 10] and both C & D are called a half-segment or a half-interval.

Note A¢ = {x | x < 7 Ú 10 < x }.

So, in the interval or segment notation A¢ = (-¥, 7) È (10, ¥).

Note that A \ C = [8, 10]; C \ A = {7} which is expressed as [7, 7]; and, A \ D = Æ.

Another import kind of set is the power set of a set denoted as P(A) where A is the set. It is the set of all subsets of a set. For example, suppose U = N and A = {1, 2, 3} whilst B = {4, 5}.

P(A) = {Æ, {1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3}, {1, 2, 3}}. P(B) = {Æ, {4}, {5}, {4, 5}}.

Note that though A and B are sets of elements in U, the elements of P(A) and P(B) are not. They are elements of another universe, namely, P(U) since P(U) contains all the subsets of N.

Finally note the similarity of the nomenclature and notation between sets and logic.

Meaning	Logic	Meaning	Set Theory
Not P	ØP	Not A (A complement)	A¢
P or Q	P Ú Q	A or B	A È B
P and Q	P Ù Q	A and B	A Ç B
P implies Q	P Þ Q	A is a subset of B	A Í B
P is logically equivalent to Q	P Û Q P º Q	A is equal to B	A = B

Table 2.1.1

Notational and Definitional Similarity between Logic and Set Theory

It is no coincidence that the symbols are quite similar. Note also that both the symbols from set theory and logic are similar to the inequality symbols of comparison of points for the real line; again no coincidence. Noting these similarities should help you remember, learn, and understand the symbols for sets.

There are basic, moderate, and complex claims about sets which you will prove or disprove in Math 255 (Set Theory). Some of the following claims are true, some are false. It might be worth your while to try to establish some intuitive feel about sets by considering these claims and determining if they are true or false.

Basic Assumptions: Let U be a well defined universe and A, B, and C be sets containing elements in the universe.

Claim 1: A Ì B, B Ì C Þ A Ì C. Claim 8: A Ì B, B É C Þ A = C.

Claim 2: Æ Ì A. Claim 9: Æ Ì U.

Claim 3: A Í B, B Í C Þ A Í C. Claim 10: A Í B, B Ê C Þ A = C.

Claim 4: Æ Í A. Claim 11: Æ Í U.

Claim 5: A Í B, B Í A Þ A = B. Claim 12: A Í Æ Þ A = Æ.

Claim 6: Æ Í Æ. Claim 13: U Í U.

Claim 7: Æ Ì Æ.

§ 2.1 EXERCISES.

1. Determine which of the following symbols: <, >, ³, £, Þ, Û, =, Æ, Ç, È, É, Ê, Ë, Ì, Í, Î, Ï, or ¹ should properly be placed between the following in column A and column B :

Column A Column B

A. {1, 2, 3, 4} and {x | x is a divisor of 24} ' U = N

B. 6, 7 and {x | x is a root of x² -13x + 42 = 0} ' U = N

C. {6, 7} and {x | x is a root of x² -13x + 42 = 0} ' U = N

D. 0 and {x | x is a root of x³ -6x² + 11x = 6} ' U = N

E. {1, 2, 3} and {x | x is a root of x³ -6x² + 11x = 6} ' U = N

F. Æ and {Æ, {1}} ' U = P(N)

G. A and A^C S. N and I EE. .33 and

H. Q and C T. Z and I FF. p and Z

I. N and C U. Q and I

J. I and C V. Z and Q

K. R and C W. N and Q

L. Z and C X. N and Z

M. Q and R Y. p and N

N. Z and R Z. p and 3.1415926535897932384626433832795

O. I and R AA. p and Q

P. C and R BB. p and R

Q. Z and I CC. p and C

R. Q and I DD. and 1

3. Write the following sets in set-builder form or with standard notation (where U = C) :

A. {1, 2, 3, 4, 5}

B. {1, 2, 3, 4, 6, 8, 12, 24}

C. {-3, -2, -1, 0, 1, 2, 3, 4}

D. The set of integers between -7 and 5.

E. The set of real numbers less than 4.

F. The set of natural numbers less than 4

G. The set of real numbers that are solutions to the equation of x³ -6x² + 11x = 6

H. The set of real numbers that are solutions to the equation of x⁴ -16 = 0

I. The set of real numbers that are solutions to the equation of x² + 16 = 0

J. The set of integers that are solutions to the equation of x³ -6x² + 11x = 0

K. The set of natural numbers that are solutions to the equation of x² + 7x + 10 = 0

L. The set of complex numbers that are solutions to the equation of x⁴ + 16 = 0

4. Write the following sets in list form or with standard notation (where U = R) :

A. {x | x is a zero of the polynomial x³ -6x² + 11x = 6}

B. {x | x < 1 Ù x > 3}

C. {x | x < 1 Ù x £ 3}

D. {x | x < 1 Ú x > 3}

E. {x | x < 1 Ú x £ 3}

F. The set of integers between -7 and 5.

G. The set of real numbers less than 4.

H. The set of natural numbers less than 4

I. The set of real numbers that are solutions to the equation of x³ -6x² + 11x = 6

J. The set of real numbers that are solutions to the equation of x⁴ -16 = 0

K. The set of real numbers that are solutions to the equation of x² + 16 = 0

L. The set of integers that are solutions to the equation of x³ -6x² + 11x = 0

M. The set of natural numbers that are solutions to the equation of x² + 7x + 10 = 0

5. Let U = , A = {x | 1 < x £ 11}, B = {x | 2 £ x < 9}, C = {x | x £ 11}, D = {x | 4 < x},

E = {x | 1 £ x £ 11}, and F = {x | 4 < x < 9}.

A. Find A Ç B B. Find B Ç C C. Find C Ç D

D. Find A Ç E E. Find B Ç F F. Find C Ç D È A

G. Find (A Ç E)^C È D H. Find (B Ç F) Ç A I. Find (C Ç D È A)^C Ç E

J. Find A Ç C È F K. Find (A Ç C) È F L. Find A Ç (C È F)

M. Find (A Ç C) È (A Ç F) N. Find B \ F O. Find B Ç D Ç F

P. Find A \ E Q. Find E \ A R. Find (A \ E) È (E \ A)

S. Find (A \ E) Ç (E \ A) T. Find (A Ç C)^C È F U. Find (A Ç (C È F))^C Ç C

V. Find (A Ç C)^C È (A Ç C) W. Find (A Ç E)^C È D X. Find B Ç D Ç E Ç F

Y. Find A Ç (C È A) Ç F Z. Find A Ç (C È A) - F AA. Find (A È B È C È D È E)

6. Let U = R , A = (1, 11], B = [2, 9), C = (-¥, 11], D = {x | 4 < x}, E = [1, 11], and F = (4, 9).

Express you solution in interval or segment notation.

A. Find A Ç B B. Find B Ç C C. Find C Ç D

D. Find A Ç E E. Find B Ç F F. Find C Ç D È A

G. Find (A Ç E)^C È D H. Find (B Ç F) Ç A I. Find (C Ç D È A)^C Ç E

J. Find A Ç C È F K. Find (A Ç C) È F L. Find A Ç (C È F)

M. Find (A Ç C) È (A Ç F) N. Find B \ F O. Find B Ç D Ç F

P. Find A \ E Q. Find E \ A R. Find (A \ E) È (E \ A)

S. Find (A \ E) Ç (E \ A) T. Find (A Ç C)^C È F U. Find (A Ç (C È F))^C Ç C

V. Find (A Ç C)^C È (A Ç C) W. Find (A Ç E)^C È D X. Find B Ç D Ç E Ç F

Y. Find A Ç (C È A) Ç F Z. Find A Ç (C È A) - F AA. Find (A È B È C È D È E)

7. Let U = , A = , B = , C = , and D = .

A. Find A Ç B B. Find B Ç C C. Find C Ç D

D. Find A Ç B^C E. Find B Ç A^C F. Find C Ç D È A

G. Find (A Ç B)^C È D H. Find (B Ç A) Ç C I. Find (C Ç D È A)^C Ç B

J. Find A Ç C È D K. Find (A Ç C) È B L. Find U^C

M. Find P(A) N. Find P(B) O. Find P(C)

P. Find P(D) Q. Find P(U) R. Find P(B) \ P(C)

S. Find P(C) \ P(B) T. Find (P(B))^C U. Find P(B^C)

§ 2.2 VENN DIAGRAMMES AND OTHER

ILLUSTRATIONS FOR SETS

Now, let us investigate the potential use of pictures to represent the concepts from section 2.1. All of you are familiar with the line, R, and its graphical representation:

¬¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾®

There is no centre (e.g.: the nonsense about ¥ + (-¥) = 0 one may have leant in high school is a fallacy) so one can reasonably represent the line as:

¬¾¾¾¾¾¾|¾¾|¾¾|¾¾|¾¾|¾¾|¾¾|¾¾|¾¾|¾¾¾¾® or

-4 -3 -2 -1 0 1 2 3 4

¬¾¾¾¾¾¾|¾¾|¾¾|¾¾|¾¾|¾¾|¾¾|¾¾|¾¾|¾¾¾¾® or

-10 -9 -8 -7 -6 -5 -4 -3 -2

¬¾¾¾¾¾¾|¾¾|¾¾|¾¾|¾¾|¾¾|¾¾|¾¾|¾¾|¾¾¾¾® or

e p 10 20 40 60 1,000 10²⁰

You (hopefully) will study the properties of the line in Advanced Calculus I (Math 353), additional topics of the line in Advanced Calculus II (Math 354), and more generalisations of the line in Real Variables (Math 451), Complex Variables (Math 454), or Topology (Math 480).

Nonetheless, there are general pictorial representations of sets that are of use to us at this stage of our mathematical development. They are called Venn diagrammes, after the mathematician Venn, who adapted them from the mathematician Euler (more on this topic later). Standard representation of the universe is a rectangle and sets of interest as circles within the rectangle. Elements within the universe are designated with points or lower case letters.

Example 2.2.1: Let U = {1, 2, 3, 4, 5}. Let A = {1, 3, 5}. Note 1 Î A, 2 Ï A, 3 Î A, 4 Ï A, and 5 Î A. The Venn Diagramme for this would be:

Figure 2.2.1

Indeed specification of the elements is not necessary. So, suppose we simply wanted to represent a situation where there was a well defined universe and two sets. Let U be the universe whilst A and B be the sets. We have a number of ways to draw this:

Figure 2.2.2 Figure 2.2.3

Figure 2.2.4 Figure 2.2.5

Of the four possible figures only one is correct for the premises stated: Let U be the universe whilst A and B be the sets; and that would be figure 2.2.2. This is because the picture shows a universe and two sets without adding premises that are not stated. Figure 2.2.3 illustrates sets such that they are disjoint (which was NOT stated; so cannot be deduced). Figure 2.2.4 illustrates sets such that A Í B (which was NOT stated; so cannot be deduced). Figure 2.2.5 illustrates sets such that A Ê B (which was NOT stated; so cannot be deduced). Hence, figure 2.2.2 is the correct Venn diagramme for the premises. Note that in figure 2.2.2 the illustration shows what seems to be an intersection between A and B. That it is drawn does not make it exist. It is simply an illustration that it might exist. If premises were stated such that it definitely does not exist; then figure 2.2.2 would be an incorrect representation of a set of premises.

So, in review for two sets let us consider examples such that a given collection of premises is stated.

Example 2.2.2: Let U be the universe. Let A and B be sets.

Example 2.2.3: Let U be the universe. Let A and B be sets such that A Í B.

Or you could use the Venn diagramme in 2.2.2 and put the symbol for the empty set in the part of set A not in B (i.e.: the set A – B); though that would be less useful.

Example 2.2.4: Let U be the universe. Let A and B be sets such that B Í A

Or you could use the Venn diagramme in 2.2.2 and put the symbol for the empty set in the part of set B not in A (i.e.: the set B – A); though that would be less useful.

Example 2.2.5: Let U be the universe. Let A and B be sets such that A and B are disjoint.

Or you could use the Venn diagramme in 2.2.2 and put the symbol for the empty set in the part of set A and B that overlap (i.e.: the set A Ç B); though that would be less useful.

This discussion illustrates the utility of the generalised two set Venn diagramme of figure 2.2.2.

Of course, what is good for the goose is good for the gander; hence, there is a generalised three set Venn diagramme. Logically, it should include the possibilities of intersection amongst each pair of sets as well as for all three sets. Hence: Let U be the universe. Let A, B, and C be sets.

Figure 2.2.6

Now, note that for a Venn diagramme for a generalised one set scenario, there are but two (2¹) distinct “regions” that compose the illustration. Also note that for a Venn diagramme for a generalised two set scenario, there are but four (2²) distinct ‘regions’ that compose the illustration and that for a Venn diagramme for a generalised three set scenario, there are but eight (2³) distinct “regions” that compose the illustration. Let us number them in no particular order with Roman numerals (to distinguish this idea from actual elements):

Figure 2.2.7

Generalised Venn Diagramme for one set within the universe with ‘ regions’ numbered.

Figure 2.2.8

Generalised Venn Diagramme for two sets within the universe with ‘ regions’ numbered.

Figure 2.2.9

Generalised Venn Diagramme for three sets within the universe with ‘ regions’ numbered.

These Venn diagrammes should be committed to memory so that you (the student) can draw them and use them.

Now, one might naturally opine that the pictorial representations generalise in an intuitively ‘pleasant’ manner. Hence, one might think that a Venn diagramme for a generalised four set scenario would be composed as figure 2.2.10.

Figure 2.2.10.

They would be wrong; however, since it does not illustrate all possible intersections of the sets. The four set generalised Venn diagramme does not illustrate easily; indeed I had to look it up in another text[9] to remind myself the precise manner of drawing it since I have a vague recollection of it. Hence, we shall not bother with it (unless provided with the illustration). Hence, the student should not waste time learning how to draw it.

Figure 2.2.11

Generalised Venn Diagramme for four sets within the universe.

An appealing exercise is to try to determine why figure 2.2.10 is incorrect and figure 2.2.11 is correct (see exercise 9).

One can create generalised Venn diagrammes for five or more sets; but, it is beyond practicality. Sometimes picturing the situation is at best useful whilst other times it is an exercise in frustration and might not aide in solving a problem. Venn diagrammes are by design of use in order to assist a person in visualising a problem; but there are some problems that might not be so easily visualised. Hence, caution is advised. Determine whether or not it is of use to you, the student, to spend time attempting to draw a graph of a problem, claim, etc. before attempting to solve the problem, construct an argument or counter-argument, etc.

Nonetheless, there are instances where drawing a Venn diagramme with more than three sets is if use: that is, when there are added hypotheses which yield an easier illustration. Such complex Venn diagrammes might be of use (it is up to you to decide).

Example 2.2.6: Let U = (note that is a well defined universe) such that the sets A, B, C, D, E, and F are defined as follows:

A = {x | x is prime},

B = {x | there is an element j in the universe so that x = 2j},

C = {x | there is an element k in the universe so that x = 4k + 1},

D = {2},

E = {x | there is an element m in the universe so that x = 6m + 1}, and,

F = {1}.

The Venn diagramme to illustrate these sets in the universe would be:

Figure 2.2.12

Venn Diagramme for example 2.2.6.

One of the most useful applications of Venn diagrammes is in the visualisation it allows for operations between sets. This use will be especially important for the student when he takes Set Theory, Math 255, and subsequent courses since he will be asked to prove or disprove certain assertions about sets.

Example 2.2.7: Suppose U is a well defined universe such that A and B are sets. Is it the case that A^C È B^C = (A È B)^C ? One may opine it is true or it is false - - the Venn diagramme provides visual evidence to suggest a proper course of action (to prove the claim or to provide a counterexample).

So, let us consider a generalised Venn diagramme for two sets:

Note that A^C is composed of regions III and IV while B^C is composed of regions I and IV. Hence since we are consider a union, this means that A^C È B^C is composed of regions I, III, and IV. So, we would shade these regions in to signify the set A^C È B^C.

Note that A is composed of regions I and II whilst B is composed of regions II and III. Hence since we are consider a union, this means that A È B is composed of regions I, II, and III. But we must further note that we are considering (A È B)^C, so we realise that the complement of A union B is composed of region IV. So, we would shade only region IV to illustrate the set (A È B)^C.

So, the question would be answered negatively (is it the case that A^C È B^C = (A È B)^C ?) and we would need to present a counterexample to the claim. But wait! We have a counterexample - - all we have to do is present it properly:

Claim: Suppose U is a well defined universe such that A and B are sets. It is case that

A^C È B^C = (A È B)^C.

Counterexample: Let U =₄ . Let A = {1, 2}. Let B = {2, 3}. Note that A^C = {3, 4} and

B^C = {1, 4}. So, A^C È B^C = (1, 3, 4}. But, A È B = {1, 2, 3}. So, (A È B)^C = {4}.

Since 1 Î A^C È B^C and 1 Ï (A È B)^C; it is the case that A^C È B^C = (A È B)^C is false. [10]

EEF.

Note that we had to construct an example [define a universe, construct sets A and B within that universe and demonstrate that there was an element in one of the sets that was not in the other so that the claim of equality of sets must be false] which shows the claim false (hence, the term counterexample) rather than just record a suggestive illustration of the case that the claim is false.

Example 2.2.8: Suppose U is a well defined universe such that A, B, and C are sets. Is it the case that A^C È B^C – C Í (A Ç B Ç C)^C ? One may opine it is true or it is false - - the Venn diagramme provides visual evidence to suggest a proper course of action (to prove the claim or to provide a counterexample).

So, let us consider a generalised Venn diagramme for three sets:

Note that A^C is composed of regions III, VI, VII, and VIII; B^C is composed of regions II, V, VI, and VIII; and C is composed of regions I, II, III, and IV. A^C È B^C is composed of regions II, III, V, VI, VII, and VIII. Now the regions in that set that overlap C are II, III, and VI.

So, A^C È B^C – C is composed of regions V, VII, and VIII. So, we would shade these regions in to signify the set A^C È B^C – C:

Now consider A is composed of regions I, II, IV, and V; B is composed of regions I, III, IV, and VII. So, A Ç B is composed of regions I and IV. C is composed of regions I, II, III, and IV. So,

A Ç B Ç C is composed of region I. Thus, (A Ç B Ç C)^C is everything but region I; so we would shade:

Now, the extremely important point for this part of the discussion: THIS IS NOT A PROOF THAT A^C È B^C – C Í (A Ç B Ç C)^C ! ! ! It is merely a pictorial representation that leads one to the realisation that he needs to prove that A^C È B^C – C Í (A Ç B Ç C)^C. We shall not ‘cover’ this in this class; it is a matter for Math 255. Suffice it to say, however, that one could prove this using an indirect or a direct method. Lest one be disturbed that we do not think the reader capable of understanding this, we shall include a proof of the claim:

Claim: Suppose U is a well defined universe such that A, B, and C are sets. It is case that

A^C È B^C – C Í (A Ç B Ç C)^C.

Proof: Assume the premises. Suppose $ x Î A^C È B^C – C ' x Ï(A Ç B Ç C)^C.

Then x Î A Ç B Ç C. So, x Î C. But, x Î A^C È B^C – C which implies x Î (A^C È B^C) Ç C^C.

But that implies x Î C^C. So, x Ï C.

Thus, x Î C Ù x Ï C which is a contradiction.

Hence, the supposition is false and A^C È B^C – C Í (A Ç B Ç C)^C.

QED

To reiterate, the important lesson is that a Venn diagramme is neither a proof nor a counterexample to a claim. It is a tool that suggests a course of action (do a proof or construct a counterexample) that one would follow to successfully prove or disprove a claim.

Venn diagrammes do not have to be drawn such that there are circles within a rectangle. Given a particular arrangement of premises there are other ways to draw a Venn. Consider the next example:

Example 2.2.9: Let U is a well defined universe such that A, B, C, and D are sets where

A Ç B Ç C = Æ, A Ç C = Æ, B Ç C = Æ, A Ç B = Æ, A È B È C = U.

The Venn diagramme can be drawn as follows

because A, B, and C do not overlap (not even pair-wise) but they comprise all of U. We must allow for D to possibly intersect A, B, and C.

When sets “fill up” the universe in such a manner (A È B È C = U) we say the sets span the universe or we say the sets are exhaustive of the universe. This notion will be rendered more rigorous in Math 255.

When sets are “non-overlapping” two at a time (A Ç C = Æ, B Ç C = Æ, A Ç B = Æ) they are said to be pair-wise disjoint.

Another interesting use of Venn diagrammes is in solving problems in elementary descriptive statistical analysis (survey, questionnaire, population amalgams). It requires that we accept without proof that certain properties of sets are so (these shall be proven in Math 255):

For all the theorems assume U is a well defined universe and A, B, and C are sets.

Theorem 3.2.1: A Í U. Theorem 3.2.2: A Í B, B Í C Þ A Í C.

Theorem 3.2.3: Æ Í A. Theorem 3.2.4: A Ç B Í A Ù A Ç B Í B.

Theorem 3.2.5: A Í A È B Ù B Í A È B. Theorem 3.2.6: A - B Í A Ù B - A Í B.

Theorem 3.2.7: A È B = B È A. Theorem 3.2.8: A Ç B = B Ç A.

Theorem 3.2.9: A Í A Theorem 3.2.10: A Ç A = A.

It also requires we have a definition for the term ‘finite’ set. That is beyond the scope of the course[11]; but we can have an intuitive understanding of a finite set to be able to solve the problem.

The intuitive sense is based on the intuitive sense of the word ‘infinite.’ We naively understand ‘infinite’ to mean goes on and one; so, ‘finite’ would intuitively mean stops. We believe that a finite set stops (which does match the definition of finite). That will suffice for surveys, etc.[12]

Notation: Let U is a well defined universe and A be a set. | A | means the number of elements in A.

It is read as the cardinality of the set A.

Example 2.2.6 (revisited): Let U = (note that is a well defined universe) such that the sets A, B, C, D, E, and F are defined as follows: A = {x | x is prime},

B = {x | there is an element j in the universe so that x = 2j},

C = {x | there is an element k in the universe so that x = 4k + 1},

D = {2}, E = {x | there is an element m in the universe so that x = 6m + 1}, and, F = {1}.

| U | = 61. | A | = 18. | B | = 31. | C | = 15. | D | = 1. | E | = 10. | F | = 1.

These values seem to come from nowhere. Let us delineate the sets in list form (other than the universe). The two easiest are D and F since they were in list form.

D = {2}. F = {1}. A = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 57, 59}.

B = {0,2,4,6,8,10,12,14,16,18,20,22,24,26,28,30,32,34,36,38,40,42,44,46,48,50,52,54,56,58,60}

C = {1, 5, 9, 17, 17, 21, 25, 29, 33, 37, 41, 45, 49, 53, 57}

E = {1, 7, 13, 19, 25, 31, 37, 43, 49, 55}. Recall the Venn diagramme for this example was:

Now consider the following:

Example 2.2.10: A survey was administered to 500 Morehouse students regarding movies they had seen. 204 saw Blade II, 137 saw Men in Black II, 180 saw Goldmember, 33 saw all 3, 41 saw Goldmember and Blade II, 78 saw Men in Black II and Blade II, while 33 saw Men in Black II and Goldmember. Draw a Venn Diagramme illustrating the survey. Answer the following questions: How many saw Men in Black II only? How many saw exactly two movies? How many did not see Goldmember? How many saw neither Men in Black II nor Blade II?

One would begin by drawing a Venn and defining the sets. Let B represent the students who saw Blade II, M represent the students who saw Men in Black II, and G represent the students who saw Goldmember. Note | U | = 500; | B | = 204; | M | = 137; | G | = 180; | B Ç M Ç G | = 33;

| G Ç B | = 41; | M Ç B | = 78; and, | M Ç G | = 33.

Start with a set that represents only one region- that would be B Ç M Ç G and it has 33 elements.

B Ç M Ç G Í M Ç G and all 33 elements are accounted for; so | (M Ç G) – B| = 0.

B Ç M Ç G Í M Ç B and M Ç B has 78 elements 33 of which have already been accounted for. Thus, | (M Ç B) – G| = 45. So, we have at this point:

Continuing, B Ç M Ç G Í G Ç B and G Ç B has 41 elements 33 of which have already been accounted for. Thus, | (G Ç B) – M| = 8.

Recall, | B | = 204 and we have accounted for 8, 33, and 45 of the elements so far; hence,

| B - (M È G)| = 204 – (8 + 33 + 45) = 204 – 86 = 118. Also, | M | = 137 and we have accounted for 33 and 45 of the elements so far; hence, | M - (B È G)| = 137 – (33 + 45) = 137 – 78 = 59.

| G | = 180 and we have accounted for 8 and 33 of the elements so far; hence,

| G - (M È B)| = 180 – (8 + 33) = 180 – 41 = 139. So, we have:

But, we are not done! There is still (M È B È G)^C to which to account.

Recall | U | = 500 and | M È B È G | = 118 + 45 + 59 + 8 + 33 + 0 + 139 = 402. This implies that

| (M È B È G)^C | must be 98. So, we are done with the Venn diagramme when we draw:

Now, the questions are facile to answer.

Question: how many saw Men in Black II only? Since | M – (B È G) | = 59, the answer is 59.

Question: how many saw exactly two movies?

Exactly two movies means ((G Ç B) – M) È ((M Ç B) – G) È ((G Ç M) – B)

So, that would be 45 + 8 + 0 = 53. The answer is 53.

Question: how many did not see Goldmember? For this we need | G^C | = 98 + 118 + 45 + 59 = 320.

So, the answer is 320.

Question: how many saw neither Men in Black II nor Blade II?

That would correspond to | (M È B)^C|. As we can see that would be 98 + 139 = 237.

We could go on and on with this example; but, suffice it to say the Venn diagramme allows for a succinct reference to answer such questions.

§ 2.2 EXERCISES.

1. Draw a Venn diagramme to illustrate the following. Assume U is a well defined universe and A, B, C, and D are sets (use only as many sets as is necessary per part):

A. A Ç C = Æ and B is a set. B. A Ç C = Æ and B È D = U

C. A Ç B = Æ. D. A Ç B Ç C = Æ

2. Shade in the corresponding region or regions associated with the following sets in a Venn diagramme. Assume U is a well defined universe and A and B are sets:

A. A Ç B^C. B. A È B

C. A^C Ç B. D. A – B

E. (A Ç B)^C. F. (A È B)^C

G. (A^C Ç B)^C. H. (B – A)^C

3. Shade in the corresponding region or regions associated with the following sets in a Venn diagramme. Assume U is a well defined universe and A, B, and C are sets:

A. A È C Ç B^C. B. A È (C Ç B^C).

C. (A Ç B) È C . D. A Ç (B È C) .

E. (A Ç B)^C - C. F. C – (A^C È B)

G. (A Ç C) Ç B ^C. H. A Ç (C Ç B ^C).

I. (A Ç C) Ç A ^C. J. (A È B) Ç (A È C) ^C.

K. A – (B – C). L. (A – B) È (A Ç C).

4. Suppose U = N₁₀, A = {x | x = 3p for some p Î U}, B = {1, 4, 6, 9},

and C = {x | there is not a q Î U where x = 4q}. Draw a Venn diagramme and place the elements in their corresponding sets.

5. Suppose U = N₁₀, A = {x | x = 2p for some p Î U}, B = {1, 4, 6, 9},

and C = {x | x = 2q – 1 for some q Î U }. Draw a Venn diagramme and place the elements in their corresponding sets.

6. Suppose the CDC had records of 189 patients from a cardiac care unit at Atlanta Medical Centre and the records reflected the fact that 69 patients had cancer, 72 had pneumonia, 89 had emphysema, 22 had cancer and emphysema, 14 had pneumonia and emphysema, 23 had cancer and pneumonia, and 8 had all three of the aforementioned diseases. Draw a Venn Diagramme illustrating the records. Answer the following questions: How many patients had only cancer? How many had emphysema, but not cancer nor pneumonia? How many had pneumonia or emphysema but not cancer? How many had cancer or emphysema but not pneumonia? How many had pneumonia and emphysema but not cancer? How many had none of the three diseases?

7. A survey was done of children regarding programmes they like. 44 kids liked Barney, 37 liked Sesame Street, 40 like Mr. Rogers, 18 liked all 3, 16 did not like any of the three, 23 likes Sesame Street and Mr. Rogers, 28 liked Barney and Mr. Rogers, while 21 liked Barney and Sesame Street. Draw a Venn Diagramme illustrating the survey. Answer the following questions: How many children were surveyed? How many liked Barney only? How many liked exactly two programmes? How many did not like Sesame Street? How many liked neither Barney nor Mr. Rogers?

8. A survey was done of 81 Morehouse students whose declared major was housed in the Division of Science and Mathematics. The survey statistics are as follows. 44 students chose their major based on potential earnings (i.e.: they are “going for the Benjamins”), 45 students majored in an area that did not interest them, 23 students were in a major that interested them. Draw a Venn Diagramme illustrating the survey. Answer the following questions: How many students were majoring in an area that interested them? How many students were majoring in an area that interested them and did not choose it based on potential earnings? How many students were majoring in an area that did not interest them and did not choose it based on potential earnings (i.e.: seem clueless)?

9. Consider the problem of drawing a generalised Venn diagramme for four sets. Why is figure 2.2.10 incorrect whilst figure 2.2.11 which was based on the figure drawn by Carol Guadagni correct? Can you opine as to what held for the generalised one, two, and three set Venn diagrammes that does not hold for figure 2.2.10 but does for figure 2.2.11?

§ 2.3 AN INTRODUCTION TO SYLLOGISTIC LOGIC

AND BASIC QUANTIFICATION

Not every argument is of the form or type (i.e.: given the premises A Þ ØB, ØA Þ ØC,

C, D Þ B, it is the case that ØD follows as a conclusion) we studied in chapter one. Some argument types are claims of quantification. Now this seems especially apropos for a discussion in a mathematics class. Many mathematical arguments hinge on an understanding of sets and involve questions of what is in a set or not, how many elements are in the set, etc. Thus, as this section illustrates we use terms such as ‘not every,’ ‘some,’ ‘many,’ ‘none,’, ‘all,’ for every,’ etc. in our discussions, arguments, and applications. Each of the aforementioned words are examples of quantifiers and are part of the area of logic known as syllogistic logic.

Arguments of the type in chapter one were examples of propositional or symbolic arguments; that is, arguments that use the conditional, biconditional, conjunction, and disjunction. However, there are other types of arguments known as syllogistic arguments which differ from symbolic argument in that syllogistic arguments use quantifying words such as all, none, or some.

Note the difference in the following two arguments:

Example 2.3.1 : All frogs have warts.

All creatures that have warts are blue.

Therefore, all frogs are blue.

Example 2.3.2: If Malcolm is talking, then people listen.

Malcolm is not talking.

Therefore, no one is listening.

The former is a syllogistic argument (or syllogisms); the latter is a symbolic argument.

To determine evidence to suggest that a syllogistic argument is valid or invalid one may use a diagramming technique known as Euler's diagrammes (named after the mathematician Leonhard Euler). Euler's Diagrams are really an application of set theory to logic for they are really just Venn diagrammes set to logic problems.[13]

Let us consider example 2.3.1 from above. Since all frogs have warts, the set of frogs is a subset of the set of creatures that have warts. Since all creatures that have warts are blue, the set of creatures that have warts is a subset of blue things. Ergo, all frogs have warts.

We need to assume there is a well defined universe, D, defined that in this instance we shall reference as the domain of discourse. We need to also the sets we shall use (i.e.: the symbols we shall use). Let F denote the set of frogs, W denote the set of creatures that have warts, and B be the set of blue things. The diagramme (Euler diagramme solution) illustrates this:

Note that we are simply showing a Venn diagramme such that the universe is D, F Í W, W Í B,

and so, F Í B. It must be the case since there is not a way to illustrate this in another manner.

Hence, the Euler diagramme illustrates that the syllogistic argument is valid (but remember that this does not prove the argument is true).

In terms of quantification, the symbol to represent each element of the set F is an element of the set W is " x Î F, x Î W. The translation of this symbol (") is ‘for all,’ ‘for each,’ ‘every,’ etc.

So, the following statements are symbolized as:

All frogs are amphibians. " f Î F, f Î A where F represents the set of frogs and A represents the set of amphibians.

Each student is attentive. " s Î S, s Î A where S represents the set of students and A represents the set of attentive people.

Every professor is funny. " p Î P, p Î F where P represents the set of professors and F represents the set of funny people.

Note the use of the lower case English letter for elements and upper case for sets. Note that one does not have to use x as the variable representing an element of the set. Finally note the difference between example 2.3.1 and example 2.3.2. Example 2.3.2 is solved using a truth table (which is left to the student as an exercise).

We can rewrite example 2.3.1 in symbols as:

" x Î F, x Î W.

" y Î W, y Î B.

\ " x Î F, x Î B.

The traditional way to represent therefore in syllogistic argument for is the “\” rather than the “Þ,” but either is (of course) fine.

Consider the following example:

Example 2.3.3: No Morehouse students are Spelman students.

Some Spelman students work.

Therefore, no Morehouse students work.

Before defining some new symbols, let us not this is a syllogistic claim since it is in terms of sets, elements, and quantification. Let us represent the domain of discourse as D, the set of Morehouse students as M, the set of Spelman students as S, and the set of people who work as W.

The first sentence means that M Ç S = Æ because if there was an element of M that was in the set S, then there would be a Morehouse student who was a Spelman student. Further, if there was an element of S that was in M, then there would be a Spelman student who was a Morehouse students which implies that this person is a Morehouse student who is a Spelman student.

The second sentence is a tad more challenging. We need a new symbol to represent the statement. In terms of quantification, the symbol to represent, ‘some,’ $. The translation of this symbol ($) is ‘some,’ ‘there exists,’ ‘there is at least one,’ etc. So, the second sentence quantified symbolically would be $ x Î S, x Î W.

The third sentence symbolized would be: \ M Ç W = Æ.

Now, do you think the claim is true or false? Let us reflect on the claim.

No Morehouse students are Spelman students. We represent the set of Morehouse students as M and the set of Spelman students as S. M Ç S = Æ. Thus, the sets are disjoint. Some Spelman students work. Notice that S Ç W ¹ Æ (since $ x Î S ' x Î W) . So, S and W intersect. The two statements are the suppositions (the premises). We are now faced with drawing any possible Euler diagramme that illustrates these two suppositions. Note that for the argument to be valid, it must be the case that M Ç W = Æ. Let us consider the following two diagrammes.

Both could be true for the premises. There is nothing in the premises that forces either to be the only possibility. However, note the second diagramme represents an instance such that the premises hold and is more generalised. The first represents a diagramme where one is assuming the conclusion (a logical fallacy from chapter one, recall). Therefore, there is evidence to conclude that the syllogism is invalid. The justification for that is the second Euler diagramme (thus, the first one need not be drawn).

One might believe the next example is obvious. Well, let’s consider it.

Example 2.3.4: Some cats are not dogs.

Some dogs are not mice.

Therefore, some cats are not mice.

Let us define our sets. Let U be the domain of discourse, C be the set of cats, D be the set of dogs, and M be the set of mice. Note we are not going to use D as the domain of discourse since it might cause confusion with the set of dogs. So, we will use our old friend, U, for that.

The first sentence means that C Ç D^C ¹ Æ because there is at least one cat that is not a dog. The second sentence means D Ç M^C ¹ Æ. The last sentence means C Ç M^C ¹ Æ. In terms of quantification, the first sentence translated reads: $ x Î C, x Î D^C or $ x Î C, x Ï D (either is fine). The second sentence translated reads: : $ y Î D, y Î M^C or $ y Î D, y Ï M. The third sentence translated into symbols would be: \ $ c Î C, c Î M^C or $ c Î C, c Ï M.

Consider the following two Euler diagrammes:

Many people would decide on the second Euler based on empirical evidence. They would be wrong since we are trying to judge the veracity of the syllogism, not the state of nature. Many people would decide on the first Euler since for sentence one there is a region corresponding to the sentence

shaded so that represents the idea that there is at least one cat that is not a dog. For sentence two there are regions corresponding to the sentence

shaded so that represents the idea that there is at least one dog that is not a mouse. However, one can reasonably draw an Euler diagramme such that the premises hold, but the conclusion does not:

Note the premises hold for this since it displays that C – D ¹ Æ (sentence one):

and since it displays that D – M ¹ Æ (sentence two):

but there is not a display such that C – M ¹ Æ! So, the syllogistic argument is invalid.

The difficulty for many with syllogisms such as example 2.3.4 is that experience dictates in the real world the claim seems true (indeed can be strengthened). However, we are not interested in the existential question of life and mice, cats, and dogs! We are interested in the argument form because it should be clear from the Euler diagramme that one can change the wording of example 2.3.4 to:

Some students are not men.

Some men are not tall.

Therefore, some students are not tall.

and the argument is still invalid!

Suffice it to say, there are some important principles to consider in this section.

Assume D is a well defined domain of discourse, A is a set and B is a set.

Assume " x Î A, x Î B. Does this mean $ x Î A, x Î B? The answer is , ‘no,’ since a counterexample exists to the claim. Let A = Æ and all elements of Æ are in B since there are no elements in Æ! Indeed note theorem 3.2.3.

So, we can say " x Î A, x Î B $ x Î A, x Î B.

Thus, in mathematics note the following two claims are different:

Theorem 3.2.1: Assume U is a well defined universe and A is a set. It is the case that A Í U.

In this instance we are trying to prove " x Î A, x Î U.

We must consider the cases where A is null and the case where A is not null.

Claim 3.2.7: Assume U is a well defined universe and A is a non-empty set and B is a set.

It is the case that A Í A È B. In this instance we are trying to prove " x Î A, x Î B.

Moreover we have as a premise $ x Î A so we do not have to consider a case where A is null.

Now, assume $ x Î A, x Î B. Does this mean $ x Î A, x Ï B? The answer is, ‘no,’ since a positive existential does not necessarily imply a negative existential. Note there exists a Morehouse student that is male does not imply there exists a Morehouse student who is not male must be true.

So, we can say $ x Î A, x Î B $ x Î A, x Ï B.

Likewise $ x Î A, x Ï B $ x Î A, x Î B.

Another principle that is of import is negation of quantifiers. What does it mean to say

Ø(" x Î A, x Î B)? Consider " x Î A, x Î B Û A Í B. So, Ø(" x Î A, x Î B) Û A B.

Hence for A B, it must be the case there is an element in A that is not in B. So, $ x Î A, x Ï B.

To sum up Ø(" x Î A, x Î B) Û $ x Î A, x Ï B.

One can reason that the other negation principle is Ø($ x Î A, x Î B) Û " x Î A, x Ï B since Ø($ x Î A, x Î B) implies that A Í B^C.

From these two principles and the law of double negation, it should be clear to the reader that

Ø(" x Î A, x Ï B) Û $ x Î A, x Î B and Ø($ x Î A, x Ï B) Û " x Î A, x Î B.

So, from a vernacular standpoint one must be quite attentive to what is being said so that we can understand a statement. For example, what is the opposite of the statement, “All Atlantans are citizens of Fulton County?” If you were to say, "no Atlantan is a citizen of Fulton County," you would be wrong. The correct statement would be, “not all Atlantans are citizens of Fulton County;” which can also be stated as, “some Atlantans are not citizens of Fulton County.” This is because some can still be citizens of Fulton, but at least one is not.

Likewise, the opposite of "no people wear hearing aids" is "some people wear hearing aids." It is incorrect to say, "all people wear hearing aids." That kind of extremism, it should be noted, is incorrect, and many times, creates many real problems. For example, to negate the statement, "all of us are poor," does not mean all of us will be rich! It simply means some of us will not be poor anymore.

Let us consider one more example using Euler's Circles.

Example 2.3.5: Some Estonians are not Nigerians.

Some Nigerians are not Argentines.

Therefore, some Estonians are not Argentines.

Let D denote the domain of discourse, E be the set of Estonians, N be the set of Nigerians, and A be the set of Argentines for the Euler's diagramme. What does the Euler diagrammes indicate, true or false?

Note, you can draw an Euler diagramme to show that a counterexample should exist to this argument form since:

So, the argument is invalid, because this diagramme indicates there exists a counter-example to the argument. Indeed further note that you can draw a diagramme such that there could be an instance where it can be true:

so, the two Euler diagrammes which both hold for the premises but the first is contrary to the conclusion whilst the second is supportive of the conclusion should assist you in noting that the argument is fallacious (and that you don’t have to use circles for the sets).

A couple of other notes: in many logic texts the form used is not set-theoretic but functional form. So, considering

Example 2.3.1 : All frogs have warts.

All creatures that have warts are blue.

Therefore, all frogs are blue.

You might see it written as " x , F(x) Þ W(x).

" x , W(x) Þ B(x).

\" x , F(x) Þ B(x).

This is indeed helpful (in a way) for it assists us in understanding that subsethood from set theory has the same intrinsic property to the conditional from logic (see table 2.1.1). However, since we are studying logic in order to help us better learn, remember, and understand mathematics we shall use the convention from set-theory.

Also, the four basic quantification statements that we have studied in this section lead to some interesting relationships (when viewed in functional form). Let F(x) be a statement where x is some element of the domain of discourse. Note that " x , F(x); " x , ØF(x); $ x , F(x); and,

$ x , ØF(x) have interesting properties.

" x , F(x) and " x , ØF(x) are contraries; that is to say they might both be false or both be true.

$ x , F(x) and $ x , ØF(x) are contraries; that is to say they might both be false or both be true.

" x , F(x) and $ x , ØF(x) are contradictories; that is to say one must false and the other true.

$ x , F(x) and " x , ØF(x) are contradictories; that is to say one must false and the other true.

$ x , F(x) being true does not necessarily imply " x , F(x) is true.

$ x , ØF(x) being true does not necessarily imply " x , ØF(x) is true.

" x , F(x) being true does not necessarily imply $ x , F(x) is true.

" x , ØF(x) being true does not necessarily imply $ x , ØF(x) is true.

So, you can see we have extremes: " x , F(x) and " x , ØF(x) (the contraries) and a middle (the contradictories to the extremes) which may be viewed as a “continuum.”

" x , ØF(x) $ x , ØF(x) $ x , F(x) " x , F(x)

negative negative positive positive

universal existential existential universal

§ 2.3 EXERCISES

1. A. For each statement define all symbols and translate the argument into symbolic form.

B. Use Euler diagrammes to illustrate whether each argument is valid or not.

A. Everybody plays the fool.

All those who play the fool are hurt.

Therefore, everybody is hurt.

B. Washington is north of California.

Oregon is north of California.

Therefore, Washington is north of California.

C. Some math majors study Spanish.

All people who study history also study Spanish.

Therefore, some math majors study history.

D. No Midtowners live outside the perimeter.

All Midtowners are Atlantans.

Therefore, no Atlantans live outside the perimeter.

E. Some Floridians are beach lovers.

All Floridians are Americans.

Therefore, some Americans are beach lovers.

F. All students are intelligent.

All dolphins are intelligent.

Therefore, some students are dolphins.

2. Use either Euler diagrammes or truth tables to illustrate whether the following arguments are valid or invalid:

A. If Kokayi is sick, then Rachel gives him aspirin.

Rachel gives Kokayi aspirin.

Therefore, Kokayi is sick.

B. All Irish are Europeans.

All Ugandans are Africans.

Some Africans are also Europeans.

Therefore, some Ugandans are Irish.

C. Judith is young or Edith is fair.

If Edith is fair, then Valeska is speaking Urdi.

Therefore, Valeska is not speaking Urdi.

D. Beulah is a good cook.

All good cooks are happy.

Some happy people are rotund.

Therefore, Beulah is rotund.

E. If Constance goes shopping, then Martin is singing.

If Grace is not cleaning, then Martin is not singing.

Therefore, if Constance goes shopping, then Grace is cleaning.

3. Symbolise the following statements using quantifiers or propositional functions:

A. Snakes are reptiles.

B. Snakes are not all poisonous.

C. Not any visitors stayed for supper.

D. All vegetables and fruits are nutritious and tasty.

E. Only policemen and firemen are both indispensable and underappreciated.

F. Some horses are well behaved and gentle.

G. Some New Yorkers are rude or arrogant.

H. Not all New Yorker are rude and arrogant.

I. There are some arrogant and rude people from New York.

4. Write the negation in vernacular English of the following statements:

A. Jermaine is studious or Helen is an economist.

B. All English majors are poets.

C. Some engineers are mathematicians.

D. Jeramiah is a bullfrog.

E. Howitson can fly and Marissa can sing.

F. Paul is fatuous and Edward is not an architect.

G. Some English majors are not poets.

H. Some engineers are not mathematicians.

I. No snake is by its nature evil.

J. Everybody rock your body.[14]

5. Consider the following Venn diagrammes. Note what set corresponds to the shaded region.

A. B.

C. D.

6. Construct an example to show " x , F(x) and " x , ØF(x) are contraries.

7. Construct an example to show " x , F(x) and $ x , ØF(x) are contradictories.

8. Construct an example to show $ x , F(x) and " x , ØF(x) are contradictories.

9. Construct an example to show $ x , F(x) and $ x , ØF(x) are contraries.

10. Let U = N. Determine if the each of the following statements is valid or invalid.

A. $ x Î N ' Î N

B. $ x Î N ' Ï N

C. " x Î N ' Î N

D. " x Î N ' Ï N

E. $ x Î N ' (x – 1) Î N

F. $ x Î N ' (x – 1) Ï N

G. " x Î N ' (x + 1) Î N

H. " x Î N ' (x + 1) Ï N

I. " x Î N ' (x – 1) Î N

J. " x Î N ' (x – 1) Ï N

K. $ x Î N ' (x + 1) Î N

L. $ x Î N ' (x + 1) Ï N

11. Construct a truth table to establish the argument in example 2.3.2 is valid or invalid.

§ 2.4 MORE SYLLOGISTIC LOGIC AND

TWO PLACE QUANTIFICATION

An important principle of mathematics is the use of quantifiers in combination. Many readers are probably familiar with the following definition from Math 251: Let f be a function with domain D and a Î D. " e > 0 $ d > 0 ' 0 < | x – a| < d Þ | f(x) – f(a) | < e which one memorised but may not have learnt. It is not an ‘easy’ definition to remember, let alone understand. One might it is the definition of a function being continuous at an x-value of a. Let us translate it: “Let f be a function with domain D and a Î D. For each epsilon greater than zero there exists a delta greater than zero such that the distance between x and a being more than zero but less than delta implies that the distance between f of x and f of a is less than epsilon.” Note the translation of, ‘for each,’ for the upside down A to signify that different epsilons can produce different deltas.

This is quite different than $ d > 0 " e > 0, 0 < | x – a| < d Þ | f(x) – f(a) | < e which would translate to, “there is a delta greater than zero that ‘works’ for all epsilon greater than zero to produce the distance between x and a being more than zero but less than delta implies that the distance between f of x and f of a is less than epsilon.” In this instance we are saying that there is one delta that will make this so no matter the epsilon.

Perhaps an easier example will suffice. Let U = N. Let A = {1, 3, 5, . . .}, B = {2, 4, 6, . . . }, C = {4, 7, 10, . . . }.

Written in set-builder notation A = { x | $ p Î U so that x = 2p – 1},

B = { x | $ p Î U so that x = 2p}, and C = { x | $ p Î U so that x = 3p + 1}.

Now consider the following statement:

" x Î N $ y Î N ' x < y. Translated the statement reads, “for each x in the natural numbers there exists a y also in the natural numbers such that x is less than y.”

Consider the statement, is it true or not?

Well, it is true based on the Archimedean property of the natural numbers (that we should have learnt in high school). Contemplate the claim. What is it saying? That each for each x Î N you can find a y also in N so that y is bigger than x (which is facile: let y = x + 1).

However consider the following statement:

$ p Î N " q Î N ' p < q. Translated the statement reads, “there is a p in the natural numbers for all q also in the natural numbers such that p is less than q.” However, that translation is quite literal but awkward and not very understandable. Thus, let us translate it as, “there is a p in the natural numbers that is less than every q also in the natural numbers.” Isn’t that what the statement is claiming?

Consider the statement, is it true or not?

Well, it is not true based on the order axioms of the real numbers (that we should have learnt in high school). Contemplate the claim. What is it saying? There is a p Î N that is less than every

q Î N. Obviously this is ridiculous. Most of us would realise that the only possibility is 1. However, 1 is not less than itself! The key here is to realise that just because the claim uses two different letters does not necessarily mean that the numbers must be different. If that was to be the case it must be stated in the claim!

Consider the following statement: $ p Î N " q Î N ' p < q , where q ¹1. This is true.

So too is: $ p Î N " q Î N ' q > 1, p < q . Etcetera, etcetera, ad nausea.

Now, back to the sets A, B, and C.

Consider the statement: " x Î A $ y Î B ' x < y. True or not? Yes, since for each x in A there is something in B so that x < y (y = x + 1 would suffice, but so too would y = x + 3, etc.)

Consider the statement: " x Î A $ y Î C ' x < y. True or not? You decide.

Consider the statement: " x Î B $ y Î C ' x < y. True or not? You decide.

Consider the statement: $ x Î A " y Î B ' x < y. True or not? Yes, since 1 Î A and 1 is less than every element in B.

Consider the statement: $ x Î A " y Î C ' x < y. True or not? You decide.

Consider the statement: $ x Î B " y Î C ' x < y. True or not? You decide.

What about mixing two universals or two existentials together?

Consider the statement: " x Î A " y Î B ' x < y. Translated the statement is, “for each x in A and for each y in B such that x is less than y.” This is a most inelegant translation. Let’s make it better. Let us translate it as, “for each x in A and for each y in B it is the case that x is less than y.”

So, what this is implying is that for any arbitrary pair of elements in the sets A and B, x is always less than y. One can see this is nonsense since a counterexample to this rot exists:

Counterexample: Let U = N. Let A = {1, 3, 5, . . .}, B = {2, 4, 6, . . . }, C = {4, 7, 10, . . . }.

Note 3 Î A and 2 Î B. 3 Ž 2 (indeed 3 ³ 2 [which can be strengthened to 3 > 2 but strengthening it is unnecessary and later we shall see skips a part of the justification]). [15] So we have shown an instance where $ x Î A $ y Î B ' x Ž y which is the contradictory to

" x Î A " y Î B ' x < y; so, since $ x Î A $ y Î B ' x Ž y is true " x Î A

" y Î B ' x < y must be false.

If one was to “write up” the counterexample it is sufficient to do as follows:

Claim: Let U = N. Let A = {1, 3, 5, . . .} and B = {2, 4, 6, . . .}. " x Î A " y Î B ' x < y. Counterexample: Let U = N. Let A = {1, 3, 5, . . .}, B = {2, 4, 6, . . . }, C = {4, 7, 10, . . . }.

Note 3 Î A and 2 Î B. 3 Ž 2. So, " x Î A " y Î B ' x < y is false.

EEF.

Consider the statement: $ x Î A $ y Î B ' x < y. Translated the statement is, “there exists an x belonging to A there exists a y belonging to B such that x is less than y.” Hopefully, you are realising that translating the symbols verbatim is not a terrific idea. More subtlety and liberal paraphrasing assists both you and others to understand the concepts. So, let’s paraphrase the sentence as, “there is an element x in A and an element y in B that have the relationship x is less than y.” So, what this is implying is that there is a pair of elements in the sets A and B, so that x is less than y. One can see this is indicating that all you need to do is demonstrate that there is something in A and something in B so that the thing in A is smaller than the thing in B. Now, that’s not so difficult is it? Indeed the claim is true since 3,185 Î A and 2,000,414 Î B and 3,185 < 2,000,414. So, $ x Î A $ y Î B ' x < y is true.

If one was to “write up” the proof it is sufficient to assume the premises and present the example. This is due to the fact that a proof of an existential requires a simple construction of an example.

Claim: Let U = N. Let A = {1, 3, 5, . . .} and B = {2, 4, 6, . . .}. $ x Î A $ y Î B ' x < y. Proof: Assume the premises.[16] Let U = N. Let A = {1, 3, 5, . . .} and B = {2, 4, 6, . . . }.

Note 3,185 Î A and 2,000,414 Î B and 3,185 < 2,000,414. So, $ x Î A $ y Î B ' x < y is true.

QED.

It is also the case that one could consider quantifiers of three, four, etc.; but, if one can really understand quantification of the first and second order then they are doing very well indeed.

Another important skill one should learn is negating quantifiers in combination. If one learnt the negation techniques from the previous section, then it can be easily seen that the same rules apply for negating two place quantifiers. Recall

Ø(" x , F(x)) Û $ x, ØF(x), Ø($ x , F(x)) Û " x, ØF(x)

so, suppose we wish to negate " x $ y , F(x, y)) where F(x, y) is some statement about x and y. This would mean that we change the quantifier and negate the statement. So, we would note this would be $ x " y , ØF(x, y)). Likewise, Ø($ x " y , F(x, y)) Û " x $ y , ØF(x, y);

Ø(" x " y , F(x, y)) Û $ x $ y , ØF(x, y); and,

Ø($ x $ y , F(x, y)) Û " x " y , ØF(x, y);

For example the negation of the statement

" e > 0 $ d > 0 ' 0 < | x – a| < d Þ | f(x) – f(a) | < e (‘for each epsilon greater than zero there exists a delta greater than zero such that the distance between x and a being more than zero but less than delta implies that the distance between f of x and f of a is less than epsilon”) would be

$ e > 0 " d > 0 ' Ø{0 < | x – a| < d Þ | f(x) – f(a) | < e} which would be

$ e > 0 " d > 0 ' {0 < | x – a| < d Ù Ø{| f(x) – f(a) | < e}} (since the negation of A Þ B is

A Ù ØB).

But that would be $ e > 0 " d > 0 ' {0 < | x – a| < d Ù {| f(x) – f(a) | ³ e}}. This translates (paraphrasing) to, “there is an epsilon greater than zero that for all delta greater than zero it is the case both the distance between x and a being more than zero but less than delta is true and distance between f of x and f of a is less equal to or more than epsilon.”

Now, that albeit was a rough one and the type of quantifiers we will be working with at this stage of our mathematical development will be easier; but, hopefully one can see that with practice one can really become adept at mathematics and truly understand what one is doing.

Let us return to U = N, A = {1, 3, 5, . . .}, B = {2, 4, 6, . . . }, C = {4, 7, 10, . . . }.

Recall the statement, " x Î A $ y Î B ' x < y was true. So, its negation must be false. Let us consider the negation of " x Î A $ y Î B ' x < y, which would be $ x Î A " y Î B, Ø( x < y ) which simplifies to $ x Î A " y Î B x ³ y. Paraphrased the statement is, “there is an element of the set A that is greater than or equal to every element in B.” You should realise that is patently false since even a rudimentary and intuitive understanding of N yields the notion that it goes on and on and there is not biggest natural number. Since there is no biggest natural number how could there be an odd number that is greater than or equal to every even natural number? The idea expressed in $ x Î A " y Î B x ³ y is utter balderdash!

Consider " x Î A $ y Î C ' x < y. The negation is $ x Î A " y Î C ' x ³ y.

Consider $ x Î A " y Î B ' x < y. The negation is " x Î A $ y Î C ' x ³ y.

Consider " x Î A " y Î C ' x = y. The negation is $ x Î A $ y Î C ' x ¹ y.

Consider $ x Î A $ y Î B ' | x – y | = 2. The negation is " x Î A " y Î B | x – y | ¹ 2.

Make sure for each of the previously mentioned statements you can translate them, and a nifty exercise would be to determine the veracity or lack thereof of each statement.

Continuing, let us consider the sets N, ^*, and Z.

Consider " x Î N $ y Î Z ' x > y. Is it true or not? Of course it is true, since for each x that is natural there is always an integer that is less than it. Now, the negation of that statement is

$ x Î N " y Î Z ' x £ y. This is false (exercise 6).

Consider $ x Î ^*, " y Î N ' x < y. Is it true or not? Of course it is true, since 0 Î ^* and it is less than every natural number. Now, the negation of that statement is

" x Î ^*, $ y Î N x ³ y. This is false (exercise 6).

Consider $ a Î N, " b Î ^* ' a = b + 1. Is it true or not? Of course it is false since it is stating there is a particular natural number that is precisely equal 1 plus to every b Î ^* .

Now, the negation of that statement is " a Î N, $ b Î ^* ' a ¹ b + 1. This is true since for each element, a, in the natural numbers you can find an element, b, in ^* that is not one less a.

Consider " a Î N, " b Î N, a + b Î N,. Is it true or not? Yes (hopefully you recognise this as the closure of N for addition).

Consider " a Î N, " b Î N, a – b Î N,. Is it true or not? No since $ a Î N Ù

$ b Î N ' a – b Ï N : namely a = 3 and b = 12 (and -9 Ï N).

Consider " a Î Z, " b Î Z, a – b Î Z,. Is it true or not? Yes.

Hopefully these examples help you comprehend that one must make certain to pay attention to the quantifiers, the sets, and the statement as a whole and that ‘tinkering’ with the symbols ever so slightly can change a false claim to a true one or visa versa. Such is the case and is of such sufficient importance that it bears paraphrasing. When you are considering a claim make sure you pay attention to the sets, the quantifiers, as well as the statement. Consider them and take some time to make sure you really understand them.

§ 2.4 EXERCISES.

1. Let U = N. Let A = {1, 3, 5, . . .}, B = {2, 4, 6, . . . }, C = {4, 7, 10, . . . }.

Translate the following into vernacular English:

A. " x Î A $ y Î C ' x < y.

B. " x Î A $ y Î A ' x < y.

C. $ x Î A " y Î B ' x < y.

D. $ x Î A " y Î C ' x < y.

E. " x Î B " y Î B, x < y.

F. " x Î A " y Î B, x = y + 1.

G. $ x Î C $ y Î C, x < y.

H. $ x Î A $ y Î B, x = y + 1.

2. Let U = N. Let A = {1, 3, 5, . . .}, B = {2, 4, 6, . . . }, C = {4, 7, 10, . . . }.

Negate each of the following and translate that negation into vernacular English:

A. " x Î A $ y Î C ' x < y.

B. " x Î A $ y Î A ' x < y.

C. $ x Î A " y Î B ' x < y.

D. $ x Î A " y Î C ' x < y.

E. " x Î B " y Î B, x < y.

F. " x Î A " y Î B, x = y + 1.

G. $ x Î C $ y Î C, x < y.

H. $ x Î A $ y Î B, x = y + 1.

3. Negate the following:

A. There is an m in N that for every b in Z it is the case that –m = b.

B. For each m in ^* there is a b in Z so that –m = b.

C. There is an m in Z and an n in Z so that (m ¸ n) is not in Z.

D. For each m in Z there is an n in Z so that (m ´ n) = n.

E. There is a pair of elements m and n in ^* for which it is the case that | n – m | > 4.

F. Every student and every professor have a positive and professional understanding.

G. There is a staff member who is rude to every student.

H. For each student there is a course with which he struggles.

4. Let U = R. Let F(x) denote that x is a number between -1 and p, Let W(y) denote that y is at least 1, and Q(x, y) denote x + y < y. Translate the following:

A. " y $ x , Q (x, y)

B. $ x , W (x)

C. " y $ x , F(x) Þ Q (x, y)

D. $ y $ x , F(y) Þ ØQ (y, x)

E. $ y , W (y) ' $ x , F(x), Q (x, y)

5. Let U = {x | x is a two dimensional polygon}. Let F(a) denote that a is a square, W(b) denote that b is rectangle, Q(c) denote c is a quadrilateral, L(d) denote that d is a polygon, Y(e) denote that e is a triangle, G(f) denote f is isosceles, D(g) denote that g is equilateral, S(h) denote that h is equiangular, and P(i) denote i is a trapezoid or a pentagon.

Translate the following using the logic symbols we have discussed so far ( ", $, Ø, Þ, Ù, ', Ú, Û, etc.).

A. All equilateral triangles are equiangular and some equiangular triangles are equilateral.

B. All squares are rectangles.

C. Some triangles are equiangular.

D. All rectangles are equiangular.

E. A triangle is not equiangular only if it is isosceles and not equiangular.

F. All squares are rectangles and all rectangles are quadrilaterals.

G. Some quadrilaterals are rectangles and no quadrilaterals are triangles.

H. There exists a polygon which is a triangle or is a trapezoid or is a pentagon.

I. There is at least one polygon that is isosceles and is a triangle.

J. There does not exist an isosceles rectangle.

K. A rectangle is equilateral if and only if it is a square.

§ 2.5 LOGIC AND DEDUCTION.

Logic as a free-standing subject is interesting. However, one does not oft find it discussed in detail in a high school level or below mathematics text. So, one may reasonably question why it is part of the canon in college. Why do we bother to study logic? Why do mathematicians opine it to be so important a subject that it warrants our attention?

Logic is an instrument or organ for appraising the correctness of an argument. The study of logic is the study of methods and principles used to distinguish correct reasoning from incorrect reasoning. It also helps one to construct arguments which are correct rather than incorrect and avoid the pitfalls of rhetoric noted in chapter one. Charles Pierce, Alfred North Whitehead, George Boole, Bertrand Russell, etc. gave formal structure to logic as we previously noted.

Corresponding to every possible inference is an argument and it is with those that we are concerned. We are concerned that you, the student, be able to construct valid arguments to justify your conclusions. Indeed, it is important that the conclusions be derived in such a way as to be apparent and transparent rather than opaque. It is not the case that one wishes to be awarded credit for a problem attempted on a test that was actually incorrect, but the instructor mistakenly didn’t notice. It is not the case that one wishes to gain entry into employment through less than honourable means. It is not the case that one wishes for hedonistic riches without gaining them through credit and hard work. Likewise, the mathematician must demand that his argument be correct and open to inspection. The mathematician desires arguments that are declarative rather than interspersed with interrogatives, pejoratives, etc. So, logic is a system that the mathematician values for its clarity, and reasoned path to conclusions that are valid rather than just possible. That is the great difference between deductive and inductive reasoning.

All arguments propose the claim that the premises provide evidence for the truth of the conclusions. Inductive arguments[17] provide evidence to suggest the conclusion is true. The evidence presented is oft anecdotal and no matter how numerous do not provide positive evidence of the veracity of a claim unless the claim is quantifiable as a finite proposal. However, only deductive arguments provide the evidence such that provided the premises are so, then the conclusion absolutely follows.

Consider the following example:

Example 2.5.1[18]: Let U = N ^* Let us consider f(n) = n² + n + 5.

Note when n = 0, f(n) is f(0) which is 5. It is a prime number.

Note when n = 1, f(n) is f(1) which is 7. It is a prime number.

Note when n = 2, f(n) is f(2) which is 11. It is a prime number.

Note when n = 3, f(n) is f(3) which is 17. It is a prime number.

.

.

.

Some people would be content to look at those examples and say, “ Yes, would you look at that! The function always yields a prime!” Then they would move onto other more ‘pressing’ concerns and abandon the exercise. However, let us observe that when n = 4, f(n) is f(4) which is 25. It is a not prime number since 25 = 5×5×1. The important point is not that the ‘educated guess’ broke down when n = 4 (it could have just as easily continued till n= 2,678,352,431); it is that an ‘educated guess’ is better than an uneducated guess (a ‘stab in the dark’) but a guess in any form does not make a claim true. Guessing in all its forms is a very crucial part of the scientific community’s modus operandi. We need to hypothesise, conjecture, etc. However, we must as mathematicians follow that with proof.

So, logic assists us in this endeavour and makes us demand accuracy. Now, let us consider some interesting logic exercises proposed by the Reverend Charles Dodgson of whom many of you are familiar but as referenced by his penname, Lewis Carroll. He was a mathematical lecturer at Christ Church and he supposedly created these little ‘ditties’ to train his children in logic then collected them and published them as the text Symbolic Logic and the Game of Logic. Of them he was reported to have said, “It will give you clearness of thought – the ability to see your way through a puzzle. Try it. That is all I ask of you.”

The game involves the quest for a ‘best’ conclusion from a set of conclusions to a set of given premises (best being defined as those conclusions which are derived from all of the premises).

Example 2.5.2[19]: Consider the following:

No ducks waltz.

No officers decline to waltz.

All my poultry are ducks.

Let us denote the domain of discourse as U. Let the set of ducks be D. Let the set of things that waltz be W. Let the set of officers be O. Let the set of my poultry be P.

We could solve this using either symbolic logic or by Euler diagrammes.

Let us consider that the quantifiers all, some, there exists, none, etc. can be translated into propositional statements. For example note the first statement, “no ducks waltz,” means

D Ç W = Æ which, in turn, means, “if it is a duck, then it does not waltz” which we can symbolise (liberally) as D ® ØW. Now let us note the second statement, “no officers decline to waltz,” means O Í W which, in turn, means, “if it is an officer, then it waltzes,” which we can symbolise as

O ® W. Finally, let us note that the statement, “all my poultry are ducks,” means P Í D which, in turn, means, “if it is one of my poultry, then it is a duck,” which we can symbolise as P ® D. Now let us look at the premises in symbolic form and we see:

No ducks waltz. D ® ØW.

No officers decline to waltz. O ® W.

All my poultry are ducks. P ® D.

Notice that the second sentence can be restated as ØW ® ØO by the contrapositive form of implication. So, we have:

D ® ØW.

ØW ® ØO

P ® D.

But we know that the order of the premises does not matter; so, we can reorder them so that we have:

P ® D.

D ® ØW.

ØW ® ØO

And we can reason that [(P ® D) Ù (D ® ØW)] Û (P ® ØW) by transitivity. Applying reasoning by transitivity again yields [(P ® ØW) Ù (ØW ® ØO)] Û (P ® ØO). So, a reasonable (logical; correct) conclusion is that, “all of my poultry are not officers.” Nonetheless, it is not the only conclusion for there are many ways to say this that are logically congruent to this conclusion. For example, we could say, “none of the officers are poultry that belong to me.” We could say, “it is not my poultry or it is not an officer.” We could say, “It is not the case that it is my poultry and an officer.”

Let us return to the example and note that:

No ducks waltz.

No officers decline to waltz.

All my poultry are ducks.

We decided to denote the domain of discourse as U; the set of ducks as D; the set of things that waltz W; the set of officers O; and, the set of my poultry P.

Now drawing an Euler diagramme for the universe and the first sentence would mean drawing an Euler diagramme to illustrate D Ç W = Æ which would mean that D Í W^C.

Now superimposing the second sentence onto that Euler diagramme involves illustrating O Í W which is not very difficult:

Finally in order to illustrate all the premises we must include the third sentence. So, this is not very challenging since the third sentence means P Í D. Hence, we have:

So, a reasonable (correct; valid; true; must follow) conclusion is that, “none of my poultry are officers,” or “none of the officers are my poultry,” since we can observe P Ç O = Æ.

It stands to reason that lawyers, politicians, educators, etc. should be well-versed in logic. In government, industry, political science, and law - even mathematics – precise use of language may not be evident. Indeed, as we move on through the centuries, language itself changes; which may cause confusion.

Nonetheless, it is your responsibility to understand that reasonable conclusions may be gleaned from a set of premises but also that often (though hopefully not in your mathematics courses) someone may infer a premise or a conclusion. A two-premise one conclusion argument such that one of the premises or the conclusion is tacitly present but instated is called an enthymeme. Note that (logically) it must be the case that at least one of the premises is stated.

Example 2.5.3: Consider the following:

Crooks end up behind bars. So, John will end up behind bars.

This enthymeme is a typical example of the mis(use) of logic. The first sentence (deliberately?) does not state that the first premise, “crooks end up behind bars,” means all crooks end up behind bars (which is a ‘doozy’ of an assumption).

Let U be the domain of discourse, B be the set of people who will end up behind bars, and C be the set of crooks. Note that John is (supposedly) an individual; so, we will denote his existence with a point or an ‘x’ in the set C.

Clearly (misused?), the missing premise is “John is a crook.”

Example 2.5.4: Consider the following:

Prilosec was shown in clinical trials to heal ulcers in the stomachs of mice.

So, prilosec will heal my ulcer.

The underlying premise is that anything that heals ulcers in samples of mice in a laboratory will also work equally well on humans. The argument form may be valid; but, as you will note upon further study of mathematics, the inferred or implied premise is dubious at best.

§ 2.5 EXERCISES.

1. Determine a ‘best’ valid conclusion assuming as premises the following Dodgson syllogisms (best being defined as those conclusions which are derived from all of the premises).

A. Babies are illogical.

Nobody is despised who can manage a crocodile.

Illogical persons are despised.

B. No one takes in the Times, unless he is well-educated.

No hedge-hogs can read.

Those who cannot read are not well-educated.

C. All members of the House of Commons have perfect self-command.

No M. P. who wears a coronet should ride in a donkey race.

All members of the House of Lords wear coronets.

D. All unripe fruit is unwholesome.

All these apples are unwholesome.

No fruit, grown in the shade, is ripe.

E. Showy talkers are conceited people.

No well-informed people are bad company.

Conceited people are bad company.

F. No kitten that loves fish is uneducable.

No kitten without a tail will play with a gorilla.

Kittens with whiskers always love fish.

No educable kitten has green eyes.

No kittens have tails unless they have whiskers.

G. When I work a logic example without grumbling, you may be certain it is one I can understand. These examples are not arranged in regular order, like the examples I am used to.

No easy example ever makes my head ache.

I can’t understand examples that are not arranged in regular order, like those I’m used to.

I never grumble at an example, unless it gives me a headache.

H. Promise-breakers are untrustworthy.

Alcohol drinkers are very verbose.

A person who keeps a promise is honest.

No teetotalers are pawnbrokers.

One can trust a very loquacious person.

I. All the dated letters in this room are written on embossed paper.

None of them are in black ink, except those that are written in the third person.

I have not filed any of them that I can read.

None of them that are written on one sheet are undated.

All of them that are not crossed are in black ink.

All of them written by Thomas Brown, Esq. begin with “Dear Sir.”

All of them written on embossed paper are filed.

None of them written on more than one sheet are crossed.

None of them that begin with “Dear Sir” are written in the third person.

2. For each of the following enthymemes, determine an implied premise or conclusion that is missing. Determine whether the enthymeme is valid or invalid.

A. You stole a wheelchair from an old lady. No one but a born thief would steal a wheelchair from an old lady.

B. Capitalism is immoral, and this is immoral.

C. Republicans always cause wars. So, Bush will get us into a war.

D. When you had no sleep, you made and A on a test. So, I’m not going to sleep.

E. If John drinks beer, then he is at least 21. So, John is not yet 21.

§ 2.6 A TREATISE ON DEDUCTIVE LOGIC, SETS, AND MATHEMATICS.

It should become by this time apparent to the reader that mathematics is not only a science but uses a systematic language and is in many ways an art. It is clearly a science by simply considering its many uses and applications. Imagine your life without the consequences of mathematics: it might be a world without technology, a world without much of what the modern man considers necessities (but are in fact comforts). Mathematics, we have shown, clearly uses a language unto itself and is quite insistent on formal arguments and uses symbols which to the outsider are considerably odd if not confusing.[20]

That mathematics is an art form is, perhaps, the most ‘controversial’ opinion that the author has proposed in the previous paragraph. As we know, philosophy is concerned with ontology, epistemology, and axiology (aesthetics). The ontological is left to the philosopher and theologians, epistemology is of concern to mathematicians, and axiology is oft thought the realm of poets, painters, sculptors, and musicians. However, aesthetics also plays a part in mathematics.

Consider the Pieta by Michelangelo and The Magic Flute by Mozart. Supposedly Michelangelo ‘saw’ the sculpture in a stoned and Mozart ‘heard’ the music before it was written. There is not argument that each was a genius. There is (I hope) no argument that each created a work of art. Why then do so many not question the genius of Cantor when he ‘saw’ his famous proof on the cardinality of the reals (which you will study in Math 255)or Dedekind’s proof of the irrationality of (which you will study in Math 475) but do question the art intrinsic in mathematics?

Let us suppose there is a creative spark in each of us. Let us further suppose that each of us has a particular talent (which we may or may not be aware of). Is it so far a stretch to think that it takes more than memorisation, a calculator, and a book to really understand and create mathematics? Just as a sculptor who is taught the rudimentary principles of sculpting does not necessarily blossom into a master sculptor and a musician who is taught the rudimentary principles of music does not necessarily develop into a master composer, so too are we left with the rather humbling proposition that a student who is taught the rudimentary principles of mathematics does not necessarily mature into a master mathematician.

Indeed this course is designed to teach the student the principles of mathematics but the course, your professor, this book, nor the school can make you do the work, live up to your potential, nor become successful. That is up to you, the individual, to make happen. That we value an education and that we value mathematics is an axiological decision that we make but is not necessarily universal.

When one is making a value judgement (let us say that ‘x’ is “better” than ‘y’) one is exercising his aesthetic; he is stating not a fact but a perception that is codified by the statement he values ‘x’ over ‘y.’ Nonetheless, there must be a reason behind said value judgement; it must be justified.

In that same manner, mathematicians oft search for the most ‘elegant’ proof. A proof that is short, succinct, logically sound, subtle, or bring either new insight or unifies or refines a theory is oft valued by mathematicians and is deemed ‘best,’ ‘elegant,’ or termed by some other subjective descriptor. Our exercise in this chapter (indeed in this book) is not to search for the most elegant proof, or the most subtle, etc. ours is simply and succinctly to find one that is right. I do not give a ‘blue blaze’ about elegance, sophistication, etc. - - I am simply struggling day in and day out to avoid being wrong. So too, I argue, should you.

Nonetheless, the beauty of mathematics cannot be denied by one who claims to wish to study it, make it his life’s work, dedicate himself to teaching it to others, or who claims to need it for another career (like an engineer, physicist, econometrician, etc.). Let us consider from chapter one the following claim (example 1.4.2):

Claim: Given the premises ØA Ù C, B Þ D, and Ø(D Ù ØA). The conclusion ØB follows.

Proof:

1. ØA Ù C 1. Premise.

2. ØA 2. Law of Simplification (line1)

3. Ø(D Ù ØA) 3. Premise.

4. ØD Ú Ø(ØA) 4. DeMorgan’s Law (line 3).

5. ØD Ú A 5. Law of Double Negation (line 4).

6. ØD 6. Disjunctive Syllogism (lines 2 and 5).

7. B Þ D 7. Premise.

8. ØB 8. Modus Tollens (lines 6 and 7).

QED

If you reflect upon it notice the beauty of the logic; how the lines flow one to the other; how each is dependent on the truth value of the previous. Note too that if any of the lines are deleted then, at best, we would have an enthymeme which is not what we mathematicians desire. Let us consider the claim again:

Claim: Given the premises ØA Ù C, B Þ D, and Ø(D Ù ØA). The conclusion ØB follows.

Proof:

1. Ø(ØB)) 1. Negation of the conclusion

2. B 2. Law of Double Negation (line1)

3. B Þ D 3. Premise.

4. D 4. Modus Ponens (lines 2 and 3).

5. Ø(D Ù ØA) 5. Premise.

6. ØD Ú Ø(ØA) 6. DeMorgan’s Law (line 5).

7. Ø(ØA) 7. Disjunctive Syllogism (lines 4 and 6).

8. A 8. Law of Double Negation (line7)

9. ØA Ù C 9. Premise.

10. ØA 10. Law of Simplification (line9)

11. A Ù ØA 11. Law of Adjunction (lines 8 and 10)

12. ØB 12. Contradiction (lines 11, 1)

QED

If you reflect upon this proof notice the beauty of the logic; how the lines flow one to the other; how each is dependent on the truth value of the previous. Note too that it is longer than the first one. So, some mathematicians claim the first proof is better than the second. Others would claim the first is better than the second because it was done directly. Still other mathematicians prefer the second proof (I amongst them) since it was done indirectly and they value the indirect argument over the direct argument. Now are any of these positions right?

No, of course said positions are value judgements; what one may term ‘splitting hairs.’ Again, we return to the central point of this section: subjective value judgements have a place in society and in our lives but do not constitute truth (epistemological) and really should not be of concern to you as you pursue your mathematical education.

By a similar stance, one can see that those who claim ‘real world’ applications are better than ‘pure’ mathematics are not right; nor are those who claim ‘pure’ mathematics is better than ‘applied’ mathematics. Our concern will simply be on comprehension and understanding. Indeed, if I recall correctly, Albert Einstein was reported to have said, “As far as the laws of mathematics refer to reality, they are not certain; and as far as they are certain they do not refer to reality.” His words are certainly food for thought (pun intended).

Hence, study these basics about deductive logic - - you will use them in the rest of your coursework (hopefully). You can be assured you will need to think clearly and rationally in Math 251, 252, 255, 272, 351, 353, 355, 365, 371, 372, and 495 as well as in other courses. Study these basics about sets for they are the tools that will assist you in subsequent coursework; namely Math 251, 252, 255, 272, 351, 353, 355, 365, 371, 372, and 495 as well as in other courses. You are studying mathematics not following a sequence of appreciation courses where you marvel at the ingenuity, depth, intelligence, wit, etc. of the professor; hence, you must see to it that you learn the material! Consider the courses; what are they called? Appreciation of Math 255 for example? Love of Math 351? Let’s watch Math 353? No! They are Math 251, 252, 255, 272, 351, 353, 355, 365, 371, 372, etc. So, get to work and study!

---

[1] Note the rather odd nature of the use of words in the sentence. It is a rather circular notion that a “well defined” set has been defined; but, that is the language used - - well defined.

[2] As with logic, a slash through a symbol means not the symbol. This is standard throughout mathematics.

[3] The symbol À is not a stylised “x” (though seemingly written as such) it is aleph the first letter of the Hebrew alphabet.

[4] The three dot symbol (the ellipsis) is most problematic. Many students think that the ellipsis establishes a pattern. It does not. Consider p. p is not 3.14. It is not 3.141592. It is 3.14159265359 . . . (the decimal does not repeat or have a pattern); thus, the three dot symbol means on and on but not necessarily in a pattern.

[5] Hopefully this rudimentary waxing upon the nature of mathematics and ideas is not something which causes you, dear reader, to be distressed. If it does cause you discomfort, I am sorry. It might indicate (dare I say?) a lack of enthusiasm for studying mathematics. If this is the case, then perhaps one should spend time asking oneself why exactly he is majoring in mathematics.

[6] Note the similarity of the symbol “Í” to the symbol “£.” In a sense (naively) C is somehow less than or equal to D.

[7] Note that some mathematicians use the symbol “Ì” to mean subset rather than “Í.” So, it is important to always check to see how the symbol is being used. A student once remarked that this is rather tedious and silly. He thought that mathematicians should standardise all the notation. He has a point, but it would probably easier to fly an aeroplane to Alpha Centauri than to get even three academicians to agree on much.

[8] Again note the need for defining the universe first; for if the universe is not defined, then A¢ is ambiguous.

[9] Louis M. Rotando, Finite Mathematics, page 67, New York: D. Van Nostrand, 1980 (originally published by Litton Publishers). The generalised four set Venn diagramme was conceived by Carol Guadagni in 1974 who was a freshman at Nassau Community College in New York.

[10] Or you could have said A^C È B^C ¹ (A È B)^C.

[11] The set A is said to be finite if and only if either A is null or there exists a bijective function, f, from A to N_p for some p ÎN.

[12] Indeed it serves to illustrate the fact that one need not really understand something in order to use it. There seem to be many more people who use computers than people who understand computers.

[13] For historical purposes, the Euler diagrammes or circles came first; Venn adapted them to the (then) newly emerging study in a rigorous sense of set theory. We shall adopt the more rigorous requirements of the Venn diagramme convention and insist on specification (presumed) of a well defined universe.

[14] No answer, just silly.

[15] 3 ³ 2 by the law of addition - - since the statement 3 > 2 is true it must follow that 3 > 2 Ú 3 = 2.

[16] When one assumes the premises one assumes not only axioms, but definitions, lemmas, theorems, corollaries, etc. previous to the claim that he proved. In many instances he might not have done all the work that he is assuming, but the point is that a proof always begins with assumptions.

[17] Inductive arguments in the general sense rather than the rigorous method of proof called mathematical induction which we will see in chapter three is a valid method of proof.

[18] From the out-of-print text, Volker & Wargo. Fundamentals of Finite Mathematics, (Scranton, PA: Intext, 1972), page 2.

[19] The examples of the Dodgson syllogisms were taken from the out-of-print text, Rotando. Finite Mathematics.

[20] These symbols to the neophyte are of confusing, too, but take heart - - I am living ‘proof’ that a Philistine can learn to use the symbols, understand the symbols, and at the very least ‘get by.’