This a bonus question for HW 2 Basic Modal Logic course 2016/2017.
Show that transitive fitration on 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 ) and the property that
has as a transitive filtration.
Linearity
For all , we have
.
Proof. WLOG, . Then, we show that for all
, we have that if
, then
. If
, then because
, we have
. If
, then there exists some
, such that
, and thus becaue
,
.
Moreover, we basically have .
Properties of irreflexive points
If , then there must be some
, such that
is the greatest number satisfying
.
Proof. If , it means that for some
, we have
but
. Thus,
and
.
I also claim no two irreflexive points can be adjacent.
Proof. Suppose that are irreflexive points w.r.t. formula
and
, respectively and suppose that they are adjacent in the finite list of filtration. Take any number
. Clearly,
. But
and
are adjacent in the filtration, then we must have
for all such
. This means that for all
, particularly
, we have
implies
. But, we have
.
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 , then all the points belong to the same cluster. If there exist
, then for reflexive points
,
means for all
,
implies
. This means,
must not be the greatest number satisfying formula
for any
. Because there is only finite number of singletons (due to the finiteness of
, we can choose rational number
such that all the numbers in
are all reflexive (not a singleton). Now pick any
. Clearly
. We show
now. Because it means for all
,
implies
, and because
is not a singleton, we then just need to check
implies
. Suppose
but
. This means that there’s a singleton for
which is a contradiction. Thus
belongs to a cluster which also contains at least the whole
.
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).