Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Let $V_\omega$ denote the set of all hereditarily finite sets. A set $S$ is called hereditarily finite if and only if its transitive closure is finite, that is, $TC(S) = \bigcup \{ S, \bigcup S, \bigcup \bigcup S, \dots \}$ is finite. Let $P(S)$ denote the power set of $S$ and let $\omega$ denote the natural numbers.

I am trying to understand what $V_\omega$ looks like and to this end I thought I could work out the relationship between $V_\omega$ and $P(\omega)$:

Of course, since $V_\omega$ is a model of $ZFC$ without the axiom of infinity, neither $\omega$ nor $P(\omega)$ are elements of $V_\omega$. Hence $P(\omega) \nsubseteq V_\omega$.

On the other hand, $\{\{\{\varnothing\}\}\}$ is in $V_\omega$ but not in $P(\omega)$. Hence $V_\omega \nsubseteq P(\omega)$.

So this is not going to give me any information about $V_\omega$. Yet, since hereditary finiteness is a stronger condition than finiteness ($\{\omega\}$ is a finite set that is not hereditarily finite) I am tempted to think that perhaps $V_\omega$ might somehow be in bijection with a subset of $P(\omega)$.

Question: Is there such a bijection? If not: what's a good intuition to think about $V_\omega$? What does $V_\omega$ look like?

Thanks for your help.

share|cite|improve this question
I think you used the wrong "not subset" symbols. Is it supposed to be $\nsubseteq$ (\nsubseteq) instead of $\subsetneq$ (\subsetneq)? – kahen Nov 26 '12 at 13:07
@kahen Oops, typo. Thanks for pointing it out! – Rudy the Reindeer Nov 26 '12 at 13:09
"Of course, since $V_\omega$ is a model of $ZFC$ without the axiom of infinity, neither $\omega$ nor $P(\omega)$ are elements of $V_\omega$." That's not really valid. Every model of ZFC is also, in particular, a model of ZFC$-$Infinity, but we cannot conclude that $\omega$ or $\mathcal P(\omega)$ cannot be elements of any model of ZFC. – Henning Makholm Nov 26 '12 at 13:26
@HenningMakholm Did I just phrase it badly? How about if I replace ZFC with ZFC' := ZFC $\setminus \{$ Axiom of Infinity $\}$? – Rudy the Reindeer Nov 26 '12 at 13:35
@Matt: That makes no difference -- removing axioms is never going to stop anything from being a model. I suspect what you're aiming for is ZFC$-$Infinity$+(\neg$Infinity$)$, but it would be easier just to note that $\omega$ and $\mathcal P(\omega)$ are both infinite, and therefore in particular not hereditarily finite. – Henning Makholm Nov 26 '12 at 13:38
up vote 4 down vote accepted

$V_\omega$ consists of exactly the sets you can write down in finite space using only the symbols {, }, and ,.

It is in bijection with $\omega$, by the rule

$$f:\omega\to V_\omega \qquad f(n) = \{f(a_1),f(a_2),\ldots,f(a_{k_n})\}$$ where $n=2^{a_1}+2^{a_2}+\cdots+2^{a_{k_n}}$ and all the $a_i$s are different.

(This bijection provides the standard proof that Peano Arithmetic is equiconsistent with ZFC$-$Infinity).

share|cite|improve this answer
Thank you! So one can think of $V_\omega$ as $\omega$ if one is talking about models? – Rudy the Reindeer Nov 26 '12 at 13:37
@Matt: Yes. Except for purposes where the difference is important, of course. :-) – Henning Makholm Nov 26 '12 at 13:41
Thank you very much : ) – Rudy the Reindeer Nov 26 '12 at 13:42
@Matt: You could also read about the enumeration in this old thread. ($R(\omega)$ is also used to denote the same set as $V_\omega$.) – Asaf Karagila Nov 26 '12 at 16:58
@AsafKaragila Thank you for pointing this out! – Rudy the Reindeer Nov 26 '12 at 20:44

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.