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

I'm not quite getting the concept of a reflexive set in my discrete math class. I think I understand that a reflexive set is the product of set $\mathit{A} \times \mathit{A}$ the idea that we're making a subset from $\mathit{A}$ from its elements. Looking on wikipedia, I see that the notion is that each element is related to itself. I think I get this, but I'm not sure. Let me know show you what's in my book:

  • $\left \{ (x,y) \in \mathbb{R}^{2} \mid x \leq y \right \}$ is a reflexive relation on $\mathbb{R}$ since $ x \leq x $ for any $x \in \mathbb{R}$

  • $\left \{ (a,b) \in \mathbb{N}^{2} \mid \frac{a}{b} \in \mathbb{N}\right \}$ is a reflexive relation on $\mathbb{N}$ since $\frac{a}{a}$ is an integer, 1, for any $a \in \mathbb{N}$

  • $\mathit{R} = \left \{ (x,y) \in \mathbb{R}^{2} \mid x^{2} + y^{2} > 0 \right \}$ is not a reflexive relation on $\mathbb{R}$ since $(0,0) \notin \mathit{R}$

To better understand what's confusing me to the first bullet point. Why use $(x,y)$ and then say that $x \leq x$. If that is indeed talking about the same $x$ value, how can it be anything but equal to it? If it is talking about the same value/element, why is $(x,y)$ used in the beginning? If we're only compre $x$ with $x$ why use $y$? That seems to imply two different elements.

Please help me understand what this is talking about.


share|cite|improve this question
To answer the specific confusion: $(x,y)$ means for all $x$ and all $y$, including cases when they are different and also cases when they are the same. A relation is defined in this way; but reflexivity is concerned only about the special case where $y=x$, which is abbreviated as $(x,x)$. – vadim123 Feb 16 '14 at 22:33
Try to separate out the formal definition of a relation from what that definition actually means. We formally define relations as sets of pairs because that lets us found everything on sets, but we really mean is that a relation is basically a statement involving two things, like "this is bigger than that". – Jack M Feb 16 '14 at 23:21
up vote 5 down vote accepted

Reflexivity is not an internal property of a relation. Given a relation $R$ we don't have a sufficient information to decide whether or not it is reflexive. The reason is that we say that $R$ is reflexive on $A$ rather than just reflexive.

The relation $\{(0,0)\}$ is certainly not reflexive as a relation on $\Bbb N$, but it is reflexive as a relation on $\{0\}$.

We say that $R$ is reflexive on $A$, if every $a\in A$ satisfies the relation with itself, that is to say $(a,a)\in R$. So we require that all the elements of $A$ will have this, so in the above example this property fails for $\Bbb N$ but holds for $\{0\}$, because not all the elements of $\Bbb N$ satisfy $(n,n)\in\{(0,0)\}$; but every element of $\{0\}$ does satisfy that.

Note, perhaps to your confusion, that a reflexive relation is not just the pairs of the form $(x,x)$, but rather a large collection of pairs, but it has to include these pairs. For example, $A\times A$ is always a reflexive relation on $A$.

The examples that you gave in your question are examples where a particular relation is defined, it has more pairs than just $(x,x)$ for the appropriate $x$; and we argue that the first relation is reflexive because $x\leq x$ means that $(x,x)$ is an ordered pair which appears in this relation.

share|cite|improve this answer
I apologize for taking so long in commenting/responding. I'm still trying to wrap my mind around this. Please, how is $\{(0,0)\}$ a relation? How is $0$ related to $0$? It's the same number. I can understand some of what you've written, but I'm still struggling on others. For example, why bother with $x \leq x$ when $x$ can't be less than itself. $x = x$ but $x < x$ is ludicrous. – Andrew Falanga Feb 18 '14 at 2:19
How do you define "relation"? – Asaf Karagila Feb 18 '14 at 4:18
Well, my book says that the Cartesian Product of $A$ x $B$, $(a, b)$ being an ordered pair of that product, is a binary relation. So, I'm reading $\{(0,0)\}$ as a relation of some sort. I'm just not seeing how they're related since they're the same thing. Am I making sense? – Andrew Falanga Feb 19 '14 at 0:33
Yes, it is a common beginners mistake. Relations are sets of ordered pairs. Period. Why these ordered pairs and not others is not important. There is a definition and we work strictly with it. – Asaf Karagila Feb 19 '14 at 3:44
Thank you for the explanations. After a lecture on this subject, I think I see where I was going wrong. I was seeing the ordered pairs as the relation, but in fact they are the result of the relation $x \leq y$ in this case. After the prof showed a few sets, and we looked at their ordered pairs, I also became aware of another mistake. A relation $R$ isn't reflexive if every ordered pair is $\{(a,a)\}$ for each $a \in A$. Rather, it is reflexive simply if for $a \in A$ there exists the pair $\{(a,a)\}$: perhaps among many other pairs. Thanks everyone for you patience. – Andrew Falanga Feb 24 '14 at 14:31

Let's write $a\prec b$ to mean “$a$ is the mother of $b$”. Then $\prec$ is a relation on people. We have for example $\text{Eve}\prec\text{Cain}$ because Eve was the mother of Cain, and $\text{Cain}\not\prec\text{Abel}$ because Cain was not the mother of Abel.

The way we model relations like $\prec$ is as a special sort of set. The set that models $\prec$ is the set $M$ of all pairs of people, $(a,b)$, for which $a\prec b$. So for $\prec$, the set $M$ includes the pair $(\text{Eve},\text{Cain})$, but it does not include the pair $(\text{Cain},\text{Abel})$.

There's a sense in which this set completely captures everything about the relation. Knowing $M$ tells you absolutely everything about who is the mother of whom, because for any people $a$ and $b$, we have $a$ is the mother of $b$ if and only if the pair $(a,b)$ is in $M$. If you know $M$, and if someone asks you whether Florence Nightingale was the mother of Michael Jordan, you just look to see if $(\text{Florence Nightingale}, \text{Michael Jordan})$ is a member of $M$. That pair is not in $M$, so you know that Michael Jordan's mother was someone else.

The reason we represent relations as sets in this way is that it reduces the idea of relations to the simpler idea of sets. We already know a lot about sets, and we have language for talking about things like intersections of sets and subsets of sets. By modeling relations as sets in this way, we get to apply all our set theory to work for relations also. This saves a lot of trouble and effort—you only have to understand one kind of thing.

Now let's consider $\le$, defined on $\def\R{\Bbb R}\R$. This can be modeled as a certain set, which we might call $L$, consisting of all pairs of numbers $(a,b)$ for which $a\le b$. So for example, $(3,4)$ is member of $L$, because $3\le 4$, but $(4,3)$ is not a member of $L$, because it is not true that $4\le3$. And it is the case that $(4,4)$ is a member of $L$, because it is the case that $4\le 4$.

A relation $\prec$ is reflexive on some set $S$ if $s\prec s$ is true for every element $s$ of $S$. Or, if we are thinking of the set formulation of $\prec$, we might say that $\prec$ is modeled by some set of pairs $P$, so that $(a,b)$ is in $P$ exactly when $a\prec b$. Then $\prec$ is reflexive on $S$ if $P$ contains $(s,s)$ for every element of $S$. Because to say that $P$ contains $(s,s)$ is just another way of saying that $s\prec s$. Because we are understanding relations as a certain kind of set, we can talk about sets being reflexive.

Now $\le$. Is $\le$ reflexive on $\R$? We can phrase this in the language of relations, in which case $\le$ is reflexive if $a\le a$ for every $a$ in $\R$—this is certainly true. Or we can put it in the language of sets: $\le$ is modeled by the set $L$ of all pairs $(a,b)$ for which $a\le b$, and it is reflexive on $\R$ if $(a,a)$ is in $L$ for every $a$ in $\R$. But these are two ways of saying the same thing.

Now let's look at your confusing bullet point:

  • $\left \{ (x,y) \in \mathbb{R}^{2} \mid x \leq y \right \}$ is a reflexive relation on $\mathbb{R}$ since $ x \leq x $ for any $x \in \mathbb{R}$

The $\left \{ (x,y) \in \mathbb{R}^{2} \mid x \leq y \right \}$ part is defining a set, the set of all pairs of numbers $(x,y)$ for which $x\le y$. This is the set-theoretic model of the $\le$ operator. It could be left out here; we could have just said

  • $\le$ is a reflexive relation on $\mathbb{R}$ since $ x \leq x $ for any $x \in \mathbb{R}$

Why didn't Wikipedia do this? Bad editing. It's Wikipedia, it's full of lousy editing.

Finally, you should know that mathematicians will often ignore the fact that the sets of pairs are being used as models of relations, and will take the view that the relation is the set of pairs, and will talk about them interchangeably. This kind of abstraction is very important in mathematics, and mathematicians are so used to it that they don't notice when they are doing it. It can take a while to get used to, but it will soon become natural.

share|cite|improve this answer

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.