Define a relation $M$ on $A×B$ Prove that $M \circ M = (A×A) × (A×B)$.

Question

Define a relation $M$ on $A×B$ by $(a,b)M(p,q) \iff$ $a=p$ or $b=q$ Prove that $M\circ M = (A×A) × (A×B)$

What I have so far..

Proof:

Let $x,y ∈ A×B$

Then, $(x,y) M (x,y)$ since $x=x$ it is reflexive

Let $(a,b)$ & $(p,q)$ $∈ A×B$ assume $(a,b)M(p,q)$ & $a=p$ or $b=q$. Therefore $p=a$ or $q=b$ $(p,q)M(a,b)$, so $M$ is symmetric.

Let $(1,2)M(1,5)$ & $(1,5)M(6,5)$ since $(1,2)M(6,5)$ is not true and so is not transitive

I'm confused on how to to prove $M\circ M$ [which I believe is equivalent to $M(M(x))$] is equal to $(A×A) ×(A×B)$.

Also, there is a hint

(You need to prove only that $(A×B) ×(A×B) ⊆ M\circ M$, since the opposite inclusion is clear)

Answer 1

It seems like you saw the problem "prove that $M\circ M = (A \times B) \times (A \times B)$" and decided to answer the entirely unrelated problem "prove that $M$ is an equivalence relation". The only thing these problems have in common is that they're both talking about relations.

In fact, it is worth noting that $M$ is transitive is precisely the same as saying that $(M \circ M) \subseteq M$, which is notably inconsistent with what we're trying to prove.

It seems that what you're really missing here is an understanding of the question. Let's clarify that. To start, look at that statement from the hint:

You need to prove only that $(A \times B) \times (A \times B) ⊆ M \circ M$

The key is to understand what that $M \circ M$ really means. Unfortunately, $M(M(x))$ only really makes sense if $M$ is a function, although that is a helpful intuition. Start here: $((a,b),(c,d)) \in M \circ M$ means that there is some $(x,y) \in A \times B$ such that $(a,b)M(x,y)$ and $(x,y)M(c,d)$. So let's rephrase that hint accordingly:

Hint: You need to prove only that for every pair $(a,b),(c,d)$, there exists an element $(x,y) \in A \times B$ such that $(a,b)M(x,y)$ and $(x,y)M(c,d)$.

Now, what is the "opposite inclusion" they're talking about?

If $(a,b)$ and $(c,d)$ are such that there exists a pair $(x,y) \in A \times B$ with $(a,b)M(x,y)$ and $(x,y)M(c,d)$, then $((a,b),(c,d)) \in (A \times B) \times (A \times B)$.

Think about it long enough to realize that we shouldn't worry about it. Now, try to prove that statement in my hint, and that'll be the proof!