## Always More Terminology ðŸ“–

Now that we have relations, we can define some properties about them and see how our examples from the previous page compare. In all of our definitions, we will use $*$ to represent some generic placeholder symbol, with $R(*)\subseteq A\times A$ being our relation set.

### Reflexivity

Let’s start with a motivating example, consider standard equality $=$ and any item $x\in\mathbb{R}$. Is $x=x$? Yes, by definition any value is always equal to itself! However, for some other relations like $<$ we cannot have $x<x$. Relations where every item is always related to itself are called *reflexive*.

Definition: A relation $*$ isreflexiveif and only if for every $a\in A$, $a*a$. In other words, every item is related to itself.

Let’s go through our examples and determine if they are reflexive.

Example: Is $a\equiv a \mod n$?

## Answer

Yes, because the remainder of $a$ divided by $n$ will be the same on both sides of the equality

Example: Is $x\leq x$ for all $x\in\mathbb{R}$?

## Answer

Yes, because $x=x$ so $x\leq x$ by definition.

Example: Is $p$.isParent$(p)$ for every person?

## Answer

No, its not possible to be your own parent, so isParent is not reflexive.### Symmetry

When we think about standard equality, notice that the order in which we perform our relation doesn’t actually matter. If I tell you that $x=y$ is true, you automatically know that $y=x$ is also true. This property isn’t always the case for a general relation (try thinking of one that isn’t!), and we will call relations that are *symmetric*.

Definition: A relation $*$ issymmetricif and only if for every $a,b\in A$, $a*b\implies b*a$. In other words, the order in which you related items doesn’t affect the truth.

Let’s go through our examples and determine if they are symmetric.

Example: Let $a\equiv b\mod n$. Does this imply that $b\equiv a\mod n$?

## Answer

Yes, because the changing the order of $a,b$ does not change the remainders when divided by $n$

Example: Let $x\leq y$, does this mean $y\leq x$for all values$x,y$

## Answer

If $x=y$ you can switch their order, however if $x\neq y$ then you can't. For example $2\leq 3$ but $3\not\leq 2$. Therefore, $\leq$ is not symmetric

Example: If $p$.isParent$(q)$, does that mean that $q$.isParent$(p)$?

## Answer

No, your child cannot also be your parent in any case, this relation is not symmetric.### Transitivity

*Transitivity* is a property that people use (and misuse) in online arguments all the time. Normally we know that if $x=y$ and $y=z$ then we can clearly chain them together to say that $x=z$, but not every relation has this property.

Definition: A relation $*$ istransitiveif and only if for every $a,b,c\in A$, then $a*b$ and ,$b*c\implies a*c$. In other words, you can chain relations together.

Example: Let $a\equiv b\mod n$ and $b \equiv c \mod n$. Does this imply that $a\equiv c\mod n$?

## Answer

Yes, because all three remainders are equal to each other

Example: Let $x\leq y$ and $y\leq z$, does this mean $x\leq z$

## Answer

Yes, $x\leq y\leq z$ means $x\leq z$

Example: If $p$.isParent$(q)$ and $q$.isParent$(r)$, does that mean that $p$.isParent$(r)$?

## Answer

No, we only need one counter example and my grandfather is not one of my parents. That'd be fucked y'all### Anti-Symmetry

The term *anti-symmetry* might make you think *“Oh this probably means not symmetric”*, which certainly would make a lot of sense. Sadly you would be wrong because mathematicians are bad at naming things (I would call this *conditional symmetry* but fuck me I guess). Remember above in our symmetry section where we saw that sometimes we had $x\leq y$ **and** $y\leq x$, but only if $x=y$? Thats what anti-symmetry means, the only time you are allowed to switch the order is if $x=y$!

Definition: A relation $*$ isanti-symmetricif and only if for every $a,b\in A$, then $a*b$ and, $b*a\implies a=b$. In other words, the relation is only symmetric if $a=b$.

For the sake of not showing confusing examples, I am going to show two. isParent is a bit of a confusing edge case, but an interesting problem to think about.

Example: Let $x\leq y$ and $y\leq x$, does this mean $x=y$

## Answer

Yes, that is the only way we can have both conditions be satisfied, so $\leq$ is anti-symmetric.

Example: Let $a\equiv b\mod n$ and $b \equiv a \mod n$. Does this imply that $a=b$?

## Answer

No, consider $0,n$. Both of these have remainder $0$ divided by $n$, so $0\equiv n\mod n$ and $n\equiv 0\mod n$ but $n\neq 0$.### Connexity

Our final property is one that is very specifically relevant in certain situations. Notice that given two items, its very often the case that they are just not related at all. For example $2\neq 3$. But for some relations, its also totally possible that we can arrange any two items in a way such that we can always relate them.

Definition: A relation $*$ isconnexif and only if for every $a,b\in A$, then $a*b$ or, $b*a$ (or both). In other words, you can always relate two items.

Example: For all $x,y$ is $x\leq y$ or $y\leq x$

## Answer

Yes, if the two numbers are equal then the order doesn't matter. If they are not then one is smaller and you can put that one first.

Example: Given any $a,b$ is it guaranteed that $a\equiv b\mod n$ or $b\equiv a\mod n$?

## Answer

No, changing the order will not change the remainders, so if they are not related to begin, then the two items are not related, therefore this is not connex.## Classes of Relations

Now that we have these properties, we can define three types of relations.

Definition: If a relation is reflexive, symmetric, and transitive, then it is anequivilence relation.

This is a very important type of relation and we will discuss it later on the next page. These relations do all the things that we would like when setting things equal to each other, so they make things equivilent in a way. In our examples equality $\mod n$ was an equivelence relation

Definition: If a relation is reflexive, transitive, and anti-symmetric, then it is apartial order relation. If a partial order is also connex, then it is atotal order relation.

In our examples, we had that $\leq$ was a total order, which is cool because these sorts of relations define a way of ordering your set, so to speak.

## Practice Problems

Example: Let $R(*)\subseteq A\times B$ be a symmetric relation and $R(*)\neq\varnothing$. Prove $A=B$.

Example: We said above thatanti-symmetricdoes not meannot symmetric. Is it possible for a relation to be both symmetric and anti-symmetric?

Example: Is isParent anti-symmetric?