Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question
up vote 3 down vote accepted

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

share|cite|improve this answer
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] – 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$.

share|cite|improve this answer
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.

share|cite|improve this answer
+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$.

share|cite|improve this answer
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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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