raja.damanik 3:54 am on 15 Oct 2016
Tags: <, cluster, filtration, finite, modal, , model, order, rational, singleton, transitive   

Transitive filtration on (Q,<)

This a bonus question for HW 2 Basic Modal Logic course 2016/2017.

Show that transitive fitration on (\mathbb{Q},<) is a finite list of clusters, maybe interspersed by some irreflexive singletons, no two of which may be adjacent.

What I did is to consider it in four steps.

Finiteness and transitivity

This follows from filtration property (upon finite \Sigma) and the property that R has as a transitive filtration.

Linearity

For all a \ne b, we have Rab \vee Rba.

Proof. WLOG, a<b. Then, we show that for all \diamond \phi \in \Sigma, we have that if b \Vdash \phi \vee \diamond \phi, then a \Vdash \diamond \phi. If b \Vdash \phi, then because a<b, we have a \Vdash \diamond \phi. If b \Vdash \diamond \phi, then there exists some c>b, such that c \Vdash \phi, and thus becaue a<b<c, a \Vdash \diamond \phi.  \blacksquare

Moreover, we basically have < \subseteq R.

Properties of irreflexive points

If \neg Raa, then there must be some \diamond \phi \in \Sigma, such that a is the greatest number satisfying \phi.

Proof. If \neg Raa, it means that for some \diamond \phi \in \Sigma, we have a \Vdash \phi \vee \diamond \phi but a \nVdash \diamond \phi. Thus, a \Vdash \phi and a \nVdash \diamond \phi. \blacksquare

I also claim no two irreflexive points can be adjacent.

Proof. Suppose that a<b are irreflexive points w.r.t. formula \alpha and \beta, respectively and suppose that they are adjacent in the finite list of filtration. Take any number c \in (a,b) \cap \mathbb{Q}. Clearly, Rac. But a and b are adjacent in the filtration, then we must have Rbc for all such c. This means that for all \diamond \phi \in \Sigma, particularly \diamond \beta, we have c \vDash \beta \vee \diamond \beta implies b \vDash \diamond \beta. But, we have b \nvDash \diamond \beta. \blacksquare

Properties of non-simple cluster

Now, we prove that for any reflexive point, it belongs to a non-simple cluster.

Proof. If there is no \diamond \phi \in \Sigma, then all the points belong to the same cluster. If there exist \diamond \phi, then for reflexive points a, Raa means for all \diamond \phi \in \Sigma, a \vDash \phi \vee \diamond \phi implies a \vDash \Diamond \phi. This means, a must not be the greatest number satisfying formula \phi for any \diamond \phi \in \Sigma. Because there is only finite number of singletons (due to the finiteness of \Sigma, we can choose rational number a_1 >a such that all the numbers in (a,a_1) \cap \mathbb{Q} are all reflexive (not a singleton). Now pick any x \in (a,a_1) \cap \mathbb{Q}. Clearly Rax. We show Rxa now. Because it means for all \diamond \phi \in \Sigma, a \vDash \diamond \phi implies x \vDash \diamond \phi, and because a is not a singleton, we then just need to check a \vDash \diamond \phi implies x \vDash \diamond \phi. Suppose a \vDash \diamond \phi but x \nvDash \diamond \phi. This means that there’s a singleton for \phi \in (a,x) which is a contradiction. Thus a belongs to a cluster which also contains at least the whole (a,a_1) \cap \mathbb{Q}.

Because every point in filtration is either reflexive or irreflexive, these properties show that the result of filtration is a finite list of clusters, may be interspersed by some irreflexive singletons, no two of which are adjacent.

This is approximately what I wrote in my homework. I have not got any feedback yet at the time I am writing this. I hope it got almost full marks (like 8 or more).

Advertisements