Suppose that $f$ is surjective and relation preserving. Then $\mathcal{R}$ is reflexive iff $\mathcal{S}$ is reflexive.

Question

This is a problem about relations from Proofs and Fundamentals by Ethan D. Bloch that I’m having some doubts and I would really appreciate if you could guide me.

The problem starts with the following definition:

Definition: Let $A,B$ be sets, and let $\mathcal{R}, \mathcal{S}$ be relations on $A$ and $B$, respectively. Let $f: A \rightarrow B$ be a map. We say that $f$ is relation preserving if and only if $xRy$ iff $f(x)Sf(y)$ for all $x, y \in A$.

After this we have the following result:

Result: Suppose that $f$ is surjective and relation preserving. Then $\mathcal{R}$ is reflexive, symmetric or transitive iff $\mathcal{S}$ is reflexive, symmetric or transitive (respectively).

I attempt to show the reflexive part. And I have the following:

Proof: $\implies$. Suppose that $\mathcal{R}$ is reflexive. By definition, we have that $aRa$ for all $a \in A$. Since $f$ is relation preserving, it follows that $f(a)Sf(a)$. Since $f$ is surjective, we know that for all $b \in B$, there existis an element $a \in A$ such that $b = f(a)$. From this we know that $f(a)Sf(a)$ for all $f(a) \in B$. Hence, by definition, $\mathcal{S}$ is reflexive.

$\Longleftarrow$. Suppose that $\mathcal{S}$ is reflexive. By definition, we have that $bSb$ for all $b \in B$.

Although, I don’t know what the next step should be. How can I deduce that $\mathcal{R}$ is reflexive?

Also, will the proof for the other two properties be similar to this one?

Thank you for your attention!

Answer 1

Suppose that $\mathcal{S}$ is reflexive, let $a\in A$, and let $b=f(a)$. Since $f$ is relation-preserving, $a\,\mathcal{R}\,a$ iff $f(a)\,\mathcal{S}\,f(a)$, i.e., iff $b\,\mathcal{S}\,b$. And $\mathcal{S}$ is reflexive, so $b\,\mathcal{S}\,b$, and therefore $a\,\mathcal{R}\,a$. Thus, $\mathcal{R}$ is reflexive.

Yes, the other two properties can be proved in much the same fashion.

Answer 2

Note that the iff part in the definition of a relation-preserving function. Also, this can be proven more easily by a chain of equivalences:

\begin{align} \textrm{$R$ is reflexive} \ & \textrm{ iff } \ (\forall a)(a \in A \to aRa) \\ \ & \textrm{ iff } \ (\forall a)(a \in A \to f(a)Sf(a)) \quad [\textrm{by definition of relation-preserving}] \\ \ & \textrm{ iff } \ (\forall b)(b \in B \to bSb) \quad [\textrm{since $f$ is surjective}] \\ \ & \textrm{ iff } \ \textrm{$S$ is reflexive.} \end{align}

And, if you're still not convinced of the third equivalence:

Suppose $(\forall a)(a \in A \to f(a)Sf(a))$ and take $b \in B$. Since $f$ is surjective, there exists $a_b \in A$ such that $b = f(a_b)$, and hence $f(a_b)Sf(a_b)$ implies that $bSb$. So, it is also true that $(\forall b)(b \in B \to bSb)$. Now suppose $(\forall b)(b \in B \to bSb)$ and take $a \in A$. Since $f(a) \in B$ we have $f(a)Sf(a)$, and so, $(\forall a)(a \in A \to f(a)Sf(a))$.

Answer 3

Let $\Phi(X,\mathcal X)$ be any statement about a relation $\mathcal X\subseteq X\times X$ that has the form $$ \forall x_1\in X,\ldots,\forall x_n\in X\colon \psi(\mathcal X;x_1,x_2,\ldots, x_n)$$ where $\psi$ is any logical formula with atoms of the form $x_i\mathrel {\mathcal X} x_j$. Examples:

• Refexivity: $\forall a\in X\colon a\mathrel {\mathcal X} a$
• Symmetry: $\forall a\in X, \forall b\in X\colon a\mathrel {\mathcal X} b\to b\mathrel {\mathcal X} a$
• Transitivity: $\forall a\in X, \forall b\in X,\forall c\in X\colon a\mathrel {\mathcal X} b\land b\mathrel {\mathcal X} c\to a\mathrel {\mathcal X} c$

Assume $f\colon A\to B$ is onto and relation-preserving for $\mathcal R\subseteq A\times A$, and $\mathcal S\subseteq B\times B$. Then $$\Phi(A,\mathcal R)\iff \Phi(B,\mathcal S).$$

Proof. First assume $\Phi(A,\mathcal R)$. Let $y_1,\ldots, y_n\in B$. By surjectivity of $f$, there exist $x_1,\ldots, x_n\in A$ with $f(x_i)=y_i$. By assumption $\psi(\mathcal R; x_1,\ldots,x_n)$ is true. By relation preserving, $\psi(\mathcal R; x_1,\ldots,x_n)\leftrightarrow\psi(\mathcal S; y_1,\ldots,y_n)$ (directly, per "atom", but the also as a whole). As the $y_i$ were arbitrary, we conclude $\Phi(B,\mathcal S)$.

The argument that $\Phi(B,\mathcal S)$ implies $\Phi(A,\mathcal R)$ is even more direct. $\square$