Enderton 3.1 problem 1 (p.193)

Printable View

December 2nd 2011, 12:20 AM
logics

Enderton 3.1 problem 1 (p.193)

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

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

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

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

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

We show that if $\psi \in A_S$ , then $\psi \in \text{Cn }A_S^*$ . Therefore, we show each $S1, S2, S3, S4.1, S4.2 \ldots, S4.n$ is a sentence in $\text{Cn }A_S^*$ . If $\psi = S1$ (resp. $S2)$ , $\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 $\text{Cn }A_S^*$ ?

From there, how do I conclude $\text{Cn }A_S^* = \text{Th }N_S$ ?
December 2nd 2011, 07:30 AM
Annatala

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.
December 2nd 2011, 12:04 PM
emakarov

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 $\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 $\text{Cn }A_S^* = \text{Th }N_S$ ?

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

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 $S3$ is a sentence in $\text{Cn }A_S^*$ by using the first two and induction?
December 3rd 2011, 01:03 AM
logics

Re: Enderton 3.1 problem 1 (p.193)

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

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

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

I have not figured out how to prove the first part yet, i.e., $A_S \subseteq \text{Cn }A_S^*$ .
December 3rd 2011, 09:15 AM
Annatala

Re: Enderton 3.1 problem 1 (p.193)

Quote:

Originally Posted by logics

For example, how do you show that $S3$ is a sentence in $\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. :)
December 4th 2011, 03:07 AM
logics

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

$\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
$\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?
December 4th 2011, 09:21 AM
Annatala

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

$\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
$\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:

$\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 $\phi_0 \leftrightarrow (\exists x,y (x = 0 \vee x = Sy))$ and plug it into the sentence for $\phi$ .

Using the above sentence, we can prove $\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 $\phi_0$ this is always true). Based on the expression above, this means $\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.
December 4th 2011, 10:30 AM
emakarov

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 $\forall n\,P(n)$ ), the base case, the induction hypothesis, etc.

You need to prove $\forall y\,(y \ne 0\to\exists x\,y = Sx)$ . Removing the universal quantifier, we are left with the property $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 $\forall z\,(z<y\to P(z))$ .

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