A Curious Construction: Defining Z-Sets and Their Properties

[Hurkyl]

For each ordinal number i, recurisively define:

$$\begin{equation*}\begin{split} Z_0 = \{ \varnothing \} \\ Z_i = (\bigcup_{j < i} Z_j) \cup \mathcal{P}(\bigcup_{j < i} Z_j) \end{split}\end{equation*}$$

Definition: A set S is a Z-set iff there is an ordinal i such that $S \in Z_i$.

Definition: For any Z-set S, define the "birthday function" B(S) to be the least ordinal i such that $S \in Z_i$.


The class of Z-sets is an interesting class...

First, notice that $i < j \implies Z_i \subseteq Z_j$.

Suppose x and y are Z-sets. Let i = B(x) and j = B(y). Let k be the maximum of i and j. Clearly x and y are both in $Z_k$. Therefore, $\{x, y\} \in Z_{k+1}$.


Suppose S is any set of Z-sets. Let k = \bigcup_{s \in S} B(s). (Recall that ordinal numbers in ZF are sets, and you can union a collection of ordinals to obtain an ordinal larger than any in the collection) All of the elements of S are in $Z_k$, therefore $S \in Z_{k+1}$.


It is vacuously true that if S is any set in $Z_0$, then any s in S is an element of $Z_0$.

Let i be an ordinal number. Suppose that for all j < i, we have that for any $S \in Z_j$ we have $\forall s \in S: s \in Z_j$.

Let $S \in Z_i$. If $S \in Z_j$ for some $j < i$, then by our hypothesis, $\forall s \in S: s \in Z_j \subseteq Z_i$. The only other possibility is that $S \in \mathcal{P}(\bigcup_{j < i} Z_j}$. Therefore, $S \subseteq \bigcup_{j < i}Z_j$, and therefore $\forall s \in S, \exists j < i: s \in Z_j \subseteq Z_i$.

Therefore, $\forall S \in Z_i: \forall s \in S: s \in Z_i$.

By the principle of transfinite induction, this statement must be true:

For any ordinal i and any set S in $Z_i$, every element of S is in $Z_i$.

In other words, if S is a Z-set, then every element of S is a Z-set.

Furthermore, if $S \in Z_i$, we have $\forall s \in S: s \subseteq Z_i$, so $\bigcup S \subseteq Z_i$, therefore $\bigcup S \in Z_{i+1}$.


So what have we proven?

If x and y are Z-sets, then {x, y} is a Z-set.
If x is a Z-set, then the sumset of x is a Z-set.
If x is a Z-set, then the powerset of x is a Z-set.

Also, it is clear that $\varnothing \in Z_0$ and $\mathcal{N} \in Z_\mathcal{N}$ (where I'm using the typical set-theoretic version of the natural numbers)

(In fact, for any ordinal i, $i \in Z_i$)


This looks a lot like the axioms of the pair set, the sum set, the power set, the empty set, and the axiom of infinity! It seems that the class of Z-sets coincides with the class of sets guaranteed to exist by the axioms of Zermelo set theory!

Is that cool or what?

 

[suyver]

I'm way way way out of my league here, but since nobody asked a question yet, I feel I might try one.

I've been trying to understand your definition:
$$\begin{equation*}\begin{split}Z_0 = \{ \varnothing \} \\Z_i = (\bigcup_{j < i} Z_j) \cup \mathcal{P}(\bigcup_{j < i} Z_j)\end{split}\end{equation*}$$
and, to be honest, I have not yet succeeded.

I understand $Z_0$ is the empty set.

I understand that you recursively define $Z_i$ in terms of all the $Z_j$ with $j<i$.

I do not understand what $\mathcal{P}(\bigcup_{j < i} Z_j)$ means. Could you please explain this to me? Also, could you maybe give an example: how do I determine $Z_1$? I start like this:

$$Z_1 = (\bigcup_{j < 1} Z_j) \cup \mathcal{P}(\bigcup_{j < 1} Z_j)$$

$$Z_1 = Z_0 \cup \mathcal{P}(Z_0)$$

$$Z_1=\{ \varnothing \}\cup \mathcal{P}(\{ \varnothing \})$$

and then what?

 

[matt grime]

P(X) means the power set of X.

So Z_1 is the empty set union the power set of the empty set, which contains only one element, it is the set containing the empty set.

So Z_1 is a set with one element.

 

[suyver]

OK, and the powerset of the empty set generates the one new element in this case? Wolfram's Mathworld-site mentiones that:
Given a set S, the power set of S is the set of all subsets of S.

But the set $Z_0$ contains no elements. So how can it's powerset contain an extra element?

Confusing...

 

[matt grime]

The empty set is a subset of every set, including the empty set

 

[suyver]

I'm sorry, I still don't get it.

$$Z_0 = \{ \varnothing \}$$

$$Z_1=\{ \varnothing \}\cup \mathcal{P}(\{ \varnothing \})$$

But, you just said that

The empty set is a subset of every set, including the empty set

So, would that mean that

$$\mathcal{P}(\{ \varnothing \})=\{ \varnothing \}$$ ??

Obviously not, because then I find that

$$Z_1=\{ \varnothing \}\cup \mathcal{P}(\{ \varnothing \})=\{ \varnothing \}\cup\{ \varnothing \}=\{ \varnothing \}$$

which wouldn't make sense to me.


So, my question is: what is $Z_1$? Or $Z_2$?

 

[matt grime]

First, the empty set is denoted $$\varnothing$$ there are n o braces round it.

How many elements does the set {X} contain? It contains one, it has one element, X. That is true even if the element is a set, and even if that set is the empty set.

Now the power set of S is the set whose elements are the subsets of S.

So, there is the empty set, no elements, then there is the power set of it, which is the collection of all subsets of the empty set. There is one and only one subset of the empty set, the empty set itself.

So $$P(\varnothing)={\varnothing}$$

see where the braces now come in? They delimit the set whose elements are inside the braces.

 

[suyver]

OK, I am very close to giving up. I guess that this is just too hard for me (as well as too much off-topic).

Originally posted by matt grime
First, the empty set is denoted $$\varnothing$$ there are n o braces round it.

Then why is Hurkyl's definition $$Z_0 = \{ \varnothing \}$$ and not $$Z_0 = \varnothing$$ ?

How many elements does the set {X} contain? It contains one, it has one element, X. That is true even if the element is a set, and even if that set is the empty set.

Now the power set of S is the set whose elements are the subsets of S.

So, there is the empty set, no elements, then there is the power set of it, which is the collection of all subsets of the empty set. There is one and only one subset of the empty set, the empty set itself.

So $$P(\varnothing)={\varnothing}$$

see where the braces now come in? They delimit the set whose elements are inside the braces.

OK, I think I get this. But it's quite hard (and abstract).


Would it be much work to explicitely write out $Z_1$ and $Z_2$ for me?

 

[matt grime]

You have to be able to distinguish between X as a set, and the set containing X. Can you do that?

eg N, and {N}

N has infinitely many elements, {N} has one element.

now replace X with the empty set. See, no harder.


Note in my last post the braces i wanted to put in didn't appear in the tex element,

it should have read:

$$P(\varnothing) = \{ \varnothing\}$$

 

[matt grime]

Let me write 0 for the empty set, we use this because it is guaranteed to exist.

Z_{zero} = {0}

z_1 = {0} U P({0})

P({0}) = { {0}, 0}

so Z_1 = { 0, {0}}

Z_2 = {0.{0}} U P( {0, {0}})

P( {0 , {0} } ) = { 0, {0} , {{0}} , {0.{0}} }

At least I think that's how it goes. Hopefully Hurkyl is reading this and can correct me.

 

[Hurkyl]

There are two ways to be aesthetic here.

It's cool to start with nothing and have $Z_0 = \varnothing$.

However, I thought it would also be cool for each (Von Neumann) ordinal number to first appear in its Z-set, so I defined $Z_0 = Z_{\varnothing} = \{ \varnothing \}$.


And yes, Matt has written Z_1 and Z_2 correctly.


I'd like to mention that the axiom of separation (aka the axiom of subsets) applied to Z-sets also gives you Z-sets, and I'm thinking with a bit of sneakiness you can prove that the axiom of replacement also gives you only Z-sets. All Z-sets are grounded (satisfy the foundation axiom), so it looks like this is actually a complete model of ZF, within ZF.

 

[Hurkyl]

All right, let's have some fun.


I want to single out a subclass of Z-sets, I'll call them W-sets, recursively by the following condition:

$(\varnothing, T)$ is a W-set if and only every element of T is a W-set.

Notice that $(\varnothing, \varnothing)$ is a W-set. Let's call it $\phi$.


Now, let me define two operators (let's call them a flattening and an enlarging operator) as follows:

$$\mathcal{E}(S) := (\varnothing, \{ \mathcal{E}(T) | T \in S \})$$

$$\mathcal{F}((\varnothing, S)) := \{ \mathcal{F}(T) | T \in S \}$$

These operations are clearly inverses, so they constitute a "bijection" between the class of Z-sets and the class of W-sets.

Now, bijections are very excellent things. For instance, I can define:

$$\begin{equation*}\begin{split} \phi := \mathcal{E}(\varphi) \\ \bigoplus A := \mathcal{E}(\bigcup \mathcal{F}(A)) \\ \mathcal{Q}(S) := \mathcal{E}(\mathcal{P}(\mathcal{F}(S))) \\ A \triangleleft B := \mathcal{F}(A) \in \mathcal{F}(B) \end{split}\end{equation*}$$

(each of these operations could be defined directly too, but I'm too lazy to type them!)

The really nifty thing is that W-sets are also a model of the axioms of ZF, where we use the above symbols to model the ordinary ZF operations!



The net effect is that we've managed to create (within ZF) a model of ZF such that every set has a "tag" on it which says "I'm part of this model!"... but we have lots of other sets to work with that aren't in the model! I get the feeling we can do cool things with this construction, such as model other set theories (such as ZF + things that aren't sets), and I think I see an easy way now to prove that the axiom of foundation is independant of the other axioms of ZF! I bet this sort of thing is what's used to prove the other cool things about set theory (like the continuum hypothesis is independant of the other axioms).

 

[matt grime]

I had a quick look at how the Cohem proved the Continuum hypothesis is independent of ZFC.

Here's a very brief synopsis, possibly contianing factual errors but hopefully correct in spirit:

Form a minimal countable model of ZF; this can be done since there are a finite number of axioms. This model has some odd properties, that one wouldn't think possible such as we can no longer say the power set of N is uncountable, because we adopt a slightly nit-picking definition of power set that isn't the one we'd recognize, and because the class of maps from N to things isn't actually a set in this model. (I hope and pray Organic does not read this.)

In this model we use 'forcing'. Forcing basically amounts to saying that provable theorems are 'compact'. That is to say that, although one can form infinite collections of deductions from the axioms, the countability of the model means that anything that is provable can be proved in a finite subset of the deductions. The proof then amounts to showing that the statement of the continuum hypothesis cannot be reached in a finite number of steps, that we cannot force it to be true.

This is my idiots guide to an idiots guide, so don't take it as anything particularly accurate, but hopefully it expresses the essence of how the proof goes through.

Actually compactness like this has lots of interesting parallels. An infinite set of equations (in some module of some ring) is compact iff every finite subset has a joint solution. An element in a module category is compact if every map to an infinite direct sum factors through a finite subsum - this leads to definitions of A-compactness for any cardinal A - every map from a module to a direct sum factors through a subsum of cardinality strictly less than A, and so compactness become aleph-0 compactness. I don't know if that has a parallel in point set topology or logic - these are definitions in category theory by Neeman. Sorry, wandered off topic a little, but it's food for thought.

 

[Hurkyl]

The text I'm planning on going through does eventually get to the GCH and forcing... it's always more fun to try and figure things out yourself, though. (IMHO)

This model has some odd properties, that one wouldn't think possible such as we can no longer say the power set of N is uncountable, because we adopt a slightly nit-picking definition of power set that isn't the one we'd recognize, and because the class of maps from N to things isn't actually a set in this model.

I briefly skimmed my text and couldn't find a restatement of the power set axiom...

I'm having difficulty seeing how this works. (Within any model), the class of maps from N to P(N) would be a subclass of P(P(P(N))), and thus a set. And in any case, Cantor's proof that there is no bijection from N to P(N) works even for 'bijections' that are proper classes.


In fact, the only way I see it is if N is a finite set (so P(N) is finite). Of course, through finite application of the axioms, we can only construct a finite number of elements of N and P(N)... maybe it is making sense.

 

[matt grime]

Typically I can't find the web page that the original idiot's guide was on. The relevant quote began something like 'but let's examine what the power set axiom actually states' and went on to give some strings of symbols that instantly made me switch off. When I can remember where it is I will post it, or the magic phrase that makes google spit out the right result.

and as if by magic the address appears in my url bar as soon as I type the letter whttp://www-math.mit.edu/~tchow/mathstuff/forcingdum

 

[Hurkyl]

I had thought about it, and had arrived at that definition; the power set contains all subsets that exist (in the model).

I've been trying it work it out on my own, and I thought I had it, but I still run into problems with Cantor's argument.

I figure we can enumerate all logical functions, and thus enumerate everything given by the axiom of subsets (and every subset can be given by the axiom of subsets), and thus enumerate P(N). The problem is that if this enumeration can be written as a logical function (and it would seem it has to be), then Cantor's argument rears its ugly head.

So, there's some silly detail in the way; my guess at the moment is that it has something to do with the recursion theorem.

 

[matt grime]

I think the problem can, and its solution, can be summed up as:

The power set is a countable set in a larger universe, but the mapping set in the larger universe is not a set in the model, hence it is 'uncountable in the model' whilst being countable in our universe. Search for 'Skolem's Paradox' in the article and check the paragraph above it.

Definitely a headache this stuff. Still as it only deals with aleph-0 and aleph-1 it is smaller than the universe in the paper I'm reading which contains lovely phrases like 'for $$\gamma$$ an enormous enough cardinal'

 

[Hurkyl]

That wasn't the problem I was having; I wasn't completely convinced that you can't explicitly construct a formula for the enumeration. I'm still not, but I'm a little more willing to believe it now.