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



Scott wrote:
On Aug 13, 4:19 pm, MoeBlee <jazzm...@xxxxxxxxxxx> wrote:

The set of sentences provable from only the logical axioms is
incomplete, just as we WANT it to be, in the sense that the contingent
sentences (those that are not logically true) are not in the set of
sentences provable only from logical axioms.

Okay, so FOL with logical axioms (or inference rules) is incomplete.
Adding non-logical axioms defines a theory, which may or may not be
complete.

Right. You might call the system of only logical axioms "the empty
theory" or "the null theory" -- it's just validities, no contingent
formula are provable or refutable.

In Godel's first incompeteness theorem, he constructs a sentence that
is shown to be undecidable in his chosen theory.

On the assumption that the chosen theory is consistent! (Actually,
omega-consistent, a stronger requirement).

If you likewise derive

Construct?

a sentence in FOL

You mean, "in the langugage of FOL"?

using only logical axioms and then show it to be undecidable,

If you deduce a sentence only from the logical axioms, it's a
validity, necessarily true. You've decided it already.

So your following questions make no sense to me.

Maybe re-ask the question?

I don't quite follow why this doesn't propagate to all
other theories based on FOL. Adding a non-logical axiom to "fix" the
problem would simply lead to a contradiction (and hence
inconsistency). For example, using your example in a previous post, if
the undecidable sentence in FOL is (Ex xex <-> ~Ex xex),

This is not an undecidable formula. It is an instance of (P <-> ~P)
which is a contradiction. It is refuted from the logical axioms
alone; i.e. from the logical axioms alone there is a proof of
~(P <-> ~P) and by substitution ~(Ex xex <-> ~Ex xex).

adding the
axiom of regularity ~Ex xex would simply lead to inconsistency. I'm
not following how adding a non-logical axiom can "fix" the undecidable
proposition in FOL. To borrow herbzet's phrase, why doesn't this make
FOL "essentially incomplete"?

It's a standard phrase, btw.

In geometry, we need the parallel postulate to prove that a triangle's
angles are equal to two right angles. If we drop the parallel postulate,
the proposition is undecidable. Adding the parallel postulate back
allows us to prove, hence decide the proposition.

If instead of the parallel postulate we add as an axiom "In a plane, any
line through a point not on a given line will cut the given line", then the proposition "A
triangle's angles sum to two right angles" is decided in the negative: its negation is
proved, and we have a non-Euclidean geometry.

--
hz
.

Relevant Pages