0
$\begingroup$

I'm now on page 40 of a set theory book and I've hit the natural numbers. I think the book has oversimplified some things.

The successor of a set $x$ is defined to be $S(x)=x\cup\{x\}$

A set $I$ is inductive if:

  • $0\in I$
  • $n\in I\implies (n+1)\in I$ where $(n+1)=S(n)$ (it's just notational niceness)

The natural numbers are defined as follows:

$\mathbb{N}=\{x|x\in I \forall\text{ inductive sets }I\}$

APPARENTLY this leaves "the only remaining question: whether there are any inductive sets at all"

This leads to "the axiom of infinity: AN inductive set exists"

This is where I get confused, surely we have at least one inductive set already, we have axioms that state: there is an empty set, what makes sets equal, and the axiom of union, from the axiom of schema of comprehensions we can define inductiveness as a property surely

So I think we actually have one inductive set from the axioms already

Then Lemma 1.4 happens: "$\mathbb{N}$ is inductive, and if $I$ is any inductive set, then $\mathbb{N}\subset I$."

This I have a problem with.

My approach

Right now we have a fixed definition of $S$, let us generalise this. (I see S functions as iterators really (programming terminology))

Lets consider $S_1=S\circ S$ ("even numbers") (I wanted to define the odd but you can "pretend 0" is the first odd, then it all follows.

I want to see a proof that "Any two (increasing) recursively defined sequences that do not converge and start at zero have an inductive set of points in common"

As without this only 0 would be in all inductive sets.

Please help me solve this.

$\endgroup$
  • 1
    $\begingroup$ The empty set and the axiom of union only give you finite sets, as you are only “allowed” to use the axioms finitely many times to create sets. Comprehensions only let you pick subsets of a set for a given property. None of this allows you to actually create an inductive set. Can you clarify the lemma – does it say that, if there is an inductive set $I$ such that $ℕ ⊂ I$, then $ℕ$ is inductive, too? $\endgroup$ – k.stm Dec 6 '14 at 21:21
  • $\begingroup$ How do we have one inductive set already? From the axioms we have $\emptyset$, (which we call $0$), $s(\emptyset)$ (which we call $1$), $s(s(\emptyset))$ (which we call $2$) etc. It does not automatically follow that there is some set which contains all of these. What one would want to do is consider the sets $\{0\},\{1\},\{2\},\ldots$, and take their union. But what is the indexing set? You cannot say $\mathbb{N}$, because that is not defined without the axiom! $\endgroup$ – Trevor J Richards Dec 6 '14 at 21:23
  • $\begingroup$ @k.stm the lemma says N is inductive. if I is any inductive set then N subset I" can you edit for me please, I'm on my phone now and it'd be painful to do it myself. $\endgroup$ – Alec Teal Dec 6 '14 at 21:23
  • $\begingroup$ @TrevorRichards I don't see what you mean, why can't this be a property, why can't we have "inductive set" as a property, much like we have topologies (which is a set with a different property, or sigma-algebras) $\endgroup$ – Alec Teal Dec 6 '14 at 21:25
  • $\begingroup$ @AlecTeal What do you mean when you say "property"? Topologies are constructed, however as k.stm said above, you cannot construct something in infinitely many steps. If you want to construct something infinite in finitely many steps, you have to know something infinite exists already (so that you can, for example, take the union over an infinite number of sets). $\endgroup$ – Trevor J Richards Dec 6 '14 at 21:28
2
$\begingroup$

Actually, it is very unclear to me what you’re asking, but I have a feeling, this might be your problem which you want to be resolved:

One might wonder how this lemma can possibly be true since there are so many sets on which you can perform induction – not only $ℕ_0$.

Intuitively one recognizes not only $ℕ_0 = \{0,1, 2, 3, …\}$, but also $$\{0, 2, 4, …\} \quad\text{and}\quad \{0, 3, 6, 9, …\}$$ as inductive sets – probably because one is used to carry out inductions on such sets as well, not only on $ℕ_0$. One is inclined to think that these are inductive sets as well, just corresponding to $S^2$ and $S^3$ respectively.

But they are not. There is an issue to this:

Inductive sets are explicitly just defined only for the successor function $S(n) = n ∪ \{n\}$ and not any other successor functions. The lemma just doesn’t make any statements about more generalized notions of inductive sets with e.g. $S^2$ or some other successor function $S'$. It doesn’t care.

If that’s your problem, think of it that way: An inductive set has to contain $0 = ∅$, and therefore $1 := 0 ∪ \{0\} = \{∅\}$, and therefore $2 := 1 ∪ \{1\} = \{∅,\{∅\}\}$, and so on. So it has to contain at least $ℕ_0 = \{0, 1, 2, 3, …\}$ as a subset. But this isn’t a proof, of course. The lemma just states that this is really true and that $ℕ_0$ itself is such an inductive set.

And if this isn’t your problem, I think you should clarify your question.

(By the way, I write $ℕ_0$ because $0$ is not a natural number.)

$\endgroup$
  • $\begingroup$ This has helped, certainly more than nothing, but I'm confused by the entire of what I posted, I've basically given you what the book says, I need my understanding corrected sufficiently to go "Oh, now I see why the definition of natural numbers makes sense" rather than just taking your (or the books) word for it. $\endgroup$ – Alec Teal Dec 6 '14 at 22:02
  • $\begingroup$ @AlecTeal Okay, well, good luck with this then. That’s all of the time I’m investing in this question. I’m tired and I actually don’t have much time this weekend. $\endgroup$ – k.stm Dec 6 '14 at 22:04
  • $\begingroup$ Thanks for trying I appreciate it $\endgroup$ – Alec Teal Dec 6 '14 at 22:05

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.