Paper 4, Section I, E

Numbers and Sets | Part IA, 2009

Let R1R_{1} and R2R_{2} be relations on a set AA. Let us say that R2R_{2} extends R1R_{1} if xR1yx R_{1} y implies that xR2yx R_{2} y. If R2R_{2} extends R1R_{1}, then let us call R2R_{2} an extension of R1R_{1}.

Let QQ be a relation on a set AA. Let RR be the extension of QQ defined by taking xRyx R y if and only if xQyx Q y or x=yx=y. Let SS be the extension of RR defined by taking xSyx S y if and only if xRyx R y or yRxy R x. Finally, let TT be the extension of SS defined by taking xTyx T y if and only if there is a positive integer nn and a sequence (x0,x1,,xn)\left(x_{0}, x_{1}, \ldots, x_{n}\right) such that x0=x,xn=yx_{0}=x, x_{n}=y, and xi1Sxix_{i-1} S x_{i} for each ii from 1 to nn.

Prove that RR is reflexive, SS is reflexive and symmetric, and TT is an equivalence relation.

Let EE be any equivalence relation that extends QQ. Prove that EE extends TT.

Typos? Please submit corrections to this page on GitHub.