Tag Info

For questions concerning partial orders, equivalence relations, properties of relations (transitive, symmetric, etc), a composition of relations, or anything else concerning a relation on a set.

A relation $$R$$ on a set $$X \times Y$$ (sometimes also called a relation between $$X$$ and $$Y$$) is any subset of $$X\times Y$$. So a relation is any set of ordered pairs $$(x,y)$$ such that $$x\in X$$ and $$y \in Y$$. Often we write $$x\mathrel R y$$ instead of $$(x,y)\in R$$. Sometimes we say a relation is defined on a single set $$X$$, but this just means that we're letting the relation $$R$$ be a subset of $$X \times X$$.

Here are some examples of relations:

• For a very abstract example of a relation, take $$X = \{1,2,3\}$$ and $$Y = \{a,b,c,d\}$$, and let $$R = \{(1,b),(3,c),(3,d),(2,c),(2,d)\}$$. This $$R$$ is a relation on $$X \times Y$$. Fun fact, there are $$2^{12}$$ distinct relations you could put on $$X \times Y$$.

• A function $$f\colon X\to Y$$ can be defined as a relation on $$X \times Y$$. The pairs in $$X \times Y$$ that are members of the relation are the input-output pairs $$(x, f(x))$$.

• A partial order is a relation that mimics the notion of one element being greater/less than the other. An example of a partial order is the relation $$\leq$$ on $$\mathbf{Z} \times \mathbf{Z}$$ where for two integers $$n$$ and $$m$$ we say $$n \leq m$$ if $$n$$ is less than or equal to $$m$$.

• Given a set $$X$$, let $$\mathcal{P}(X)$$ denote the set of all subsets of $$X$$. We can define a partial order $$\subseteq$$ on $$\mathcal{P}(X)$$ by saying that for two susbsets $$A$$ and $$B$$ of $$X$$, $$A \subseteq B$$ if $$A$$ is a subset of $$B$$.

• An equivalence relation is a relation that mimics the notion of two things being "equal". For example, on the set $$\mathbf{Z}$$ of integers let's define the relation $$\equiv_{37}$$ on $$\mathbf{Z}\times \mathbf{Z}$$ by saying $$a\equiv_{37} b$$ if both $$a$$ and $$b$$ give the same remainder when divided by $$37$$. If $$a \equiv_{37} b$$ we say that $$a$$ and $$b$$ are congruent modulo $$37$$.

• Let $$T$$ be the set of all triangles in the plane. An example of an equivalence relation on $$T$$ is the relation of two triangles being congruent.