Binary Relations and Functions
Binary Relation
A binary relation is a set of ordered pairs (x, y).
Example: {(0,2), (1,3), (2,4)}
Function
A function is a binary relation where each input x has exactly one output y.
If (x,y) and (x,z) are in the function, then y = z.
Example: f = {(0,2),(1,3),(2,4),(3,5),(4,6)}
Function Rule
A function can also be written as a formula instead of a list of pairs.
f(x) = x + 2 (for x ≤ 4 in N)
Modular Function Example
Some functions use modulo arithmetic.
g(x) = (x + 3) mod 5
Set Representation of g
A function can also be written as a set of ordered pairs generated by a rule.
g = {(0,3),(1,4),(2,0),(3,1),(4,2),...}
Key Idea
Functions are the smallest (under ⊆) sets of pairs that satisfy a rule.