Proof $(A-\{a\}) \sim (B - \{b\}) $

Question

I must prove the following:

"let $A$ and $B$ two set, with $A \neq \emptyset$ and $B \neq \emptyset$ and $A \sim B$, and $a \in A$ and $b \in B$, then $(A-\{a\}) \sim (B - \{b\})$

The symbol $\sim$ is used for "equipotency"!!

Thanks in advance!

Answer 1

Let $f:A\to B$ be a bijection. Intuitively you can think of $f$ as a bunch of strings tying each element of $A$ to an element of $B$ in such a way that each element of $B$ is tied to some member of $A$. If one of those strings ties $a$ to $b$ — i.e., if $f(a)=b$ — you can throw away $a$, $b$, and the string tying them together, and what’s left is a bijection from $A\setminus\{a\}$ to $B\setminus\{b\}$. More formally, $g=f\upharpoonright(A\setminus\{a\})$ is bijection from $A\setminus\{a\}$ to $B\setminus\{b\}$. Here’s a rough sketch of this nice situation.

$$\begin{array}{} \begin{array}{ccc} A&\overset{f}\longrightarrow&B\\ \hline \bullet&\longrightarrow&\bullet\\ \bullet&\longrightarrow&\bullet\\ \bullet&\longrightarrow&\bullet\\ \bullet&\longrightarrow&\bullet\\ a&\longrightarrow&b\\ \bullet&\longrightarrow&\bullet\\ \bullet&\longrightarrow&\bullet\\ \bullet&\longrightarrow&\bullet \end{array}&&& \begin{array}{ccc} A\setminus\{a\}&\overset{g}\longrightarrow&B\setminus\{b\}\\ \hline \bullet&\longrightarrow&\bullet\\ \bullet&\longrightarrow&\bullet\\ \bullet&\longrightarrow&\bullet\\ \bullet&\longrightarrow&\bullet\\ \color{white}\bullet&\color{white}\longrightarrow&\color{white}\bullet\\ \bullet&\longrightarrow&\bullet\\ \bullet&\longrightarrow&\bullet\\ \bullet&\longrightarrow&\bullet\\ \end{array} \end{array}$$

But we can’t expect to be so lucky: most likely $a$ is tied to something other than $b$, and therefore $b$ is tied to something other than $a$. Suppose that $a$ is tied to $b'$, and $a'$ is tied to $b$; more formally, $f(a)=b'$, and $f(a')=b$. If I throw away $a$, that breaks the string tying $a$ to $b'$ and leaves $b'$ not attached to anything in $A$. And if I throw away $b$, that breaks the string tying $a'$ to $b$ and leaves $a'$ not attached to anything in $B$. All of the other strings remain intact. I now have one loose end coming from $a'\in A$ and another loose end attached to $b'\in B$. I can get rid of both loose ends by tying them together. In other words, I’ll define a function $g:A\setminus\{a\}\to B\setminus\{b\}$ that ties $a'$ to $b'$ and retains all of the unbroken threads from $f$:

$$g(x)=\begin{cases} f(x),&\text{if }x\in A\setminus\{a,a'\}\\ b',&\text{if }x=a'\;. \end{cases}$$

And here’s a sketch of what’s going on intuitively.

$$\begin{array}{} \begin{array}{ccc} A&\overset{f}\longrightarrow&B\\ \hline \bullet&\longrightarrow&\bullet\\ \bullet&\longrightarrow&\bullet\\ a&\longrightarrow&b'\\ \bullet&\longrightarrow&\bullet\\ \bullet&\longrightarrow&\bullet\\ a'&\longrightarrow&b\\ \bullet&\longrightarrow&\bullet\\ \bullet&\longrightarrow&\bullet\\ \bullet&\longrightarrow&\bullet \end{array}&&& \begin{array}{ccc} A\setminus\{a\}&\longrightarrow&B\setminus\{b\}\\ \hline \bullet&\longrightarrow&\bullet\\ \bullet&\longrightarrow&\bullet\\ &\color{red}\longrightarrow&\color{red}{b'}\\ \bullet&\longrightarrow&\bullet\\ \bullet&\longrightarrow&\bullet\\ \color{red}{a'}&\color{red}\longrightarrow&\\ \bullet&\longrightarrow&\bullet\\ \bullet&\longrightarrow&\bullet\\ \bullet&\longrightarrow&\bullet\\ \end{array}&&& \begin{array}{ccc} A\setminus\{a\}&\overset{g}\longrightarrow&B\setminus\{b\}\\ \hline \bullet&\longrightarrow&\bullet\\ \bullet&\longrightarrow&\bullet\\ \color{red}{a'}&\color{red}\longrightarrow&\color{red}{b'}\\ \bullet&\longrightarrow&\bullet\\ \bullet&\longrightarrow&\bullet\\ \color{white}\bullet&\color{white}\longrightarrow&\color{white}\bullet\\ \bullet&\longrightarrow&\bullet\\ \bullet&\longrightarrow&\bullet\\ \bullet&\longrightarrow&\bullet\\ \end{array} \end{array}$$

Answer 2

Let $f:A\to B$ a bijection. If $f(a)=b$, we may of course just restrict $f$ to $A\smallsetminus\{a\}$. Otherwise, there is some unique $c\in A\smallsetminus\{a\}$ and some unique $d\in B\smallsetminus\{b\}$ such that $f(a)=d$ and $f(c)=b.$ (Why?) How can we use these facts, and the function $f,$ to construct the bijection we're looking for?

---

In general, we don't need the casewise approach that I was hinting at, above. If $f:A\to B$ is a bijection and $a\in A,b\in B$, then we know there is a unique $c\in A$ and a unique $d\in B$ such that $f(c)=b$ and $f(a)=d.$ (Why?) You should be able to show that $c=a$ if and only if $b=d.$

Now, given such an $f,$ let's construct a function $g:A\to A$ defined by $$g(x)=\begin{cases}c & \text{if }x=a,\\a & \text{if }x=c,\\x & \text{if }x\in A\smallsetminus\{a,c\}.\end{cases}$$ Now, what can you say about $f\circ g:A\to B,$ given what you know about $f$ and how we defined $g$? What about the restriction of $f\circ g$ to $A\smallsetminus\{a\}$?

Answer 3

Here is an example for finite $A,B$. The general case is similar.
Assume that $A=\{1,2,3,4,5,6,7\},B=\{p,q,r,s,t,u,v\}, \ a=2, \ b=s$ and the function $f$ which gives $A\sim B$ is given by $$ \begin{pmatrix} 1&\rightarrow&q\\ \color{red}{2}&\rightarrow&\color{green}{r}\\ 3&\rightarrow&p\\ 4&\rightarrow&t\\ \color{green}{5}&\rightarrow&\color{red}{s}\\ 6&\rightarrow&v\\ 7&\rightarrow&u\\ \end{pmatrix} $$ Then the function $g$ which gives $(A-\{a\})\sim (B-\{b\})$ is given by $$ \begin{pmatrix} 1&\rightarrow&q\\ 3&\rightarrow&p\\ 4&\rightarrow&t\\ \color{green}{5}&\rightarrow&\color{green}{r}\\ 6&\rightarrow&v\\ 7&\rightarrow&u\\ \end{pmatrix} $$

Answer 4

Let $f$ be a bijection between $A$ and $B$. If $f(a)=b$ then this would be wonderful, since the restriction of $f$ to $A\setminus\{a\}$ would be a bijection onto $B\setminus\{b\}$.

But if $f$ is not such a bijection, we can make it into such:

Let $c\in A$ such that $f(c)=b$ and $d\in B$ such that $f(a)=d$. What could be a good solution for our problem? If there was a slightly modified version of $f$, say $\hat f$, such that $\hat f(c)=d$ and $\hat f(a)=b$, and otherwise $\hat f(x)=f(x)$, then we would be done.

But we actually just described the solution. Let $\hat f$ be the following: $$\hat f=\big(f\setminus\{\langle c,d\rangle,\langle a,d\rangle\}\big)\cup\{\langle a,b\rangle,\langle c,d\rangle\}$$

I leave it to you to verify that $\hat f$ is a bijection from $A$ onto $B$ and $\hat f(a)=b$. Now return to the first sentence of this answer, and finish.