Vectors and Vector Operations



1.8 Sets

In the section we shall look at sets. Sets and set operation closely mirror logic and the logical operations that we discussed in sections 1.1 – 1.4.

1.8.1 Sets and Set Operations

A set is a collection of items.

There are similarities between sets and lists which were discussed in the previous section. The major difference is that order is not important in a set, nor is the number of repetitions. For example,

(1) A = {John, Mary, Paul}

is an example of a set. It is has three members or elements which are

John

Mary

Paul

As this example illustrates, sometimes we pick a letter to stand for a certain set. In this case it is A. The following all represent the set A because neither the order of the items nor the number of repetitons matters for a set.

A = {John, Paul, Mary}

A = {Paul, John, Mary}

A = {Paul, Mary, John}

A = {Mary, John, Paul}

A = {Mary, Paul, John}

A = {Mary, Paul, John, Paul}

A common convention in many books is to enclose the items in parentheses ( , , ) to represent a list and to enclose the items in braces { , , } to represent a set. However, many programming languages don't follow this convention. For example, Mathematica encloses the items in a list in braces.

(1) illustrates one common way to specify a set, namely as a list of the members of the set enclosed in braces. Another common way to specify a set is by means of a condition that characterizes the members of the set. For example, we might be interested in the set B of solutions to the equation x2 – 5x + 6 = 0. We can write this in the following ways.

(2) B = set of solutions of x2 – 5x + 6 = 0

= {x : x2 – 5x + 6 = 0}

The second way {x : x2 – 5x + 6 = 0} has the general form {x : P(x)} where P(x) is a predicate. {x : P(x)} represents the set of elements x for which P(x) is true. If we note that x2 – 5x + 6 = (x-2)(x-3) then one sees that {x : x2 – 5x + 6 = 0} = {2, 3}.

Somethings are more natural to view as lists while others are more natural to view as sets. For example, the coordinates (x, y) of points in the plane are lists since order is important. However, the example (2) of the solutions to x2 – 5x + 6 = 0 may be more natural to view as a set if we don't care about the order. If we did care about the order, then we could view it as a list.

People who work with sets usually distinguish between an object and the set that consists of just that object. For example,

Tom Cruise = a well know actor

{Tom Cruise} = set consisting of the one element Tom Cruise

Tom Cruise ( {Tom Cruise}

An interesting example is when we do an internet search. If we Google the phrase "John Wayne" the result is a list of files on computers on the internet which contain the term "John Wayne". However, this list could be regarded as a set if the order of the items and duplications are unimportant.

Set Operations

There are a number of interesting operations involving sets. We begin with the following.

membership

is-a-subset-of

union

intersection

difference

symmetric difference

complement

The first two produce values of true or false, i.e. they are predicates. The last five are operations in the usual sense, i.e. they take sets and produce new sets. In the following A and B stand for sets and x stands for an object that might or might not be an element of a set.

1. Membership

x ( A is a symbolic form of the phrase "x is a member of A"

x ( A is a symbolic form of the phrase "x is a not a member of A"

For example,

2 ( {x : x2 – 5x + 6 = 0}

5 ( {x : x2 – 5x + 6 = 0}

x ( A is actually a predicate. It evaluates to true if the object x is a member of A and false if not. From this point of view

2 ( {x : x2 – 5x + 6 = 0} evaluates to true

5 ( {x : x2 – 5x + 6 = 0} evaluates to false

2. Is-a-subset-of

A ( B is a symbolic form of the phrase "A is a subset of B" and means every member of A is a member of B

A B is a symbolic form of the phrase "A is not a subset of B" and means some member of A is not a member of B

We often say "B contains A" if A is a subset of B and "B does not contain A if A is not a subset of B. For example,

{2, 4} ( {1, 2, 4, 5}

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

A ( B is also a predicate. It evaluates to true if every member of A is a member of B and false if not. From this point of view

{2, 4} ( {1, 2, 4, 5} evaluates to true

{2, 4} ( {1, 2, 3, 5} evaluates to false

In fact A ( B is equivalent to (x ( (x(A) ( (x(B) ).

Often we represent sets by regions in the plane. Such a picture is called a Venn diagram. For example, we might represent the set A by a circle, including its interior, as indicated at the right (

With this in mind, here is a case where A ( B.

While, here is a case where A B

There is an important set that comes up frequently. It is the set analogue of the number 0.

( = { } = the empty set = the set with no elements

One has x ( ( for all x and ( ( A for all A. An example of the empty set is

{x : x is a person on Earth who has visited Mars}

Another type of set that comes up frequently is a universal set which is a set that contains all of the sets being considered in a certain situation. Often it is denoted by U.

U = a universal set = a set that contains all sets being considered in a certain situation

What set to choose as a universal set depends on the situation. If we are considering sets of real numbers, then we might choose the set of all real numbers as the universal set. Sometimes a writer may not explicitly indicate what set he is using as a universal set. A universal set is important when we work with the complement operation discussed below.

Now we look at 5 operations that take sets and produce new sets. The first two and last two operations are the set analogues of or, and, exclusive-or and not. In this discussion we will represent A and B by the interior of circles in the plane as in the picture at the right. A is the interior of the left circle and B is the interior of the right one. We draw them as overlapping, although in general they might not be.

Here is a table that summarizes these 5 operations. Below the table is more discussion of each one.

|Operation |Symbol |Definition |Logical |Venn diagram |Example |

| | | |analogue | |A = {John, Mary, Paul} |

| | | | | |B = {Sue, Bill, Mary} |

|union |A ( B = A + B |Set of objects in A or |or | |{John, Mary, Paul, Sue, |

| | |B | | |Bill} |

|intersection |A ( B = AB |Set of objects in A and|and | |{Mary} |

| | |B | | | |

|difference |A \ B = A - B |Set of objects in A but| | |{John, Paul} |

| | |not B | | | |

|symmetric |A ( B |Set of objects in A or |exclusive or | |{John, Paul, Sue, Bill} |

|difference | |B but not both | | | |

| |A' = | |not | |All people in the universe|

|complement | |Set of object not in A | | |except John, Mary and Paul|

3. Union

The union operation is the set analogue of the logical or operation. If A and B are sets then

A ( B

A + B

are two ways of denoting the union operation applied to A and B. A ( B is much more common, but A + B is useful if we are doing algebra with the set operations.

A ( B denotes the set of all objects that are either in A or in B or in both.

A ( B = {x: x ( A or x ( B} = {x: (x ( A) + (x ( B)}

For example, if

A = {John, Mary, Paul}

B = {Sue, Bill, Mary}

then

A ( B = {John, Mary, Paul, Sue, Bill}

In terms of the circles, A ( B is the set of points in the plane that are in the A circle or the B circle or both.

4. Intersection

The intersection operation is the set analogue of the logical and operation. If A and B are sets then

A ( B

AB

are two ways of denoting the intersection operation applied to A and B. A ( B is much more common, but AB is useful if we are doing algebra with the set operations.

A ( B denotes the set of all objects that are in both A and B.

A ( B = {x: x ( A and x ( B}

= {x: (x ( A) (x ( B)}

For example, if

A = {John, Mary, Paul}

B = {Paul, Bill, Mary}

then

A ( B = {Mary, Paul}

In terms of the circles, A ( B is the set of points in the plane that are both the A circle and the B circle.

5. Difference

The difference operation is the set analogue of the logical expression pq'. If A and B are sets then

A \ B

A - B

are two ways of denoting the difference operation applied to A and B.

A - B denotes the set of all objects that are in A but not in B.

A - B = {x: x ( A and x ( B} = {x: (x ( A) (x ( B)'}

For example, if

A = {John, Mary, Paul}

B = {Sue, Bill, Mary}

then

A - B = {John, Paul}

In terms of the circles, A - B is the set of points in the plane that are in the A circle but not in the B circle.

6. Symmetric Difference

The symmetric difference operation is the set analogue of the logical exclusive or operation. If A and B are sets then

A ( B

is a common way of denoting the symmetric difference operation applied to A and B.

A ( B denotes the set of all objects that are in A or B but not both.

A ( B = {x: x ( A or x ( B and x ( A ( B}

= {x: (x ( A) ( (x ( B)}

For example, if

A = {John, Mary, Paul}

B = {Sue, Bill, Mary}

then

A ( B = {John, Paul, Sue, Bill}

In terms of the circles, A ( B is the set of points in the plane that are in the A circle or in the B circle but not in both circles.

7. Complement

The difference operation is the set analogue of the logical not operation. In order to define the complement operation we first need to decide upon a "universe". A universe is a set U that contains all the sets arising in the current discussion. In a given situation there will be many possible sets that one can take for the universe, but often there is one that is more natural than all the others. For example, if we are considering sets of real numbers, then the universe could be the set of all real numbers. Having decided upon a universe U, then if A is a subset of this universe, then the complement of A is the set of objects in the universe which are not in A. Two common notations for it are

A' and

Thus

A' = {x: x ( U and x ( A} = {x: (x ( U) (x ( A)'} = U - A

Suppose, for example, we are considering various sets of people and the people in all these sets are people who work in the accounting department at DataCo. For the universe we could take the set U of all people in the accounting department at DataCo. Suppose it is

U = {Allen, Bill, Carl, Doreen, Ellen, Fred, Gina, Henry, Isabell, John}

Suppose with this universe

A = {Carl, Ellen, Gina, John}

then

A' = {Allen, Bill, Doreen, Fred, Henry, Isabell}

Pictorially, let's represent the universe by the set of points U inside a certain rectangle and A be the set of points inside a circle that is contained in the rectangle. Then A' is the set of points in the rectangle that are not in the A circle.

Example 1. Suppose the universe is the students in the Engineering 390 class, namely

U = {Alan, Barbara, Carl, Doreen, Ellen, Fred, Gail, Henry, Karen}

= {a, b, c, d, e, f, g, h, k}

Suppose

E = set of students in U who are ECE majors = {c, d, e, h, k}

F = set of students in U whose age is over 25 = {b, c}

M = set of students in U who are ME majors = {f, g, h, k}

T = set of students in U who gpa is above 3.5 = {a, e, g, h}

How would you represent symbolically the set of students in U who are

ECE majors not over 25 years of age

or

ME majors whose gpa is above 35 years of age

but not both

Answer: (E – F) ( (MT)

Determine the members of this set.

E – F = {d, e, h, k}

MT = {g, h}

(E – F) ( (MT) = {d, e, g, k}

The Algebra of Set Operations

Because union, intersection, complement and symmetric difference are the set analogues of the operations of the logical or, and, not and exclusive or operations, they satisfy the same identities these logical operations in Boolean algebra. In the following A, B, C are sets and U is a universe that contains all them. A+B denotes the union of A and B, AB denotes the intersection of A and B, etc. Then the following are true

(3) AB = BA A + B = B + A commutative

(4) A(BC) = (AB)C A + (B + C) = (A + B) + C associative

(5) A(B + C) = AB + AC A + (BC) = (A + B)(A + C) distributive

(6) (AB)' = A' + B' (A + B)' = A'B' DeMorgan

(7) A – (B + C) = (A – B)(A – C) A – BC = (A – B) + (A – C)

(8) AU = A A + ( = A identity

(9) A( = ( A + U = U domination

(10) AA = A A + A = A idempotent

(11) AA' = ( A + A' = U complement laws

(12) (A')' = A double complement law

One way to verify set identities such as these is to express each side of the equation in terms of a logical expression using logical operations and then use logical identities to verify the two logical expressions are equivalent. Here is an example illustrating this method.

Example 2. Show that the left identity in (7) is valid, i.e. A – (B + C) = (A – B)(A – C).

For the left side we have

A – (B + C) = {x: (x ( A) (x ( (B + C))'}

= {x: (x ( A) [(x ( B) + (x ( C)]'}

= {x: p(q + r)'}

where

p = (x ( A)

q = (x ( B)

r = (x ( C)

For the right side we have

(A – B)(A – C) = {x: (x ( (A – B)) (x ( (A – C ))}

= {x: [(x ( A)(x ( B)'] [(x ( A)(x ( C)']}

= {x: (pq')(pr')}

So, to show A – (B + C) = (A – B)(A – C) we must show p(q + r)' = (pq')(pr'). However, using DeMorgan one has p(q + r)' = p(q'r') = pq'r'. On the other hand (pq')(pr') = ppq'r' = pq'r'. So p(q + r)' = (pq')(pr') and hence A – (B + C) = (A – B)(A – C).

There is another method for proving assertions about set operations that is often more intuitive to use, especially when the assertion is something different from an identity. This method is a pictorial representation of a truth table using a Venn diagram. We illustrate this by another proof of A - (B + C) =  (A - B)(A - C).

At the right is a Venn diagram representing all three of the sets A, B and C and all the different subsets formed by intersecting these sets and their complements. In particular, eight of these regions represent the eight possible combinations of ways that an element x can either be an element of or not be an element of each of the three sets A, B and C. We can represent these eight possible combinations by the following truth table along with the corresponding region in the Venn diagram.

With this in mind we determine which regions comprise A – (B + C) and (A – B)(A – C). One has

B + C = R1 + R2 + R3 + R5 + R6 + R7

A – (B + C) = R4

On the other hand

A – B = R4 + R5

A – C = R4 + R6

(A – B)(A – C) = R4

Since A – (B + C) = R4 and (A – B)(A – C) = R4 we conclude A – (B + C) = (A - B)(A - C).

The Power Set

Sometimes we want to compare all subsets of a given set using some criterion. The set of all subsets of a given set is the power set of the given set A and is denoted by ((A). Let

A = a set

((A) = set of all subsets of A

Example 3. Let D be the set of people in the database department of Computer Services Corporation. In fact,

D = {Alice, Bob, Colleen} = {a, b, c}

Then

((D) = { (, {a}, {b}, {c}, {a, b}, {a, c}, {b, c}, {a, b, c} }

An important database project just came in and we need to select a team from the database department to work on it. Let T be the set of possible teams. In fact

T = ((D) – {(} = { {a}, {b}, {c}, {a, b}, {a, c}, {b, c}, {a, b, c} }

There is a connection between ((D) and a truth table and also between a set of bit strings.

With this interpretation, one has

T ~ { 000, 001, 010, 011, 100, 101, 110, 111}

This is useful when we want to run through all subsets of a given set evaluating them with respect to some criterion.

There are identities (and incorrect identities) involving power sets.

Example 4. Is ((A ( B) = ((A) ( ((B) for any two sets A and B.

Solution. In words is every subset of A ( B a subset of A or a subset of B or both. The answer is No, since if A does not contain B or B does not contain A there will be sets that contain elements of A and B that are not subsets of A or B. For example, let

A = {1, 2, 3} B = }3, 4, 5}

Then

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

and {1, 5} ( ((A ( B) but {1, 5} ( ((A) ( ((B).

Cartesian Products

In section 1.7 we considered lists. In many situations we want to consider all lists where the elements come from certain sets. This gives rise to the Cartesian product of sets. Let

A1, A2, …, An = n sets

A1 ( A2 ( … ( An = set of all lists (a1, a2, …, an) where a1 is in A1, a2 is in A2, … an is in An.

= {(a1, a2, …, an): a1 ( A1, a2 ( A2, … an ( An}

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

A - B

A ( B

B

A

A ( B

B

A

B

A

A

B

A

B

A

B

A

A ( B

B

A

A'

U

A

A

B

A

A

B

A

A

C

B

A

R7

R6

R5

R4

R3

R2

R1

R0

|x ( A |x ( B |x (C |Region |

|0 |0 |0 |R0 |

|0 |0 |1 |R1 |

|0 |1 |0 |R2 |

|0 |1 |1 |R3 |

|1 |0 |0 |R4 |

|1 |0 |1 |R5 |

|1 |1 |0 |R6 |

|1 |1 |1 |R7 |

|Subset S |x ( S |x ( S |x (S |Bit string |

|( |0 |0 |0 |000 |

|{c} |0 |0 |1 |001 |

|{b} |0 |1 |0 |010 |

|{b, c} |0 |1 |1 |011 |

|{a} |1 |0 |0 |100 |

|{a, c} |1 |0 |1 |101 |

|{a, b} |1 |1 |0 |110 |

|{a, b, c} |1 |1 |1 |111 |

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

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

Google Online Preview   Download