1

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!

Novice
  • 1,127
BigJamo
  • 13

1 Answers1

0

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^*$.

Ali V.
  • 195
  • Legend. Explained it so much better than my lecturer lol and now I understand it. Thanks! – BigJamo Aug 19 '20 at 12:13
  • @BigJamo: Many thanks for your comment. If you think it appropriately answers your question, you can mark it as "Answer" ;-) – Ali V. Aug 19 '20 at 12:21
  • 1
    I would consider it more natural for $b$ not to be a predecessor of $b$, even if $(b,b)\in P$. An immediate predecessor would then be maximal amongst the predecessors, so in the definition there would then be an implicit $c\neq b$ too. – Jaap Scherphuis Aug 19 '20 at 12:38
  • @JaapScherphuis: Thank you very much for the very good comment! I have edited the answer. – Ali V. Aug 19 '20 at 13:51