INTRODUCTORY CHAPTER: Mathematical Logic, Proof and Sets



INTRODUCTORY CHAPTER: Mathematical Logic, Proof and Sets

SECTION A Joy of Sets

By the end of this section you will be able to

• understand what is meant by a set

• understand different types of sets

• plot Venn diagrams of set operations

• carry out set operations

This section is straightforward. You will need to understand set theory notation. Once you have digested this notation then the remaining material is routine mathematical work.

A1 Introduction to Set Theory

What does the term set mean?

A set is a collection of objects and these objects are normally called elements or members of the set. The following are examples of sets:

1. The numbers 1, 2, 3 and 4.

2. Students who failed the mathematics exam.

3. A pack of cards.

4. European capital cities.

5. All the odd numbers.

6. The roots of the equation [pic].

A set can be described in various ways:

i. By listing all the elements of the set. For example in 1 above the set can be written as [pic]. The curly brackets, [pic], capture the set and each element in the set is separated by a comma.

ii. By listing the first few elements to give an indication of the pattern of the set. For example [pic]. This is the set in number 5 above. Note that the 3 dots (ellipses), [pic], represents the missing members when there is a pattern.

iii. By describing a property of the set such as [pic].

iv. By stating a mathematical expression like

[pic]

What does the set D mean?

The set D consists of the elements x such that x satisfies the quadratic equation [pic]. The vertical line, [pic], in the set is read as ‘such that’. Hence the set D has members x such that [pic].

In some mathematical literature the above set D is written as

[pic]

The vertical line is replaced by the colon : However throughout this book we will use the vertical line in the curly brackets to represent ‘such that’.

In mathematical notation sets are normally denoted by capital letters such as A, B, C … X, Y … The elements or objects of the set are denoted by lower case letters such as a, b, c … x, y …

Example 1

Determine the elements of the set D given above.

Solution.

We need to solve the quadratic equation given in the set [pic].

We have

[pic]

We can write the set D as [pic] but it can be written as [pic]. The order of the elements in a set does not matter.

Hence the set [pic]. The order of the members of the set does not matter, that is

[pic]

We denote the number 7 is a member of the set D by

[pic]

The symbol [pic] means ‘is a member of’. Since 2 is not a member of this set therefore we denote this by [pic] and read it as ‘2 is not a member of the set D’.

In general

[pic] means x is a member of the set A

What does [pic] mean?

[pic] means x is not a member of the set A

Example 2

Let A be the set of all even numbers. Write the set A in set notation.

Solution.

We can write even numbers as the symbol x such that x is an even number, thus we have

[pic]

What is the size of the set A?

It is an infinite set. Note that sets maybe infinite or finite. Can you think of an example of a finite set?

The above set [pic].

A2 Types of Sets

There maybe no elements in a set. What do you think we call a set which has no members?

The empty set or the null set. The empty set is normally denoted by [pic] (The Greek letter phi). Can you think of any examples of the empty set?

[pic]

[pic]

Remember prime numbers are greater than 1.

What does the universal set mean?

Universal set is the set of all the elements under consideration. For example if we are discussing prime numbers then the universal set will be the set of all prime numbers. The universal set is denoted by [pic].

There are various types of numbers that we have used throughout our lives but they have not been placed in set form or been given a special symbol. Can you remember what types of numbers you have used?

Real numbers, natural numbers, rational numbers etc. We can give all of these their own symbol:

[pic] the set of all natural numbers 1, 2, 3, 4, … These are sometimes called the counting numbers.

[pic] the set of all integers …[pic],… This is the set of all whole numbers.

[pic] the set of all rational numbers. These are numbers which can be written as ratios or fractions such as [pic] etc. Note that all the integers are also in this set because numbers like 6 can be written as [pic].

Numbers such as [pic] etc cannot be written as fractions so these are not rational numbers. These are called the irrational numbers.

[pic]the set of all real numbers. This is the set of all rational and irrational numbers. For example [pic]2.333 … are all members of [pic].

[pic] the set of all complex numbers. This set contains all the real numbers as well as numbers such as [pic] which is not a real number. Complex numbers are normally written as [pic] where i denotes an imaginary number and is equal to [pic].

All the above sets [pic] are examples of infinite sets.

Example 2

Determine the elements of the set [pic].

Solution.

The factorized quadratic has the solutions

[pic]

Does the set A contain both these elements 3 and [pic]?

No because the set A has the qualification [pic]. What does this notation [pic] mean?

x is a member of the set of natural numbers which means x is a counting number. Since [pic] (rational) is not a natural number therefore it cannot be a member of the set A. Thus the set A only has the element 3, that is [pic].

The set A only has one element 3 and in general a set with only one element is called a singleton.

Definition (I.1). Any set with precisely one element is called a singleton.

Example 3

Write the following statements in set notation:

a) The set of positive real numbers excluding 0.

b) The set of negative integers.

c) The set of rational numbers between 0 and 1.

Solution.

a) The set of positive real numbers can be written as a symbol x which represents a real number such that it is greater than 0:

[pic]

What does [pic] in this set mean?

[pic] means x is a real number.

b) What is the symbol for the set of integers?

[pic] represents the set of all integers. The set of negative integers can be written as x which is an integer such that it is less than 0:

[pic]

c) What is the symbol for the set of rationals?

[pic] represents the set of rationals (Q for quotient). The set of rationals between 0 and 1 can be written as:

[pic]

A3 Venn Diagrams

Venn diagrams are a graphically way of representing sets. Venn diagrams were introduced by John Venn.

[pic]

Fig 1 John Venn

1834 to 1923

In 1883 John Venn was elected as a Fellow of the prestigious Royal Society. At this time he started to take an interest in history and by 1897 he published a history of his college Gonville and Caius, Cambridge.

Consider the set[pic]. What are the elements of the set A?

A is the set of integers which lie between [pic] to 2. Thus the elements are [pic] and 2. A Venn diagram of this looks like:

Fig 2

The U in the bottom right hand corner of the rectangle is the universal set which means it includes every element under consideration. The members of the set A lie within the boundary of the oval shape as shown in Fig 2.

We can use Venn diagrams to display set operations.

A4 Union and Intersection of Sets

From the age of 5 we have added and subtracted numbers. In a similar fashion we can carry out similar operations on sets. These operations are called union and intersection.

What is the union of two sets?

The word union in everyday language means combining of 2 or more things. Union of two sets is the combination of all elements in both sets.

Definition (I.2). The union of two sets A and B is the set of all the elements belonging to set A or set B. The union of two sets A and B is denoted in set theory notation as [pic] and

[pic]

In terms of a Venn diagram we can draw this as:

Fig 3 [pic](A union B) is shaded

The other operation on sets is intersection. What does intersection mean in everyday language?

Intersection means crossroads. Intersection of two sets A and B is the set of all elements which belong to both sets A and B.

Definition (I.3). The intersection of two sets A and B is the set of all the elements belonging to set A and set B. The intersection of two sets A and B is denoted in set theory notation as [pic] and

[pic]

The Venn diagram of [pic] is:

Fig 4 [pic](A intersection B) is shaded

Example 4

Let [pic] and [pic]. Determine the sets [pic] (A union B) and [pic] (A intersection B).

Also draw the Venn diagrams of these sets.

Solution.

What does [pic] mean?

A union B is the set of all elements which are in the set A or B. Thus we have

[pic]

Which elements does the set [pic] have?

[pic]is the set of all elements which belong to both the sets A and B. Which elements are common to both the sets [pic] and [pic]?

Only the number 3 belongs to both sets A and B. Therefore

[pic]

Note that [pic] is a singleton.

The Venn diagrams of [pic] and [pic] are

Fig 5 [pic]is shaded [pic]is shaded

Example 5

Let [pic] and [pic]. Determine the sets [pic] and [pic]. Draw Venn diagrams of [pic] and [pic].

Solution.

What does the notation [pic] mean?

[pic] is the set of all the even and odd numbers which means it is the set of all the integers. Which symbol is used to represent all integers?

[pic] is the set of all integers. Thus we have [pic].

What is [pic] equal to?

There is no element which is common to both the set of even and odd numbers. Therefore the intersection of these sets is empty. What is the symbol for the empty set?

The Greek letter phi, [pic], denotes the empty set. Thus we have

[pic]

Venn diagrams of these is:

[pic] is shaded [pic]

Fig 6

In general if for given sets A and B we have [pic] then we say the sets A and B are disjoint.

We can extend the above set operations to 3 or more sets.

Example 6

Let[pic], [pic] and [pic]. Determine the elements of the following sets:

(a)[pic] (b) [pic]

What do you notice about your results?

Draw a Venn diagram of the set [pic].

Solution.

(a) How do we find the elements of [pic]?

First we determine [pic]. Thus [pic] is the set of elements which are common to both sets [pic] and [pic]. That is

[pic]

[pic] is the set of elements which are in set [pic] or set [pic]. Which elements are in either of these sets?

It is all the elements in set A and the element 9:

[pic]

(b) How do we find the elements of [pic]?

Well [pic] is the set of elements which belong to either of these given sets [pic] or [pic]:

[pic]

Similarly the elements in set [pic] or [pic] are

[pic]

What does [pic] mean?

It is the set of elements which are common to both [pic] and [pic]. Which elements belong to both these sets [pic] and [pic]?

[pic]

Note that the answers to parts (a) and (b) are the same, that is

[pic]

Venn diagrams of [pic] are

Fig 7

Shading in the union of these sets of Fig 7 gives:

Fig 8

[pic]

The last observation, [pic], is true for all sets and we will prove this result in later sections. You may like to convince yourself of this result by drawing general Venn diagrams.

A5 Other Set Operations

What does the word complement mean in everyday language?

Complement is something which completes or fills up. In set theory the complement of a set A is the elements which are in the universal set but not in set A.

Definition (I.4). The complement of a set A is denoted by [pic] and is defined to be

[pic]

What does the Venn diagram of [pic] look like?

[pic] (complement of A) is shaded

Fig 9

You may see [pic] written as [pic] in other mathematical literature.

Example 7

Let [pic] and universal set [pic]. Determine [pic].

Solution.

What does [pic] mean?

The universal set is the set of natural numbers 1, 2, 3, 4 … Note that E is the set of even numbers. What does [pic] mean?

[pic]is the set of elements which are not in the set E but are in the universal set. This means numbers which are not even but are natural numbers. What numbers are these?

The odd numbers. Thus [pic].

In mathematics what does difference mean?

Difference is subtraction. Given two sets A and B the difference of A and B is the set of elements which belong to the set A but not to B. [Subtract the members of B from A].

Definition (I.5). The difference of set A and set B is denoted by [pic] and is defined to be

[pic]

What does the Venn diagram of [pic] look like?

Fig 10 [pic] is shaded

In other mathematics literature you might find the following notation for difference of two sets such as [pic] or [pic].

Example 8

Let [pic] and [pic] be two given sets. Find [pic].

Solution.

What does the set theory notation [pic] mean?

From the set A subtract the members of set B. This means from the set [pic] we delete members which are in the set [pic] and the remaining set is [pic]. Thus

[pic]

There is one more difference in set theory called symmetric difference. The symmetric difference between two sets A and B are the elements which are in set A or set B but not in both.

Definition (I.6). The symmetric difference of set A and set B is denoted by [pic] and is defined to be

[pic]

What does the Venn diagram of this look like?

Fig 9 [pic]is shaded

In the exercises we will show the result [pic] . This means [pic] is the set of [pic] take away the elements of [pic].

Example 9

Let [pic], [pic] and [pic]. Find [pic], [pic] and [pic].

Solution.

The elements in[pic] are members which are in the set A or B but not in both. Which elements are in both sets [pic] and [pic]?

The elements 1 and 3 are common to both sets A and B. Thus removing elements 1 and 3 from the union of sets A and B gives

[pic]

Similarly we can find[pic]. What members are common between the sets [pic] and [pic]?

1 and 4 therefore removing these from [pic] gives

[pic]

To find [pic] we delete the members which are in common between the sets [pic] and [pic]. Only the element 1 is common therefore

[pic]

Example 10

For the Venn diagram of Fig 9 above show that

[pic]

Solution.

We first shade in [pic] and then [pic] which is everything outside [pic]:

Fig 10

Similarly for [pic]we shade in [pic] and [pic] and then take the union of these 2 sets, [pic].

Fig 11

Notice that the same regions are shaded in Fig 10 and 11 for [pic] and [pic]. We have [pic] for the sets shown.

You can show results of set theory by using Venn diagrams like these but they are only valid for the sets shown. We will prove results of set theory more rigorously in later sections by using algebra of subsets.

SUMMARY

A set is a collection of objects. Capital letters are used to represent sets and lower case letters for elements of sets. The notation [pic] means the element x is a member of the set A.

There are various types of sets such as the empty set [pic], the universal set U and the sets which give the type of numbers:

[pic] Natural numbers. These are positive whole numbers.

[pic]Integers. These are whole numbers.

[pic]Rational Numbers. These are ratios of integers.

[pic]Real numbers. These are rational as well as irrational numbers.

[pic] Complex numbers. These are numbers of the form [pic].

Any set with just one element is called a singleton.

Let A and B be sets. Then we have the following set operations:

The union of two sets is given by [pic]

The intersection of two sets is given by [pic]

The complement of a set A is given by[pic].

The difference of sets A and B is given by [pic]

The symmetric difference of sets A and B is given by

[pic]

-----------------------

such that

John Venn was born in Hull, England in 1834. His father and grandfather were priests and John was also groomed for a similar post. In 1853 he went to Gonville and Caius College Cambridge and graduated in 1857 becoming fellow of the college. For the next 5 years he went into priesthood and returned to Cambridge in 1862 to teach logic and probability theory.

John Venn is popular known as the person who developed a graphically way to look at sets and this graph become known as a Venn diagram. The sets were represented by oval or circular shape figures but they can be any shape.

[pic]

[pic]

[pic]

E

O

[pic]

[pic]

[pic]

[pic]

[pic]

[pic]

[pic]

[pic]

[pic]

[pic]

[pic]

[pic]

[pic]

................
................

In order to avoid copyright disputes, this page is only a partial summary.

Google Online Preview   Download