Is This an Equivalence Relation?

Question

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 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
[1, 2, 3], [[1, 1]] => 0
[1, 2, 3], [[1, 2], [2, 3], [3, 3]] => 0
[1, 2, 3], [[1, 1], [1, 2], [2, 2], [2, 3], [3, 1], [3, 3]] => 0
[1, 2], [[1, 2], [2, 2]] => 0

This is code golf, so aim to get your programs as short as possible.

Answer 1

05AB1E, 3 bytes

δQQ

Try it online!

Takes input as an adjacency matrix.

Explanation

δ      double vectorized - for each pair of rows in the adjacency matrix
Q      check if they are equal
Q      then check if the matrix produced by that is equal to the original matrix

If the input matrix is an equivalence relation, then it's easy to see that two values are equal iff their rows are equal, so the algorithm will return true.

Otherwise, since δQ returns an equivalence relation, it's impossible for it to be equal to the input.

Answer 2

Prolog (SWI), 95 bytes

X*Y:-member(X,Y).
X-Y:-forall(X,Y).
D+R:-X*D-[X,X]*R,[X,Y]*R-[Y,X]*R,([X,Y]*R,[Y,Z]*R)-[X,Z]*R.

Try it online!

Predicate that succeeds if the relation given is an equivalence relation. Call as +(Domain, Relation) or Domain+Relation.

Answer 3

Python NumPy, 33 bytes

lambda M:(M^M.T@M<M.any(0)).all()

Attempt This Online!

Expects adjacency matrix.

How?

First note that arithmetic is boolean, so 1+1=1.

The test can only be satisfied if

1. there is no empty column
2. M is symmetric (M=M^T)
3. M is idempotent (M^2=M)

together these imply

4. the diagonal of M is set

4 corresponds to "reflexive", 3 to "transitive" and 2 to "symmetric"

Answer 4

Python 2, 86 bytes

lambda X,R:any(R[a][c]<R[a][b]&R[b][c]|R[c][a]|(a==c)for a in X for b in X for c in X)

Try it online!

Takes the relation R as a two-level dictionary so we can write R[a][b] to query whether \$(a,b) \in R\$. Outputs True/False inverted.

---

Python 2, 55 bytes

lambda R:all(R[a]=={a}|R[b]for a in R for b in{a}|R[a])

Try it online!

Uses a more liberal input format of a dictionary taking each \$a \in X\$ to a set of all \$\{b:(a,b) \in R\}\$. We no longer need to take X as input because the keys of the dictionary will do.

---

Python 2, 54 bytes

lambda R:R=={a:{b for b in R if R[a]==R[b]}for a in R}

Try it online!

Based on Command Master's solution. I/O as above.

---

Python 2, 39 bytes

lambda M:M==[map(a.__eq__,M)for a in M]

Try it online!

A more direct port of Command Master's solution, with input as a adjacency matrix, that is, a list of lists of Booleans. Less golfed:

41 bytes

lambda M:M==[[a==b for b in M]for a in M]

Try it online!

Answer 5

Factor, 32 bytes

[ 3 dupn [ = ] cartesian-map = ]

Try it online!

Port of @CommandMaster's 05AB1E answer (and so takes an adjacency matrix as input).

Answer 6

Charcoal, 9 bytes

⁼θＥθＥθ⁼ιλ

Try it online! Link is to verbose version of code. Takes input as an adjacency matrix and outputs a Charcoal boolean, i.e. - for an equivalence relation, nothing if not. Explanation: Port of @CommandMaster's 05AB1E solution.

 θ          Input matrix
⁼           Is equal to
   θ        Input matrix
  Ｅ         Map over rows
     θ      Input matrix
    Ｅ       Map over rows
       ι    Outer row
      ⁼     Is equal to
        λ   Inner row
            Implicitly print

14 bytes to take input as an adjacency matrix of bit strings for convenience:

ＷＳ⊞υι⁼υＥυ⭆υ⁼ιλ

Try it online! Link is to verbose version of code.

Answer 7

Jelly, 3 bytes

⁼þ⁼

Try it online!

another port of Command Master's 05AB1E answer, so takes an adjacency matrix as input

Answer 8

APL (Dyalog Classic), 6 bytes

⊢≡∧.=⍨

Try it online!

Similar to Command Master's submission, but compares each column to each row, instead of pairs of rows.

Answer 9

Vyxal 2, 6 bytes

v‡$v⁼⁼

Try it Online!

Input as adjacency matrix. Yet another port of Command Master's answer (YAPOCMA).

Using a different flag:

Vyxal r, 6 bytes

ƛ?v⁼;⁼

Try it Online!