ontolog-forum
[Top] [All Lists]

## Re: [ontolog-forum] cyclic and acyclic definitions

 To: "[ontolog-forum]" Bart Gajderowicz Fri, 24 Apr 2009 04:35:30 -0400 <6b20199d0904240135k24a804c4qd01a8b65f5f4be43@xxxxxxxxxxxxxx>
 ```Chris, thanks for the questions. I hope I answered them here. If not, please let me know.    (01) >> JK> How does a cyclic definition introduce incompleteness? >> >> When sentences contain cyclic sentences, they become inconsistent, >> think of the halting problem (undecidability) with turing machines. >> If we were to introduce recursion to our interpretations, it would be >> limited to partial recursion. The task, then, would be to create an >> interpretation of the sentence which is acyclic, and our sentence >> consistent. The interpretation would be decidable, and our recursive >> function total. > > Bart, you keep using terms in ways I don't understand. > > 1. Did I miss the definition of a "cyclic" sentence? Could you > provide a reasonably rigorous definition and then demonstrate how (as > it seems you are saying) any sentence containing a cyclic sentence > "becomes inconsistent"?    (02) I view a cyclic sentence (S) as one for which all of the following are true: 1) S has the same formula (F) in both the left immediate subformula (LIS) and right immediate subformula (RIS) of the "implies" logical connective.    (03) 2) LIS has a quantification of F with respect to a variable (a).    (04) 3) RIS has a quantification of F with respect to a variable (b).    (05) I believe that if (a) and (b) are not distinct, it's a tautology, unless other formulas exist in both LIS and RIS, with different logical connectors.    (06) Essentially, RIS is true if LIS is true. But since both subformulas are the same, mainly F(x), this is a cyclic sentence.    (07) Example 1: forall a F(a) iff forall b F(b)    (08) Example 2: Momo = Man who has Only Male Offspring (forall x (Momo(x) iff exists y s.t. Man(x) ^ Momo(y) ^ hasChild(y,x)))    (09) Sorry.... correction, not inconsistent, but *incomplete*. I used "incomplete" in my explanations, but for some reason wrote "inconsistent" in the paragraph stating the problem I'm addressing, from the original **web-syllogism-and-worldview** thread, which I then copy-pasted into this thread.    (010) So now: S in this case becomes incomplete because: 1) We need a truth value for LIS to determine truth value for RIS. 2) But we can't determine the truth value for LIS without first determining the truth value for RIS 3) i.e. we can't prove whether F(x) is true to false 4) By Gödel's incompleteness theorem, I believe, if we can't prove whether F(x) is true or false, it is incomplete.    (011) Am I wrong about this? Did I misunderstand something?    (012) Again, my apologies. I should really write this stuff during the day.    (013) > 2. How could the halting problem demonstrate anything about cyclic > sentences (no matter how they are defined)? The halting problem is > the problem of whether a certain well-defined function is computable > by a Turing machine. On the face of it, it has nothing whatever to do > with sentences, cyclic or otherwise.    (014) If a Turing Machine runs forever on input (x), it is said to be uncomputable on (x). In my example above, the sentence S is recursive on F(x), and does not have a stop condition, and so recursively executes F(x) forever. If a Turing Machine recursively executes some code forever, it would be uncomputable. As my explanation in the original thread, I was speaking in terms of programing.    (015) > > 3. What does it mean to "introduce recursion in our interpretations"? > Recursion is a way of defining one function in terms of others. An > interpretation might interpret a *theory* that is capable of defining > functions by recursion, for example, but I have no idea what it means > to "introduce recursion in" an interpretation; it seems like a > category mistake.    (016) I believe recursion is when a function F is defined by having itself in the definition. You can have other functions, but it's only recursive if the function itself is amongst them in the definition. Does this not apply to predicate logic?    (017) When I said *introduce recursion to our interpretation*, I meant, which I think is the same as your example, that we will now concern ourselves with interpreting theories which have recursive formulas in their sentences.    (018) > > 4. Interpretations are mathematical structures. What do you mean by a > "decidable" interpretation? One whose domain is decidable?    (019) Yes.    (020) -- Bart Gajderowicz MSc Candidate, '10 Dept. of Computer Science Ryerson University http://www.scs.ryerson.ca/~bgajdero    (021) _________________________________________________________________ Message Archives: http://ontolog.cim3.net/forum/ontolog-forum/ Config Subscr: http://ontolog.cim3.net/mailman/listinfo/ontolog-forum/ Unsubscribe: mailto:ontolog-forum-leave@xxxxxxxxxxxxxxxx Shared Files: http://ontolog.cim3.net/file/ Community Wiki: http://ontolog.cim3.net/wiki/ To join: http://ontolog.cim3.net/cgi-bin/wiki.pl?WikiHomePage#nid1J To Post: mailto:ontolog-forum@xxxxxxxxxxxxxxxx    (022) ```
 Current Thread [ontolog-forum] cyclic and acyclic definitions, Bart Gajderowicz Re: [ontolog-forum] cyclic and acyclic definitions, John F. Sowa Re: [ontolog-forum] cyclic and acyclic definitions, John Bottoms Re: [ontolog-forum] cyclic and acyclic definitions, Jawit Kien Re: [ontolog-forum] cyclic and acyclic definitions, Bart Gajderowicz Re: [ontolog-forum] cyclic and acyclic definitions, Jawit Kien Re: [ontolog-forum] cyclic and acyclic definitions, Bart Gajderowicz Re: [ontolog-forum] cyclic and acyclic definitions, Christopher Menzel Re: [ontolog-forum] cyclic and acyclic definitions, Bart Gajderowicz <= Re: [ontolog-forum] cyclic and acyclic definitions, John F. Sowa Re: [ontolog-forum] cyclic and acyclic definitions, Bart Gajderowicz Re: [ontolog-forum] cyclic and acyclic definitions, Azamat