Scribd
Upload
197 views16 pages

Set Theory

Basic set theory

Uploaded by

Mohammad Gulam Ahamad
Copyright
© Attribution Non-Commercial (BY-NC)
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PPT, PDF, TXT or read online on Scribd
197 views16 pages

Set Theory

Basic set theory

Uploaded by

Mohammad Gulam Ahamad
Copyright
© Attribution Non-Commercial (BY-NC)
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PPT, PDF, TXT or read online on Scribd
You are on page 1/ 16

Discrete Mathematics

Lecture 5
Dr. Mohammed Gulam Ahamad
Basics of Set Theory
Set and element are undefined notions in the set theory
and are taken for granted
Set notation: {1, 2, 3}, {{1, 2}, {3}, {1, 2, 3}}, {1, 2,
3, }, C, {x e R | -3 < x < 6}
Set A is called a subset of set B, written as A _ B,
when x, x e A x e B
A is a proper subset of B, when A is a subset of B and
-x e B and x e A
Visual representation of the sets
Distinction between _ and e
Set Operations
Set a equals set B, iff every element of set A is in
set B and vice versa
Proof technique for showing sets equality
Union of two sets is a set of all elements that
belong to at least one of the sets
Intersection of two sets is a set of all elements that
belong to both sets
Difference of two sets is a set of elements in one
set, but not the other
Complement of a set is a difference between
universal set and a given set
Cartesian Products
Ordered n-tuple is a set of ordered n
elements. Equality of n-tuples
Cartesian product of n sets is a set of n-
tuples, where each element in the n-tuple
belongs to the respective set participating in
the product
Formal Languages
Alphabet E: set of characters used to construct
strings
String over alphabet E: either empty string of n-
tuple of elements from E, for any n
Length of a string is value n
Language is a subset of all strings over E
E
n
is a set of strings with length n over E
E
*
is a set of all strings of finite length over E
Notation for arithmetic expressions: prefix, infix,
postfix
Subset Check Algorithm
Let two sets be represented as arrays A and B
m = size of A, n = size of B
i = 1, answer = yes;
while (i s m && answer == yes) {
j = 1, found = no;
while (j s n && found == no) {
if (a[i] == b[j]) found = yes;
j++;
}
if (found == no) answer = no;
i++;
}
Set Properties
Inclusion of Intersection:
A B _ A and A B _ B
Inclusion in Union:
A _ A B and B _ A B
Transitivity of Inclusion:
(A _ B . B _ C) A _ C
Set Definitions:
x e X Y x e X v y e Y
x e X Y x e X . y e Y
x e X Y x e X . y e Y
x e X
c
x e X
(x, y) e X Y x e X . y e Y
Set Identities
Commutative Laws: A B = A B and A B = B A
Associative Laws: (A B) C = A (B C) and (A B) C = A (B C)
Distributive Laws:
A (B C) = (A B) (A C) and A (B C) = (A B) (A C)
Intersection and Union with universal set: A U = A and A U = U
Double Complement Law: (A
c
)
c
= A
Idempotent Laws: A A = A and A A = A
De Morgans Laws: (A B)
c
= A
c
B
c
and

(A B)
c
= A
c
B
c
Absorption Laws: A (A B) = A and A (A B) = A
Alternate Representation for Difference: A B = A B
c
Intersection and Union with a subset: if A _ B, then A B = A and A B = B
Exercises
Is is true that (A B) (B C) = A C?
Show that (A B) C = (A C) (B C)
Is it true that A (B C) = (A B) C?
Is it true that (A B) (A B) = A?
Empty Set
S = {x e R, x
2
= -1}
X = {1, 3}, Y = {2, 4}, C = X Y
Empty set has no elements C
Empty set is a subset of any set
There is exactly one empty set
Properties of empty set:
A C = A, A C = C
A A
c
= C, A A
c
= U
U
c
= C, C
c
= U
Set Partitioning
Two sets are called disjoint if they have no
elements in common
Theorem: A B and B are disjoint
A collection of sets A
1
, A
2
, , A
n
is called
mutually disjoint when any pair of sets from this
collection is disjoint
A collection of non-empty sets {A
1
, A
2
, , A
n
} is
called a partition of a set A when the union of
these sets is A and this collection consists of
mutually disjoint sets
Power Set
Power set of A is the set of all subsets of A
Theorem: if A _ B, then P(A) _ P(B)
Theorem: If set X has n elements, then P(X)
has 2
n
elements
Boolean Algebra
Boolean Algebra is a set of elements together
with two operations denoted as + and * and
satisfying the following properties:
a + b = b + a, a * b = b * a
(a + b) + c = a + (b + c), (a * b) *c = a * (b * c)
a + (b * c) = (a + b) * (a + c), a * (b + c) = (a * b) + (a * c)
a + 0 = a, a * 1 = a for some distinct unique 0 and 1
a + = 1, a * = 0

Exercises
Simplify: A ((B A
c
) B
c
)
Symmetric Difference: A B = (A B) (B
A)
Show that symmetric difference is associative
Are A B and B C necessarily disjoint?
Are A B and C B necessarily disjoint?
Let S = {2, 3, , n}. For each S
i
_ S, let P
i
be the
product of elements in S
i
. Show that:
EP
i
= (n + 1)! / 2 1
Russells Paradox
Set of all integers, set of all abstract ideas
Consider S = {A, A is a set and A e A}
Is S an element of S?
Barber puzzle: a male barber shaves all
those men who do not shave themselves.
Does the barber shave himself?
Consider S = {A _ U, A e A}. Is S e S?
Halting Problem
There is no computer algorithm that will
accept any algorithm X and data set D as
input and then will output halts or loops
forever to indicate whether X terminates in
a finite number of steps when X is run with
data set D.

You might also like