The Central Idea
A relation records which objects are connected. A mapping records how inputs are assigned to outputs.
Both are built from ordered pairs such as
\[ (a,b). \]The first entry identifies a source or input, while the second identifies a target or output.
Relations Begin with Cartesian Products
Let
\[ A=\{1,2,3\},\qquad B=\{a,b\}. \]The Cartesian product is
\[ A\times B=\{(1,a),(1,b),(2,a),(2,b),(3,a),(3,b)\}. \]A relation from \(A\) to \(B\) is any subset of this set of possible ordered pairs.
What Is a Relation?
A relation from \(A\) to \(B\) is a subset
\[ R\subseteq A\times B. \]For example,
\[ R=\{(1,a),(2,a),(3,b)\} \]is a relation from \(A\) to \(B\).
Relation Notation
If \((x,y)\in R\), we may write
\[ xRy. \]This means that \(x\) is related to \(y\) by the relation \(R\).
Domain of a Relation
The domain is the set of first coordinates that actually occur.
If
\[ R=\{(1,a),(2,a),(2,b)\}, \]then
\[ \boxed{\operatorname{dom}(R)=\{1,2\}}. \]Range of a Relation
The range is the set of second coordinates that actually occur.
For the same relation,
\[ \boxed{\operatorname{ran}(R)=\{a,b\}}. \]Source and Target Sets
A relation may be declared from a source set \(A\) to a target set \(B\), even if some elements of those sets never appear in an ordered pair.
Therefore the source set need not equal the actual domain, and the target set need not equal the actual range.
One Input May Relate to Several Outputs
The relation
\[ R=\{(1,a),(1,b),(2,a)\} \]is valid even though \(1\) is related to two different outputs.
Ordinary relations do not require a unique output.
A Relation May Leave Inputs Unused
If
\[ A=\{1,2,3\},\qquad R=\{(1,a),(2,b)\}, \]then no pair begins with \(3\).
This is allowed for a relation.
Relations on a Set
A relation on \(A\) is a subset of
\[ A\times A. \]Both coordinates therefore come from the same underlying set.
Example: Less Than
On
\[ A=\{1,2,3\}, \]define \(xRy\) when \(x
Example: Divisibility
On
\[ A=\{1,2,3,6\}, \]define \(xRy\) when \(x\mid y\). Examples include
\[ 1R6,\qquad2R6,\qquad3R6,\qquad6R6. \]Relations as Tables
A finite relation can be displayed as a list or table of input-output connections.
| Input | Related output |
|---|---|
| 1 | a |
| 2 | a |
| 3 | b |
Finite tables can specify every connection explicitly.
Arrow Diagrams
A finite relation may also be visualized with arrows:
\[ 1\to a,\qquad2\to a,\qquad3\to b. \]Several arrows may leave one source if the relation connects that source to several targets.
Relation Matrices
For finite sets \(A=\{a_1,\ldots,a_m\}\) and \(B=\{b_1,\ldots,b_n\}\), define
\[ M_{ij}=\begin{cases}1,&(a_i,b_j)\in R,\\0,&(a_i,b_j)\notin R.\end{cases} \]This zero-one matrix records the entire relation.
Example: Relation Matrix
If
\[ R=\{(a_1,b_1),(a_2,b_1),(a_2,b_2)\}, \]then
\[ \boxed{M=\begin{bmatrix}1&0\\1&1\\0&0\end{bmatrix}}. \]What Is a Mapping?
A mapping assigns elements of one set to elements of another and is commonly written
\[ f:A\to B. \]In ordinary mathematical usage, mapping and function are usually interchangeable terms.
What Makes a Relation a Function?
A relation from \(A\) to \(B\) is a function when every element of \(A\) has exactly one output in \(B\).
- Every input must be assigned.
- No input may have two different outputs.
Example of a Finite Function
Let
\[ A=\{1,2,3\},\qquad B=\{a,b\}. \]The relation
\[ f=\{(1,a),(2,b),(3,b)\} \]is a function because every input appears exactly once as a first coordinate.
Many Inputs May Share an Output
A function may satisfy
\[ f(1)=a,\qquad f(2)=a,\qquad f(3)=b. \]This is valid. The uniqueness requirement applies to outputs per input, not inputs per output.
An Input Cannot Have Two Function Values
The relation
\[ \{(1,a),(1,b),(2,a)\} \]is not a function from \(\{1,2\}\) to \(\{a,b\}\) because the input \(1\) has two outputs.
Every Domain Element Must Be Assigned
If a function is declared as
\[ f:A\to B, \]then every member of \(A\) must receive an output.
A relation that omits a declared domain element does not define a function on that full domain.
Domain, Codomain, and Range
For
\[ f:A\to B, \]\(A\) is the domain and \(B\) is the codomain.
The outputs actually reached form the range:
\[ \operatorname{ran}(f)\subseteq B. \]Range May Be Smaller Than the Codomain
Suppose
\[ f:\{1,2,3\}\to\{a,b,c\} \]with
\[ f(1)=a,\qquad f(2)=a,\qquad f(3)=b. \]Then
\[ \boxed{\operatorname{ran}(f)=\{a,b\}}, \]while \(c\) remains an unused codomain element.
Finite Mapping Tables
A finite function can be specified completely with a lookup table.
| \(x\) | \(f(x)\) |
|---|---|
| 1 | a |
| 2 | c |
| 3 | c |
No algebraic formula is required when every finite assignment is explicitly listed.
Mappings as State Transitions
Let
\[ S=\{A,B,C\}. \]If
\[ f(A)=B,\qquad f(B)=C,\qquad f(C)=A, \]then repeated application produces
\[ A\to B\to C\to A\to\cdots. \]Mappings as Lookup Rules
Finite mappings can formalize assignments such as
\[ \text{symbol}\mapsto\text{code}, \] \[ \text{state code}\mapsto\text{state name}, \]or
\[ \text{item}\mapsto\text{category}. \]Injective Mappings
A function is injective, or one-to-one, when different inputs always have different outputs.
Equivalently,
\[ f(x_1)=f(x_2)\Longrightarrow x_1=x_2. \]Example of an Injection
Let
\[ A=\{1,2,3\},\qquad B=\{a,b,c,d\}. \]If
\[ 1\mapsto a,\qquad2\mapsto c,\qquad3\mapsto d, \]then all outputs are distinct, so the function is injective.
Surjective Mappings
A function
\[ f:A\to B \]is surjective, or onto, when every element of \(B\) is reached.
\[ \boxed{\operatorname{ran}(f)=B}. \]Example of a Surjection
Let
\[ A=\{1,2,3,4\},\qquad B=\{a,b\}. \]If
\[ 1\mapsto a,\quad2\mapsto a,\quad3\mapsto b,\quad4\mapsto b, \]then every codomain element is reached, so the function is surjective.
Bijective Mappings
A function is bijective when it is both injective and surjective.
Every domain element is paired with exactly one codomain element, every codomain element is used, and no codomain element is used twice.
Example of a Bijection
For
\[ A=\{1,2,3\},\qquad B=\{a,b,c\}, \]the mapping
\[ 1\mapsto b,\qquad2\mapsto c,\qquad3\mapsto a \]is bijective.
Bijections Compare Cardinality
Two finite sets have the same cardinality exactly when a bijection exists between them.
\[ f:A\to B\text{ bijective}\quad\Longrightarrow\quad\boxed{|A|=|B|}. \]More Inputs Than Outputs
If finite sets satisfy
\[ |A|>|B|, \]then no function
\[ f:A\to B \]can be injective.
At least two inputs must share an output. This anticipates the pigeonhole principle.
Fewer Inputs Than Outputs
If
\[ |A|<|B|, \]then no function from \(A\) to \(B\) can be surjective.
There are not enough inputs to reach every element of the larger codomain.
Equal Finite Sizes
If
\[ |A|=|B|<\infty, \]then an injective function \(A\to B\) is automatically surjective, and a surjective function is automatically injective.
Either property therefore establishes bijectivity.
Identity Mapping
The identity mapping on \(A\) is
\[ \operatorname{id}_A:A\to A \]with
\[ \boxed{\operatorname{id}_A(x)=x}. \]It is always bijective.
Constant Mapping
A constant mapping sends every input to the same output.
For example,
\[ f(1)=f(2)=f(3)=a. \]This is a function, but it is not injective when the domain has more than one element.
Composition of Mappings
If
\[ f:A\to B,\qquad g:B\to C, \]then
\[ g\circ f:A\to C \]is defined by
\[ \boxed{(g\circ f)(x)=g(f(x))}. \]Example of Composition
If
\[ f(1)=a,\qquad f(2)=b \]and
\[ g(a)=10,\qquad g(b)=20, \]then
\[ (g\circ f)(1)=10,\qquad(g\circ f)(2)=20. \]Order Matters in Composition
Composition generally is not commutative:
\[ g\circ f\ne f\circ g. \]The rightmost mapping is applied first.
Inverse Mappings
If a function
\[ f:A\to B \]is bijective, its inverse
\[ f^{-1}:B\to A \]reverses every assignment.
If \(f(a)=b\), then \(f^{-1}(b)=a\).
Why an Inverse Function Requires a Bijection
If two inputs share an output, reversing the mapping would give that output two possible images.
If a codomain element is unused, reversing the mapping would leave it without an image.
Thus an ordinary inverse function exists precisely for bijections.
Inverse Relation
Every relation has an inverse relation:
\[ R^{-1}=\{(y,x):(x,y)\in R\}. \]If
\[ R=\{(1,a),(2,a),(3,b)\}, \]then
\[ R^{-1}=\{(a,1),(a,2),(b,3)\}. \]The inverse relation need not be a function.
Every Function Is a Relation
A function can always be represented as a set of ordered pairs, so every function is a relation.
But not every relation is a function because a general relation need not obey the exactly-one-output rule.
Relations as Directed Connections
For a relation on a finite set, each ordered pair
\[ (a,b)\in R \]may be represented as a directed connection
\[ a\to b. \]This is the bridge from relations to directed graphs.
Relations in Data Systems
Relations can describe connections such as
\[ \text{student}\;R\;\text{course}, \] \[ \text{product}\;R\;\text{supplier}, \]or
\[ \text{person}\;R\;\text{organization}. \]These relationships may be one-to-one, one-to-many, or many-to-many.
Many-to-Many Relations
A student may take several courses, while a course may contain several students.
The enrollment relation is therefore generally many-to-many rather than a function from students to courses.
Finite Mappings and Algorithms
Algorithms use finite mappings as lookup tables, substitutions, state transitions, encodings, and decision rules.
A finite-state transition rule often has the form
\[ (\text{state},\text{input})\mapsto\text{next state}. \]Common Error: Assuming Every Relation Is a Function
The relation
\[ \{(1,a),(1,b),(2,b)\} \]is valid, but it is not a function because \(1\) has two outputs.
Common Error: Confusing Codomain and Range
If
\[ f:\{1,2\}\to\{a,b,c\} \]and
\[ f(1)=a,\qquad f(2)=b, \]then the codomain is \(\{a,b,c\}\), but the range is only \(\{a,b\}\).
Common Error: Thinking Injective Means Onto
An injective function may leave codomain elements unused.
Injective means outputs are not shared; surjective means every codomain element is reached.
Common Error: Thinking Surjective Means One-to-One
A surjection may send several inputs to the same output as long as every codomain element is reached.
Common Error: Reversing a Nonbijective Function
If
\[ f(1)=a,\qquad f(2)=a, \]then reversing the pairs creates
\[ (a,1),(a,2), \]which is an inverse relation but not an inverse function.
A Reliable Procedure for Analyzing a Finite Relation
- Identify the source and target sets.
- List or inspect the ordered pairs.
- Find the actual domain and range.
- Check whether each declared input appears.
- Check whether any input has multiple outputs.
- If it is a function, test injectivity.
- Test whether every codomain element is reached.
- Classify the function as injective, surjective, bijective, or neither.
Example: Full Classification
Let
\[ A=\{1,2,3\},\qquad B=\{a,b,c\} \]and
\[ f=\{(1,b),(2,c),(3,a)\}. \]Every input has exactly one output, every output is distinct, and every codomain element is reached.
\[ \boxed{f\text{ is bijective}.} \]Practice 1: Domain and Range
Let
\[R=\{(1,a),(2,a),(4,c)\}.\]Find the domain and range.
Practice 2: Relation or Function?
Is
\[R=\{(1,a),(1,b),(2,a)\}\]a function from \(\{1,2\}\) to \(\{a,b\}\)?
Practice 3: Missing Input
Is
\[R=\{(1,a),(2,b)\}\]a function from \(\{1,2,3\}\) to \(\{a,b\}\)?
Practice 4: Injective?
Let
\[f:\{1,2,3\}\to\{a,b,c,d\}\]with \(1\mapsto a\), \(2\mapsto c\), and \(3\mapsto d\). Is \(f\) injective?
Practice 5: Surjective?
Let
\[f:\{1,2,3\}\to\{a,b\}\]with \(1\mapsto a\), \(2\mapsto a\), and \(3\mapsto b\). Is \(f\) surjective?
Practice 6: Bijective?
Let
\[f:\{1,2,3\}\to\{a,b,c\}\]with \(1\mapsto c\), \(2\mapsto a\), and \(3\mapsto b\). Is \(f\) bijective?
Practice 7: Range
Let
\[f:\{1,2,3\}\to\{a,b,c,d\}\]with \(f(1)=a\), \(f(2)=a\), and \(f(3)=c\). Find the range.
Practice 8: Inverse Relation
Find the inverse relation of
\[R=\{(1,a),(2,b),(3,a)\}.\]Practice 9: Composition
If \(f(1)=a\), \(f(2)=b\), \(g(a)=5\), and \(g(b)=8\), find \((g\circ f)(1)\) and \((g\circ f)(2)\).
Practice 10: Cardinality Reasoning
Can a function from a five-element set to a three-element set be injective? Explain.
Practice Answers
Practice 1
\(\boxed{\operatorname{dom}(R)=\{1,2,4\}}\) and \(\boxed{\operatorname{ran}(R)=\{a,c\}}\).
Practice 2
No. The input \(1\) has two different outputs.
Practice 3
No. The declared input \(3\) has no output.
Practice 4
Yes. The outputs \(a,c,d\) are all distinct.
Practice 5
Yes. Both codomain elements \(a\) and \(b\) are reached.
Practice 6
Yes. Every input has a distinct output and every codomain element is reached.
Practice 7
\(\boxed{\operatorname{ran}(f)=\{a,c\}}\).
Practice 8
\(\boxed{R^{-1}=\{(a,1),(b,2),(a,3)\}}\).
Practice 9
\((g\circ f)(1)=\boxed{5}\) and \((g\circ f)(2)=\boxed{8}\).
Practice 10
No. Five distinct inputs cannot use only three outputs without at least two inputs sharing an output.
What to Remember
- A relation from \(A\) to \(B\) is a subset of \(A\times B\).
- The domain contains first coordinates that actually occur.
- The range contains second coordinates that actually occur.
- A function assigns every declared input exactly one output.
- An injective function does not reuse outputs.
- A surjective function reaches the entire codomain.
- A bijection is both injective and surjective.
- Bijections establish equal cardinality.
- Composition connects mappings in sequence.
- A bijection has an inverse mapping.
The central distinction is: a relation records allowed connections, while a function requires every input to have exactly one output.
Where We Go Next
Relations and mappings describe connections among discrete objects. When many such connections are considered together, they form larger structural systems.
The next lesson, Graphs, Trees, Networks, and States, develops vertices, edges, branches, pathways, networks, and state structures.