1
$\begingroup$

The notation of my teacher confuses me in the title. If x is the same on the both sides, it seems trivial. So I suspect the x is different so it becomes:

$x_{1}\leq x_{2}$ for every $x_{1} \in S$

so what it would mean is that every $x_{1} \in S$ has a maximum element $x_{2}$ that does not need be in $S$. Attacking the problem with an example, why not trivial with the explicit interpretation in the following. I can imagine a partial ordering that would satisfy the condition like cardinality with a $n$-cube where $n$ is the number of nodes and the number of nodes is $2^{n}$. To prove the condition in the case would require to show that the subsets form a chain with each nodes like the case with 3-cube $card(\emptyset) \leq card(\{1\}) \leq card(\{2\}) ... \leq card(\{1,2\}) \leq card(\{1,2,3\})$.

So what does the reflexive -term mean? Am I interpreting it right about maximum element or am I leaping to conclusion?

4 Answers 4

2

No, it should in fact be $x \le x$, for every $x \in S$. I myself find it best to think of power sets, partially ordered by inclusion $\subset$.

So let $\mathcal{P}(S)$ be the power set of some set $S$, and let $A \in \mathcal{P}(S)$. Here it's easy to see what $A \subset A$ means: every set is a subset of itself. You can check that transitivity and antisymmetry hold here as well.

And no, it doesn't mean that there is a maximal element. For example, $\mathbb{R}$ is partially ordered by $\le$.

  • 0
    What you say is true indeed, but you never just talk about a *partial ordering* but rather a *partial ordering on a set.* Yes, for any set $A$, it is true that $A \subset A$. But what set does $A$ belong to? Of course it need not be a power set. It could just be a set containings sets as elements - but talking about an order on a power set is more conventional.2011-02-04
3

It seems trivial just because you're using a familiar symbol $\le$ for a relation that you really do not know. Try a different symbol such as $\preceq$ or $\triangleleft$.

  • 0
    @hhh: the signs are just comparison signs that we use to look different from the usual $\ge$. They do not have a canonical meaning, but generally do mean at least a partial order rather than an arbitrary relation.2011-02-04
3

For an order, reflexive means just what you said in the title. For all $x \in S$ you have $x \le x$ This is a useful requirement to place on orders. Without it, you could have an "order" that was simply $\forall x,y \in S \neg (x\le y)$ That doesn't seem like an order and would ruin lots of what we want to say about orders.

  • 0
    +1 for quantifying but what does it really mean to prove that something is reflexive? Wondering... I could always take your case $\forall x,y \in S \neg (x \leq y)$ and to lead it to contradiction so it must be reflexive but it may not always be easy, ideas/examples to prove reflexivity in non-trivial cases?2011-02-04
3

A relation $R$ on a set $S$ is just a subset of $S\times S$, that is, a set of pairs of elements from $S$. If $(a,b) \in R$ then $aRb$. As an example, here is the $<$ relation on $\{1,2,3\}$: $< = \{(1,2),(1,3),(2,3)\}.$ So $1<3$ because $(1,3) \in <$. On the other hand, $1 \nless 1$ since $(1,1) \notin <$. So $<$ is an example of a non-reflexive (in fact, anti-reflexive) relation. The corresponding reflexive relation $\leq$ is $\leq = \{(1,1),(1,2),(1,3),(2,2),(2,3),(3,3)\}.$ Both relations are \emph{transitive}, that is $aRb$ and $bRc$ together imply $aRc$. That need not be true in general, for example it fails in $R = \{(1,2),(2,3)\}$ since $1R2$ and $2R3$ but $1\not{R}3$. In this case the relation $R$ represents the successor function, but in general a relation can be arbitrary. A third useful property is antisymmetry. It is the property that guarantees that if $x \leq y$ and $y \leq x$ then $x = y$. It usually fails, for example, in the case of an equivalence relation. A fourth property is that for every $x,y \in S$, either $x \leq y$ or $y \leq x$; along with reflexivity and transitivity these are the defining properties of a total order. This property fails, for example, for the set inclusion relation $\subseteq$.

As Ross mentioned, usually we're not interested in general relations but in some "well-behaved" ones. A good example is a function, when viewed as a relation (try to think yourself how to do that). Other common examples are partial orders (reflexive and transitive), total orders and equivalence relations (reflexive, symmetric and transitive).

  • 0
    Very insightful, big thanks. Vote him up!2011-02-04