set relations (relation that is symmetric and transitive but not reflexive)

Question

My discrete book says that the set $A = \{4,5,6\}$ and the relation $R = \{(4,4),(5,5),(4,5),(5,4)\}$ is symmetric and transitive but not reflexive.

I was wondering how this is possible, because if a set $A$ is symmetric, doesn't it also need to include $(5,6),(6,5),(4,6),(6,4)$?

Also if it's transitive, doesn't it have to include $(4,5),(5,6),(4,6)$? I thought the definition of a transitive relation was that $(x$ $R$ $y)$ $\land$ $(y$ $R$ $z)$ then $(x$ $R$ $z)$.

Answer 1

A set can't be symmetric; a relation can be. (By the way, it's possible for a set to be "transitive", but that doesn't mean the same thing as a transitive relation: a transitive set is a set $x$ such that if $z \in y$ and $y \in x$, then $z \in x$.)

A relation on a set need not involve every member of the set. For example, the relation on $\mathbb{N}$ given by "is a prime divisor of" doesn't touch $1$ at all: $1$ is not related to anything and nothing is related to it. In your example, $6$ is not related to anything by $R$, and nothing is related to $6$ by $R$.

"Symmetric" just means that if $a \sim b$, then $b \sim a$. Note that it doesn't tell us about any elements of $A$ we haven't seen before: from the mere knowledge that $4 \sim 5$, we can't use symmetry to deduce that anything is related to $6$. Similarly transitivity.

Answer 2

Def.: let be $A,R$ sets, we define $$ \operatorname{dom}(R):=\{x| \exists y : (x,y) \in R\} \\ \operatorname{cod}(R):=\{x| \exists y :(y,x)\in R\} \\ \operatorname{field}(R):=\operatorname{dom}(R)\cup \operatorname{cod}(R) \\ R \text{ is reflexive in }A \text{ if } \,\forall x \in A:(x,x)\in R \\ R \text{ is symmetric in }A \text{ if } \,\forall x,y \in A:(x,y)\in R \to (y,x)\in R \\ R \text{ is transitive in }A \text{ if } \,\forall x,y,z\in A:(x,y)\in R \wedge (y,z)\in R \to (x,z)\in R \\ R \text{ is reflexive} \text{ if } \,R \text{ is reflexive in}\operatorname{field}(R) \\ R \text{ is symmetric} \text{ if } \,R \text{ is symmetric in}\operatorname{field}(R)\\ R \text{ is transitive } \text{if } \,R \text{ is transitive in}\operatorname{field}(R) $$

Now, we have $A:=\{4,5,6\}$ and $R:=\{(4,4),(5,5),(4,5),(5,4)\}$, therefore:

• $R$ is not reflexive in $A$ because $(6,6) \notin R$
• $R$ is symmetric in $A$
• $R$ is transitive in $A$

([$R$ is symmetric in $A$ $\wedge$ $R$ is transitiv in $A$ $\to$ $R$ is reflexiv in $A$] is generally false, and you have an example)

But:

• $ \operatorname{dom}(R)= \operatorname{cod}(R)= \operatorname{field}(R)=\{4,5\}$
• $R$ is reflexiv (in $\operatorname{field}(R)$)
• $R$ is symmetric (in $\operatorname{field}(R)$)
• $R$ is transitiv (in $\operatorname{field}(R)$)

([$R$ is symmetric $\wedge$ $R$ is transitiv $\to$ $R$ is reflexiv] is true, but the converse generally is false, an example $R^´:=\{(1,1),(0,1),(0,0)\}$)

Why $R$ is symmetric and transitive in $A$? For example, let be $4,6 \in A$ and I prove that $(4,6) \in R \to (6,4) \in R$ and $(4,6) \in R \wedge (6,4) \in R \to (4,4)$ are true, but it is vacuously symmetric and transitive by def of "$\to$" (see ex.1, ex.2), similary with $(5,6)$, $(6,5)$...