Set OperatorsSet TheoryA set is a collection of objects, or elements. Typically, the typeof all the elements in a set is the same. (For example, all theelements in a set could be integers.) However, it is possible tohave different types of elements in a set. (An analogy for this isthat usually a bookbag contains just books. But sometimes itmay contain other elements such as pencils and folders aswell.)We have two usual methods of denoting the elements in a set:1) Explicitly list the elements inside of a set of curly braces({}),as follows: {1, 2, 3, 4}2) Give a description of the elements in a set inside of a set ofcurly braces as follows: { 2x | xN }.In order to understand the second method, we must define thevarious symbols that are used in this notation. Here is a list ofthe symbols we will be using:| - translates to “such that”- “is an element of”- “is a proper subset of” - “is a subset of”Now we have to define what a subset is. A subset is also a set.So, if we have sets A and B, AB if for all xA, xB.In layman’s terms, a set A is a subset of a set B, if all theelements in the set A also lie in the set B. Note: A B iff A B AB.We still have to define what { 2x | xN } really means. Here it isin English:“The set of all numbers of the form 2x such that x is an elementof the natural numbers.” (Note: The set N denotes the naturalnumbers, or the non-negative integers, according to the book.)So, the set above could also be listed as {0, 2, 4, 6, ...}Now that we have gotten that out of the way, let’s talk aboutthe empty set(). The empty set is a set with no elements in it.In our standard notation, we could denote it as {}. It is alsovery common to use , to denote the empty set. It’s important to denote that the following are not equal: , {0}, and 0.The first two are sets, while the third is an element. However,the empty set has no elements while {0} contains one element,zero.Typically, sets will be denoted by uppercase letters. There aresome other sets we should be familiar with since they come upso often. Here they are:Z = {0, 1, -1, 2, -2, ...} (the set of integers)N = {0, 1, 2, 3, ...} (the set of non-negative integers)Z+ = {1, 2, 3, ...} (the set of positive integers)Q = {a/b | a, bZ b0}R = the set of real numbers...Also, one last definition... |A| for a set a is known as the“cardinality” of A, which equals the number of elements in A.Set OperatorsNow we are ready to discuss set operators. We can use severaloperators on existing sets to define new ones. The first twooperators are binary operators, union and intersection. In eachof these examples, let A and B be sets.union() : A B = { x | xA xB } intersection() : A B = { x | xA xB }complement():A ={ x | xA }relative complement(–) : B – A = { x | xB xA }In English, the union of two sets contains all elements in eitherset and the intersection of two sets contains all elements inBOTH sets.To define the complement, we must define what an universe is.For each set, there is a possible set of elements. This possibleset of elements is known as the universe. Typically, you will betold what the universe is for each problem. (Most of the time itis the set of integers, or real numbers...) The complement of aset contains all the elements in the universe that are NOT inthe set itself.You can think of relative complement as the subtractionbetween two sets. B – A refers to a set that subtracts out all theelements from A out of B. Now if a particular element of Awasn't in B to begin with, there’s no need to take it out of B atall... Also, an identity that we can use is that B – A = B A.Equality of SetsThere are three essentially different ways that we can show twosets to be equal. The first two are going to be analogous tomethods used in logic.1) Use the laws of set theory.2) Use the table method.I will go through the laws of set theory, showing you why theywork through something called a Venn Diagram. Then we will consider working through showing A = (A – B) (A B).Set Laws1. A = A Law of DoubleComplement2. (A B) = A B De Morgan’s Laws (A B) = A B3. A B = B A Commutative Laws A B = B A4. A (B C) = (A B) C Associative Laws A (B C) = (A B) C5. A (B C) = (A B) (A C) Distributive Laws A (B C) = (A B) (A C)6. A A = A, A A = A Idempotent Laws7. A = A, A U = A Identity Laws8. A A = U, A A = Inverse Laws9. A U = U, A = Domination Laws10. A (A B) = A Absorption Laws A (A B) = ANow, using these laws we can prove that A = (A – B) (A B),for all sets A and B.(A – B) (A B) = (A B) (A B), defn of –= A (B B), distributive law= A U, Inverse law= A, Identity lawTable MethodAnother way to think of showing set equality is to look at aVenn Diagram and consider each possible position an arbitraryelement can be located.In essence, we know that two sets A and B are equal if xA xB, for an arbitrary element x. What we can do is anexhaustive search of all the “places” an element x could like ina Venn diagram. If, in each situation, the above bidirectionalimplication holds, they we proven the statement for anarbitrary x, proving the two sets to be equal.Let’s look at an example showing thatA = (A – B) (A B)A B A - B A B (A – B) (A B)0 0 0 0 00 1 0 0 01 0 1 0 11 1 0 1 1 Finally, a third way to show that two sets A and B are equal isto prove that A B AND B A.Let’s use this idea to show once again that A = (A – B) (A B).Part 1: Show that A (A – B) (A B).Consider an arbitrary element x A. We must show thatx (A – B) (A B).Now, consider the situation that xB. In this particularsituation, by definition, we know that x(A – B), and thusMUST BE an element of (A – B) (A …
View Full Document
Unlocking...