• English only

# 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] (current) Both sides previous revision Previous revision 2008/04/30 17:01 vkuncak 2008/04/30 16:56 vkuncak 2008/04/30 16:56 vkuncak old revision restored2008/04/30 16:10 piskac 2008/04/30 16:02 vkuncak 2008/04/30 15:57 vkuncak 2008/04/30 15:56 vkuncak 2008/04/30 15:55 vkuncak 2008/04/30 15:54 vkuncak 2008/04/30 15:54 vkuncak 2008/04/30 15:54 vkuncak 2008/04/30 15:54 vkuncak 2008/04/30 15:53 vkuncak 2008/04/30 15:48 vkuncak 2008/04/30 15:48 vkuncak 2008/04/30 15:47 vkuncak 2008/04/30 15:27 vkuncak 2008/04/30 15:20 vkuncak 2008/04/30 15:19 vkuncak 2008/04/30 15:16 vkuncak created Next revision Previous revision 2008/04/30 17:01 vkuncak 2008/04/30 16:56 vkuncak 2008/04/30 16:56 vkuncak old revision restored2008/04/30 16:10 piskac 2008/04/30 16:02 vkuncak 2008/04/30 15:57 vkuncak 2008/04/30 15:56 vkuncak 2008/04/30 15:55 vkuncak 2008/04/30 15:54 vkuncak 2008/04/30 15:54 vkuncak 2008/04/30 15:54 vkuncak 2008/04/30 15:54 vkuncak 2008/04/30 15:53 vkuncak 2008/04/30 15:48 vkuncak 2008/04/30 15:48 vkuncak 2008/04/30 15:47 vkuncak 2008/04/30 15:27 vkuncak 2008/04/30 15:20 vkuncak 2008/04/30 15:19 vkuncak 2008/04/30 15:16 vkuncak created Line 4: Line 4: Let ${\cal F}$ be the set of all first-order formulas (viewed as syntax trees) and let $r$ be the implication relation on formulas: Let ${\cal F}$ be the set of all first-order formulas (viewed as syntax trees) and let $r$ be the implication relation on formulas: - $+ \begin{equation*} r = \{ (F_1,F_2) \mid \models F_1 \rightarrow F_2 \} r = \{ (F_1,F_2) \mid \models F_1 \rightarrow F_2 \} -$ + \end{equation*} Check whether $r$ is reflexive, antisymmetric,​ and transitive relation. Check whether $r$ is reflexive, antisymmetric,​ and transitive relation. Line 12: Line 12: 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. 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 ===== ===== Problem 3 ===== Line 17: Line 18: Let function $f : A \to A$ be given by Let function $f : A \to A$ be given by - $+ \begin{equation*} f(x) = \left\{\begin{array}{l} f(x) = \left\{\begin{array}{l} \frac{1}{2} + \frac{1}{4}x,​ \mbox{ if } x \in [0,​\frac{2}{3}) \\ \frac{1}{2} + \frac{1}{4}x,​ \mbox{ if } x \in [0,​\frac{2}{3}) \\ Line 23: Line 24: \frac{3}{5} + \frac{1}{5}x,​ \mbox{ if } x \in [\frac{2}{3},​1] \frac{3}{5} + \frac{1}{5}x,​ \mbox{ if } x \in [\frac{2}{3},​1] \end{array}\right. \end{array}\right. -$ + \end{equation*} (It may help you to try to draw $f$.) (It may help you to try to draw $f$.) Line 36: Line 37: === Part c) === === 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)$.) + 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)$ ​when $f$ is a monotonic bounded function.) 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? 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? 