=========================================================================== CSC 363H Exercise 4 -- Grading Scheme Fall 2007 =========================================================================== As usual, take off marks for ambiguous or incorrect notation, ambiguous or vague or incorrect claims that are not substantiated, or any other aspect of the answer's write-up that makes it difficult or impossible to understand. A. [5 marks] 2 marks: clear attempt to describe systematic way to list all 5-tuples and argue enumeration is exhaustive 3 marks: correct enumeration B. [4 marks] Argument given in sample solutions: -1 per mistake Proof by diagonalization: -1 per mistake, including missing argument that constructed number is irrational (must include argument that constructed number has non-repeating decimal expansion) C. [3 marks] 1 mark: answer implies A' subset of ~A_TM 2 marks: answer implies ~A_TM not a subset of A' ----------------- Marker's Comments ----------------- In general, the proofs were full of inconsistencies, ambiguities, incorrect claims and unreadable arguments. I took off many marks as suggested by the standard scheme we have. For this reason I can hold extra office hours so that I can explain my claims in person. A. 1. When describing an enumeration, we have to give an explicit (systematic) procedure that realizes the enumeration. The procedure has to be well defined and should be usable by anyone who does not know the procedure in advance. This is in general true, anytime we have to design an algorithm. 2. Some students associated with each natural number a set of 5-tuples that add up to that number. They did so only for the first few natural numbers; there was no way to deduce the algorithmic idea they were applying. Moreover, I believe that if they were challenged to give the same (finite) sequence of 5-tuples when the natural number is (let's say) 106, they would not be able to. 3. Whoever wrote just an example without describing what he (she) is arguing about got 0. There should be no need to mention here that a bunch of 5-tuples followed by some natural numbers do not explain anything! 4. Many students tried to use a lemma saying that if A,B are countable then so is their cartesian product (of course this is true). However only a few stated explicitly the lemma and proved it. Most of the students used ideas of that approach, but their arguments were full of inconsistencies, ambiguities, and incorrect claims. For this reason I decided to write down how a full proof of such an argument should look like (up to some level of details). claim (i): If A, B are countable sets, so is their cartesian product C = AxB. proof: If any of them is finite, then C can be easily seen to be countable. Next suppose that both A,B are infinite sets. Since both are countable, we can write A={a_1,a_2,...} and B={b_1,b_2,b_3,...} (that is we can enumerate their elements). Then use the same proof as for the rational numbers to argue that AxB is countable. claim(ii): For any t>=1, if A is countable, so is A^t (where A^t is the cartesian product of A with itself. Note that the question is about N^5). proof of claim by induction on t: basis of induction: t=1, A is countable. inductive step: we assume the correctness of the claim for some t, and we prove the validity of the statement for t+1. Note that A^{t+1} is exactly AxA^t, and both A,A^t are countable (inductive hypothesis). By claim (i) so is their cartesian product. 5. When describing an algorithm, giving code (in c++ or java) can be very confusing, especially if you are not explaining the high level of your idea. If you decide to do so, make sure that you define every variable or procedure that you will use so that the reader can understand. 6. When writing a proof, you have to be formal and use explanatory statements. In particular, you have to make sure that you precisely state your claims and then prove them; the first is important so that the reader can follow the argument, and the second because a claim without a proof is useless. 7. Many students claimed that they used diagonalization to prove that the set of 5-tuples of natural number is countable. This technique is used to prove exactly the opposite! 8. Many students associated (existentially and not constructively) with each natural number a finite set of 5-tuples (the 5tuples that add up to that number). It was nice that they argued that any such set is indeed finite, but for the argument to be complete, one should argue about the following two statements as well: a) Why is this union of infinite many finite sets countable, b) why does this union cover all 5-tuples (the second is much easier). B. 1. Many students thought that it was enough to say that R is uncountable while Q is countable. Of course this is not a complete proof. This was worth 1 mark (out of 4). The point of the exercise was to prove(!!) that you cannot have R-Q countable when R is uncountable and Q is countable. 2. When using diagonalization the following step is very important: We start with an enumeration of some infinite set A (for the sake of contradiction), and then we construct an element x, that was supposed to be in the enumeration but it turns out that it is not. It is crucial to argue that the element x is actually in A, something that is not immediate. C. 1. A' is not recognizable. If it were, there should be a TM M that could say whether any TM M' on any input loops or not. I am challenging you to find such a TM (you cannot actually!). 2. A_TM is a language, that is a set (a collection) of strings. A language does not "have inputs", does not "reject", does not "accept", and does not "loop" -- it's just a set! All of those properties apply to Turing Machines, not to languages. Moreover, we cannot "simulate" a language (actually this expression means nothing). You have to be careful with the terms you are using, otherwise your arguments (proofs) will not be valid (because they become meaningless).