Week 5 - Quantifiers and induction

Monday, 18 March 2019

11:05 AM

Machine generated alternative text: This question is about statements with quantifiers V and A and their negations. The set of all integers is denoted by Z. a) Consider the following Statement 1: For every integer x there is an integer zsuch that x < z < 2m. Let us first rewrite this statement using mathematical notation for the sets and quantifiers. Which of the following is a correct formulation of Statement 1? Choose any that apply. 3zez vzez : Azez . < z < 2m . < z < 2m . < z < 2m Submit part You chose a correct answer. You were awarded 1 mark. You scored 1 mark for this part. Score: 1/1 Answered

 

Machine generated alternative text: b) Let x be an integer and consider the following Statement 2: Is Statement 2 correct if x @ yes O no 0? Submit part For x = 0 and z Othe statement is true. You were awarded 1 mark. You scored 1 mark for this part. Score: 1/1 Answered

 

Machine generated alternative text: c) Is there some integer so that Statement 2 in b) is false? If not, enter 0, otherwise give such an integer a; (you will get additional feedback in part d): Submit part Your answer is correct. You were awarded 1 mark. You scored 1 mark for this part. Score: 1/1 Answered

 

Machine generated alternative text: d) In view of your answer to c), is Statement 1 in a) above true? O yes @ no Submit part Statement 1 is indeed incorrect. If x < 2x, then a suitable zso that x < z < 2x is, for example, z x. So for the statement to be incorrect we need •(x < 2x), that is, x > 2:r, which (by subtractingx on both sides) holds if and only if 0 > x. So any negative integer x makes Statement 2 false and is therefore a counterexample to Statement 1. You were awarded 1 mark. You scored 1 mark for this part. Score: 1/1 Answered

 

Machine generated alternative text: We consider the negation of Statement 1 in a). Which of the following is a correct formulation of this negated statement? Choose any that apply. O For every integer there exists an integer z such that z < x or z > 2m. O For every integer zthere exists an integer such that z < x or z > 2m. O There exists an integer a; such that there is an integer zso that z < x or z > 2m. @ There exists an integer a; such that for all integers zwe have z < x orz > 2m. O There exists an integer a; such that for all integers zwe have x > z > 2x. Submit part You chose a correct answer. You were awarded 1 mark. You scored 1 mark for this part. Score: 1/1 Answered

 

Machine generated alternative text: Choose the appropriate proposition for the following English sentences. Also choose whether they are true or false. You must choose two of the five options presented in each row. You may need to scroll over to see all five options. Note also that every wrong answer takes away one from your score. However, your minimum score is 0. vn e Z AX c (IXI = n). (IXI < n) Given an integer n, there is a subset of the natural numbers with n elements. All subsets of the natural numbers have less than a fixed number of elements. Given a real number then some integral power is not negative. True False Submit part You chose a correct answer. You were awarded 0.5 marks. You chose a correct answer. You were awarded 0.5 marks. You chose a correct answer. You were awarded 0.5 marks. You chose a correct answer. You were awarded 0.5 marks. You chose a correct answer. You were awarded 0.5 marks. You chose a correct answer. You were awarded 0.5 marks. You scored 3 marks for this part.

 

Machine generated alternative text: b) (IXI < n) Vn e ax c True For every natural number n there is a subset of with less than n members. The square of any real number is greater than 0. A subset of the natural numbers is a subset of the reals. False Submit part You chose a correct answer. You were awarded 0.5 marks. You chose a correct answer. You were awarded 0.5 marks. You chose a correct answer. You were awarded 0.5 marks. You chose a correct answer. You were awarded 0.5 marks. You chose a correct answer. You were awarded 0.5 marks. You chose a correct answer. You were awarded 0.5 marks. You scored 3 marks for this part. Score: 3/3 Answered

 

Machine generated alternative text: c) Given an integer, then adding 5 to it gives another integer. All subsets of the natural numbers are finite. There is an integer t such that adding 5 to any integer gives t. True (IXI = n). m False Submit part You chose a correct answer. You were awarded 0.5 marks. You chose a correct answer. You were awarded 0.5 marks. You chose a correct answer. You were awarded 0.5 marks. You chose a correct answer. You were awarded 0.5 marks. You chose a correct answer. You were awarded 0.5 marks. You chose a correct answer. You were awarded 0.5 marks. You scored 3 marks for this part. Score: 3/3 Answered

 

Machine generated alternative text: In a seminar group, for group members m and n, we let P (m, n) to be the predicate m knows the name ofn. For each English sentence choose the corresponding proposition involving quantifiers. Note that you will lose one mark for every incorrect choice. However, the minimum mark is 0. a) The numbers heading the columns refer to the following: 4. 3mVn(P(m, n)) Someone's name is known to everyone else. Nobody knows the name of anybody else. Everybody knows at least one other person's name. There is someone who knows everyone's name. 1 O O O 2 O O O 3 O O O 4 O O O Submit part

 

Machine generated alternative text: b) The numbers heading the columns refer to the following: There is a pair of group members who do not know each other's name. Every group member doesn't know the name of at least one other. There is someone not known to the rest. There is at least one person who knows the name of somebody else. 1 O O O 2 O O O 3 O O O 4 O O O Submit part You chose a correct answer. You were awarded 0.25 marks. You chose a correct answer. You were awarded 0.25 marks. You chose a correct answer. You were awarded 0.25 marks. You chose a correct answer. You were awarded 0.25 marks. You scored 1 mark for this part. Score: 1/1 Answered

 

Machine generated alternative text: c) The numbers heading the columns refer to the following: Any member of the group has at least one person who doesn't know their name. There are at least two people who know each other's name. There is at least one person who does not know the name of anybody else. There is someone who doesn't know the name of at least one other group member. 1 O O O 2 O O O 3 O O O 4 O O O Submit part You chose a correct answer. You were awarded 0.25 marks. You chose a correct answer. You were awarded 0.25 marks. You chose a correct answer. You were awarded 0.25 marks. You chose a correct answer. You were awarded 0.25 marks. You scored 1 mark for this part. Score: 1/1 Answered

 

Machine generated alternative text: In a seminar group, for group members m and n, we let P (m, n) be the predicate m knows thenameofn. Negate each of the following English sentences and choose the corresponding expression for the negated proposition involving quantifiers. Note that you will lose one mark for every incorrect choice. However, the minimum mark is 0. a) If you want some help in answering this question click on Show steps. You will lose a mark as one of the questions is answered for you. (You will lose 1 mark.) Show steps Everybody knows at least one other person's name. There is at least one person who knows the name of somebody else. Nobody knows the name of anybody else. There is someone whose name is not known to the rest of the group. O O O Vm3n(P(n, m)) O O O O O O O O O Submit part You chose a correct answer. You were awarded 0.25 marks. You chose a correct answer. You were awarded 0.25 marks. You chose a correct answer. You were awarded 0.25 marks. You chose a correct answer. You were awarded 0.25 marks. You scored 1 mark for this part.

 

Machine generated alternative text: b) ArnVn(P(m, n)) There is a pair of group members who do not O know each other's name. There is someone who knows everyone's O name. Every group member doesn't know the name of at least one other. There is someone who doesn't know the O name of at least one other group member. VmVn(P(m, n) V P (n, m)) O O O O O O VmVn(P(n, m)) O O O Submit part You chose a correct answer. You were awarded 0.25 marks. You chose a correct answer. You were awarded 0.25 marks. You chose a correct answer. You were awarded 0.25 marks. You chose a correct answer. You were awarded 0.25 marks. You scored 1 mark for this part. Score: 1/1 Answered

 

Machine generated alternative text: c) There is at least one person who does not O know the name of anybody else. There are at least two people who know O each other's name. Someone's name is known to everyone Any member of the group has at least one O person who doesn't know their name. Vm3n(P(m, n)) O O O O O O O O O Submit part You chose a correct answer. You were awarded 0.25 marks. You chose a correct answer. You were awarded 0.25 marks. You chose a correct answer. You were awarded 0.25 marks. You chose a correct answer. You were awarded 0.25 marks. You scored 1 mark for this part. Score: 1/1 Answered

 

Machine generated alternative text: Mathematical induction is a style of proof consisting of a base case and inductive step. Informally, the base case is the foundation of the proof and the inductive step is used to build the rest of the proof. For example, let's prove that 1 + 2 + + n s(n) where a) Base case: first show that s(l) 1 Submit part Gap 1 Your answer is correct. You were awarded 1 mark. You scored 1 mark for this part. Score: 1/1 Answered

 

Machine generated alternative text: b) Induction step: assume that 1 + + n = s(n), and then use this assumption to prove that 1 + s(l). By the inductive step, if 1 s(l) then 1 + 2 s(2). By a further inductive step, if 1 + 2 Initially we know only the base case 1 then 1 + 2 + 3 = s(3). By repeating the inductive step, we prove that 1 —n(n + 1) for all integers n 1. 2 Submit part Gap 1 Your answer is numerically correct. You were awarded 1 mark. You scored 1 mark forthis part. Score: 1/1 Answered

 

Machine generated alternative text: uo, UI, to, defined by Prove by strong induction that f(n) a) Prove the base case: Strong induction is the name given to induction that makes more assumptions in the inductive step. Consider the sequence of numbers x 51 —1 ¯ 17 45un—2 forn 2. f(0) = f(l) = —3 —3 x x 90 91 x 50 -1 -17 Submit part Gap 1 Your answer is correct. You were awarded 0.5 marks. Gap 2 Your answer is correct. You were awarded 0.5 marks. You scored 1 mark for this part. Score: 1/1 Answered

 

Machine generated alternative text: b) Induction step: Assume for each integer 2 < k < n that: Uk 2*5Ak 3*9Ak 2 X 5 Using the assumptions that you just made, show that f (n + 1) = un+l. That is: 14un — 45un—1 ¯ un+l — 14 (2 X —3 X W) —45 (2 X 1 -45* (2*5A (n-l) -3*9A (n-l) ) Gap 1 Submit part Your answer is numerically correct. You were awarded 1 mark. Gap 2 Your answer is numerically correct. You were awarded 1 mark. You scored 2 marks for this part. Score: 2/2 Answered

 

Machine generated alternative text: c) The base case gives thatuo = f(0) and UI = f(l). The first iteration of the induction step uses these assumptions to proveu2 = f(2). A second iteration uses proves that f(3) — and so on. Hence f (n) = un forevey integer n 0.

 

 

Created with Microsoft OneNote 2016.