How can FOL logic be at the same time complete and only semi-decidable?
in [Logic]
|
From: Aatu Koskensilta on 7 Aug 2010 10:06 cesare cassiobruto <vjq001(a)gmail.com> writes: > SO, it seems that if FOL is complete, then it IS DECIDABLE. The observation that a complete theory is decidable is perfectly fine. (It's a mystery why it seems to have eluded Hilbert!) However, first-order logic is not complete in the relevant sense. That is, it is not the case that for any formula A, either A or the negation of A is logically provable. -- Aatu Koskensilta (aatu.koskensilta(a)uta.fi) "Wovon man nicht sprechen kann, dar�ber muss man schweigen" - Ludwig Wittgenstein, Tractatus Logico-Philosophicus
From: Nam Nguyen on 7 Aug 2010 14:23 cesare cassiobruto wrote: > On 7 Ago, 19:07, Colin <colinpoa...(a)hotmail.com> wrote: >> On Aug 7, 8:21 am, cesare cassiobruto <vjq...(a)gmail.com> wrote: >> >>> Hi, I'm new to this forum. 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. >>> [snip] >>> 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. So, we know that a procedure TC(not-a ) for >>> checking if not-A is a theorem WILL halt, eventually, saying it is a >>> theorem. >> This is where you go wrong. Yes, if A is not a theorem then A is not >> vaild. But, no, that does mean that not-A is therefore valid. A being >> invalid simply means not-A is satisfiable in SOME model. For not-A to >> be valid it would have to be valid in EVERY model. (You yourself seem >> to have finally gotten this point in your response to Aatu's post.) > > Yes, now I finally grasped it. Intuitively, I think the problem is, > when you talk about logic you don't talk about a formal system which > is intepreted in a fixed model, so you forget that in FOL not every > sentence is simply true or false, but that can be true in a possible > world and false in another. While when talking about let's say, > arithmetic, you talk about an intepreted system for which every > statement is either true or false, and being not true means being > false. In logic, when you say it's a validity you don't simply say > it's true, but that it's true in every possible interpretation. > Anyway, such questions always confuse me a bit. For example: > decidability > Is the definition I cited correct? It was this one: > > DEF.: A theory T is decidable iff given a statement P in the > language of the theory, it does exist a general mechanical > procedure > that always ends in a finite time for checking if P is or is not a > theorem of T. > > BUT in many textbooks I found a definition that states " for > checking if P is or is not a > VALID formula of T". So, it seems the first one is SYNTACTICAL, > the second a SEMANTIC requirement. Accfording to yuo, which is the > standard meaning of "decidable theory"? Which it seems to this is the > same as asking "what do we mean with 'theory', the set of all > derivations from the a�xioms (syntax) or the set of all logical > consequences (semantics)?" What is your opinion? > > Moreover, can anybody of you please clarify the distinction > between syntactic an semantic completeness? Despite intuition, common usage, or convention, we should really make a distinction between formula truth and formula semantic: each of all formulas has its own FOL semantic, whether or not it has any truth value. For instance, x=x has its own semantics whether or not it's FOL with - or without - equality we're talking about. I found many definitions > of them, not always clear. Is this distinction related in a way to the > distinction between the two definition of decidability I mentioned > above? > > Thanks a lot > > > Edit / Delete Edit Post Quick reply to this message Reply Reply > With Quote Reply With Quote Multi-Quote This Message Thanks -- ----------------------------------------------------------- Normally, we do not so much look at things as overlook them. Zen Quotes by Alan Watt -----------------------------------------------------------
From: Aatu Koskensilta on 8 Aug 2010 04:47 cesare cassiobruto <vjq001(a)gmail.com> writes: > Do you mean that from the fact that a sentence A is not valid, i.e. it > is not true in EVERY interpretation, it does NOT follow that not-A is > true in every interpretation? Yes. For example (x)P(x) is not true on every interpretation but neither is ~(x)P(x). -- Aatu Koskensilta (aatu.koskensilta(a)uta.fi) "Wovon man nicht sprechen kann, dar�ber muss man schweigen" - Ludwig Wittgenstein, Tractatus Logico-Philosophicus
From: Aatu Koskensilta on 8 Aug 2010 19:17 George Greene <greeneg(a)email.unc.edu> writes: > Aatu K.'s replies are often abusive. They are? > There is a very simple answer to your question. Indeed. -- Aatu Koskensilta (aatu.koskensilta(a)uta.fi) "Wovon man nicht sprechen kann, dar�ber muss man schweigen" - Ludwig Wittgenstein, Tractatus Logico-Philosophicus
From: Herman Jurjus on 9 Aug 2010 03:29 On 8/7/2010 4:06 PM, Aatu Koskensilta wrote: > cesare cassiobruto<vjq001(a)gmail.com> writes: > >> SO, it seems that if FOL is complete, then it IS DECIDABLE. > > The observation that a complete theory is decidable is perfectly > fine. (It's a mystery why it seems to have eluded Hilbert!) Huh? The set of all closed sentences that are true in N is a theory, and it's complete - but it isn't decidable. > However, > first-order logic is not complete in the relevant sense. That is, it is > not the case that for any formula A, either A or the negation of A is > logically provable. -- Cheers, Herman Jurjus
|
Next
|
Last
Pages: 1 2 Prev: How can FOL logic be at the same time complete and only semi-decidable? Next: I am a human son |