[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](https://codegolf.stackexchange.com/tags/decision-problem/info)
## 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]
# [05AB1E](https://github.com/Adriandmen/05AB1E), 3 bytes
```
δQQ
```
[Try it online!](https://tio.run/##yy9OTMpM/f//3JbAwP//o6MNdUDQIFYHK8tABwQNY2MB "05AB1E – 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]
# [Prolog (SWI)](http://www.swi-prolog.org), 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!](https://tio.run/##lVHNDoIwDL7zFLuYAHbEde7i2SfwNCQcNPEvgWDQxMfHDjsHJGo8fev303bbtW2q5iRvj0vX2TRfyfpQ7w9tbCFPsshKYo5Nu6sqZtbzzUradC0LC7ZMN0CYE8oif9UxE0DEljBxTnfIui6ax4UCgSA0iGUJonClcgfi0CEJ2uHSGUqRZGImVPRvkFAxj@xTrOuQ8zX@GjRq1A/iwKIPOCsI07t9TDPRCyN3aO8zfoJfUYUrmOFkvzKyjqzrsJl/iukOihEZ9Xs3QsO6Yd2wbgZ/MNo9fMA3FSfPrH/0Gn/aNK0@d5kOxIHlvKvu2RM "Prolog (SWI) – Try It Online")
Predicate that succeeds if the relation given is an equivalence relation. Call as `+(Domain, Relation)` or `Domain+Relation`.
[Answer]
# [Python](https://www.python.org) NumPy, 33 bytes
```
lambda M:(M^M.T@M<M.any(0)).all()
```
[Attempt This Online!](https://ato.pxeger.com/run?1=lVJBTsMwEJQ45hVLTzbaRrXTSKgiiAvH3HorRXKbRLWUxCFNkMJXuFRC8B6u8Brs1G5oEUicxt6ZnR1v8vxWdc1GlbuXLLp7bZtsfPlxnotilQiIZyS-j_35TXwV-6LsyIRSX-Q5oVb4ntWqgLItqg5kUam6AVHXosO2lA9tik9prbYoksTLVA25LFOQJagqLbXVzAOS4JqigggKUZH0UeRoRP62ymVDRhBdw4hSD1qUWrM3JWucINNF6W83okqjXLtplzHzQGhVP5MQU00o7oHiSqlc9-govmiIQHIh_TnS3qiqZdmQjAhq37X7PLtdMASOECBMlwgLc2XmoGvcoCYCg1MjWJqkzPtXj0Zm69zqmOWDoc_d-R8zjjz6Gb124pmLnhX2QtcR2EJPOOFg6uTO12ViQ-bw-zyXkVueWz4Y8ri3n45nFrnF4BBLY2j50PKh5cPDvofYw7J_IfjJNoPfHY4_y2njzxU78XGXZfe_0xc)
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]
## [Python 2](https://docs.python.org/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!](https://tio.run/##lVCxboMwEN35ipsqkLzYjhdUtnyBJyTiwdCiIKUERVQFJfl2enbPdaBZuvid33v3fL5hHo/nXixtcVhO9qN@s1Ayndt@TnVlTdWYV4@1edF44P2m8UDqltqiaLL2fAELXQ8luLKOZePLbPk6dqd34HnikgEKpIfPMc0S2BfXKb/OeVpNbDbOrn3e7DvvPmX6qRMYLl0/QpuWbJ8tFWcgGEgGO8OgclfuCuSEQxSkw50zmORfdkROvCAfJ13GvnAXz@NX7T4ebc7AQHlPMEsivLCKCs6QFobgcUj1@EoYSpAuSJdxivDZ7cucUBDK34kQFemKdEW6Wu82LvYvJzZLk0/71ovf9jxs8hs "Python 2 – 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](https://docs.python.org/2/), 55 bytes
```
lambda R:all(R[a]=={a}|R[b]for a in R for b in{a}|R[a])
```
[Try it online!](https://tio.run/##lZCxboMwEIZ3nuJGkLz4HC9I3vIEniK5HoxaFCRKUERVEOXZqe2eS6BZOv32ff9/Pl8/Dddbh2utXtbWvVevDnTp2jbXxlmlZrd8aVPZ@nYHB00HGsKx8scf5Gyxfl6b9g14mcGFaQDlYf8x5EUGZzWP5TzFzBTiF2hqMCObbGy2RDJGsmTQ35tugDo/F6vhDJCBYHCyDEy48nDwNQzqgQh6Cgab/cvulVMdyceJiy2X7vi8/S4e23tbMDCQ0ZPMggoR7FolZ@qWhuDbkPLxlTQUEkfiYpsiffb4MidFUvE7kVdJXBKXxOV@t9ti/9bwsDTxNLdf/DHzsMlv "Python 2 – 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](https://docs.python.org/2/), 54 bytes
```
lambda R:R=={a:{b for b in R if R[a]==R[b]}for a in R}
```
[Try it online!](https://tio.run/##lZCxjsMgEER7f8WUiUQDhMYSXb6AKhLnAitnxVLOsSJHZ8vytzvALefYl@aqgX2zw7Lt0F1ujZgr/TFf3Vd5djC50Xp0@Viiut1Rom5gUFcw1hVaG1sWUwAugmn@vtTXT/A8w4kZQPty@@h2@wxHPfb5OMSYIbhPIcb2bCh@eiPpI5kytPe66VDtjvvZcgbBIBkOBYMNVx4OviaCeiCDHoKhyP5l98qpLsjHiculL93F@/hVe4z3tmBgUNGTzJIKEayikjOlpSH4MqR6fSUNJYgL4nKZIn12@zInFaTydyKvirgiroir9W6Xxf6tic3S5Nu@9eK3PS@bfAI "Python 2 – Try It Online")
Based on [Command Master's solution](https://codegolf.stackexchange.com/a/251632/20260). I/O as above.
---
## [Python 2](https://docs.python.org/2/), 39 bytes
```
lambda M:M==[map(a.__eq__,M)for a in M]
```
[Try it online!](https://tio.run/##lVDNCsIwDL7vKXLcoAhN7UXYI/TiaVDL6NDhQOeUifj0Mx2pc9OLp6/J95M03bM/Xloc6nw3nPy52nswG5Pn9uy71K/K8nAtS2Gy@nIDD00Lxg2PY3M6gNwkUIgtQE7t7t6nWQKGCmutF5UL2i0EWxWehYN3ROES6G5N20OdmmywUgAKUALWTpCdShke1MOARKiA6yBwyV9yQsl9ZJ1kXk2@WOPv@Jl9jCdZEAjQoyaKFTdGYhYVlTEtLiGnJfXnlLgUMo/Mq2mL@NnlZMmIjOq9EaFmXjOvmdfz206H/e7h4mjqp29@@KXn45Iv "Python 2 – Try It Online")
A more direct port of [Command Master's solution](https://codegolf.stackexchange.com/a/251632/20260), 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!](https://tio.run/##lVA9j8IwDN37K94IUpY4ZEHKT8jCVKmXodVRUYkrFSpC/Pqe03MILSw3PdvvI46Hx3i69DS17ms61z/Ndw2/985VVe1cg/ZyRYOuhw@xrP/K6X7qzkfofYFSHQDH4@E2brYFPDcVm1UTovaQE8qAZ0QZCgzXrh/Rbvx2qrQCKRiFXVBs51bHgmcUkQkTcRcFofiXnFHLnESnhTfZl3r6HL@wz/EsiwIFO2uS2MhgJhZRSZnS0hI6L2lfX0lLkfAkvMlbpM@uX9aCJGieGzFa4a3wVni7vG0@7PuMVkczH33Lw689L5f8BQ "Python 2 – Try It Online")
[Answer]
# [Factor](https://factorcode.org/), 32 bytes
```
[ 3 dupn [ = ] cartesian-map = ]
```
[Try it online!](https://tio.run/##fcgxDsIwDEbhPaf4LwALG4gZdWGpmCoGKzgoauoGxx1K1bMH6AHQWz69QN5Grbe2uV6OeLKwUopvsjhKQc8qnFD4NbF4LsjKZnPWKIaTcwsW2FbA@sdhy75eXe1wwGPKgg5n3OFJjUsk2Q2Uf6d6Sgn7@gE "Factor – Try It Online")
Port of @CommandMaster's [05AB1E answer](https://codegolf.stackexchange.com/a/251632/97916) (and so takes an adjacency matrix as input).
[Answer]
# [Charcoal](https://github.com/somebody1234/Charcoal), 9 bytes
```
⁼θＥθＥθ⁼ιλ
```
[Try it online!](https://tio.run/##S85ILErOT8z5/z@gKDOvRMO1sDQxp1ijUEfBN7EAiYKKZ@oo5GiCgPX//9HR0YY6BjpwHKsTDWEZQESAfEx5qBwIYpXHpz829r9uWQ4A "Charcoal – 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!](https://tio.run/##S85ILErOT8z5/788IzMnVUHDM6@gtCS4pCgzL11DU1MhoLQ4Q6NURyFT05orAChYouFaWJqYUwwS800sAFEQxVAOVDZTRyFHEwSs//83NDQwMDA05ILRQAIIDbhAPAMwDeGjq/uvW5YDAA "Charcoal – Try It Online") Link is to verbose version of code.
[Answer]
# [Jelly](https://github.com/DennisMitchell/jelly), 3 bytes
```
⁼þ⁼
```
[Try it online!](https://tio.run/##y0rNyan8//9R457D@4DE/8Ptj5rW/P8fHR1tqKNgAEGxOgrRQNoQhQcVQPBAArEgLkinIUIWHw9dJ6otGC7AZqcBsk5DJIVIqlCUIBQawkxEEkCIoboWXcAQbixGsBjgsNkAq@NQwgwpqJFdGBsbCwA "Jelly – Try It Online")
another port of Command Master's 05AB1E answer, so takes an adjacency matrix as input
[Answer]
# [APL (Dyalog Classic)](https://www.dyalog.com/), 6 bytes
```
⊢≡∧.=⍨
```
[Try it online!](https://tio.run/##SyzI0U2pTMzJT9dNzkksLs5M/v//UdeiR50LH3Us17N91Lvif9qjtgmPevsedTUbPmqb/KhvanCQM5AM8fAM5uICMoDSCmkKJkD4qHeLgqGCARRiZWHTYAhWgE7j1AAzD6EIhY3QYAyEMA0oWhBKTIEQoQTVCXjZ2GxBg9gdguxeQ0wlCJdCrUQoMQJChCmG/wE "APL (Dyalog Classic) – Try It Online")
Similar to [Command Master's submission](https://codegolf.stackexchange.com/a/251632/6972), but compares each column to each row, instead of pairs of rows.
[Answer]
# [Vyxal](https://github.com/Vyxal/Vyxal) `2`, 6 bytes
```
v‡$v⁼⁼
```
[Try it Online!](https://vyxal.pythonanywhere.com/#WyIyQSIsIiIsInbigKEkduKBvOKBvCIsIiIsIltbMSwgMCwgMCwgMF0sIFswLCAxLCAwLCAwXSwgWzAsIDAsIDEsIDBdLCBbMCwgMCwgMCwgMV1dXG5bWzEsIDEsIDEsIDBdLCBbMSwgMSwgMSwgMF0sIFsxLCAxLCAxLCAwXSwgWzAsIDAsIDAsIDFdXVxuW1swLCAxLCAwLCAwXSwgWzEsIDAsIDAsIDBdLCBbMCwgMCwgMSwgMF0sIFswLCAwLCAwLCAwXV1cbltbMCwgMSwgMV0sIFswLCAwLCAxXSwgWzAsIDAsIDBdXVxuW1swLCAxLCAxLCAxLCAxXSwgWzEsIDAsIDEsIDEsIDFdLCBbMSwgMSwgMCwgMSwgMV0sIFsxLCAxLCAxLCAwLCAxXSwgWzEsIDEsIDEsIDEsIDBdXVxuW1sxLCAwLCAwXSwgWzAsIDAsIDBdLCBbMCwgMCwgMF1dXG5bWzAsIDEsIDBdLCBbMCwgMCwgMV0sIFswLCAwLCAxXV1cbltbMSwgMSwgMF0sIFswLCAxLCAxXSwgWzEsIDAsIDFdXSJd)
Input as adjacency matrix. Yet another port of Command Master's answer (YAPOCMA).
Using a different flag:
# [Vyxal](https://github.com/Vyxal/Vyxal) `r`, 6 bytes
```
ƛ?v⁼;⁼
```
[Try it Online!](https://vyxal.pythonanywhere.com/#WyJyQSIsIiIsIsabP3bigbw74oG8IiwiIiwiW1sxLCAwLCAwLCAwXSwgWzAsIDEsIDAsIDBdLCBbMCwgMCwgMSwgMF0sIFswLCAwLCAwLCAxXV1cbltbMSwgMSwgMSwgMF0sIFsxLCAxLCAxLCAwXSwgWzEsIDEsIDEsIDBdLCBbMCwgMCwgMCwgMV1dXG5bWzAsIDEsIDAsIDBdLCBbMSwgMCwgMCwgMF0sIFswLCAwLCAxLCAwXSwgWzAsIDAsIDAsIDBdXVxuW1swLCAxLCAxXSwgWzAsIDAsIDFdLCBbMCwgMCwgMF1dXG5bWzAsIDEsIDEsIDEsIDFdLCBbMSwgMCwgMSwgMSwgMV0sIFsxLCAxLCAwLCAxLCAxXSwgWzEsIDEsIDEsIDAsIDFdLCBbMSwgMSwgMSwgMSwgMF1dXG5bWzEsIDAsIDBdLCBbMCwgMCwgMF0sIFswLCAwLCAwXV1cbltbMCwgMSwgMF0sIFswLCAwLCAxXSwgWzAsIDAsIDFdXVxuW1sxLCAxLCAwXSwgWzAsIDEsIDFdLCBbMSwgMCwgMV1dIl0=)
]