Is This an Equivalence Relation?

code-golf decision-problem

Given a relation, and a domain, output whether the relation is an equivalence relation.

Context

For this challenge, a relation is defined as being a set of ordered pairs that is a subset of the cartesian product of a domain with itself. That is, \$R \subset X \times X\$.

For a relation \$R\$ to be an equivalence relation on domain \$X\$, it needs to be: a) reflexive, b) symmetric and c) transitive.

If a relation is reflexive, for all items in the relation's domain, the item paired with itself is in the relation. That is:

$$ \forall a \in X : (a, a) \in R $$

or as one might write in Python:

all([(a, a) in R for a in X])

If a relation is symmetric, for all pairs of items in the relation, the reverse of the pair is also in the relation. That is:

$$ \forall a, b \in X : (a, b) \in R \implies (b, a) \in R $$

or as one might write in Python:

all([(y, x) in R for x in X for y in X if (x, y) in R])

If a relation is transitive, for all items a, b and c in the relation's domain, (a, b) being in the relation and (b, c) being in the relation means that (a, c) is in the relation. That is:

$$ \forall a, b, c \in X : (a, b) \in R \land (b, c) \in R \implies (a, c) \in R $$

or as one might write in Python:

all([(x, z) in R for x in X for y in X for z in X if (x, y) in R and (y, z) in R])

Worked Example

Let the domain of the relation be \${1, 2, 3, 4}\$ and the relation be \${(1, 1), (2, 2), (3, 3), (4, 4), (1, 2), (2, 1), (1, 3), (3, 1), (2, 3), (3, 2)}\$

The relation is reflexive, as \$(1, 1)\$, \$(2, 2)\$, \$(3, 3)\$ and \$(4, 4)\$ are all in the relation.

The relation is symmetric, as \$(1, 2)\$ and \$(2, 1)\$ are in the relation, as are \$(1, 3)\$ and \$(3, 1)\$. As are \$(2, 3)\$ and \$(3, 2)\$.

The relation is transitive, as \$(1, 2)\$, \$(2, 3)\$, and \$(1, 3)\$ are in the relation.

Therefore, the relation is an equivalence relation.

Rules

• The domain can be taken as a list of arbitrary objects (e.g. numbers, strings, a mix of numbers and strings) or any similar format. You do not need to take the domain if you take the relation as an adjacency matrix
• The relation can be taken as a list of ordered pairs/tuples, as an adjacency matrix or any other reasonable format. It can not be taken as a function object though.
• The domain will not be empty. That is, it will not be \$\emptyset\$ / {}
• The relation will not be empty. That is, it will not be \$\emptyset\$ / {}.
• Default [tag:decision-problem] output rules apply

Tests

Assuming the domain is given as a list of integers and that the relation is given as a list of lists

Domain, Relation => Equivalence?
[1, 2, 3, 4], [[1, 1], [2, 2], [3, 3], [4, 4]] => 1
[1, 2, 3, 4], [[1, 1], [2, 2], [3, 3], [4, 4], [1, 2], [2, 1], [1, 3], [3, 1], [2, 3], [3, 2]] => 1
[1, 2, 3, 4], [[1, 2], [2, 1], [3, 3]] => 0
[3, 4, 5], [[3, 4], [3, 5], [4, 5]] => 0
[1, 2, 3, 4, 5], [[1, 2], [1, 3], [1, 4], [1, 5], [2, 1], [2, 3], [2, 4], [2, 5], [3, 1], [3, 2], [3, 4], [3, 5], [4, 1], [4, 2], [4, 3], [4, 5], [5, 1], [5, 2], [5, 3], [5, 4]] => 0

Meta

• Are the plain english descriptions for reflexiveness, symmetry and transivity clear enough?
• Are the test cases good?

Is This an Equivalence Relation?

• The domain can be taken as a list of arbitrary objects (e.g. numbers, strings, a mix of numbers and strings) or any similar format.
• The relation can be taken as a list of ordered pairs/tuples, as an adjacency matrix or any other reasonable format. It can not be taken as a function object though.
• The domain will not be empty. That is, it will not be \$\emptyset\$ / {}
• The relation will not be empty. That is, it will not be \$\emptyset\$ / {}.
• Default [tag:decision-problem] output rules apply

• The domain can be taken as a list of arbitrary objects (e.g. numbers, strings, a mix of numbers and strings) or any similar format. You do not need to take the domain if you take the relation as an adjacency matrix
• The relation can be taken as a list of ordered pairs/tuples, as an adjacency matrix or any other reasonable format. It can not be taken as a function object though.
• The domain will not be empty. That is, it will not be \$\emptyset\$ / {}
• The relation will not be empty. That is, it will not be \$\emptyset\$ / {}.
• Default [tag:decision-problem] output rules apply

• The domain can be taken as a list of arbitrary objects (e.g. numbers, strings, a mix of numbers and strings) or any similar format.
• The relation can be taken as a list of ordered pairs/tuples, as an adjanancy matrix or any other reasonable format. It can not be taken as a function object though.
• The domain will not be empty. That is, it will not be \$\emptyset\$ / {}
• The relation will not be empty. That is, it will not be \$\emptyset\$ / {}.
• Default [tag:decision-problem] output rules apply

• The domain can be taken as a list of arbitrary objects (e.g. numbers, strings, a mix of numbers and strings) or any similar format.
• The relation can be taken as a list of ordered pairs/tuples, as an adjacency matrix or any other reasonable format. It can not be taken as a function object though.
• The domain will not be empty. That is, it will not be \$\emptyset\$ / {}
• The relation will not be empty. That is, it will not be \$\emptyset\$ / {}.
• Default [tag:decision-problem] output rules apply