关系能否无环且完备但不传递？无环性与完备性是否蕴含传递性？

解答你的两个偏好关系问题 #

Let's break down these two questions step by step, using core properties of binary relations from choice theory:

问题1：是否存在同时满足无环性、完备性但不满足传递性的关系？

答案：不存在

Here's the reasoning: Suppose there was a binary relation ( R ) that is complete, acyclic, but not transitive. By definition of non-transitivity, there must be some elements ( x, y, z ) where ( xRy ) and ( yRz ), but ( \neg xRz ) (i.e., ( x ) does not relate to ( z )).

Since ( R ) is complete, for any pair of elements, either ( xRz ) or ( zRx ) must hold. We already established ( \neg xRz ), so this forces ( zRx ) to be true.

Now we have a cycle: ( xRy ), ( yRz ), ( zRx ). This directly violates the acyclicity condition, which prohibits any such cyclic sequences of distinct elements. The contradiction proves no such relation can exist.

问题2：无环性与完备性是否必然蕴含传递性？

答案：是的

This follows directly from the logic above, so let's formalize it:

1. Assume ( R ) is complete and acyclic.
2. Take any three elements ( x, y, z ) where ( xRy ) and ( yRz ).
3. If ( R ) were not transitive, we'd have ( \neg xRz ). By completeness, this implies ( zRx ), creating a cycle ( xRy \to yRz \to zRx )—which breaks the acyclicity rule.
4. Therefore, ( xRz ) must hold, so ( R ) is transitive.

To put it simply: completeness removes the possibility of having an unordered pair that could break transitivity without creating a cycle. On its own, acyclicity is weaker than transitivity (you can have acyclic relations that aren't transitive if they're incomplete), but adding completeness forces the relation to be fully transitive.

内容的提问来源于stack exchange，提问作者Bhavook