Math Home
Set Theory

Injections

An injection is a function \(f:A \rightarrow B\) such that if \(a_1, a_2 \in A\) are distinct then \(f(a_1) \neq f(a_2).\)

Example: Let \(A = \{a,b,c\}\) and \(B = \{2,4,6,8\}.\) Define two functions, \(f: A \rightarrow B\) and \(g: A \rightarrow B\) as follows: \[f(a) = 2, f(b) = 8, f(c) = 6\] \[g(a) = 4, g(b) = 6, g(c) = 4\] The function \(f\) is an injection because \(f\) maps every element of \(A\) to a different element of \(B.\) The function \(g\) is not an injection because \(g\) maps both \(a\) and \(c\) to \(4.\)

Surjections

A surjection is a function \(f:A \rightarrow B\) such that for every \(b \in B\) there exists an \(a \in A\) such that \(f(a) = b.\)

Example: Let \(A = \{1,2,3,4\}\) and \(B = \{r,s,t\}.\) Define two functions, \(f: A \rightarrow B\) and \(g: A \rightarrow B\) as follows: \[f(1) = r, f(2) = s, f(3) = t, f(4) = r\] \[g(1) = r, g(2) = r, g(3) = s, g(4) = s\] The function \(f\) is a surjection. Given any element in \(B,\) for example \(s,\) there is an element in \(A\) such that \(f\) maps to that element. In this case, \(f(2) = s.\) The function \(g\) is not a surjection because there is no element in \(A\) that maps to \(t.\)

Bijections

A bijection is a function that is both an injection and a surjection.

Example: Let \(A = \{u,v,w\}\) and \(B = \{i,j,k\}.\) Define the function \(f: A \rightarrow B\) by \[f(u) = i, f(v) = j, f(w) = k\] The function \(f\) is injective because \(f\) maps every element of \(A\) to a different element of \(B.\) Also, \(f\) is surjective because every element of \(B\) gets mapped to. Therefore, \(f\) is a bijection.