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
- k-tuple - 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 input-output 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 Z5
to Z5)
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 Z3 x Z3
to Z3)
| 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: One-to-One
- One-to-one 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
- k-ary, 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,