Proving the Inclusion Property for Sets in Axiomatic Set Theory

[Aryth1]

For reference, my class is using The Joy of Sets by Keith Devlin. I've been asked to solve this as a practice problem, but this stuff is really confusing over the first read or two and I've yet to see any example proofs and I think I'll just mess it up.

A link to the book can be found here if you need some context: The Joy of Sets

The question is 2.2.1 (Chapter 2, Section 2, Problem 1).

Show that if [math]y\in V_{\alpha}[/math] and [math]x\in y[/math], then [math]x\in V_{\alpha}[/math].

I think this book is strange since it references sets as lower case letters, yet, if I'm not mistaken [math]V_{\alpha}[/math] are sets in a hierarchy of sets created by the axioms of set theory...

I really have no idea how to approach this problem. Any hints to get started would be very helpful.

 

[Deveno]

I don't know if this is correct, but I think it goes something like this:

If $y \in V_{\alpha}$ then $y = V_{\beta}$ for some (limit) ordinal $\beta < \alpha$.

Similarly, since $x \in V_{\beta} (= y)$, then $x = V_{\gamma}$ for some (limit) ordinal $\gamma < \beta$.

It follows then, that $\gamma < \alpha$, so $x \in V_{\alpha}$, since the ordinals are ordered.

 

[Aryth1]

I don't know if this is correct, but I think it goes something like this:

If $y \in V_{\alpha}$ then $y = V_{\beta}$ for some (limit) ordinal $\beta < \alpha$.

Similarly, since $x \in V_{\beta} (= y)$, then $x = V_{\gamma}$ for some (limit) ordinal $\gamma < \beta$.

It follows then, that $\gamma < \alpha$, so $x \in V_{\alpha}$, since the ordinals are ordered.

It turns out that's what we were trying to show! We don't have that fact yet. In particular, the results of this problem prove that, if [math]\alpha < \beta[/math], then [math]V_{\alpha} \subseteq V_{\beta}[/math].

The second problem was to show that, in general, [math]V_{\alpha} = \bigcup_{\alpha < \beta} \mathcal{P}(V_{\beta})[/math].

Then, we use the results of those to show that [math]\alpha < \beta[/math] implies [math]V_{\alpha} \subset V_{\beta}[/math]

I figured out the proof for the first one... And I'm slowly trudging through the second one. I'll post again if I get any further trouble. I appreciate your reply.

 

[Aryth1]

I need some help again! We have the following facts:

$V_0 = \emptyset$
If $\alpha < \beta$, then $V_{\alpha} \subseteq V_{\beta}$
$V_{\alpha} = \bigcup_{\beta < \alpha} \mathcal{P}(V_{\beta})$

and we need to show that:

If $\alpha < \beta$, then $V_{\alpha}\subset V_{\beta}$.

My initial attempt at a proof is this:

We need to show that, if $\alpha < \beta$, then $V_{\alpha} \subset V_{\beta}$. So, suppose that $V_{\alpha}\not\subset V_{\beta}$, then $V_{\alpha} = V_{\beta}$. Then, $\forall \gamma$ so that $\alpha \leq \gamma \leq \beta$, $V_{\alpha} \subseteq V_{\gamma}$ and $V_{\gamma}\subseteq V_{\beta} = V_{\alpha}$ and so $V_{\alpha} = V_{\gamma} = V_{\beta}$. In particular, $V_{\alpha} = V_{\alpha + 1} = \mathcal{P}(V_{\alpha})$, which means that $V_{\alpha}\in\mathcal{P}(V_{\alpha})$ and so $V_{\alpha} \in V_{\alpha}$.

From here, I'm not sure what to do. I wanted to let $\alpha$ be the smallest ordinal so that $V_{\alpha} \in V_{\alpha}$ and arrive at a contradiction from there, but if $\alpha = 0$, most everything I can think of fails since $0$ is the minimal ordinal.

Any ideas about where to go from here would be greatly appreciated!

 

[Deveno]

You do realize that for any set $A$, we have: $A \not\in A$, yes?

In particular, $\emptyset \not\in \emptyset$ since the empty set HAS no elements.

There are "alternative set theories" for which this is NOT true, but it IS true for Zermelo-Fraenkel set theory (axiom of regularity, I think it is).

Basically, there is no "infinitely nested set":

$S = \{a,\{a,\{a,\dots\}\}\}$.

Put another way, the sets $A = \{a\}$ and $B = \{A\}$ are distinct. It matters "how many brackets there are".

 

[Aryth1]

You do realize that for any set $A$, we have: $A \not\in A$, yes?

In particular, $\emptyset \not\in \emptyset$ since the empty set HAS no elements.

There are "alternative set theories" for which this is NOT true, but it IS true for Zermelo-Fraenkel set theory (axiom of regularity, I think it is).

Basically, there is no "infinitely nested set":

$S = \{a,\{a,\{a,\dots\}\}\}$.

Put another way, the sets $A = \{a\}$ and $B = \{A\}$ are distinct. It matters "how many brackets there are".

Thanks for your response!

I get that, but apparently my proof doesn't stop there. In the language of axiomatic set theory, the expression that a set is in itself is not invalid. The purpose of this proof is to show that that inclusion can't happen, apparently.

 

[Deveno]

As I recall the precise statement of the axiom of regularity goes as follows:

For all sets $X \neq \emptyset$ there exists a set $Y$ such that $Y \in X$ and $X \cap Y = \emptyset$.

If we apply this axiom to the set $\{A\}$ (the set whose sole member is the set $A$), we are guaranteed by the axiom that there is some $Y \in \{A\}$ with $Y \cap \{A\} = \emptyset$.

Since $\{A\}$ only has one element, the existence of $Y$ means that $Y$ must BE $A$. Hence:

$A \cap \{A\} = \emptyset$.

Now if $A \in A$, then we have that $A \in A \cap \{A\}$, a contradiction to the axiom (because there is NO set $A$ with $A \in \emptyset$).

*******

Now, if you forego that axiom, then sure, you're kinda stuck. It turns out that this axiom is equivalent to saying:

$\displaystyle \bigcup_{\alpha} V_{\alpha}$ is not a set (I cannot prove this, but people smarter than me say it's so).

This, in fact, is sort of my big beef with set theory: it rather begs the question of what sets "are". That is, the entire construction of the cumulative hierarchy is not, itself, a set, so one needs a "larger theory" (of classes, for example) to distinguish "non-set classes" from "set-classes" (classes which are also sets). It gets even worse, the theory of classes suffers from the same problem: the collection of all (proper) classes is "too big" to be a class itself (such an entity would be, of course, unimaginably infinite).

Practically speaking, this doesn't bother "most mathematicians", because MOST sets are "small enough" (like the real numbers, for example) so that we can imagine a suitable "context" to do "local set theory" in (such "contexts" are often given the vague name: "universe of discourse"). For example, if $\omega$ is the ordinal type of the natural numbers, the set $V_{\omega + \omega}$ is "big enough" to do most things in ($V_{\omega+1}$ is the same size as the real numbers, and $V_{\omega+2}$ is typically enough to do calculus in). /rant.

******

Defining sets in terms of ordinals doesn't help matters much, it just puts the burden on the setclass of ordinal numbers (which has the same problem). In your problem, I think what you may want to do is show that if:

$V_{\alpha} \in V_{\alpha}$

that:

$\alpha < \alpha$, a contradiction (you don't say how you define "<" but one assumes it is "anti-reflexive").

 

[Aryth1]

As I recall the precise statement of the axiom of regularity goes as follows:

For all sets $X \neq \emptyset$ there exists a set $Y$ such that $Y \in X$ and $X \cap Y = \emptyset$.

If we apply this axiom to the set $\{A\}$ (the set whose sole member is the set $A$), we are guaranteed by the axiom that there is some $Y \in \{A\}$ with $Y \cap \{A\} = \emptyset$.

Since $\{A\}$ only has one element, the existence of $Y$ means that $Y$ must BE $A$. Hence:

$A \cap \{A\} = \emptyset$.

Now if $A \in A$, then we have that $A \in A \cap \{A\}$, a contradiction to the axiom (because there is NO set $A$ with $A \in \emptyset$).

*******

Now, if you forego that axiom, then sure, you're kinda stuck. It turns out that this axiom is equivalent to saying:

$\displaystyle \bigcup_{\alpha} V_{\alpha}$ is not a set (I cannot prove this, but people smarter than me say it's so).

This, in fact, is sort of my big beef with set theory: it rather begs the question of what sets "are". That is, the entire construction of the cumulative hierarchy is not, itself, a set, so one needs a "larger theory" (of classes, for example) to distinguish "non-set classes" from "set-classes" (classes which are also sets). It gets even worse, the theory of classes suffers from the same problem: the collection of all (proper) classes is "too big" to be a class itself (such an entity would be, of course, unimaginably infinite).

Practically speaking, this doesn't bother "most mathematicians", because MOST sets are "small enough" (like the real numbers, for example) so that we can imagine a suitable "context" to do "local set theory" in (such "contexts" are often given the vague name: "universe of discourse"). For example, if $\omega$ is the ordinal type of the natural numbers, the set $V_{\omega + \omega}$ is "big enough" to do most things in ($V_{\omega+1}$ is the same size as the real numbers, and $V_{\omega+2}$ is typically enough to do calculus in). /rant.

******

Defining sets in terms of ordinals doesn't help matters much, it just puts the burden on the setclass of ordinal numbers (which has the same problem). In your problem, I think what you may want to do is show that if:

$V_{\alpha} \in V_{\alpha}$

that:

$\alpha < \alpha$, a contradiction (you don't say how you define "<" but one assumes it is "anti-reflexive").

Thanks again for replying!

I understand where the proof should go now and have a general idea of how to get there. You were right to suspect that I can't use the axiom of regularity (I can't). It's interesting, though, my professor made three attempts to prove this and the proof she arrived at didn't really satisfy my questions. That's why I'm attempting this myself to see if there are other ways.

Thanks again, your post was a big help.

 

[Deveno]

Here is an interesting counter-example if one does not take the axiom of regularity as given:

Define our "sets" as infinite sequences: $a_1,a_2,a_3,\dots$.

Define a head of a sequence as any finite truncation: $a_1,a_2,\dots,a_n$.

Define a tail of a sequence as the new sequence formed by removing a head.

Now, consider the following sequence:

$S = 1,0,1,0,1,0,\dots$

If we choose the head $H = 1,0$, we have:

$\text{tail}_H(S) = S$, that is $S \in S$.

While this might seem somewhat contrived, a similar method is employed in proving the limit of a geometric series, and in proving results in "formal power series".

ZF(C) is often called "well-founded" set theory, it supposes we build "up", not "down". IF we have an infinite set to start with (like, for example, the natural numbers), there is no reason to assume a priori we cannot go "both ways" in creating sets.

Avoiding paradoxical sets like $R = \{x: x\not\in x\}$ becomes a bit more of a challenge in this scenario.