Differences
This shows you the differences between two versions of the page.
|
sav08:homework10 [2008/04/30 16:56] vkuncak |
sav08:homework10 [2015/04/21 17:30] |
||
|---|---|---|---|
| Line 1: | Line 1: | ||
| - | ====== Homework 10, Due May 7th ====== | ||
| - | ===== Problem 1 ===== | ||
| - | |||
| - | Let ${\cal F}$ be the set of all first-order formulas (viewed as syntax trees) and let $r$ be the implication relation on formulas: | ||
| - | \[ | ||
| - | r = \{ (F_1,F_2) \mid \models F_1 \rightarrow F_2 \} | ||
| - | \] | ||
| - | Check whether $r$ is reflexive, antisymmetric, and transitive relation. | ||
| - | |||
| - | ===== Problem 2 ===== | ||
| - | |||
| - | Let $(A,\sqsubseteq)$ be a [[:partial order]] such that every set $S \subseteq A$ has the greatest lower bound. Prove that then every set $S \subseteq A$ has the least upper bound. | ||
| - | ===== Problem 3 ===== | ||
| - | |||
| - | Let $A = [0,1] = \{ x \in \mathbb{R} \mid 0 \le x \le 1 \}$ be the interval of real numbers. Recall that, by definition of real numbers and complete lattice, $(A,\le)$ is a complete lattice with least lattice element $0$ and greatest lattice element $1$. Here $\sqcup$ is the least upper bound operator on sets of real numbers, also called //supremum// and denoted //sup// in real analysis. | ||
| - | |||
| - | Let function $f : A \to A$ 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 $f$.) | ||
| - | |||
| - | === Part a) === | ||
| - | |||
| - | Prove that $f$ is monotonic and injective (so it is strictly monotonic). | ||
| - | |||
| - | === Part b) === | ||
| - | |||
| - | Compute the set of fixpoints of $f$. | ||
| - | |||
| - | === Part c) === | ||
| - | |||
| - | Define $iter(x) = \sqcup \{ f^n(x) \mid n \in \{0,1,2,\ldots \}\}$. (This is in fact equal to $\lim_{n\to\infty} f^n(x)$.) | ||
| - | |||
| - | Compute $iter(0)$ (prove that the computed value is correct by definition of $iter$, that is, that the value is indeed $\sqcup$ of the set of values). Is $iter(0)$ a fixpoint of $f$? Is $iter(iter(0))$ a fixpoint of $f$? Is $f$ an $\omega$-continuous function? | ||
| - | |||
| - | === Optional part d) === | ||
| - | |||
| - | Define a monotonic function $f : A \to A$ such that, for every natural number $k$, the value $iter^k(0)$ is not a fixpoint of $f$. (It may be difficult to draw $f$.) | ||