Re: Question regarding incompleteness in formal systems without sufficient power for arithmetic.

On 2 huhti, 22:07, Gc <Gcut...@xxxxxxxxxxx> wrote:
On 2 huhti, 10:52, Aatu Koskensilta <aatu.koskensi...@xxxxxxxxx>
wrote:



On 2008-04-01, in sci.logic, Scott wrote:

I'm just curious: what is a sufficient proof to show such a formal
system is incomplete?

That depends on the system.

Let me take an example: First-Order Logic (FOL). To show FOL is
incomplete, you would need to find a true theorem that could not be
derived in FOL.

No. All we need is to exhibit a formula P such that neither P nor
not-P is provable in first-order logic. And it's trivial to find such
examples: ExEy(x =/= y), AxEyP(x,y), ...

In case of first-order logic it makes no sense to say these
undecidable formulas are "true" since the language has no single
intended interpretation.

I would guess that no closed formula in FOL with identity is un
undeciable. And you of course know this: For nonclosed formulas which
are not actually universally quantified decidability makes, of course,
no sense.

I made a wrong guess. ExEy(x =/ y) says that there are at least 2
things. The unaru group ({1},*) contains only one element.
.

Relevant Pages
Quantcast