Apr 25, 2014
0 notes


Apr 24, 2014
1 note

Moschovakis, x6.32

Prove the absorption law of cardinal multiplication, i.e. \(\kappa \cdot \lambda = \max(\kappa,\lambda)\) whenever \(\max(\kappa,\lambda) \geq \omega\).

Lemma: For any cardinal \(\kappa\) satisfying \(\omega \leq_{ON} \kappa\), \(\kappa = \kappa \cdot \kappa\).

Proof of Lemma. Let \(\kappa\) denote the least such witness to the failure of the lemma. Define a wellordering \(r\) on \(\kappa \times \kappa\) by, say, (denoting \((a_1,a_2) = a, (b_1,b_2) = b\))

\[a \leq_r b \iff ((a_1 = b_1 \land a_2 = b_2) \lor ((\max a <_{ON} \max b) \lor ((\max a =_{ON} \max b) \land (a_1 <_{ON} b_1))\]\[ \lor ((\max a =_{ON} \max b) \land (a_1 =_{ON} b_1) \land (a_2 <_{ON} b_2))).\]

It is easy, though tedious, to verify this is a wellordering, so I’ll omit everything but the verification that there exist lower bounds. Let \(S \subseteq \kappa \times \kappa\); let \(S’ \subseteq S\) be given by \(S’ := \{a \in S | \max(a)\) is \(ON\)-least in \(\max[S]\}\); now we see that \(S’\) must have an \(r\)-least element since we can find an \(ON\)-least element in the first or second slot.

Continuing with the proof of the Lemma, we have by the above that \(\kappa \times \kappa\) is isomorphic (by some order-isomorphism \(f\)) to some ordinal \(\eta\); by assumption, \(\kappa \in \eta\) so there must be \((\alpha_1,\alpha_2) \in \kappa \times \kappa\) such that \(f((\alpha_1,\alpha_2)) = \kappa.\) By transitivity, \[f[\{\xi \in \kappa \times \kappa : \xi <_r (\alpha_1,\alpha_2)\}] = \kappa.\] Consider \(\max(\alpha_1,\alpha_2)’\). On one hand, \[\kappa \leq_c f[\{\xi \in \kappa \times \kappa : \xi <_r (\alpha_1,\alpha_2)\}] \leq_c \max(\alpha_1,\alpha_2)’ \times \max(\alpha_1,\alpha_2)’.\] On the other hand, \(\max(\alpha_1,\alpha_2)\) is either finite or infinite. In the former case we obtain a contradiction. In the latter case we obtain a contradiction by the minimality of \(\kappa\), and the lemma is proved.

Now, WLOG let \(\kappa > \lambda\); we have that \(\kappa \times \lambda \leq_c \kappa \times \kappa =_c \kappa\) by inclusion; in the other direction, \(\kappa \times \kappa =_c \kappa \leq_c \kappa \times \lambda\) again by inclusion (say, \(k \mapsto (k, \emptyset)\).) Since cardinal numbers are unique up to equality under the \(\leq_c\)-relation, we have \(\kappa \cdot \lambda = \kappa = \max(\kappa,\lambda)\), as desired.

Apr 24, 2014
1 note

Moschovakis, x6.29 (The Schroder-Bernstein Theorem)

Prove that for any two sets \(x,y\),

\[(x \leq_c y \land y \leq_c x) \Rightarrow x =_c y.\]

The hypotheses guarantee injections \(x \overset{f}{\hookrightarrow} y\) and \(y \overset{g}{\hookrightarrow} x\); consider, for any \(a \in x\) (resp. starting with \(f^{-1}\) for \(a \in y\)) the sequence \[g^{-1}(a), (f^{-1} \circ g^{-1})(a), (g^{-1} \circ f^{-1} \circ g^{-1})(a) \cdots\] where we put (technically we’re abusing notation by extending the inverse given by the injectivity of \(f\) and \(g\) from \(\operatorname{Image}(f)\) (resp. \(g\)) to \(x\) (resp. \(y\)) to be defined over all of \(y\) (resp. \(x\)) with the emptyset adjoined) \[(\forall a \in \operatorname{Image}(f))[f^{-1}(a) = \text{ the unique } b : f(b) = a] \land (\forall a \not \in \operatorname{Image}(f))[f^{-1}(a) = \emptyset] \land (f^{-1}(\emptyset) = \emptyset)\] (and similarly for \(g^{-1}\)).

Call the sequence associated to an element \(\alpha\) \(s_\alpha\); say \(s_\alpha\) terminates if it stabilizes to the emptyset. Define \(S_1(x) := \{\alpha \in x | s_\alpha \text{ terminates }\}\) (resp. \(y\)) and \(S_2(x) := x \backslash S_1(x)\), i.e. the set of all elements of \(x\) (resp. \(y\)) whose sequences don’t terminate. Clearly \(S_1,S_2\) partition \(x,y\).

I claim the map \(S_2(x) \rightarrow S_2(y)\) by \(a \mapsto g^{-1}(a)\) is a bijection. Indeed, \(\forall a \in S_2(x), a \in \operatorname{Image}(g)\) (since otherwise \(s_a\) would terminate), and \(g^{-1} \restriction \operatorname{Image}(g)\) is a bijection to \(y\); we’ll just need to show \(g^{-1}[S_2(x)] = S_2(y)\). On one hand, \(g[S_2(y)] \subseteq S_2(x) \Rightarrow S_2(y) \subseteq g^{-1}[S_2(x)]\); on the other, everything with a nonterminating sequence in \(x\) still has a nonterminating sequence after being pulled back to \(y\), so \(g^{-1}[S_2(x)] \subseteq S_2(y).\)

To complete the proof, we’ll need to show \(S_1(x) =_c S_1(y)\). Since, for every \(a \in S_1(x)\) (resp. \(b \in S_2(y)\)), \(s_a\) ends up in either \(x\) or \(y\) before terminating to the emptyset, we can further partition \(S_1(x),S_2(y)\) into \(S_1(x)_x,S_1(x)_y\) (resp. for \(S_1(y)\)), where we read \(S_1(x)_x\) as ‘the subset of \(S_1(x)\) whose sequences end up in \(x\) before terminating in the emptyset.’ Set up a bijection between \(S_1(x)_x\) and \(S_1(y)_x\) by \(a \mapsto f(a)\); \(f\) is already injective so it suffices to show surjectivity; let \(a \in S_1(x)_x\); clearly \(s_{f(a)}\) also ends up in \(x\) before terminating to the emptyset, so \(f(x) \in S_1(y)_x\); let \(b \in S_1(y)_x\); by definition everything in \(S_1(y)_x\) must have nonempty preimages under \(f\) (since \(\forall b \in S_1(y)_x\) the first instance of the emptyset in \(s_b\) has to occur after taking \(g^{-1}\)). An identical argument giving a bijection \(g \restriction S_1(y)_y : S_1(y)_y \rightarrow S_1(x)_y\) gives us \(S_1(x) =_c S_1(y)\). We then glue together our bijections by taking unions of their domains and ranges to obtain \(x =_c y\), completing the proof.

Apr 24, 2014
1 note

Moschovakis, (2)-(5) of 6C.9

6C.9 (2) For each \(\xi\) in ON, \(\xi’ = \xi \cup \{\xi\}\) is the successor of \(\xi\) i.e. \[\xi <_{ON} \xi’ \land (\forall \eta)[\xi <_{ON} \eta \Rightarrow \xi’ \leq \eta].\]

Clearly \(\xi \in \xi’\) so \(\xi <_{ON} \xi’\); for the second part, suppose otherwise, i.e. let \(\eta_1\) witness the failure of \[(\forall \eta)[\xi <_{ON} \eta \Rightarrow \xi’ \leq \eta].\] By Trichotomy (c.f. (1)), we must have that \(\xi’ >_{ON} \eta\), i.e. \(\eta \in \xi \cup \{\xi\}\), so either \(\eta = \xi\) or \(\eta \in \xi\), but by Trichotomy both are excluded by our assumption that \(\xi <_{ON} \eta\), an impossibility.

6C.9 (3) Every ordinal is grounded.

Unwinding definitions, an ordinal \(\alpha\) is grounded if \[\forall x \subseteq \alpha’ : x \not = \emptyset, (\exists y \in x)(\forall t \in x)[t \not \in y].\] Every subset of \(\alpha’\) is also, by transitivity, a subset of \(ON\), so by (1) we obtain in each \(x\) a \(\leq_{ON}\)-least element \(y\). By Trichotomy, \[(\forall t \in x)[y \leq_{ON} t] \Rightarrow t \not <_{ON} y \iff t \not \in y,\] and we’re done.

6C.9 (4) For every \(x \in ON\),

\(\bigcup x = \sup \{\xi : \xi \in x\} = \) the least ordinal \(\eta\) such that \((\forall \xi \in x)[\eta \geq_{ON} \xi]\).

Clearly \(\bigcup x\) is transitive by the transitivity of the members of \(x\); now let \(x,y \in \bigcup x\); \(x\) and \(y\) lie in \(\alpha, \beta \in x\); WLOG \(\alpha <_{ON} \beta\); if \(y <_{ON} \alpha\) we’re done so suppose otherwise; then by transitivity \(x \in \beta \land x <_\beta y \Rightarrow x <_{ON} y\), so \(\bigcup x\) is an ordinal. Now suppose towards a contradiction there exists an \(\eta\) such that \(\eta <_{ON} \bigcup x \land (\forall \xi \in x)[\xi \leq_{ON} \eta]\). Then \(\eta \in \bigcup x \iff\) (by definition of the unionset operation) \(\eta \in \alpha \in x\), but by Trichotomy this contradicts \((\forall \xi \in x)[\xi \leq_{ON} \eta]\).

6C.9 (5) For every ordinal \(\xi\), exactly one of the following hold:

(1) \(\xi\) = \(\emptyset\)
(2) \(\xi\) is a successor i.e. \(\xi = \eta’\), some \(\eta\).
(3) \(\xi\) is a limit ordinal, i.e. \((\forall \eta <_{ON} \xi)[\eta’ <_{ON} \xi] \land \xi = \bigcup \xi\).

(I’m not quite sure if the emptyset doesn’t satisfy the definition of a limit ordinal given in the notes, since \(\sup \{0\} = 0\) and the first condition is vacuously satisfied; but I’m sure that’s not the point of this exercise.)

1) Since, by extensionality, the emptyset is unique, we ignore this case.

2) and 3) Define the successorset \(S(\alpha)\) of an ordinal \(\alpha\) as the set of successors of elements of \(\alpha\). Now, for all \(\alpha\), either \(S(\alpha) \subseteq \alpha\) or not; I claim the latter holds if and only if \(\alpha\) is a successor and that the former holds if and only if \(\alpha\) is a limit ordinal.

For the first half of my claim, it’s clear in one direction that if \(\alpha = \eta’\) then \(\eta’ \not \in \alpha\); in the other direction, let \(\beta’\) be the \(ON\)-least element of \(S(\alpha) \backslash \alpha\); suppose \(\alpha \not <_{ON} \beta’ \Rightarrow \alpha \leq \beta,\) but \(\beta \in \alpha\), so that cant happen; suppose then that \(\alpha >_{ON} \beta’ \Rightarrow \beta’ \in \alpha\), which would contradict the definition of \(\beta’\), so by Trichotomy we have \(\alpha = \beta’\).

For the second half of my claim, in one direction we see that the condition \((\forall \eta <_{ON} \alpha)[\eta’ <_{ON} \alpha]\) implies \(S(\alpha) \subseteq \alpha\); in the other direction, we have by definition \(S(\alpha) \subseteq \alpha \Rightarrow (\forall \eta \in \alpha)[\eta’ \in \alpha]\), which gives the first part of the definition of a limit ordinal; for the second part, see that

\[S(\alpha) \subseteq \alpha \Rightarrow (\forall \eta \in \alpha)[\eta’ \in \alpha] \Rightarrow (\forall x \in \alpha)[x \in x’ \in \alpha]\] i.e every member of \(\alpha\) is a member of a member of \(\alpha\), so \(\alpha \subseteq \bigcup \alpha\); the other inclusion is given by transitivity and we’re done.

Apr 22, 2014
2 notes

1.10.17, AEoR vol. 1

Show that the space of signed finite Radon measures \(M(X)\) with the total variation norm \[||u||_{M(X)} := |u|(X) = (\mu^+ + \mu^-)(X)\] is a real Banach space isomorphic to both \(C_c(X \rightarrow \mathbf{R})^*\) and \(C_0(X \rightarrow \mathbf{R})^*.\)

It is easy to verify \(M(X)\) is a real normed space. Let \((\mu_i)\) be a \(||\cdot ||_{M(X)}\)-Cauchy sequence of signed finite Radon measures on \(X\); this means precisely that \((|\mu_i|(X))\) is a Cauchy sequence of real numbers which therefore converges to some limit \(c \in \mathbf{R}\). Choose \(a,b \in \mathbf{R}^+\) such that \(a\mu_1^+(X) + b \mu_1^-(X) = c\). Then \((\mu_i) \rightarrow \mu\) where \(\mu\) is the signed finite Radon measure given by \( a \mu_1^+ - b \mu_1^-\), so \(M(X)\) is complete, hence Banach.

We obtain a map \[M(X) \overset{f}{\simeq} C_c(X \rightarrow \mathbf{R})^*\] by \(\mu \mapsto I_\mu = I_{\mu^+} - I_{\mu^-}\); by the existence guaranteed via the Riesz representation theorem \(f\) is surjective; by the uniqueness part, it’s injective. In one direction, \[||I_\mu||_{\mathrm{op}} \leq \mu(X) \leq |\mu|(X).\] To show the other direction, let \(\epsilon > 0\) and write \(\mu = \mu^+ - \mu^-\); \(\mu^+\) and \(\mu^-\) are supported on disjoint subsets of \(X\), say \(X_1\),\(X_2\); by inner-regularity obtain \(K_1,K_2\) compact in \(X_1,X_2\) such that \(\mu^+(K_1) \geq \mu^+(X) - \epsilon \) (resp. for \(\mu^-\)); let \(U_1^n, U_2^n\) be disjoint open neighborhoods for the \(K\)’s such that \[U_i^n := \bigcup_{x \in K_i} B(x,1/n).\] By Exercise 1.10.6 we can obtain for each \(U_i^n\) an approximation \(f^+_n\) (resp. \(f^-_n\)) of the characteristic function of \(K_i\); taking limits we get \[I_\mu(f^+_n - f^-_n) \rightarrow \mu^+(K_1) - \mu^-(K_2) \geq ||\mu||_{M(X)} - 2 \epsilon\] and since \(||f^+n - f^-_n||_{\mathrm{op}} = 1\), this gives the desired inequality.

To show \(C_c(X \rightarrow \mathbf{R})^* \simeq C_0 (X \rightarrow \mathbf{R})^*,\) since Riesz allows us to embed (with operator norm 1) \(C_c^* \overset{\iota}{\hookrightarrow} C_0^*\) by integrals, it’ll suffice to exhibit an embedding in the other direction \(C_0 (X \rightarrow \mathbf{R})^* \hookrightarrow C_c(X \rightarrow \mathbf{R})^*\). We can take this as \(I \mapsto I |_{\iota(C_c(X \rightarrow \mathbf{R})^*}\), \(\forall I \in C_0(X \rightarrow \mathbf{R})^*\). Indeed, since continuous functionals preserve limits, there can’t exist \(I_1,I_2\) which agree over \(C_c\) but over its completion \(C_0\), so this is injective, and we’re done.

Apr 21, 2014
3 notes


Shaking has stopped with a second cup of coffee but now my anxiety is at ridiculous levels.

basically me when problem sets are due

Apr 19, 2014
3 notes

1.10.16, AEoR vol. 1

Let \(I \in C_c(X \rightarrow \mathbf{R})^*\) a continuous linear functional; show \(\exists!\) finite Radon measure \(\mu\) such that \(I = I_\mu\).

Obtain unique Radon measures \(\mu^+,\mu^-\) corresponding to \(I^+\) and \(I^-\) via the Riesz representation theorem; then \(I_{\mu^+},I_{\mu^-}\) are continuous (with respect to the uniform norm on \(C_c\)) hence \(\mu^+,\mu^-\) are finite as well as Radon. I claim the signed measure \(\mu = \mu^+ - \mu^-\) satisfies the exercise.

From the definition of integration we see that whenever a finite measure \(\mu\) can be decomposed as \(\mu_1 - \mu_2\), \(\int_X f d\mu\ = \int_X f d(\mu_1 - \mu_2) = \int_X f d \mu_1 - \int_X f d \mu_2.\) Then we have (\(\forall f \in C_c\)) \[I_\mu(f) = \int_X f d \mu = \int_X f d(\mu^+ - \mu^-) = \int_X f d \mu^+ - \int_X f d \mu^-\]\[ = I_{\mu^+}(f) - I_{\mu^-}(f) = (I^+ - I^-)(f) = I(f).\] It remains to show uniqueness. Let \(\mu’\) be a signed measure satisfying \(I_{\mu’} = I = I_{\mu^+} - I_{\mu^-} = I_{\mu}\). In other words, \(\forall f \in C_c\), \[\int_X f d \mu’ = \int_X f d \mu.\] But this means we can just pass to the positive and negative variations of \(\mu\) and \(\mu’\) and apply an argument identical to the uniqueness proof in the unsigned version of Riesz, namely using \((\forall K \text{ compact })(\forall U \supset K \text{ open })(\exists f \in C_c)[1_K \leq f \leq 1_U]\) and inner-regularity to force agreement on open sets and then amplifying via outer-regularity to all Borel sets.

Apr 16, 2014
95 notes


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

(via antinegationism)

Apr 14, 2014
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\).

Apr 14, 2014
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.

« To the past Page 1 of 28
Repository for math-related links, anecdotes, code, and random thoughts. Subscribe via RSS.