# 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}
• P({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?
• |A x B| = ??

## Functions

• A function specifies an input-output relationship

• A given input (always) produces a specified output
• Written as f(a) = b

• A function is also known as a mapping
• Example: f maps a to b

## 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
• f(x) = f(y) iff x = y

• 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
• 1:1
• onto
• 1:1 and onto

## 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,