Re: Goedel incompl. theorems

Hi Henrik:

If we go through Dedekind's (1888?) proof that all models of Peano
arithmetic are isomorphic to the natural numbers, then we have a valid,
"ordinary" theorem of mathematics. But, if you look more carefully at
the argument, you'll see that the uses of the induction axiom
constitute an argument which is not 1st-order. So this is what I mean
by "ordinary mathematicians use ... 2nd-order logic...."

Yes, absolutely correct. ZFC can be axiomatized in a 1st-order theory,
and this is (much more) than adequate for mathematics such as we use in
physical science. In fact, it is a theorem of 1st-order ZFC that every
model of 2nd-order Peano arithmetic is isomorphic to the natural
numbers. The problems with ZFC, if we can call them that, are:

(1) It doesn't answer some basic questions from analysis and algebra.
(2) It needs an infinite set of axioms, and some of these axioms seem
to be way off the road that conventional mathematicians travel; the
axioms are "extraordinary".

Yes, you can try to capture 2nd-order arithmetic with a 1st-order
theory. The problem is that the quantifiers range over "sets" and
"numbers". It is still possible to find uncountable models of this
theory by the Cardinality Theorem (Tarski) [a consistent theory has a
model of any cardinality equal to or exceeding the cardinality of the
language of the theory]. Some models of this 1st-order theory of
"2nd-order arithmetic" will have "natural numbers" that aren't a finite
sequence of successors of 0--they will be non-standard natural numbers.
The same could be true of some of the "subsets" of natural numbers. In
some models there will be things that appear to be predicates on the
natural numbers but which are uncountable things. This isn't true in
genuine 2nd-order arithmetic by Dedekind's result.

For these reasons, 2nd-order arithmetic is usually considered not as a
1st-order theory, but as a restricted 2nd-order theory. One way to do
this restriction is to only permit quantification over finite
relations, not the general relations as in full 2nd-order logic.

Thanks!
--Ron Allen


Henrik wrote:
waveletter skrev:


Because of (a) and (d), some mathematicians and philosophers (e.g.
Quine) assert that 2nd-order logic is improper for mathematics and
science. It's proof theory is too problematic. But, what ordinary
mathematicians use is essentially 2nd-order logic without the
formalism. The power and commonality of the 2nd-order theory, despite
its ugly proof theory, are still attractive. Some people try to find
limited versions of 2nd-order logic that have a decent proof theory but
retain enough power to derive all of conventional mathematical
analysis. Boolos himself was one of these. If you're interested in this
pursuit, you might seek out:


What do you mean with "But, what ordinary mathematicians use is
essentially 2nd-order logic without the formalism"? Is not most of
ordinary mathematics possible to formalize in ZFC, which is a first
order theory?

A last question, is not Second Order Arithmetic most often formalized
using first order logic?


3. Simpson, "Subsystems of Second Order Arithmetic," Berlin: Springer,
1999.

4. Finally, check out the Wikipedia page:
http://en.wikipedia.org/wiki/Second-order_arithmetic

Hope this helps!
--Ron Allen

.

Relevant Pages