Chapter 5: Q31E (page 358)
Define well-formed formulae of sets, variables representing sets, and operators from .
If X is a variable representing a set, then X is a well-formed formula.
If X is a set, then X is a well-formed formula.
If X and are well-formed formulae, then are well-formed formulae.
Over 30 million students worldwide already upgrade their learning with Vaia!
All the tools & learning materials you need for study success - in one app.
Get started for free
Let P(n) be the statement that , where n is an integer greater than 1.
a) What is the statement P(2)?
b) Show that P(2) is true, completing the basis step of the proof.
c) What is the inductive hypothesis?
d) What do you need to prove in the inductive step?
e) Complete the inductive step.
f) Explain why these steps show that this inequality is true whenever n is an integer greater than 1.
Prove that a set with n elements has subsets containing exactly three elements whenever n is an integer greater than or equal to 3.
Prove that whenever nis a nonnegative integer
In the proof of Lemma 1 we mentioned that many incorrect methods for finding a vertex such that the line segment is an interior diagonal of have been published. This exercise presents some of the incorrect ways has been chosen in these proofs. Show, by considering one of the polygons drawn here, that for each of these choices of , the line segment is not necessarily an interior diagonal of .
a) p is the vertex of P such that the angleis smallest.
b) p is the vertex of P with the least -coordinate (other than ).
c) p is the vertex of P that is closest to .
A stable assignment, defined in the preamble to Exercise 60 in Section 3.1, is called optimal for suitors if no stable assignment exists in which a suitor is paired with a suitee whom this suitor prefers to the person to whom this suitor is paired in this stable assignment. Use strong induction to show that the deferred acceptance algorithm produces a stable assignment that is optimal for suitors.
What do you think about this solution?
We value your feedback to improve our textbook solutions.
