# Does the reflexivity mean maximum element in partial ordering $x \leq x$ for every $x \in S$

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?

-

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).

-
Let's consider $g(x)=x+1$. $g=\{(x,Sx), a:=(x ≡ λf.λx. fn x, S≡\lambda x.+ x 1), +≡λm.λn.λf.λx. m f (n f x))\} \not\supset \{(Sx,x), a\}$ where the $a$ is an assignment, the $fn$ is $n$-fold composition, i.e. $\lambda f.\lambda x. x=0, \lambda f.\lambda x. fx=1, \lambda f.\lambda x. fn x=n$, and the $+$ is a function that takes two functions $1$ and $n$ and return a function, the numbers are [1]. So $g$ is not a reflexive function. [1] en.wikipedia.org/wiki/Church_numeral –  hhh Feb 4 '11 at 4:02
err $\notsupset$ should be there (cannot edit it for some reason). –  hhh Feb 4 '11 at 4:13
Very insightful, big thanks. Vote him up! –  hhh Feb 4 '11 at 4:20

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$.

-
can you give some example with such signs where it is not trivial? –  hhh Feb 4 '11 at 2:39
@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. –  Ross Millikan Feb 4 '11 at 3:50

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.

-
+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? –  hhh Feb 4 '11 at 2:35

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$.

-
why are you actually choosing power set? Each set is a subset of itself despite not being a member of a power set. But to prove reflexivity this way, you must interpret it correctly. Seems like proof by exhaustion but it may not work in every case or error-prone. Can you find non-trivial example? –  hhh Feb 4 '11 at 2:56
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. –  milcak Feb 4 '11 at 3:23