I'm learning about partial orderings and need some help understanding the following statement. Say we have a relation, R, between the objects of finite set $S$:
If every element in R is preceded by another, then we could express R as an arbitrarily long linear sequence $b_1,b_2,b_3,...$ where $b_{j+1} \prec b_j$. Since $S$ is a finite set, we must have $b_j = b_k$, for some $j < k$. But $j < k$ implies that $b_k \preceq b_{j+1}$, hence $b_j = b_k$ contradicts the property of anti-symmetry (i.e. if $x \preceq y$ and $y \preceq x$, then $x = y$).
I tried deconstructing the statement by using an example as follows:
I took "every element in the relation is preceded by another" to mean some sort of circular relation like:
...which we could express linearly as an arbitrarily long sequence such as
$$b_1 = 1, \ b_2 = 3, \ \ b_3 = 7, \ \ b_4 = 1, \ \ b_5 = 3.$$ (Is this correct?)
Then, we have $b_{j+1} \prec b_j$ from transitivity (e.g. if $j = 1$, then we have $3 \prec 7$ and $7 \prec 1$, so $3 \prec 1$). And since S is finite, elements will repeat periodically in the sequence, so we have $b_j = b_k$ for some $j < k$ (e.g. in the example above we have $b_1 = b_4$).
But I'm not sure I understand how $j < k$ implies that $b_k \preceq b_{j+1}$.
I figured since $j < k$, we have $k \geq j+1$, so:
- if $k = j+1$, then $b_k = b_{j+1}$, and
- if $k > j+1$, then $b_k \prec b_{j+1}$ from transitivity.
Therefore, $b_k \preceq b_{j+1}$. And if $b_k = b_j$, then we can sub $b_k$ into $b_{j+1} \prec b_j$ to get $b_{j+1} \prec b_k$. So $b_k = b_j$ for some $j < k$ implies both $b_k \preceq b_{j+1}$ and $b_{j+1} \preceq b_k$, which contradicts the anti-symmetry rule. Is this correct?
The argument you quote says that wherever you start you can build a decreasing sequence. So start somewhere. Finiteness says that sequence can't keep finding new elements, so there must be a repeat. At that repeat you have an element that's less than itself, which is a contradiction.
I think it's better to write that argument as I did with words rather than with indices. Indices can be unnecessarily formal and confusing. In your example there are only three elements, so it makes no sense to talk about $b_4$.