Enderton 3.1 problem 1 (p.193)

Let $\displaystyle A_S^*$ be the set of sentences consisting of S1, S2, and all sentences of the form

$\displaystyle \phi(0) \rightarrow \forall v_1(\phi(v_1) \rightarrow \phi(Sv_1)) \rightarrow \forall v_1 \phi(v_1),$

where $\displaystyle \phi$ is a wff (in the language of $\displaystyle N_S$) in which no variable except $\displaystyle v_1$ occurs free. Show that $\displaystyle A_S \subseteq \text{Cn }A_S^*$. Conclude that $\displaystyle \text{Cn }A_S^* = \text{Th }N_S$. (Here $\displaystyle \phi(t)$ is by definition $\displaystyle \phi_t^{v_1}$. The sentence displayed above is called the *induction axiom* for $\displaystyle \phi$.)

The necessary definitions can be found here (especially, page 2, slide 7).

================================================== =======

We show that if $\displaystyle \psi \in A_S$, then $\displaystyle \psi \in \text{Cn }A_S^*$. Therefore, we show each $\displaystyle S1, S2, S3, S4.1, S4.2 \ldots, S4.n $ is a sentence in $\displaystyle \text{Cn }A_S^*$. If $\displaystyle \psi = S1$ (resp. $\displaystyle S2)$, $\displaystyle \psi \in \text{Cn }A_S^*$ by assumption.

S3 asserts that any nonzero number is the successor of somthing.

How do I show that each S3, S4.1, S4.2, ... , and S4.n is a sentence in $\displaystyle \text{Cn }A_S^*$?

From there, how do I conclude $\displaystyle \text{Cn }A_S^* = \text{Th }N_S$?

Re: Enderton 3.1 problem 1 (p.193)

The sentence schema you're given is the definition of the principle of finite induction. It should be sufficient to derive the other axioms from the first two and induction.

Re: Enderton 3.1 problem 1 (p.193)

If T is a set of sentences, is Cn T the set of all sentences that can be derived from T?

Quote:

Originally Posted by

**Annatala** The sentence schema you're given is the definition of the principle of finite induction. It should be sufficient to derive the other axioms from the first two and induction.

Yes. Usually it is sufficient to write the proofs informally. The study of first-order logic is supposed to convince one that reasonably detailed informal proofs cab be converted to formal derivations. Just write carefully the induction statement (i.e., the property P(n) such that you need to prove $\displaystyle \forall n\,P(n)$), the base case, the induction hypothesis, etc. Let us know about the concrete difficulties you are having.

Quote:

Originally Posted by

**logics** From there, how do I conclude $\displaystyle \text{Cn }A_S^* = \text{Th }N_S$?

If my assumption about Cn above is true, then for any sets T, S, if $\displaystyle T\subseteq\mathop{\mathrm{Cn}} S$, then $\displaystyle \mathop{\mathrm{Cn}} T\subseteq\mathop{\mathrm{Cn}} S$. So, $\displaystyle \mathop{\mathrm{Cn}} A_S\subseteq\mathop{\mathrm{Cn}} A^*_S$. Also, $\displaystyle \mathop{\mathrm{Cn}} A^*_S$ is satisfiable, so you can use the reasoning of the theorem on slide 11.

Re: Enderton 3.1 problem 1 (p.193)

Quote:

Originally Posted by

**Annatala** The sentence schema you're given is the definition of the principle of finite induction. It should be sufficient to derive the other axioms from the first two and induction.

I don't understand what you mean by that.

For example, how do you show that $\displaystyle S3$ is a sentence in $\displaystyle \text{Cn }A_S^*$ by using the first two and induction?

Re: Enderton 3.1 problem 1 (p.193)

The set of consequences of $\displaystyle \Sigma$, $\displaystyle \text{Cn }\Sigma$, is defined as

$\displaystyle \text{Cn }\Sigma = \{\sigma | \Sigma \models \sigma\}=\text{Th Mod }\Sigma$.

In the textbook, we have $\displaystyle \text{Cn }A_S = \text{Th }N_S $.

I have not figured out how to prove the first part yet, i.e., $\displaystyle A_S \subseteq \text{Cn }A_S^*$.

Re: Enderton 3.1 problem 1 (p.193)

Quote:

Originally Posted by

**logics** For example, how do you show that $\displaystyle S3$ is a sentence in $\displaystyle \text{Cn }A_S^*$ by using the first two and induction?

Induction here implies that the only objects in the universe are the ones you can get to through successor, so you do it like this:

Take the property "this object is either zero, or is the successor of some number x". You would agree this is S3 I hope. Well, induction is easy:

1) Zero meets this property. (base)

2) For any number y, if y meets this property, then Sy meets this property. (inductive step)

3) By FPI, all objects meet this property. :)

Re: Enderton 3.1 problem 1 (p.193)

Quote:

Originally Posted by

**Annatala** Induction here implies that the only objects in the universe are the ones you can get to through successor, so you do it like this:

Take the property "this object is either zero, or is the successor of some number x". You would agree this is S3 I hope. Well, induction is easy:

1) Zero meets this property. (base)

2) For any number y, if y meets this property, then Sy meets this property. (inductive step)

3) By FPI, all objects meet this property. :)

I don't think your 2) is the inductive hypothesis. Your 2) is basically what we need to prove.

Do you mean

$\displaystyle \forall y_1(y_1 \neq 0 \rightarrow \exists x\text{ } y_1=Sx) \rightarrow \forall y_1(Sy_1 \neq 0\rightarrow \exists x \text{ } Sy_1 = Sx) \in \text{Cn }A_S^*$, where

$\displaystyle \forall y_1(y_1 \neq 0 \rightarrow \exists x \text{ } y_1=Sx) \in \text{Cn }A_S^*$ is the inductive hypothesis?

How do you prove this?

Re: Enderton 3.1 problem 1 (p.193)

Quote:

Originally Posted by

**logics** I don't think your 2) is the inductive hypothesis. Your 2) is basically what we need to prove.

Do you mean

$\displaystyle \forall y_1(y_1 \neq 0 \rightarrow \exists x\text{ } y_1=Sx) \rightarrow \forall y_1(Sy_1 \neq 0\rightarrow \exists x \text{ } Sy_1 = Sx) \in \text{Cn }A_S^*$, where

$\displaystyle \forall y_1(y_1 \neq 0 \rightarrow \exists x \text{ } y_1=Sx) \in \text{Cn }A_S^*$ is the inductive hypothesis?

How do you prove this?

No, my approach is correct: I was trying to lead you there without going all the way.

You're allowed to assume all sentences of the form:

$\displaystyle \phi(0) \rightarrow \forall v_1(\phi(v_1) \rightarrow \phi(Sv_1)) \rightarrow \forall v_1 \phi(v_1)$

Before we begin the induction, we define $\displaystyle \phi_0 \leftrightarrow (\exists x,y (x = 0 \vee x = Sy))$ and plug it into the sentence for $\displaystyle \phi$.

Using the above sentence, we can prove $\displaystyle \phi_0$ holds for zero. We can also prove that if it holds for some number, it holds for the successor of that number (because of how we defined $\displaystyle \phi_0$ this is always true). Based on the expression above, this means $\displaystyle \forall v_1 \phi_0(v_1)$: every number is either zero or a successor. But this is exactly what we wished to show.

Does that help? :) Try the others on your own if you get it now.

Re: Enderton 3.1 problem 1 (p.193)

Quote:

Originally Posted by

**Annatala** Take the property "this object is either zero, or is the successor of some number x". You would agree this is S3 I hope. Well, induction is easy:

1) Zero meets this property. (base)

2) For any number y, if y meets this property, then Sy meets this property. (inductive step)

3) By FPI, all objects meet this property. :)

Quote:

Originally Posted by

**logics** I don't think your 2) is the inductive hypothesis. Your 2) is basically what we need to prove.

That's why I said:

Quote:

Originally Posted by

**emakarov** Just write carefully **the induction statement** (**i.e., the property P(n) such that you need to prove $\displaystyle \forall n\,P(n)$**), the base case, the induction hypothesis, etc.

You need to prove $\displaystyle \forall y\,(y \ne 0\to\exists x\,y = Sx)$. Removing the universal quantifier, we are left with the property $\displaystyle P(y)\stackrel{\text{def}}{=}y \ne 0\to\exists x\,y = Sx$. This is the property you prove by induction, which is also the induction hypothesis in the case of regular (weak) induction. As has been said, in simple cases the induction statement is obtained just by removing the universal quantifier from the statement one has to prove. In more complex cases one needs to strengthen the property to make the induction step go through. In the case of strong induction, the induction hypothesis is $\displaystyle \forall z\,(z<y\to P(z))$.

For a procedure to create a proof by induction, see this post.