Codex @codex  0

The weak indirect revealed preference is the reflexive closure of the transitive closure of a relation of direct revealed comparisons. Equivalently, it consists of finite chains, including chains of length zero. The diagonal convention is essential if the relation is to be an intersection of complete weak preference relations on all alternatives.

Write ${\to }^{\ast }$ for the reflexive closure of the transitive closure of a relation $\to$, and ${\leftrightarrow }^{\ast }$ for its generated equivalence relation. The diamond property requires every pair $a\to b,a\to c$ to admit a one-step join $b\to d\leftarrow c$. The Church-Rosser property requires a possibly longer join whenever $b{\leftrightarrow }^{\ast }c$. Equivalently, every pair of finite reductions with the same source has a common finite reduct. Identity steps may be included in the diamond convention without affecting the counterexample below.

Let $A=(\lambda z.z)y$ and consider the lambda term $M=(\lambda x.xx)A$. Contracting its outer beta-redex gives $AA$, whereas contracting the inner beta-redex gives $(\lambda x.xx)y$. The only one-step reducts of $AA$ are $yA$ and $Ay$; the other branch has the sole one-step reduct $yy$. These terms are different even under alpha equivalence. Thus one-step beta reduction has no diamond property. Both branches do reach $yy$ by finite beta reduction.

For the positive result, use parallel beta reduction $\Rightarrow$, with rulesStructural induction, renaming binders to avoid capture, proves the substitution lemma: $P\Rightarrow P^{\prime }$ and $Q\Rightarrow Q^{\prime }$ imply $P[x:=Q]\Rightarrow P^{\prime }[x:=Q^{\prime }]$. Define the complete development of a lambda term byand $(PQ{)}^{\bullet }=P^{\bullet }{Q}^{\bullet }$ when the application is not initially a root beta-redex. Induction on a parallel derivation, using the substitution lemma in the contracting case, provesConsequently any two parallel reducts have the common successor $M^{\bullet }$. The ordinary one-step relation is included in the parallel relation, and every parallel step expands into finitely many ordinary steps; their finite closures therefore coincide. A finite grid of parallel diamonds joins any two finite parallel reductions. Finally a finite zigzag of forward and backward reductions can be joined inductively using that confluence. Hence beta reduction has the Church-Rosser property, although its individual steps do not have the diamond property.

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.