Re: Looking for Undecidable Propositions in Systems without a certainamountofarthimetic.



Nam Nguyen wrote:
herbzet wrote:
Nam Nguyen wrote:
herbzet wrote:
Nam Nguyen wrote:
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)
...
Not sure I'm getting the joke. All these are true in a domain
with exactly one object.
It's not a joke. I just showed you that for the "pure FOL" theory
you mentioned above, it would be much a stronger statement if the
undecidable formulas that are not contingent formulas!

A formula is undecidable in pure FOL if and only if it is contingent.

Wrong! The formulas F = Axy(x=y) and ~F are both undecidable in the
"pure FOL" theory, but none of them is contingent!

They are both contingent.

(Again, according to
you below, "Contingent formulae are non-logical formulae").

I stand by that, when understood as below.


(I take it
here "contingent formula" means non-logical formulas).

Contingent formulae are non-logical formulae, but so are
contradictions.

[After all,
this "pure FOL" theory wouldn't have any theorems that are non-logical
formulas, right?]

Right. But your formulae above are contingent.

According to you above, a contingent formula is a non-logical formula.
But according to FOL, a non-logical formula *must* have non-logical
symbol(s).

I've never heard that.

So which of my formulas above have non-logical symbols? And
what are those non-logical symbols?

Some logicians consider the equal sign a non-logic symbol, some
don't. I personally like to avoid using it as a logical symbol
when it can be avoided.

But I assumed you were, in fact, using it as a logical symbol,
and I have no problem with that. It's more common than not.

They are not true in
infinite domains, or in sufficiently large finite domains -- that
is, for each formula in the series, there are finite domains in
which it is false.

Let's not talk about these until you're quite clear what a non-logical
(contingent) formula is.

My understanding of a contingent formula is that it is a formula
that is neither a validity or a contradiction.

Do you not agree?

--
hz
.

Relevant Pages