Ex 2.1 Sets

CC1041
Discrete Mathematics
course mentor
Seher Ansar Khawaja
seheransarkhawaja@ncbae.edu.pk
National College of Business Administration and Economics main

campus, Lahore, Pakistan
Sets
Chapter 2 :
Section 2.1 : Sets
Sets are used to group
Set
objects together. Often the
objects
in a set have similar
properties.
A set is an unordered collection of objects.
Example:
Z is the set of integers.
Set membership
The objects in a set are called the elements, or members,
of the set.
• a is an element of the set A, denoted by a ∈ A.
• a is not an element of the set A, denoted by a ∉ A.
Example:
Set D: all students taking Discrete Mathematics course.
Assume Bill is taking Discrete Mathematics course and
George is not taking Discrete Mathematics course.
Bill ∈ D
George ∉ D
Expressing set
There are many ways to express the sets
1. Listing all the elements
2. Set builder notation
3. Venn diagrams
Listing all elements
S = {e1 , e2 , e3 ,…,en }
where 𝑒𝑖 is element in the set
Example
All vowels in the English alphabet.
• V = {a, e, i , o, u}
Odd positive integers < 10.
O = {1, 3, 5, 7, 9}
Positive integers less than 100.
{1, 2, 3, …, 99}
Set builder notation
Describe the properties the elements must have to be
members
S = {x | P(x)}
S contains all the elements which make the predicate P
true
Example:
• R = { x | x is integer < 100 and > 40}
• Z+ = { x | x is a positive integer}
• O= {1,3,5,7,9} write set builder notation.
Important Sets
• N = {0,1,2,3,…} , Set of natural numbers
• Z = {…,-2,-1,0,1,2,…}, Set of integers
• Z + = {1,2,3,…} , Set of positive integers
• Q = {p/q | p ∈ Z, q ∈ Z, and q = 0}, Set of rational numbers
• R , Set of real numbers
• Sets can have other sets as members

Example: The set {N, Z, Q, R} is a set containing four
elements, each of which is a set.
Venn diagrams
Sets can be represented graphically using Venn diagram.
• Universal set U contains all objects under consideration say English alphabets
is represented by a rectangle
• Other geometric figures are used to represent sets. Say set of vowels
• Points are used to represent particular elements of sets. i.e. a, e, i, o, u
Show set A={a,b,c} using Venn diagram
Set equality
 Two sets are equal if and only if they contain exactly the
same
elemen
ts.
denote
d by A
= B.
 Mathematically: A = B iff ∀x (x ∈ A x ∈ B)
 Example: Are the following sets equal? Why &why not?
 1. {1, 2, 3, 4} and {1, 2, 3, 4}
 2. {1, 2, 3, 4} and {4, 1, 3, 2}
 3. {a, b, c, d, e} and {a, a, c, b, e, d}
 4. {a, e, i, o} and {a, e, i, o, u}

Set equality
 Two sets are equal if and only if they contain exactly the
same
elements.
denoted by A =
B.
 Mathematically: A = B iff ∀x (x ∈ A x ∈ B)
 Example: Are the following sets equal? Why &why not?
 1. {1, 2, 3, 4} and {1, 2, 3, 4} yes
 2. {1, 2, 3, 4} and {4, 1, 3, 2} yes
 3. {a, b, c, d, e} and {a, a, c, b, e, d} yes
 4. {a, e, i, o} and {a, e, i, o, u} } no

Empty set, Singleton Set
A set that has no elements called empty set, or null set.
Denoted
by {} , Ø.
Example:
The set of all positive integers that are less than and
equal to 0.
S = {x | x ∈ Z+ and x ≤ 0 } = {} = Ø
Singleton set: a set with one element

• are Ø and {Ø} equal? No
Ф: an empty set. Think of this as an empty folder
{ф}: a set with one element. The element is an empty
set. Think of this as an folder with an empty folder in it.
Subset
Let A and B be sets.
• A is a subset of B if and only if every element of
A is also an element of B, denoted by A ⊆ B.
• A ⊆ B if and only if ∀x(x ∈ A → x ∈ B)

Subset equality:
A ⊆ B = ∀x(x ∈ A → x ∈ B) and B U
B ⊆ A = ∀x(x ∈ B→ x ∈ A) A
then A = B, ∀x(x ∈ A x ∈ B)
Proper subset
• A is a subset of a set B but that A ≠ B, we write
A ⊂ B and say that A is a proper subset of B
• For A ⊂ B to be true, it must be the case that

A ⊆ B and there must exist an element x of B
that is not an element of A, i.e.
∀x(x ∈ A → x ∈ B) ∧ ∃x(x ∈ B ∧ x ∉ A)
Cardinality of Set
Let S be a set. If there are exactly n distinct elements in S where n is a
nonnegative integer, then S is a finite set.
n is the cardinality of S, denoted by |S|.
A set is said to be infinite if it is not finite.
Example:
1. A be the set of odd positive integers less than 10, |A| =5
2. S be the set of letters in the English alphabet, |S| =?
The power set
Let S be a set.
• The power set of S is the set of all subsets of S, denoted by P(S).

If a set has n elements, then its power set has
2n elements
Example:
P({a ,b }) = {Ø,{a},{b},{a ,b }}
Practice
How many elements do they have?
1. What is P({1,2,3})?
2. What is P({a, b, c, d})?
Ordered n-tuple
The order of elements in a collection is often
important
Ordered n-tuple (a1 ,a2 ,... ,an ) is the ordered
collection that has :
a1 as its first element
a2 as its second element
...
an as its nth element
Example: (a ,b ) is an ordered 2-tuple (ordered pair).
Ordered n-tuple
Let A=(a1, a2, …, an) and B=(b1, b2, …, bn) be ordered
n-tuples.
A and B are equal if and only if each corresponding
pair of their elements are equal, denoted by A=B.
A=B if and only ai = bi and for i = {1,2,…,n}
Example: Assume c ≠ b.
Are ordered 3-tuples (a ,b ,c ) and (a ,c ,b ) equal?
Cartesian product
• The Cartesian product of A and B, denoted by A × B,
is the set of all ordered pairs (a, b), where a ∈ A and
b ∈ B. Hence,
A × B = {(a, b) | a ∈ A ∧ b ∈ B}.
Example:
Cartesian product of A = {1, 2} and B = {a, b, c}?
A × B = {(1, a), (1, b), (1, c), (2, a), (2, b), (2, c)}.
Practice
Given A = {1, 2} and B = {a, b, c}
What are A x B and B x A?
A × B = {(1, a), (1, b), (1, c), (2, a), (2, b), (2, c)}.
B × A = {(a,1),(a,2),(b,1),(b,2),(c,1),(c,2)}
• Are A x B and B x A equal?

• A x B and B x A are equal if A = ∅ or B = ∅ (so that A
x B = ∅) or A = B
Cartesian product
The Cartesian product of sets A1, A2, …, An, denoted
by A1 × A2 × … × An is the set of ordered n-tuples (a1,
a2, …, an), where ai belongs to Ai for i = 1,2, …,n.
In other words,
A1 × A2 × … × An = {(a1, a2, . . . , an) | ai ∈ Ai for i = 1,
2, . . . , n}.
Cartesian Products (example)
Example:
What is the Cartesian product of A × B × C
where A= {0,1}, B = {1,2}, and C = {0,1,2}?
Solution:
A × B × C= {(0,1,0), (0,1,1), (0,1,2), (0,2,0), (0,2,1),
(0,2,2), (1,1,0), (1,1,1), (1,1,2), (1,2,0), (1,2,1), (1,2,2)}
Practice questions
2.1: 2,3,5,7,13,15,17,19,23,29,33,35

Ex 2.1 Sets

Uploaded by

Copyright:

Available Formats

Ex 2.1 Sets

Uploaded by

Document Information

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Ex 2.1 Sets

Uploaded by

Copyright:

Available Formats

CC1041

National College of Business Administration and Economics main

• Sets can have other sets as members

 2. {1, 2, 3, 4} and {4, 1, 3, 2}

 3. {a, b, c, d, e} and {a, a, c, b, e, d}

 4. {a, e, i, o} and {a, e, i, o, u}

 2. {1, 2, 3, 4} and {4, 1, 3, 2} yes

 3. {a, b, c, d, e} and {a, a, c, b, e, d} yes

 4. {a, e, i, o} and {a, e, i, o, u} } no

Singleton set: a set with one element

• A ⊆ B if and only if ∀x(x ∈ A → x ∈ B)

• For A ⊂ B to be true, it must be the case that

A set is said to be infinite if it is not finite.

• The power set of S is the set of all subsets of S, denoted by P(S).

• Are A x B and B x A equal?

You might also like