Re: Looking for Undecidable Propositions in Systems without a certain amount of arthimetic.

herbzet wrote:

Scott wrote:
On Aug 13, 2:52 pm, Chris Menzel <cmen...@xxxxxxxxxxxxxxxxxxxx> wrote:
uninteresting, and implies nothing about the completeness of first-order
theories generally. The question of completeness is interesting only
If the undecidable proposition is derivable

If by "derivable" you mean "deducible" then you have a contradiction
of terms: a proposition that is deduced is thereby decided -- it
isn't undecidable.

in FOL, it should be

A validity. I presume you mean deducible in pure FOL with no
non-logical axioms.

Pure FOL as a theory with no non-logical axioms has undecidable
propositions -- every contingent formula is undecidable.

Better yet, such a theory would have infinite undecidable formulas
which are not logical formulas and which are of the forms:

Ex0Ay(x0=y)
Exox1Ay(x0=y \/ x1=y)
Exox1x2Ay(x0=y \/ x1=y \/ x2=y)
....


That is, there are propositions /in the language/ of FOL that
are not /in the theory/ -- no contingent formula is provable
in pure FOL.

derivable in any theory. Doesn't this make any theory incomplete? If
not, how does a theory prevent the derivation?

What on earth do you mean by a "derivation"? Get persnickity here!
From axioms one deduces theorems! One doesn't deduce non-theorems!
One _decides_ a proposition by proving it or its negation!

If we add contingent formulae as non-logical axioms to pure FOL
then we get a first-order theory. It might be complete, it might
be incomplete (there are undecideable formula), it might be
essentially incomplete.

It also might be inconsistent, if we add axioms that contradict each
other.

Adding contingent formulae as non-logical axioms allows us to prove
-- to decide -- other contingent formulae. That's how it works.

Note though it's also possible to prove logical formulas from non-logical
formulas!

--
"To discover the proper approach to mathematical logic,
we must therefore examine the methods of the mathematician."
(Shoenfield, "Mathematical Logic")
.

Relevant Pages