# Thread: Relations on A

1. ## Relations on A

Def:
R is irreflexive iff. $\displaystyle a\nsim a \ \forall a\in A$
Not irreflexive iff. $\displaystyle \exists a\in A \ni a\sim a$
R is asymmetric iff. if $\displaystyle a\sim b$, then $\displaystyle b\nsim a$
Not asymmetric iff. $\displaystyle \exists a\sim b$ and $\displaystyle b\sim a$
R is anti-symmetric iff. if $\displaystyle a\sim b \ \mbox{and} b\sim a$, then $\displaystyle a=b$.
Not anti-symmetric iff. $\displaystyle \exists a\sim b \ \mbox{and} \ b\sim a \ \mbox{and} \ a\neq b$
$\displaystyle \bigtriangleup ={(a,a)|a\in A}$

Proofs:
Let R be a nonempty relation on A. If R is symmetric and transitive, then R is not irreflexive.

Since R is symmetric, assume $\displaystyle a\sim b \ \mbox{and} \ b\sim a$. Then, since R is transitive, $\displaystyle a\sim a$. Therefore, R is not irreflexive.
Q.E.D.

If $\displaystyle R\cap R^{-1}=\bigtriangleup$, then R is anti-symmetric.

(1)$\displaystyle R\cap R^{-1}\subseteq\bigtriangleup$
Let $\displaystyle (a,b)\in R\cap R^{-1}$. Therefore, $\displaystyle (a,b)\in R \ \mbox{and} \ (a,b)\in R^{-1}\leftrightarrow (b,a)\in R$. By the anti-symmetric hypothesis, if $\displaystyle a\sim b \ \mbox{and} \ b\sim a$, then $\displaystyle a=b$.

(2)$\displaystyle \bigtriangleup\subseteq R\cap R^{-1}$
$\displaystyle (a,a)\in\bigtriangleup\rightarrow a=a\rightarrow a=b\rightarrow a\sim b \ \mbox{and} \ b\sim a$$\displaystyle \rightarrow (a,b)\in R^{-1} Thus, \displaystyle (a,b)\in R\cap R^{-1} Hence, R is anti-symmetric. If R is transitive and irreflexive, then R is asymmetric. By contradiction: Suppose R is transitive and irreflexive and R is not asymmetric. Let \displaystyle a\sim b \ \mbox{and} \ b\sim a. By transitivity, \displaystyle a\sim a. However, R is irreflexive. Therefore, we have reached a contradiction and R is asymmetric. Are these all logically correct? 2. Originally Posted by dwsmith Def: R is irreflexive iff. \displaystyle a\nsim a \ \forall a\in A Not irreflexive iff. \displaystyle \exist a\in A \ni a\sim a R is asymmetric iff. if \displaystyle a\sim b, then \displaystyle b\nsim a Not asymmetric iff. \displaystyle \exist a\sim b and \displaystyle b\sim a R is anti-symmetric iff. if \displaystyle a\sim b \ \mbox{and} b\sim a, then \displaystyle a=b. Not anti-symmetric iff. \displaystyle \exist a\sim b \ \mbox{and} \ b\sim a \ \mbox{and} \ a\neq b \displaystyle \bigtriangleup ={(a,a)|a\in A} Proofs: Let R be a nonempty relation on A. If R is symmetric and transitive, then R is not irreflexive. If this one was true then there wouldn't be equivalence relations... Tonio Since R is symmetric, assume \displaystyle a\sim b \ \mbox{and} \ b\sim a. Then, since R is transitive, \displaystyle a\sim a. Therefore, R is not symmetric. Q.E.D. If \displaystyle R\cap R^{-1}=\bigtriangleup, then R is anti-symmetric. (1)\displaystyle R\cap R^{-1}\subseteq\bigtriangleup Let \displaystyle (a,b)\in R\cap R^{-1}. Therefore, \displaystyle (a,b)\in R \ \mbox{and} \ (a,b)\in R^{-1}\leftrightarrow (b,a)\in R. By the anti-symmetric hypothesis, if \displaystyle a\sim b \ \mbox{and} \ b\sim a, then \displaystyle a=b. (2)\displaystyle \bigtriangleup\subseteq R\cap R^{-1} \displaystyle (a,a)\in\bigtriangleup\rightarrow a=a\rightarrow a=b\rightarrow a\sim b \ \mbox{and} \ b\sim a$$\displaystyle \rightarrow (a,b)\in R^{-1}$ Thus, $\displaystyle (a,b)\in R\cap R^{-1}$

Hence, R is anti-symmetric.

If R is transitive and irreflexive, then R is asymmetric.

By contradiction: If R is transitive and irreflexive, then R is not asymmetric.
Let $\displaystyle a\sim b \ \mbox{and} \ b\sim a$. By transitivity, $\displaystyle a\sim a$. However, R is irreflexive. Therefore, we have reached a contradiction and R is asymmetric.

Are these all logically correct?
.

3. Originally Posted by dwsmith
Def:
R is irreflexive iff. $\displaystyle a\nsim a \ \forall a\in A$
Not irreflexive iff. $\displaystyle \exist a\in A \ni a\sim a$
R is asymmetric iff. if $\displaystyle a\sim b$, then $\displaystyle b\nsim a$
Not asymmetric iff. $\displaystyle \exist a\sim b$ and $\displaystyle b\sim a$
R is anti-symmetric iff. if $\displaystyle a\sim b \ \mbox{and} b\sim a$, then $\displaystyle a=b$.
Not anti-symmetric iff. $\displaystyle \exist a\sim b \ \mbox{and} \ b\sim a \ \mbox{and} \ a\neq b$
$\displaystyle \bigtriangleup ={(a,a)|a\in A}$
This is how it should be.

Suppose ~ is a relation on a set A. Consider the following definitions.

$\displaystyle \sim$ is irreflexive iff $\displaystyle \forall a\in A,\;a\nsim a$.

$\displaystyle \sim$ is asymmetric iff $\displaystyle \forall a, b\in A$, if $\displaystyle a\sim b$, then $\displaystyle b\nsim a$.

$\displaystyle \sim$ is antisymmetric iff $\displaystyle \forall a, b\in A$, if $\displaystyle a\sim b \ \mbox{and } b\sim a$, then $\displaystyle a=b$.

$\displaystyle \bigtriangleup =\{(a,a)\mid a\in A\}$

Therefore:

$\displaystyle \sim$ is not irreflexive iff $\displaystyle \exists a\in A,\;a\sim a$.

$\displaystyle \sim$ is not asymmetric iff $\displaystyle \exists a,b\in A,\;a\sim b\mbox{ and }b\sim a$.

$\displaystyle \sim$ is not antisymmetric iff $\displaystyle \exists a,b\in A,\;a\sim b \ \mbox{and} \ b\sim a \ \mbox{and} \ a\neq b$.

(After looking at the source of your post, I see that existential quantifiers were not shown because they were misspelled as \exist instead of \exists.)

4. Originally Posted by tonio
Let R be a nonempty relation on A. If R is symmetric and transitive, then R is not irreflexive.

If this one was true then there wouldn't be equivalence relations...
The claim is that the relation is not irreflexive. One does not claim it is not reflexive.

Originally Posted by dwsmith
Proofs:
Let R be a nonempty relation on A. If R is symmetric and transitive, then R is not irreflexive.

Since R is symmetric, assume $\displaystyle a\sim b \ \mbox{and} \ b\sim a$. Then, since R is transitive, $\displaystyle a\sim a$. Therefore, R is not symmetric.
Q.E.D.
Should be:

Proposition 1. Let ~ be a nonempty relation on A. If ~ is symmetric and transitive, then R is not irreflexive.

Proof.
...
Therefore, ~ is not irreflexive.
Q.E.D.

Now, concerning the proof. You should stress where you use the fact that the relation is nonempty: assume that a ~ b. I would also say, "since ~ is symmetric, we have b ~ a" instead of assuming that b ~ a.

If $\displaystyle R\cap R^{-1}=\bigtriangleup$, then R is anti-symmetric.

(1)$\displaystyle R\cap R^{-1}\subseteq\bigtriangleup$
Let $\displaystyle (a,b)\in R\cap R^{-1}$. Therefore, $\displaystyle (a,b)\in R \ \mbox{and} \ (a,b)\in R^{-1}\leftrightarrow (b,a)\in R$. By the anti-symmetric hypothesis, if $\displaystyle a\sim b \ \mbox{and} \ b\sim a$, then $\displaystyle a=b$.

(2)$\displaystyle \bigtriangleup\subseteq R\cap R^{-1}$
$\displaystyle (a,a)\in\bigtriangleup\rightarrow a=a\rightarrow a=b\rightarrow a\sim b \ \mbox{and} \ b\sim a$$\displaystyle \rightarrow (a,b)\in R^{-1}$ Thus, $\displaystyle (a,b)\in R\cap R^{-1}$
You are proving the converse of what is claimed. Besides, in (2), $\displaystyle (a,a)\in\bigtriangleup\rightarrow a=a\rightarrow a=b$ does not make sense. One does not need to know that $\displaystyle (a,a)\in\bigtriangleup$ to conclude a = a, which is always true. Also, it is not clear what b is and so no reason to conclude that a = b.

If R is transitive and irreflexive, then R is asymmetric.

By contradiction: If R is transitive and irreflexive, then R is not asymmetric.
Is this what you are going to show? If you want to prove the original claim by contradiction, then you need to show (1) that R being transitive, irreflexive and asymmetric is impossible or (2) that if R is not asymmetric, then R cannot be transitive and irreflexive. Proving (1) is more natural.

Let $\displaystyle a\sim b \ \mbox{and} \ b\sim a$.
What if the relation is empty and you cannot find such a and b?

5. How is $\displaystyle \displaystyle \bigtriangleup\subseteq R\cap R^{-1}$ direction proved?

6. Originally Posted by emakarov
The claim is that the relation is not irreflexive. One does not claim it is not reflexive.

Well, it is what was claimed first time I read the message. Then somebody fixed that.

A very annoying thing to do, by the way.

Tonio

Should be:

Proposition 1. Let ~ be a nonempty relation on A. If ~ is symmetric and transitive, then R is not irreflexive.

Proof.
...
Therefore, ~ is not irreflexive.
Q.E.D.

Now, concerning the proof. You should stress where you use the fact that the relation is nonempty: assume that a ~ b. I would also say, "since ~ is symmetric, we have b ~ a" instead of assuming that b ~ a.

You are proving the converse of what is claimed. Besides, in (2), $\displaystyle (a,a)\in\bigtriangleup\rightarrow a=a\rightarrow a=b$ does not make sense. One does not need to know that $\displaystyle (a,a)\in\bigtriangleup$ to conclude a = a, which is always true. Also, it is not clear what b is and so no reason to conclude that a = b.

Is this what you are going to show? If you want to prove the original claim by contradiction, then you need to show (1) that R being transitive, irreflexive and asymmetric is impossible or (2) that if R is not asymmetric, then R cannot be transitive and irreflexive. Proving (1) is more natural.

What if the relation is empty and you cannot find such a and b?
.

7. What?

I didn't make an changes until today 3:52 today, and what I changed was the line at the end stating: Therefore, R is not irreflexive (I had symmetric in this line by accident first).

8. Originally Posted by dwsmith
How is $\displaystyle \displaystyle \bigtriangleup\subseteq R\cap R^{-1}$ direction proved?
Why do you want to prove something you are given?

9. I am not given that it is a subset. It says they are equal, but to prove the are equal I must prove they are both subsets of each other, correct?

10. Of the three problems in the OP, only the second one mentions $\displaystyle \Delta$: "If $\displaystyle R\cap R^{-1}=\bigtriangleup$, then R is anti-symmetric." In this problem $\displaystyle R\cap R^{-1}=\bigtriangleup$ is an assumption, not something to prove.

11. This is what you are to prove.
Given that $\displaystyle R\cap R^{-1}=\Delta$ prove that $\displaystyle R$ is anti-symmetric.
Proof:
If $\displaystyle (a,b)\in R~\&~(b,a)\in R$ then it follows that $\displaystyle (b,a)\in R^{-1}~\&~(a,b)\in R^{-1}$ by definition.
That implies that $\displaystyle (a,b)\in(R\cap R^{-1})$.
BUT $\displaystyle R\cap R^{-1}=\Delta$ so $\displaystyle (a,b)\in \Delta$ so $\displaystyle a=b$.