0

A partially ordered set is defined as a set with a relation that is symmetric, transitive, and anti-reflexive.

The transitivity and anti-reflexivity rule out cycles. We can't have "a < b < c < ... < z < a", because "a < b < c" transitively implies "a < c", etc. until "a < z", and anti-reflexivity rules out "a < z < a".

This seems obvious, but I just realized that this argument actually depends on the assumption that the cycle has a finite length.

As an informal counter-example, imagine a circle that grows until it becomes infinitely large. It is infinite, yet circular; you can walk around it, if you make infinitely many steps.

The set consists of the points at the boundary of this infinite circle. The relation "a < b" is defined as: the point "a" is at a final distance clockwise from the point "b".

This satisfies the definition of a partially ordered set. (If "a" and "b" are at a finite distance, and so are "b" and "c", then "a" and "c" are also at a final distance. If "a" is at a finite distance clockwise from "b", it is at an infinite distance counter-clockwise.) But if you walk all around this circle, making steps of a finite length, you just made an infinite cycle.

Does this make sense, mathematically? The predictable objection is that there is no such thing as an "infinite circle with a boundary" and consequently no infinite cycles. But perhaps there is a model of geometry where infinite circles make sense, or perhaps some other method can be used to create a partially ordered set with an infinite cycle.

Viliam Búr
  • 174
  • Does $0 < 1 < 2 < 3 < \cdots \cdots < -3 < -2 < -1 < 0$ work as a counter-example? If not, why not? – TomKern May 14 '22 at 12:14
  • There's such a thing as "transfinite recursion". You should read about Zorn's lemma. – Joe May 14 '22 at 12:16
  • @TomKern I am not sure about how the "⋯⋯" part works. As soon as you say that any specific positive number is smaller than any specific negative number, you have a cycle of a finite length. If you don't say that, then all positive numbers are simply larger than all negative ones. – Viliam Búr May 14 '22 at 12:20
  • @Joe Zorn's lemma applies when every chain has an upper bound, which doesn't seem to be the case in my informal example. Or perhaps I misunderstand it (quite likely), in which case I need more details. – Viliam Búr May 14 '22 at 12:31
  • 1
    What's the definition of "infinite cycle"? I honestly don't know what you mean by that term... – David C. Ullrich May 14 '22 at 12:48
  • @ViliamBúr I believe Tom's point is that there needs to be a reason that the "infinite" part of the "loop" ties together. The reason has to be expressible purely in terms of partial orders. If you place countably many points along a circle in a well-ordered chain:$$\ldots < a_{-2} < a_{-1} < a_0 < a_1 < a_2 < \ldots,$$ then this is order-isomorphic to $\Bbb{Z}$ under its usual ordering. If we can say $a_0 < a_1 < a_2 < \ldots < a_{-2} < a_{-1} < a_0$ is a cycle, then why not $0 < 1 < 2 < \ldots < -2 < -1 < 0$? It would mean that cycles are not preserved under isomorphism, which is a bad sign. – Theo Bendit May 14 '22 at 12:59
  • @DavidC.Ullrich, I'm not sure if this is what the OP meant, but I was thinking it was something like: If a connected topological space with a partial order has an open cover such that each open set is linearly ordered by the partial order, does that imply the space is linearly ordered. (the vaguely described "infinite cycle" being an attempt to think of a counter example proving the answer is no) Perhaps the topological space should be the standard topology on the unit circle to count as an "infinite cycle". – Joe May 14 '22 at 13:07
  • 1
    Actually, without involving topology, perhaps the question could be: Let $P$ be a poset such that: (1) $\forall a, b, c \in P , ((a<b) \land (a<c)\land (b\ne c)) \implies ((b<c) \lor (c<b))$, (2) $\forall a, b, c \in P , ((a<c) \land (b<c)\land (a\ne b)) \implies ((a<b) \lor (b<a))$, and (3) for every non-empty chain $C \subsetneq P$, there exists $a \in C$ and $b \in (P \setminus C)$ such that $(a<b) \lor (b<a)$. Is it necessarily true that the partial order is a total order on $P$? Would that rule out the kind of "infinite cycle" you had in mind @ViliamBúr? – Joe May 14 '22 at 14:16
  • @DavidC.Ullrich, I do not have an exact definition. Maybe this all actually doesn't make sense -- that is a part of my question. I just have an intuition of "making infinitely many steps and arriving at the starting point", where I noticed that the relation "A is finitely many steps in front of B" would technically be a poset. And I imagine the path as a circle to express that there is nothing special about the specific starting point; it is simply an infinitely long path that forms a loop. I am not even sure what kind of infinity this would be; whether this picture even makes sense in ZF(C). – Viliam Búr May 14 '22 at 20:58
  • 1
    @TheoBendit, I think I may be starting to see something... is it that there is simply no way to place ω points on a circle in regular intervals? So my imagined "path around the infinite circle" would actually require uncountably many steps, so instead of one path it would actually be a sequence of (uncountably many) disjoint paths, and instead of "infinite cycle" it would actually fall apart into a sequence of (uncountably many) disjoint chains. – Viliam Búr May 14 '22 at 21:37
  • " I do not have an exact definition. Maybe this all actually doesn't make sense": If you ask about infinite cycles and you cannot give a definition of "infinite cycle" then you are not making sense, no maybe about it. Sorry, I don't make the rules... – David C. Ullrich May 14 '22 at 22:04
  • @Joe, yes for (1) and (2), a "locally total order". But I didn't realize that "the situation is perfectly symmetrical, like points on a circle" does not necessarily imply "the chains are connected". You could have a copy of Z (a local total ordering, infinite in both directions) at each point on a circle, but if those local copies are mutually incomparable, you get a poset that is both "locally total ordered" and "symmetrical around the circle" and yet unconnected, so no actual "infinite cycle". (Sorry, I am thinking in pictures, I am probably not communicating this clearly in plain text.) – Viliam Búr May 14 '22 at 22:10
  • @ViliamBúr, that's why I added condition (3) in my comment above, so that no non-empty chain $C \subsetneq P$ could be such that every one of its members is incomparable to every member of $P \setminus C$. – Joe May 14 '22 at 22:16
  • @DavidC.Ullrich, imagine infinitely many people, standing in a circle, holding hands, facing inwards. Each one sees thousand neighbors to the left, and thousand neighbors to the right, so from their perspective "standing to the left of someone" is a total ordering. But because they are all connected (maybe this cannot be expressed in first-order logic), anyone is kinda to the left of anyone, if you walk around the whole circle. This is not a formal definition, but I hope it is clear enough for someone to either help me make the formal definition, or explain the precise reason it can't be done. – Viliam Búr May 14 '22 at 22:32
  • @ViliamBúr, when you say "help [you] make the formal definition", would a partial order satisfying the three conditions I gave above, on the unit circle, match your intuition for an "infinite cycle"? And if so, would your question be: "Does such a partial order exist on the unit circle?" – Joe May 14 '22 at 23:56
  • @Joe, yes, in my intuition the three conditions you gave are definitely true. The idea of a circle could be expressed as "the entire relation is isomorphic from each element's perspective". This seems necessary but not sufficient (I guess my idea satisfies these conditions, but they also allow some creative interpretation I didn't have in mind, e.g. some infinite fractal), but it seems the best I can do. Ok, so do the conditions (1) (2) (3) imply that the relation is a total order? Is there a non-empty relation that is isomorphic from each element's perspective, and satisfies (1) (2) (3)? – Viliam Búr May 15 '22 at 08:46
  • Yes, I believe they do imply a total order, although I don't have time to write a careful proof. But if we assume there are any two elements $a,b$ with $a<b$, then take the union of all chains containing those two elements. By (1), (2), and transitivity, we show the union is a chain. Then we show that it is the whole set by assuming it's not, using (3) to find another comparable element $c$, and creating a new larger chain that contains $a<b$, which contradicts that our union was of all chains containing $a$ and $b$. – Joe May 15 '22 at 11:28
  • Also, I agree that "isomorphic from each element's perspective" probably isn't sufficient to capture your intuition, since from the perspective of each element in $\mathbb{Z}$, "there are just as many points on either side of me." – Joe May 15 '22 at 11:59

0 Answers0