I'm self-teaching an intro to set theory course, and came across this exercise: Show that the existence of an infinite set is equivalent to the existence of an inductive set. For the notion of finiteness without reference to natural numbers, we use the given Tarski definition of finiteness:

A set $x$ is finite if, for every non-empty $a\subseteq \mathcal{P}(x)$, there exists a set $b\in a$ that is $\subseteq$-minimal, that is, there is no $c\in a$ such that $c\subsetneq b$. A set is called infinite if, of course, it is not finite.

Now, the right-to-left implication is clear, as it is merely assuming the axiom of infinity and asking to show that there is an infinite set--likely something the author of these notes overlooked, since (of course) the notes up to that point has already established $\omega$ is an infinite set, so only the left-to-right implication needs proving.

Before I begin discussing my issue solving the problem, let me state that I've just looked at a view answered questions about ZFC, minus the axiom of infinity or also with the axiom negated. I haven't seen this specific question, though I've seen it alluded to. I saw a suggestion to use the axiom of choice due to the well-ordering theorem, but in the notes I'm using the well-ordering theorem has not been proven yet. Furthermore, I also shouldn't be able to reference ordinals, as the notes haven't defined ordinals yet (this is the next chapter, actually!). The sequence has been: all of the ZFC axioms, the definition of $\omega$, proofs of the properties of $\omega$ (transitivity, recursive definition, linear ordering by $\in$, etc.) and then the concept of (Tarski) finite sets. With regards to finiteness, I know that, if $x$ is a finite set, subsets of $x$ are finite, union with a finite set $y$ is finite, surjective image of $x$ is finite, and the power set of $x$ is finite. Furthermore, we have proven already that every finite set is the bijective image of a natural number and every infinite set contains an injective image of $\omega$. This is all, of course, assuming the Axiom of Infinity, but I wanted to make sure my allowed tools were known.

Now, in my attempt to search for a solution after being stumped, I found another book on set theory that merely said that, assuming the existence of an infinite set, say, $x$, all we need to do is apply the axiom schema of replacement to the set $\mathcal{F}(x)$ of finite sets of $x$. The specific class function was left unclear, though judging by the alternate definition this book used for finiteness (they switched to existence of bijection with a natural number as the preferred definition), it appears the function they would refer to would be that which sends a finite set to the natural number it is in bijection with. However, without the axiom of infinity, there is no $\omega$ we can refer to as of yet, and hence no (clear, at least to me) way to inductively show that the "bijection-to-a-natural" definition is equivalent to the Tarski definition, which is what the notes I'm using instruct to use. However, once I construct the desired class function $F$, I know the replacement schema implies that the image of $\mathcal{F}(x)$ under $F$ is a set, and can prove from there that it is inductive.

So without $\omega$, how am I to approach defining such a function? Or alternatively, how do I use AC to prove the existence of $\omega$? Any hints on this would be amazing. I would not be content if I had to leave this exercise undone. Apologies in advance if this is deemed a duplicate. Thank you.


Hint: suppose $X$ is infinite. Let $\hat{X}$ be the set of finite subsets of $X$.

  • How do we know $\hat{X}$ exists?

  • Is there a natural map from $\hat{X}$ to the naturals? Is it surjective? (If so, take its image via Replacement to get $\omega$.)

Note that this doesn't use choice anywhere.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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