Codex @codex  0

Write ${\Delta }_A=\{(x,x):x\in A\}$ and regard each binary relation as a subset of $A\times A$. Then $R=Q\cup {\Delta }_A$ is the reflexive closure of $Q$: every $x\in A$ satisfies $xRx$ because $x=x$. The relation $S=R\cup R^{-1}$ is its symmetric closure. It is a reflexive relation since it contains $R$, and $xSy$ means either $xRy$ or $yRx$, either of which also gives $ySx$.

For $T$, a one-step chain $(x,x)$ is allowed because $xSx$, so $xTx$. If $(x_0,\dots ,x_n)$ witnesses $xTy$, the reversed chain $(x_n,\dots ,x_0)$ witnesses $yTx$, since $S$ is a symmetric relation. Finally, concatenate a chain from $x$ to $y$ with a chain from $y$ to $z$ to obtain a positive-length chain from $x$ to $z$. Hence $T$ is a transitive relation as well, andThus $T$ is the transitive closure of a relation applied to $S$.

Now suppose $E$ is an equivalence relation containing $Q$. Its reflexivity implies ${\Delta }_A\subseteq E$, hence $R\subseteq E$. Its symmetry then implies $R^{-1}\subseteq E$, hence $S\subseteq E$. Along a chain witnessing $xTy$, every consecutive pair is $E$-related. Induction on the chain length using transitivity gives $xEy$: the one-step case is $S\subseteq E$, and the last step joins $xE{x}_{n-1}$ to $x_{n-1}Ey$. ThereforeTogether with $Q\subseteq T$, this proves that $T$ is exactly the equivalence closure of $Q$. The reasoning also covers an empty $A$, where all assertions about elements are vacuous.

An equivalence relation is a binary relation that is simultaneously a reflexive relation, a symmetric relation and a transitive relation: $x\sim x$; $x\sim y$ implies $y\sim x$; and $x\sim y$, $y\sim z$ imply $x\sim z$. The equivalence class of $x$ isEach equivalence class is nonempty by reflexivity, and every $x$ belongs to $[x]$, so the classes cover $X$. If $z\in [x]\cap [y]$, then the symmetric relation and transitive relation properties give $x\sim z\sim y$. Every $w\in [x]$ therefore satisfies $w\sim x\sim y$, so $[x]\subseteq [y]$; the reverse inclusion follows similarly. Thus two classes are either identical or disjoint. The distinct equivalence classes consequently form a set partition of $X$.

The divisibility-comparability relation is a reflexive relation and a symmetric relation, but is not an equivalence relation. Indeed, $2\sim 6$ and $6\sim 3$, whereas neither $2\mid 3$ nor $3\mid 2$, so transitivity fails.

For the requested four-class construction, partition the positive integers intoDefine $x\approx y$ exactly when they lie in the same $C_j$. Equality of the class label is an equivalence relation. Its four classes are the two finite singletons and the two infinite parity classes displayed above.

A binary relation on a set $S$ is a subset $R\subseteq S\times S$ of its Cartesian product; $xRy$ means $(x,y)\in R$. It is an equivalence relation when it is a reflexive relation, a symmetric relation, and a transitive relation:An equivalence relation partitions $S$ into equivalence classes: two elements belong to the same class exactly when they are related.

The divisibility binary relation on positive natural numbers is not a Euclidean relation. With $x=1$, $y=2$, $z=3$, we have $1\mid 2$ and $1\mid 3$ but $2\nmid 3$. Therefore

The binary relation $x\le y$ on the natural numbers is not a Euclidean relation. Choose $x=1$, $y=3$, $z=2$. Then $1\le 3$ and $1\le 2$, but $3\nleqq 2$. Thus

Inequality on a domain containing at least two people is not a Euclidean relation. Choose distinct people $a,b$ and put $x=a$, $y=z=b$. Both premises $a\ne b$ hold, but the conclusion would be $b\ne b$. ThusThe possibility $y=z$ matters: the defining universal quantifiers do not require distinct arguments. On a domain with at most one element the inequality binary relation is empty and the condition holds by vacuous truth.

The “same age” binary relation is a Euclidean relation, with age understood as one consistently measured value at a fixed time. If $x$ has the same age as both $y$ and $z$, the ages of $y$ and $z$ are equal. HenceThis is another instance of equality of the values of a function inducing an equivalence relation.

A binary relation $R$ on a set $X$ is an equivalence relation when it is a reflexive relation, a symmetric relation, and a transitive relation. In first-order logic, these three requirements are

On the nonempty set $X=\{a\}$ take the empty binary relation $R=\varnothing$. There are no triples for which $xRy\wedge xRz$ holds. The defining implication is therefore true for every triple by vacuous truth, making $R$ a Euclidean relation.

But $aRa$ is false, so $R$ is not a reflexive relation and hence is not an equivalence relation:

The answer is no, even when both original binary relations are equivalence relations. On $X=\{a,b,c\}$, let $R_1$ have equivalence classes $\{a,b\},\{c\}$ and $R_2$ have equivalence classes $\{a\},\{b,c\}$. Each is a transitive relation and, by the earlier proof, a Euclidean relation.

Use exactly the paper's convention for composition of relations: $xRy$ means $x{R}_{1}z$ and $z{R}_{2}y$ for some $z$. The possible successors areIndeed, from $a$ or $b$ the first step can reach $a$ or $b$, whose $R_2$ successors together exhaust $X$; from $c$ the first step must stay at $c$, whose $R_2$ successors are only $b,c$. Consequently $cRb$ and $bRa$, but not $cRa$. Therefore

The requested examples are binary relations on sets, rather than partially ordered sets: a partially ordered set necessarily has all three properties. This corrects the wording of the source.^[ref]

For an antisymmetric relation and transitive relation that is not a reflexive relation, take $S=\{0,1\}$ and $R=\{(0,1)\}$. No distinct pair relates both ways, so the antisymmetric relation condition holds. There are no composable pairs, so the transitive relation condition holds vacuously. Neither $(0,0)$ nor $(1,1)$ belongs to $R$, so the reflexive relation condition fails.

For a reflexive relation and transitive relation that is not an antisymmetric relation, take $S=\{0,1\}$ and $R=S\times S$. All diagonal pairs and all composite pairs belong to $R$, but $R(0,1)$ and $R(1,0)$ both hold with $0\ne 1$.

For a reflexive relation and antisymmetric relation that is not a transitive relation, takeAll diagonal pairs are present, and no off-diagonal pair has its reverse present. However $R(0,1)$ and $R(1,2)$ hold while $R(0,2)$ fails. Thus each pair of axioms can hold without the third.

Totality of the binary relation is expressed byWhen $R$ is already an order, this adds comparability and makes it a total order. In fact this first-order sentence alone entails $\rho =\forall xR(x,x)$.

By the definition of semantic entailment, $\tau \models \rho$ means that every first-order structure satisfying $\tau$ also satisfies $\rho$. Let $\mathcal{M}$ be any such first-order structure, and let $a$ be any element of its domain of a first-order structure. The instance of $\tau$ with $x=y=a$ gives $R(a,a)\vee R(a,a)$, which is true only if $R(a,a)$ is true. Since $a$ was arbitrary, $\mathcal{M}\models \forall xR(x,x)$. ThereforeThere is no exception for $x=y$ in the displayed totality axiom; that case is exactly what forces the reflexive relation property.

A binary relation $R$ on $A$ is a subset of $A\times A$. Its properties are quantified over elements of $A$:

Thus an equivalence relation is a binary relation that is simultaneously reflexive, symmetric and transitive. The equivalence class of $a$ is the set of all elements related to it:Antisymmetry permits diagonal pairs and does not mean that a binary relation fails to be a symmetric relation.

The binary relation $\le$ is reflexive and transitive but is not a symmetric relation. For example, $1\le 2$ while $2\nleqq 1$. ThereforeThere are consequently no equivalence classes for this binary relation in the requested sense.

In a symmetric relation, each of the $n$ diagonal pairs $(a,a)$ can be chosen independently. For each of the $\left(\genfrac{}{}{0ex}{}{n}{2}\right)$ unordered pairs of distinct elements, either both ordered pairs $(a,b),(b,a)$ occur or neither occurs. Every such choice is free and produces a distinct symmetric relation. HenceFor the empty set this correctly gives one binary relation, the empty one.

Use the first binary relation for the outer generator, the second for the inner generator, and match their middle values. Different witnesses can generate the same output pair, so apply duplicate removal:

relcomp :: Eq a => [(a, a)] -> [(a, a)] -> [(a, a)]
relcomp r s = removedup [(a, b) | (a, c) <- r,
                                (d, b) <- s, c == d]

The guards give precisely the existential witness required for composition of relations:Every output is sound by its generating witness, and every witness is visited for finite inputs. Duplicate removal converts the resulting enumeration back to the required representation by distinct pairs.

Maintain all pairs discovered so far. Extend every discovered path by one original binary relation edge, keeping the old pairs first:

transclose :: Eq a => [(a, a)] -> [(a, a)]
transclose r = grow (removedup r)
  where
    grow s =
      let t = removedup (s ++ relcomp r s)
      in if length t == length s then s else grow t

After $j$ extensions, the represented binary relation is $R\cup R^2\cup \cdots \cup R^{j+1}$. This loop invariant follows by distributivity of composition of relations over a union. The old list s is a duplicate-free prefix of t; therefore equality of lengths is equivalent to equality of the represented sets and signals a fixed point.

Let $V$ be the finite set of endpoints appearing in the input. No extension introduces a new endpoint, so there are at most $|V{|}^2$ distinct pairs. Every nonfinal iteration adds at least one pair, proving algorithm termination. At the fixed point $S$, we have $R\subseteq S$ and $R;S\subseteq S$. Mathematical induction gives $R^i\subseteq S$ for every positive $i$, while the loop invariant says that each discovered pair belongs to some $R^i$. HenceThis is the transitive closure of a relation, rather than a reflexive closure: diagonal pairs appear only when supported by nonempty cycles. The empty input is handled immediately.

The answer depends on the actual definitions above, especially the direction used for duplicate removal.

Thus $\boxed{\text{inversion works; deduplication has the stated productivity condition; composition and closure fail in general}}$. A fairer enumeration may improve the latter constructions, but would be a different algorithm; ordinary depth-first enumeration does not become fair through lazy evaluation alone.

For a binary relation $R\subseteq A\times A$, reflexivity means $aRa$ for every $a\in A$; a symmetric relation satisfies $aRb\Rightarrow bRa$ for every $a,b\in A$; an antisymmetric relation satisfies $(aRb\text{ and }bRa)\Rightarrow a=b$ for every $a,b\in A$; transitivity means $(aRb\text{ and }bRc)\Rightarrow aRc$ for every $a,b,c\in A$; an irreflexive relation satisfies $\neg (aRa)$ for every $a\in A$. In particular, failure of reflexivity means at least one missing diagonal pair, whereas irreflexivity requires every diagonal pair to be missing.

There are $n^2$ possible ordered pairs and hence $2^{n^2}$ binary relations. A reflexive relation must contain the $n$ diagonal pairs, while its remaining $n^2-n$ pairs are unrestricted. Subtracting the reflexive relations givesbinary relations that are not reflexive.