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

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"!!

• @AlfonsoFernandez, $A \sim B$ if $\exists f:A \to B |f$ is bijective function – mle May 11 '13 at 13:28

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}$$

• in what sense $g=f\upharpoonright(A\setminus\{a\})$ is bijection from $A\setminus\{a\}$ to $B\setminus\{b\}$ ?? – mle May 12 '13 at 19:19
• @Garnak: No special sense: it simply is one. It’s an injective function whose domain is $A\setminus\{a\}$ and whose range is $B\setminus\{b\}$. In case it’s the notation that’s confusing you, $f\upharpoonright X$ is the restriction of the function $f$ to the set $X$, where $X$ is some subset of the domain of $f$. – Brian M. Scott May 12 '13 at 19:20
• ok...... thanks!! – mle May 12 '13 at 19:23
• @Garnak: You’re welcome! – Brian M. Scott May 12 '13 at 19:23

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\}$?

• I do not understand.. – mle May 11 '13 at 13:41
• He is mathematically describing the intuition you should have. The bijection f matches up elements of A and B. But if you take a out of A then you have some element of B unmatched, and if you take b out of B there is an element of A unmatched. Gee, how are we going to fix that? – Peter Webb May 11 '13 at 13:51
• @Garnak: Which part(s)? – Cameron Buie May 11 '13 at 14:05

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}$$

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.