# Minimum number of elements in equivalence relation

I'm just wondering if my thinking is correct here.

A is set {1,2,3,4,5} and R is a relation on A so that R ⊂ A x A.

If R isn't an equivalence relation, then the minimum number of elements R could have is 1 or 0? Would R = {} or would R = {{}}? R is a set so I was thinking R = {{}}

And if R is an equivalence relation, would the minimum number of elements R could have is 5? R = {(1,1),(2,2),(3,3),(4,4),(5,5)}? Or can empty set be reflexive, symmetric and transitive?

• For an equivalence relation we must have $a\sim a$ for each element $a\in A$.
– lulu
Jan 13 at 19:25
• As an aside, the empty relation would be the empty set $\{\}$. The set containing the empty set $\{\{\}\}$ is not a subset of $A\times A$ here and is not equal to the empty relation. The empty relation is vacuously symmetric and transitive over any set $A$ but is not reflexive whenever $A$ is itself non-empty. Jan 13 at 19:36
• In order to understand why the empty set satisfies the defining properties of an equivalence relation, you can use this fact " when the antecedent of a material conditional is false, the whole conditional is true". Jan 14 at 8:36
• @VinceVickler The empty relation is not reflexive (given nonempty $A$) and as such is not an equivalence relation Jan 14 at 14:38

## 2 Answers

If $$R$$ is a binary relation on $$A$$, then $$R$$ could be the empty set, which has $$0$$ elements.

If $$R$$ is an equivalence relation on $$A$$, then $$R$$ must be reflexive, which requires that $$(x, x) \in R$$ for each $$x \in A$$. So $$R$$ must have at least $$|A| = 5$$ elements.

First things first $$\{\{\}\} = \{\emptyset\}$$ is a set with one element in it. That element is the empty set. As $$R\subset A\times A$$ and $$A\times A$$ is a set of ordered pairs of elements of $$A$$, the empty set (as an object) is not an ordered pair. So the emptyset is not an element of $$A\times A$$ so the set containing the the emptyset, that is the set $$\{\emptyset\}$$ can not be a subset of $$A\times A$$ so $$R= \{\emptyset\}$$ is not possible.

One the other hand the empty set, itself, the set with no elements is a subset of all sets. (As $$\emptyset$$ has no elements all of its elements (all zero of them) can be said to be ... anything... so $$\emptyset \subset A\times A$$. That is true because $$\emptyset$$ has no elements it doesn't have any elements that are not in $$A\times A$$). So $$R = \{\} = \emptyset$$ is possible.

Now to second things. $$R = \{\}$$ is certainly a relationship as it is a subset of $$A\times A$$. It is called the empty relationship and one can think of it as the relationship where nothing is related to anything.

If we assume $$A$$ is not empty[1], then $$R=\emptyset$$ is not reflexive. For every $$a\in A$$ it is not the case that $$(a,a)\in \emptyset$$. That is certainly false[1].

So it is not an equivalence relation.

It turns out it is (vacuously) symmetric and transitive. If $$(a,b) \in \emptyset$$ (which is impossible and never happens) then $$(b,a)\in \emptyset$$ because a false hyptothesis ($$(a,b)\in \emptyset$$) can lead to any conclusion. There is no case of $$(a,b)\in \emptyset$$ where $$(b,a)\not\in \emptyset$$ because there is no case of $$(a,b) \in \emptyset$$ period. So it is symmetric. Likewise it is transitive as $$(a,b)\in \emptyset$$ and $$(b,c)\in \emptyset$$ never happen so every time they never happen $$a,c\in \emptyset$$.... but that's not important. It's not an equivalence relation because it is not reflexive.[1]

As an equivalence relation must be reflexive it must contain all $$(a,a)$$ and if $$A = \{1,2,3,4,5\}$$ we must have $$\{(1,1),(2,2),(3,3),(4,4),(5,5)\}\subset R$$ if $$R$$ is an equivalence relation. The question is must $$R$$ contain any more elements.

And it does not have to. $$R= \{(a,a)| a\in A\}\subset A\times A$$ is an equivalence relation.

It is reflexive as for all $$a\in A$$ we have $$(a,a)$$ in $$R$$.

It is symmetric because if $$(a,b)\in R$$ then $$a=b$$ and if $$a=b$$ then $$(a,b)=(a,a)= (b,a)$$ and $$(b,a)\in R$$.

It is transitive because if $$(a,b) \in R$$ and $$(b,c)\in R$$ then $$a=b$$ and $$b=c$$ so $$a=c$$ and $$(a,c) =(a,a)\in R$$.

So $$R=\{(a,a)|a\in A\}$$ is the smallest possible equivalence relation on a (non-empty[2]) $$A$$.

====

[1] If $$A$$ is empty then $$A\times A = \{(a,b)|a,b\in \emptyset\} = \{\} = \emptyset$$. And as a relation $$R = \emptyset \subset \emptyset = A\times A$$ we do have that $$R$$ is an equivalence relationship and is reflexive.

As there are no $$a\in A=\emptyset$$ it is a vacuously true statement that $$(a,a)\in \emptyset$$ (because there is not such $$(a,a)$$!) so $$R$$ is reflexive (and transitive and symmetric).

That as it is a relation ... on nothing it is considered utterly trivial and boring and we never bother dealing with it. But theoretically $$R = \emptyset$$ is the only relation on the emptyset itself and it is an equivalence relation.

[2] And on an empty $$A$$ we have $$R= \{(a,a)|a\in \emptyset\} =\{\}=\emptyset$$ so we can say $$R=\{(a,a)|a\in \emptyset\}$$ is the smallest equivalence relationship on any set $$A$$ (empty or not).