Chapter 1: Relations and Functions (Relations and Functions)

$R=\{(x,y):y=3x\}=\{(1,3),(2,6),(3,9),(4,12)\}$.

• Not reflexive: $(1,1)\notin R$.
• Not symmetric: $(1,3)\in R$ but $(3,1)\notin R$.
• Not transitive: $(1,3)\in R$ and $(3,9)\in R$, but $(1,9)\notin R$.

Neither reflexive, nor symmetric, nor transitive.

$R=\{(1,6),(2,7),(3,8)\}$.

• Not reflexive: $(1,1)\notin R$.
• Not symmetric: $(1,6)\in R$ but $(6,1)\notin R$.
• Transitive: for $(x,y),(y,z)$ both in R we would need $y<4$, but every second entry is at least 6. There is no such pair, so the condition is never violated: R is transitive.

Not reflexive, not symmetric, but transitive.

• Reflexive: every $x$ divides itself, so $(x,x)\in R$.
• Not symmetric: $(1,2)\in R$ (2 is divisible by 1) but $(2,1)\notin R$.
• Transitive: if $x\mid y$ and $y\mid z$, then $y=kx$, $z=my=mkx$, so $x\mid z$.

Reflexive and transitive, but not symmetric.

For integers $x,y,z$:

• Reflexive: $x-x=0$ is an integer.
• Symmetric: if $x-y$ is an integer, so is $y-x=-(x-y)$.
• Transitive: if $x-y$ and $y-z$ are integers, then $x-z=(x-y)+(y-z)$ is an integer.

Reflexive, symmetric and transitive (an equivalence relation).

(a) x works at the same place as x (reflexive); if x and y work at the same place, so do y and x (symmetric); if x, y and y, z work at the same place, so do x and z (transitive). Reflexive, symmetric and transitive.

(b) By the same reasoning with "live in the same locality": reflexive, symmetric and transitive.

(c) x is not 7 cm taller than himself (not reflexive). If x is 7 cm taller than y, y is not 7 cm taller than x (not symmetric). If x is 7 cm taller than y and y is 7 cm taller than z, then x is 14 cm taller than z, so $(x,z)\notin R$ (not transitive). Neither reflexive, nor symmetric, nor transitive.

(d) x is not the wife of x (not reflexive). If x is the wife of y, y is the husband of x, not the wife (not symmetric). For $(x,y),(y,z)\in R$, y would have to be both a husband (of x) and a wife (of z), which is impossible; so the condition is never violated: transitive. Not reflexive, not symmetric, but transitive.

(e) x is not the father of x (not reflexive). If x is the father of y, y is not the father of x (not symmetric). If x is the father of y and y the father of z, x is the grandfather of z, not the father (not transitive). Neither reflexive, nor symmetric, nor transitive.

(a), (b): equivalence relations. (c), (e): none of the three. (d): only transitive.

• Not reflexive: take $a=\frac{1}{2}$: $\frac{1}{2}\le {\left(\frac{1}{2}\right)}^2=\frac{1}{4}$ is false, so $\left(\frac{1}{2},\frac{1}{2}\right)\notin R$.
• Not symmetric: $(1,4)\in R$ since $1\le 16$, but $(4,1)\notin R$ since $4\le 1$ is false.
• Not transitive: $(3,2)\in R$ since $3\le 4$, and $(2,1.5)\in R$ since $2\le 2.25$, but $(3,1.5)\notin R$ since $3\le 2.25$ is false.

Counter-examples $(\frac{1}{2},\frac{1}{2})$, $(1,4)$ and $(3,2),(2,1.5)$ show it is none of the three.

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

• Not reflexive: $(1,1)\notin R$.
• Not symmetric: $(1,2)\in R$ but $(2,1)\notin R$.
• Not transitive: $(1,2),(2,3)\in R$ but $(1,3)\notin R$.

Neither reflexive, nor symmetric, nor transitive.

• Reflexive: $a\le a$ for every real $a$.
• Transitive: $a\le b$ and $b\le c$ give $a\le c$.
• Not symmetric: $(1,2)\in R$ since $1\le 2$, but $(2,1)\notin R$.

Reflexive and transitive, not symmetric (e.g. (1, 2) ∈ R, (2, 1) ∉ R).

• Not reflexive: $\frac{1}{2}\le \frac{1}{8}$ is false, so $\left(\frac{1}{2},\frac{1}{2}\right)\notin R$.
• Not symmetric: $(1,2)\in R$ ($1\le 8$), but $(2,1)\notin R$ ($2\le 1$ is false).
• Not transitive: $\left(3,\frac{3}{2}\right)\in R$ since $3\le \frac{27}{8}$; $\left(\frac{3}{2},\frac{4}{3}\right)\in R$ since $\frac{3}{2}\le \frac{64}{27}$; but $\left(3,\frac{4}{3}\right)\notin R$ since $3\le \frac{64}{27}\approx 2.37$ is false.

Neither reflexive, nor symmetric, nor transitive.

• Symmetric: $(1,2)\in R$ and $(2,1)\in R$.
• Not reflexive: $(1,1)\notin R$.
• Not transitive: $(1,2),(2,1)\in R$ but $(1,1)\notin R$.

Symmetric only.

• Reflexive: a book has the same number of pages as itself.
• Symmetric: if x and y have the same number of pages, so do y and x.
• Transitive: if x, y have the same number of pages and y, z do too, then x and z have the same number.

R is reflexive, symmetric and transitive, hence an equivalence relation.

• Reflexive: $|a-a|=0$ is even.
• Symmetric: $|b-a|=|a-b|$.
• Transitive: if $a-b$ and $b-c$ are even, then $a-c=(a-b)+(b-c)$ is even.

So R is an equivalence relation.

• In {1, 3, 5}, all elements are odd; the difference of two odd numbers is even, so they are all related.
• In {2, 4}, both are even; their difference is even, so they are related.
• An odd number minus an even number is odd, so no element of {1, 3, 5} is related to any element of {2, 4}.

R is an equivalence relation; {1, 3, 5} and {2, 4} are its two equivalence classes.

$A=\{0,1,2,\dots ,12\}$.

(i) Reflexive: $|a-a|=0=4\times 0$. Symmetric: $|b-a|=|a-b|$. Transitive: if $a-b=4k$ and $b-c=4m$, then $a-c=4(k+m)$. Equivalence relation.

Elements related to 1: $|1-b|$ is a multiple of 4, so $b=1,5,9$: {1, 5, 9}.

(ii) Reflexive: $a=a$. Symmetric: $a=b\Rightarrow b=a$. Transitive: $a=b$, $b=c\Rightarrow a=c$. Equivalence relation.

Elements related to 1: {1}.

Both are equivalence relations; elements related to 1: (i) {1, 5, 9}, (ii) {1}.

Take $A=\{1,2,3\}$ (for (ii) and (iv) use real numbers).

• (i) $R=\{(1,2),(2,1)\}$: symmetric; not reflexive; not transitive since $(1,1)\notin R$.
• (ii) $R=\{(a,b):a<b\}$ on R: transitive; not reflexive ($a<a$ is false); not symmetric.
• (iii) $R=\{(1,1),(2,2),(3,3),(1,2),(2,1),(2,3),(3,2)\}$: reflexive and symmetric; not transitive since $(1,2),(2,3)\in R$ but $(1,3)\notin R$.
• (iv) $R=\{(a,b):a\le b\}$ on R: reflexive and transitive; not symmetric.
• (v) $R=\{(1,1),(1,2),(2,1),(2,2)\}$ on {1, 2, 3}: symmetric and transitive; not reflexive since $(3,3)\notin R$.

See the five examples above.

Let O be the origin.

• Reflexive: $OP=OP$.
• Symmetric: $OP=OQ\Rightarrow OQ=OP$.
• Transitive: $OP=OQ$ and $OQ=OS\Rightarrow OP=OS$.

So R is an equivalence relation.

Points related to P are all Q with $OQ=OP=r$ (a fixed positive number). These are exactly the points at distance $r$ from O, i.e. the circle with centre O passing through P.

R is an equivalence relation; the points related to P form the circle with centre at the origin through P.

• Reflexive: every triangle is similar to itself.
• Symmetric: if $T_1\sim T_2$, then $T_2\sim T_1$.
• Transitive: if $T_1\sim T_2$ and $T_2\sim T_3$, then $T_1\sim T_3$.

So R is an equivalence relation.

For T₁ and T₃: $\frac{3}{6}=\frac{4}{8}=\frac{5}{10}=\frac{1}{2}$, so the sides are proportional and $T_1\sim T_3$. T₂ has $\frac{5}{3}\ne \frac{12}{4}$, so it is not similar to either.

T₁ and T₃ are related.

• Reflexive: a polygon has the same number of sides as itself.
• Symmetric: if P₁ and P₂ have the same number of sides, so do P₂ and P₁.
• Transitive: if P₁, P₂ and P₂, P₃ have the same number of sides, so do P₁ and P₃.

So R is an equivalence relation. The polygons related to the triangle T are those with 3 sides: the set of all triangles.

R is an equivalence relation; T is related to all triangles.

• Reflexive: every line is parallel to itself (taken as a convention).
• Symmetric: if $L_1\parallel L_2$, then $L_2\parallel L_1$.
• Transitive: if $L_1\parallel L_2$ and $L_2\parallel L_3$, then $L_1\parallel L_3$.

So R is an equivalence relation.

Lines parallel to $y=2x+4$ have the same slope 2: the set of all lines $y=2x+c$, where $c\in$ R.

R is an equivalence relation; related lines: y = 2x + c, c ∈ R.

• Reflexive: (1, 1), (2, 2), (3, 3), (4, 4) are all in R.
• Not symmetric: $(1,2)\in R$ but $(2,1)\notin R$.
• Transitive: the only chains are $(1,3),(3,2)\to (1,2)\in R$; $(1,2),(2,2)\to (1,2)\in R$; $(1,3),(3,3)\to (1,3)\in R$; $(3,2),(2,2)\to (3,2)\in R$ and those with $(a,a)$. All hold.

(B)

• (2, 4): $b=4$ is not greater than 6.
• (3, 8): $3\ne 8-2$.
• (6, 8): $6=8-2$ and $8>6$. ✔
• (8, 7): $8\ne 7-2$.

(C)

One-one: $f(x_1)=f(x_2)\Rightarrow \frac{1}{x_1}=\frac{1}{x_2}\Rightarrow x_1=x_2$.

Onto: for any $y\in$ R∗, take $x=\frac{1}{y}\in$ R∗; then $f(x)=y$.

So $f$ is one-one and onto.

With domain N: $g:N\to R_{\ast }$, $g(x)=\frac{1}{x}$ is still one-one (same argument), but not onto: e.g. $y=2$ would need $x=\frac{1}{2}\notin$ N. So the result is not fully true.

One-one and onto on R∗; with domain N it is one-one but not onto.

• (i) One-one: for natural numbers $x_1^2=x_2^2\Rightarrow x_1=x_2$. Not onto: 2 is not a square of any natural number. Injective, not surjective.
• (ii) Not one-one: $f(-1)=f(1)=1$. Not onto: $-1$ (or 2) has no pre-image. Neither.
• (iii) Not one-one: $f(-1)=f(1)$. Not onto: $-1$ has no real pre-image. Neither.
• (iv) One-one: $x_1^3=x_2^3\Rightarrow x_1=x_2$. Not onto: 2 is not a cube of a natural number. Injective, not surjective.
• (v) One-one: $x_1^3=x_2^3\Rightarrow x_1=x_2$. Not onto: 2 is not a cube of an integer. Injective, not surjective.

(i), (iv), (v): one-one but not onto. (ii), (iii): neither one-one nor onto.

• Not one-one: $f(1.2)=1$ and $f(1.9)=1$, but $1.2\ne 1.9$.
• Not onto: $f(x)$ is always an integer, so a non-integer like $0.7$ in the co-domain R has no pre-image.

[1.2] = [1.9] = 1 (not one-one) and the range is Z ≠ R (not onto).

• Not one-one: $f(-1)=f(1)=1$.
• Not onto: $|x|\ge 0$, so a negative number such as $-1$ has no pre-image.

f(−1) = f(1) and negative numbers have no pre-image.

• Not one-one: $f(1)=f(2)=1$.
• Not onto: the range is $\{-1,0,1\}$, so e.g. $2$ has no pre-image.

f(1) = f(2) and the range is only {−1, 0, 1}.

$f(1)=4$, $f(2)=5$, $f(3)=6$: different elements of A have different images. So $f$ is one-one. (It is not onto, as 7 has no pre-image.)

The images 4, 5, 6 are distinct, so f is one-one.

(i) One-one: $3-4x_1=3-4x_2\Rightarrow x_1=x_2$. Onto: for any $y$, take $x=\frac{3-y}{4}$; then $f(x)=3-(3-y)=y$. Bijective.

(ii) Not one-one: $f(1)=f(-1)=2$. Not onto: $1+x^2\ge 1$, so e.g. $0$ has no pre-image. Neither one-one nor onto.

(i) Bijective. (ii) Neither one-one nor onto.

One-one: $f(a_1,b_1)=f(a_2,b_2)\Rightarrow (b_1,a_1)=(b_2,a_2)\Rightarrow b_1=b_2,a_1=a_2\Rightarrow (a_1,b_1)=(a_2,b_2)$.

Onto: for any $(b,a)\in B\times A$, the element $(a,b)\in A\times B$ satisfies $f(a,b)=(b,a)$.

So $f$ is bijective.

f swaps the coordinates; it is one-one and every (b, a) has the pre-image (a, b), so it is bijective.

• Not one-one: $f(1)=\frac{1+1}{2}=1$ and $f(2)=\frac{2}{2}=1$.
• Onto: for any $n\in N$, $f(2n)=\frac{2n}{2}=n$.

So $f$ is onto but not one-one, hence not bijective.

Not bijective: onto, but f(1) = f(2) = 1.

One-one:

$$\frac{x_1-2}{x_1-3}=\frac{x_2-2}{x_2-3}\Rightarrow (x_1-2)(x_2-3)=(x_2-2)(x_1-3)$$

$$\Rightarrow x_1{x}_2-3x_1-2x_2+6=x_1{x}_2-3x_2-2x_1+6\Rightarrow -x_1=-x_2\Rightarrow x_1=x_2$$

Onto: let $y\in B$ ($y\ne 1$). Solve $y=\frac{x-2}{x-3}$: $xy-3y=x-2$, so $x=\frac{3y-2}{y-1}$, which is a real number since $y\ne 1$. Also $x\ne 3$ (if $\frac{3y-2}{y-1}=3$ then $-2=-3$, impossible), so $x\in A$, and $f(x)=y$.

So $f$ is one-one and onto (bijective).

Yes, f is one-one and onto; the pre-image of y is $x=\frac{3y-2}{y-1}$.

$f(1)=f(-1)=1$, so not one-one; $x^4\ge 0$, so negative numbers have no pre-image: not onto.

(D)

One-one: $3x_1=3x_2\Rightarrow x_1=x_2$. Onto: for any $y$, $f\left(\frac{y}{3}\right)=y$.

(A)

One-one. If $x\ge 0$, $f(x)=\frac{x}{1+x}\ge 0$; if $x<0$, $f(x)=\frac{x}{1-x}<0$. So equal values can only come from $x_1,x_2$ of the same sign.

• Both $\ge 0$: $\frac{x_1}{1+x_1}=\frac{x_2}{1+x_2}\Rightarrow x_1+x_1{x}_2=x_2+x_1{x}_2\Rightarrow x_1=x_2$.
• Both $<0$: $\frac{x_1}{1-x_1}=\frac{x_2}{1-x_2}\Rightarrow x_1-x_1{x}_2=x_2-x_1{x}_2\Rightarrow x_1=x_2$.

Onto. Let $-1<y<1$.

• If $0\le y<1$: take $x=\frac{y}{1-y}\ge 0$. Then $f(x)=\frac{y/(1-y)}{1+y/(1-y)}=\frac{y/(1-y)}{1/(1-y)}=y$.
• If $-1<y<0$: take $x=\frac{y}{1+y}<0$. Then $f(x)=\frac{x}{1-x}=\frac{y/(1+y)}{1/(1+y)}=y$.

So $f$ is one-one and onto.

Same-sign values give $x_1=x_2$ (one-one); pre-images $x=\frac{y}{1-y}$ for $y\ge 0$ and $x=\frac{y}{1+y}$ for $y<0$ (onto).

$$x_1^3=x_2^3\Rightarrow (x_1-x_2)(x_1^2+x_1{x}_2+x_2^2)=0$$

The second factor $x_1^2+x_1{x}_2+x_2^2={\left(x_1+\frac{x_2}{2}\right)}^2+\frac{3x_2^2}{4}$ is positive unless $x_1=x_2=0$. So $x_1-x_2=0$ in every case, i.e. $x_1=x_2$: $f$ is injective.

$x_1^3=x_2^3$ forces $x_1=x_2$, so f is one-one.

• Reflexive: $A\subset A$ for every subset A.
• Transitive: $A\subset B$ and $B\subset C\Rightarrow A\subset C$.
• Not symmetric: $\varphi \subset X$, but $X\not\subset \varphi$ (X is non-empty).

So R is not an equivalence relation.

No: it is reflexive and transitive but not symmetric (φ ⊂ X but X ⊄ φ).

For a finite set mapped to itself, onto is the same as one-one, so the onto functions are exactly the arrangements (permutations) of the n elements: $1$ can go to any of $n$ elements, $2$ to any of the remaining $n-1$, and so on.

Number $=n(n-1)(n-2)\cdots 1=n!$.

n!

$f(a)=g(a)$ for every $a\in A$, and both have the same domain and co-domain, so f and g are equal.

Yes, f(a) = g(a) for all a ∈ A, so f = g.

Reflexive and symmetric with (1, 2), (1, 3) forces $R=\{(1,1),(2,2),(3,3),(1,2),(2,1),(1,3),(3,1)\}$.

This is not transitive: $(2,1),(1,3)\in R$ but $(2,3)\notin R$. The only possible addition is $(2,3),(3,2)$ together (for symmetry), which makes R the universal relation, which is transitive. So there is exactly one such relation.

(A) 1

• $\{(1,1),(2,2),(3,3),(1,2),(2,1)\}$
• the universal relation $A\times A$

Adding any other pair, e.g. (2, 3), forces (by symmetry and transitivity) all pairs. So there are two.

(B) 2