Basic Structures: Sets, Functions,

Sequences, Sums, and Matrices

Sets
Set Operations
Sets

 Sets are used to group objects together.

 Uppercase letters are usually used to denote sets

 Lowercase letters are usually used to denote elements of sets.
How to describe a set?

 Roster method
 Set builder notation
Roster Method

 A notation where all members of the set are listed between braces.
 For example, the notation {a, b, c, d} represents the set with the four elements a, b, c, and
d.
 The set V of all vowels in the English alphabet can be written as V = {a, e, i, o, u}.
 The set O of odd positive integers less than 10 can be expressed by O = {1, 3, 5, 7, 9}.
 The set of positive integers less than 100 can be denoted by {1, 2, 3, … , 99}.
Set builder notation

 characterize all those elements in the set by stating the property or properties they must
have to be members
 We often use this type of notation to describe sets when it is impossible to list all the
elements of the set.
 The general form of this notation is {x ∣ x has property P} and is read “the set of all x such
that x has property P.”
 For instance, the set O of all odd positive integers less than 10 can be written as
O = {x ∣ x is an odd positive integer less than 10}, or,
specifying the universe as the set of positive integers, as
O = {x ∈ Z+ ∣ x is odd and x < 10}.
Set builder notation

 These sets, each denoted using a boldface letter, play an important role in discrete
mathematics:
 N = {0, 1, 2, 3, …}, the set of all natural numbers
 Z = {… ,−2,−1, 0, 1, 2, …}, the set of all integers
 Z+ = {1, 2, 3, …}, the set of all positive integers
 Q = {p∕q ∣ p ∈ Z, q ∈ Z, and q ≠ 0}, the set of all rational numbers
 R, the set of all real numbers
 R+, the set of all positive real numbers
 C, the set of all complex numbers.
 Types of Real Numbers

 A real number is a number that can be found

on the number line.
 Real numbers are mainly classified into
rational and irrational numbers.

Rational numbers include all integers and
fractions.

All negative integers and whole numbers make
up the set of integers.

Whole numbers comprise of all natural
numbers and zero.
 An Irrational Number is a real number that
cannot be written as a simple fraction.
Note that some people do not consider 0 a natural number, so be careful to check how
the term natural numbers is used when you read other books.
Sets can have other sets as members

 The set {N, Z, Q, R} is a set containing four elements, each of which is a set. The four
elements of this set are N, the set of natural numbers; Z, the set of integers; Q, the set of
rational numbers; and R, the set of real numbers.
 Note that the concept of a datatype, or type, in computer science is built upon the concept
of a set.
 In particular, a datatype or type is the name of a set, together with a set of operations that
can be performed on objects from that set.
 For example, boolean is the name of the set {0, 1}, together with operators on one or more
elements of this set, such as AND, OR, and NOT.
Two sets to be equal

 The sets {1, 3, 5} and {3, 5, 1} are equal, because they have the same elements.
 Note that the order in which the elements of a set are listed does not matter.
 Note also that it does not matter if an element of a set is listed more than once, so {1, 3, 3,
3, 5, 5, 5, 5} is the same as the set {1, 3, 5} because they have the same elements.
Two sets to be equal

• Two sets are called equal if they have exactly the same elements.
• The order is irrelevant.
• Any repetition of an element is ignored.
• If a is an element of a set S, we write a ∈ S.
• If b is not an element of a set S, we write b ∉ S.
Empty Set

 set that has no elements

 Also called null set
 denoted by ∅ or by { }
Singleton Set

 A set with one element

 set ∅ is an empty set
 set {∅} is a singleton set
Exercises

 List the members of these sets.

 {x ∣ x is a real number such that x2 = 1}
 {−1,1}

 {x ∣ x is a positive integer less than 10}

 {1,2,3,4,5,6,7,8,9}

 {x ∣ x is the square of an integer and x < 50}

 {0,1,4, 9, 16, 25, 36, 49}

 {x ∣ x is an integer such that x2 = 2}

 ∅
Exercises

 Determine whether each of these pairs of sets are equal.

 {1, 3, 3, 3, 5, 5, 5, 5, 5}, {5, 3, 1}
 {{1}}, {1, {1}}
 ∅, {∅}
Exercises

 For each of the following sets, determine whether 2 is an element of that set.
 {x ∈ R | x is an integer greater than 1}
 {x ∈ R | x is the square of an integer}
 {2,{2}}
 {{2},{{2}}}
 {{2},{2,{2}}}
 {{{2}}}
Venn Diagram

 Sets can be represented graphically using Venn diagrams, named after the English
mathematician John Venn, who introduced their use in 1881
 In Venn diagrams the universal set U, which contains all the objects under consideration, is
represented by a rectangle.
 Inside this rectangle, circles or other geometrical figures are used to represent sets.
 Sometimes points are used to represent the particular elements of the set.
 Venn diagrams are often used to indicate the relationships between sets.
Example
 Draw a Venn diagram that represents V, the set of vowels in the English alphabet.
 Solution: We draw a rectangle to indicate the universal set U, which is the set of the 26
letters of the English alphabet. Inside this rectangle we draw a circle to represent V. Inside
this circle we indicate the elements of V with points.
Example

 In the Venn diagram below, the universal set is E = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 }, and each of
these numbers has been placed somewhere within the rectangle.

 The region inside the circle represents the set A of odd whole numbers between 0 and 10. Thus
we place the numbers 1, 3, 5, 7 and 9 inside the circle, because A = { 1, 3, 5, 7, 9 }. Outside the
circle we place the other numbers 0, 2, 4, 6, 8 and 10 that are in E but not in A.
Example

 For example, let S = { 0, 1, 2 }, and T = { 0, 1, 2, 3, 4 }. Then S is a subset of T, as

illustrated in the Venn diagram below.
Subsets

 the elements of one set are also the elements of a second set
Example

 The set of all odd positive integers less than 10 is a subset of the set of all positive integers
less than 10
 the set of rational numbers is a subset of the set of real numbers,
Theorem 1

 every nonempty set S is guaranteed to have at least two subsets, the empty set and the set S
itself, that is, ∅ ⊆ S and S ⊆ S.
Proper subset

 When we wish to emphasize that a set 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.
Exercises

 Suppose that A={2,4,6,7}, B={2,4,6}, C={2,6}, D={4,6,8}, E={2,4,6} and F={4,6,8}.

Determine which of these sets are subsets or proper subsets of which other of these sets.
Exercises
 Determine whether each of these statements is true or false.
 0∈∅ -
 ∅∈{0} -
 {0} ⊂ ∅ -
 ∅ ⊂ {0} -
 {0}∈{0} -
 {0} ⊂ {0} -
 {∅} ⊆ {∅} -
 x ∈ {x} -
 {x} ⊆ {x} -
 {x}∈{x} -
 {x} ∈ {{x}} -
 ∅ ⊆ {x} -
 ∅ ∈ {x} -
The Size of a Set

 The cardinality of a set is a measure of a set's size, meaning the number of elements in the
set. For instance, the set A = {1,2,4} has a cardinality of 3 for the three elements that are in
it. The cardinality of a set is denoted by vertical bars, like absolute value signs; for
instance, for a set A its cardinality is denoted |A|.
 Let A be the set of odd positive integers less than 10. Then |A| = 5.
 Let S be the set of letters in the English alphabet. Then |S| = 26.
 Because the null set has no elements, it follows that | ∅| = 0.
Cardinality of a Set
Exercises

 What is the cardinality of each of these sets?

 {a}
 {{a}}
 {a, {a}}
 {a, {a}, {a, {a}}}
 ∅
 {∅}
 {∅, {∅}}
 {∅, {∅}, {∅, {∅}},{{∅}}}
Power Sets

 The total number of elements of a set is 2n

 The power set P(S) is the set of all subsets of S, including the empty/null set & the set S itself
 What is the power set of the set {0, 1, 2}?
 Answer: 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}}.
Exercises

 Find the power set of each of these sets, where a and b are distinct elements.
 {a}
 P({a})={∅, {a}}
 {a, b}
 P({a, b})= {∅, {a}, {b}, {a, b}}
 {∅, {∅}}
 P({∅, {∅}) = {∅, {∅}, {{∅}}, {∅, {∅}}}
Power Sets

 A= {1,2}, B={2,3,4}, C={1}

 P(A) =
 P(B) =
 P(C) =
Exercises

 How many elements does each of these sets have where a and b are distinct elements?
 P({a, b, {a, b}})
 P{∅, a, {a}, {{a}}})
 P(∅)

Note: The number of elements in a power set is equal to 2n , where n is the number of elements
in the set. Empty sets are included as an element

---The cardinality of a set is the number of elements contained.

Ordered n-tuple

 Because sets are unordered, a different structure is needed to represent ordered collections.
This is provided by ordered n-tuples.
Cartesian Product

 What is the Cartesian product of A = {1, 2} and B = {a, b, c}?

 The Cartesian product A × B is
A × B = {(1, a), (1, b), (1, c), (2, a), (2, b), (2, c)}.

 The Cartesian product B × A is

 B × A = {(a, 1), (a, 2), (b, 1), (b, 2), (c, 1), (c, 2)}.

Note that the Cartesian products A × B and B × A are not equal

unless A = ∅ or B = ∅
Cartesian Product
Exercises
 A = {a, b, c}, B = {x, y}, and C = {0, 1}
 A × B × C.

 C = {0, 1}, B = {x, y}, A = {a, b, c}

 C × B × A.

 C = {0, 1}, A = {a, b, c}, B = {x, y}

 C × A × B.
A2
Exercises

 Find A2 if
 A = {0, 1, 3}
 {(0, 0), (0, 1), (0, 3), (1, 0), (1, 1), (1, 3), (3, 0), (3, 1), (3, 3)}
 A = {1, 2, a, b}
 {(1, 1), (1, 2), (1, a), (1, b), (2, 1), (2, 2), (2, a), (2, b), (a, 1), (a, 2), (a, a), (a, b), (b, 1), (b, 2), (b,
a), (b, b)}
References

 Discrete Mathematics and Its Applications by Rosen, K.

 https://www.purplemath.com/modules/venndiag3.htm
 https://www.cimt.org.uk/projects/mepres/book7/bk7i1/bk7_1i3.htm
 https://www.math24.net/set-operations-venn-diagrams
 http://amsi.org.au/teacher_modules/Sets_and_venn_diagrams.html
 https://www.cs.odu.edu/~toida/nerzic/level-a/set/set_operations.html
 https://www.tutorialspoint.com/set-operations