# Just a few problems I've been working on for too long... (Bijections, sup/inf)

• Sep 13th 2009, 01:24 PM
thaopanda
Just a few problems I've been working on for too long... (Bijections, sup/inf)
Even after reviewing my notes over and over again and trying to do these problems over and over again, I still can't figure out how to finish them or start them....

1. Let S, T be sets such that (S \ T) ~ (T \ S). Prove that S ~ T

2. Let S, S1, T, T1 be sets such that S ~ S1 and T ~ T1. Show that S x T ~ S1 X T1

3. Let A, B be subsets of R and nonempty
A is bounded from above and B is bounded from below
Define A - B as the set { z = x - y : x e A, y e B}
Show that sup (A - B) = sup A - inf B

4. Show that [0,1] ~ [0,2)

Hopefully the problems above are understandable...

- Nicole
• Sep 13th 2009, 05:36 PM
Taluivren
Hi
1) $S = (S\smallsetminus T) \cup (S\cap T)\$, $T = (T\smallsetminus S) \cup (S\cap T)\$. Note that both unions are in fact disjoint unions.
Because $|S\smallsetminus T| = |T\smallsetminus S|$, there's a bijection $g: (S\smallsetminus T) \rightarrow (T\smallsetminus S)$. Now we're ready to construct a bijection $f:S\rightarrow T$ like this:

$f(x) = \begin{cases} g(x) & \mbox{if } x\in (S\smallsetminus T) \\ x & \mbox{if } x\in S\cap T \end{cases}$
Verify it is really a bijection!

2) $|S|=|S_1|$ means there's a bijection $g:S\rightarrow S_1$
$|T|=|T_1|$ means there's a bijection $h:T\rightarrow T_1$
Define $f:S\times T \rightarrow S_1\times T_1$ as follows: $f\left((a,b)\right) = (g(a),h(b))$
Verify it is a bijection.

3) Conditions say that $\sup A$ and $\inf B$ exist.
Is $\sup A - \inf B$ an upper bound of $A-B$ ? Yes: let $z \in A-B$, so $z = a-b$ for some $a\in A$, $b\in B$.
But $a<\sup A$ and $b>\inf B$, so $z=a-b <\sup A - \inf B$.

Is $\sup A - \inf B$ the least upper bound of $A-B$ ? Suppose it is not, then there exist $\varepsilon >0$ such that $\sup A - \inf B -\varepsilon$ is an upper bound of $A-B$.
Because $\sup A$ is a supremum, there must exist some $a\in A$ such that $a>\sup A-\varepsilon/2$.
Because $\inf B$ is an infimum, there must exist some $b\in B$ such that $b<\inf B+\varepsilon/2$.
We get $z=a-b>\sup A-\varepsilon/2 - (\inf B+\varepsilon/2) = \sup A - \inf B -\varepsilon$ which contradicts the assumption that $\sup A - \inf B -\varepsilon$ is an upper bound of $A-B$.
We conclude that $\sup A - \inf B = \sup(A-B)$.

4) Because x->2x is a bijection from [0,1) to [0,2), it will suffice to construct a bijection between [0,1] and [0,1) and composition of the two bijections will be a bijection from [0,1] to [0,2).

If you know Cantor-Bernstein Theorem, it is easy, because there obviously exist an injective map from [0,1) to [0,1] (the identity map) and an injective map from [0,1] to [0,1) (x -> x/2).

If you don't know the theorem, consider set $A=\{\frac{1}{1},\frac{1}{2},\frac{1}{3},\frac{1}{4 },\frac{1}{5},\ldots\} \subseteq [0,1]$ and set $B=\{\frac{1}{2},\frac{1}{3},\frac{1}{4},\frac{1}{5 },\ldots\} \subseteq [0,1)$. You can construct bijection $g:A\rightarrow B$ by setting $g\left(\frac{1}{i}\right)=\frac{1}{i+1}$ (verify it is a bijection).

Next, we see that $[0,1]\smallsetminus A = [0,1)\smallsetminus B$, so the identity on $[0,1]\smallsetminus A$ is a bijection from $[0,1]\smallsetminus A$ to $[0,1)\smallsetminus B$.

Now we're ready to construct a bijection $f:[0,1]\rightarrow [0,1)$ as follows:

$f(x) = \begin{cases} g(x) & \mbox{if } x \in A \\ x & \mbox{if } x\in [0,1]\smallsetminus A \end{cases}$