1. Functions vs. Relations
The Distinction
A function maps each input to exactly one output. A relation generalizes this: an input can map to multiple outputs, or none.
Not Functions (Relations):
- $x < y$ (One number is less than infinitely many others)
- $x$ is a parent of $y$ (A parent can have multiple children)
- Matrix $A$ is orthogonal to Matrix $B$
- Triangle $t_1$ congruent to $t_2$
Function ($y=x^2$)
Passes Vertical Line Test
Relation ($x=y^2$)
Fails Vertical Line Test
2. Binary Relations & Inverses
Definition
A binary relation $R$ from set $A$ to set $B$ is a subset of $A \times B$.
The inverse relation $R^{-1}$ flips the pairs: $R^{-1} = \{(y, x) \in B \times A
\mid (x, y) \in R\}$.
Finite Example
Set A: {2, 3, 4} | Set B: {2, 6, 8}
Relation R: $a$ divides $b$ ($a|b$)
R
(2,2)
(2,6)
(2,8)
(3,6)
(4,8)
R⁻¹
(2,2)
(6,2)
(8,2)
(6,3)
(8,4)
Inverse Meaning: $b$ is a multiple of $a$.
Infinite Example
Relation: $v = 2|u|$ on $\mathbb{R} \times \mathbb{R}$.
Graph R ($v=2|u|$)
Graph R⁻¹ ($u=2|v|$)
R⁻¹ is not a function (fails vertical line test).
3. Properties of Relations
Reflexive
$(x,x) \in R$ for all $x$.
"Every element loops to itself."
Symmetric
If $(x,y) \in R$, then $(y,x) \in R$.
"Arrows go both ways."
Transitive
If $(x,y) \in R$ and $(y,z) \in R$, then $(x,z) \in R$.
"Direct paths exist for indirect routes."
Analyze R on set {0, 1, 2, 3}
R = {(0,0), (0,1), (0,3), (1,0), (1,1), (2,2), (3,0), (3,3)}
YES
(0,0)..(3,3) all present.
YES
(0,1)↔(1,0), (0,3)↔(3,0).
NO
(1,0) & (0,3) exist, but (1,3) is missing.
4. Equivalence Relations
A relation is an Equivalence Relation if it is Reflexive, Symmetric, and Transitive. It partitions a set into disjoint Equivalence Classes.
Example: "Least Element" on Power Set
Let $X$ be the power set of $\{1, 2, 3\}$. Relation $R$: $A R B \iff \min(A) = \min(B)$.
Equivalence Classes:
- [{1}] (Min is 1): $\{1\}, \{1,2\}, \{1,3\}, \{1,2,3\}$
- [{2}] (Min is 2): $\{2\}, \{2,3\}$
- [{3}] (Min is 3): $\{3\}$
Example: Congruence Modulo $n$
$a \equiv b \pmod n \iff n \mid (a-b)$. This partitions integers into $n$ classes.
{..., -3, 0, 3, 6...}
{..., -2, 1, 4, 7...}
{..., -1, 2, 5, 8...}
Example for Mod 3
5. Modular Arithmetic Applications
1. Finding the Last Digit
Find the units digit of $1483^{8650}$.
1. We need $3^{8650} \pmod{10}$.
2. Pattern of powers of 3:
$3^1=3, 3^2=9, 3^3=7, 3^4=1$. (Cycle of 4)
3. Exponent $8650 = 4(2162) + 2$. Remainder is 2.
4. $3^{8650} \equiv 3^2 \equiv \mathbf{9}$.
2. Inconsistent Systems
Solve $16x + 12y = 32$ and $40x - 9y = 7$.
Apply Mod 3:
Eq 1: $16 \equiv 1, 12 \equiv 0, 32 \equiv 2$.
$\implies 1x + 0y \equiv 2 \implies
\mathbf{x \equiv 2}$.
Eq 2: $40 \equiv 1, -9 \equiv 0, 7 \equiv 1$.
$\implies 1x + 0y \equiv 1 \implies
\mathbf{x \equiv 1}$.
Contradiction! $x$ cannot be 1 and 2. No integer solution.
3. Universal Product Code (UPC) Check Digit
Code: 88442334010. Find the 12th digit.
Formula:
$k = 3(\text{Sum Odd Pos}) + (\text{Sum Even Pos})$
$a_{12} = (210 - k) \pmod{10}$
Odd (1,3,5...): $8+4+2+3+0+0 = 17$
Even (2,4,6...): $8+4+3+4+1 = 20$
$k = 3(17) + 20 = 51 + 20 = 71$.
$a_{12} = (210 - 71) \pmod{10} = 139 \pmod{10} = \mathbf{9}$.