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, firstorder 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 LogicoPhilosophicus
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 Firstorder logic that I cannot solve: how is it >>> possible for firstorder logic to be at the same time complete and >>> only semidecidable? 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, notA is true, i.e. >>> it is valid. But then again, from the completeness of FOL it follows >>> that notA is a theorem. So, we know that a procedure TC(nota ) for >>> checking if notA 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 notA is therefore valid. A being >> invalid simply means notA is satisfiable in SOME model. For notA 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 MultiQuote 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 notA 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 LogicoPhilosophicus
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 LogicoPhilosophicus
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, > firstorder 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 semidecidable? Next: I am a human son 