Basic Set Theory

BASIC SET THEORY

A set can be thought of as

"something that holds things"

More specifically, for every "object" in the universe, a set S either contains it or it doesn't. If S contains x we write xÎS ("x is in S" or "x is a member of S " ), otherwise we write x S.

Many sets can be given by listing their elements. We write out a set given like this by putting the list inside curly braces.

{ JOHN, PAUL, RINGO, GEORGE}

Sometimes we just show enough to set the pattern , but this is informal (sometimes even sloppy) notation:

{1,2,4,8,…,1024} (an 11-element set)

{1,2,4,… } (an infinite set)

Many more sets can be given by a rule for determining whether something is a member.

We write out a set given like this by giving a "dummy" element, a colon, and the test such an element has to satisfy:

{x: x is at least 5 feet tall}

{x: x is divisible by 2} these are the

{y: y is divisible by 2} same set!

The variables x and y above are known as “dummy variables”; they have no meaning outside the expression. That’s why we can change the name.

The question of exactly how a set can be defined is a very deep one. There is no one right answer; it's a "choice of rules of play"

like figure skating vs ice dancing or Canadian football vs American football.

We can leave this one to the mathematicians.
NOTE: An object is either in a set or not in it. Nothing can be "half in" , "in twice", etc.

{A,B,C} and {A,A,B,C} are the same set.

If set A and set B have the same elements, then by definition they are two names for the SAME SET. If either has an element the other doesn't, they are DIFFERENT SETS. This is called the "extensive property" of sets and it is very important.

In particular, the order does not matter.

{A,B,C} and {C,B,A} are the same set.

A set may have no elements. This is called an empty set.

THEOREM: There is only one empty set (or, equivalently, all empty sets are the same.)

Proof: if A is an empty set and B is an empty set, then they both have no elements, so they are the same set.

So the set of unicorns and the set of Sasquatches are (probably) the same set!

We often call this set  , pronounced "the empty set" rather than "phi".

A set may have one element. To every object x there corresponds a set {x } called the singleton set containing x .

THEOREM: {x } = {y } if and only if x = y .

Proof: If {x } = {y }, then:

Any member of {y } is also a member of {x }.

Any member of {x } is equal to x itself.

So any member of {y } is equal to x itself.

So {y } is the singleton set {x }.

The first several weeks of a course in set theory are filled with annoying theorems like

this that prove very obvious things:

S=S ("reflexivity")

if S=T then T=S ("symmetry")

if R=S and S=T then R=T ("transitivity")

We shall skip most of this!

Sets can be finite or infinite. (A rigorous definition of "finite set" will have to wait, but our intuition should be adequate here.)

Every finite set has a cardinality or size. This is often written as |S| or #(S). For finite sets this is just the number of elements.

THEOREM: Two finite sets have the same size if there is a 1-1 pairing between their elements.

Fire John

Water Paul (order here is

Earth Ringo arbitrary!!)

Air George

For infinite sets we adopt this as a definition of cardinality. The resulting math is very hard, very interesting, and not part of this course.

SUBSETS:

A set A is a subset of another set B if every member of A is also a member of B.

On a Venn diagram: B

We write AÍB. (If we know A

that some element(s) of B

are NOT in A, we can write AÌB.)

We can interpret “AÍB” as saying:

“IF x ÎA, THEN x ÎB ”.

THEOREM: If AÍB and BÍC then AÍC.

If AÌB and BÍC then AÌC.

If AÍB and BÌC then AÌC.

INTERSECTION

The intersection of two sets consists of all the elements that are common to both.

AB = {x: xA and xB}

The membership rule for the set AB is:

The element must satisfy BOTH the rule for membership of A AND the rule for membership of B.

EXAMPLES:

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

{1,3,5,7,9,…}  {1,2,3,…,10} = {1,3,5,7,9}

{1,2,3}  {4,5,6} = 

{Bill, Mary}  {Mary, Jim, Jane} = {Mary}

{A,B,C,D,E}  {D,N,T,O} = {D}

There are lots of obvious, easy, and annoying theorems about intersection. Many of them look a lot like addition or multiplication facts.

AA = A

A = 

AB = BA

(AB)C = A(BC)

These can all be proved by going back to the definition of intersection.

We can visualize "intersection" using a Venn diagram:

UNION

Another widely used set operation is union.

The union of two sets consists of all the elements that are in one set, or the other, or both.

AÈB = {x: xA or xB}

The membership rule for the set AB is:

The element must satisfy EITHER the rule for membership of A OR the rule for membership of B.

Remember, even if an element appears in both sets, it appears only once in the union.

EXAMPLES:

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

{1,3,5} È {2,4,6} = {1,2,3,4,5,6}

{1,2,3} È {2} = {1,2,3}

{oats, peas,beans} È {beans, weiners} =?

Unions can be visualized with Venn diagrams.

There are lots of easy theorems about unions, too:

(AÈB) È C = AÈ(B È C)

AÈB = BÈA

AÈÆ = A

AÈA = A

And we also have two distributive laws, so you don’t have to remember which way it goes:

(AÈB)ÇC = (AÇC) È (BÇC)

(AÇB)ÈC = (AÈB) Ç (AÈC)

A B A B

C C

(fill them in!)

COMPLEMENTS

If we have a well-defined “universe” U , then every set A has a complement A containing everything that is NOT in A.

The membership rule for the set A is

The element must NOT satisfy the rule for membership of A.

Venn diagram:

U A

A

{January, February, March} =

{April,May,...,December}

{1,3,5,...} = ? (U = natural numbers)

{2,4,6,...}

Rules for complements

A = A

U = Æ

Æ = U

A Ç B = A È B

“De Morgan’s laws”

A Ç B = A È B

“not (A and B) = (not A) or (not B) “

“not (A or B) = (not A) and (not B)”

DIFFERENCE OF SETS

We define the difference of two sets,

A-B, to be the set of all elements that are in A and not in B. B does not have to be a subset of A.

A-B = A Ç B.

EXAMPLES:

{a,b,c} – {a,c} = {b}

{1,2,3,4,5} - {4,5,6,7} = {1,2,3}

THEOREMS: A-A = Æ

A- Æ = A

A-B Í A

(A-B) Ç B = Æ

PRODUCTS

The product AxB of two sets is the set of ordered pairs (a,b) with aÎA, bÎB. Note that the elements of the product are NOT elements of the original sets!

{1,2} x {A,B,C} =

{(1,A),(2,A),(1,B),(2,B),(1,C),(2,C)}

{Soup, salad} x {meat,fish,chicken} =

{(soup,meat),(soup,fish),(soup,chicken),

(salad,meat),(salad,fish),(salad,chicken)}

(It’s often good to think about products as “meals from a menu” where you can take one choice for each course.)

The membership rule for AxB:

“This is an ordered pair, AND the first element is in A, AND the second element is in B.”

We can think of the elements of the product as arranged in a rectangle:

{a,b,c} x {c,d,e} =

(a,c) (a,d) (a,e)

(b,c) (b,d) (b,e)

(c,c) (c,d) (c,e)

NOTE: the repeated element can be used twice! If this doesn’t make sense, don’t use a product.

Pick a committee of two out of {Ann, Bill, Cathy}. As (Ann,Ann) is not a valid committee, we are not taking a product. [In fact it’s what we call a “combination”.]

Pick a committee with one man and one woman out of {Ann, Betty, Cathy},{Paul,Quentin,Rob}.

This is a product; we have 3x3 = 9 choices.

(Ann,Paul) (Ann,Quentin) (Ann,Rob)

(Betty,Paul) (Betty,Quentin) (Betty,Rob)

(Cathy,Paul) (Cathy,Quentin) (Cathy,Rob)