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)
|