Set Theory
• Set: Collection of objects (“elements”)
• aÎA “a is an element of A”
“a is a member of A”
• aÏA “a is not an element of A”
• A = {a1, a2, …, an} “A contains…”
• Order of elements is meaningless
• It does not matter how often the same element
is listed.
January 31, 2013 Applied Discrete Mathematics 1
Week 1: Logic and Sets
Set Equality
Sets A and B are equal if and only if they contain
exactly the same elements.
Examples:
• A = {9, 2, 7, -3}, B = {7, 9, -3, 2} : A=B
• A = {dog, cat, horse},
B = {cat, horse, squirrel, dog} : A¹B
• A = {dog, cat, horse},
B = {cat, horse, dog, dog} : A=B
January 31, 2013 Applied Discrete Mathematics 2
Week 1: Logic and Sets
Examples for Sets
“Standard” Sets:
• Natural numbers N = {0, 1, 2, 3, …}
• Integers Z = {…, -2, -1, 0, 1, 2, …}
• Positive Integers Z+ = {1, 2, 3, 4, …}
• Real Numbers R = {47.3, -12, p, …}
• Rational Numbers Q = {1.5, 2.6, -3.8, 15, …}
(correct definition will follow)
January 31, 2013 Applied Discrete Mathematics 3
Week 1: Logic and Sets
Examples for Sets
• A=Æ “empty set/null set”
• A = {z} Note: zÎA, but z ¹ {z}
• A = {{b, c}, {c, x, d}}
• A = {{x, y}}
Note: {x, y} ÎA, but {x, y} ¹ {{x, y}}
• A = {x | P(x)}
“set of all x such that P(x)”
• A = {x | xÎN Ù x > 7} = {8, 9, 10, …}
“set builder notation”
January 31, 2013 Applied Discrete Mathematics 4
Week 1: Logic and Sets
Examples for Sets
We are now able to define the set of rational
numbers Q:
Q = {a/b | aÎZ Ù bÎZ+}
or
Q = {a/b | aÎZ Ù bÎZ Ù b¹0}
And how about the set of real numbers R?
R = {r | r is a real number}
That is the best we can do.
January 31, 2013 Applied Discrete Mathematics 5
Week 1: Logic and Sets
Subsets
AÍB “A is a subset of B”
A Í B if and only if every element of A is also
an element of B.
We can completely formalize this:
A Í B Û "x (xÎA ® xÎB)
Examples:
A = {3, 9}, B = {5, 9, 1, 3}, AÍ B? true
A = {3, 3, 3, 9}, B = {5, 9, 1, 3}, A Í B ? true
A = {1, 2, 3}, B = {2, 3, 4}, AÍ B? false
January 31, 2013 Applied Discrete Mathematics 6
Week 1: Logic and Sets
Subsets
Useful rules:
• A = B Û (A Í B) Ù (B Í A)
• (A Í B) Ù (B Í C) Þ A Í C (see Venn Diagram)
B
A C
January 31, 2013 Applied Discrete Mathematics 7
Week 1: Logic and Sets
Subsets
Useful rules:
• Æ Í A for any set A
• A Í A for any set A
Proper subsets:
A Ì B “A is a proper subset of B”
A Ì B Û "x (xÎA ® xÎB) Ù $x (xÎB Ù xÏA)
or
A Ì B Û "x (xÎA ® xÎB) Ù ¬"x (xÎB ® xÎA)
January 31, 2013 Applied Discrete Mathematics 8
Week 1: Logic and Sets
Cardinality of Sets
If a set S contains n distinct elements, nÎN,
we call S a finite set with cardinality n.
Examples:
A = {Mercedes, BMW, Porsche}, |A| = 3
B = {1, {2, 3}, {4, 5}, 6} |B| = 4
C=Æ |C| = 0
D = { xÎN | x £ 7000 } |D| = 7001
E = { xÎN | x ³ 7000 } E is infinite!
January 31, 2013 Applied Discrete Mathematics 9
Week 1: Logic and Sets
The Power Set
2A or P(A) “power set of A”
2A = {B | B Í A} (contains all subsets of A)
Examples:
A = {x, y, z}
2A = {Æ, {x}, {y}, {z}, {x, y}, {x, z}, {y, z}, {x, y, z}}
A=Æ
2A = {Æ}
Note: |A| = 0, |2A| = 1
January 31, 2013 Applied Discrete Mathematics 10
Week 1: Logic and Sets
The Power Set
Cardinality of power sets:
| 2A | = 2|A|
• Imagine each element in A has an “on/off” switch
• Each possible switch configuration in A corresponds
to one element in 2A
A 1 2 3 4 5 6 7 8
x x x x x x x x x
y y y y y y y y y
z z z z z z z z z
• For 3 elements in A, there are
2´2´2 = 8 elements in 2A
January 31, 2013 Applied Discrete Mathematics 11
Week 1: Logic and Sets
Cartesian Product
The ordered n-tuple (a1, a2, a3, …, an) is an ordered
collection of objects.
Two ordered n-tuples (a1, a2, a3, …, an) and
(b1, b2, b3, …, bn) are equal if and only if they
contain exactly the same elements in the same
order, i.e. ai = bi for 1 £ i £ n.
The Cartesian product of two sets is defined as:
A´B = {(a, b) | aÎA Ù bÎB}
Example: A = {x, y}, B = {a, b, c}
A´B = {(x, a), (x, b), (x, c), (y, a), (y, b), (y, c)}
January 31, 2013 Applied Discrete Mathematics 12
Week 1: Logic and Sets
Cartesian Product
Note that:
• A´Æ = Æ
• Æ´A = Æ
• For non-empty sets A and B: A¹B Û A´B ¹ B´A
• |A´B| = |A|×|B|
The Cartesian product of two or more sets is
defined as:
A1´A2´…´An = {(a1, a2, …, an) | aiÎAi for 1 £ i £ n}
January 31, 2013 Applied Discrete Mathematics 13
Week 1: Logic and Sets
Set Operations
Union: AÈB = {x | xÎA Ú xÎB}
Example: A = {a, b}, B = {b, c, d}
AÈB = {a, b, c, d}
Intersection: AÇB = {x | xÎA Ù xÎB}
Example: A = {a, b}, B = {b, c, d}
AÇB = {b}
January 31, 2013 Applied Discrete Mathematics 14
Week 1: Logic and Sets
Set Operations
Two sets are called disjoint if their intersection is
empty, that is, they share no elements:
AÇB = Æ
The difference between two sets A and B contains
exactly those elements of A that are not in B:
A-B = {x | xÎA Ù xÏB}
Example: A = {a, b}, B = {b, c, d}, A-B = {a}
January 31, 2013 Applied Discrete Mathematics 15
Week 1: Logic and Sets
Set Operations
The complement of a set A contains exactly those
elements under consideration that are not in A:
-A = U-A
Example: U = N, B = {250, 251, 252, …}
-B = {0, 1, 2, …, 248, 249}
Table 1 in Section 2.2 (4th edition: Section 1.5; 5th
edition: Section 1.7; 6th edition: Section 2.2) shows
many useful equations for set identities.
January 31, 2013 Applied Discrete Mathematics 16
Week 1: Logic and Sets
Set Operations
How can we prove AÈ(BÇC) = (AÈB)Ç(AÈC)?
Method I:
xÎAÈ(BÇC)
Û xÎA Ú xÎ(BÇC)
Û xÎA Ú (xÎB Ù xÎC)
Û (xÎA Ú xÎB) Ù (xÎA Ú xÎC)
(distributive law for logical expressions)
Û xÎ(AÈB) Ù xÎ(AÈC)
Û xÎ(AÈB)Ç(AÈC)
January 31, 2013 Applied Discrete Mathematics 17
Week 1: Logic and Sets
Set Operations
Method II: Membership table
1 means “x is an element of this set”
0 means “x is not an element of this set”
A B C BÇC AÈ(BÇC) AÈB AÈC (AÈB) Ç(AÈC)
0 0 0 0 0 0 0 0
0 0 1 0 0 0 1 0
0 1 0 0 0 1 0 0
0 1 1 1 1 1 1 1
1 0 0 0 1 1 1 1
1 0 1 0 1 1 1 1
1 1 0 0 1 1 1 1
1 1 1 1 1 1 1 1
January 31, 2013 Applied Discrete Mathematics 18
Week 1: Logic and Sets
