0
$\begingroup$

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?

$\endgroup$
4
  • $\begingroup$ For an equivalence relation we must have $a\sim a$ for each element $a\in A$. $\endgroup$
    – lulu
    Jan 13 at 19:25
  • $\begingroup$ 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. $\endgroup$
    – JMoravitz
    Jan 13 at 19:36
  • $\begingroup$ 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". $\endgroup$ Jan 14 at 8:36
  • $\begingroup$ @VinceVickler The empty relation is not reflexive (given nonempty $A$) and as such is not an equivalence relation $\endgroup$
    – JMoravitz
    Jan 14 at 14:38

2 Answers 2

1
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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