Chapter  7, Infinite Sets
Section  7.3  The Cantor–Schröder–Bernstein Theorem
Summary
 If and are sets, then we will say that dominates , and write , if there is a function that is onetoone. If and , then we say that strictly dominates , and write .
 (Cantor–Schroöder–Bernstein theorem): Suppose and are sets. If and , then .
 Using Cantor–Schroöder–Bernstein theorem, it is easier to prove that . We need to define a onetoone function and other onetoone function .
Soln1
(a)
Suppose such that . Clearly is onetoone and onto. It follows that . Thus is reflexive.
(b)
Suppose and . Thus we can choose onetoone function and another onetoone function . Since are onetoone, the function is also onetoone. Thus .
Soln2
(a)
Suppose . It follows that and . But . Thus we have a contradiction. It follows that .
(b)
Suppose and . Thus we can choose onetoone function and another onetoone function . Since are onetoone, the function is also onetoone. Thus .
Now suppose , or we can also say . Since is transitive and , it follows that , or . But it contradicts with . Thus our assumption is wrong. Thus .
Since and , it follows that .
Soln3
Suppose and . Since , it follows that . Since , it follows that . Thus . Since is transitive and , it follows that .
Now since , it follows that . Thus we have and . Thus by Cantor–Schroöder–Bernstein theorem, it follows that .
Soln4
Suppose and . Thus we can choose onetoone function and another onetoone function .
(a)
Suppose such that .
Suppose such that . Thus . Since are onetoone, it follows that and . Thus . Thus is onetoone. Thus we can conclude that .
(b)
Suppose such that:
 if then .
 if then .
Suppose such that . Since . We have following possible cases:

Case .
Thus . Also by definition of , . Suppose . Thus . Since , it follows . Since and , it follows that . But . Thus we have contradiction. Thus . It follows that . Thus . Since , it follows . Since is onetoone, it follows that .

Case .
Similar to previous case, we can prove by contradiction that . Thus . Thus .
Thus by all possible cases, it follows that . Thus is onetoone. Thus .
(c)
Suppose such that .

.
Suppose . Clearly we can choose some such that . Since , it follows that , or . Since is arbitrary, . Thus .

is onetoone.
Suppose and are in such that . We can prove as follows:
Suppose such that . Since , it follows that . Thus for some , we have . Thus . Since is onetoone, it follows . Thus .
Since is arbitrary, it follows that .
Similarly we can also prove .
Thus .
Thus is onetoone. It follows that .
Soln5
Suppose and . Thus we can choose onetoone function and another onetoone function .
(a)
Since , we can choose some element . Lets define a function such that:
 if , then . Clearly is defined for all .
 if , then .
Clearly is onto.
Now consider the function such that . Clearly , thus . Thus is a function from to .
Now we will prove that is onetoone. Suppose such that . Thus .
Suppose is an arbitrary element. Since is onto, it follows that we can choose such that .
Since and , it follows that .
Thus . Since is one=toone, it follows . Since ,
we get . Since is arbitrary, it follows that . Thus .
Thus is onto. Thus we can conclude that .
(b)
Yes.
Suppose . Since , it follows that such that is onetoone. Thus .
Suppose , and and .
Thus . And .
Thus the only function possible from to is . But clearly is not onetoone, because it is a part of every set. Thus there is no onetoone function from to .
Soln6
(a)
Suppose . Since is finite, by countable set theorems of last section, we can choose onetoone function . Since , we can choose a onetoone function . Thus is a onetoone function. Thus is countable. Thus either finite or denumerable.
Now we will prove by contradiction that is finite. Suppose is infinite. Since is countable, it follows that must be denumerable. Thus we can represent elements of as . Let where . Thus . Since is onetoone, it follows that , if . Thus . Since , it follows . Thus . But . Thus we have a contradiction. It follows that is finite.
Suppose contains elements. Suppose . Thus . Similar to above step, lets define where . Thus . Thus . Since is onetoone, it follows that . Thus . This contradicts with our assumption that . Thus . Thus .
(b)
Since , it follows that there exist a onetoone function . Thus . Since is finite it follows from part(a) that is finite and .
Now suppose . Thus . Since , it follows that . Thus we have a contradiction. It follows that .
Since and , it follows that .
Soln7
Suppose such that .
Now we will show that is onetoone. Suppose such that . Clearly by definition of , it follows . Similarly . Note that all the elements of must contain . Thus every set in has more than one element except the set . Similarly is the only set in that contains one element. Since , it follows that . Thus . Thus is onetoone.
Thus . From Section7.2, Ex4, we know that . Thus .
Soln8
(a)
We will prove this by induction.

Base Case:
For , Thus . Using Ex7 we have . Thus .

Induction Step:
Suppose for , .
We know from Ex7 that . Since , it follows that . Since is transitive and and , it follows that .
(b)
Suppose . Clearly this set is not equinumerous with any set . Another example can be . Thus , where . Thus there are infinite possible sets which are not equinumerous with .
Soln9
Suppose such that .
Suppose such that .
Let and . Also we can define such that such that .
Clearly and are onetoone. Thus by Cantor–Schröder–Bernstein Theorem, we can define a onetoone and onto function such that:
 if , then .
 if , then .
where and and .
.
Lets compute :
.
.
.
….
.
Thus .
Thus .
Thus we have such that:
 if , then .
 if , then .
Soln10
Let .
(a)
Clearly . Thus . Since , it follows from Section7.1, Ex5 that . Thus .
(b)
Suppose such that . Thus it follows that:
.
Thus either , or . Since , it follows that . Thus the only possible case is . Thus . It follows that is onetoone.
(c)
We have is the set of all partitions of and is the set of all equivalence relation of . As we saw in section5.3, we can define a onetoone and onto function such that .
Thus .
Now from part(b) we have . Also since , it follows that . Thus . Since and , it follows that . Since , it follows that .
Now from part(a) we have . Thus by applying Cantor–Schröder–Bernstein Theorem, it follows that .
Soln11
TODO
Soln12
(a)
TODO[This is not complete.]
Suppose . Suppose and . Thus .
Since contains atleast two elements, by definition and also .
Clearly , thus it follows from Section7.2, Ex7, that .
Since , it follows . Similarly since , it follows .
Since and , it follows:
.
Since , it follows .
But we have already seen that . Thus it follows that .
Now if we also prove that , then applying Cantor–Schröder–Bernstein theorem will complete the proof.
I got stuck in proving this part: .
(b)
TODO.
Soln13
Suppose is a set of nondegenerate intervals and is pairwise disjoint.
Suppose is an arbitrary interval. Since it is nondegenerate interval, it must contains real numbers. We know
from lemma 7.3.4, that it between every two real numbers, there exist a rational number. Thus we can define a nonempty set:
.
Clearly and .
Suppose such that:
.
Now we will prove that is onetoone:
Suppose such that . Now we will prove by contradiction that . Suppose . Since is pairwise disjoint, it follows that . Suppose . It follows that for some , we have . Thus by definition of interval, . Similarly since , we can prove that . Thus . But . Thus we have a contradiction. It follows that .
Thus is onetoone.
Since is denumerable, we can define a onetoone function .
Thus we can define a funnction as:
.
Since is onetoone, it follows that is also onetoone.
Thus .
Soln14
TODO.