Set Theory(chapter1)

Discrete Mathematics

AM 1005 SET THEORY

Definition 





A set is a group of “objects”  People in a class: { Abhishek, Kunal, Chetna }  Courses offered by a department: { CI 101, CI 202, … }  Colors of a rainbow: {violet, indigo, red, orange, yellow, green, blue }  States of matter { solid, liquid, gas, plasma }  States in the US: { Alabama, Alaska, Virginia, … }  Sets can contain non-related elements: { 3, a, red, Virginia } Although a set can contain (almost) anything, we will most often use sets of numbers  All positive numbers less than or equal to 5: {1, 2, 3, 4, 5}  A few selected real numbers: { 2.1, π, 0, -6.32, e } Order does not matter  {1, 2, 3, 4, 5} is equivalent to {3, 5, 2, 4, 1}

Properties 

Sets do not have duplicate elements 

Consider the set of vowels in the alphabet. It makes no sense to list them as {a, a, a, e, i, o, o, o, o, o, u}  What we really want is just {a, e, i, o, u} 



Sets can contain other sets   



S = { {1}, {2}, {3} } T = { {1}, {{2}}, {{{3}}} } V = { {{1}, {{2}}}, {{{3}}}, { {1}, {{2}}, {{{3}}} } }

Note that 1 ≠ {1} ≠ {{1}} ≠ {{{1}}} 

They are all different

Specifications 

Sets are usually represented by a capital letter (A, B, S, etc.)



Elements are usually represented by an italic lowercase letter (a, x, y, etc.)



Easiest way to specify a set is to list all the elements: A = {1, 2, 3, 4, 5} 

Not always feasible for large or infinite sets

Specifications 

Can use an ellipsis (…): B = {0, 1, 2, 3, …}  Consider the set C = {3, 5, 7, …}. What comes next?  If the set is all odd integers greater than 2, it is 9  If the set is all prime numbers greater than 2, it is 11



Can use set-builder notation  D = {x | x is prime and x > 2}  E = {x | x is odd and x > 2}  The vertical bar means “such that”  How to read these sets ?

Specifications 

A set is said to “contain” the various “members” or “elements” that make up the set 

If an element a is a member of (or an element of) a set S, we use then notation a ∈ S 



4 ∈ {1, 2, 3, 4}

If an element is not a member of (or an element of) a set S, we use the notation a ∉ S 7 ∉ {1, 2, 3, 4}  Chandigarh ∉ {1, 2, 3, 4} 

Finite and infinite sets 

Finite sets 

Examples:  



A = {1, 2, 3, 4} B = {x | x is an integer, 1 < x < 4}

Infinite sets 

Examples:  

Z = {integers} = {…, -3, -2, -1, 0, 1, 2, 3,…} S={x| x is a real number and 1 < x < 4} = [1, 4]

Often used sets   



N = {1, 2, 3, …} is the set of natural numbers Z = {…, -2, -1, 0, 1, 2, …} is the set of integers Z+ = {1, 2, 3, …} is the set of positive integers (whole numbers)  Note that people disagree on the exact definitions of whole numbers and natural numbers Q = {p/q | p ∈ Z, q ∈ Z, q ≠ 0} is the set of rational numbers  Any number that can be expressed as a fraction of two integers (where the bottom one is not zero)  Q* is the set of nonzero rational numbers



R is the set of real numbers R+ is the set of positive real numbers R* is the set of nonzero real numbers



C is the set of complex numbers

 

Some important sets Universal set: the set of all elements about which we make assertions.  The empty set ∅ = { } has no elements. Also called null set or void set. 

U is the universal set – the set of all of elements (or the “universe”) from which given any set is drawn  For the set {-2, 0.4, 2}, U would be the real numbers  For the set {0, 1, 2}, U could be the natural numbers (zero and up), the integers, the rational numbers, or the real numbers, depending on the context

More Examples For the set of the students in this class, U would be all the students in the University (or perhaps all the people in the world)  For the set of the vowels of the alphabet, U would be all the letters of the alphabet  To differentiate U from U (which is a set operation), the universal set is written in a different font (and in bold and italics) 

The empty set 1 If a set has zero elements, it is called the empty (or null) set  Written using the symbol ∅  Thus, ∅ = { }  VERY IMPORTANT  If you get confused about the empty set in a problem, try replacing ∅ by { }  As the empty set is a set, it can be a element of other sets  { ∅, 1, 2, 3, x } is a valid set 

The empty set 2 

Note that ∅ ≠ { ∅ }  



The first is a set of zero elements The second is a set of 1 element (that one element being the empty set)

Replace ∅ by { }, and you get: { } ≠ { { } } 

It’s easier to see that they are not equal that way

Cardinality Cardinality of a set A (in symbols |A|) is the number of elements in A  Examples: 

If A = {1, 2, 3} then |A| = 3 If B = {x | x is a natural number and 1< x< 9} then |B| = 9 

Infinite cardinality  

Countable (e.g., natural numbers, integers) Uncountable (e.g., real numbers)

Set equality 

Two sets are equal if they have the same elements 

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



{1, 2, 3, 2, 4, 3, 2, 1} = {4, 3, 2, 1} 



Remember that order does not matter! Remember that duplicate elements do not matter!

Two sets are not equal if they do not have the same elements 

{1, 2, 3, 4, 5} ≠ {1, 2, 3, 4}

Subsets 



If all the elements of a set S are also elements of a set T, then S is a subset of T  For example, if S = {2, 4, 6} and T = {1, 2, 3, 4, 5, 6, 7}, then S is a subset of T  This is specified by S ⊆ T  Or by {2, 4, 6} ⊆ {1, 2, 3, 4, 5, 6, 7} If S is not a subset of T, it is written as such: S ⊄T  For example, {1, 2, 8} ⊄ {1, 2, 3, 4, 5, 6, 7}

Subsets 

Note that any set is a subset of itself!   

Given set S = {2, 4, 6}, since all the elements of S are elements of S, S is a subset of itself This is kind of like saying 5 is less than or equal to 5 Thus, for any set S, S ⊆ S

Subsets 

 

The empty set is a subset of all sets (including itself!)  Recall that all sets are subsets of themselves All sets are subsets of the universal set The textbook has this gem to define a subset:  ∀x ( x∈A → x∈B )  English translation: for all possible elements of a set, if x is an element of A, then x is an element of B  This type of notation will be gone over later

Proper Subsets 

If S is a subset of T, and S is not equal to T, then S is a proper subset of T  Let T = {0, 1, 2, 3, 4, 5}  If S = {1, 2, 3}, S is not equal to T, and S is a subset of T  A proper subset is written as S ⊂ T  Let R = {0, 1, 2, 3, 4, 5}. R is equal to T, and thus is a subset (but not a proper subset) or T  Can be written as: R ⊆ T and R ⊄ T (or just R = T)  Let Q = {4, 5, 6}. Q is neither a subset of T nor a proper subset of T

Proper Subsets 

The difference between “subset” and “proper subset” is like the difference between “less than or equal to” and “less than” for numbers



For a given set X, The empty set and the set X, itself are the only, improper subset of set X.

Venn diagrams

A Venn diagram provides a graphic view of sets  Set union, intersection, difference, symmetric difference and complements can be easily and visually identified 

Venn diagrams 

Represents sets graphically  





The box represents the universal set Circles represent the set(S)

Consider set S, which is the set of all vowels in the alphabet The individual elements are usually not written in a Venn diagram

b

c

d f

g

h

k

l

j m

n

p

q

r

s

t

v

w

x

y

z

U S e

a o

i u

Proper subsets: Venn diagram S⊂R R

S

U

Subsets: review 

X is a subset of Y if every element of X is also contained in Y (in symbols X ⊆ Y)



Equality: X = Y if X ⊆ Y and Y ⊆ X, i.e., X = Y whenever x ∈ X, then x ∈ Y, and whenever x ∈ Y, then x ∈ X



X is a proper subset of Y if X ⊆ Y but Y ⊄ X 

Observation: ∅ is a subset of every set

Question 

What is the meaning of X ⊆ Y and X≠ Y ?

Question 

What is the meaning of X ⊆ Y and X≠ Y ?

X is a proper subset of Y

Power sets 

Given the set S = {0, 1}. What are all the possible subsets of S? 

They are: ∅ (as it is a subset of all sets), {0}, {1}, and {0, 1}



The power set of S (written as P(S)) is the set of all the subsets of S



P(S) = { ∅, {0}, {1}, {0,1} } 

Note that |S| = 2 and |P(S)| = 4

Power sets 

Let T = {0, 1, 2}. The P(T) = { ∅, {0}, {1}, {2}, {0,1}, {0,2}, {1,2}, {0,1,2} } 



P(∅) = { ∅ } 



Note that |T| = 3 and |P(T)| = 8

Note that |∅| = 0 and |P(∅)| = 1

If a set has n elements, then the power set will have 2n elements If |A|=n, then |P(A)|=2n.  n  n  n  n   +   +   +  +   = 2 n , for n ≥ 0  0  1  2  n

Set operations: Union and Intersection 



Given two sets A and B The union of A and B is defined as the set A U B = { x | x ∈ A or x ∈ B } The intersection of X and Y is defined as the set A ∩ B = { x | x ∈ A and x ∈ B}

Two sets A and B are disjoint if A∩B=∅

Set operations: Union & Intersection 

examples      



{1, 2, 3} U {3, 4, 5} = {1, 2, 3, 4, 5} {New York, Washington} U {3, 4} = {New York, Washington, 3, 4} {1, 2} U ∅ = {1, 2} {1, 2, 3} ∩ {3, 4, 5} = {3} {1, 2, 3} and {3, 4, 5} are not disjoint {New York, Washington} ∩ {3, 4} = ∅  No elements in common, these sets are disjoint {1, 2} ∩ ∅ = ∅  Any set intersection with the empty set yields the empty set

Set Operations: Relative Complement 

The relative complement (difference) of two sets is the set defined as: A — B = { x | x ∈ A and x ∉ B } Given: A = {a, b, c, d} and B = {a, c, f, g} A — B = {b, d} B — A = {f, g}

A-B 

B-A

U-A

The complement_ of a set A contained in a Universal set U is the set A = U – A

Set Operations: Symmetric Difference Definition:

The symmetric Difference of sets A and B, denoted A ∆ B, consists of those elements which belong to A or B but not to both. i.e. A Δ B = { x | (x ∈ A or x ∈ B) and x ∉ A ∩ B} Or A Δ B = (A U B) – (A ∩ B)  Important!

Note:- The pink region is the required symmetric difference If A = {1,2,3} and B = {2,5,6,7} Then A ∆ B = { 1,3,5,6,7}

Set operations: Complement and symmetric difference Examples {1, 2, 3} - {3, 4, 5} = {1, 2}  {New York, Washington} - {3, 4} = {New York, Washington}  {1, 2} - ∅ = {1, 2} The difference of any set S with the empty set will be the set Now, assuming U = Z  Complement of {1, 2, 3} = { …, -2, -1, 0, 4, 5, 6, … }  {1, 2, 3} Δ {3, 4, 5} = {1, 2, 4, 5}  {New York, Washington} Δ {3, 4} = {New York, Washington, 3, 4}  {1, 2} Δ ∅ = {1, 2}  The symmetric difference of any set S with the empty 

Example 

If X={1, 4, 7, 10}, Y={1, 2, 3, 4, 5}     

X∪Y= X∩Y= X–Y= Y–X= X Δ Y = (how else can you write this?)

Example 

If X={1, 4, 7, 10}, Y={1, 2, 3, 4, 5}     

X ∪ Y = {1, 2, 3, 4, 5, 7, 10} X ∩ Y = {1, 4} X – Y = {7, 10} Y – X = {2, 3, 5} X Δ Y = (X ∪ Y) – (X ∩ Y) = {2, 3, 5, 7, 10}

Properties of Set operations 

Properties of the union operation     



AU∅=A AUU=U AUA=A AUB=BUA A U (B U C) = (A U B) U C

Identity law Domination law Idempotent law Commutative law Associative law

Properties of the intersection operation     

A∩U=A A∩∅=∅ A∩A=A A∩B=B∩A A ∩ (B ∩ C) = (A ∩ B) ∩ C

Identity law Domination law Idempotent law Commutative law Associative law

Properties contd… 

Properties of complement sets  A=A ¯ ¯ UA=U  A ¯ =∅  A∩A

Complementation law Complement law Complement law

Properties of set operations Theorem 2.1.10: Let U be a universal set, and A, B and C subsets of U. The following properties hold: a) Associativity: (A ∪ B) ∪ C = A ∪ (B ∪ C) (A ∩ B) ∩ C = A ∩ (B ∩C) b) Commutativity: A ∪ B = B ∪ A c) Distributive laws: A ∩ B = B ∩ A A∪(B∩C) = (A∪B)∩(A∪C) A∩(B∪C) = (A∩B)∪(A∩C) d) Identity laws: A∩U=A A∪∅ = A

Properties of set operations (e) Complement laws: A∪Ac = U

A∩Ac = ∅

f) Idempotent laws: A∪A = A A∩A = A g) Bound or Identity laws: A∪U = U A∩∅ = ∅ h) Absorption laws: A∪(A∩B) = A A∩(A∪B) = A

Properties of set operations i) Involution law: (Ac)c = A j) Compliment laws: ∅ c = U k) De Morgan’s laws for sets: (A∪B)c = Ac∩Bc (A∩B)c = Ac∪Bc

Uc = ∅

Computer representation of sets 

Assume that U is finite (and reasonable!)  Let U be the alphabet



Each bit represents whether the element in U is in the set



The vowels in the alphabet: abcdefghijklmnopqrstuvwxyz 10001000100000100000100000



The consonants in the alphabet: abcdefghijklmnopqrstuvwxyz 01110111011111011111011111

Computer representation of sets 

Consider the union of these two sets: 10001000100000100000100000 ∨01110111011111011111011111 11111111111111111111111111



Consider the intersection of these two sets: 10001000100000100000100000 ∧01110111011111011111011111 00000000000000000000000000

Classic Boolean Model 

Illustrates the 8 possible relations between Sets, A, B and C Region Relationship

1

A ∩B ∩C

2

A ∩B ∩C

3

A ∩B ∩C

4

A ∩B ∩C

5

A ∩B ∩C

6

A ∩B ∩C

7 8

A ∩B ∩C A ∩B ∩C

Principle of Duality: 

Suppose E is an equation of set algebra. The dual E* of E is the equation obtained by using the following replacements

E ∅ U ∪ ∩

dual of E (E*) U ∅ ∩

∪ •Theorem (The Principle of Duality) Let E denote a theorem dealing with the equality of two set expressions. Then E* is also a theorem.

Duality contd: 

For example

The dual of (U ∩ A) ∪ ( B ∩ A) = A is (φ ∪ A) ∩ ( B ∪ A) = A.

Thus if E is an identity, then its dual E* is also an identity. What is the dual of A ⊆ B ? Since A ⊆ B ⇔ A ∪ B = B . The dual of A ⊆ B is the dual of A ∪ B = B , which is A ∩ B = B . That is, B ⊆ A.

Counting Principle: a) If A and B are finite then A ∪ B and A ∩ B are finite and n (A ∪ B) = n (A) + n (B) – n (A ∩ B)

b) If A and B are disjoint finite sets, then A ∪ B is finite and n (A ∪ B) = n (A) + n (B) c) Similarly If A, B, C are finite sets then A ∪ B ∪ C is finite and n (A ∪ B ∪ C) = n (A) + n (B) + n(C) – n (A ∩ B) - n(B ∩ C ) − n( A ∩ C ) + n( A ∩ B ∩ C ).

Examlples: 1. In a class of 50 college freshmen, 30 are studying JAVA, 25 studying UNIX, and 10 are studying both. How many freshmen are studying either computer language? U

5

A 20

B 10

| A ∪ B | = | A|+ | B |− | A ∩ B |

15

Examples: 2. Defect types of an AND gate: D1: first input stuck at 0 D2: second input stuck at 0 D3: output stuck at 1 Given 100 samples set A: with D1 set B: with D2 set C: with D3 We have

A

B 4

11 5

3 15

12 43

7 C

| A ∪ B ∪ C |= | A | + | B | + | C | − | A ∩ B | − | A ∩ C | − | B ∩ C | + | A ∩ B ∩ C | with |A|=23, |B|=26, |C|=30, | A ∩ B | = 7, | A ∩ C | = 8, | B ∩ C | = 10, | A ∩ B ∩ C | = 3 , how many samples have defects? Ans:57

Partition of a set: Let S be a nonempty set. A partition of S is a subdivision of S into non-overlapping, non-empty subsets. i.e. a partition of S is a collection { Ai } of non-empty subsets of S such that

(i) Each a ∈ S ⇒ a ∈ Ai for some i (ii) the sets { Ai } are mutually disjoint i.e. Ai ∩ A j = φ The subsets in a partition are called cells. Example: Let S = { 1,2,3,….9} A1 ={1,2} A2={5,6,7} A3 ={8}

A4 ={3,4} and A5 ={9}

Then

{ Ai } 5i =1 = { A1 , A2 ,...... A5 }

for i ≠ j

A1 A3

is a partition of S.

A5

A2 A4

S

Example X = { 1, 2, 3, 4, 5} S = { {1,2}, {3}, {4,5}} S is a partition of X. Determine other possible partitions of the set X.

Partition of a set A partition divides a set into nonoverlapping subsets.  A collection S of nonempty subsets of X is said to be a partition of the set X if every element in X belongs to exactly one member of S.  If S is a partition of X, S is pairwise disjoint and ∪ S = X 

Mathematical Induction 

Let P(n) be the predicate



This is true for particular values of n, e.g:

  

n( n + 1) P( n ) = 1 + 2 + 3 + ⋅ ⋅ ⋅ + n = 2 2(2 + 1) 1+ 2 = 3 = 2 3(3 + 1) 1+ 2 + 3 = 6 = 2 4(4 + 1) 1 + 2 + 3 + 4 = 10 = 2

Want to show that P(n) is true for all integers n i.e.: ∀n:P(n) The easiest way to prove such a statement is to use the method of proof by induction

Mathematical Induction • The principle of mathematical induction is a useful tool for proving that a certain predicate is true for all natural numbers. • It cannot be used to discover theorems, but only to prove them. • If we have a propositional function P(n), and we want to prove that P(n) is true for any natural number n, we do the following: • Show that P(0) is true. (basis step) We could also start at any other integer m, in which case we prove it for all n ≥ m.

Contd: • Show that if P(n) then P(n + 1) for any

n∈N. (inductive step) • Then P(n) must be true for any n∈N. (conclusion).  Intuitively…  Show that P(k) ⇒ P(k+1) for any k  Show that P(1) is true  Then from 1 and 2, P(2) is true  …and from 1 and 3, P(3) is true  …and from 1 and 4, P(4) is true  etc

Example 1 n( n + 1) P( n ) : S ( n ) = 1 + 2 + 3 + ⋅ ⋅ ⋅ + n = ,n ≥1 2

1(1 + 1)  Case n=1: S (1) = 1 = 2 so P(1) is true  Now assume P(k) is true  

Need to show P(k+1) is true I.e. need to show that

( k + 1)( k + 2 ) S ( k + 1) = 2

Example 1 (continued) S ( k + 1) = 1 + 2 + ⋅ ⋅ ⋅ + k + ( k + 1) = S ( k ) + ( k + 1) Step 1: Write S(k+1) in terms of S(k) k ( k + 1) = + ( k + 1) 2 Step 2: Use the fact k ( k + 1) + 2( k + 1) that P(k) is true = 2 Step 3: Manipulate to ( k + 1)( k + 2 ) = get the right formula 2

Example 1 (concluded) 

So,

( k + 1)( k + 2 ) S ( k + 1) = 2

Therefore P(k+1) is true  Therefore, by the principle of mathematical induction, ∀n:P(n) 

Example 2 Let P(n) be the predicate defined by: P(n): ‘n3-n is divisible by 3’ Show that ∀n:P(n)  Case n=1: n3-n=1-1=0, which is divisible by 3. Hence P(1) is true  Now assume that P(k) holds  Need to prove that P(k+1) holds 

Example 2 (continued) Case n=k+1: (k+1)3 - (k+1) = (k3+3k2+3k+1) - (k+1) = (k3-k)+(3k2+3k) = (k3-k) + 3(k2+k) 

Divisible by 3 since P(k) is true 

  

divisible by 3

Hence if k3-k is divisible by 3, then (k+1)3-(k+1) is also divisible by 3 In other words, ∀k:(P(k) ⇒ P(k+1)) Also, P(1) is true Therefore, by mathematical induction, ∀n:P(n)

Example 3: Solution:

Notes: (Limitations of Induction) 







Mathematical induction can only be used to prove arguments for which the domain of discourse is the positive, whole numbers. For example, if P(b) is the predicate: the roots of the equation x2+bx+1 are given by

− b ± b2 − 4 x= 2

Then ∀b:P(b) is true, but cannot be proved by induction Also We can not prove the uniqueness part of fundamental Theorem of Arithmetic.

End of chapter 1.