Differences
This shows you the differences between two versions of the page.
Both sides previous revision Previous revision | Next revision Both sides next revision | ||
sav08:homework10 [2008/04/30 16:10] piskac |
sav08:homework10 [2008/04/30 16:56] vkuncak old revision restored |
||
---|---|---|---|
Line 7: | Line 7: | ||
r = \{ (F_1,F_2) \mid \models F_1 \rightarrow F_2 \} | r = \{ (F_1,F_2) \mid \models F_1 \rightarrow F_2 \} | ||
\] | \] | ||
- | Check whether $r$ is reflexive, antisymmetric, and transitive relation. | + | Check whether $r$ is reflexive, symmetric, and transitive relation. |
===== Problem 2 ===== | ===== 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. | 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 39: | Line 38: | ||
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)$.) | ||
- | Compute $iter(0)$ (if you can, prove that the computed value is correct by definition of $iter$). 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? |
=== Optional part d) === | === 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$.) | 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$.) | ||
- |