Mathematical Foundation of Computer Science

DHARM

6 MATHEMATICAL FOUNDATION OF COMPUTER SCIENCE

Difference
Given two sets X and Y, then difference of X and Y denoted by X – Y is the set taken all those
elements of X that are not in Y i.e.,
X – Y = {x/x ∈ X AND x ∉ Y}
For example,
l {a, b, c, $} – {a, b, c} = {$}
l {a, b, c} – {a, b, c, $} = ∅
l {{a, b}, c, d} – {a, b, c, d} = {{a, b}}
l {1, a, b} – {1, a, b} = ∅
l {a, b, c} – { } = {a, b, c}
We can also define the symmetric difference of the two sets X and Y, which is denoted
by X ~ Y, is the set taken all the elements of X or Y but not in both i.e.,
X ~ Y = {x/x ∈ (X – Y) ∪ x ∈ (Y – X)}
For example,
l {a, b, c} ~ {c, d} = {a, b, d}
l {a, b, c} ~ { } = {a, b, c}
l {a, b, c} ~ {a, b, c} = ∅
Complement
Often all the sets are probably the subsets of a general larger set U called universal set. For
example, if we are considering various sets made up only of integers, thus the set S of integers
is an appropriate universal set. Given a universal set U, we define the complement of a set X
as,
X′ = U – X
For any set X ⊆ U, we obtain following equivalence,
l X′′ = X [De Morgan’s Law]
l X ∩ X′ = ∅
l X ∪ X′ = U
Assume X and Y are two sets (i.e. X, Y ⊆ U) then De Morgan’s law can be written with
complements, i.e.
l (X ∩ Y)′ = X′ ∪ Y′
l (X ∪ Y)′ = X′ ∩ Y′

1.3.3 Power Set................................................................................................................

Given a set X, then power set of X is denoted by P(X), is the set take in all the subsets of X. For

a finite set X with | X | = n, then | P(X) | = 2n or number of elements in the power set is 2n

including the null set ∅.

For example,

l Let set X = {α, β, γ}, then power set of X will be P(X) = {∅, {α}, {β}, {γ}, {α, β}, {α, γ}, {β,γ},

and {α, β, γ}}

l Let set X = {1, 2, ∅}, then P(X) = {∅, {1}, {2}, {∅}, {1, 2}, {1, ∅}, {2, ∅}, {1, 2, ∅}}.

l Let X = ∅, then P(X) = {∅} or power set of empty set is not empty.

l For any set X, ∅ ∈ P(X) or ∅ ⊆ P(X).