Sets A and B are examples of finite sets, whereas C is an infinite set. For any finite set A, |A| denotes the number of elements in A and is referred to as the cardinality, or size of A. In the example above |A| = 9 and |B| = 4.
If C, D are sets from a universe U, C is a subset of D, written C ⊆ D, or D ⊇ C, if every element of C is an element of D. Additionally, if D contains an element that is not in C, then C is called a proper subset of D, denoted C ⊂ D or D ⊃ C.
For the universe U = {1,2,3,4,5}, consider the set A = {1,2}. If B ={x | x2 ∈ U } then the members of B are 1,2. Hence A and B contain the same elements – and no other, thus sets A and B should be equal. It is also true that A ⊆ B and B ⊇ A giving us the following definition of equality.
For a given universe U, the sets C and D (taken from U) are said to be equal, written C=D, when C ⊆ D, or D ⊇ C.
We can see that neither order nor repetition is relevant for a set. Consequently, we find that {1,2,3} = {3,2,1} = {2,2,1,3} = {1,2,1,2,3}.
We can define the negation of a subset. A /⊆ B if there is at least one element x in the universe where x is a member of A but x is not a member of B.
We have introduced four ideas so far:
- set membership
- set equality
- subsets
- proper subsets
Examples
Let U = {1,2,3,4,5,6,x,y,{1,2},{1,2,3},{1,2,3,4}} – where x,y are simply letters of the alphabet. Then | U | = 11.
-
If A = {1,2,3,4}, then |A| = 4 and:
-
A ⊆ U
-
A ⊂ U
-
A ∈ U
-
{A} ⊆ U
-
{A} ⊂ U, but
-
{A} ∉ U
-
Let B = {5,6,x,y,A} = {5,6,x,y,{1,2,3,4}}. Then |B| = 5 (not 8). Now
-
A ∈ B
-
{A} ⊆ B and
-
{A} ⊂ B, but
-
{A} ∉ B
-
A /⊆ B (A is not a subset of B)
-
A ⊄ B (A is not a proper subset of B)
1.4 The Empty Set and Powersets
The null set, or empty set, is the (unique) set containing no elements. It is denoted by ∅ or {}. Note that |∅| = 0 but {0} ≠ ∅. Also ∅ ≠ {∅} because {∅} is a set with one element, namely the null set.
Let us now consider the subsets of the set C = {1,2,3,4}. In constructing a subset of C, we have, for each member x of C, two distinct choices: either include it in the set, or exclude it. Consequently, there are 2 x 2 x 2 x 2 choices, resulting in 24 = 16 subsets of C. These include the empty set and the set C itself.
If A is a set from universe U, the power set of A, denoted P(A) is the collection (or set) of all subsets of A.
Example
For the set C given above, P(C)= {∅, {1},{2},{3},{4},{1,2},{1,3},{1,4},{2,3},{2,4},{3,4},{1,2,3},{1,2,4},{1,3,4},{2,3,4},C}
In general, for any finite set A with |A| = n ≥0, A has 2n subsets and that |P(A)| = 2n
Some Useful Sets
-
Z = the set of integers = {0,1,-1,2,-2,3,-3,…}
-
N = the set of non-negative integers of natural numbers = {0,1,2,3,…}
-
Z+ = the set of positive integers = {1,2,3,…}
-
Q = the set of rational numbers = {a/b | a,b ∈ Z, b ≠ 0}
-
Q+ = the set of positive rational numbers = {r | r ∈ Q, r>0)
-
R = the set of real numbers
-
R+ = the set of positive real numbers
1.5 Set Operations and the Laws of Set Theory
For A,B ⊆ U we define the following:
-
A ∪ B (the union of A and B) = {x | x ∈ A ∨ x ∈ B}
-
A ∩ B ( the intersection of A and B) = {x | x ∈ A ∧ x ∈ B}
-
A Δ B ( the symmetric difference of A and B) = {x | (x ∈ A ∨ x ∈ B) ∧ x ∉ A ∩ B} = {x | x ∈ A ∪ B ∧ x ∉ A ∩ B}
Note that if , A,B ⊆ U then A ∪ B, A ∩ B, A Δ B ⊆ U .Consequently, ∪, ∩ and Δ are closed binary operations on P(U) or that P(U) is closed under these binary operations.
Examples
With U = {1,2,3,4,5,6,7,8,9,10}, A = {1,2,3,4,5}, B= {3,4,5,6,7} and C = {7,8,9} we have:
-
A ∩ B = {3,4,5}
-
A ∪ B = {1,2,3,4,5,6,7}
-
B ∩ C = {7}
-
A ∩ C = ∅
-
A Δ B = {1,2,6,7}
-
A ∪ C = {1,2,3,4,5,7,8,9}
-
A Δ C = {1,2,3,4,5,7,8,9}
Definition
Let A,B ⊆ U. The sets A and B are called disjoint, or mutually disjoint, when A ∩ B = ∅.
_
For a set A ⊆ U, the complement of A, denoted U – A, or A is given by {x | x ∈ U ∧ x ∉ A}
Examples
Referring to sets A,B,C above:
_ _ _
A = {6,7,8,9,10}, B = {1,2,8,9,10} and C = {1,2,3,4,5,6,10}
Definition
Let A,B ⊆ U. the relative complement of A in B, denoted B-A, is given by {x | x ∈ B ∧ x ∉ A}.
Examples
Referring to sets A,B,C above:
- B-A = {6,7}
- A-B = {1,2}
- A-C = A
- C-A = C _
-
A-A = ∅ f) U –A = A
The Laws of Set Theory
For any sets A,B, and C taken from a universe U
=
1. A = A Law of Double Complement
_____ _ __
2. A ∪ B = A ∩ B De Morgan’s Laws
_____ __ __
A ∩ B = A ∪ B
3. A ∪ B = B ∪ A Commutative Laws
A ∩ B = B ∩ A
4. A ∪ (B ∪ C) = (A ∪ B) ∪ C Associative Laws
A ∩ (B ∩ C) = (A ∩ B) ∩ C
5. A ∪ (B ∩ C) =(A ∪ B) ∩ (A ∪ C) Distributive Laws
A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C)
6. A ∪ A = A Idempotent Laws
A ∩ A = A
7. A ∪ U = U Identity laws
A ∩ U = A
__
8. A ∪ A = U Inverse Laws
__
A ∩ A = ∅
9. A ∪ U = U Domination laws
A ∩ ∅ = ∅
10. A ∪ (A ∩ B) = A Absorption Laws
A ∩ (A ∪ B) = A
When we consider the relationships that exist between sets, we can investigate this graphically using something called a Venn diagram. A Venn diagram is constructed as follows: U is depicted as the interior of a rectangle, while subsets of U are represented by the interiors of circles.
The Venn diagram is a useful way of establishing set equalities. Another technique for establishing set equalities is the membership table.
We observe that for sets A,B ⊆ U, an element x ∈ U,satisfies exactly one of the following four situations:
-
x ∉A, x ∉B
-
x ∉A, x ∈B
-
x ∈A, x ∉B
-
x ∈A, x ∈B
This can then be written in tabular form, using a 0 when x is not in a set and a 1 when it is in a set.
Example
Use Membership Tables to establish the equality of A ∪ (B ∩ C) with (A ∪ B) ∩ (A ∪ C)
Set Theory – Tutorial Exercises
1. Which of the following sets are equal?
a) {1,2,3} b) {3,2,1,3} c) {3,1,2,3} d) {1,2,2,3}
2. Let A = {1, {1}, {2}}. Which of the following statements are true?
a) 1 ∈ A b) {1} ∈ A c) {1} ⊆ A d) {{1}} ⊆ A
e) {2} ∈ A f) {2} ⊆ A g) {{2}} ⊆ A h) {{2}] ⊃ A
3. Repeat question 2 using the set A = {1,2,{2}}
4. Determine all the elements in each of the following sets:
-
{1 + (-1)n | n ∈ N}
-
{n + (1/n} | n ∈ {1,2,3,5,7}}
-
{n3 + n2 | n ∈ {0,1,2,3,4}}
-
{1/(n2 + n) | n is an odd positive integer and n ≤11}
5. For A= {1,2,3,4,5,6,7}, determine the number of
-
Subsets of A
-
Nonempty subsets of A
-
Proper subsets of A
-
Nonempty proper subsets of A
-
Subsets of A containing 3 elements
-
Subsets of A containing 1,2
-
Subsets of A containing 5 elements including 1,2
-
Proper subsets of A containing 1,2
-
Subsets of A with an even number of elements
-
Subsets of A with an odd number of elements
-
Subsets of A with an odd number of elements, including the element 3
6. For U= {1,2,3,4,5,6,7,8,9,10}, let A={1,2,3,4,5}, B={1,2,4,8}, C={1,2,3,5,7} and D={2,4,6,8}. Determine each of the following:
a) (A ∪ B) ∩ C
b) A ∪ (B ∩ C)
__ __
c) C ∪ D
______
d) C ∩ D
e) (A ∪ B) –C
f) A ∪ (B - C)
g) (B – C) – D
h) B – (C – D)
i) (A ∪ B) - (C ∩ D)
7. Let U= {a,b,c,…x,y,z} with A={a,b,c} and C={a,b,d,e}. If | A ∩ B| =2 and (A ∩ B) ⊂ B ⊂ C, determine B.
8. Using Venn diagrams or Membership Tables, investigate the truth or falsity of the each of the following for sets A,B,C ⊆ U .
-
A Δ (B ∩ C) = (A Δ B) ∩ (A Δ C)
-
A ∩ (B Δ C) = (A ∩ B) Δ (A ∩ C)
9. A supermarket discovers that from a sample of 50 shoppers, 30 buy tea, 25 buy coffee and 10 buy both coffee and tea. How many shoppers buy either coffee or tea.? (Hint – use Venn Diagrams)
Named after the English Logician John Venn (1834-1923)