Re: Logical problem: how is it possible for first-order logic to be at the same time complete and only semi-decidable?
G. A. Edgar
<f6b6f350-7607-4fc1...@s9g2000yqd.googlegroups.com>,
<"luca.r...@gmail.com"> wrote:
> Now, if A is NOT a theorem, then from the completeness of FOL (1), it
> follows that A is not valid, i.e. it is false. So, not-A is true, i.e.
> it is valid. But then again, from the completeness of FOL it follows
> that not-A is a theorem.
This is not correct. For most A, neither A nor ~A is a theorem. For
example, suppose as our axioms we take the notion of group, and A the
commutative law. Then since some groups are commutative, ~A is not a
theorem, and since some groups are non-commutative, A is not a theorem.
--
G. A. Edgar http://www.math.ohio-state.edu/~edgar/
Irving Anellis
> time complete and only semi-decidable? - 1 new
> ----------------------------------------------
> Hi, I'm hope I'm not too offtopic. I have a doubt about completeness and
> decidability in First-order logic that I cannot solve: how is it possible for
> first-order logic to be at the same time complete and only
> semi-decidable? Let
> me explain. In 1930 Kurt Goedel demonstrated the completeness of first-order
> logic - Sat, Aug 7 2010 5:14 am
> 1 message, 1 author
> http://groups.google.com/group/sci.math.research/t/0591412928f7bbd6?hl=en
>
Do not confuse his completeness theorem for restricted FOL
with his incompleteness theorem for full first-order functional
calculus with identity.
Up until Andrew Wiles' proof was tested and confirmed, FLT was very
often
cited as the very me of a theorem which was in principle undecidable
(in
Gödel's sense).
We say that a logical theory is complete if every valid wff of the
theory is
provable in the theory.
In simplest terms Gödel's first incompleteness theorem states that
there is a sentence in the theory Z that is not provable in Z. It
means
that that all consistent axiomatic formulations of number theory
include undecidable propositions. This is sometimes called Gödel's
first incompleteness theorem, and answers in the negative Hilbert's
second problem asking whether mathematics is complete in the sense
that
every statement in the language of number theory, PRA [primitive
recursive arithmetic], can be either proved or disproved. Formally,
Gödel's theorem states:
Theorem 21.1 (Gödel 1931). To every omega-consistent recursive class
K
of formulas, there correspond recursive class-signs r such that
neither
(v Gen r) nor Neg(v Gen r) belongs to Flg(K), where v is the free
variable of r,
and Flg(K) is the set of all wffs that are immediate consequences of
the smallest set of wffs derived from the axioms of Z.
We may, if we like, consider the theorem in the following terms: Any
adequate axiomatizable theory is incomplete. In particular the
sentence
"This sentence is not provable" is true but not provable in the
theory.
Theorem 21.1 (Gödel 1931). To every omega-consistent recursive class
K
of formulas, there correspond recursive class-signs r such that
neither
(v Gen r) nor Neg(v Gen r) belongs to Flg(K), where v is the free
variable of r,
and Flg(K) is the set of all wffs that are immediate consequences of
the smallest set of wffs derived from the axioms of Z.
We may, if we like, consider the theorem in the following terms: Any
adequate axiomatizable theory is incomplete. In particular the
sentence
"This sentence is not provable" is true but not provable in the
theory.
See: Kurt Gödel, "Über die formal unentscheidbare Sätze der Principia
mathematica und verwandter Systeme, I“, Monatshefte für Mathematik
und
Physik 38 (1931), 173–198; English translation by Stefan Bauer-
Mengelberg
as “On Formally Undecidable Propositions of Principia Mathematica and
Related Systems, I”, in Jean van Heijenoort (ed.), From Frege to
Gödel: A
Source Book in Mathematical Logicm 1879–1931 (Cambridge, Mass.:
Harvard
University Press, 1967), 596–616; English translation by Elliott
Mendelson
in Martin Davis (ed.), The Undecidable: Basic Papers on Undecidable
Propositions, Unsolvable Problems and Computable Functions 4–38;
reprinted,
German and English on facing pages, K. Gödel (Solomon Feferman, et
al., eds.),
Collected Works, vol. I: Publications 1929–1936 (Oxford/New York:
Oxford
University Press, 1986), 144–195.
Irving H. Anellis
Peirce Edition
Indiana University-Purdue University at Indianapolis