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.
Thanks
$\endgroup$ 22 Answers
$\begingroup$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.
$\endgroup$ 5 $\begingroup$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.
$\endgroup$
