1
$\begingroup$

Context / Disclosure on the Origins of the Question:

My question is motivated by an MSE question posted earlier today which ultimately was closed. I was thinking about it when it was posted, just for its own sake: I never contended with relations on the empty set in my coursework, and vacuous logic was always something I felt I had a tenuous understanding of at best. So I wanted to make sure my own personal understanding of the question was okay, plus it also made me think of a related question which I ask here.

While I understand that usually reposting previously-closed questions is frowned upon, I feel like in the spirit of this post on Meta, my elaborations and attempts might make me reposting this question worthwhile, and useful for people who come by in the future.

Below, I employ a more proper formulation of the question (that being which of the four properties the empty relation has), and ask a question based on some of the results I saw.


Formulation of the Question:

Since the empty set is a subset of every set, i.e. $\emptyset \subseteq \emptyset$, we can consider the empty relation on the empty set. In studying relations, there are four particular properties we're interested in.

Definitions: Let $R$ be a relation on a set $S$, i.e. $R \subseteq S \times S:$. Then we define four properties of $R$ by the following:

  • Reflexivity: $\forall x \in S, (x,x) \in R$

  • Transitivity: $\forall x,y,z \in S, (x,y), (y,z) \in R \implies (x,z) \in R$

  • Symmetry: $\forall x,y \in S, (x,y) \in R \iff (y,x) \in R$

  • Anti-Symmetry: $\forall x,y \in S, (x,y), (y,x) \in R \iff x=y$

With that in mind, we want to see which of these properties the empty relation on the empty set has.


My Attempts:

For ease in notation, we let $R$ be the empty relation on $\emptyset$, i.e. $R \subseteq \emptyset \times \emptyset = \emptyset$.

Each proof follows through vacuous logic. To my understanding, we can look at each definition from before as an "if this then that" statement - symbolically, $P \implies Q$. If $P$ is always false, then the overall statement is always true, and thus the definition satisfied. So we investigate each property in that light:

  • Reflexivity: Since there exists no $x \in \emptyset$, there is no element $x$ such that $(x,x) \not \in R$. Thus, vacuously, $R$ is reflexive.

  • Transitivity: Similarly, there exists no $(x,y), (y,z) \in R$, so for all such pairs $(x,z) \in R$. Thus, vacuously, $R$ is transitive.

  • Symmetry: For every $(x,y) \in R$, none of which exist, we cannot say there is no $(y,x) \in R$. Therefore, vacuously, $R$ is symmetric.

  • Anti-Symmetric: There are no $(x,y), (y,x) \in R$, and therefore, for all such pairs, vacuously $x=y$ and $R$ is anti-symmetric.


My Questions:

  • Are the above proofs, if not fully formal, at least in the right line of thinking? Are there any particular errors?

  • I noticed that, if so, the empty relation is both symmetric and anti-symmetric. Intuitively, I feel like this is almost self-contradicting (but that's probably an issue in the terminology). Is this a particularly common property for relations that don't involve the empty set and aren't artificially constructed to be this way? I know that per Alessandro Codenotti's answer to this related question the equality relation is both antisymmetric and symmetric. A post on Physics Forums indicates that the only relations which are both symmetric and antisymmetric where $S$ is nonempty are relations $$R = \{(x,x) | x \in S \} \subseteq S \times S$$ This would suggest such relations $R$ are very rare, and not entirely interesting or useful (aside from the aforementioned equality relation). Is this really the case? Do no other such relations exist for nonempty $S$? If so, how would one show that? (Showing this $R$ is indeed both is trivial. Showing no other such $R$ exist ... I'm not sure how to do that.)

$\endgroup$
  • 1
    $\begingroup$ I would argue that the relation = is extremely interesting and useful $\endgroup$ – Holo Jan 2 at 8:07
  • 1
    $\begingroup$ in the second question, do you search for symmetry and anti-symmetry relation, or a relation that satisfy all of the properties?(mainly talking about reflexivity) $\endgroup$ – Holo Jan 2 at 8:14
  • 1
    $\begingroup$ Why aren't people upvoting this question? $\endgroup$ – Git Gud Jan 2 at 8:48
  • 1
    $\begingroup$ "I noticed that, if so, the empty relation is both symmetric and anti-symmetric. Intuitively, I feel like this is almost self-contradicting (but that's probably an issue in the terminology)". You correctly gauged that this is just terminology. For another example and an advice, see this. $\endgroup$ – Git Gud Jan 2 at 8:52
  • 1
    $\begingroup$ To add to @GitGud , it is possible for a set to be both closed and open together (clopen) $\endgroup$ – Holo Jan 2 at 9:11
1
$\begingroup$

In general, when you consider an all-quantified property like $\forall x\in S [ P(x)]$, where $P$ is a predicate in $x$, the assertion is defined as $$\forall x(x\in S\Rightarrow P(x)).$$ The truth-table for the implication, $\Rightarrow$, says that if the premise is false (such as $x\in\emptyset$), then the whole statement is true. That's the thing behind your reasoning.

$\endgroup$
1
$\begingroup$

First, anti-symmetry relation means $(a,b),(b,a)\in R\implies a=b$, it is not if and only if there.

There are more relations that are symmetry and anti-symmetry (exercise, prove that if a relation is both of those, it is also transitive)

For example, let $R$ be relation on $\Bbb N$ such that $(a,b)\in R\iff a=b=0$.

That being said, if $R$ on $A$ relation that satisfy those 2 properties, then $(a,b)\in R\implies a=b$, because $(a,b)\in R\implies (b,a)\in R\implies a=b$.

This way you can also see that adding reflexivity than the only relation is $=$.

Because $(a,a)\in R$ for all $a\in A$, so $=\subseteq R$, but also $(a,b)\in R\implies a=b$, so $R\subseteq =$, thus they are one and the same.

$\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.