MAT 246, PS3 First Draft Due. Mon April 10 Time 10:00 pm. EST
Please note:
1. Ideally the PS must be written in the spaces provided, and page by page (a picture or scan of individual pages) to be
uploaded to the appropriate pages of a Crowdmark file (link to be posted.) If you wish, you can write your answers on
separate pieces of paper and upload them properly at each page of the Crowdmark. Please note that any mismatch in
uploading the pages of the solutions may cause in parts of the solutions not getting marked.
2. Please provide your final, polished solutions in the spaces provided. If you have no access to a printer you can write your
solutions on a blank sheet of paper and upload a picture of scan. Remember, it is an art to write a short yet complete
solution; one learns a lot from practicing this art. Please write a complete, even though long solutions. Then inspect and
edit; while editing, ask yourselves:
- am I proving common believes and facts accepted in the literature? If yes, know which facts are common belief and
which ones need an argument.
- can I just quote some of the facts that I tried to prove? This requires a good familiarity with the literature of the
subject (in our case, the textbook and the slides, and earlier questions in the same PS).
- am I introducing too many cases in my proof, and presenting parallel arguments? Change your type of argument if
possible (direct proof versus proof by cases, or proof by contradiction.)
Editing your first complete solution is a very good way of learning. Make sure you have a good solution, then return to
it and reflect on the above questions.
3. Problem set questions contain ideas complementary to the textbook and lecture materials, opportunity for reflection
and deepening on the subject. The level of difficulty of the questions is elementary so that each student has chance to
individually think about the problems. So, please don’t let your “kind" friends take this opportunity away from you!
4. Not all questions will be marked, nor they are all of equal weight, and it is not known in advance which questions will be
marked, and how heavy they will be weighed. Therefore if a question is skipped one may lose a larger portion of the PS
mark than one would expect.
5. To receive full mark on the computational questions all the computation details must be provided. For questions involving
proofs there is no need to prove textbook or “slides" proofs but one can simply quote them. When a theorem is applied
the relevance of it to the proof must be made clear.
6. Collaboration in this work is not allowed. You may discuss the idea of a the solutions only, but each person must write
their own solutions completely independently, without knowing or consulting the structure and details of the argument of
another person.
So please be careful not to share any written hint with your friends, because some people have photographic memory,
and then your solutions may become subject to plagiarism.
7. By participating in this problem set you agree that you are aware of the university regulations regarding plagiarism.
Individual students are expected to organize and write their own solutions independently. During the online teaching,
and while students are connected through email, any assistance to your fellow classmate in the form of a written note
might be directly copied and it may count as a form of plagiarism. Markers are carefully monitoring the solutions, and
any incidence of plagiarism, and all the parties involved will be dealt with according to university regulations. Please
carefully read the item regarding plagiarism in our course outline, and consult the university policies regarding plagiarism
(not knowing the rules is not a good excuse for not obeying them):
http://www.artsci.utoronto.ca/newstudents/transition/academic/plagiarism
Page 1 of 3
MAT 246, PS3 First Draft Due. Mon April 10 Time 10:00 pm. EST
-
0. Failure to answer this question may result in a mark of 0 on the entire PS2. And it is not the name,
signature and date, but it is the acknowledgement .. signing some statement that is intended in this part:
Please sign below as an acknowledgment that you have read the cover page ; (unsigned papers shall not be marked.)
Print Name (first, last) : , Signature: Date:
1. (a) Apply RRT to prove 3
√
2 +
√
3 is irrational.
(b) Prove Q[ 3
√
2] is not a field extension of Q.
(c) Prove Q(
√
2)(
√
3) is a field extension of Q(
√
2), and that Q(
√
2)(
√
3) = Q(
√
3)(
√
2).
2. (a) Design a bijection between Z ∪ [1,+∞) and (0,+∞). Justify your answer.
(b) Consider the infinite set S and a countable set A disjoint from S. Design a bijection between A ∪ S and S.
(Hint: how is Theorem 10.3.26 and part (a) are relevant to this question?)
3. (a) Read Theorem 12.4.12 and repeat this process to determine the Cartesian form of the first complex cube root
of unity, other than 1. (Of course this is known to us, but we are trying to use the technique of 12.4.12 to carry
on this task.)
(b) Prove, using mathematical induction, (PMI or PCMI whichever works better) that any non-constant polynomial
p(x) (of degree n, for any n ∈ N) with real coefficients can be factored into product of linear and quadratic
polynomials with real coefficients. (Note: make sure to justify each step of your argument.)
4. Recall, the set of functions from a set A to a set B is denoted by BA.
(a) Consider the set S = {a, b, c} and design a bijection between NS (the set of all functions from {a, b, c} to N)
and the set N× N× N. On the other hand design a bijection between SN and [0, 1].
(b) Design a bijection between
({0, 1}N)N and {0, 1}N×N
(c) Prove that the set of all sequences of real numbers has cardinality c. (Hint: one such sequence is a function from
N to [0, 1])
5. (a) Here is a formal argument for proving theorem 10.2.10 (textbook proof is very intuitive, which is good to know, but
not formal enough.) Let {An : n ∈ N} be a countable collection of pairwise disjoint, countable sets. (Pairwise
disjoint means any two sets in this collection are disjoint.) Assume further that for each n, fn : N −→ An is a
bijection that witnesses the set An is countable. We define a function
F : N× N −→
∞⋃
n=1
An as follows F (n, i) = fn(i) for all (n, i) ∈ N× N
Prove that F is a bijection.
Page 2 of 3
MAT 246, PS3 First Draft Due. Mon April 10 Time 10:00 pm. EST
(b) Apply Corollary 10.3.10 and FTA (uniqueness of factorization and the Canonical factorization) to prove the collection
of all finite sequences of natural numbers must be countable. (Hint: a finite sequence of natural number is of the
form (n1, n2, . . . , nk) for some k ∈ N, and where all nj ∈ N. Furthermore we know there are infinitely many prime
numbers p1, p2, p3, . . . .
6. Read the document on Structural Induction (posted in LECTURES module). Also read the statements of theorems
12.3.7, 12.3.8, 12.3.9, 12.3.10, 12.3.11, and briefly look at the discussions there (these are basically grade 11 algebra.)
In this question we are writing a complete proof using technique of structural induction, for the following fact:
all the Constructible point in the plane must have Surd coordinates. Of course this is mentioned in lines 2-3 of
the proof of Theorem 12.3.12, and we are trying to formalize this using an application of Structural Induction.
Make sure you understand the involvement of the Structural induction in this arguemnt and clearly present a
sold argument. (Note: even though the readings involved for answering this question is a lot, the answer itself is very
short, as it is the proof given in the textbook.)
Page 3 of 3