1028-FINAL-2023-SOL

pdf

School

York University *

*We aren’t endorsed by this school

Course

1028

Subject

Electrical Engineering

Date

Oct 30, 2023

Type

pdf

Pages

Uploaded by PresidentInternet8539

York University Department of Electrical Engineering and Computer Science Lassonde School of Engineering EECS1028M FINAL EXAM , April 12, 2023; 7:00–9:00PM Professor George Tourlakis Question 1. (a) (1 MARK) Define precisely the term “ labelling ” of the members of a class A —where the legal labels are the members of a set L . Answer . Labelling assigns labels to EACH member of class A from SET L as follows. At the end of the process : • No member of A stays unlabelled. • No member of A gets the same label twice (or more). • No TWO distinct members of A get the SAME label. (b) (2 MARKS) State Principle 3 . Answer . If a class A has a labelling from a SET L , then it is a set.

EECS 1028 M FINAL EXAM —Solutions April 2023 Question 2. (a) (2 MARKS ) Does the usual < on the Integers Z have MC? Justify your answer . Answer . An order < has MC (minimal condition) iff each nonempty class A has an < -minimal element. < on Z does NOT have MC. For example, Z is a set that has no < -minimal member. (b) (5 MARKS) Now suppose that some order R has MC. Prove that there is NO infinite (enumerable) sequence of objects a i in the Field of R , for which the “infinite descending (from low to high subscripts) chain” below represents a true statement about the set of the a i : . . . R a i +1 R a i R . . . R a 2 R a 1 R a 0 (1) Hint . If we do have the truth of (1), then consider the set { . . . , a i +1 , a i , . . . , a 2 , a 1 , a 0 } (2) also the assumption at the onset of (b), and take it from here. Be sure to elaborate WHY is (2) a “SET”? Proof . (a) (2) is a set because —by assumption— it has an enumeration using N as the label-SET. (b) Prove that (2) is a nonempty SET with no R -minimal members: For any a i , the member a i +1 is below it —i.e., a i +1 R a i — if we imagine walking backwards along R (imagine the intuitively obvious case of < on numbers). NOTE that a minimal member of (2) — say a k — ought to satisfy that no member b of (2) satisfies b R a k ; not true as we noted ( b = a k +1 so satisfies!). This contradicts —given that R DOES have MC— the existence of (1) and (2). 2

EECS 1028 M FINAL EXAM —Solutions April 2023 Question 3. (4 MARKS) Prove that a set is countable iff it is one of 1) finite, or 2) enumerable. Be mathematically precise! Proof . Two directions. (a) ( → ) So let A be countable. Then there is —by definition— an ONTO f : N → A that is NOT necessarily total! Now A IS either finite or is NOT. Cases: • ( A finite). Nothing else to say. Done in this case! • ( A infinite). Then, by a theorem from Class/Notes (5.2.15), A —being countable— is enumerable. Done in this case too! (b) ( ← ) Here we are told that we have to prove A is countable under two cases: • ( A is finite) Then (Def of “finite”) we have a ∼ via some f : { 0 , . . . , n } → A . But then the function g : N → A given by g ( k ) = ( f ( k ) if 1 ≤ k ≤ n ↑ othw is onto, and A is countable be Def of “countable”. • ( A is enumerable) Then (Def of “enumerable”) we have a ∼ via some f : N → A . By def of ∼ this is onto A so this set is countable by Def of “countable”. 3

Your preview ends here

Eager to read complete document? Join bartleby learn and gain access to the full version

Access to all documents
Unlimited textbook solutions
24/7 expert homework help

EECS 1028 M FINAL EXAM —Solutions April 2023 Question 4. (4 MARKS) Say A is enumerable and an enumeration a 0 , a 1 , a 2 , . . . (1) is given. Prove that you can find an enumeration that repeats every a i infinitely often . Answer . This is easy. Form an infinite matrix ( ∞ × ∞ ) of which EVERY row is a copy of (1) above a 0 a 1 a 2 . . . a 0 a 1 a 2 . . . a 0 a 1 a 2 . . . . . . . . . . . . . . . Traverse the matrix in NE manner to obtain a “linear” (1-dimensional) array just as we “linearised” N × N in the notes. It is trivial that EACH a i —once it appears in a “NE diagonal”— it will appear also in EACH subsequent “NE diagonal”, so it is enumerated infinitely many times. 4

EECS 1028 M FINAL EXAM —Solutions April 2023 Question 5. (4 MARKS) Prove that if A is uncountable and a / ∈ A , then A ∪ { a } is also uncountable . Proof . So let A ∪ { a } NOT be uncountable. By definition then it is countable. Say f : N → A ∪ { a } be an onto function (an enumeration). Define g : N → A by g ( x ) = ( f ( x ) if f ( x ) 6 = a ↑ othw So g enumerates everything except a , that is, it is onto A . By Def, A is countable. Contra- diction to assumption. 5

EECS 1028 M FINAL EXAM —Solutions April 2023 Question 6. (4 MARKS) Prove ‘ ( ∃ x )( A → B ) → ( ∀ x ) A → ( ∃ x ) B . Proof . By DThm suffices to prove ( ∃ x )( A → B ) ‘ ( ∀ x ) A → ( ∃ x ) B instead. Ditto, suffices to prove ( ∃ x )( A → B ) , ( ∀ x ) A ‘ ( ∃ x ) B instead. 1) ( ∃ x )( A [ x ] → B [ x ]) h Dthm hyp i 2) ( ∀ x ) A [ x ] h Dthm hyp i 3) A [ c ] → B [ c ] h aux. hyp for line 1; c a NEW constant not in the conclusion i 4) A [ c ] h 2 + Spec i 5) B [ c ] h 3 + 4 + Post i 6) ( ∃ x ) B [ x ] h 6 + Dual Spec i 6

Your preview ends here

Eager to read complete document? Join bartleby learn and gain access to the full version

Access to all documents
Unlimited textbook solutions
24/7 expert homework help

EECS 1028 M FINAL EXAM —Solutions April 2023 Question 7. (4 MARKS) Use induction to prove that n X i =1 (3 i - 2) = (3 n 2 - n ) / 2 (1) Proof . Since the index i starts at 1, this is to be proved for n ≥ 1. Basis . n = 1. lhs = 3(1) - 2 = 1. rhs = (3(1) 2 - 1) / 2 = 2 / 2 = 1. We are good! I.H. Assume (1) for fixed unspecified n ≥ 1. I.S. n +1 X i =1 (3 i - 2) = I.H. z }| { 3 n 2 - n 2 + ( n +1) st term z }| { 3( n + 1) - 2 arithmetic = 3 n 2 - n + 6 n + 2 2 arithmetic = 3[ n 2 + 2 n + 1] - ( n + 1) 2 arithmetic = 3[ n + 1] 2 - ( n + 1) 2 7

EECS 1028 M FINAL EXAM —Solutions April 2023 Question 8. (4 MARKS) Use induction to prove that n X i =1 1 (4 i - 3)(4 i + 1) = n 4 n + 1 (1) Proof . The index i starts at 1, thus the claim is for n ≥ 1. Basis . n = 1. lhs = 1 (4(1) - 3)(4(1) + 1) = 1 / ((1)(5)) = 1 / 5. rhs = 1 4(1) + 1 = 1 / 5. Good! I.H. Assume (1) for fixed unspecified n . I.S. n +1 X i =1 1 (4 i - 3)(4 i + 1) = I.H. z }| { n 4 n + 1 + ( n +1) st term z }| { 1 (4 n + 1)(4 n + 5) arithmetic = 1 4 n + 1 n + 1 4 n + 5 arithmetic = 1 4 n + 1 4 n 2 + 5 n + 1 4 n + 5 arithmetic = 1 4 n + 1 (4 n + 1)( n + 1) 4 n + 5 arithmetic = n + 1 4 n + 5 = n + 1 4( n + 1) + 1 8