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

M	T	W	T	F	S	S
« Aug				Feb »
					1	2
3	4	5	6	7	8	9
10	11	12	13	14	15	16
17	18	19	20	21	22	23
24	25	26	27	28	29	30
31

	raja.damanik on Seleksi TOMI 2015 Tahap 2 di…
	Danang on Seleksi TOMI 2015 Tahap 2 di…
	raja.damanik on Non-deterministic version of a…
	Bayu Fajar Pratama on Non-deterministic version of a…
	saveforfreecom on OSN 2017 Matematika Hari Perta…
	Pip on Karya tahun 2008 (omg)
	afif~ on OSK Bidang Matematika 201…
	nivotko on OSN 2016 Hari 1 Soal 2
	afif~ on OSN 2016 Hari 1 Soal 2
	Thirafi Dide on Kronologi peradaban Islam…
	boykolot on Kronologi peradaban Islam…
	iisafriyanti on Kronologi peradaban Islam…
	nivotko on Hasil Tahap 3 IMO 2016
	nivotko on ON MIPA PT 2012
	Erwin on ON MIPA PT 2012

Share this:

Like this:

Leave a Reply Cancel reply