# 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) $\displaystyle S = (S\smallsetminus T) \cup (S\cap T)\$, $\displaystyle T = (T\smallsetminus S) \cup (S\cap T)\$. Note that both unions are in fact disjoint unions.
Because $\displaystyle |S\smallsetminus T| = |T\smallsetminus S|$, there's a bijection $\displaystyle g: (S\smallsetminus T) \rightarrow (T\smallsetminus S)$. Now we're ready to construct a bijection $\displaystyle f:S\rightarrow T$ like this:

$\displaystyle 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) $\displaystyle |S|=|S_1|$ means there's a bijection $\displaystyle g:S\rightarrow S_1$
$\displaystyle |T|=|T_1|$ means there's a bijection $\displaystyle h:T\rightarrow T_1$
Define $\displaystyle f:S\times T \rightarrow S_1\times T_1$ as follows: $\displaystyle f\left((a,b)\right) = (g(a),h(b))$
Verify it is a bijection.

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

Is $\displaystyle \sup A - \inf B$ the least upper bound of $\displaystyle A-B$ ? Suppose it is not, then there exist $\displaystyle \varepsilon >0$ such that $\displaystyle \sup A - \inf B -\varepsilon$ is an upper bound of $\displaystyle A-B$.
Because $\displaystyle \sup A$ is a supremum, there must exist some $\displaystyle a\in A$ such that $\displaystyle a>\sup A-\varepsilon/2$.
Because $\displaystyle \inf B$ is an infimum, there must exist some $\displaystyle b\in B$ such that $\displaystyle b<\inf B+\varepsilon/2$.
We get $\displaystyle z=a-b>\sup A-\varepsilon/2 - (\inf B+\varepsilon/2) = \sup A - \inf B -\varepsilon$ which contradicts the assumption that $\displaystyle \sup A - \inf B -\varepsilon$ is an upper bound of $\displaystyle A-B$.
We conclude that $\displaystyle \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 $\displaystyle A=\{\frac{1}{1},\frac{1}{2},\frac{1}{3},\frac{1}{4 },\frac{1}{5},\ldots\} \subseteq [0,1]$ and set $\displaystyle B=\{\frac{1}{2},\frac{1}{3},\frac{1}{4},\frac{1}{5 },\ldots\} \subseteq [0,1)$. You can construct bijection $\displaystyle g:A\rightarrow B$ by setting $\displaystyle g\left(\frac{1}{i}\right)=\frac{1}{i+1}$ (verify it is a bijection).

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

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

$\displaystyle f(x) = \begin{cases} g(x) & \mbox{if } x \in A \\ x & \mbox{if } x\in [0,1]\smallsetminus A \end{cases}$
The text passage contains a series of mathematical problems and their solutions. The problems are related to set theory and real analysis, and the solutions are detailed step-by-step proofs.
multiple_questions_with_answers
Given a text passage, determine:
    1. If it contains a mathematical question (including word problems or calculations)
    2. If an answer to that mathematical question is provided in the text

First, describe the content structure you found in 1-2 sentences.

Then provide your analysis in the following format:
TYPE: <one of the following values>
- NO_QUESTION
- SINGLE_QUESTION
- SINGLE_QUESTION_WITH_ANSWER
- MULTIPLE_QUESTIONS
- MULTIPLE_QUESTIONS_WITH_ANSWERS
system
# 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) $\displaystyle S = (S\smallsetminus T) \cup (S\cap T)\$, $\displaystyle T = (T\smallsetminus S) \cup (S\cap T)\$. Note that both unions are in fact disjoint unions.
Because $\displaystyle |S\smallsetminus T| = |T\smallsetminus S|$, there's a bijection $\displaystyle g: (S\smallsetminus T) \rightarrow (T\smallsetminus S)$. Now we're ready to construct a bijection $\displaystyle f:S\rightarrow T$ like this:

$\displaystyle 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) $\displaystyle |S|=|S_1|$ means there's a bijection $\displaystyle g:S\rightarrow S_1$
$\displaystyle |T|=|T_1|$ means there's a bijection $\displaystyle h:T\rightarrow T_1$
Define $\displaystyle f:S\times T \rightarrow S_1\times T_1$ as follows: $\displaystyle f\left((a,b)\right) = (g(a),h(b))$
Verify it is a bijection.

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

Is $\displaystyle \sup A - \inf B$ the least upper bound of $\displaystyle A-B$ ? Suppose it is not, then there exist $\displaystyle \varepsilon >0$ such that $\displaystyle \sup A - \inf B -\varepsilon$ is an upper bound of $\displaystyle A-B$.
Because $\displaystyle \sup A$ is a supremum, there must exist some $\displaystyle a\in A$ such that $\displaystyle a>\sup A-\varepsilon/2$.
Because $\displaystyle \inf B$ is an infimum, there must exist some $\displaystyle b\in B$ such that $\displaystyle b<\inf B+\varepsilon/2$.
We get $\displaystyle z=a-b>\sup A-\varepsilon/2 - (\inf B+\varepsilon/2) = \sup A - \inf B -\varepsilon$ which contradicts the assumption that $\displaystyle \sup A - \inf B -\varepsilon$ is an upper bound of $\displaystyle A-B$.
We conclude that $\displaystyle \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 $\displaystyle A=\{\frac{1}{1},\frac{1}{2},\frac{1}{3},\frac{1}{4 },\frac{1}{5},\ldots\} \subseteq [0,1]$ and set $\displaystyle B=\{\frac{1}{2},\frac{1}{3},\frac{1}{4},\frac{1}{5 },\ldots\} \subseteq [0,1)$. You can construct bijection $\displaystyle g:A\rightarrow B$ by setting $\displaystyle g\left(\frac{1}{i}\right)=\frac{1}{i+1}$ (verify it is a bijection).

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

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

$\displaystyle f(x) = \begin{cases} g(x) & \mbox{if } x \in A \\ x & \mbox{if } x\in [0,1]\smallsetminus A \end{cases}$
user
The text passage contains a series of mathematical problems and their solutions. The problems are related to set theory and real analysis, and the solutions are detailed step-by-step proofs.

TYPE: MULTIPLE_QUESTIONS_WITH_ANSWERS