Suppose $R$ is a relation on $A$, and $S$ is a relation on $\mathscr P(A)$. If $R$ is transitive, must $S$ be transitive?

Question

These are Velleman's exercises 4.3.19 and 4.3.21.c ("$\mathscr P(A)$" is the power set of $A$):

In problem 19, $S$ is defined as:

$$S = \{(X, Y ) ∈ \mathscr P(A) × \mathscr P(A) | ∃x ∈ X∃y ∈ Y (x Ry)\}.$$

In problem 21, $S$ is defined as:

$$S = \{(X, Y ) ∈ \mathscr P(A) × \mathscr P(A) | ∀x ∈ X∃y ∈ Y (x Ry)\}.$$

Now here are my questions:

1. Does the counterexample below work for both questions (i.e. exercises 19 and 21)?

$$A = \{1,2\},$$

$$R = \{(1,2), (2,1), (1,1)\},$$

$$S = \{(\{1\}, \{2\}), (\{2\}, \{1\})\}.$$

2. I'm having a difficulty understanding the distinction between those two definitions of $S$ given above.

3. Why in both definitions we have "$xRy$"? How "$R$", primarily a relation on $A$, could link $x$ and $y$ which are elements of "$\mathscr P(A)"$?

Thanks a lot.

Answer 1

To answer the first part of your three questions, no your "counterexample" doesn't work because your $S$ is incorrect. Given a specific $A$ and $R$, there is only one possible $S$ that follows and your $S$ is not the correct one. $S$ is defined in terms of $A$ and $R$.

To see this more clearly and to hopefully answer the following two questions, perhaps a worked out example will help so you can see what $S$ is for a specific relation.

Let $A=\{apple, banana, cherry\}$

Let $R$ be the relation on $A$ where $xRy$ iff the words share a letter in common. That is to say $R=\{(apple, apple),(apple, banana),(apple, cherry),(banana,apple),(banana,banana),(cherry,apple),(cherry,cherry)\}$

Notice that apple is related to banana for example because they both have the letter $a$ appearing in the words. It is also worth mentioning that $R$ is not in this specific example transitive because although banana is related to apple and apple is related to cherry, we do not have that banana is related to cherry. There are no letters in common between those words.

For the first problem's definition of $S$, we have:

$S=\{(\{apple\},\{apple\}),(\{apple\},\{apple,banana\}),(\{apple\},\{apple,cherry\}),(\{apple\},\{banana,cherry\}),(\{apple\},\{apple,banana,cherry\}),(\{apple,banana\},\{apple\}),\dots\}$

Reworded for our specific $R$, the relation $S$ is between sets of fruit where the set of fruit $X$ is related to the set of fruit $Y$ iff at least one of the fruits names in $X$ shares a letter in common with at least one of the fruits names in $Y$.

For example, $\{\color{red}{a}pple,cherry\}$ is related to $\{b\color{red}{a}nana\}$ because of the red $a$.

In the second problem, with the same $A$ and $R$, the relation $S$ could be described instead as the relation between sets of fruit $X$ and $Y$ where every fruit in $X$ shares a letter with at least one fruit in $Y$. In this example $\{apple,cherry\}$ would not be related to $\{banana\}$ because although apple shares a letter with banana, cherry does not.

This should hopefully explain to you the difference between the definitions for $S$ in the two problems and how to think of $S$ in general.

---

As for the content of the original question, the goal is to show that if $(X,Y)\in S$ and if $(Y,Z)\in S$ that it must follow that $(X,Z)\in S$

For the first definition of $S$, Since $(X,Y)\in S$ and $(Y,Z)\in S$ that means that there is some $x\in X$ and $y_1\in Y$ that $(x,y_1)\in R$ and that there is some $y_2\in Y$ and $z\in Z$ such that $(y_2,z)\in R$. The difficulty though is that $y_1$ might be different than $y_2$. If we knew that $y_1$ and $y_2$ were the same, the transitivity of $R$ would imply that $(x,z)\in R$. Since there doesn't appear to be any way to rectify this ambiguity it should be a very big hint as to how to construct a counterexample.

For the second definition of $S$, since $(X,Y)\in S$ and $(Y,Z)\in S$ that means that all $x\in X$ have some $y_x\in Y$ such that $(x,y_x)\in R$ and that for all $y\in Y$ there is some $z_y\in Z$ such that $(y,z_y)\in R$. Note that the value of $y_x$ can depend on the value of $x$ and does not need to be the same.

Now... for each value of $x\in X$ then we have a corresponding $y_x\in Y$ and $z_{y_x}\in Z$ such that $(x,y_x)$ and $(y_x,z_{y_x})$. Transitivity of $R$ will now imply something about $(x,z_{y_x})$ and the definition of $S$ will then imply something then about $(X,Z)$ which further implies something about $S$ itself.

Answer 2

1. No, in both cases, your $S$ is not the relation defined from your $R$ using the definition. For example, in both cases, $(\{ 1, 2 \}, \{ 1, 2 \}) \in S$.
2. The difference is in the quantifier on $x$. For example, $(\{ 1, 2 \}, \{ 2 \}) \in S$ in the first case for your $R$, since for $x = 1$ and $y = 2$ we have $1 \in \{ 1, 2 \}$, $2 \in \{ 2 \}$. However, it is not in $S$ in the second case for your $R$, since for $x = 2$ there is no element $y \in \{ 2 \}$ such that $(x, y) \in R$.
3. $x \mathrel{R} y$ is just a shorthand notation for $(x, y) \in R$. And if you look at the definitions, the quantifiers "bind" $x$ to be an element of $X \subset A$, and therefore $x \in A$ also; and similarly, $y$ is "bound" to be an element of $Y \subset A$.