Chapter - 7, Infinite Sets

Section - 7.1 - Infinite Sets


Summary

  • Suppose and are sets. Then is equinumerous with if there is a function that is one-to-one and onto. We use notation to indicate is equinumerous with .
  • Suppose is a natural number. Suppose . A set is called finite if there is a natural number such that . Otherwise, is infinite.
  • We can easily note that is an equivalence relation. Thus for any sets and :
    • .
    • If , then .
    • if and , then .
  • It is shown in the book that and by giving the examples of corresponding one-to-one and onto function:
    • such that if is even, then , and if is odd .
    • , such that .
  • Using the properties of equinumerous relation, and from above example, it can be shown that , and , are equinumerous with .
  • A set is called denumerable if . It is called countable if it is either finite or denumerable. Otherwise, it is uncountable.
  • Suppose is a set.The following statements are equivalent:
    • is countable.
    • Either or there is a function that is onto.
    • There is a function that is one-to-one.
  • is denumerable.

Soln1

(a)

Suppose such that .

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

Suppose . Let . Since smallest natural number is , clearly . Thus . Thus . Since was arbitrary, it follows that is onto.

Thus there exist a one-to-one and onto function from to . Thus . It follows that is denumerable.

(b)

Suppose such that . Clearly is the set of all even integers.

Now consider a function such that .

It is trivial to see that is one-to-one and onto. Thus . We know that . Since is a transitive relation, it follows that . Thus is denumeberable.


Soln2

(a)

We know that is denumerable. Thus . Thus we can choose a function such that is one-to-one and onto.

Suppose there is a function such that .

Suppose such that . It follows that and . Since is one-to-one, it follows and . Thus . Thus is one-to-one.

Suppose . Since and is onto, it follows that for some , . Similarly for some , . Thus and . Thus is onto.

Thus . Since and is a transitive relation, it follows that . Thus is denumerable.

(b)

From Section-6.5 Ex-6 part(b), we know that .

Suppose . Thus we can define a function such that .

Clearly is onto by definition as .

Suppose such that . Thus , or . Since , it follows that and .

Thus is one-to-one and onto. Thus . Now from part(a) of this solution, , and since is transitive relation, it follows that . Thus is denumerable.


Soln3

(a)

Suppose such that . Clearly . Thus we can define a function such that .

Clearly is a one-to-one and onto function. Thus .

(b)

Suppose such that .

Suppose such that . Thus . Since and are in range , it follows that . Thus is one-to-one.

Suppose . Thus we can select some from such that . Thus is onto.

Thus .

(c)

We shall prove this in steps:

  • Prove .
  • Prove
  • Prove
  • Prove by combining last two proofs.

Lets prove one by one:

  • Proof for .

    Since is one-to-one and onto function if , and the value of will fall in for the given range.(note that since range of does not include and , value of will not equal and ). Thus the function such that is one-to-one and onto.

    It follows that .

  • Proof for .

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

  • Proof for

    Since and is associative, it follows that . Also from part(b) of this solution we know that . Since is transitive, it follows that .

  • Proof .

    Since and , it follows that .

(d)

Lets prove it in steps:

  • .

    Suppose , where . It is clear since that is one-to-one and onto. Thus .

  • .

    Suppose , where . It is clear since that is one-to-one and onto. Thus .

  • .

    Since is associative and transitive relation, we can directly see from last two steps that .

  • .

    From part(b) and (c) and since is transitive and associative, it follows that .

  • .

    From last two steps and is transitive, it follows that .


Soln4

(a)

No. Counterexample:

Suppose .

Clearly and but is not possible.

(b)

No. Counterexample:

Suppose .

Clearly and but is not true.


Soln5

Suppose . It follows that we can choose a one-to-one and onto function .

Now consider such that .

Now we shall prove following:

  • .

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

  • 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 .

  • is onto.

    Suppose . Suppose .

    Now proving that , will prove that is onto.

    Suppose . Thus we have:
    Since is onto:
    .
    Using the definition of :
    .
    Using the definition of :
    .

    Since is arbitrary, it follows that .

    Since is arbitrary, it follows that is onto.


Soln6

(a)

We will prove this by induction.

  • Base Case:

    For , Thus . Clearly since , it follows that we can choose a one-to-one and onto function . Since is onto and , it follows that . Thus .

  • Induction Step:

    Suppose theorem is correct for . Thus if , it follows that .

    Now suppose . Thus we can choose a function such that is one-to-one and onto.

    If we prove that , then we can use induction hypothesis to conclude that , or , thus proving .
    To prove , we need to prove that there exists a one-to-one and onto function from to .

    To define such a function, lets first introduce few things.

    Let . Since . Since , it follows . Thus . Thus .

    Since and is onto, it follows that we can choose some such that . Thus we have following:

    • such that .
    • such that .

    Thus we can say that and .

    Consider the relation . Since is a function, it follows is also a function. Clearly by the definition of , we have . Similarly .

    Thus is a function from . Also by the definition of and since is one-to-one and onto, we can easily see that is also one-to-one and onto.

    Thus . Thus by our induction hypothesis, it follows that , or .

    Thus we can conclude that if , then .

(b)

Suppose is finite. Thus by the definition of finite, there atleast exist some such that . Suppose there are two such sets such that and . Since is a transitive and associative relation, it follows that . Now we can follow from part(a) of this solution that .


Soln7

Given that is finite. We need to prove that iff:

  • is finite.
  • .

() Suppose is finite and . Since is finite, it follows that there is a unique such that and . Since and , it follows that . Thus is finite and .

() Suppose is finite. Since is finite, it follows that there is a unique such that and . Since , it follows that . Thus . Since and and is transitive, it follows that .


Soln8

(a)

We have to prove that . Also if then .

We will prove this by induction:

Note: We cant say anything about number of elements of . Thus we cant use induction on the number of elements in . Because lets say if we assumed that contains elements, then this assumption automatically means that is finite(which may not be the case).

  • Base Case:

    For , clearly . Since , it follows that . Thus and .

  • Induction Step:

    Suppose for theorem is correct. Thus for all , if , then is finite and . Also if , then .

    Now consider that . Consider the following cases:

    • Case .

      Since , it follows , or is finite and . Also clearly .

    • Case .

      Since , there are following possible cases:

      • Case .

        Since and , it follows that , or . Now clearly from the induction hypothesis is finite and .

      • Case .

        Since and , it follows that we can choose some element from such that . Also since , it follows that . Now consider that set .
        Clearly . Thus by induction hypothesis, it follows that is finite and .

        Now suppose such that:

        • if then .
        • if then .

        Clearly is one-to-one and onto function. Thus . Then since is finite, we can follow from Ex-7 that . Thus .

      Thus from both cases is finite and .

    Thus from all cases is finite and .

(b)

Suppose is finite and . Since is finite, it follows that we can choose a one-to-one and onto function . Consider a function such that . Let . Clearly . Thus from part(a) we have:

  • .
  • if , then .

Now consider the function such that . Now we can easily check that is one-to-one an onto.

Suppose such that . Thus . Since is one-to-one, it follows that . Thus is one-to-one.

Now suppose that . Thus . Thus we can choose an element such that . Since , it follows that is onto.

Thus is one-to-one and onto. Thus . Thus from Ex-7, it follows that .

Thus . Also if , then .

For the case , it follows that . Thus we can choose some element in such that . But because , it follows that there exist some element such that . Since , it follows . Thus .

Thus we can conclude the following:

  • .
  • if , then .

Soln9

We will prove this by contradiction. Suppose is finite. Thus we can choose some positive number such that . Since , it follows that . Thus .
Now since is finite and and , then it follows from Ex-8 part(b) that . Thus we have a a contradiction. Thus is not finite, or is infinite.


Soln10

We will prove this by induction.

  • Base Case:

    For , it follows that . Since is onto, it follows that . Thus is finite and .

  • Induction Step:

    Suppose theorem is correct for . Thus if and onto then is finite and .

    Now consider an onto function . Thus proving is finite and will complete our proof.

    Let and . Suppose . Since is a function, clearly is also a function. Also since is onto, is also onto. Also we can see that and .

    Thus we have and is onto. It follows from induction hypothesis that is finite and .

    Since is finite, we can choose a number such that . Thus . Since , we can choose a one-to-one and onto function . Now consider . As is one-to-one and onto, it follows that is also one-to-one and onto. Also by the definition of we have and . Thus . Thus . It follows that is finite and .

    We have , or , it follows that . Thus .


Soln11

(a)

Suppose and are finite and . Suppose . We will prove by contradiction. Suppose is onto. Since is finite, we can choose some integer such that . Thus we can choose a one-to-one and onto function . Since and , it follows . Since and are onto, it follows that is onto. Thus it follows from Soln10 that . Since , it follows . But this contradicts with the given that . Thus our assumption that is onto is wrong. It follows that is not onto.

(b)

Suppose and are finite and . Suppose . We will prove by contradiction. Suppose is one-to-one. Since is finite, we can choose some integer such that . Thus we can choose a one-to-one and onto function . Since and , it follows . Since and are one-to-one, it follows that is one-to-one. Let . Clearly . Consider the function such that . Clearly is one-to-one and onto. Thus . Since , it follows form Ex-8 that is finite and . Also since is finite and is finite, it follows from Ex-7 that . Thus . Since , it follows that . But this contradicts with . Thus our assumption is wrong. Thus is one-to-one.

(c)

Suppose . Thus and are finite and for some positive number , and . It follows that . Suppose . We have to prove the following:

  • if is one-to-one, then is onto.
  • if is onto, then is one-to-one.

Lets prove one by one:

  • if is one-to-one, then is onto.

    Suppose is one-to-one. To prove that is onto, it will suffice to prove that . Let . Thus . Suppose such that . Clearly is one-to-one and onto. Thus . It follows from Ex-7 that . Since , it follows . Now we will prove by contradiction that . Suppose . Since , it follows that we can choose some element such that . Suppose . Since , clearly . Thus . Also we can see that and , it follows from Ex-8 part(b) that . Since and , it follows that . But this contradicts with . Thus it follows that . Thus . Thus is onto.

  • if is onto, then is one-to-one.

    Suppose is onto. Suppose such that . Now we will prove by contradiction that . Suppose . Let . Thus and . Consider function such that . Clearly is onto. Also since and , it follows from Ex-8 part(b) that is finite and . Let . Thus . Since , we can choose a one-to-one and onto function . Thus . Since and are onto, it follows that is also onto. Since and is onto, it follows from Ex10 that . Since , it follows that . This contradicts with . Thus our assumption that is wrong. Thus . Since are arbitrary, it follows that is one-to-one.


Soln12 TODO. It is solved in book.


Soln13

Given:

  • and .
  • and such that both functions are one-to-one and onto.

Goal:

  • To Prove is one-to-one and onto function from to .

Thus we first need to prove that is a function.

To prove is a function, we need to prove existence and uniqueness:

  • Existence:

    Suppose . Since , it follows either or . Suppose then . Thus . Since , it follows such that and .

    Similarly if , we can prove that there exist an element such that .

  • Uniqueness:

    Suppose . Thus we have following possible cases:

    • Case and .

      Thus and . But . Thus this case is not possible.

    • Case and .

      Thus and . But . Thus this case is not possible.

    • Case and .

      Since is a function, it follows .

    • Case and .

      Since is a function, it follows .

    Thus from all possible cases, . Thus is a function.

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

Suppose . Thus we have following possible cases:

  • Case and .

    Thus and . But this is not possible since .

  • Case and .

    Thus and . But this is not possible since .

  • Case and .

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

  • Case and .

    Since is onto, it follows that .

Thus from all possible cases, . Thus is a one-to-one function.

Now we will prove that is onto:

Suppose . Thus either or . Suppose , it follows that we can choose such that . Thus . Thus there exist an element such that .
Now suppose . It follows that we can choose such that . Thus . Thus there exist an element such that . Thus in either case there exist an such that . Thus is onto.


Soln14

(a)

Suppose is infinite. Let . We will prove by contradiction that . Suppose . It follows that . Suppose such that . Clearly is an onto function. Thus by Ex-10, it follows that is finite and . Since and is finite, it follows from Ex-8 part(b) that is finite. But this is a contradiction since it was assumed in the problem the is infinite. Thus .

(b)

We will prove this by strong induction.

Suppose is an arbitrary natural number. Suppose .

We know that smallest element of . Suppose . Let . We will prove by contradiction that . Suppose , or . Since , then by induction hypothesis it follows that .

We know that smallest element of set . Thus we can also say .

Since , it follows that . Or we can also say .

We know that for sets , if , then .

Thus .

Since , it follows . But by definition of , smallest element of . Thus . But . Thus .

Since , then by the definition of , it follows that . Thus . Thus , which is clearly a contradiction with the definition of function . Thus our assumption is wrong. Thus .

(c)

  • Proof for is one-to-one:

    Suppose such that . We will prove by contradiction that . Suppose . Thus either or . Suppose . Since smallest element of . Since , it follows that . Thus . Thus . But it contradicts with . Similarly we will get a contradiction for . Thus . Thus is one-to-one.

  • Proof for is onto:

    Suppose . From part(b) we have . Since smallest element of and , it follows that . Since , it follows that . Thus for some such that , . Thus is onto.


Soln15

Suppose . Suppose is countable. Thus by theorem 7.1.5, we can choose a function such that is one-to-one. Suppose such that . Since is one-to-one, it clearly follows that is also one-to-one. Thus again by theorem 7.1.5, it follows that is countable.


Soln16

Suppose , and is infinite, and is finite. We will prove by contradiction that is infinite. Suppose is finite. Thus for some , . Since is finite and for some , .

Suppose . Thus . Thus . It follows that . Thus we can difine a function from to . Thus .

Since and , it follows that . Also we have . Since and are disjoint, and and , it follows that . Thus . It follows that is finite. But this contradicts with is inifinite. Thus our assumption is wrong. Thus is infinite.


Soln17

Suppose is denumerable. Thus we can declare as . Thus we can also say such that . Since is partial order on , it follows from Ex-2 from section 6.2, that we can define a partial order such that and .

Now consider such that . Since is partial order on , and again using Ex-2, Sec-6.2, we can define a partial order such that and .

Let . Thus we have . Suppose .

Now we will prove that is a total order on such that .

Thus we first need to prove that is partial order:

  • is reflexive:

    Since is partial order on it follows . Since , it follows . Thus . Thus is reflexive.

  • is transitive:

    Suppose and . Thus for some , and . Suppose , then clearly since is partial order, it follows .
    Now suppose . Then either or . Thus either or . Since and are partial order, it follows that either or . Thus . Thus is transitive.

  • is antisymmetric:

    Suppose and . Thus for some , and . If , clearly since ia partial order, it follows . Now suppose . Thus either or . Thus either or . Thus in either case. Thus is antisymmetric.

Since is reflexive, transitive and antisymmetric it follows that is partial order.

Now suppose that . Suppose is the largest of and . By the definition of , it follows that and . Since , it follows that either or . Since , it follows that either or .

Thus is total order.


Soln18

Suppose , and are finite. Thus for some , , and . .

Suppose . Thus . Thus . It follows that . Thus we can difine a function from to . Thus .

Since and , it follows that . Since are disjoint and are also disjoint and , it follows that . Thus . It follows from Ex-7 that . Thus , or , or .


Soln19

We will prove this by induction.

  • Base Case:

    For , we have . Since is finite, it follows is also finite. Also .

  • Induction Step:

    Suppose for , theorem is correct. Thus is finite and .

    Since , if , it follows that . Since is finite and by induction hypothesis is also finite. Thus for some we have and .

    Since , it follows that .

    Since and , it follows that . Thus .

    Thus is finite and is



    .


Soln20

(a)

Suppose and are finite. We will prove by induction on number of elements in .

  • Base Case:

    Suppose . Thus . It follows that .

  • Induction Step:

    Suppose theorem is correct if . Thus .

    Now suppose contains elements. Suppose is an arbitrary element. Let . Since and are finite, it follows form Ex-18 that . Thus .

    Since , it follows . By induction hypothesis we know that .

    Clearly each set of contains where . Thus we can clearly write a one-to-one and onto function such that . Thus . Thus it follows from Ex-7 that .

    Since and are disjoint it follows that is




(b)

A meal is a pair where is set of entrees and is set of desserts.
Thus from part(a) .


Soln21

(a)

Since all the functions from to are subsets of . Thus we have:

.
.

Since , it follows that we can choose one-to-one and onto function .
Similarly, since , it follows that we can choose one-to-one and onto function .

Suppose is defined as:

.

Now we will prove that is a one-to-one and onto function.

  • Proof for is a function:

    Suppose . If , clearly . Suppose if , then clearly the set is not empty because and are functions. Now suppose . Then by the definition of , it follows that . Thus for each there exist a single/unique . Thus is a function.

  • Proof for is one-to-one:

    Suppose are arbitrary elements in such that . Thus if we show that , it will prove that is one-to-one.

    Suppose . It follows that . Let . Thus . Since , it follows that . By the definition of , it follows that for some , , and for some , such that . Since are one-to-one function, it follows that and . Thus it follows that . Since is arbitrary, it follows that .
    Similarly it can be proved that . Thus . Thus is one-to-one.

  • Proof for is onto:

    Suppose . Suppose . Thus and . Since are onto functions, it follows that we can choose element and such that and . Thus we can define the following set:

    .

    Clearly . Thus is onto.

Thus is a one-to-one and onto function. It follows that .

(b)

Suppose such that .

Clearly proving as a one-to-one and onto function will complete the proof.

  • Proof that is a function:

    Since and , it follows that is also a set and . Also clearly by set the definition of union, there is exactly one union for the sets and .

  • Proof that is one-to-one:

    Suppose are arbitrary elements of such that . Thus by the definition of , it follows that . Since are subsets of and are subsets of and , it follows that:

    • .
    • .
    • .
    • .
      Now we will prove by contradiction that and . Suppose . Thus we can choose an element , either or . Suppose . Since and and , it follows that . Thus . But . Thus it is a contradiction. Thus our assumption is wrong. Similarly for the case , we will get a contradiction. Thus .
      Similarly we can also prove that . Thus . Thus is one-to-one.
  • Proof that is onto:

    Suppose . Thus ,or . Consider the set and . Clearly . Thus is onto.

(c)

Suppose are finite sets. We know that . Thus we can say that all the elements of are in the set of all subsets of . Thus . Since and are finite it follows from Ex-20 that is also finite. Since is finite, we can choose a unique positive number . Thus contains elements. It follows that contains elements. Clearly . Thus is also finite. Since and is finite, it follows that is also finite.

We will prove that . We will prove it using induction on .

  • Base Case:

    Suppose . Thus . Thus . Thus .

    Note that because it is a set of all functions from to . Since function is also a set and there is no element in any of these functions. Thus these sets(functions) are empty. Thus . It is similar to the case of power set of empty set: .

  • Induction Step:

    Suppose theorem is correct if . Thus if , then .

    Now suppose . Suppose is an arbitrary element. Let . Thus . Since , it follows from part(b) of this solution that . Thus . Using Soln20 part(a) it follows that .

    Thus we have .

    Since , by induction hypothesis .

    Now consider the set of functions: . Suppose . We shall prove by contradiction that contains only one element. Suppose contains elements. Thus are the elements in . But this is not possible because is a function and in this case is not unique. Thus can contain only one element. Thus it is easy to check that total number of such functions will be same as the number of elements in . Thus .

    Thus we have .

    Thus , or .

(d)

Each student gets exactly one grade but one grade can be assigned to multiple students. Thus we can say that any possible assignment of grades will be a function from to . Thus the total number of ways of grade assignment will be total number of such functions possible, or . From part(c), .


Soln22

(a)

We will prove it by induction on .

Suppose .

  • Base Case:

    For , and . Thus there is only one function possible such that . Thus n! = 0! = 1 where .

  • Induction Step:

    Suppose theorem is correct for . Thus .

    Now consider . If we can find a way to create using , it will lead us to formulae for .

    Consider the sets and . Clearly both have elements. Since , we use also represent elements of as . Thus . We know that . Now suppose is an arbitrary element of . Let . Thus contains element. Let is the set of all one-to-one and onto functions from . Suppose . Clearly all the elements of are one-to-one and onto functions from \to .

    Let . Now we will prove that .

    () Suppose . Thus is a one-to-one and onto function from to . Thus for some , . Clearly . It follows that . Thus . Thus .

    () Clearly for , . Suppose . Thus is a one-to-one and onto function from to . Thus must be in . Thus . Since is arbitrary it follows that .

    Thus .

    Now note that for , the sets and are disjoint. Consider a function such that . Clearly is one-to-one and onto function. Thus . But by our induction hypothesis . Thus . Since and , if , it follows from Soln19 that:
    .
    .
    .
    .
    .

    Thus .

(b)

We need to prove that . Thus . Thus if we can prove that , then will directly follow from the result.

Now we will use induction to prove that where is number of elements in .

  • Base Case:

    For , , thus . Thus .

  • Induction Step:

    Suppose if contains elements, then .

    Now suppose contains elements. Since is finite, we can represent elements of as . Let for some natural number . Let . Thus contains elements. Let . Thus by induction hypothesis .

    Now lets define and . We know that contains all relations which are total order. Suppose , then clearly by the definition of , it follows that there exist some such that . Since is total order, it follows that is also total order. Clearly we can see that is the smallest element in . Thus if . Also note that it can be easily seen that . Thus .

    Clearly the set . Since , it follows from Ex-19 that .

    Thus .

Thus .

(c)

We can say that each arrangement is a one-to-one and onto function from each student to seat. Thus the total possible ways will be total number of such functions. Thus it follows form part(a) that total number of ways .


Soln23

Since is an equivalence relation, it follows that is a partition on . It follows that if and and then . Now suppose , it follows that where is any arbitrary element. Since , it follows that .

Since , it follows that . Also we know that . Thus it follows from Ex-19 that . Thus .


Soln24

(a)

Since and are finite, it follows we can choose natural numbers such that and . Thus and . Since , it follows that .

Clearly and are disjoint sets. Thus it follows from Ex-19 that: . From Ex-18 we have . Thus . Clearly . Thus .

(b)

We can write . Using part(a) we have:
.
.
.
.
.
.


Soln25

We need to prove , where:
.
.

We will proceed by induction.

  • Base Case:

    For , we have . Also , thus we have . Thus .

  • Induction Case:

    Suppose theorem is correct for . Thus .

    Now consider for , we have . Thus by applying Ex-24 part(a), we get:
    .
    .

    Let :
    .
    Thus we can apply induction hypothesis on first and last term:
    .

    is also defined like . Thus . As we can see is present in every term of . Since all terms are intersection of sets and every term contains , we can also say . Thus . Putting this into our equation above:

    .

    We know that . Thus . Putting this into equation:

    .
    .
    .
    .

    We know that contains two type of terms. One type of term contains and other type of terms will not contain . Thus we can say that . Now we can see that all the sets used in above equation belongs to . Thus we can also write the equation as:

    .


Soln26

We have

Using Ex-18:

Using Ex-24:

Since :


where .

Thus is even.


Soln27

Since pin is a 4 digit number, it follows that number of total pins (from to ).

Suppose , where is set of pin number and is set of customer number. Thus maps the customer to pin.

Since , it follows . Thus it follows from Ex-11 part(b) that is not one-to-one.

Thus there is atleast one case such that same pin is mapped to more than one customer.


Soln28

Suppose is set of all classes. Suppose and denotes the set of classes attended by Alice and Bob respectively.

As both have never seen each other in any class, it follows that . Also note that the set denotes the classes attended by atleast one of them. Clearly . Thus . Since , it follows that .

Now we will prove by contradiction. Suppose and both missed less than half of the classes. We know that classes missed by Alice and Bob are and . Thus . Thus we have . Similarly . Thus adding both we get . This contradicts with . Thus our assumption is wrong. Thus either Alice or Bob missed atleast half of the classes.