Pril
Sun, 13 Nov 2011 23:44:58 GMT

Sie ist endlich da ...


... Besser spät als nie!
Show comments (Requires JavaScript, loads external content and cookies from Disqus.com)

University Library Again
Fri, 04 Nov 2011 12:04:06 GMT

I already wrote about a campaign "Vergoogeln Sie keine Zeit" (do not waste your time with google) in my university's library. I usually try not to use it, but today, I was looking for a book to learn for my current tests, about algebraic curves.

Firstly, I tried to survive without technology, and went to the shelves for the topic of algebraic geometry. Since I did not find the book there, I searched with their local web interface. The main problem was probably that I misspelled the actual author, I searched for "Fulten" rather than "Fulton", but every reasonable search mechanism should be able to find the right book with a perfectly correct title given, and a little mistake on the author's name. However, of course I tried to search only for "Fulten" and only for "Algebraic Curves", the latter query returned a long list of highly specialized stuff related to algebraic curves, but not the desired book (at least not at the first three pages of at least 20).

As I did not want to waste any more time with this, I searched with Google for "Fulten Algebraic Curves". It suggested "Fulton Algebraic Curves", and using this suggestion, the first Item I found was the site of William Fulton, publishing his book as a free PDF.

I rest my case.
Show comments (Requires JavaScript, loads external content and cookies from Disqus.com)

Unsere Regierung ist wie eine Jeans ...
Tue, 01 Nov 2011 04:01:24 GMT

... an den wichtigen Stellen wird sie nur von Nieten zusammengehalten.

(via)
Show comments (Requires JavaScript, loads external content and cookies from Disqus.com)

Black Hole
Fri, 28 Oct 2011 22:44:23 GMT

Panel 1: A zoom into the center of our galaxy is shown. Title: "They say that at the center of our galaxy... There is probably a black hole." -- Panel 2: A black hole is shown, with a "ONE WAY" sign. Title: "Nothing that enters a black hole can escape it anymore." -- Panel 3: Title: "So nobody knows what cruel things might be inside it...". A zoom into the black hole is shown, which shows a cinema with a screen with the text "Doctor Zhivago".
(Sorry for this one)
Show comments (Requires JavaScript, loads external content and cookies from Disqus.com)

AC is not refutable in ZF - Part 4
Wed, 12 Oct 2011 21:39:00 GMT

So, finally, this is part 4 of my series about the irrefutability of the AC from ZF. We are almost there!

Theorem 1: Let ZF-Formulae \phi_0(\vec{x}),\ldots,\phi_n(\vec{x}) be given. Then \forall_\alpha\exists_{\beta\ge\alpha}\forall_{\vec{x}\in V_\beta} \bigwedge\limits_{i=0}^n (\phi_i(\vec{x})\leftrightarrow\phi_i^{V_\beta}(\vec{x})). We then say that V_\beta reflects the \phi_i.
Proof: Let \alpha be given. Without loss of generality we may assume that the \phi_i can be written without universal quantifiers, as we can replace every universal quantifier by a negated existential quantifier of the negated quantfied formula.
Recursively define a sequence \left<\beta_n \mid n<\omega\right> where \beta_0=\alpha and \beta_{n+1} is the smallest ordinal \gamma>\beta_n, such that if \exists_y\theta(\vec{z},y) is a subformula of one of the \phi_i, we have \forall_{\vec{z}\in V_{\beta_n}}((\exists_y\theta(\vec{z},y))\rightarrow\exists_{y\in V_\gamma}\theta(\vec{z},y)). Let \beta be the supremum of the \beta_i. It is sufficient to show that for all subformulae \psi(\vec{z}) of any \phi_i we have \forall_{\vec{z}\in V_\beta}(\psi(\vec{z})\leftrightarrow\psi^{V_\beta}(\vec{z})), which goes by structural induction. If \psi is of the form x\in y this is trivial. The step over \rightarrow,\wedge,\bot is clear. We can assume that every occurence of \forall is in the scope of an occurence of \exists, and therefore, instead of having an induction step for \forall, we have an induction step for \exists: \psi=\exists_y\theta(\vec{z},y), and let \vec{z}\in V_\beta. By induction hypothesis, \psi^{V_\beta}(\vec{z})\rightarrow\psi(\vec{z}). For the other direction, let \exists_y\theta(\vec{z},y), then \exists_y\in V_{\beta_{n+1}}\theta(\vec{z},y). By induction hypothesis, we have \exists_{y\in V_\beta}\theta^{V_\beta}(\vec{z},y).
□
We can do everything we did in Part 1 as well directly in ZF. Alphabets become sets, and formulae become finite sequences. Especially, there is a set of all formulae, which is countable. Notice that there is no need to fix a special "encoding" for formulae, it is clear that one exists, and it is clear that all such encodings have to be equivalent. For a ZF-formula \phi, let \lceil\phi\rceil be its embedding into ZF, that is, \lceil\phi\rceil is a set.

For every set u we can define an interpretation, interpreting \in by \{\left<x,y\right>\in u\times u \mid x\in y\}. We write u\models \phi if this interpretation (for all valuations) models \lceil\phi\rceil, notice that in this case, \models is a relation inside ZF. Trivially, we have \forall_{\vec{a}\in u}((u\models\phi(\vec{a})) \Leftrightarrow\phi^u(\vec{a})).

Definition: Now we can define the class of OD of ordinal definable sets:

OD:=\{x \mid \exists_{\alpha\in On}\exists_{\vec{p}\in\alpha}\exists_{\lceil\phi\rceil} x=\{y\in V_\alpha \mid V_\alpha\models \phi(y,\vec{p})\}\}

where we write \exists_{\lceil\phi\rceil} to denote that there must exist an encoded ZF-formula.

This class is interesting, as it messes around with the intuition about two meta-layers. However, it is not yet our goal.

Definition: The transitive closure TC(x) of a set x is the smallest y\supseteq x such that every element of y is also subset of y.

Definition: The class HOD of hereditary ordinal definable sets is defined by

HOD:=\{x \mid TC(\{x\})\subseteq OD\}

Since x\in TC(\{x\}), trivially HOD\subseteq OD.

Lemma 1: x\in HOD \Leftrightarrow x\in OD\wedge x\subseteq HOD.
Proof: "=>": From x\in HOD directly follows TC(\{x\}\subseteq OD, therefore, x\in OD. For y\in x we have TC(\{y\})\subseteq TC(\{x\})\subseteq OD\subseteq HOD, that is, y\in HOD, therefore, x\subseteq HOD.
"<=": For x\in OD and TC(\{x\})\subseteq HOD we have TC(\{x\})=\{x\}\cup\bigcup_{y\in x} TC(\{y\})\subseteq OD. Therefore, x\in HOD.
□
Lemma 2: For every ZF-formula \phi(x,\vec{y}) we have \forall_{\vec{\gamma}\in On}(\{x \mid \phi(x,\vec{\gamma})\}\in V\rightarrow\{x \mid \phi(x,\vec{\gamma})\}\in OD.
Proof: Let \{x \mid \phi(x,\vec{\gamma)}\in V, \alpha such that \{x \mid \phi(x,\vec{\gamma)}\in V_\alpha, and \vec{\gamma}<\alpha. By Theorem 1 there is a \beta\ge\alpha such that V_\beta reflects \phi, therefore \{x \mid \phi(x,\vec{\gamma})\} = \{x\in V_\beta \mid \phi^{V_\beta}(x,\vec{\gamma})\} = \{x\in V_\beta \mid V_\beta\models\phi(x,\vec{\gamma})\}\in OD.
□
Theorem 2: HOD is an inner model.
Proof: Due to Part 3, it is sufficient to show (I1), (I2) and (I3). By Lemma 1, (I1) holds.
Let x\subseteq HOD, and \alpha such that x\subseteq V_\alpha. Then trivially, x\subseteq V_\alpha\cap HOD. But by Lemma 2 we have V_\alpha\cap HOD=\{x \mid x\in V_\alpha\wedge x\in HOD\}\in OD. Trivially, we also have V_\alpha\cap HOD\subseteq HOD, so by Lemma 1, V_\alpha\cap HOD\in HOD. Thus, (I2) holds.
For (I3), let \phi(x,\vec{z}) be a \Sigma_0-formula, choose arbitrary \vec{z},u\in HOD, and let a=\{x\in u \mid \phi(x,\vec{z})\}. Then a\subseteq u\subseteq HOD by (I1), so by Lemma 1, it is sufficient to show that a\in OD. As HOD\subseteq OD we have \vec{z},u\in OD, therefore there are \vec{\lceil\phi\rceil},\lceil\psi\rceil and \vec{\alpha},\gamma\in On and for i=1,\ldots,n there are p_i\in \alpha_i^{<\omega}, q\in\gamma^{<\omega} sucht hat z_i = \{y\in V_{\alpha_i} \mid V_{\alpha_i}\models\phi_i(y,p_i)\} and u=\{y\in V_\gamma \mid V_\gamma\models\psi(y,q)\}. Let \alpha=\max\{\vec{alpha},\gamma\}, and \chi(x,y)=\lceil y=V_x\rceil. By Theorem 1 we get a \beta>\alpha such that V_\beta reflects \chi. Therefore

a=\{x\in V_\beta \mid V_\beta\models \exists_{\vec{w}}\exists_w(\chi(\gamma, w)\wedge
(\bigwedge\limits_{i=1}^n\chi(\alpha_i,w_i))\wedge
\exists_{\vec{v}}\forall_y (\psi^w(x,q)\wedge\phi(x,\wedge{v})\wedge\bigwedge\limits_{i=1}^n (y\in v_i\leftrightarrow\phi_i^{w_i}(y,p_i))))\}

which is in OD. Therefore, a\in HOD.
□
Lemma 3: There exists a surjective functor F:On\rightarrow OD.
Proof: In Part 2 we proved that there is a bijection G:On\rightarrow\omega\times On^{<\omega}, so it is sufficient to give a surjective functor F:\omega\times On^{<\omega}\rightarrow OD. Now let \left<\phi_n \mid n<\omega\right> be an enumeration of all ZF-formulae. Define

F(n,p) = \left\{\begin{array}{rl} \{x\in V_{p(m)} \mid V_{p(m)}\models\phi_n(x,p \mid _m)\} & \mbox{ for } \operatorname{dom}(p)=m+1 \\ \emptyset & \mbox{ otherwise}\end{array}\right.

Then F is surjective.
□
Lemma 4: There exists a surjective functor H:On\rightarrow HOD
Proof: Since HOD\subseteq OD, use H=F \mid _{HOD}.
□
Theorem: (AC) holds in HOD
Proof: By Lemma 4, we have our surjective H:On\rightarrow HOD. For \alpha\in On, define g_\alpha= H \mid _\alpha. By Lemma 2 we know that for every \alpha, g_\alpha\in OD, and since g_\alpha\subseteq HOD, we have g_\alpha\in HOD. Let u\in HOD be arbitrary but fixed. Then there exists an \alpha such that u\subseteq \operatorname{ran}(g_\alpha). Now define a well-ordering r\subseteq u\times u by

\{\left<x;y\right> \mid \min\{\gamma \mid x=g_\alpha(\gamma)\}<\min\{\gamma \mid y=g_\alpha(\gamma)\}

r is a well-ordering, and r\in HOD. Thus, in HOD, the well-ordering theorem holds, therefore, AC holds in HOD.
□
Show comments (Requires JavaScript, loads external content and cookies from Disqus.com)

AC is not refutable in ZF - Part 3
Sun, 09 Oct 2011 20:15:00 GMT

This is part 3 of my posts about the irrefutability of AC in ZF.

We define a hierarchy of sets, the V-hierarchy.
  • V_0:=\emptyset
  • V_{\kappa+1}:=\mathbb{P}(V_{\kappa})
  • V_\lambda := \bigcup_{\gamma<\lambda} V_\gamma for limes-ordinals \lambda
Furthermore, we have V_\alpha\subseteq V_\beta for \alpha\le\beta, which can be shown by a trivial inductive argument.

Theorem: We have V=\bigcup_{\gamma\in On} V_\gamma.
Proof: Assume there was an x\in V which is not in V_\alpha for some \alpha. Then it cannot be subset of any V_\alpha, since otherwise it would be element of V_{\alpha+1}. Therefore it must contain an element x' which is not in V_\alpha for every \alpha as well. That is, every set not being in any of the V_\alpha must contain a set not being in any of the V_\alpha, hence, we would get an infinite \ni-chain, which contradicts (FUN). □

Definition: The relativization \phi^W of a formula \phi regarding a class W is defined inductively over the structure on \phi by:
  • \bot^W := \bot
  • (x=y)^W := (x=y)
  • (x\in y)^W := x\in y
  • (\phi\wedge\psi)^W:=\phi^W\wedge\psi^W
  • (\forall_x \phi)^W := \forall_x (x\in W \rightarrow \phi^W)
Intuitively, \phi^W means that \phi holds in W. We will later write W\models\phi to denote that \phi^W holds, defining yet another additional meaning for \models.

Definition: A class W is called inner model of ZF, if it satisfies
  • for all x\in W we have x\subseteq W
  • On\subseteq W
  • for all axioms \phi of ZF we have ZF\models\phi^W
Remark: V is an inner model of ZF, since \phi=\phi^V.

Inner models provide a way of getting new models from models of ZF:

Remark: Let W be an inner model of ZF, and {\mathcal M} be a model of ZF with domain M and the \in-relation interpreted by a relation \epsilon\subseteq M^2. Let N=\{a\in M|{\mathcal M}\models a\in W\} and \mathcal N be an interpretation with domain N and \in-relation \epsilon\cap N^2. Then {\mathcal N}\models ZF.

Therefore, it is sufficient to give an inner model of ZF satisfying AC to show that AC is not refutable: From a model of ZF, we would get a model of ZF satisfying AC. That is what we are going to do. Before we can do this, we have to do some work to give an alternative classification of inner models.

Definition: A formula is called \Sigma_0-formula, if every quantifier is bounded, that is, every universal quantifier is of the form \forall_x (x\in y\rightarrow \phi), and equivalently, every existential quantifier is of the form \exists_x (x\in y \wedge \phi). (Recall that our language does not contain existential quantifiers directly, but defines them by universal quantifiers. However, our definition is equivalent to what we would get directly.)

Notice that x=y is a \Sigma_0-formula.

We write \forall_{x\in y} \phi for \forall_x (x\in y\rightarrow \phi), and \exists_{x\in y} \phi for \exists_x (x\in y\wedge\phi). Furthermore, if we want to denote a list of variables, then we use the vector notation \vec{x}, and we will use \forall_{\vec{x}} to denote the universal quantification over all of these variables.

Theorem I: Let W be a class. Then the following propositions are equivalent:
  • a. W is an inner model
  • b. W satisfies:
    • (I1) Every element of W is a subset of W
    • (I2) For every x\subseteq W there is an element y\in W such that x\subseteq y
    • (I3) For every \Sigma_0-formula \phi(x,\vec{z}) we have \forall_{\vec{z}\in W}\forall_{u\in W} \{x\in u|\phi(x,\vec{z})\}\in W
To proof Theorem I, some additional work needs to be done. Firstly, we will replace the replacement scheme by two other schemes:

\Sigma_0-comprehension: For every \Sigma_0-formula \phi(x,\vec{z}) we have \forall_{\vec{z}}\forall_u\{x\in u|\phi(x,\vec{z})\}\in V.

Limitation: For every ZF-formula \phi(x,y,\vec{z}) we have \forall_{\vec{z}}\forall_u\exists_v\forall_{x\in u} ((\exists_y \phi(x,y,\vec{z}))\rightarrow \exists_{y\in v}\phi(x,y,\vec{z}))

Theorem: These schemes are derivable from ZF.
Proof: \Sigma_0-comprehension follows by general comprehension, which follows by (RPL). For limitation, let \phi, \vec{z} and u be given, and a=\{x\in u|\exists_y\phi(x,y,\vec{z})\}. Define a function g:a\rightarrow On, g(x)=\min\{\gamma|\exists_{y\in V_\gamma}\phi(x,y,\vec{z})\}; this is well-defined, since such a \gamma always exists according to the above theorem. Then the range of g is a set of ordinals, and therefore has a supremum \alpha. Now set v=V_\alpha. Then v contains an y for every x, such that \phi(x,y,\vec{z}).
□

We now show the converse, these schemes imply replacement.

Lemma: For every ZF-formula \phi(\vec{x}), \forall_{u_1}\ldots\forall_{u_n}\{\left<\vec{x}\right>\in u_1\times\ldots\times u_n|\phi(\vec{x})\}\in V can be shown by \Sigma_0-comprehension and limitation, not using full comprehension.
Proof: Recall that for pairs \left<x,y\right>:=\{\{x,y\},\{x\}\}\}. We show that from u,v\in V follows u\cap v,u\backslash v,u\times v\in V: u\cap v=\{x\in u\cup v| x\in u\wedge x\in v\}, u\backslash v = \{x\in u|x\not\in v\} are sets by \Sigma_0-comprehension. By limitation, there exists a set b such that for all x\in u we have an y\in b with \forall_{z\in v} \left<x,z\right>\in y. That is, b contains a superset of \{x\}\times v for every x\in u, that is \bigcup_{r\in b}\{r\} is a superset of u\times v, thus, u\times v=\{a \in \bigcup_{r\in b}\{r\}| \exists_{x\in u}\exists_{y\in v} a=\{\{x,y\},\{x\}\}\} is a set due to \Sigma_0-comprehension.

We now use structural induction on \phi(\vec{x}).

If \phi(\vec{x})=\bot, then \emptyset is the desired set.

If \phi(\vec{x}) is of the form x_i\in x_j, let u_1,\ldots,u_n be given and let W=\{\left<\vec{x}\right>\in u_1\times\ldots\times u_n|\phi(\vec{x})\}=\{z\in u_1\times\ldots\times u_n|\exists_{x_1\in u_1}\ldots\exists_{x_n\in u_n} (z=\left<x_1,\ldots,x_n\right>\wedge x_i\in x_j)\}, and \exists_{x_1\in u_1}\ldots\exists_{x_n\in u_n} (z=\left<x_1,\ldots,x_n\right>\wedge x_i\in x_j) is a \Sigma_0-formula, which means that W is a set by \Sigma_0-comprehension.

If \phi(\vec{x}) is of the form \phi_1(\vec{x})\wedge\phi_2(\vec{x}), then \{\left<x_1,\ldots,x_n\right>\in u_1\times\ldots\times u_n|\phi(\vec{x})\}=\{\left<x_1,\ldots,x_n\right>\in u_1\times\ldots\times u_n|\phi(\vec{x})\}\cap\{\left<x_1,\ldots,x_n\right>\in u_1\times\ldots\times u_n|\phi(\vec{x})\} and these are both sets by induction.

For \phi(\vec{x})=\phi_1(\vec{x})\rightarrow\phi_2(\vec{x}) notice that \phi(\vec{x})\leftrightarrow \lnot (\phi_1(\vec{x})\wedge\lnot\phi_2(\vec{x})), therefore it is sufficient to show the induction step for negations. Thus, let \phi(\vec{x})=\lnot\phi_3(\vec{x}). Then \{\left<\vec{x}\right>\in u_1\times\ldots\times u_n|\phi(\vec{x})\}=u_1\times\ldots\times u_n \backslash \{\left<\vec{x}\right>\in u_1\times\ldots\times u_n|\phi_3(\vec{x})\} which is a set by induction.

For \phi(\vec{x}) = \forall_y \phi_1(\vec{x},y), by limitation we have a set v\in V with \forall_{x_1\in u_1}\ldots\forall_{x_n\in u_n}((\exists_y \lnot\phi_1(\vec{x},y))\rightarrow\exists_{y\in v}\lnot\phi_1(\vec{x},y)). By induction hypothesis, q=\{\left<\vec{x},y\right>\in u_1\times\ldots\times u_n\times v|\phi_1(\vec{x},y)\}\in V, and therefore a=u_1\times\ldots\times u_n\times v-q=\{\left<\vec{x},y\right>\in u_1\times\ldots\times u_n\times v|\lnot\phi_1(\vec{x},y)\}\in V. Therefore, by \Sigma_0-comprehension, b=\{\left<\vec{x}\right>\in u_1\times\ldots\times u_n|\exists_x\lnot\phi_1(\vec{x})\}=\{z\in u_1\times\ldots\times u_n|\exists_{y\in v}\left<z,y\right>\in a\}\in V, therefore, \{\left<\vec{x}\right>\in u_1\times\ldots\times u_n|\phi(\vec{x})\}=u_1\times\ldots\times u_n-b\in V.
□
Lemma: For \Sigma_0-formulae \phi(\vec{x}) and classes W such that x\in W\Rightarrow x\subseteq W follows \forall_{\vec{x}\in W} (\phi(\vec{x})\leftrightarrow\phi^W(\vec{x})).
Proof: By structural induction. For everything except quantors, the relativization can be looped through. For quantors, we may assume that we always have an existential quantifier, since \forall_x\phi\leftrightarrow\lnot\exists_x\lnot\phi. So let \phi(\vec{x})=\exists_{z\in y}\psi(z,\vec{x},y). We may assume that x\neq y, since otherwise the formula would be equivalent to \bot. Let \vec{x},y\in W, then by induction hypothesis \psi^W(z,\vec{x},y)\rightarrow\psi(z,\vec{x},y), and therefore \phi^W(\vec{x},y)\rightarrow\phi(\vec{x},y). For the other direction, assume \phi(\vec{x},y), that is, there is some z\in y such that \psi(z,\vec{x},y). Then y\in W implies y\subseteq W which implies z\in W, so by induction hypothesis, \psi^W(z,\vec{x},y), and since z\in W we have \exists_{z\in y\cap W}\psi^W(z,\vec{x},y), therefore \phi^W(\vec{x}).
□
Corollary: For \Sigma_0-formulae \psi(\vec{x},\vec{y}) and classes W in which every element is a subset we have \forall_{\vec{y}\in W}((\forall_{\vec{x}}\psi(\vec{x},\vec{y}))\rightarrow\forall_{\vec{x}\in W}\psi^W(\vec{x},\vec{y}) and \forall_{\vec{y}\in W}((\exists_{\vec{x}}\psi(\vec{x},\vec{y}))\leftarrow\exists_{\vec{x}\in W}\psi^W(\vec{x},\vec{y})

Theorem: From \Sigma_0-comprehension and limitation follows replacement.
Proof: Let F be a functor, and u\in v. By limitation we get a v\in V with \forall_{x\in u} ((\exists_y F(x)=y)\rightarrow \exists_{y\in v} F(x)=y). Then \{F(x)|x\in u\}=\{y\in v|\exists_{x\in u} F(x)=y\}\in V by the above Lemma.
□

We finally arrive at...

Proof of Theorem I: "a=>b": (I1) by definition. For (I2), consider the V_\alpha-hierarchy inside W, that is, define W_\alpha := V_\alpha^W. For x\in V,x\subseteq W we can find an \alpha such t hat x\subseteq W_\alpha, and W_\alpha\in W. For (I3), let \phi(x,\vec{z}) be a \Sigma_0-formula and let \vec{z}\in W. Because of (I1) we have \phi(x,\vec{z})\leftrightarrow\phi^W(x,\vec{z}) for all x\in W according to the above lemma. Therefore, for every u\in W, \{x\in u|\phi(x,\vec{z})\}=\{x\in u\cap W|\phi^W(x,\vec{z})\}, which is in W by comprehension.
"b=>a": Trivially, On\cap W is transitive, and as every transitive set of ordinals is an ordinal, either On\cap W\in On or On\cap W = On. Assume On\cap W\in On, then by (I2) we have an y\in W such that On\cap W\subseteq y. But On\cap W = \{x\in y|x\in On\} which is in W by (I3), so On\cap W\in On\cap W. Contradiction. Therefore, On\subseteq W. We show the ZF-axioms. (EXT) and (FUN) hold because of the above Corollary, (NUL) and (INF) hold since \omega,\emptyset\in On\subseteq W.  For (UNI), let x\in W, then x\subseteq W and therefore every y\in x is subset of W, therefore \bigcup_{y\in x}y\in W and according to (I2) we find a superset u\in W. But then, \bigcup_{y\in x}y = \{y\in u|\exists_{z\in x} y\in z\}\in W by (I3). Similar for (PAR). For (POW), let x\in W. Then by (I2), since \mathbb{P}(x)\cap W\subseteq W, there exists an u\in W such that \mathbb{P}(x)\cap W\subseteq u. Then by (I3), \mathbb{P}(x)\cap W=\{z\in u|z\subseteq x\}\in W.
We have proven that replacement can be replaced by \Sigma_0-comprehension and limitation, therefore, we show \Sigma_0-comprehension and limitation in W. For \Sigma_0-comprehension, let \phi(x,\vec{z}) be a \Sigma_0-formula. We have to show that \forall_{\vec{z}\in W}\forall_{u\in W}\{x\in u|\phi^W(x,\vec{z})\}\in W. But by the above Lemma, this is the same set as \{x\in u|\phi^W(x,\vec{z})\}, which is in W according to (I3). For limitation, consider again a \Sigma_0-formula \phi(x,y,\vec{z}). Then we have to show \forall_{\vec{z}\in W}\forall_{\vec{u}\in W}\exists_{v\in W}\forall_{x\in U}((\exists_{y\in W}\phi^W(x,y,\vec{z}))\rightarrow\exists_{y\in v}\phi^W(x,y,\vec{z})). Let \vec{z},u\in W, then there exists a v'\in V such that \forall_{x\in u}((\exists_{y\in W}\phi^W(x,y,\vec{z}))\rightarrow\exists_{y\in v'} (y\in W\wedge \phi^W(x,y,\vec{z}))). By (I2) we get a v\in W such that v'\cap W\subseteq v, which trivially satisfies the above formula.
□
Show comments (Requires JavaScript, loads external content and cookies from Disqus.com)

AC is not refutable in ZF - Part 2
Wed, 05 Oct 2011 13:21:00 GMT

This is part 2 of my series about the irrefutability of the axiom of choice from ZF. It will mainly introduce concepts about set theory.

Set theory is all about collections. While some set theories use elementary objects, ZF only knows sets. It needs no function symbol, but one binary relation symbol \in. Firstly of course, we notice that collections can usually be denoted by propositions with a free variable. Such collections are called classes. The intuition is that a class A associated with a formula B(x) is the collection \{x|B(x)\} (which is of course not possible for all B). We write x\in A for B(x), and sometimes we associate B itself with the class. We write A\not\in B for \lnot A\in B.

Most important, classes are only syntactical objects. We cannot quantify over them. They are only a convenient form of talking about collections, but everything we do with classes could be done logically directly. For example, if we write A\cup B, we could as well talk about the formula A(x)\vee B(x). Especially, we say that two classes are equal when they contain the same elements.

A first important class is the class \emptyset := \{x|\bot\}. It obviously contains no element. It is the empty class, we will axiomatically postulate that it is a set, the empty set.

Furthermore, there is the class V:=\{x|\bot\rightarrow\bot\}, the universe, which contains all sets. It is not a set, it is a proper class.

Another interesting class, which resembles Russel's paradoxon, is the class R:=\{x|x\not\in x\}. It is not a set: Assume it was a set and R\in R. Then R\not\in R. Contradiction, so R\not\in R, but then R\in R. Contradiction. R cannot be a set. R is a proper class.

The duty of ZF is it now to provide a class of sets, by postulating the existence of sets that can be created from other sets. However, the first axiom we deal with does not give us extra powers of creating sets, but limits the existing sets. It is the axiom of extensionality.

Since we did not want to add axioms for equality, we define equality of sets as it is done in Wikipedia:

x=y :\Leftrightarrow \forall_z (z\in x\leftrightarrow z\in y) \wedge \forall_z(x\in z\leftrightarrow y\in z)

Then the extensionality axiom sais that two sets containing the same elements are equal, which can be expressed by

(EXT) \forall_x\forall_y( \forall_z (z\in x \leftrightarrow z\in y) \rightarrow \forall_z(x\in z\leftrightarrow y\in z))

The first axiom giving us a set is the axiom of the empty set. Formally, it can be expressed by \exists_x \forall_y y\not\in x. However, we choose an equivalent, but more convenient notation, using the class V we defined above:

(NUL) \emptyset\in V

Having two sets, we axiomatically postulate the existence of a set containing these two sets, \forall_x\forall_y\exists_z (x\in z\wedge y\in z). Again, we use a more convenient notation

(PAR) \forall_x\forall_y \{x,y\}\in V

As the high-level-notations should be well-known and as it should be clear how they can be rewritten into what we defined in Part 1, we will continue using high-level-notations.

For every set, there is the union of its elements:

(UNI) \forall_x \bigcup_{y\in x}\{y\} \in V

Then there is the axiom of infinity, which gives us the existence of an infinite set, which will turn out to guarantee the existence of the set of finite (ordinal) numbers. If one has never worked with ordinals before, it is rather counter-intuitive, but as soon as ordinals are definet, it should become clear. Essentially, it sais that there is a set containing \emptyset, and for all elements x it contains, it also contains x\cup\{x\}. Therefore, it contains \emptyset,\{\emptyset\},\{\{\emptyset\},\emptyset\},\ldots.

(INF) \exists_u (\emptyset\in u\wedge\forall_x (x\in u\rightarrow x\cup\{x\}\in u))

Then, for every set b we want a powerset \mathbb{P}(b), containing all subsets of b:

(POW) \forall_b \mathbb{P}(b)\in V

A further boundary for sets is the axiom of foundation, which sais that every nonempty set contains an element which is disjoint to itself. From this axiom follows that there are no infinite \ni-chains.

(FUN) \forall_z (z\neq\emptyset\rightarrow\exists_x(x\in z\wedge x\cap z=\emptyset))

For the final axiom, we need an additional concept. Usually, a binary relation can be considered a set of pairs, and a function can be considered a special type of relation. That is, a function is a relation which is left-unique, that is, if it contains (a,b_1) and (a,b_2), then b_1=b_2. We can extend this notion to classes: A class B is called functor, if it contains only pairs of sets, and if (a,b_1)\in B and (a, b_2)\in B implies b_1=b_2 for all a,b_1,b_2.

As functors are classes, there is no way of quantifying over all of them. The final axiom is therefore not really an axiom (even though it is often considered so), but an axiom scheme, describing infinitely many axioms. It sais that if we have a functor and a set, then the image of that set under the functor is also a set. It is called replacement scheme.

(RPL) For every functor F we have \forall_x \{F(y)|y\in x\}\in V

From the replacement scheme follows the comprehension scheme:

Lemma: For every class B and every set x\in V we have B\cap x\in V.
Proof: We can easily define a functor sending every element a onto \{a\} if a\in B, and onto \emptyset otherwise. Applying (RPL) and (UNI) we then get what we want.
□
Lemma: There is no infinite \ni-chain
Proof: Assume we had an infinitely long decreasing chain x_1\ni x_2\ni x_3\ni\ldots. Consider x=\bigcup_i \{x_i\}. For an arbitrary y\in x we can find an i such that y=x_i. Therefore, x_{i+1}\in y\cap x, and so, x violates (FUN). Contradiction.
□

Now we have all axioms of ZF. The critical part, which is the center of our further attention, is the axiom of choice:

(AC) \forall_x \exists_f ((f\mbox{ function on domain }x)\wedge\forall_y((y\in x\wedge y\neq\emptyset)\rightarrow f(y)\in y))

The relevance of this axiom is not immediately clear. It becomes clearer when dealing with well-orderings and ordinals:

Definition: A strict total ordering on a set s is a binary relation R satisfying
  • Transitivity: xRy and yRz imply xRz
  • Trichotomy: xRy or yRx or y=x
  • Irreflexivity: \lnot xRx
for all x,y,z\in s.

Definition: A well-ordering on a set s is a strict total ordering W on s, such that every x\subseteq s has a minimum.

Well-orderings are interesting since their existence for every set is equivalent to the axiom of choice:

Theorem: If every set A has a well-ordering w_A, then the axiom of choice holds.
Proof: Let an arbitrary set A be given. By (UNI), B=\bigcup\limits_{x\in A}x exists, and by assumption, there is a well-ordering w_B. Define f(\emptyset)=\emptyset and let f(x) for x\in A, x\neq\emptyset be the minimum of x regarding w_B. Then this f satisfies the axiom of choice.
□

Theorem: From the axiom of choice follows that every set has a well-ordering

We will not prove this here. A German version of this proof can be found on Wikipedia.

Well-orderings turn out to be extremely useful, therefore, we are interested in classifying them in a simple way. In the usual way we can define order-isomorphisms as structure-preserving bijective functions, and as usual, isomorphism becomes an equivalence relation, and therefore, we want to find representatives for every equivalence class.

Lemma: Let (x,<) be a well-ordering and y\in x. Then (\{z\in x|z<y\},<) is also a well-ordering, and is not isomorphic to (x,<).
Proof: Trivially (\{z\in x|z<y\},<) is also a well-ordering. Assuming there was an isomorphism f:\{z\in x|z<y\}\rightarrow x, then \{z\in x|f(z)\neq z\} is non-empty and contains a smallest element m such that f(m)\neq m. Then there must be some n\in x such that f(n)=m, but as m was minimal and n\neq m, we know that n>m, therefore f(n)>f(m), so m>f(m), which means that f(f(m))=f(m) since m was minimal, and therefore f(m)>f(f(m))=f(m). Contradiction.
□
Definition: A set x is called an ordinal if for all y\in x we have y\subseteq x and x is well-ordered by \in. The class of all ordinals is called \operatorname{On}, we will later prove that it is a proper class.

The following definition of natural numbers are examples for finite ordinals:
  • 0:=\emptyset
  • n+1 := n\cup\{n\}
We call the set of these numbers \omega, it is the smallest infinite ordinal.

Lemma: \emptyset\in x for x\in \operatorname{On}
Proof: x contains an \in-minimum y. Assume there was some z\in y, then also z\in x, and y would not be minimal anymore. Contradiction. Thus, y=\emptyset.
□
Lemma: If y\in x and x\in \operatorname{On}, then y\in \operatorname{On}.
Proof: As y\in x, y\subseteq x, so trivially, y is also well-ordered by \in. Assuming z\in y and t\in z, by transitivity we have t\in y, so every element of y is a subset. y\in \operatorname{On}.
□
Theorem: If x and y are ordinals whose well-orderings regarding \in are isomorphic, then x=y
Proof: Call the isomorphism f. Assuming f\neq id, there must be a minimal z\in x such that f(z)\neq z. Trivially, f(\emptyset)=\emptyset, so z\neq\emptyset. Therefore, there is some t\in z. Trivially, we have f(z) = \{f(t)|t\in z\}=\{t|t\in z\}=z. Contradiction.□

Theorem: Any two ordinals are comparable.

We will not prove this here.

Definition: For a class A we define A^{<\omega} as the collection of finite sequences of sets inside A.

Theorem: There is a bijective functor G:\operatorname{\operatorname{On}}\rightarrow\omega\times \operatorname{\operatorname{On}}^{<\omega}.
Proof: We show that there exists a well-ordering on \omega\times \operatorname{\operatorname{On}}^{<\omega} such that the class of predecessors of every element is a set. From this, the theorem follows directly. Firstly, on \operatorname{\operatorname{On}}^{<\omega}, define an ordering

pRq :\Leftrightarrow (\max(p) < \max(q)) \vee (\max(p) = \max(q) \wedge \operatorname{dom}(p) < \operatorname{dom}(q)) \vee (\max(p) = \max(q) \wedge \operatorname{dom}(p) = \operatorname{dom}(q) \wedge \exists_i\forall_{j<i} (p_i=q_j\wedge p_i<q_j))

, where max(\emptyset)=0. This is a well-ordering: Firstly, it sorts according to the maximum of the sequence, then according to the length, if both are equivalent, then it uses lexicographical ordering. Form \omega\times \operatorname{\operatorname{On}}^{<\omega} now, define \left<n,p\right><\left<m,q\right> :\Leftrightarrow pRq \vee (p=q \wedge n<m).
□
Show comments (Requires JavaScript, loads external content and cookies from Disqus.com)

Tuition Fees
Tue, 04 Oct 2011 09:15:00 GMT

Title: "Tuition Fees" -- Panel 1: Student holding a sign with "Against Tuition Fees!" Adult person saying "How dare you. You cannot work. You cannot pay taxes. You are no productive members of the society. This is why you have to pay tuition fees!" -- "30 Years Later" -- Panel 2: Adult person is shown. Old person with a walking stick is shown, holding a sign "Increase Pensions!", saying "How dare you. I cannot work. I cannot pay taxes. I am not a productive member of the society. That is why you have to pay my pension!"
Show comments (Requires JavaScript, loads external content and cookies from Disqus.com)