Relations

Properties

As a reminder, we take a relation $R$ and write it as $a R b$ or $R(a,b)$. A relation is defined as:

$$R \subseteq A \times A$$

and (the comma is the same as writing $\land$)

$$R = \{ (a,b) | a \in A, b \in A, a R b \}$$

Ergo, R is a set made up of tuples of two elements of the same set in a certain order, so that the relation operator makes a true statement.

We're now going to take a look at some properties (there can be many more, we're just looking at some important ones), and then do the check of whether the relations we know follow them or not.

We're going to talk about an abstract relation operator, defined with $\triangle$. The notation is going to be $a \triangle b$ or $\triangle(a,b)$ for saying $(a,b)\in\triangle(A)$ (there is a tuple in the relation subset from set A, assuming both a and b are from the set A).

Reflexive

$$\forall x \in A, x \triangle x$$

This means that taking any element $x \in A$, we know that the statement $x\triangle x$ is true (ergo $(x,x) \in \triangle(A)$). In the "people x knows" relation, (hopefully) no matter which person we take, they will know themselves.

Irreflexive

$$\forall x \in A, \lnot x\triangle x$$

That means that for all possible values of "x", the statement $x\triangle x$ is false (ergo $(x,x) \notin \triangle(A)$).

This is not the same as negating the reflexivity property outright. Why?

The answer here lies in logic again. When negating a "forall/$\forall$" operator, what we're saying is that something is not true for all the values.

$$\lnot (\forall x \in \mathbb{N}, x > 5)$$

That means that, if we were to "scroll" through every value of "x", not all of them satisfy the property. Irreflexivity instead says that "all of them do not satisfy" the property (which would still not apply here, as some do).

We'll cover logic transmutations more in depth with proofs in a later article.

Symmetric

$$\forall x,y \in A, x\triangle y \implies y\triangle x$$

Picking two elements "x" and "y", if they're in relation, then switching them around keeps them in the relation. This is important as we said tuples $(x,y)$ are ordered, so knowing that $(y,x)$ is also in the relation is not a given. These relations can be anything at all, from "sharing the same cousin", to "has eaten more bread in life than me". The important thing is that we make no assumption about $\triangle$ and how it is defined.

Also to note, the double implication $\iff$ here is not needed, because the reverse is already implied by the fact we're checking all possible values of both x and y.

Asymmetric

$$\forall x,y \in A, x \triangle y \implies \lnot (y \triangle x)$$

Take two numbers "x" and "y", if they're in relation in a certain order, they will not be in the opposite one. For example, if "x is taller than y", it will never make sense to state "y is taller than x", as this relationship goes only one way.

Antisymmetric

$$\forall x,y \in A, (x \triangle y \land y \triangle x) \implies (x = y)$$

What if we take the asymmetry, but rather than imply that the opposite tuple ($(x,y)$ and $(y,x)$) does not exist, we simply state that if they both exist, it is actually okay, but only because they're the same element. In the asymmetric example above, a "taller than" would never work for themselves, as you can't be taller than yourself. But if we slightly change the relation to be "at least as tall as", then any person "x" would be "at least as tall as" "x", while two distinct elements "y,z" (let's assume in our case that two different people will always have differing heights), then the relation could only be in one way, that is $y\triangle z$ or $z \triangle y$.

Transitive

$$\forall x,y,z \in A, (x \triangle y \land y \triangle z) \implies (x \triangle z)$$

Taking three different elements, $x,y,z$, this allows us to "skip" the middle element and connect $x$ and $z$ directly, skipping $y$. In the relationship "can travel to" with cities as elements, knowing that "(from) Rome (can travel to) Paris" and "(from) Paris (can travel to) London", we can then know that "(from) Rome (can travel to) London" (as we know Paris can be definitely a middle point, connecting the two, even if it doesn't have to be).

Connected

$$\forall x,y \in A, (x \neq y) \implies (x \triangle y \lor y \triangle x)$$

Taking two elements $x,y$, if they're not the same element, then they are in relation to each other, in one way or the other (could be both ways!). The name is borrowed due to graph theory, which we're not going to see much, but I am going to at least make an effort to give some basics.

Let's take a set $A = \{a,b,c,d\}$. We're going to build a relation in this set, with the following

$$\triangle(A) = \{(a,b),(a,c),(d,a),(b,c),(d,b),(c,d)\}$$

This is of course, totally invented, as I am simply taking random element names and deciding which tuples are in the relation.

We're now going to place these tuples on a plane (two dimensional one, basically a piece of paper) as points.

We're now going to display a tuple $(a,b)$ as an arrow going from $a$ to $b$.

We're going to do the same with the rest.

The "connected part" comes from the fact every element is now connected to every other, even if only in one direction.

Strongly Connected

$$\forall x,y \in A, (x \triangle y \lor y \triangle x)$$

This is the same as connected, except we're including the same element for both "x" and "y" (they can both refer to a 5, for example). In the above diagram, it would be the same to adding an arrow going from every element, to itself.

Relation Check!

We now do the same thing as we did for the operators, and try to take a swing at checking what properties hold for the relations we know.

We currently know three types of relations: equality, less than, "less than or equal".

---

Equality

Reflexivity

$$\forall x \in A, x = x$$

Every element is equal to itself. While this is trivial to understand (why wouldn't 5 be equal to 5 after all), it's important to be methodical in our observations. Of course, this property holds.

Irreflexive

$$\forall x \in A, \lnot x = x$$

We know that reflexivity holds, so the "anti-property" of course does not hold. There are indeed elements that are equal to themselves, and it's all of them.

Symmetric

$$\forall x,y \in A, x = y \implies y = x$$

In our equality relation, we only have tuples of the variety $(3,3)$ or $(5,5)$ or $(\frac{3}{4},\frac{3}{4})$. So swapping the two terms around does not do much difference. Therefore this holds.

Asymmetric

$$\forall x,y \in A, x = y \implies \lnot (y = x)$$

Since our relation is symmetric already, this does not hold.

Antisymmetric

$$\forall x,y \in A, (x = y \land y = x) \implies (x = y)$$

Technically correct, as we can logically reduce the above to "if x=y is true then x=y is true" which is a basic tautology (statement that is correct no matter our truth value of assumptions). So this holds.

Transitive

$$\forall x,y,z \in A, (x = y \land y = z) \implies (x = z)$$

Trivial again, as x,y,z can only really be the same exact value. It's useful at least for writing expressions as $x = y = z$. Of course, this holds.

Connected

$$\forall x,y \in A, (x \neq y) \implies (x = y \lor y = x)$$

Taking "x" and "y" as 3 and 5, we know these are not equal, and yet this tells us that $3=5$ or $5=3$. Of course this does not hold.

Strongly Connected

$$\forall x,y \in A, (x = y \lor y = x)$$

If it was not "connected", it definitely isn't strongly connected. As always, since it's a "for all" type statement, it can be broken by any example, so take your favourite pair of numbers, and determine that, "whoops they're not equal, guess this does not hold!".

---

Less than

Of course, while we're considering $<$, all of this can hold for $>$ as it's the same exact relation.

Reflexivity

$$\forall x \in A, x < x$$

Take $x=3$, $3<3$ does not hold. Therefore reflexivity does not hold.

Irreflexive

$$\forall x \in A, \lnot x < x$$

This holds, as we know that every element is not "less than" itself.

Symmetric

$$\forall x,y \in A, x < y \implies y < x$$

If this were to hold, the entire concept of a greater quantity would cease to exist. Safe to say, this does not hold.

Asymmetric

$$\forall x,y \in A, x < y \implies \lnot (y < x)$$

As we gave the same example with "taller than" relation (which was simply < in disguise), this actually holds. Our "less than" relation only holds one way.

Antisymmetric

$$\forall x,y \in A, (x < y \land y < x) \implies (x = y)$$

Of course, this does not hold, as if the elements were equal, I could simply write $x < x$ which I already know not to hold.

Transitive

$$\forall x,y,z \in A, (x < y \land y < z) \implies (x < z)$$

This holds, and writes out the inequality $x < y < z$. In terms of natural numbers, we can prove it by thinking in absolute amount of "xs" (unary notation), where if y has more, and z has more than y, then of course z is going to have an amount of "xs" bigger than "x".

Connected

$$\forall x,y \in A, (x \neq y) \implies (x < y \lor y < x)$$

This is interesting, because it depends on the set we're discussing. In our usual numbers we've seen, this of course holds. But if we were to consider our element a tuple like $(3,5)$, and pair it up to something like $(4,4)$, does the following hold?

$$(3,5) < (4,4)$$

It really depends on how we define the $<$ term. If you consider first element as priority, then it does. If you consider second element as priority, the inverse holds. But if you were to only consider the cases where either the first or second element have to match up (ergo $(3,5) < (3,6)$ or $(2,4) < (3,4)$), the two elements don't have an actual ordering. In a more abstract but also concrete example, if two people were to be holding (3 apples, 5 oranges) and (4 apples, 4 oranges), there cannot be a single way to define $<$.

So, for our purposes in normal numbers, this holds. But not always. I'll have a paragraph at the end with more explanation.

Strongly Connected

$$\forall x,y \in A, (x < y \lor y < x)$$

This does not hold, as taking $x=y$, gives us the usual $x < x$ that we know does not hold. So even if the relation is connected, it is not strongly connected.

---

Less than or equal

We can express the relation of "less than or equal" through the less than and equal relations separately.

$$\leq(A) = Eq(A) \cup <(A)$$

That is, we take the relations of equality and "less than" (which are just sets!), and simply make a bigger set with the union of the two.

$$\leq (A) = \{ (a,b) | a=b \lor a < b \}$$

So we both have the tuples in the usual "<" relation, but also adding all the $(a,a)$ tuples from equality.

Reflexivity

$$\forall x \in A, x \leq x$$

Thanks to the equality subset, this relation now holds.

Irreflexive

$$\forall x \in A, \lnot x \leq x$$

This now does not hold anymore. As an element can now be in relation with itself.

Symmetric

$$\forall x,y \in A, x \leq y \implies y \leq x$$

This still does not hold. While we can now pick elements that are the same for both "x" and "y" ($3 \leq 3$), if we pick differing elements, the reverse still does not hold.

Asymmetric

$$\forall x,y \in A, x \leq y \implies \lnot (y \leq x)$$

This now does not hold, as I can pick "x" and "y" to be equal, and therefore having both $x \leq y$ and $y \leq x$ being true.

Antisymmetric

$$\forall x,y \in A, (x \leq y \land y \leq x) \implies (x = y)$$

This now holds, as we said in the example for asymmetric, if we have the relation being true in both directions, it means it's describing the same element. This is kind of interesting, as we're determining a property of "x" and "y", without really giving them any concrete values.

Transitive

$$\forall x,y,z \in A, (x \leq y \land y \leq z) \implies (x \leq z)$$

This still holds, as our previous "proof" in the less than part, now simply changes the number of "xs" to also possibly being the same.

Connected

$$\forall x,y \in A, (x \neq y) \implies (x \leq y \lor y \leq x)$$

Same caveat as before, but this still holds. Our addition of the equality relation did not change the truth value of this statement, as it explicitly throws out any tuple of the form $(x,x)$.

Strongly Connected

$$\forall x,y \in A, (x \leq y \lor y \leq x)$$

This now holds, as if we take differing elements, they're in some kind of order between them, and if we take the same element twice (for both x and y), it will still be in relation with itself.

Relations - The Generalization step

Note: this is an extra step that won't be used for a bit, around modulo operators (where it might make more sense). I'm introducing it here, as it's a very common consequence of having spent all this time writing about relations, that we can generalize a little. If you want to skip and come back after, feel free to do so.

We've seen some equality in the sense of actual numbers, and inequality with concrete numbers. These relations are "structures" we define in mathematics, so that any set of "elements" that we explore, can be reasoned upon through these relations. Even if we don't know the actual elements, we can start to tell facts about how they're related to each other.

If there's an element "a" that is in relation with every other element for example, and we know there's another element "b" in relation with everyone else except "a", if that relation is "<", we've just found elements that are related to "0" and "1" in the Natural set.

So we're going to define combination of properties that give relations similar to Equality and "Less than".

Equivalence relation

An equivalence relation is a criteria that a relation has. It needs to have the following properties:

• Reflexivity

• Symmetry

• Transitivity

This allows elements that, even if not "the exact same" can fall into "equality classes/groups". Let's say, $A=\{1,2,3,4,5,6,7,8\}$, and we take our equality relation as "they're both even or both odd" with symbol $\sim$.

Then we would have

$$1 \sim 3 \sim 5 \sim 7$$

and

$$2 \sim 4 \sim 6 \sim 8$$

This allows us to think as a "macro element" $x=\{2,4,6,8\}$ and $y=\{1,3,5,7\}$. We can also think of the set A as being made up only of these two macro elements. So the set could be made up like $B=\{x,y\}$ and have our usual equality relation being $x=x$ and $y=y$ and $x\neq y$. This set B is called a "partition" of set A, as we're dividing A's elements in many subsets, but keeping every element.

If you need more examples of equivalence that aren't strictly "=" on numbers, a good example is having the same birthday, or being as tall as. Multiple people can share the same birthday, and you can make "groups" of people based on their birth date, dividing the population neatly, and making sure nobody gets in a group twice, or is left behind.

Partial order

Note: While the actual definition is a bit more complex, I am going to introduce it as it will be interesting for more advanced forms of math.

A partial order is a structure made from a set $A$ and a relation $R$, and can be strict or weak.

A relation for a strict partial order has the following properties:

• Irreflexivity (anti-reflexive)

• Asymmetry

• Transitivity

This represents a generalization of our $<$ symbol. Consider that there's no "connected" requirement, so we can have "isles" of elements that are all at the same level.

A relation for a weak partial order has the following properties:

• Reflexivity

• Antisymmetry

• Transitivity

As opposed to the one above, this is the generalization of our $\leq$ symbol. Our isles of "no order" can still apply, as there's still no connected requirement.

Conclusion

These are some concepts to basically stew on, as we're going to look at more and more structures of algebra. A finalization of the notation used is that, while I defined a relation as $R(a,b) \subseteq A \times A$, that is only true for "homogeneous relations". A more generalized concept of relations is to declare:

$$R(a,b) = \{ (a,b) | a \in A, b \in B, a R b \}$$

A little bit outside our scope, but this allows relations to be expanded to different kind of sets, allowing elements to be paired up together. (As a final example, think of possible equality relations that could happen by determining two sets are "alike")