Set Theory And Logic

2007

• 1.II.16G

  Set Theory and Logic | Part II, 2007

  By a directed set in a poset $(P, \leqslant)$, we mean a nonempty subset $D$ such that any pair $\{x, y\}$ of elements of $D$ has an upper bound in $D$. We say $(P, \leqslant)$ is directed-complete if each directed subset $D \subseteq P$ has a least upper bound in $P$. Show that a poset is complete if and only if it is directed-complete and has joins for all its finite subsets. Show also that, for any two sets $A$ and $B$, the set $[A>B]$ of partial functions from $A$ to $B$, ordered by extension, is directed-complete.

  Let $(P, \leqslant)$ be a directed-complete poset, and $f: P \rightarrow P$ an order-preserving map which is inflationary, i.e. satisfies $x \leqslant f(x)$ for all $x \in P$. We define a subset $C \subseteq P$ to be closed if it satisfies $(x \in C) \rightarrow(f(x) \in C)$, and is also closed under joins of directed sets (i.e., $D \subseteq C$ and $D$ directed imply $\bigvee D \in C$ ). We write $x \ll y$ to mean that every closed set containing $x$ also contains $y$. Show that $\ll$ is a partial order on $P$, and that $x \ll y$ implies $x \leqslant y$. Now consider the set $H$ of all functions $h: P \rightarrow P$ which are order-preserving and satisfy $x \ll h(x)$ for all $x$. Show that $H$ is closed under composition of functions, and deduce that, for each $x \in P$, the set $H_{x}=\{h(x) \mid h \in H\}$ is directed. Defining $h_{0}(x)=V H_{x}$ for each $x$, show that the function $h_{0}$ belongs to $H$, and deduce that $h_{0}(x)$ is the least fixed point of $f$ lying above $x$, for each $x \in P$.

  comment

• 2.II.16G

  Set Theory and Logic | Part II, 2007

  Explain carefully what is meant by a deduction in the propositional calculus. State the completeness theorem for the propositional calculus, and deduce the compactness theorem.

  Let $P, Q, R$ be three pairwise-disjoint sets of primitive propositions, and suppose given compound propositions $s \in \mathcal{L}(P \cup Q)$ and $t \in \mathcal{L}(Q \cup R)$ such that $(s \vdash t)$ holds. Let $U$ denote the set

  $$\{u \in \mathcal{L}(Q) \mid(s \vdash u)\} .$$

  If $v: Q \rightarrow 2$ is any valuation making all the propositions in $U$ true, show that the set

  $$\{s\} \cup\{q \mid q \in Q, v(q)=1\} \cup\{\neg q \mid q \in Q, v(q)=0\}$$

  is consistent. Deduce that $U \cup\{\neg t\}$ is inconsistent, and hence show that there exists $u \in \mathcal{L}(Q)$ such that $(s \vdash u)$ and $(u \vdash t)$ both hold.

  comment

• 3.II.16G

  Set Theory and Logic | Part II, 2007

  Write down the recursive definitions of ordinal addition, multiplication and exponentiation. Prove carefully that $\omega^{\alpha} \geqslant \alpha$ for all $\alpha$, and hence show that for each non-zero ordinal $\alpha$ there exists a unique $\alpha_{0} \leqslant \alpha$ such that

  $$\omega^{\alpha_{0}} \leqslant \alpha<\omega^{\alpha_{0}+1} .$$

  Deduce that any non-zero ordinal $\alpha$ has a unique representation of the form

  $$\omega^{\alpha_{0}} \cdot a_{0}+\omega^{\alpha_{1}} \cdot \alpha_{1}+\cdots+\omega^{\alpha_{n}} \cdot a_{n}$$

  where $\alpha \geqslant \alpha_{0}>\alpha_{1}>\cdots>\alpha_{n}$ and $a_{0}, a_{1}, \ldots, a_{n}$ are non-zero natural numbers.

  Two ordinals $\beta, \gamma$ are said to be commensurable if we have neither $\beta+\gamma=\gamma$ nor $\gamma+\beta=\beta$. Show that $\beta$ and $\gamma$ are commensurable if and only if there exists $\alpha$ such that both $\beta$ and $\gamma$ lie in the set

  $$\left\{\delta \mid \omega^{\alpha} \leqslant \delta<\omega^{\alpha+1}\right\}$$

  comment

• 4.II.16G

  Set Theory and Logic | Part II, 2007

  Explain what is meant by a well-founded binary relation on a set.

  Given a set $a$, we say that a mapping $f: a \rightarrow \mathcal{P} a$ is recursive if, given any set $b$ equipped with a mapping $g: \mathcal{P} b \rightarrow b$, there exists a unique $h: a \rightarrow b$ such that $h=g \circ h_{*} \circ f$, where $h_{*}: \mathcal{P} a \rightarrow \mathcal{P} b$ denotes the mapping $a^{\prime} \mapsto\left\{h(x) \mid x \in a^{\prime}\right\}$. Show that $f$ is recursive if and only if the relation $\{\langle x, y\rangle \mid x \in f(y)\}$ is well-founded.

  [If you need to use any form of the recursion theorem, you should prove it.]

  comment