I came across this following problem:
Let $R$ be a reflexive relation on a finite set $A$ having $n$ elements and let there be $m$ ordered pairs in $R$, then:
A) $m\ge n$
B) $m \le n$
C) $m=n$
D) None of these
I initially started with taking a simple example:
Let set $A$ was ${1,2,3,4,5,6}$ then one of the relations on it could be:
$R={(1,1),(2,2),(1,2)}$ which is reflexive right?
so this(according to my knowledge) showed that m doesn't have to be $\le$ or $\ge$ than n. But the answer showed that I was wrong and $m\ge n$ But why does this happen?
Is it necessary for all the elements of $A$ to be included in $\mathbb R$ for it to be reflexive? That is, considering the previous example, do the pairs $(1,1), (2,2),(3,3),(4,4),(5,5),(6,6)$ need to exist in $R$ for it to be reflexive?
I have this conceptual confusion about what a reflexive relation really is and would be glad if someone could clear this out.
Another sort of counter question to this, then technically is an equivalence relation even possible for sets like the set of natural numbers as the following example illustrates what I mean:
lets take any relation $R$ defined on the set of natural numbers,
$R=${$(2,3),(3,4)$}
then what minimum number of ordered pairs should we add to make it an equivalence relation ?
Does the word 'minimum' allow us to not care about adding all the ordered pairs of natural numbers, that is, $(1,1),(2,2),(3,3),(4,4)$ and so on…?
Best Answer
A relation $R$ on a set $A$ is reflexive iff for every $a\in A$ we have $(a,a)\in R$. Note that this means that unlike transitivity and symmetry, reflexivity crucially depends on the "carrier set" involved". So for example, $\{(1,1),(2,2),(1,2)\}$ is reflexive as a relation on $\{1,2\}$ but is not reflexive as a relation on $\{1,2,3\}$.
Note that one consequence is that a reflexive relation on a set must have at least as many elements as that set; in particular, addressing one of your later questions, every reflexive relation on $\mathbb{N}$ contains infinitely many ordered pairs.
This "context dependence" may feel odd at first, but it's a crucial aspect of the definition.