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 . Here is the least upper bound operator on sets of real numbers, also called supremum and denoted sup in real analysis.
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 . (This is in fact equal to .)
Compute . Is a fixpoint of ? Is a fixpoint of ? 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 .)