Chapter 0
Mathematical Notions and
Terminology
Sets and Functions
Topics
 Sets
 Functions
 Graphs (Skip for now)
Sets
 A set is a "group of objects represented as a unit"
 Properties:
 Order does not matter
 Duplicates are ignored
 Set size: {a,b,c} = 3
 Empty set: size=0. Written as {} or as φ (Greek letter phi)
 Infinite set
 Sizes of the naturals, integers, rationals, reals
 1:1, onto mappings
 Diagonalization arguments
 Multiset (duplicates not ignored)
 Set: {2, 17, 2, 4} = {2, 4, 17}
 Multiset: {2, 17, 2, 4} ≠ {2, 4, 17}
 Operations: Union, intersection, complement
 Complement is all elements NOT in the set
 Must know the set's universe to find its complement
Power Set
 Power set of set A:
 The set of all subsets of A
 Written as P(A)
 Example: What is the power set of A when A = {a, b}
 Power set elements can be arranged in a lattice that shows the subset relation:
 P is higher than Q with a line between them iff Q is a proper subset of P.
 Don't include lines that are implied by other lines.
 Question: Does the power set of S have more elements than
S?
 Always?
 What sets should we think about?
Sequences and Tuples
 Sequences
 List of objects in some order
 Associate each object with a natural number (ie 1, 2, 3, ...)
 A string is a sequence of characters
 Can be finite or infinite
 Tuples: Finite sequences
 ktuple  sequence of length k (eg (x, y, z) coordinates)
 pair  sequence of length 2 (eg (x, y) coordinates)
 Cartesian product (ie cross product) of 2 or more sets
 The cross product of an ordered group of sets is a set of tuples, with each tuple
containing one element from each set, in order
 Example: {a, b, c} x {c, d} = ?
 How large is the Cartesian product A x B?
Functions
 A function specifies an inputoutput relationship
 A given input (always) produces a specified output
 A function is also known as a mapping
Functions: Domain and Range
 Domain of function f: set of possible inputs for f
 Range of f: set from which outputs of f are taken
 We specify functions using the notation f: D → R
 Example 1: Integer Square function  Z → Z
 Example 2: Square root function  Z^{+} → R
 Example 3: Integer Plus function  Z x Z → Z
 We only consider functions that are defined on the entire domain
Functions: Several Ways to Specify
 Procedure to compute output from input
 Table:
 If domain is set of single values: 1D table (eg increment mod 5 maps Z_{5}
to Z_{5})
x  f(x) 
0  1 
1  2 
2  3 
3  4 
4  0 
 If domain is set of pairs: 2D table (eg addition mod 3 maps Z_{3} x Z_{3}
to Z_{3})
 0  1  2 
0  0  1  2 
1  1  2  0 
2  2  3  1 
 Set of tuples
 Example 1: increment mod 3: {(0,1), (1,2), (2,0)}
 Example 2: addition mod 3: {((0,0),0), ((0,1),1), ((0,2),2), ..., ((2,2), 1)}
 Arrow diagrams, typically with domain on left
 Each element of domain has exactly one arrow coming from it
 (We assume functions are total (ie defined on entire domain)
Functions: Onto
 An Onto function uses all elements of the range

Assume f: Z → Z and
g: Z → Z_{+} and
h: Z^{+} → Z_{+}
 Are these functions onto?
 f(x) = x * x * x
 f(x) = x * x
 f(x) = x
 f(x) = x
 f(x) = x
 f(x) = 3
 g(x) = x * x * x
 g(x) = x * x
 g(x) = x
 g(x) = x
 g(x) = 3
 h(x) = x * x * x
 h(x) = x * x
 h(x) = x
 h(x) = x
 h(x) = 3
Functions: OnetoOne
 Onetoone function  each range element is mapped to by only one domain
element
 Written as 1:1

Assume f: Z → Z and
g: Z → Z_{+} and
h: Z^{+} → Z_{+}
 Are these functions 1:1?
 f(x) = x * x * x
 f(x) = x * x
 f(x) = x
 f(x) = x
 f(x) = x
 f(x) = 3
 g(x) = x * x * x
 g(x) = x * x
 g(x) = x
 g(x) = x
 g(x) = 3
 h(x) = x * x * x
 h(x) = x * x
 h(x) = x
 h(x) = x
 h(x) = 3
Functions: 1:1 and Onto

Assume f: Z → Z and
g: Z → Z_{+} and
h: Z^{+} → Z_{+}
 Are these functions 1:1 and onto?
 f(x) = x * x * x
 f(x) = x * x
 f(x) = x
 f(x) = x
 f(x) = x
 f(x) = 3
 g(x) = x * x * x
 g(x) = x * x
 g(x) = x
 g(x) = x
 g(x) = 3
 h(x) = x * x * x
 h(x) = x * x
 h(x) = x
 h(x) = x
 h(x) = 3
 For function f: D → R, what can we say about the relative sizes of D and R if
f is
Functions: More Terminology
 Arguments
 kary, arity
 unary function, binary function
Logic: IFF
 IFF = if and only if
 Example: p iff q means if p then q AND if q then p
 Also written as p ⇔ q
 When is p ⇔ q true?
Graphs (Ignore for now)
 Set of points (called nodes or vertices)
and set of lines (called edges) connecting some of the points
 Degree of a node: Number of edges at that node
 Specify edges with pair of nodes
 Subgraph: G is a subgraph of H if nodes of G are a subset
of nodes of H
 Connected graph: a path exists between any pair of nodes
 Unconnected graph: some pair of nodes does not have a path between them
 Notation: G = (V, E) for set of nodes V and set of edges E
Graphs: Paths and Cycles (Ignore for now)
 Path: a sequence of nodes connected by edges
 Simple path: no repeated nodes
 Cycle: a path that starts and ends in the same node
 Simple cycle: Cycle that repeats only the first and last
node
Graphs: Trees (Ignore for now)
 Tree: Graph that is connected and has no (simple) cycles
 Leaves: nodes of degree 1
 Root: designated node
Directed Graphs (Ignore for now)
 Directed Graph: Connects nodes with arrows rather than
lines
 Indegree, outdegree
 Directed path: path in which every arrow points in the
same direction
 Strongly connected: a directed graph is strongly connected
if a directed path connects every two nodes
 Useful for depicting binary relations
ITEC 420 Course Page,