Which of these formulas holds in a tree? Temporal logic

42 Views Asked by At

Problem: A frame $(U, \prec)$ that is irreflexive, transitive, extendible in both directions and $L$-total is called a tree. I need to determine which of the formula's are true everywhere in every tree:

(a) $GHA \rightarrow HGA$

(b) $HGA \rightarrow GHA$.

(c) $PFA \rightarrow FPA$.

(d) $FPA \rightarrow PFA$.

I was trying to prove $(a)$. I assume $U \models GHA [u]$ for some arbitrary $u \in U$.Then for all $v$ with $u \prec v$ and all $w$ with $w \prec v$ we know that $U \models A[w]$. By $L$-totality, I know that $u \prec w, w \prec u$ or $u = w$ must hold.

The consequence says that for any $x$ with $x \prec u$ and any $y$ with $x \prec y$ we need that $U \models A[y]$. I'm not sure how to continue, since I might not able to compare $u$ and $y$ since $R$-totality is not given.

Help is appreciated.

Edit: G means 'it is always the case that...', while H means 'it has always been the case that...'. So for a model $U$, we have that $U \models Gp [u] $ if for all 'times' $v$ with $u \prec v$ we have that $U \models p[v]$. Similarly, $U \models Fp[u]$ means that there exists a time $v$ with $u \prec v$ such that $U \models p[v]$. And similarly for the past operators $H$ and $P$. So these are the tensor operators. In modal logic $ \Box \leftrightarrow G$, while $\Diamond \leftrightarrow F$.

This is from Burgess 'philosophical logic' book.

1

There are 1 best solutions below

0
On BEST ANSWER

(a) is false: take a tree with two branches and consider $A$ holds in one branch (and before) but not on the other branch, and let $u$ be on the first branch, then $u\Vdash GHA$ but $u\not\Vdash HGA$.

(b) does hold: assume $u\Vdash HGA$, and let $v, w$ such that $u\prec v$ and $w\prec v$.
Then, by being left total, one has either $u\prec w$ or $u=w$ or $w\prec u$.
If $u\prec w$, by L-extendibility, there's an $u'\prec u$, but then $u'\Vdash GA$, so $w\Vdash A$.
In the other two cases, choose a $w'\prec w$, then $w'\prec u$, so we have $w'\Vdash GA$, and thus $w\Vdash A$ again.

(c) and (d) can be either done analogously, or can be directly derived from (a) and (b) by applying $GA=\lnot F\lnot A$ and $HA=\lnot P\lnot A$.

Note that (b) encodes the property of the frame that if $u, v$ has a common upper bound, then they also have a common lower bound.