This is an old revision of the document!
Homework 10, Due May 7th
Problem 1
Let be the set of all first-order formulas (viewed as syntax trees) and let be the implication relation on formulas: \[
r = \{ (F_1,F_2) \mid \models F_1 \rightarrow F_2 \}
\] Check whether is reflexive, symmetric, and transitive relation.
Problem 2
Let be a partial order such that every set has the greatest lower bound. Prove that then every set has the least upper bound.
Problem 3
Let be the interval of real numbers. Recall that, by definition of real numbers and complete lattice, is a complete lattice with least lattice element and greatest lattice element .
Let function be given by \[
f(x) = \left\{\begin{array}{l}
\frac{1}{2} + \frac{1}{4}x, \mbox{ if } x \in [0,\frac{2}{3}) \frac{3}{5} + \frac{1}{5}x, \mbox{ if } x \in [\frac{2}{3},1] \end{array}\right. \] (It may help you to try to draw .)
Part a)
Prove that is monotonic.
Part b)
Compute the set of fixpoints of .
Part c)
Define where is the least uppser bound operator on sets of real numbers (also called 'supremum' and denoted 'sup', and in this case equal to ).
Compute . Is a fixpoint? Compute . Is an -continuous function?
Optional part d)
Define a monotonic function such that, for every natural number , the value is not a fixpoint of . (It may be difficult to draw .)