CHAPTER - 1
Set Theory
Books
Textbooks:
1. Discrete Mathematics and Its Applications.
Kenneth H. Rosen
2. Discrete Mathematics
Seymour Lipschutz & Marc Lipson
2
Discrete Mathematics
Discrete Mathematics is a branch of
mathematics involving discrete objects rather
than continuous. Discrete objects are those
which are separated from (not connected
to/distinct from) each other. Integers (aka
whole numbers), graphs, automobiles, houses,
people etc. are all discrete objects.
It is increasingly being applied in the practical
fields of mathematics and computer science.3
Topics in Discrete Mathematics
Though there cannot be a definite number of branches of Discrete
Mathematics, the following topics are almost always covered in
any study regarding this matter:
® Sets, Relations and Functions
® Mathematical Logic
® Group theory
® Counting Theory
® Probability
® Mathematical Induction and Recurrence Relations
® Graph Theory
® Trees
® Boolean Algebra
4
Set Theory
A set is a collection of objects.
These objects are sometimes called elements or members of the
set.
Example:
The set A is, A = {a, e, i, o, u}.
We write a, e ∈ A to denote that a and e are an element/member
of the set A.
The notation b ∉ A denotes that b is not an element of the set A.
5
Specifying Sets
Sets can be represented in two ways:
1. Roster or Tabular Form
2. Set Builder Notation
Roster or Tabular Form
The set is represented by listing all the elements containing it. The
elements are enclosed within braces {} and separated by commas.
Example 1:
Set of vowels in English alphabet, A = {a,e,i,o,u}
Example 2:
Set of odd numbers less than 10, B = {1,3,5,7,9}
6
Cont.
Discrete data is counted.
Continuous data is measured
Discrete Data: Discrete Data can only take certain values.
Example: the number of students in a class (you can't have half a student).
Continuous Data: Continuous Data can take any value (within a range)
Examples:
A person's height: could be any value (within the range of human heights), not
just certain fixed heights,
A dog's weight,
The length of a leaf,
Lots more!
7
Cont.
Set Builder Notation:
The set is defined by specifying a property which characterized
the elements in the set.
Example 1: The set {a,e,i,o,u} is written as:
A = { x : x is a vowel in English alphabet}
Example 2: The set {1,3,5,7,9} is written as:
B = { x : 1≤x<10, (x%2) ≠ 0}
Note that a letter, usually x, is used to denote a typical member
of the set; and the colon is read as “such that” and the comma as
“and.”
8
Subsets
If every element in a set A is also an element of a set B , then A is
called a subset of B. we also say that A is contained in B or that B
contains A. This relationship is written A ⊆ B or B ⊇ A.
Example: Let, X = { 1, 2, 3, 4, 5, 6 } and Y = { 1, 2 }.
Here set Y is a subset of set X. Because all the elements of set Y is in
set X.
. Hence, we can write Y ⊆ X .
If A is not a subset of B, that is, if at least one element of A does
not belong to B, we write A ∉ B.
9
Equality
Two sets are equal if and only if they have the same
elements.
A = B if and only if A ⊆ B and B ⊆ A
Example:{1,2,3} = {3,1,2} = {1,2,1,3,2}
Note: Duplicates don't contribute anything new to a set,
so remove them. The order of the elements in a set doesn't
contribute anything new.
Example: Are {1,2,3,4} and {1,2,2,4} equal?
No!
1
proper subset
Definition: A set A is said to be a proper subset of B if and only if
A ⊆ B and A ≠B.
We denote that A is a proper subset of B with the notation A ⊂ B.
Example:
A={1,2,3}, B ={1,2,3,4,5}
Is: A ⊂ B ? Yes.
1
Finite and Infinite set
Sets can be finite or infinite.
A set S is said to be finite if S is empty or if S contains exactly m
elements where m is a positive integer; otherwise S is infinite.
Examples:
(a) The set A of the letters of the English alphabet.
The set D of the days of the week are finite sets.
Specifically, A has 26 elements and D has 7 elements
(b) Let E be the set of even positive integers.
………E={2,4,6……}
The set of natural numbers is an infinite set.
N = {1, 2, 3, ... }
1
Disjoint set
Two sets A and B are said to be disjoint if they have no elements in
common.
Therefore, disjoint sets have the following properties:
n(A ∩ B) = ∅
n(A ∪ B) = n(A) + n(B)
A and B are disjoint if and only if A ∩B = ∅
For example, suppose
A = {1, 2}, B= {4, 5, 6}, and C = {5, 6, 7, 8}
Then A and B are disjoint, and A and C are disjoint. But B and C
are not disjoint since B and C have elements in common, e.g., 5 and
6.
1
Power set
Given a set S, the power set of S is the set of all subsets of S.
The power set is denoted by P(S).
What is the power set of the set {0, 1, 2}?
Solution: The power set P({0, 1, 2}) is the set of all subsets of {0,
1, 2}. Hence,
P({0, 1, 2}) = {∅, {0}, {1}, {2}, {0, 1}, {0, 2}, {1, 2}, {0, 1, 2}}.
Note that the empty set and the set itself are members of this set of
subsets.
1
Complements, Differences, Symmetric
Differences
Complement of a set A, denoted by AC or A, is the set of elements
which belong to U but which do not belong to A.
More specifically, A'= (U–A) where U is a universal set which
contains all objects.
Example:
U={1,2,3,4,5,6,7,8} A ={1,3,5,7}
AC or A = {2,4,6,8}
Differences: A-B or A\B.
A = {1,2,3,6} B = { 2, 4, 6, 9}
A - B = { 1, 3}, B – A = {4, 9}
1
Symmetric Differences
The symmetric difference of sets A and B, denoted by A ⊕ B,
consists of those elements which belong to A or B but not to both.
That is,
A ⊕ B = (A ∪ B)\(A ∩ B) or
A ⊕ B = (A\B) ∪ (B\A)
Example :
A={1,2,3,4,5,6}and B={4,5,6,7,8,9}. Then
A\B={1,2,3}, B\A={7,8,9}
A ⊕ B = {1,2,3,7,8,9}
1
Universal Set, Empty Set
A universal set is the set of all elements under consideration,
which we denote by U.
Example: We may define U as the set of all animals on earth. In
this case, set of all animals is a subset of U, set of all fishes is a
subset of U, set of all insects is a subset of U, and so on.
Empty Set or Null Set
An empty set contains no elements. It is denoted by ∅. As the
number of elements in an empty set is finite, empty set is a finite
set. The cardinality of empty set or null set is zero.
1
Venn Diagrams
Venn diagram, invented in1880 by John Venn, is a schematic
diagram that shows all possible logical relations between different
mathematical sets.
Examples
1
Set Theory Symbols
1. ∈ “is an element of”
2. ∉ “is not an element of”
3. ⊂ “is a proper subset of”
4. ⊆ “is a subset of”
5. ⊄ “is not a subset of”
6. ∅ the empty set; a set with no elements
7. ∩ intersection
8. ∪ union
1
Cont.
9. A or A’ the compliment of A; all elements not in A
10. A – B all elements in A but not in B
11. n(A) the number of elements in A
12. A = B A is equal to B; A and B contain the same elements
13. A ≅ B A is equivalent to B ; A and B contain the same number
of elements
2
H.W
Techniques of Counting
❖ 5.1 Introduction 88
❖ 5.2 Basic Counting Principles 88
❖ 5.3 Mathematical Functions 89
❖ 5.4 Permutations 91
❖ 5.5 Combinations 93
❖ 5.6 The Pigeonhole Principle 94
❖ 5.7 The Inclusion–Exclusion Principle 95
❖ 5.8 Tree Diagrams
2
H.W
Probability
❖ 7.1 Introduction
❖ 7.2 Sample Space and Events
❖ 7.3 Finite Probability Spaces
❖ 7.4 Conditional Probability
❖ 7.5 Independent Events
❖ 7.6 Independent Repeated Trials, Binomial Distribution
❖ 7.7 Random Variables
❖ 7.8 Chebyshev’s Inequality, Law of Large Numbers
2
H.W
Properties of the Integers
❖ 11.1 Introduction 264
❖ 11.2 Order and Inequalities, Absolute Value 265
❖ 11.3 Mathematical Induction 266
❖ 11.4 Division Algorithm 267
❖ 11.5 Divisibility, Primes 269
❖ 11.6 Greatest Common Divisor, Euclidean Algorithm 270
❖ 11.7 Fundamental Theorem of Arithmetic 273
❖ 11.8 Congruence Relation 274
❖ 11.9 Congruence Equations 278
2
K. M. Aslam Uddin
Assistant Professor (ICE)
Noakhali Science and Technology University
24
*