How do I solve relations involving immediate predecessors?

284 Views Asked by At

Give the relation $R$ defined by: $(a,b) \in R$ if and only if a is an immediate predecessor of $b$ in $P$, where $P$ is the poset (partially ordered set)

$$P = \{ (a_6,a_{22}),(a_{23},a_{23}),(a_{22},a_{26}),(a_{22},a_{22}),(a_{18},a_{18}),(a_{23},a_{26}),(a_6,a_{18}),(a_6,a_{23}),(a_6,a_{26}),(a_{26},a_{26}),(a_{18},a_{26}),(a_6,a_6),(a_{23},a_{18}) \},$$

where $a$ is an immediate predecessor of $b$ if $(a,b)$ is in $P$ and there is NO path of length greater than $1$ from $a$ to $b$ in the graph of the relation $P$. In other words $(a,b) \in R$ if and only if $a$ and $b$ are connected in the Hasse diagram associated with $P$ and $a$ is below $b$ in that diagram. What does $R$ equal?

Any help would be great. Thanks!

1

There are 1 best solutions below

4
On BEST ANSWER

A more proper definition for a predecessor is the following:

Definition. An element $a$ is an immediate predecessor of $b$ in $P$ if $(a,b)\in P$ and $a$ is a maximal such element; i.e., there does not exist an element $c\neq a$ with $(a,c)\in P$ and $(c,b)\in P$.

Based on the above definition, since each element in your poset is in relation with itself, the relation $R$ will be the identity which I denote by $R^*$: $$R^*=\{(a_6,a_6), (a_{18},a_{18}),(a_{22},a_{22}),(a_{23},a_{23}),(a_{26},a_{26})\}$$

Now, according to your definition for an immediate predecessor, $R$ actually turns out to be equal to $R^*$. The reason is that your poset is reflexive, i.e. each element in $P$ is in relation to itself.

More precisely, given two distinct elements in $P$, say $a$ and $b$, if it is the case that $(a,b)$ belongs to $P$, then the very fact that $(b,b)$ also belongs to $P$ leads to a path of length greater than 1 from $a$ to $b$.

If you change the definition of an immediate predecessor by not allowing the reflexive witnesses affecting the length of your paths, the situation will heavily change. I mean, you might let the pairs like $(b,b)$ not increase the length of your paths. That would seem ultimately more natural, at least to me.

Or alternatively, in order to have a more natural definition of an immediate predecessor for an element $b$, we can only consider the elements that are distinct from $b$. By doing so, reflexivity of the poset does not affect the set of predecessors of an element $b$ anymore. More precisely, we'd better to consider the following:

Definition. An element $a$ is an immediate predecessor of $b$ in $P$ if $a\neq b, (a,b)\in P$ and $a$ is a maximal such element; i.e., there does not exist an element $c\neq a$ with $(a,c)\in P$ while having $c\neq b $ and $(c,b)\in P$.

By the latter definition, in the example mentioned in the question, we will have that $R=P\backslash R^*$.