Discrete Math�Fall 2012

Sections 2.1 and 2.2

​

Set Operations

• The union of sets A and B is the set consisting of all the elements in A or in B.
• The intersection of A and B is the set of elements in A and B.
• Two sets are disjoint if their intersection is empty.
• The difference of sets A and B is the set of all elements in A that are not in B.

Example:

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

​

• Give the union
• Give the intersection
• Are A and B disjoint?
• Give the difference A-B

Universal Set

Many times all of the sets in question are a subset of one set.

• In this situation we call the set containing all of the elements of interest the universal set.
• Can there be more than one universal set?

​

Complement

• The complement of A in U is the set U-A.

​

Example 2

Let A={1,2,4}, B = {2,4,6,8}, C = {3,6,9} and U = {1,2,3,4,6,8,9}.

• Give the complement of A, B, and C.

Theorem 2.1

Let U be a universal set. For any subsets A, B, and C of U, the following are true:

• A u B = B u A and A n B = B n A (commutative)
• (A u B)u C = A u (B u C) (associative)
• (A n B) n C = A n (B n C)
• A u (B n C) = (A u B) n (A u C) (distributive)
• A n (B u C) = (A n B) u (A n C)

Page 43 has more….

​

De Morgan’s Laws

For any subsets A and B of a universal set U, the following are true:

• (A u B)^c = A^c n B^c
• (A n B)^c = A^c u B^c

​

​

​

Example De Morgan’s Laws:

• Verify De Morgan’s Laws using a Venn Diagram.

​

The Cartesian Product

• The Cartesian product of A and B is the set consisting of all the ordered pairs (a,b), where a is an element of A and b is an element of B.

Example:

Let A = {a,b,c} and B ={2,3,4}

• Write down the Cartesian product A x B:

​

Section 2.2 Relations

Remember the marriage problem?

​

Brides Grooms

Sue Bobby

Jess Tim

Beth Mike

​

{(Sue,Bobby), (Jess, Bobby), (Jess,Mike),

(Beth, Tim)}

​

Relations

• A relation from a set A to a set B is a subset of the Cartesian product of A x B.
• If R is a relation from A to B and (x,y) in R, we will say that x is related to y by R.
• We will often write xRy instead of (x,y) in R.

​

• A relation from a set S to itself is called a relation on S.

​

​

Example

Let S = {1,2,3,4}. Define a relation R on S by letting x R y mean x<y.

• Write down all of the ordered pairs in this relation.
• Is 4 R 2 under this relation?

​

​

Possible Properties of Relations

• If for each x in S, x R x is true, then R is called reflexive.
• If y R x is true whenever x R y is true, then R is called symmetric.
• If x R z is true whenever x R y and y R z are both true, then R is called transitive.

Example

Let S = {1,2,3,4}. Define a relation R on S by letting x R y mean x<y.

• Which of the previous properties does this relation have?

​

Equivalence Relations

• A relation that is reflexive, symmetric, and transitive is called an equivalence relation.

Let S be the set of people in this classroom. Let x R y if person x and person y have the same favorite color.

• Is this an equivalence relation?

​

Equivalence classes

• If R is an equivalence relation on a set S and x is in S, the set of elements of S that are related to x is called the equivalence class of x. (denoted [x])
• [x] = { y in S: y R x }

​

• Write down the equivalence classes for this class under the favorite color relation

Theorem 2.3

Let R be an equivalence relation on a set S.

• If x and y are elements of S, then x is related to y by R if and only if [x]=[y].
• Two equivalence classes of R are either equal or disjoint.

​

Time permitting– proof…

1. Double inclusion
2. Assume they are not disjoint.

Partition

• Equivalence classes of an equivalence relation R on a set S divide S into disjoint subsets having the properties:
• No subset is empty
• Each element of S belongs to some subset
• Two distinct subsets are disjoint.

​

• A decomposition of a set S into subsets of this form is called a partition of S.

Example

Let A = {1,2,3}, B = {4,5}, and C = {6,7}. Then

P ={A,B,C} is a partition of S = {1,2,3,4,5,6,7}.

​

Theorem 2.4

• Equivalence relations and partitions are two different ways of describing the same thing.