York University
Department of Electrical Engineering and Computer Science
Lassonde School of Engineering
EECS1028M FINAL EXAM, April 27, 2022; 2:00–4:00PM
SOLUTIONS
Professor George Tourlakis
Question 1. (a) (1 MARK) What does Principle 2 state?
Answer. “Every state has some state following it”.
(b) (1 MARK) Define “labelling” of the members of a class A —where the legal labels are
the members of a set L.
Answer. “A Labelling of the members of A from L is the assignment (say, as sub-
scripts) of members of L to each member of A so that we never assign the same label
to any two distinct members of A”.
(c) (2 MARK) State Principle 3.
Answer. “If A has a labelling from a set L, then A is itself a set”.
, EECS 1028 M FINAL EXAM April 2022
Question 2. (a) (2 MARKS ) Let < be an arbitrary order.
Translate in MATHEMATICAL language the quoted statement: “< has MC”.
Definition. < has MC iff every nonempty class A has an <-minimal member a. In
symbols:
“< has MC iff every nonempty class A has some a ∈ A such that NO b ∈ A satisfies b < a”.
Or (this formulation is not required), totally in symbols,
A ̸= ∅ → (∃a ∈ A)A ∩ (a) > = ∅
(b) (2 MARKS ) Does the usual < on the integers Z = {. . . , −2, −1, 0, 1, 2, . . .} have MC?
Justify your answer.
Answer. No. For example, Z ̸= ∅, yet, for any k ∈ Z, we have Z ∋ k − 1 < k.
(c) (5 MARKS) Now suppose that some < —which is NOT THE USUAL ONE on N—
indeed has MC.
Prove that there is NO infinite (enumerable) sequence of objects ai —these are NOT
NECESSARILY NUMBERS— for which the “infinite descending (by size) chain” below
represents a true statement about the ai :
. . . < ai+1 < ai < . . . < a2 < a1 < a0 (1)
Hint. If we do have the truth of (1) for some “well-chosen” ai , then consider the set
B = {. . . , ai+1 , ai , . . . , a2 , a1 , a0 } (2)
and take it from here.
WHY is (2) a “SET”?
Proof. Per Hint, consider the class B in (2) above. We assumed we have the chain (1) so the
ai ’s are no fiction: B ̸= ∅. Take any b ∈ B. This is, say, b = ak .
Now ak+1 < b, so b cannot be minimal. As b was arbitrary in B, we contradicted that < has
MC.
Incidentally, by Principle 3, B is a set, but we do not need this fact in the proof.
2
Department of Electrical Engineering and Computer Science
Lassonde School of Engineering
EECS1028M FINAL EXAM, April 27, 2022; 2:00–4:00PM
SOLUTIONS
Professor George Tourlakis
Question 1. (a) (1 MARK) What does Principle 2 state?
Answer. “Every state has some state following it”.
(b) (1 MARK) Define “labelling” of the members of a class A —where the legal labels are
the members of a set L.
Answer. “A Labelling of the members of A from L is the assignment (say, as sub-
scripts) of members of L to each member of A so that we never assign the same label
to any two distinct members of A”.
(c) (2 MARK) State Principle 3.
Answer. “If A has a labelling from a set L, then A is itself a set”.
, EECS 1028 M FINAL EXAM April 2022
Question 2. (a) (2 MARKS ) Let < be an arbitrary order.
Translate in MATHEMATICAL language the quoted statement: “< has MC”.
Definition. < has MC iff every nonempty class A has an <-minimal member a. In
symbols:
“< has MC iff every nonempty class A has some a ∈ A such that NO b ∈ A satisfies b < a”.
Or (this formulation is not required), totally in symbols,
A ̸= ∅ → (∃a ∈ A)A ∩ (a) > = ∅
(b) (2 MARKS ) Does the usual < on the integers Z = {. . . , −2, −1, 0, 1, 2, . . .} have MC?
Justify your answer.
Answer. No. For example, Z ̸= ∅, yet, for any k ∈ Z, we have Z ∋ k − 1 < k.
(c) (5 MARKS) Now suppose that some < —which is NOT THE USUAL ONE on N—
indeed has MC.
Prove that there is NO infinite (enumerable) sequence of objects ai —these are NOT
NECESSARILY NUMBERS— for which the “infinite descending (by size) chain” below
represents a true statement about the ai :
. . . < ai+1 < ai < . . . < a2 < a1 < a0 (1)
Hint. If we do have the truth of (1) for some “well-chosen” ai , then consider the set
B = {. . . , ai+1 , ai , . . . , a2 , a1 , a0 } (2)
and take it from here.
WHY is (2) a “SET”?
Proof. Per Hint, consider the class B in (2) above. We assumed we have the chain (1) so the
ai ’s are no fiction: B ̸= ∅. Take any b ∈ B. This is, say, b = ak .
Now ak+1 < b, so b cannot be minimal. As b was arbitrary in B, we contradicted that < has
MC.
Incidentally, by Principle 3, B is a set, but we do not need this fact in the proof.
2
