Using a counterexample, explain why the following proposition is false: $A\subset B \Longrightarrow A\circ \theta \subset B \circ \theta $

Question

3 relations: $A, B \subseteq X \times Y$ and $\theta \subseteq Y \times Z$

Using a counterexample, explain why the following proposition is false: $A\subset B \Longrightarrow A\circ \theta \subset B \circ \theta $

How do I tackle this problem? From my understanding, the following proposition is $true$ only if the left side is $false$ OR if the right side is $true$.

Edit: So I need to find an example where the left side is $true$, and the right side is $false$.

Let $ \emptyset \subset A$, $ \emptyset \subset B$, $ \emptyset \subset \theta $

Let $B\in \langle x,y\rangle $ $$$$ So far, I believe the left side $A\subset B$ is true.

Let $ \theta \in \langle y,z\rangle $

$A\circ \theta$ = $\emptyset$

$B \circ \theta \in \langle x,z\rangle $

I did all I could. Any help is appreciated to solve this problem. Thank you!

Answer 1

You are right in your understanding of when the proposition is true. Thus, the proposition is false is simply the opposite of that, using De Morgan's Laws: The conditional is false when the left side is true and the right side is false.

Now, the key to solving this problem is that it's strict subset, which I will from here on out denote as $\subsetneqq$. If this wasn't strict subset, then this would be true. That gives us a clue as to what the answer is: We want $A \subsetneqq B$ to be true to satisfy the hypothesis, but then $A \circ \theta = B \circ \theta$ in order to make the right side false.

How do we do this? Well, we can make $A \circ \theta=B \circ \theta$ if we make all of the $x \in X$ relate to all of the $z \in Z$. This is easy if $X$ has just one element and $Z$ has just one element, so we will say $X=\{x_0\}$ and $Z=\{z_0\}$. Also, to make all of the $z \in Z$ be in the range, we can make $\theta=Y \times Z$.

Now, for $A \subsetneqq B$ without any of them being an empty set, we can have one element in $A$ and two elements in $B$. Since we have decided that $X$ and $Z$ only have one element, this means $Y$ needs two elements, so we will make it $\{y_0,y_1\}$. Thus, the one element in $A$ can be $(x_0,y_0)$ and the two elements in $B$ can be that and $(x_0,x_1)$.

Now, to clarify, here is our counterexample: $$X=\{x_0\} \\ Y=\{y_0,y_1\} \\ Z=\{z_0\} \\ A=\{(x_0,y_0)\} \\ B=\{(x_0,y_0),(x_0,y_1)\} \\ \theta=Y \times Z=\{(y_0,z_0),(y_1,z_0)\} \\ A\circ \theta=B \circ \theta=X \times Z=\{(x_0,z_0)\}$$

Hopefully, this helps you understand how to construct counterexamples to statements that seem to be true because there are statements very close to them that are true: Identify the statement very close to this that is true and then try to think outside of that statement.

Answer 2

Let $X=\{1,2\},$ $Y = \{p,q,r\},$ $Z = \{y,z\}.$

Let $A=\{(1,p), (2,r)\},$ $B=\{(1,p),(1,q),(2,q), (2,r)\},$ $\theta=\{(p,y),(r,y),(r,z)\}.$

Then $A\subsetneq B,$ and $A\circ\theta \subseteq B\circ\theta,$ but $A\circ\theta = B\circ\theta.$ The relation $B\circ\theta$ is not more extensive than the relation $A\circ\theta$, because $r\in B$ is not related via $\theta$ to anything.