2
$\begingroup$

enter image description here enter image description here

What is the significance of the phrase "for any two objects $x,y \in X$, the statement $x \leq_X y$ is either a true statement or a false statement."?

By the law of the excluded middle, I think that it's always the case that $x \leq_X y$ is either true or not true. Does that mean a "partially ordered set" is not more restrictive than simply a "set"?

$\endgroup$
  • $\begingroup$ A set by itself does not need to even have a relation in the first place, much less a partial order. A partially ordered set specifically needs to have a partial order. A partially ordered set is the combination of both a set and a partial order. In that sense, a partially ordered set is more restrictive than a set. $\endgroup$ – JMoravitz Jan 17 '18 at 23:49
  • $\begingroup$ There is a word thus at the beginning of that sentence. $\leq_X$ being a relation implies $x \leq_X y$ is either true or false. $\endgroup$ – stochastic Jan 17 '18 at 23:55
  • $\begingroup$ It is trying to avoid saying "either $x \le_X^{\,} y$ or $y \lt_X^{\,} x$", which is a property of totally ordered sets but not necessarily partially ordered sets $\endgroup$ – Henry Jan 17 '18 at 23:56
  • 1
    $\begingroup$ The following quoted statement about a 'mere' set $X$ is false: "for any set $X$, and any $x, y \in X$, either the statement $x \le_X y$ is true or it is false." It is false for a silly reason, which is that it refers to an ordering $\le_X$, which a 'mere' set doesn't have. Once you equip the set $X$ with the ordering $\le_X$, then, as you say, it is immediately the case that "for any $x, y \in X$, either the statement $x \le_X y$ is true or it is false". As @stochastic points out, this is what 'thus' means in the quoted statement. $\endgroup$ – LSpice Jan 18 '18 at 0:05
  • $\begingroup$ (The book may just be trying to emphasise that the relation is written infix; that is, that one doesn't use the awful but technically correct notation "$(x, y) \in {\le_X}$", but rather changes it to "$x \le_X y$". It's similar to how we denote the value of the function ${+} : \mathbb R \times \mathbb R \to \mathbb R$ at $(2, 3)$ not by ${+}(2, 3)$, but by $2 + 3$; we just don't mention this convention because it is so ingrained.) $\endgroup$ – LSpice Jan 18 '18 at 0:06
2
$\begingroup$

Not having more context I would have to guess. But it looks like instead of looking at relations as subsets of $X\times X$, the text is looking as relations as predicates: so $ x\leq y$ is established by means of a certain assertion.

The issue is that with that point of view it could be the case that the assertion is neither true or false, in the same sense that "this sentence is false" is neither true or false (i.e., Russell's Paradox).

So the text is saying that you have a relation when the $x\leq y$ is actually a statement (that is, true or false) for all $x,y$.

$\endgroup$
2
$\begingroup$

It just means that the $\leq_X$ binary operator must be a predicate function that is in fact defined for any pair of elements from $X^2$ (ie, it is surjective ). $~\leq_X : X{\times} X\twoheadrightarrow \{\bot,\top\}$

Which, yeah, should not really need to be stated, but better safe than sorry.

$\endgroup$
1
$\begingroup$

There is a word thus at the beginning of that sentence. That is, [$\leq_X$ being a relation on $X$] implies that [for all $x,y\in X$, $x \leq_X y$ is either true or false].

$\endgroup$
1
$\begingroup$

You're right. That parenthetical statement by itself effectively says nothing; I think the authors put it there to help the reader conceptually think about the nature of the structure involved. But it is not what makes it a partial order.

It is the three properties listed after that that makes it a partial order ... and which makes it more than simply a 'set'. Indeed, the fact that we are dealing with a binary relation already makes it more than just any 'set'.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.