**Navigate**

84 notes

Ain’t no party like a halting problem party because we have no idea if the party will stop

(via antinegationism)

1 note

## x6.10, Moschovakis

Prove that \(( \exists z)[(\emptyset \in z)\) && \((\forall t \in z)[\{t\} \in z]].\) Outline a proof of the axiom of infinity in ZF - Infinity + (Z - infty).

For the first part, we want to show \[S = \{\emptyset, \{\}, \{\{\}\}, \{\{\{\}\}\},…\}\] is, indeed, a set. Define the relation \[r(x,y)\] \[\Leftrightarrow ([(x \not \in \omega) \land (x = y)] \lor [(x = 0) \land (y = \emptyset)]\]\[ \lor [(x = 1) \land (y = TC(\emptyset))] \lor [(x \in \omega) \land (y = \operatorname{pair}(x-1,0))]).\] By the uniqueness of set-equality, \(\emptyset\), transitive closure, the predecessor operation on \(\omega\), and the pairing operation, this induces a function \[\omega \overset{f}{\rightarrow} S\] by \(f(0) = \emptyset, f(1) = TC( \emptyset ), f(n) = \operatorname{pair}(n-1,0)\) which satisfies the conditions of the Replacement Axiom Schema and so we find that \(f[\omega]\) is, indeed, a set.

Alternately, for the first part, we can also see that \(f\) satisfies the conditions of a recursively definable function on \(\omega\) given by Theorem 6C.6, by taking \(f = \bar{f}, a = \emptyset,\) and \(H\) as the constant function that sends everything to \(\emptyset\).

(Note: Actually, we can do away with the special case for \(n =1,\) since we obtain it by pairing the emptyset with the emptyset.)

Next, we’ll want to show we can reconstitute \(\omega\) from something that looks like \(S\). As requested, we’ll outline the proof. Let \(S’\) witness \(( \exists z)[(\emptyset \in z)\) && \((\forall t \in z)[\{t\} \in z]].\) (Am I using ‘witness’ correctly, here?) Show \(S = \bigcap S’\); define a wellordering \(<_r\) on \(S\) in the obvious way; generate by wellfounded recursion the canonical instance of \(\mathbb{N}\) by \[g(0) = \emptyset, g(n) = TC(g(\sup_r(\{s \in S : s <_rn\})))\] where we define \(\sup_r\) analogously to how we defined \(\sup_\omega\) for \(x6.11\).

1 note

## x6.5, Moschovakis

Show that \[\operatorname{Russell}(x) = \{t \in x : t \not \in t \} \not \in x\] and infer that the class \(V\) of all sets is not a set.

If it does, it doesn’t; if it doesn’t, it does; Immediate.

(Glad that’s off my bucket list, lols)

Actually, this resolves Russell’s paradox, as well: Russell(Sets) isn’t a set either, since otherwise (contracting Russell to ‘R’) we’d have
R(R(Sets)) \not \in R(Sets), which means R(R(Sets)) \in R(R(Sets)), implying R(R(Sets)) \not \in R(R(Sets)), a contradiction.

0 notes

## x6.11, Moschovakis

Prove that TFAE, \(\forall x\):

(1) \(x\) finite i.e. \(x =_c n,\) some \(n \in \omega\)

(2) \(\exists! n \in \omega\) so that \(x =_c n\)

(3) \(x <_c \omega\).

\((2) \Rightarrow (1)\) and \((1) \Rightarrow (3)\) are immediate; it remains to show \((1) \Rightarrow (2)\) and \((3) \Rightarrow (1)\). Suppose towards a contradiction \((1) \not \Rightarrow (2)\) i.e. \[(\exists n \in \omega)[x =_c n] \land (\exists m \in \omega)[(m \not = n) \land (x =_c m)],\] which implies by composition of isomorphisms that \(n =_c m\); WLOG \(n <_\omega m \Rightarrow n \in m.\) But by transitivity we can embed \(n\) in \(m\), so \(m\) contains something the size of \(n\) along with \(n\) itself, contradicting \(n =_c m.\)

Suppose now that \(x <_c \omega.\) By definition there exists an embedding \(x \overset{f}{\hookrightarrow} \omega;\) consider \[\sup_{\omega} (\operatorname{Image}(f)) := \inf_\omega \{(w \in \omega)[(\forall x \in \operatorname{Image}(f))[w \geq x]]\}.\] Now, if \(\sup_\omega (\operatorname{Image}(f))\) is finite, we’re done, since \(x =_c \operatorname{Image}(f) \subseteq
\sup_\omega (\operatorname{Image}(f))\) and we can induct downwards/use the pigeonhole principle on the expression \[(x =_c 0) \lor (x =_c 1) \lor … \lor (x =_c\sup_\omega(\operatorname{Image}(f)).\] But we see immediately that \(\sup_\omega (\operatorname{Image}(f)\) has to be finite, because if it were infinite we could induce an embedding \(\omega \overset{g}{\hookrightarrow} x\) by \[n \mapsto f^{-1}(\inf_\omega \{(w \in \operatorname{Image}(f))[w \geq_\omega \operatorname{max}_\omega (n, g(n - 1))]\})\] where we put \(g(-1) = 0\) and where \(f^{-1}\) is the inverse mapping from the image of the injection \(f\) to its domain.

8 notes

Coding a sequence of operations that might fail in C.

I miss “Maybe” and “Either.”

#haskell #has ruined my life (regexkind)

(via light-rook)

0 notes

## x6.9, Moschovakis

Prove that the restriction \[S = \{\langle n,n’ \rangle\} : n \in \omega\}\] of the operation \(x’ = x \cup \{x\}\) is a bijection of \(\omega\) with \(\omega \backslash \{0\}\).

Denote the operation by \(f,\) i.e. we want to show \(\omega \overset{f \restriction \omega}{\rightarrowtail \hspace{-8pt} \rightarrow} \omega \backslash \{0\}\). We have that \(f \restriction \omega\) is a surjection since \((\forall x \in \omega)[x = 0 \lor (\exists k \in \omega)[x = f(k)]].\) It remains to show \(f \restriction \omega\) is injective. Consider \((a,b \in \omega)[a \not = b]\); WLOG \(a \text{ strictly less than } b\); then \(f \restriction \omega (a) = \inf_{\omega}\{x \in \omega : x > a\}\); now, \[b \geq \inf_{\omega} \{x \in \omega : x > a\} \Rightarrow f \restriction \omega (b) > \inf_{\omega} \{x \in \omega : x > a\}\] (if one requires more clarity, split it into the case where they *are* equal versus when they’re not), so \(\forall a,b)[a \not b] \Rightarrow f \restriction \omega (a) \not = f \restriction \omega (b)\), verifying the claim.

3 notes

There are deep connections between model theory and arithmetic geometry. There are deep connections between model theory and arithmetic geometry…What I have to keep saying to stop myself from screaming with rage as I try to read this textbook on mathematical logic.

0 notes

## x6.8, Moschovakis

Show the transitive closure of a transitive set \(x\) is \(x \cup \{x\}\).

Let \(y \in x \cup \{x\}\); then \(y \in x \lor y = x \Rightarrow (\forall Y \text{transitive} )[x \in Y], \bigcup Y \subset Y = \bigcup_{s \in Y} y \Rightarrow\) either \(y = x\) in which case \(y \in Y\) or \(y \in x\) in which case \(y \in \bigcup Y \subset Y \Rightarrow y \in Y.\) Then \(y \in \bigcap_{Y \text{ transitive containing (as a member) } x} Y,\) i.e. we have that \(x \cup \{x\} \subseteq Y.\)

In the other direction, \(x \cup \{x\}\) is transitive whenever \(x\) is transitive since
\[\bigcup x \cup \{x\} = \bigcup x \cup x \subset x \subset x \cup \{x\}\] since the union of subsets is a subset. Then \[y \in \operatorname{TC}(x) = \cap_{Y \text{ transitive containing (as a member) } x} Y \Rightarrow y \in x \cup \{x\},\] which verifies the other direction of the inclusion; hence \(x \text{ transitive } \Rightarrow \operatorname{TC}(x) = x \cup \{x\}\), as was to be shown.

(In particular, the successor of a transitive set is its transitive closure.)

16 notes

I believe the correct pluralization is “topoi” :PFrom the end of the introduction to P.T. Johnstone’s

Topos Theory:P

0 notes

## 1.10.8, AEoR vol.1

Let \(X\) be a metric space; let \(K \overset{\text{closed}}{\subset} X\), and let \(f:K \rightarrow \mathbf{R}\) be a Lipschitz continuous map with some Lipschitz constant \(A\) (thus we have \[|f(x) - f(y)| \leq A \cdot d(x,y),\] \(\forall x,y \in K.\)) Show \(\exists \tilde{f} : X \rightarrow \mathbf{R},\) also Lipschitz continuous with same constant \(A.\)
*Proof.* Since metric spaces are normal, we can find for any closed \(K\) and a neighborhood \(U\) containing it a continuous \(h\) satisfying \(1_K \leq h \leq 1_U\) pointwise. Let \(\tilde{f}\) be the continuous extension to \(\mathbf{R}\) guaranteed by the intermediate step in the Tietze extension theorem; the idea is to show that we can make \(h \cdot \tilde{f}\) have Lipschitz constant \(A\).

Let \(\epsilon > 0\) and obtain by the continuity of \(\tilde{f}\) a \(\delta\); consider \(U_\delta\) around \(K\) as \(\bigcup_{x \in K} B(x, \delta)\) and obtain an \(h_\delta\) as above. Consider the case where \(x,y \in U_\delta \backslash K;\) choose a \(x’ \in K\) such that \(d(x,x’) = \operatorname{inf}_{x’ \in K} d(x,x’)\) and similarly obtain a \(y’\); by repeated applications of the triangle equality see that \(d(x,y) \leq d(x’,y’) + 2 \delta \Rightarrow\) (by continuity) \(d(f(x),f(y) \leq d(f(x’),f(y’)) + 2 \epsilon \leq A \cdot d(x’,y’) + 2 \epsilon\). Take \(\epsilon \rightarrow 0\), and we’re done. \(_\square\)

(I’m unsure of the validity of this argument.)

**About**