2
$\begingroup$

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!

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

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

$\endgroup$
  • $\begingroup$ in what sense $g=f\upharpoonright(A\setminus\{a\})$ is bijection from $A\setminus\{a\}$ to $B\setminus\{b\}$ ?? $\endgroup$ – mle May 12 '13 at 19:19
  • 1
    $\begingroup$ @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$. $\endgroup$ – Brian M. Scott May 12 '13 at 19:20
  • $\begingroup$ ok...... thanks!! $\endgroup$ – mle May 12 '13 at 19:23
  • $\begingroup$ @Garnak: You’re welcome! $\endgroup$ – Brian M. Scott May 12 '13 at 19:23
10
$\begingroup$

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

$\endgroup$
  • $\begingroup$ I do not understand.. $\endgroup$ – mle May 11 '13 at 13:41
  • 1
    $\begingroup$ 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? $\endgroup$ – Peter Webb May 11 '13 at 13:51
  • 1
    $\begingroup$ @Garnak: Which part(s)? $\endgroup$ – Cameron Buie May 11 '13 at 14:05
2
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.