******************************************************************** ELECTRONIC NEWSLETTER ON REASONING ABOUT ACTIONS AND CHANGE Issue 98040 Editor: Erik Sandewall 24.4.1998 Back issues available at http://www.ida.liu.se/ext/etai/actions/njl/ ******************************************************************** ********* TODAY ********* Due to an editing mistake, we yesterday only sent out the first half of Jixin Ma's contribution in the debate about the ontology of time. Today's issue also contains additional contributions by Pat Hayes and Sergio Brandano. ********* DEBATES ********* --- ONTOLOGIES FOR TIME --- -------------------------------------------------------- | FROM: Jixin Ma -------------------------------------------------------- (Contribution continued from yesterday's issue:...) Sergio Brandano wrote: > > Now, "why an alternative notion of continuous structure is needed at > > all"? It has been noted that, temporal knowledge in the domain of > > aritifical intelligence, including "temporal reasoning about actions > > and change", is usually imcomplete, and using time intervals in > > many cases is more convenient and more in-keeping with common > > sense of temporal concepts than to use the classical abstraction of > > points. In fact, the notion of time intervals (or periods) has been > > introduced for a long time in the literature. In addition, in order > > to overcome/bypass the annoying question of if intervals are open or > > closed, various approached have been proposed. An example is Allen's > > interval-based time theory. As for these time theories, the old > > (classical?) notion of continuity no longer simply applies. > > My question referred to what is *needed* rather than *convenient*. > I understand it may be convenient, in some cases, to use intervals, but > this is not pertinent with my criticism, which still holds. So, you think intervals are NOT NEEDED? Anyway, our arguements about the convenience of using intervals are based on the belief of the need of them. > Let me ask you a more stringent question. > > Premise: It is evident that if you assume the axiom of completeness, > the domain $S$ can just be continuous, while if you do not assume the > axiom of completeness then $S$ is necessarily discrete. Wrong! Even if you do not asssume the axiom of completeness, it is still not nessarily discrete. > Question: Suppose that you define your neither continuous nor discrete > Temporal Structure. What is your domain $S$? What is your > replacement for the axiom of completeness? Does this structure > (provably) solve for at least one problem what can not be (provably) > solved via the axiom of completeness? Can you give an example? The domain is just a collection of time elements each of which is either an interval (specially a moment) or a point. The basic core theory doesn't commit itself if the time stucture is continuous or discrete. So, if you would like one which is neither continuous nor discrete, you don't need the axiom of completeness. Why I need a replacement for it, anyway, if it is not supposed? Extra axioms regarding dense/discrete, linear/non-linear, bounded/non-bounded time structure, etc. can be given (e.g., see Ma and Knight's CJ94 paper). Specially, the characterisation of continuity does not have to be in the form of axiom of completeness. In addition, as shown above, in the case where time intervals are addressed, it becomes very complicated (if not impossible) to simply appy such an axiom. As for example you would like to see, the DIP is a typical one, as I have shown in the above. Also, Sergio wrote in his reply to Pat: > What properly formalizes the notion of continuity is the axiom of > completeness. Alternative notions are equivalent, until we speak > about continuous domains. The point was whether one can have a > continuous domain (that is the $S$ I stated above) ... with > exceptions. > If another axiom exists, which *does as well*, then it is surely > equivalent to the axiom of completeness, just because *it does as > well*. Alternative notions are clearly equivalent, until we speak > about continuous domains. The point here, instead, was whether one > can have a continuous domain with exceptions, that is the claim I > originally criticized. First, as shown in the above, the axiom of completeness doesn't simply apply to the case when time intervals are involved. Therefore, your claim that "alternative notions of continuity are clearly equivalent" is unjustified, at least it is not CLEAR! Second, the question of "whehter one can have a continuous domain with exceptions" depends on how do you understand the real meaning. It is important to note that neither Pat nor myself claims that one can have such a structure as you understood and hence described by "a continuous domain with exceptions". Of course, if you have already assume that the domain as a whole is continuous, then it must be continuous - no exception! This is just like if you impose that "The traffic light was green throughout last week", then, of course, it was green any time during last week, no exception. Similarly, if you impose that "The traffic light was red throughout last week", then it was red any time during last week. Again, no exception. However, if you don't have either of them, why can not one have the case that over the last week, the traffic light was sometimes red, and sometimes green, and even sometimes yellow? As I said earlier, when Pat talked about "continuous with exceptions", he actually meant that "except at those time moments, the time is continuous", or more specially, "except for time moments, each time interval is decomposable". I don't think he would actually assume, in the first place, the continuity of the WHOLE DOMAIN, then expect there are some exceptions. Do I understand your meaning rightly, Pat? Jixin -------------------------------------------------------- | FROM: Pat Hayes -------------------------------------------------------- John McCarthy wrote: >If axioms are guaranteed to be used only in a particular program or >set of programs, they need be no stronger than necessary. > >As to the rhetorical "what use", suppose the theory is to tolerate the >elaboration that two successive events, shooting Pat and his falling >to the ground, occurred between successive ticks of the clock. If you >guarantee that no such elaborations will be required or that you are >willing to do major surgery on your theory should elaboration be >required, then you are ok with a weak theory even if it is >unextendable. in answer to my remarks: >> In my view, axioms are tools which we can manipulate at will; they are not >> set in stone or somehow inevitable. Different formal accounts of time might >> be appropriate for different purposes or to capture different intuitions. >> ... and >> A more mundane example is given by temporal databases, which usually assume >> in their basic ontology that time is discrete:... If I understand what John is saying, then I completely agree with him. (If he intended to disagree with me, then maybe I dont understand his point.) However, note that both Jixin and I are trying to give a theory which is as elaboration-tolerant as possible, without being completely vacuous. Answers to Sergio Brandano: Sergio seems to be on a different planet, as his responses to both Jixin and I seem to quite miss the point of our debate, and often to be completely free of content. >I can just quote myself ... Well, you *can*; but to do so is at best unhelpful, and at worst arrogant. If someone fails to understand you and asks for clarification, to simply repeat yourself is obviously unlikely to give them the clarification they need. >> Here in Pisa, we write ``continuity'' and we read ``axiom of >> completeness'', which is what everyone commonly means when speaking >> about (the founding notion of) continuity. May I ask in return if "everyone" here is meant to refer to everyone in Pisa, or to a broader community? If the former, my advice is to travel more; if the latter, then you are simply wrong. >The word "continuity", even at the ontological level, can not be read >as "continuous with some exception". There is an entire mathematical theory of punctuated continua, ie spaces which are continuous everywhere except for a non-dense set of points. Such structures even arise naturally from purely continuous phenomana in, for example, catastrophe theory. The formal trick, you see, is to alter the axiom so that instead of reading 'for all points...' it reads 'there exists a set S such that for all points not in S...'. The result is also an axiom, believe it or not. >> For a point-based model, the continuity is usually characterized as >> "Between any two points, there is a third"; while for an >> interval-based model (like that of Allen), it is characterized as >> "Every interval can be decomposed into two adjacent sub-intervals". > >The axiom of completeness states: > >Let be $A$ and $B$ non empty subsets of $S$ such that $a leq b$ >for all $a in A$ and $b in B$. Then exists $xi in S$ such that >$a leq xi leq b$ for all $a in A$ and $b in B$. > >Now, the set $S$, that is your domain, may consists as well either of >time-points or time-intervals; $S$ holds real numbers on the former >case, intervals from the real line on the latter case. You havent said what 'leq' means for intervals. If it means that the endpoint of a is point-leq the first point of b, then this axiom seems false; for consider a point p and the set A= { } for any p1

} for any p2>p. This satisfies your premis, but there is no interval between any of the intervals in A and any interval in B (unless you allow intervals consisting of a single point.) But in any case, you are here *assuming* that the real line is your intended model. But this axiom doesnt characterize the real line. Its true on the rationals, for one thing, but thats not all. For example, here is a nonstandard model of your axiom: interpret points as pairs where n is an integer and q is a rational number or the symbol "i", and say that leq just when aPremise: It is evident that if you assume the axiom of completeness, >the domain $S$ can just be continuous, while if you do not assume the >axiom of completeness then $S$ is necessarily discrete. If you do not assume the axiom, then $S$ may be discrete, continuous or any mixture. Did you mean to say, if you assume the *negation* of the axiom? But the negation of your axiom simply says that some point of discontinuity exists; it does not impose a discrete structure on the whole of $S$. It is much more difficult to axiomatise a discrete structure than a dense one; in fact, it cannot be done in first-order logic. >Question: Suppose that you define your neither continuous nor discrete >Temporal Structure. What is your domain $S$? What is your >replacement for the axiom of completeness? See above, but modify the domain to exclude the "i" symbols. This structure (N copies of Q) is dense almost everywhere, but your axiom fails to hold when the sets A and B are infinite in a particular way. There are 2|Q subsets in the power set of this domain, and only N|2 of them fail your axiom, so by almost any standard it is true 'almost' everywhere. (Another interesting example is got by reversing N and Q, so that one has Q copies of N laid end-to-end. This fails your axiom 'locally', ie when the subests are only finitely separated, but satisfies it for sufficiently separated sets. It is like a discrete space which changes to a dense one when the scale is reduced sufficiently. See J.F.A.K.Van Benthem " The Logic of Time", Synthese Library v. 156, Reidel, (1983) for a lovely discussion of such examples. >> Why cannot time be continuous in some places but discontinuous at others? > >Places? If we shall understand time like (physicists) understands the >space, ... Yes, that is more or less what I have in mind. Do you propose to formalise a theory of time which is incompatible with physics? (Why??) >> There is no mathematical objection to such a structure, and it has been > >If a Temporal Structure exists in this sense, may I have a look at >its domain (that is at the $S$ domain, as stated above)? See above examples and use your imagination. But this is a trivial challenge. It can be done for any set S with a (strict) ordering <. Select a subset P of S, and define a new order relation << on S+P as follows: x<..... I have no problems accepting that >a *function of* time may be piecewise continuous, or that it may be >undefined for some points along the time axis. However, it seems to >me that there are several problems with saying that *time itself* >is piecewise continuous (btw - do you mean piecewise dense?). (Yes, most of this discussion is really about density rather than continuity. Ive just let this ride for now.) >The first problem is with respect to motivation. For what reasons would >Time suddenly skip over potential timepoints? If the reason is, as you >wrote, that > >> The 'dividing point' problem which gave rise to this discussion would do. >> According to the modern account of the continuum, this point must exist, >> and since all intervals consist of points, the light is therefore either on >> or off at it. But it seems more natural, as well as formally simpler, to >> just say that the question is meaningless; perhaps (though this is no >> longer my own preference) because that point doesn't exist. > >then exactly what events in the world would be allowed to contribute to >the continuity faults? Does the next time I hit a key on my keyboard >qualify? It all depends on whether you find it useful to describe things that way. The idea of intervals simply *meeting* seems to be a very useful way to think about time, and it immediately gives rise to all these problems. > And what about the midpoint halfway between two continuity faults, > is it also a continuity fault, recursively? Not necessarily. (Im not sure quite what your point is here. Must there be a waterfall exactly between two waterfalls?) > The other problem is with respect to the axiomatizations. Since your > article "A catalog of temporal theories" characterizes the various > theories through axiomatizations, I thought I'd go back to that article > and check how you had done this formally. However I was not able to > find it; the closest I got was the denseness axiom on page 15. Throughout the catalog, I give density and discreteness axioms. As I say in the text, you can take your pick; or, if you like, you can say that time is dense sometimes and discrete others, making obvious slight changes to the axioms to make these assertions. The axioms in the theories of the catalog are offered to you like pieces of an erector set. I make no committment to their truth, only that they fit together properly. As to whether time *really is* discrete or continuous, etc., the only people who can answer questions like that are physicists, not we who merely craft ontologies. > If the > intuitive notion is that time itself is continuous in some places but > not in others, wouldn't it be natural to start with an axiomatization > of continuous time (such as the real numbers) and then to proceed from > there? For example, a domain of piecewise continuous time could be > represented as a twotuple $$ where $R$ is the real numbers and > $D$ is a "small" subset of it; the intention being that $R-D$ is the > modified time domain in question. The notions of non-standard intervals > could then be constructed as the natural next step. Yes, that is a possible approach. However, (1) the real numbers are already a very compicated domain to axiomatise, requiring such things as set theory and notions of limits, etc..; I was looking for something much more mundane; and (2) as Ive said repeatedly, the real line isnt a very good model of our temporal intuitions, in my view, but comes along with a lot of misleading assumptions which are not necessary for temporal reasoning. > Maybe I'm missing something - are constructs of this kind subsumed by > the axioms in your report, or can they be inferred as theorems? Neither. The time axioms are far too weak to be able to infer anything about real analysis. However, it should be possible to construct models of the time axioms using ordinary mathematical notions like the integers and the reals, and indeed I try to do that for every theory in the catalog. At the very least, this helps guide ones intuitions about just what it is ones axioms really say, instead of what one hopes they ought to say. Pat -------------------------------------------------------- | FROM: Sergio Brandano -------------------------------------------------------- In reply to Jixin Ma (ENRAC 23.4.1998) > So, you didn't refer "the classical one" to "the Basic Time > Structure" you developed, did you? If No, why DID you develop it? > What is YOUR convincing argument(s) on the need of such a structure? > Is it also an alternative to the classical one? (Sorry, I am here > using the similar question raised by youself to ask you, though I > don't have to). If Yes, I shouldn't ask this question. By "the classical one" I mean the classical notion of continuity. By "the basic time structure" I mean a basic (minimal) time structure. By "the time structure X" I mean the temporal structure we like to deal with. It is obtained from the basic time structure via additional axioms. You also invited me to be more explicit with respect to the following sentence. > The axiom of completeness states: > > Let be $A$ and $B$ non empty subsets of $S$ such that $a leq b$ > for all $a in A$ and $b in B$. Then exists $xi %in S$ such that > $a leq xi leq b$ for all $a in A$ and $b in B$. > > Now, the set $S$, that is your domain, may consists as well either of > time-points or time-intervals; $S$ holds real numbers on the former > case, intervals from the real line on the latter case. The (temporal) domain $S$, as I meant, may consist either of time-points xor of time-intervals (exclusive "or"). An interval from the real-line is an ordered set of real numbers limited by its end-points, which are not necessarily included in the set. Suppose $S$ consists of intervals from the real line. Assume $ \in A$ and $ \in B$, intervals in $S$. We say that $ \leq $ iff $t1 \leq s2$. The strict order relation $\less$ is an abbreviation for $\leq \logical-and \noteq$. Suppose now that $ \less $. The axiom of completeness states the existence of $\xi \in S$ such that $ \leq \xi \leq $. I reply in advance to your next question: "Why did you write <= instead of < ?". The reply is that <= means "less or equal", that is $\xi$ may not be equal to $t1$ or $s2$, but it can do so. Note that since $\xi$ belongs to $S$, then $\xi$ is an interval. This is also meant as a reply to your question about the dividing instant problem. I could not penetrate the rest of your message. Best Regards Sergio ******************************************************************** This Newsletter is issued whenever there is new news, and is sent by automatic E-mail and without charge to a list of subscribers. To obtain or change a subscription, please send mail to the editor, erisa@ida.liu.se. Contributions are welcomed to the same address. Instructions for contributors and other additional information is found at: http://www.ida.liu.se/ext/etai/actions/njl/ ********************************************************************