Wednesday 14 November 2018

discrete mathematics - Using the Cantor Schroeder Bernstein Theorem



I am asked to show that if $a


(i) $(a,b)$ ~ $(0,1)$



(ii) $[a,b]$ ~ $(0,1)$



using the Cantor Schroeder Bernstein Theorem.



Now, I know that $(0,1)$ ~ $\mathbb{R}$, so I think I would need to use this somehow to create my injections. Also, I am thinking I might need to use decimal expansions to define my functions but I am not too sure how the fact that for (i) $a,b$ are not included but for (ii) they are. Would it be less complicated to just give an actual function rather than go into decimal expansions?



Any suggestions on how to go about finding the injections for (i) and (ii)? Also, I would think we need to use that assumption that the decimal does not end in infinitely many $9$'s.


Answer




For the first one, you can give the bijection directly: $$f(x) = \frac{x-a}{b-a}$$



For the second one, use the inverse of the above bijection as an injection from $(0, 1)\to (a,b)\subset [a,b]$. For the reverse injection, define $g: [a, b]\to [0.1, 0.9]\subset(0,1)$.



Edit 1: For part one, this is how I find the bijection. Every open finite interval can be mapped bijectively to another open finite interval with a linear function. This is also true for closed finite intervals. All you need to do is to find an equation for a line that maps the endpoints of one interval to the other. In my case I wanted a line $f(x) = \alpha\, x + \beta$ such that $f(a) = 0$ and $f(b) = 1$. You have two equations and two unknowns:
$$
\begin{cases}
\alpha\, a +\beta = 0\\
\alpha\, b +\beta = 1
\end{cases}

$$
Solving for $\alpha$ and $\beta$, we have $\alpha = 1/(b-a)$ and $\beta = -a/(b-a)$. This gives $f(x) = (x-a)/(b-a)$.



Of course, I didn't do any of this when I wrote the answer. I just said I want $f(x)$ that maps $a$ to $0$, therefore, I'm going to have $x-a$ multiplies by something, and that something should cancel out the value of $x-a$ at $x=b$ so that it maps $b$ to $1$. So it should be $1/(b-a)$.



Edit 2: For part 2, we are using Schröder–Bernstein theorem, which by the way I did not know it had a name until today. It states that to prove that there exists a bijection, you don't need to find the bijection itself. All you need is to show that there is an injection from the first set into the second, and another from the second set into the first.



Note that for an injection, you do not need to cover the whole interval in the second set. You just need a one to one map from the first set with an image that is a subset of the second. And that is why you do not have to worry about the endpoints.



Injection from $(0,1)$ into $[a,b]$: If you find an injection from $(0,1)$ into $(a,b)$, it is also an injection from $(0,1)$ into $[a,b]$ because an injection does not need to be onto. That is, it does not need to cover the whole interval $[a,b]$.




Injection from $[a,b]$ into $(0,1)$: If you find an injection from $[a,b]$ into $[0.1, 0.9]$ that is also an injection from $[a,b]$ to $(0,1)$ because, again, you don't need to cover the whole interval $(0,1)$ for an injection. I will leave it to you to find the second injection.


No comments:

Post a Comment

real analysis - How to find $lim_{hrightarrow 0}frac{sin(ha)}{h}$

How to find $\lim_{h\rightarrow 0}\frac{\sin(ha)}{h}$ without lhopital rule? I know when I use lhopital I easy get $$ \lim_{h\rightarrow 0}...