Exercise 1.2 · Q8: $(a,b)\mapsto(b,a)$ is bijective

Basics you need

Solution

1. Check that $f$ maps $A\times B$ into $B\times A$

   Take any element of the domain; it has the form $(a, b)$ with $a\in A$ and $b\in B$⁠. Its image $f(a,b) = (b, a)$ has first entry $b\in B$ and second entry $a\in A$⁠, so $(b,a)\in B\times A$⁠. Each input pair gives exactly one output pair, so $f$ is a function from $A\times B$ to $B\times A$⁠.

   The domain and codomain are different sets, so it is worth confirming that the swapped pair lands in the right one. It does, precisely because the entries are swapped: what came from $B$ is now first, as $B\times A$ requires.
   $B\times A$ consists of pairs whose first entry is in $B$ and second entry is in $A$ (Basic 1). Basics: sets, ordered pairs and A × B

2. One-one: equal swapped pairs come from equal pairs

   Let $(a_1, b_1)$ and $(a_2, b_2)$ be any two elements of $A\times B$ with $f(a_1, b_1) = f(a_2, b_2)$⁠. Then

   $$\begin{aligned} &(b_1, a_1) = (b_2, a_2) \\ \Longrightarrow\ &b_1 = b_2 \ \text{ and } \ a_1 = a_2 &&\text{(compare entries)}\\ \Longrightarrow\ &(a_1, b_1) = (a_2, b_2) &&\text{(reassemble the pair)}. \end{aligned}$$

   So equal images force equal inputs: $f$ is one-one.

   The input of $f$ is a whole pair, so "$x_1 = x_2$" in the definition of one-one becomes "$(a_1,b_1) = (a_2,b_2)$". We use the equality rule for ordered pairs twice: first to break the equal outputs into equal entries, then to reassemble those entries into equal inputs. The entries are the same; only their positions differ.
   $(x,y) = (u,v)$ if and only if $x=u$ and $y=v$ (Basic 2). One-one: equal images imply equal inputs (Definition 5).

3. Onto: every pair in $B\times A$ is a swapped pair

   Take an arbitrary element of the codomain $B\times A$⁠. It has the form $(b, a)$ with $b\in B$ and $a\in A$⁠. Choose the input $(a, b)$⁠. Since $a\in A$ and $b\in B$⁠, this input lies in the domain $A\times B$⁠, and

   $$f(a, b) = (b, a). \ ✓$$

   So every element of $B\times A$ is the image of some element of $A\times B$⁠: $f$ is onto.

   To prove onto we start from an arbitrary element of the codomain and produce a preimage. The natural guess is to swap back. We then confirm two things: the guess is in the domain (its first entry $a$ is in $A$ and its second entry $b$ is in $B$⁠), and applying $f$ to it really gives the element we started with.
   Onto: for every $y$ in the codomain, find $x$ in the domain with $f(x)=y$⁠, and check that $x$ lies in the domain (Definition 6). Basics: one-one and onto

4. Conclude, and see it on a small example

   $f$ is one-one (Step 2) and onto (Step 3), so $f$ is bijective.

   For a concrete picture, take $A = \{1, 2\}$ and $B = \{p, q, r\}$⁠. Then $A\times B$ and $B\times A$ each have $2\times3 = 6$ elements, and $f$ pairs them off one to one:

   $(a,b)\in A\times B$	$(1,p)$	$(1,q)$	$(1,r)$	$(2,p)$	$(2,q)$	$(2,r)$
   $f(a,b)\in B\times A$	$(p,1)$	$(q,1)$	$(r,1)$	$(p,2)$	$(q,2)$	$(r,2)$

   The six outputs are all different (one-one), and they are all six elements of $B\times A$ (onto).

   The inverse is the swap in the other direction, $g : B\times A \to A\times B$⁠, $g(b, a) = (a, b)$⁠. Indeed $g(f(a,b)) = g(b,a) = (a,b)$ and $f(g(b,a)) = f(a,b) = (b,a)$⁠.

   The general proof in Steps 2 and 3 covers every possible $A$ and $B$⁠, including infinite ones; the table is only an illustration. The remark about $g$ gives a second way to see the result: a function that has a two-sided inverse is a bijection (Section 1.4). Swapping is undone by swapping back.
   Bijective = one-one and onto (Definition 7); a function is invertible exactly when it is bijective. Lesson: invertible functions

Every fact used, and where it comes from