Let $f$ be a binary relation between sets $A_0$ and $B_0$ and $g$ be a binary relation between sets $A_1$ and $B_1$.

It can be proved that $[f\cap(A_1\times B_1)=g]\wedge [g\cap(A_0\times B_0)=f]$ implies $f=g$.

Really, it follows $g\cap(A_0\times B_0)\cap(A_1\times B_1)=g$. Thus $g\subseteq A_0\times B_0$. Consequantly $g=f$.

Do the following hold?

  1. $[f\cap(A_1\times B_1)\supseteq g]\wedge [g\cap(A_0\times B_0)]\supseteq f$ implies $f=g$.

  2. $[f\cap(A_1\times B_1)\subseteq g]\wedge [g\cap(A_0\times B_0)]\subseteq f$ implies $f=g$.

  • $\begingroup$ what exactly is the difference between $\land$ and $\cap$ in this context? $\endgroup$ – Yanko Nov 22 '18 at 17:55
  • $\begingroup$ @Yanko: Their meanings are standard - $\cap$ is intersection of sets, $\wedge$ is conjunction of statements (meaning 'and'). $\endgroup$ – Clive Newstead Nov 22 '18 at 17:56
  • $\begingroup$ @CliveNewstead I get that, but if $f,g$ are binary relations, isn't $f\land g$ the same as $f\cap g$ where $f$ and $g$ are being viewed as subsets of the cartesian product? $\endgroup$ – Yanko Nov 22 '18 at 17:57
  • $\begingroup$ @Yanko: I'd presume so, yes. What's the confusion? $\endgroup$ – Clive Newstead Nov 22 '18 at 17:58
  • 2
    $\begingroup$ @Yanko: Ah, you're just parsing it wrong. Read it as $$[f \cap (A_1 \times B_1) = g] \wedge [g \cap (A_0 \times B_0) = f]$$ and so on. $\endgroup$ – Clive Newstead Nov 22 '18 at 18:01

It is true in general that if $X \subseteq Y \cap Z$, then $X \subseteq Y$ and $X \subseteq Z$. The hypothesis of statement (1) implies that $f \subseteq g$ and $g \subseteq f$, and so $f = g$, as required. So statement (1) is true.

The hypothesis of statement (2) holds for all $f,g$, provided that $A_0 \cap A_1 = \varnothing$ or $B_0 \cap B_1 = \varnothing$, so it doesn't follow in general that $f=g$. So statement (2) is false in general.

In fact, more generally, we have $(A_0 \times B_0) \cap (A_1 \times B_1) = (A_0 \cap A_1) \times (B_0 \cap B_1)$, and so the hypothesis of (2) holds whenever the relations $f$ and $g$ agree on $(A_0 \cap A_1) \times (B_0 \cap B_1)$; but then $f$ and $g$ can say what they like about the elements not in these intersections, so they need not be equal.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.