Change Logic and the Change in Logic

bucephalus.org

March 25, 2010

\underline{Abstract} This paper is a prelude to a research project called change logic.

\underline{Preface} Suppose, temporal logic is the subject that looks for a language and logic to reason about processes and things that change in time. Then it seems, that this implies a thorough study of time itself. But this is wrong. Time is a philosophical burden and dead weight in temporal logic. We shouldn’t try to associate events to a time structure, we only need to realize change during the process. This paradigm shift is one starting point of a research project called change logic. However, the elimination of time from temporal logic may not be so surprising as it tries to sound here. Actually, in the standard modal logical reconstruction, the relation to a time structure via a Kripke model is also only temporary. Once the formal system is motivated and its soundness and completeness is shown, time becomes superfluous here as well and disappears. In fact and in return, it is also possible to attach a linear time structure to what will be introduces as change logic. So in the end, the real change with change logic does not so much come from a new philosophical semantics, but from the fact, that the whole thing was pulled off without adding new constructs to the syntax. In other words, change logic is temporal logic without modal operators.

\underline{Overview} This text has three parts:

1. How to formalize a dynamic system? This is an attempt to introduce change logic from a meta–perspective and in opposition to modal logic. I doubt, if this explains a lot.

2. Chronologies and their relation This is the stable part in this report. It explains the core structure of the subject by means of an example.

3. Change Logic as a research project A more mathematical elaboration of the whole subject is in progress and this part tries to highlight some aspects I am working on. The terminology, notation and ideas mentioned here will probably not remain. Change logic emerged from research on an “intelligent” learning algorithm, and this is also the goal I am aiming at with the whole project.

                    www.bucephalus.org                                            Change Logic and the Change in Logic  2

1. How to formalize a dynamic system?

Defining the problem Suppose L is a language. In the sequel, we usually think of L as the language of propositional logic (based on some atom set A), but it may be any other formal language, as well. We say that the propositions (or statements or sentences) φ of L describe a static world or states of a static world. Our problem now is to find a way to formalize dynamic behavior of this static world and the change of states through time. The solution should be a well–defined logical system, similar to say propositional logic. Let us call this the “temporalization of L”.

First approach: global time We often explain things in time by attaching time stamps, e.g. “in 1970” or “on Monday” or “at 18:34”. A dynamic world or temporal event 𝔚 could be formalized as a function

𝔚 : 𝔗 ⟶ L

where 𝔗 is a time structure and φ = 𝔚 (t) is the event at time t. Usually 𝔗 is an (interval of a) linear structure. In most of physics, the real number line ℝ is taken for 𝔗. The global or absolute time concept is often used in history in phrases like “in November 1989”.

Second approach: local time Different to history, natural sciences are more often interested in a more local time concept, where future events are describled as consequences of past events. This involves a concept of “now”, with pointers to before and after. A formalization of this local time concept could be similar to the Dedekind cuts in mathematics, so that each “now” moment is a pair of intervals ⟨(..., t], [t, ...)⟩, where (..., t] is the past time up to t ∈ 𝔗 and [t, ..) is the time interval starting from t.

Local time in modal logical systems Temporal logic, dynamic logic and other modal logical approaches do have a local time concept.^{1} They all introduce this local time structure by extending the syntax of the language and attach an appropriate Kripke semantics. For example, the syntax of basic temporal logic ^{2} for formulas ϕ is given by

ϕ ::= α | ⊥ | ⊤ | ¬ϕ | ϕ ∧ ϕ | ϕ ∨ ϕ | Fϕ | Pϕ | Gϕ | Hϕ

for atomic formulas α, i.e. four unary modal operators F, P, G, H have been added to propositional formulas with the interpretation that ( ; 𝅝 ; ) Fϕ means “ϕ will be true at some future time” ( ; 𝅝 ; ) Pϕ means “ϕ was true at some past time” ( ; 𝅝 ; ) Gϕ means “ϕ is always going to be true” ( ; 𝅝 ; ) Hϕ means “ϕ was always true”

In other variations, more or less or other modal operators are added, like “next” or “until”. ^{3}

Third approach: no time reference at all We could think by now, that we have to introduce some kind of temporal concepts for our temporalization problem. But when we take the right look at our daily life and native language, we notice, that this is not necessary. Actually, when we describe dynamic processes in daily life, we don’t refer to an absolute or relative time so very often. We rather and much more often refer to events in the context.

\underline{Example} For example, when I ask you “When did you meet your friend?”, you could answer: ( ; 𝅝 ; ) “Sunday at 8 am.” (absolute time reference). ( ; 𝅝 ; ) “An hour ago.” (relative time reference). ( ; 𝅝 ; ) “During the rain.” (reference to an event)

Core features of Change Logic

( ; 𝅝 ; ) Any process in time is given by a sequence ⟨φ_{1}, …, φ_{n}⟩ of L–

statements. This is called a story or chronology. ( ; 𝅝 ; ) So if ψ is another statement and we ask about the “time” when ψ happened during the process, the answer is: at φ_{i}, where φ_{i} is the component in ⟨φ_{1}, …, φ_{n}⟩ with ψ ⊑ φ_{i} (where ⊑ is the usual semantic relation in L).

( ; 𝅝 ; ) As a consequence of this approach, change logic does not use additional operators for L.^{4}

1All these designs are introduced in a standard text Modal Logic, by Patrick Blackburn, Maarten de Rijke, and Yde Venema, Cambridge University Press, 2001 , with an own home page on http://mlbook.org. The unifying approach in this book is not restricted to temporal structures 𝔗, but considers relational structures structures (called frames) in general. It elaborates the fundamental ideas of modal logic in Slogan 1: “Modal languages are simple yet expressive languages for talking about relational structues.” and Slogan 2: “Modal languages provide an internal, local perspective on relational structures.”

2See Example 1.14 in the mentioned book or the Wikipedia entry on “Temporal logic” at http://en.wikipedia.org/wiki/Temporal logic. 3It is possible to embed temporal logic into change logic, i.e. we can translate each of these modal constructors into a construct of change

logic. This text doesn’t unfold the subject detailed enough to present the method. But to give a hint, suppose we want to express that all “processes” s start with ϕ and then change to ψ, that this means that s ⊴ ⟨ϕ, ψ⟩ must hold.

4 Change logic does not mean, that we cannot include time concepts in the language. It only means, that these are not introduced as fixed syntactic constructs. For example, we could add an atom night to the atom set, where night means that it is dark and ¬night means daylight. This can then be “attached” to an event φ by say ¬night ∧ φ, which means that this event took place during the day. Similarly, we could add a 24–hour time reference or any other precision required. The digitalized clock of a computers central processing unit is also an example of a time representation in propositional (i.e. digital) logic.

2. Chronologies and their relation

Family vacation Let us start all over again. Suppose, a family came back from one week vacation and now they are telling us stories about it.

Propositional chronologies The language they use is a very poor one and only uses propositions (propositional formulas^{5}) made of the atomic statements warm and wet. Every story is a sequence φ_{1}, …, φ_{n} of these propositional formulas, and they are (propositional) chronologies in the sense that it means “first φ_{1}, then φ_{2}, then ..., and finally φ_{n}”.

Fathers version For example, the father gives the following report

(1) First, it was cold when we arrived. (Formally: ¬warm)

(2) Then, it became warm. (Formally: warm)

(3) Then it was raining (i.e. warm and wet). (Formally:

  warm ∧ wet)

(4) When we left again, it was snowing (i.e. not warm and wet). (Formally: ¬warm ∧ wet)

Alltogether and properly formalized, fathers report is given as a tuple or list of four statements

   ⟨¬warm, warm, warm ∧ wet, ¬warm ∧ wet⟩ or [\begin{matrix}¬warm \\ warm \\ warm ∧ wet \\ ¬warm ∧ wet \end{matrix}]

Mothers version When mother was asked about the vacation, she said:

(1) In the beginning it was dry (i.e. not wet).

(2) But the second half was wet, all along.

Put formally, mother said

                ⟨¬wet, wet⟩  or  [\begin{matrix}¬wet \\ wet \end{matrix}]

Elementary chronologies We heard two stories, what about the real history of this vacation? At each moment, it was either warm or not warm, and either wet or not wet (due to the binary character of propositional logic). So at any moment, exactly one of the following elementary propositons is true: ( ; 𝅝 ; ) warm ∧ wet we abbreviate this by “raining” ( ; 𝅝 ; ) ¬warm ∧ wet we call this “snowing”

( ; 𝅝 ; ) warm ∧ ¬wet  i.e. “sunny”

( ; 𝅝 ; ) ¬warm ∧ ¬wet we abbreviate this by “chilly”

Let us say that a chronology ⟨φ_{1}, …, φ_{n}⟩ is an elementary chronology, if each of the φ_{i} is an elementary proposition.

Daughters diary Suppose the family daughter has kept a diary with a weather report for every day:

                                                                                           Monday  chilly

Tuesday  sunny
Wednesday sunny
Thursday  sunny

                                                                                           Friday  raining

Saturday  raining

                                                                                           Sunday  snowing

If we omit the references to the days, the elementary chronology is

                                                                                      [\begin{matrix}chilly \\ sunny \\ sunny \\ sunny \\ raining \\ raining \\ snowing \end{matrix}] = [\begin{matrix}¬warm ∧ ¬wet \\ warm ∧ ¬wet \\ warm ∧ ¬wet \\ warm ∧ ¬wet \\ warm ∧ wet \\ warm ∧ wet \\ ¬warm ∧ wet \end{matrix}]

The relation between chronologies Intuitively, we can see that the three stories of father, mother and the girl are compatible, i.e. they can all be true at the same time, and that the girls chronology is the most concrete of the three. We are about to define the following notation and concepts:

(a) s ⊴ t, saying that the chronology s is more concrete than t, or t is more abstract than s, or that s is a concretion of t and t is a abstraction of s. In our example,

                                                                                       daughtersDiary ⊴ fathersStory
                                                                                       daughtersDiary ⊴ mothersStory

(b) s and t are (chronologically) covalent if there is (at least) one (elementary) chronology e, with e ⊴ s and e ⊴ t. In our example, and as a consequence of (a), fathers and mothers story are covalent. In fact, all three stories are (pairwise) covalent.

The previous definition of the covalence relation on chronologies is a proper definition. ⊴ may be intuitive for the example cases, but we need to explain it more precisely.

Daughters diary and mothers story

                                                                       So, what does daughtersDiary ⊴ mothersStory exactly mean?

Fully written, that is

                                                                                [\begin{matrix}chilly \\ sunny \\ sunny \\ sunny \\ raining \\ raining \\ snowing \end{matrix}] = [\begin{matrix}¬warm ∧ ¬wet \\ warm ∧ ¬wet \\ warm ∧ ¬wet \\ warm ∧ ¬wet \\ warm ∧ wet \\ warm ∧ wet \\ ¬warm ∧ wet \end{matrix}] ⊴ [\begin{matrix}¬wet \\ wet \end{matrix}]

Obviously, the mother was refering to the the first four days, when she said that it was dry in the beginning. And when she said that it was wet in the second half of their vacation, she was talking about the last three days. There is what we call a correspondence between the two chronologies:

5In other material on bucephalus.org, we make a distinction between propositional formulas and propostions, which are an abstraction and the elements of a propositional algebra. And such an algebra is not just a boolean algebra, as usual, but what we call a theory algebra. Nevertheless, all this in not relevant in this present text. Think of propositions as propositional formulas on the atom set A = {warm, wet}, with constant boolean values 0 and 1 and junctors ¬, ∧, ∨, →, ↔, as usual. Subvalence (or entailment) of proposition is denoted by φ ⊑ ψ, equivalence by φ ≡ ψ.

chilly sunny sunny sunny raining raining snowing                wet ¬wet

There is a line from each component of the left story to at least one component of the right story, and vice versa, but such that the lines don’t cross each other. And for each line from component s_{i} to component t_{j} the propositional subvalence (or entailment) relation s_{i} ⊑ t_{j} must hold. For example chilly ⊑ ¬wet,

sunny ⊑ ¬wet, etc.

The “order relation” on chronologies

Later on we will say that, for any two chronologies s, t, s ⊴ t is true if and only if there is a ⊑–correspondence between s and t.

This is a core concept of what we call change logic. But it is a rather awkward concept when we try to approach it with conventional order–theoretical methods. In fact, ⊴ violates even the most important feature of all other kinds of order relations, namely transitivity. (Transitivity means, that s ⊴ t and t ⊴ u always implies s ⊴ u.) On the other hand, the “order relation” does have an equivalence relation, written ≜, which is a proper equivalence relation in the traditional sense. It is also easier to define and check than ⊴, as we shall see, soon.

Daughters diary and fathers story We claimed, that the diary version is a concretion of fathers story, i.e. that

[\begin{matrix}chilly \\ sunny \\ sunny \\ sunny \\ raining \\ raining \\ snowing \end{matrix}] = [\begin{matrix}¬warm ∧ ¬wet \\ warm ∧ ¬wet \\ warm ∧ ¬wet \\ warm ∧ ¬wet \\ warm ∧ wet \\ warm ∧ wet \\ ¬warm ∧ wet \end{matrix}] ⊴ [\begin{matrix}¬warm \\ warm \\ warm ∧ wet \\ ¬warm ∧ wet \end{matrix}] = [\begin{matrix}¬warm \\ warm \\ raining \\ snowing \end{matrix}]

We confirm this relation by showing that there is a ⊑– correspondence between the two chronologies. In fact, there are several versions, and we consider two of them:

chilly sunny sunny sunny raining raining snowing  ¬warm warm raining snowing

and the second correspondence is

chilly sunny sunny sunny raining raining snowing  ¬warm warm raining snowing

The interesting point here is the fact that the raining Friday (fifth component in the diary) can be subsumed under both the second (warm) and the third (raining) statement in fathers story. This is an example of in important phenomenon. Fathers story is not distinct, as we call it.

Distinct chronologies

A chronology s = ⟨s_{1}, …, s_{n}⟩ is said to be distinct (or stepwise disvalent), if s_{i} and s_{i+1} are disvalent, i.e. s_{i} ∧s_{i+1} ≡ 0, for all i = 1, ..., n − 1.

Recall, that s_{i} and s_{i+1} are disvalent, iff either e ⊑ s_{i} or e ⊑ s_{i+1}, but never both, for every elementary (or more general: for every satisfiable) proposition e.

In fathers chronology,

                          [\begin{matrix}¬warm \\ warm \\ raining \\ snowing \end{matrix}]

the first (from ¬warm to warm) and last step (from raining to snowing) are disvalent, but not the middle one (from warm to

raining), because warm ∧ raining ≡ warm ∧ (warm ∧ wet) ≡
warm ∧ wet ≡ raining.

The important property of distinct chronologies ⟨s_{1}, …, s_{n}⟩ is, that it cuts the whole flow of events into n distinct sections. At each step from s_{i} to s_{i+1} there is a real change of the events.

\underline{Theorem} And there is yet another important feature: On the set of distinct chronologies, the relation ⊴ is transitive. It is a quasi–order relation (i.e. reflexive and transitive). As mathematicians we are immediately tempted to ask about the general possibility of operations like join and meet. Is the logic of (distinct) chronologies similar to that of propositions? Does all that provide us with an algebra for dynamic systems?

The equivalence relation Let us consider the daughters diary again, with seven entries, one for each day of the week. Note, that the reference to any time values are removed in our formal version of a chrononogy

                           chilly
                            sunny
                            sunny
                            sunny
                           raining
                           raining
                           snowing

It turns out, that repetitions in a chronology are similar to repetitions in conjunctions or disjunctions, where the idempotency law is telling us that

φ ∧ ψ ∧ ξ ≡ φ ∧ ψ ∧ ψ ∧ ξ
≡ φ ∧ ψ ∧ ψ ∧ ψ ∧ ξ
≡ φ ∧ ψ ∧ … ∧ ψ ∧ ξ

In effect, we may remove any multiple occurrences of ψ. We may as well remove repetitions in a chronology, i.e.

 [\begin{matrix}chilly \\ sunny \\ raining \\ snowing \end{matrix}] ≜ [\begin{matrix}chilly \\ sunny \\ raining \\ raining \\ snowing \end{matrix}] ≜ [\begin{matrix}chilly \\ sunny \\ sunny \\ raining \\ raining \\ snowing \end{matrix}] ≜ [\begin{matrix}chilly \\ sunny \\ sunny \\ sunny \\ raining \\ raining \\ snowing \end{matrix}] ≜ . . .

That seems only reasonable: If no change has occurred, then it doesn’t make a difference! In our formal abstraction from all rhetoric figures and connotations, a vacation story like “It was raining (all the time)” is equivalent and telling the same as “It was raining and raining and raining and raining”.

3. Change Logic as a research project

Introduction The whole subject is very much a work in progress and here is a sketch of things I am working on. Initially in Part 1, we denied the connection to a time structure. But it is useful to have a local time concept in order to formulate rules or causal relations. We introduce them as abbreviations or constructs on the algebra of chronologies.^{6}

Chronologies as defining frameworks for dynamic systems We could rename usual propositional logic as static propositional logic, and introduce a structure on chronologies (i.e. tuples of propositions) as dynamic propositional logic, because chronologies provide us with means to describe the behavior of systems in time, as we saw. A static propositional world (or theory) can be defined as a function θ : (A ⟶ 𝔹) ⟶ 𝔹, which divides all elementary states or valuations ω : A ⟶ 𝔹 into possible states (i.e. θ(ω) = 1) and impossible states (i.e. θ(ω) = 0). This semantic function θ is just the formal version of what is usually displayed as a truth table. A dynamic propositional world (or theory) could as well be defined as a distinction between possible and impossible elementary chronologies on a given atom set A. And, as usual for binary distinctions, we could represent the dynamic theory by the set of all possible chronologies. This shall be our starting point for a general framework for dynamic systems. However, not every arbitrary set Ω of elementary chronologies makes a reasonable dynamic theory. It should have certain properties, e.g. if s † t ∈ Ω, then both s, t ∈ Ω as well. In other words, if a chronology is possible, then all its sections must be possible, too. In fact, we introduce several classes of properties and thus certain classes of dynamic theories. (A particular important class of dynamic theories is the class of what we call causal theories.)

Alternative representations The idea of dynamic theory as a set Ω of elementary chronologies seems a simple and reasonable concept. However, it is not a practical one, because in most of the interesting cases, Ω is an infinite set, with members that tend to grow to infinite length. In most cases, we would want to use different and more compact representations for Ω. ( ; 𝅝 ; ) One alternative representation for Ω is that of a binary relation M_{Ω}, where M_{Ω}(s, t) means that there is a (possible) moment in Ω with the past s and the future t. And this is only the case if and only if s † t ∈ Ω.

( ; 𝅝 ; ) Next to the indeterministic relational representation M_{Ω}, a functional version f is often useful, which returns for every (elementary) chronology s the next or future f (s), which is either a single proposition or a chronology, which could be defined as the disjunction or join of all t with s † t ∈ Ω or M_{Ω}(s, t). And similar to the future function f, there is a past function p, which is the same in the backward direction. ( ; 𝅝 ; ) A mixture of a relational and functional representation is a possible rule set, where each rule has the form s ↠ t, saying that, if a chronology s′ is a concretion of s or ends on s, then the system continues with t. And similar again, there are also possible backward rules of the form s ↞ t.

( ; 𝅝 ; ) Yet another representation for Ω is that of (finite) set Σ of

chronologies, where {s | ∃t ∈ Σ . s ⊴ t} = Ω. ( ; 𝅝 ; ) From the well–established subject of regular expressions, we know that these class of languages can very effectively be implemented as finite automata. Particular dynamic theories Ω are implemented by certain finite automata, as well.

The construction mutual transformation of these different representations are subject of separate mathematical investigation.

Change Logic The study of the structure on chronologies, together with the concretion ⊴ and equivalence relation ≜, the investigation of chronology sets, operations and normalizations on them, the different relational, functional and other representations etc. — this is subject of what we call change logic. ^{7}

6I must admit, that all this is not well explained here. 7For a while, I thought to call the subject causal logic. But now I like to subsume causal logic under change logic, similar to regular

languages are special context-free languages etc. By a causal system I mean a dynamic system, where the next event is determined by only a finite number of predecessor events, i.e. a causing chronology. The weather in most places is certainly not a causal system in this sense, because we are usually not able to predict the weather on the knowledge of some days experience. (Although, if we transform the daughters diary into the law for the dynamic world in question, then raining follows on sunny, and snowing on raining.) The assumption of this kind of causality in a system induces very effective and powerful learning algorithms, and the whole functionality can be performed on finite automata that operate on propositions. But all that must be propery elaborated and formalized, first.