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
.)