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 one-to-one. 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 one-to-one function and other one-to-one function .

Soln1

(a)

Suppose such that . Clearly is one-to-one and onto. It follows that . Thus is reflexive.

(b)

Suppose and . Thus we can choose one-to-one function and another one-to-one function . Since are one-to-one, the function is also one-to-one. Thus .


Soln2

(a)

Suppose . It follows that and . But . Thus we have a contradiction. It follows that .

(b)

Suppose and . Thus we can choose one-to-one function and another one-to-one function . Since are one-to-one, the function is also one-to-one. 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 one-to-one function and another one-to-one function .

(a)

Suppose such that .

Suppose such that . Thus . Since are one-to-one, it follows that and . Thus . Thus is one-to-one. 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 one-to-one, 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 one-to-one. Thus .

(c)

Suppose such that .

  • .

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

  • is one-to-one.

    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 one-to-one, it follows . Thus .

    Since is arbitrary, it follows that .

    Similarly we can also prove .

    Thus .

Thus is one-to-one. It follows that .


Soln5

Suppose and . Thus we can choose one-to-one function and another one-to-one 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 one-to-one. 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=to-one, 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 one-to-one. Thus .

Suppose , and and .

Thus . And .

Thus the only function possible from to is . But clearly is not one-to-one, because it is a part of every set. Thus there is no one-to-one function from to .


Soln6

(a)

Suppose . Since is finite, by countable set theorems of last section, we can choose one-to-one function . Since , we can choose a one-to-one function . Thus is a one-to-one 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 one-to-one, 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 one-to-one, it follows that . Thus . This contradicts with our assumption that . Thus . Thus .

(b)

Since , it follows that there exist a one-to-one 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 one-to-one. 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 one-to-one.

Thus . From Section-7.2, Ex-4, we know that . Thus .


Soln8

(a)

We will prove this by induction.

  • Base Case:

    For , Thus . Using Ex-7 we have . Thus .

  • Induction Step:

    Suppose for , .

    We know from Ex-7 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 one-to-one. Thus by Cantor–Schröder–Bernstein Theorem, we can define a one-to-one 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 Section-7.1, Ex-5 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 one-to-one.

(c)

We have is the set of all partitions of and is the set of all equivalence relation of . As we saw in section-5.3, we can define a one-to-one 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 Section-7.2, Ex-7, 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 non-empty set:
.

Clearly and .

Suppose such that:

.

Now we will prove that is one-to-one:

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 one-to-one.

Since is denumerable, we can define a one-to-one function .

Thus we can define a funnction as:

.

Since is one-to-one, it follows that is also one-to-one.

Thus .


Soln14

TODO.