I Understanding the Induction Axiom: Notation & Equivalence

[Danijel]

So , what I was wondering about was a slight difference in notation, for which I am not certain if correct (mine, in particular.).
The induction axiom says: If M is a subset of ℕ, and if holds that:
a)1∈M
b)(∨n∈ℕ)(n∈M→s(n)∈M)
then M=ℕ.
Now my question is: why do we write (∨n∈ℕ)(n∈M→s(n)∈M), instead of (∨n∈M) s(n)∈M? Are these equivalent? Because, if we say n ∈ M, we consider that n∈ℕ and n∈M, since M⊆ℕ.
Thank you.

 

[fresh_42]

So , what I was wondering about was a slight difference in notation, for which I am not certain if correct (mine, in particular.).
The induction axiom says: If M is a subset of ℕ, and if holds that:
a)1∈M
b)(∨n∈ℕ)(n∈M→s(n)∈M)
then M=ℕ.
Now my question is: why do we write (∨n∈ℕ)(n∈M→s(n)∈M), instead of (∨n∈M) s(n)∈M?

The first is rigorous, the second a bit sloppy. Induction means, we assume $n \in \mathbb{N}$ and $n \in M$ in order to conclude $s(n)\in M$. To write for all $n \in M$ is shorter, but $M \subseteq \mathbb{N}$ is suppressed.

Are those equivalent?

I'd say yes. However, since we are in the field of logic here, I would prefer the former over the latter. The explicit deduction $\rightarrow$ makes the induction principle more clear.

Because, if we say n ∈ M, we consider that n∈ℕ and n∈M, since M⊆ℕ.

 

[Stephen Tashi]

Now my question is: why do we write (∨n∈ℕ)(n∈M→s(n)∈M), instead of (∨n∈M) s(n)∈M? Are these equivalent?
.

No, the two statements are not equivalent. For example, for each natural number n it is True that "If n < 0 then the successor of n is < 0". The Truth of that statement follows from the convention that an if-then statement is True whenever the if-clause is False. By contrast, the statement "For each natural number n, n < 0" is False.

This illustrates why step a)$1 \in M$ is a crucial part of proof by induction.

Note that $M \subset N$ does not rule out the possibility that $M$ is the empty set.

 

[fresh_42]

Note that $M \subset N$ does not rule out the possibility that $M$ is the empty set.

But if $M$ is the empty set, both statements are still true. (!?)

 

[Danijel]

This may be a silly way to approach it, but I thought of this.
(∀n∈M) s(n)∈M is by definition equivalent to (∀n)(n∈M →s(n)∈M), which is obviously not equivalent to (∀n∈ℕ)(n∈M →s(n)∈M). Another way to think about it is that these can become equivalent if we consider a few things, which is not what we usually do.

 

[Erland]

This may be a silly way to approach it, but I thought of this.
(∀n∈M) s(n)∈M is by definition equivalent to (∀n)(n∈M →s(n)∈M), which is obviously not equivalent to (∀n∈ℕ)(n∈M →s(n)∈M). Another way to think about it is that these can become equivalent if we consider a few things, which is not what we usually do.

These three sentences are in fact equivalent in this case, since it is assumed that M⊆ℕ.
But I agree with Fresh 42 that the form (∀n∈M) s(n)∈M is not good pedagogically, since it seems less clear with this form that inductionn means going from n to s(n).

 

[Stephen Tashi]

But if $M$ is the empty set, both statements are still true. (!?)

I see your point. Yes both are true if the notation "$\forall n \in M"$ is interpreted to mean "For each n, (if $n \in M$ then...)" With that interpretation, the two statements are equivalent by definition.

In the formal logic I have seen, the notation for quantifiers is in the form $(\forall x) (...)$ rather than having any operation immediately after the quantifier - so we would not write "$\forall x \in M$" for "$\forall x > 0$". However, people also use the notation for quantifiers informally, as if "$\forall$" can be used to abbreviate the English phrase "for each" in any English sentence where "for each" occurs.