0
$\begingroup$

Let $A = \{1,2,3\}$. Write the ordered pairs for a binary relation R on A which is reflexive and symmetric, but not transitive.

From my understanding is when listing if we want reflexive we need every example. However, for symmetric and reflexive providing ONE example is enough to show it. So if I wanted it to be transitive I can just do $\{(2,3),(3,1)$ and $(2,1)\}$. HOWEVER, when looking at solutions I'm extremely confused.

The solution is $\{(1,1),(2,2),(3,3)(1,2),(2,1),(2,3),(3,2)\}$ I get it's reflexive because (a,a) is always there. and I get it's symmetric because $(1,2),(2,1)$. Our prof says that $(1,2)$ and $(2,3)$ is in the list, but $(1,3)$ is not therefore it's not transitive.BUT how doesn't $(1,2),(2,1),(1,1)$ make it transitive. Isn't this one example enough to show its transitive???

$\endgroup$
5
  • $\begingroup$ Are you talking about equivalence relations or just looking for one example in the set? $\endgroup$ Oct 11 '20 at 0:08
  • $\begingroup$ "BUT how doesn't (1,2),(2,1),(1,1) make it transitive. Isn't this one example enough to show its transitive???" No, every possible triplet must be in there. And you have $(1,2)$ and $(2,3)$ but not $(1,3)$ si it can't be transitive. (And you don't need any examples to be symmetric. You just can't have any counterexamples). $\endgroup$
    – fleablood
    Oct 11 '20 at 0:24
  • $\begingroup$ One example, doesn't show it is any property. But a counter example shows it doesn't have the the property. $\endgroup$
    – fleablood
    Oct 11 '20 at 0:28
  • $\begingroup$ Having $(1,2)$ and $(2,1)$ is not enough to show it is transitive. YOu also have that as $(2,3)$ is in it must have $(3,2)$. If you had $(1,2)$ and $(2,1)$ and $(2,3)$ but not $(3,2)$ it would not be symmetric. Also if you had $(1,1), (2,2),(3,3)$ but no other it would be symmetric. $\endgroup$
    – fleablood
    Oct 11 '20 at 0:30
  • $\begingroup$ Brian Borcher has given a good answer. Recheck the definitions of reflexive, symmetric and transitive relations. For example on the set A you've given, R1= {(1,1)} is not a reflexive relation because it doesn't contain (2,2) or (3,3). But R2={(1,1),(2,2),(3,3),(1,3),(3,2),(2,3)} is a reflexive relation. But R2 is not symmetric because it contains (1,3) but not (3,1). Also R2 is not transitive because it contains (1,3) and (3,2) but not (1,2). $\endgroup$ Oct 11 '20 at 1:15
4
$\begingroup$

BUT how doesn't (1,2),(2,1),(1,1) make it transitive. Isn't this one example enough to show its transitive???

You've misunderstood an important part of the definition. A relation is transitive if for every a, b, and c with (a,b) and (b,c) in the relation, (a,c) is also in the relation.

This is not the same as "There exist a, b, and c such that (a,b), (b,c), and (a,c) are in the relation."

You need to be more precise in your use of mathematical English and particularly in the use of quantifiers like "there exists" and "for all".

$\endgroup$
1
$\begingroup$

Just think of the ordered pair $(a,b)$ as saying $a \sim b$. Because we have $(a,a)$ in the set for $a \in \{1,2,3\}$, we know that the relation is reflexive, after all, $(a,a)$ means $a \sim a$.

We know that the relation is symmetric, because for every element $(a,b)$ in the set, we have $(b,a)$ also in the set. That is, we have both $a \sim b$ (from $(a,b)$) and $b \sim a$ (from $(b,a)$).

We not transitive? Well, notice the set has $(1,2)$ so that $1 \sim 2$ and we have $(2,3)$ so that $2 \sim 3$. By transitivity, we should have $(1,3)$ in the set so that $1 \sim 3$, but notice it is not in the set! Therefore, the given $\sim$ is not transitive, and therefore not an equivalence relation.

Remember, it is not enough that you find an example of something transitive in the set, it has to be true for all of them! Meaning, every time you have $a \sim b$ and $b \sim c$ for some $a,b,c$, you then must have $a \sim c$ by transitivity. The example of $1 \sim 2$ and $2 \sim 3$ but $1 \not\sim 3$ is enough to show that the relation is not transitive.

So to show something is transitive, you need to show it for all of the possible applicable pairs. But to show something is not transitive, you only need to find a single example where it fails.

There may be an easier example. We will draw a 'graph' using the set $\{1,2,3\}$. We will say $a \sim b$ if either $a=b$ or if there is an edge connecting $a$ and $b$. Then draw the graph $$ 1 - 2 - 3 $$ Notice $1 \sim 1$, $2 \sim 2$, and $3 \sim 3$. We also have $1 \sim 2$ and $2 \sim 1$ because there is a 'segment' connecting them. Similarly, we have $2 \sim 3$ and $3 \sim 2$. But despite $1 \sim 2$ and $2 \sim 3$, we do not have $1 \sim 3$ because there is no direct 'segment' connecting $1$ and $3$. [There is a path through 2, but we dont want paths, we want direct paths.]

Edit. Note instead of the odd $a \sim b$ if $a=b$ or.... criterion, you could just draw a loop at each of the numbers $1,2,3$ connecting them with themselves....but TeXing that would be an irritation, so I opted for the former.

$\endgroup$
0
0
$\begingroup$

To be reflexive you need $(1,1),(2,2),(3,3)$ to be included. To be symetric we don't need to put anything in but if you put in $(a,b)$ you need $(b,a)$. The not be transitive we need a $(a,b), (b,c)$ but not $(a,c)$.

So put in $(1,2)$ and $(2,3)$ but not $(1,3)$. As we put in $(1,2)$ we need $(2,1)$ and as we put in $(1,3)$ we need $(3,1)$>

So $\{(1,1),(2,2),(3,3), (1,2),(2,1), (2,3),(3,2)\}$ will do. (note: the requires $7$ of the $9$ pairs)

$\endgroup$
0
$\begingroup$

Isn't this one example enough to show its transitive???

No.

The statements describing the properties of Reflexivity, Symmetry, and Transitivity, are universally quantified.$${\text{Reflexivity:}~\forall x{\in}A~.x\operatorname R x\\\text{Symmetry:}~\forall x{\in}A~\forall y{\in}A~.(x\operatorname R y\to y\operatorname R x)\\\text{Transitivity:}~\forall x{\in}A~\forall y{\in}A~\forall z{\in}A~.(x\operatorname R y\wedge y\operatorname R z\to x\operatorname R z)}$$ As such, they are each held to be true exactly when the predicate is satisfied by every occurrence of the bound variables, and so they are each falsified by the existence of some counterexample.

$${\text{Non-Reflexive:}~\exists x{\in}A~.\neg x\operatorname R x\\\text{Non-Symmetry:}~\exists x{\in}A~\exists y{\in}A~.(x\operatorname R y\wedge\neg y\operatorname R x)\\\text{Non-Transitive:}~\exists x{\in}A~\exists y{\in}A~\exists z{\in}A~.(x\operatorname R y\wedge y\operatorname R z\wedge\neg x\operatorname R z)}$$

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