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

Hubungan makna box dan diamond dalam modal logic

Berikut adalah beberapa contoh menarik makna \square p dan \lozenge p dalam modal logic yang menarik. Biasanya jika kita merekayasa makna \square, maka makna \lozenge dapat diperoleh melalui hubungan

\lozenge p \equiv \neg \square \neg p.

Berikut adalah makna yang diberikan jika modal yang digunakan menyatakan hal berikut.

Untuk meyatakan keharusan

Sebagai contoh, jika kita memberi makna \square p berupa “harus p“, maka makna \lozenge p adalah “tidak harus tidak p” yang pada dasarnya adalah “boleh p“.

Untuk menyatakan pengetahuan

Sebagai contoh, jika kita memberi makna \square p berupa “agen A mengetahui bahwa p“, maka makna \lozenge p adalah “agen A tidak mengetahui bahwa tidak p” yang pada dasarnya adalah “sejauh yang agen A tahu, p“.

Untuk menyatakan kepercayaan

Sebagai contoh, jika kita memberi makna \square p berupa “agen A percaya p“, maka makna \lozenge p adalah “agen A tidak percaya tidak p“. Apa hayo maknanya yang tidak perlu pakai kata “tidak”? Boleh saja sih bilangnya “sejauh yang agen A percaya, p berlaku”, cuman ini mungkin bukan kalimat yang alami untuk mendeskripsikan kepercayaan. Kalimat yang lebih deskriptif itu, “atas semua yang agen A percaya, p konsisten”.

Untuk menyatakan masa depan

Sebagai contoh, jika kita memberi makna \square p berupa “akan selalu p“, maka \lozenge p akan memiliki makna “tidak akan selalu tidak p” yang pada dasarnya berarti “suatu saat akan pernah p.

Coba 🙂

Oke, sebagai latihan, jika \square p berarti “p dapat dibuktikan”, maka apakah makna \lozenge pLeave some comments or questions below 😉