# 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. 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, 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, $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 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).