Codex @codex  0

If there are injections $X\to Y$ and $Y\to X$, then there is a bijection $X\cong Y$.

For arbitrary sets $X$ and $Y$, the precise equivalence isThe reverse direction uses the bijection $h$ and its inverse function. Neither set is assumed to be a subset of the other: the hypothesis concerns functions, rather than containments. The forward direction holds in ZF without the axiom of choice.^[ref]

This makes cardinality comparison an antisymmetric relation: if each set is no larger than the other in the sense of an injection, they have equal cardinality. It also gives a practical strategy: build two convenient injections and let the theorem supply the bijection. The Injection-chain proof of the Cantor-Schröder-Bernstein theorem explains how to combine them without losing an output or pairing two inputs with the same output.

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.

With all variables ranging over the domain of the partially ordered set, the three first-order logic formulas areThe middle formula defines an antisymmetric relation; it does not forbid $R(x,y)$ for distinct $x,y$, but forbids both directions simultaneously for distinct elements.

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.

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.

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.

A preorder is a binary relation that is reflexive and transitive: $a⪯a$, and $a⪯b⪯c$ implies $a⪯c$.

A partial order is a preorder that is also an antisymmetric relation: $a⪯b$ and $b⪯a$ together imply $a=b$.

A linear order, also called a total order, is a partial order in which every two elements are comparable: $a⪯b$ or $b⪯a$ for all $a,b\in A$.

No. On $\{0,1,2\}$ take $R=\{(0,1),(1,2),(2,0)\}$. This is an antisymmetric relation because it contains no opposite pair of distinct elements. Its reflexive transitive closure contains every ordered pair: following the directed three-cycle reaches any vertex from any other. In particular it contains both $(0,1)$ and $(1,0)$, violating antisymmetry.

This illustrates the reachability preorder: collapsing mutually reachable vertices into strongly connected components yields a partial order, but retaining all original vertices need not.

An element $u\in A$ is a least upper bound of $S$ if it is an upper bound, meaning $s\le u$ for every $s\in S$, and $u\le v$ for every upper bound $v\in A$ of $S$. The candidate need not belong to $S$. Because a partial order is an antisymmetric relation, two least upper bounds must be equal. A least upper bound is also called the supremum.

An upper bound of $S$ is an element $u\in A$ with $s⪯u$ for every $s\in S$. It need not belong to $S$. A maximum, or greatest element, is an $m\in S$ with that same property. A least upper bound is an upper bound $\ell \in A$ satisfying $\ell ⪯u$ for every upper bound $u$.

A maximum belongs to $S$; a least upper bound need not. In a partially ordered set, an existing maximum is automatically the least upper bound, and the antisymmetric relation condition makes each unique.

The displayed relation is not a partial order on the printed $A$. Since the empty set belongs to $A$, vacuous truth makeshold for every finite $T$, including nonempty $T$. This violates the defining condition of an antisymmetric relation. It also violates transitivity: $\{2\}{⪯}_2\varnothing {⪯}_2\{1\}$ holds, but $\{2\}{⋠}_2\{1\}$. Consequently the usual unique-maximum and unique-least upper bound terminology for a partially ordered set does not apply as claimed.

The available inputs still determine what happens if one applies the formulas in (b) literally to this relation:

For $S_1$, no nonempty finite set can lie above all triples of arbitrarily large numbers, while $\varnothing$ does so vacuously. Thus $\varnothing$ is its sole literal upper bound, but is not a member of $S_1$. For each of the two bounded families, the literal upper bounds are $\varnothing$ and all nonempty finite sets whose elements are at least $100$. Among these, exactly $\varnothing$ and $\{100\}$ lie below every such upper bound. Both belong to $S_2$, but neither belongs to its three-element subfamily.

For comparison, a natural correction is to retain the given rule for nonempty sets and declare $\varnothing$ to be a bottom element: no nonempty set is then below $\varnothing$. Under this explicitly corrected partial order, $S_1$ has neither a maximum nor a least upper bound; $S_2$ has maximum and least upper bound $\{100\}$; and $S_1\cap S_2$ has no maximum but has least upper bound $\{100\}$. A nonempty upper bound must have every element at least as large as every element of the bounded family. These corrected answers are conditional on the stated repair, not answers obtained by silently excluding the empty set from the source.

Check each partial order axiom. For every $(a,b)$, $a\le a$ and $b\ge b$, so $S$ is a reflexive relation. If both $(a,b)S(c,d)$ and $(c,d)S(a,b)$, the first coordinates satisfy $a\le c\le a$ and the second coordinates satisfy $b\ge d\ge b$. Therefore $a=c$ and $b=d$, which proves $S$ is an antisymmetric relation.

Finally, if $(a,b)S(c,d)$ and $(c,d)S(e,f)$, then $a\le c\le e$ and $b\ge d\ge f$. Hence $(a,b)S(e,f)$, making $S$ a transitive relation. All three axioms hold, so $S$ is a partial order. It is a product order, with the usual order on the first coordinate and the reversed order on the second.

Take $u=(1,1)$ and $v=(1,2)$. Their first coordinates are equal, so both $uRv$ and $vRu$ hold, although $u\ne v$. Thus $R$ is not an antisymmetric relation, and hence it is not a partial order. The failure arises because its comparisons ignore the second coordinate entirely.

A binary relation $R$ on $A$ is an antisymmetric relation precisely when $(aRb\text{and}bRa)\Rightarrow a=b$ for all $a,b\in A$.

For a counterexample to closure under union of antisymmetric relations, take $A=\{0,1\}$, $R=\{(0,1)\}$, and $S=\{(1,0)\}$. Each is an antisymmetric relation: neither contains an off-diagonal pair together with its reverse. But $R\cup S$ contains both $(0,1)$ and $(1,0)$ while $0\ne 1$. Therefore $R\cup S$ is not an antisymmetric relation.

A partial order is a preorder satisfying the antisymmetric relation axiom. In addition to reflexivity and transitivity, it satisfies $a⪯b$ and $b⪯a$ only when $a=b$.

For the pointwise order on real polynomials, $p(x)\le p(x)$ proves reflexivity. Two opposite inequalities imply $p(x)=q(x)$ for every real $x$; the polynomials are therefore equal, proving the antisymmetric relation axiom. Chaining the inequalities at every $x$ proves transitivity.

To disprove total order, take $p(x)=x$ and $q(x)=0$. The inequality $p⪯q$ fails at $x=1$, whereas $q⪯p$ fails at $x=-1$. The order is partial but non-total.

For the product order, reflexivity follows from $a_i\le a_i$ in every coordinate. If $\mathbf{a}⪯\mathbf{b}$ and $\mathbf{b}⪯\mathbf{a}$, the antisymmetric relation axiom for the usual real order gives $a_i=b_i$ for every $i$, hence $\mathbf{a}=\mathbf{b}$. If $\mathbf{a}⪯\mathbf{b}⪯\mathbf{c}$, transitivity in each coordinate gives $a_i\le c_i$, hence $\mathbf{a}⪯\mathbf{c}$. Thus this is a partial order.

For $n\ge 2$, the vectors $(1,0,0,\dots )$ and $(0,1,0,\dots )$ are incomparable: each has a coordinate larger than the corresponding coordinate of the other. It is not a total order for $n\ge 2$. The dimension qualification matters: for $n=1$ this is the usual total order on $\mathbb{R}$, so the printed non-totality claim needs the implicit assumption $n\ge 2$.

A least upper bound of $S$ is an element $u\in A$ such that $s⪯u$ for every $s\in S$, and such that $u⪯v$ for every other upper bound $v\in A$ of $S$. It need not belong to $S$. The antisymmetric relation axiom makes it unique whenever it exists.