and

``for all '' is true,

then

``for all '' is true.

In order to prove ``for all '' by using the induction principle, you should

1. Prove that is true.

2. Take a generic element of
and
prove
.

Recall that the way to prove ``
'' is true, is to
assume that is true and show that then must be true.

Then says

which is true, since both sides of this equation are equal to . Now let be a generic element of Then

It follows from the induction principle that is true for all , which is what we wanted to prove.

Proof: Define a proposition form over by

Now , so and thus is true.

Let be a generic element of
Since
, we
know that

Hence

Hence, for all
It follows from
the induction principle that for all