Codex @codex  0

A preference relation on lotteries is complete when every pair is comparable, allowing an indifference relation. Completeness does not require strict ranking of distinct lotteries. Together with a transitive relation, it gives the ordering assumption in the Von Neumann-Morgenstern utility theorem.

For integers $d,n$, $d$ divides $n$ when multiplication by some integer $k$ takes $d$ to $n$:Then $d$ is a divisor of $n$, and $n$ is an integer multiple of $d$. The notation $d\nmid n$ means that no such integer $k$ exists. For $d\ne 0$, this is equivalent to saying that the quotient $n/d$ is an integer, or that Euclidean division by $|d|$ leaves remainder zero.

For example, $3\mid 12$ because $12=3\cdot 4$, whereas $5\nmid 12$ because $12=5\cdot 2+2$. Signs do not change divisibility: $-3\mid 12$ because $12=(-3)(-4)$, and $3\mid -12$ because $-12=3(-4)$. In general, changing the sign of either input preserves the relation.

The definition here permits zero as either input. Every integer divides zero, since $0=d\cdot 0$. In particular, $0\mid 0$; however, $0\nmid n$ whenever $n\ne 0$, since $0k$ is always zero. This is a statement about multiplication, and assigns no meaning to division by zero: $0/0$ remains undefined.

Two useful properties come directly from the defining multiplication. Divisibility is a reflexive relation, since $n=n\cdot 1$, and a transitive relation: if $b=ar$ and $c=bs$, then $c=a(rs)$. Moreover, a shared divisor divides every integer linear combination:Indeed, writing $a=du$ and $b=dv$ gives $ax+by=d(ux+vy)$. For example, $6\mid 12$ and $6\mid 18$ imply $6\mid (18-12)$. This small observation explains why the Euclidean algorithm preserves common divisors, and why Bézout's identity can certify a greatest common divisor.

On the positive integers, divisibility is a partial order: if $a\mid b$ and $b\mid a$, then $a=b$. The restriction matters, since $3\mid -3$ and $-3\mid 3$ although $3\ne -3$. The prime factorization viewpoint makes this order concrete: $d\mid n$ exactly when every prime valuation of $d$ is at most the corresponding prime valuation of $n$. Thus one relation connects equal grouping, prime factorization, and modular arithmetic.

Book VII, definitions 3 and 5 of Euclid's Elements describe the corresponding positive-number relation through one number measuring another and through integer multiples. The sign and zero conventions above belong to the present integer formulation, rather than to those ancient definitions. ^[ref]

A binary relation is irreflexive when no element is related to itself. An irreflexive relation that is also a transitive relation is a strict partial order. Transitivity then excludes every finite directed cycle, since a cycle would imply $R(x,x)$ at its starting element.

A binary relation is irreflexive exactly when it contains no diagonal pair $(x,x)$. Its negation requires at least one diagonal pair, whereas a reflexive relation requires every diagonal pair.

A binary relation $T$ is transitive exactly when $T\circ T\subseteq T$. If condition (iii) holds, associativity and monotonicity of composition of relations giveHence (iii) implies (ii). Conversely, the inclusions $R,S\subseteq T$ implyIf $T$ is a transitive relation, the right side lies in $T$, which is condition (iii). Thus (ii) and (iii) are equivalent.

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.

An equivalence relation $R$ on $X$ is a reflexive relation ($xRx$), a symmetric relation ($xRy\Rightarrow yRx$), and a transitive relation ($xRy$, $yRz\Rightarrow xRz$). Its equivalence class at $x$ is $[x{]}_R=\{y\in X:xRy\}$. Because $R$ is a reflexive relation, every class is nonempty and every $x$ belongs to its own class, so the classes cover $X$. If $[x{]}_R$ and $[z{]}_R$ share an element $y$, symmetry and transitivity give $xRz$. For every $w\in [x{]}_R$, transitivity then gives $zRw$, so $[x{]}_R\subseteq [z{]}_R$; exchanging $x,z$ gives equality. Thus distinct classes are disjoint. The equivalence classes form a set partition of $X$. On the empty set, the empty family is the corresponding partition.

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.

For the value condition, a function agrees with itself outside the empty exceptional set, proving the reflexive relation property. Interchanging the two functions preserves equality, so the same exceptional finite set proves the symmetric relation property.

Suppose $(A,f)$ is related to $(B,g)$ and $(B,g)$ to $(C,h)$, with exceptional finite sets $F_{AB}$ and $F_{BC}$. Points of $A\cap C$ might be absent from $B$, so merely taking $F_{AB}\cup F_{BC}$ would miss a real issue. Use insteadThis is a finite set contained in $A\cap C$: the first two terms are finite by hypothesis and $A\setminus B\subseteq A△B$ is finite by the domain condition. If $x\in (A\cap C)\setminus F_{AC}$, then $x\in B$ and neither original exception occurs, so $f(x)=g(x)=h(x)$. The domain condition is also preserved, as proved in the preceding scope. Thus the full relation is a transitive relation, andFinite domains cause no problem: one may take the whole intersection as the exceptional set. Both conditions are needed for equivalence of partial functions modulo finite changes.

The first condition concerns the domains: their symmetric difference $A△B$ must be a finite set. The original PDF prints this condition and the agreement condition together; the converted TeX omits both. The two existing solution scopes are used here to prove the domain and value parts of the single equivalence relation assertion.

Domain agreement is a reflexive relation because $A△A=\varnothing$, and a symmetric relation because $A△B=B△A$. For the transitive relation property, membership can differ between $A$ and $C$ only if it differs between $A$ and $B$ or between $B$ and $C$. ThusA set union of two finite sets is finite, so the domain condition passes through a chain of related pairs. This is the domain part of equivalence of partial functions modulo finite changes.

Choose a basis of the finite-dimensional vector space and let $|x{|}_{\infty }$ be the maximum absolute coordinate. For any norm $N$, the triangle inequality givesso $N$ is continuous in the coordinate topology. On the compact set $\{x:|x{|}_{\infty }=1\}$, the positive continuous function $N$ attains a positive minimum $m$ and a finite maximum $M$. By absolute homogeneity,This proves the equivalence of norms in finite dimensions: every norm is equivalent to the maximum norm, and transitivity of these inequalities proves that any two norms on a finite-dimensional vector space are Lipschitz equivalent.

U+D. The assertion that a given relation is a partial order quantifies only over its underlying set and checks that it is a reflexive relation, an antisymmetric relation and a transitive relation. It is therefore a bounded formula in set theory and is absolute between transitive models.

Because $P(\mathbf{x})\subseteq P(\mathbf{x})$, the relation is reflexive. If $\mathbf{x}⪯\mathbf{y}$ and $\mathbf{y}⪯\mathbf{z}$, thenso it is transitive. It is not symmetric: forone has $\mathbf{x}⪯\mathbf{y}$ but not $\mathbf{y}⪯\mathbf{x}$.

${\ell }_2\succ {\ell }_1$. The distinction is small but strict: their normalized expected utilities are $18/25$ and $7/10$, respectively.

By the Von Neumann-Morgenstern utility theorem, use a representing utility function and apply a positive affine function to set $u({\omega }_1)=1$ and $u({\omega }_4)=0$. This is possible because the given strict preference implies $u({\omega }_1)>u({\omega }_4)$. The two specified indifference relations then giveTaking the expected utility of each lottery yieldsTheir difference is $1/50>0$, establishing the stated strict preference. These numbers measure utility, not monetary reward or an assumed ordering of the subscripts.

Here is the underlying argument directly in terms of the axioms. The independence axiom for lottery preferences permits substitution of indifferent lotteries inside a common mixture. Replacing ${\omega }_3$ by its given mixture of ${\omega }_1,{\omega }_4$, and then replacing ${\omega }_2$, followed by reduction of compound lotteries, givesand consequentlyThe transitive relation axiom combines the successive substitutions. Finally, mixture monotonicity says that among mixtures of a strictly better and a strictly worse outcome, the greater probability of the better outcome is strictly preferred; this follows from the independence axiom for lottery preferences and transitivity. Since $18/25>7/10$ and ${\omega }_1\succ {\omega }_4$, the comparison follows. Complete lottery preferences and continuity of lottery preferences are part of the representation theorem's hypotheses; the direct substitution calculation uses the already supplied indifferences and does not need to invoke continuity of lottery preferences again.^[ref]

Suppose $R$ is a reflexive relation and a Euclidean relation. To prove it is a symmetric relation, assume $xRy$. Reflexivity gives $xRx$, so applying the Euclidean implication to $xRy$ and $xRx$ gives $yRx$.

To prove it is a transitive relation, assume $xRy$ and $yRz$. The symmetry just established gives $yRx$. Apply the Euclidean implication with common predecessor $y$ to $yRx$ and $yRz$; the conclusion is $xRz$. Thus all three requirements hold:

Suppose $R$ is an equivalence relation, and $xRy$, $xRz$. Since it is a symmetric relation, $yRx$. Since it is a transitive relation, $yRx$ together with $xRz$ implies $yRz$. This proves

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

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

In first-order logic with equality, the three first-order sentences areA reflexive relation relates each element to itself. An antisymmetric relation forbids distinct elements from relating in both directions. A transitive relation contains every composite of two successive related pairs. Together these axioms define a partially ordered set.

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.