Solution to We assume the question is: What is mathematical foundation for computer science? Solution: The mathematical … - Sikademy
Author Image

Archangel Macsika

We assume the question is: What is mathematical foundation for computer science? Solution: The mathematical side concentrates on areas where computers are used, or which are relevant to computer science, namely algebra, general topology, number theory, combinatorics and logic. Examples from the computing side include computational complexity, concurrency, and quantum computing.

The Answer to the Question
is below this banner.

Can't find a solution anywhere?

NEED A FAST ANSWER TO ANY QUESTION OR ASSIGNMENT?

Get the Answers Now!

You will get a detailed answer to your question or assignment in the shortest time possible.

Here's the Solution to this Question

Proof:

Given theorem is Schroeder-Bernstein Theorem


\begin{aligned} &\text { We call an element } b \text { of } B \text { lonely if there is no element } a \in A \text { such that } f(a)=b . \text { We say that an element } b_{1} \text { of } B \text { is a descendent of an } \\ &\text { element } b_{0} \text { of } B \text { if there is a natural number } n \text { (possibly zero) such that } b_{1}=(f \circ g)^{n}\left(b_{0}\right) \text {. } \\ &\text { We define the function } h: A \rightarrow B \text { as follows: } \\ &\text { Note that } f(a) \text { cannot be lonely itself. If } f(a) \text { is the descendent of a lonely point, then } f(a)=f \circ g(b) \text { for some } b \text {; since } g \text { is injective, the } \\ &\text { element } g^{-1}(a) \text { is well defined. Thus our function } h \text { is well defined. We claim that it is a bijection from } A \text { to } B \text {. } \\ &\text { We first prove that } h \text { is surjective. Indeed, if } b \in B \text { is the descendent of a lonely point, then } h(g(b))=b ; \text { and if } b \text { is not the descendent of a } \\ &\text { lonely point, then } b \text { is not lonely, so there is some } a \in A \text { such that } f(a)=b ; \text { by our definition, then, } h(a)=b \text {. Thus } h \text { is surjective. } \\ &\text { Next, we prove that } h \text { is injective. We first note that for any } a \in A \text {, the point } h(a) \text { is a descendent of a lonely point if and only if } f(a) \text { is a } \\ &\text { descendent of a lonely point. Now suppose that we have two elements } a_{1}, a_{2} \in A \text { such that } h\left(a_{1}\right)=h\left(a_{2}\right) . \text { We consider two cases. } \\ &\text { If } f\left(a_{1}\right) \text { is the descendent of a lonely point, then so is } f\left(a_{2}\right) \text {. Then } g^{-1}\left(a_{1}\right)=h\left(a_{1}\right)=h\left(a_{2}\right)=g^{-1}\left(a_{2}\right) . \text { Since } g \text { is a well defined function, it } \\ &\text { follows that } a_{1}=a_{2} \text {. } \\ &\text { On the other hand, if } f\left(a_{1}\right) \text { is not a descendent of a lonely point, then neither is } f\left(a_{2}\right) \text {. It follows that } f\left(a_{1}\right)=h\left(a_{1}\right)=h\left(a_{2}\right)=f\left(a_{2}\right) . \text { Since } \\ &f \text { is injective, } a_{1}=a_{2} \text {. } \\ &\text { Thus } h \text { is injective. Since } h \text { is surjective and injective, it is bijective, as desired. } \end{aligned}


Related Answers

Was this answer helpful?

Join our Community to stay in the know

Get updates for similar and other helpful Answers

Question ID: mtid-5-stid-8-sqid-406-qpid-293