Introduction to Mathematical Thinking. Tutorial for Assignment 1. Prove or disprove the statement “ All birds can fly. “ False. Counterexample. Ostrich Starting with the premise that all birds can fly, we will prove or disprove thisstatement by finding a counter-example. An obvious one is the ostrich, which cannotfly. 2. Prove or disprove the claim (∀𝑥, 𝑦ϵ𝑅)[(𝑥 − 𝑦) 2 > 0] False. Counterexample. 𝑥 = 𝑦 = 1. (𝑥 − 𝑦) 2 = 0 To prove that all x in r, for all x and y in r, x minus y squared is greater than 0 is false,one must find a counter example. A counter example could be any pair of equalnumbers. We will give a specific counter example by taking x equals y equals 1. Inthis case, x minus y squared equals 0 and 0 is not strictly based on 0 (it came close).If we excluded the cases when x or y was 0 then we would have a positive result, butit says that it's true for all values of r not just one value, so any pair of equal numbersgives us a counterexample. 3. Prove that between any two unequal rationals there is a third rational. 𝐿𝑒𝑡 𝑥, 𝑦 ϵ 𝑄, 𝑥 = 𝑦. 𝑇ℎ𝑒𝑛 𝑥 = 𝑝𝑞 , 𝑦 = 𝑟𝑠 , 𝑤ℎ𝑒𝑟𝑒 𝑝, 𝑞, 𝑟, 𝑠 ϵ 𝑍 𝑇ℎ𝑒𝑛 𝑥+𝑦 2 = 𝑝/𝑞+𝑟/𝑠 2 = 𝑝𝑠+𝑞𝑟 𝑞𝑠 2 = 𝑝𝑠+𝑞𝑟 2𝑞𝑠 ϵ𝑄 𝑅𝑢𝑡 𝑥 < 𝑥+𝑦 2 < 𝑦. The third way is to prove that between any two unequal rational numbers there is athird. Let x and y be unequal rational numbers, with x less than y. Then because theyare rational numbers, x is p/q and y is r/s where p, q, r, and s are integers. We mustshow that there is a number between them; let’s call this number x plus y over 2. Ifthis number is a rational number then we have shown our result; but here is a proofthat it is indeed rational: x plus y over 2 = p/q + r/s over qs/2 = ps + qr over 2 = (ps +qr)/2 = rational since it is the quotient of 2 integers. 7. Prove that is irrational. 3 Prove it by contradiction. Assume were rational. 3 Then , where p, q є N, with no common factors. 3 = 𝑝𝑞 Then . 3 = 𝑝 2 /𝑞 2 So 3𝑞 2 = 𝑝 2 So 3|𝑝 2
But 3 is primeSo 3|pSo p=3r So 𝑝 2 = 9𝑟 2 So 3𝑞 2 = 𝑝 2 = 9𝑟 2 So 𝑞 2 = 3𝑟 2 So 3|𝑞 2 So 3|qContradiction, since p,q have no factors.ct proov p is even = 2|p 𝑓𝑛 2 We will prove it by contradiction. We assume the square root of 3 is rational; that is, itcan be expressed as a fraction p/q where p and q are natural numbers with nocommon factors. If that were true, then we would have 3 = p2/q2. Canceling out anycommon factors on both sides gives us 3 = p2. Let us multiply 3 times q squared. Wewill get 3q squared, which means p squared equals 3q squared. Since 3 is prime,and since a prime number divides any product of two numbers, the prime number 3must divide one of these numbers. This means p is divisible by 3, or in other words,it can be written as 3r. So, if p is any number, then p squared equals nine times rsquared. We can take p squared and substitute it back in here to get 3q squaredequals p squared, equals nine times r squared. So if we forget the middle term now,3q squared equals 9r squared. So if we divide both sides of this equation by 3, we'llget q squared equals three times r squared, so that means three divides q. Now wehave an inconsistency since p and q have no common factors. Yet we just showedthat 3 is a common factor. So there is a contradiction. Just as with the proof ofsquare root of 2, if we consider that p is even, then that's just another way of saying2 divides p. The proof that we have just seen for , the one in terms of even and odd,could be restated in terms of divisibility by three. The fact that 2 is prime is used inthis proof as well. The only difference between this proof and the previous one is thatwe only use the fact that 2 is prime instead of 3. 1. Yes, suppose r+3 were rational. Then 𝑟 + 3 = 𝑝𝑞 where p, q, є Z. Then 𝑟 = 𝑝𝑞 − 3 = 𝑝−3𝑞 𝑞 ∈ 𝑄 ContraditionalOther similar . 8. Write down the converses of the following conditional statements: (a) If Dollar falls, the Yuan will rise If the Yuan rises, the Dollar falls. (b) If x<y then -y<-x (For x,y real numbers) ← 𝑇 If -y<-x, then x<y ← 𝑇 (с) If two triangles are congruent they have the same area. ← 𝑇
If two triangles have the same area, then they are arguments. ← 𝐹 The converse of a conditional statement is true only when the antecedent is false. Ifwe swap the antecedent and consequent in a conditional statement and change thetruth value of that statement, then we get its converse. For example, if the Yuanrises, then the dollar falls. The opposite case—if the dollar falls then the Yuanrises—is also true, reflecting the fact that these are two sides to the same coin. Inthis example, if x is less than y, then y must be greater than x; likewise if twotriangles have equal areas, then they are congruent to each other. This exercise isintended to contrast it with the contrapositive. Also, we want to observe that truth andfalsity can change. In this case,we start out with something that's true - two trianglesare congruent if and only if they have the same area. The converse of a trueimplication is also true: If two triangles are congruent, then they have the same area.It is true that if two triangles have the same area, they are congruent. It is false that iftwo triangles have different areas, they are not congruent. Sometimes the converseof a true statement can be false and sometimes it can be true. The situation with thecontrapositive is different because when you swap around the order you cansometimes get through going to false and you can sometimes reserve truth. 11. Let r, s be irrationals. For each of the following, say whether the givennumber is necessarily irrational, and prove your answer. 1. r+3 2. 5r 3. r+3 4. rs 5. 6. 𝑟 𝑟 2 That was the topic of irrational numbers in the lecture. We saw that some of theseare rational. We saw that this one can be rational, and there is an issue about thisone being rational. Those were easy, so let's move on to the more complicated stuff.If we assume that r plus 3 is rational, it can be written as p over q, where p and q areintegers. However, if r equals p over q minus 3, then r must be rational and thiscontradicts the assumption that r is irrational. In each of these examples, we assumecontinuity by expressing it in terms of p over q, manipulate a bit and end up showingthat r is rational in the square root example. 12. Let m and n be integers. Prove that: (a) If m and n are even, then m+n is even.(b) If m and n are even, then mn is divisible by 4.(с) If m and n are odd, then m+n is even.(d) If one of m,n is even and the other is odd, then m+n is odd.(e) If one of m, n is even and the other is odd, then mn is even. Key facts: n even iff n=2k, some k n add iff n=2k+1, some k
(a) m=2k, n=2l, m+n=2k+2l=2(k+l)(d) m=2k, n=2l+1, m+n=2k+(2l+1)=2(k+l)+1etc. The key facts to keep in mind when dealing with the even and odd numbers are thatif n is even, then n is a multiple of 2 (whereas if n is odd, then n equals 2k + 1 forsome integer k). The even numbers are therefore the multiples of 2, whereas the oddnumbers are those that are 1 more than a multiple of 2. Between multiples of two, we can see that m is even if m is twice k and n is twice l.So for example, if m equals 2k, then n will be 2l. (Or vice versa.) This means that mplus n equals 2(2k) + 2(2l). If you put this into a calculator and press the equal sign,you'll find that it's 4 times something else. If one of the numbers is even, then it's twice that number plus 1. The other number isodd: it's equal to 2 times the first number plus 1. That works for all of them. We cando a tiny bit of algebra at this point, if we want to. The rest of this assignment is fairlystraightforward; however, if you have not encountered proofs like this before in yourstudies, then they will likely be challenging.