Problem 0: Complete the Canvas quiz "PSet 11 - Relations and Graphs".

Problem (12 points): Let $R$ be any partial order relation on a non-empty finite set $S$.

• Prove that there is at least one minimal element in $S$ with respect to $R$.
• Prove that if there is a greatest element in $S$ with respect to $R$, then that element is unique.

Problem (6 points): Let $R$ be any partial order relation on an infinite set $S$.

• Prove or give a counterexample to the following statement: there is at least one minimal element in $S$ with respect to $R$.
• Prove or give a counterexample to the following statement: if there is a greatest element in $S$ with respect to $R$, then that element is unique.

Problem (8 points): A full binary tree is a rooted tree in which every node as 0 or 2 children. A leaf is a node with no children. An internal node is a node that is not a leaf. Prove by induction that the number of leaves in a full binary tree is one more than the number of internal nodes. (There are ways to prove this without induction, but the point of this problem is to practice structural induction. So we will take "prove by induction" to mean "write a proof in which you make use of the relationship between what the inductive hypothesis says something about and what the induction step needs to prove something about.")