Why Every Function Is a Relation but Not Every Relation Is a Function

Is a sibling of, is less than, is the capital of — everyday language is full of links between objects. Mathematics captures these links as relations built from ordered pairs, and one special kind of relation becomes the function studied in the next chapter.

This lesson covers Cartesian products, relations and their representations, domain, co-domain and range, and how a relation differs from a function.

**The Cartesian product $A\times B$ is the set of all ordered pairs $(a,b)$ with $a\in A$ and $b\in B$, and if A has p elements and B has q elements, then $A\times B$ has $pq$ elements.

Ordered pairs.** $(a,b)=(c,d)$ only when $a=c$ and $b=d$, so $(2,3)\ne (3,2)$.

Worked example. Let $A=\{1,2,3\}$ and $B=\{x,y\}$.

$$A\times B=\{(1,x),(1,y),(2,x),(2,y),(3,x),(3,y)\}$$

so $n(A\times B)=3\times 2=6$. The product $B\times A$ also has 6 elements, but its pairs are different.

Useful facts:

- $A\times B\ne B\times A$ unless $A=B$ or one of the sets is empty
- If A or B is empty, then $A\times B=\varphi$

An everyday example. A dosa stall offering 4 kinds of dosa with 3 chutneys has $4\times 3=12$ dosa-chutney combinations — a Cartesian product.

The substance. Order matters in a pair but not in a set — $\{2,3\}=\{3,2\}$, yet $(2,3)\ne (3,2)$.

**A relation R from A to B is any subset of $A\times B$; it can be shown as an arrow diagram joining related elements, in roster form as a list of ordered pairs, or in set-builder form as the rule the pairs satisfy.

Worked example.** Let $A=\{1,2,3,4\}$, $B=\{1,4,9,16,25\}$ and let R relate a to b when $b=a^2$.

- Roster form — $R=\{(1,1),(2,4),(3,9),(4,16)\}$
- Arrow diagram — arrows from 1 to 1, 2 to 4, 3 to 9 and 4 to 16; the element 25 receives no arrow
- Set-builder form — $R=\{(a,b):a\in A,b\in B,b=a^2\}$

Counting relations. Since $A\times B$ has $pq$ elements, the number of relations from A to B is $2^{pq}$. With $n(A)=2$ and $n(B)=3$, there are $2^6=64$ relations, including the empty relation.

An everyday example. Linking each student to the school clubs they have joined — one student to several clubs, some clubs to nobody — is a relation.

The substance. The empty set is also a relation — it is a subset of $A\times B$, simply one with no pairs.

The domain of a relation R from A to B is the set of first elements of its ordered pairs, the co-domain is the whole set B, and the range is the set of second elements that actually occur, which is always a subset of the co-domain.

For the squares relation above, $R=\{(1,1),(2,4),(3,9),(4,16)\}$:

- Domain $=\{1,2,3,4\}$
- Co-domain $=B=\{1,4,9,16,25\}$
- Range $=\{1,4,9,16\}$

Worked example. Let $A=\{1,2,3,4,5,6\}$ and define R on A by $b=a+2$. Then

$$R=\{(1,3),(2,4),(3,5),(4,6)\}$$

so the domain is $\{1,2,3,4\}$, the range is $\{3,4,5,6\}$ and the co-domain is A.

An everyday example. Relating each post office to its six-digit PIN code — the codes actually used form the range, while all possible six-digit codes form the co-domain.

The substance. Range and co-domain are not the same — 25 is in the co-domain of the squares relation but appears in no pair, so it is not in the range.

A function from A to B is a relation in which every element of A has exactly one image in B — so every function is a relation, but a relation fails to be a function if some element of A has no image or more than one image.

**Conditions for a function $f:A\to B$:

- Every element of A appears as a first element
- No element of A is the first element of two different pairs
- Two elements of A may share the same image — that is allowed

Worked example.** Let $A=\{1,2,3\}$ and $B=\{4,5,6\}$.

- $R_1=\{(1,4),(2,5),(3,5)\}$ — a function; 2 and 3 share an image, which is fine
- $R_2=\{(1,4),(1,5),(2,6),(3,6)\}$ — not a function; 1 has two images
- $R_3=\{(1,4),(2,5)\}$ — not a function on A; 3 has no image

Counting. With $n(A)=3$ and $n(B)=3$, there are $3^3=27$ functions from A to B, but $2^9=512$ relations.

An everyday example. Each student in a class has exactly one roll number, so 'student to roll number' is a function, while 'student to subjects studied' is only a relation, since one student takes several subjects.

The substance. The vertical line test captures the same idea on a graph — a vertical line meeting a curve twice means one input has two outputs.