2
$\begingroup$

Prove or give a counterexample:

$$(A ∪ B = A ∪ C) \land (A ∩ B = A ∩ C) \implies B = C.$$

I think this is true, but I am not sure how to show it. I don't know if there are any manipulations with unions and intersections that allows me to move things around. Thanks in advance for any hints.

$\endgroup$
  • $\begingroup$ Note that this is essentially the same thing as saying "you can uniquely identify a set if you know its intersection with $A$ and its union with $A$". $\endgroup$ – Excluded and Offended Oct 7 '15 at 9:34
  • 1
    $\begingroup$ BTW the same question was asked previously here. $\endgroup$ – Martin Sleziak Oct 7 '15 at 16:28
  • $\begingroup$ @AlecTeal Re: How is this a hot question? My guess would be that there are several factors here. The questions having MathJax in the title cannot get to the hot question list. This radically reduces the number of questions that can appear there. And when question with a title like this appears among the hot questions, I guess it can get more views than, for example, some question about homology. (There are more people that can say: "Well, based on the title, this might be something I might be able to solve.) $\endgroup$ – Martin Sleziak Oct 8 '15 at 3:54
  • $\begingroup$ I should add that I do not necessarily think that this is a bad thing. If some question appears in the list and makes several users aware of this site, then maybe some of those users can come here later again and contribute to this site. I have thought about some related issues recently - see here. However, I am not sure whether it is important enough issue to bring up on meta. (And even if I decide to ask about this on meta, I should think a bit more about the way how to frame this question and how to clarify what I want to ask.) $\endgroup$ – Martin Sleziak Oct 8 '15 at 3:57
21
$\begingroup$

$$\begin{align} B &= B \cup (A \cap B)\\ &= B \cup (A \cap C)\\ &= (B \cup A) \cap (B \cup C)\\ &= (C \cup A) \cap (B \cup C)\\ &= (C \cup A) \cap (C \cup B)\\ &= C \cup (A \cap B)\\ &= C \cup (A \cap C)\\ &= C \end{align}$$

$\endgroup$
  • $\begingroup$ how did you get the first line? $\endgroup$ – Jacob Rodgers Oct 7 '15 at 2:52
  • $\begingroup$ By observing that $(A \cap B) \subset B$ $\endgroup$ – BigbearZzz Oct 7 '15 at 2:54
  • 1
    $\begingroup$ +1, this is the easiest answer... needing basically no explanation. $\endgroup$ – jdods Oct 7 '15 at 3:10
7
$\begingroup$

We want to show that (i) every element of $B$ is an element of $C$ and (ii) every element of $C$ is an element of $B$. There is symmetry, so the proof of (ii) is almost the same as the proof of (i). We prove (i).

Proof of (i). Let $x\in B$. We want to show that $x\in C$.

Suppose first that $x$ is not an element of $A$. We have $x\in A\cup B$, so $x\in A\cup C$. But $x$ is not in $A$, so $x$ is in $C$.

Suppose next that $x$ is an element of $A$. We have $x\in A\cap B$, therefore $x\in A\cap C$, and therefore $x\in C$.

$\endgroup$
3
$\begingroup$

Don't worry too much about tricks. If $x \in B$, then either $x \in B \cap A$ or $x \in B \setminus A$. Using those two cases, can you show that if $x \in B$, then $x \in C$ ?

If you can, then you can use that, and symmetry (ie swap $B$ for $C$), to establish the result.

$\endgroup$
2
$\begingroup$

To the earlier barrage of answers, here is an alternative in a different style: treat this as a simplification problem, and try to do this using the laws of logic, so on the level of elements/logic rather than on the set level, by starting out with expanding the definitions.

The number of symbols may seem a bit daunting at first, but the structure is really straightforward.$ \newcommand{\calc}{\begin{align} \quad &} \newcommand{\op}[1]{\\ #1 \quad & \quad \unicode{x201c}} \newcommand{\hints}[1]{\mbox{#1} \\ \quad & \quad \phantom{\unicode{x201c}} } \newcommand{\hint}[1]{\mbox{#1} \unicode{x201d} \\ \quad & } \newcommand{\endcalc}{\end{align}} \newcommand{\ref}[1]{\text{(#1)}} \newcommand{\then}{\Rightarrow} \newcommand{\followsfrom}{\Leftarrow} \newcommand{\true}{\text{true}} \newcommand{\false}{\text{false}} $

This gives us:

$$\calc A \cup B = A \cup C \;\land\; A \cap B = A \cap C \op\equiv\hint{set extensionality, twice} \langle \forall x :: x \in A \cup B \;\equiv\; x \in A \cup C \rangle \;\land\; \\& \langle \forall x :: x \in A \cap B \;\equiv\; x \in A \cap C \rangle \op\equiv\hint{definitions of $\;\cup\;$ and $\;\cap\;$, each twice} \langle \forall x :: x \in A \lor x \in B \;\equiv\; x \in A \lor x \in C \rangle \;\land\; \\& \langle \forall x :: x \in A \land x \in B \;\equiv\; x \in A \land x \in C) \rangle \op{\tag{*} \equiv}\hints{logic: LHS: extract common disjunct, see $\ref 0$ below;} \hint{RHS: extract common conjunct, see $\ref 1$ below} \langle \forall x :: x \in A \;\lor\; (x \in B \equiv x \in C) \rangle \;\land\; \\& \langle \forall x :: x \in A \;\then\; (x \in B \equiv x \in C) \rangle \op\equiv\hint{logic: write $\;P \then Q\;$ as $\;\lnot P \lor Q\;$; merge quantifications} \langle \forall x :: (x \in A \;\lor\; (x \in B \equiv x \in C)) \;\land\; (x \not\in A \;\lor\; (x \in B \equiv x \in C)) \rangle \op\equiv\hint{logic: extract common disjunct} \langle \forall x :: (x \in A \land x \not\in A) \;\lor\; (x \in B \equiv x \in C) \rangle \op\equiv\hint{logic: left part is contradiction; simplify} \langle \forall x :: x \in B \equiv x \in C \rangle \op\equiv\hint{set extensionality} B = C \endcalc$$

The key step here of course is $\ref{*}$ which start the simplification phase of the calculation. This step uses the following two laws of logic: $\;\lor\;$ distributes over $\;\equiv\;$, and its dual. \begin{align} \tag{0} P \lor (Q \equiv R) &\;\;\equiv\;\; (P \lor Q) \equiv (P \lor R) \\ \tag{1} P \then (Q \equiv R) &\;\;\equiv\;\; (P \land Q) \equiv (P \land R) \end{align}

$\endgroup$
  • $\begingroup$ It is probably not very surprising that this answer seems a bit similar to this one. $\endgroup$ – Martin Sleziak Oct 7 '15 at 16:33
1
$\begingroup$

Short answer: Draw Venn diagram of 3 sets.

Long answer: $$ B=(A\cap B\cap C)\cup(A\cap B\cap C^c)\cup(A^c\cap B\cap C)\cup(A^c\cap B\cap C^c) $$

Observe that the second set in the union above is empty as can be seen here $$ A\cap B\cap C^c = (A\cap B)\cap C^c = (A\cap C)\cap C^c = A\cap(C\cap C^c)=A\cap\emptyset=\emptyset. $$.

Also observe that the last set in the union is also empty as $$ A^c\cap B\cap C^c = B\cap(A^c\cap C^c)=B\cap(A\cup C)^c=B\cap(A\cup B)^c=B\cap A^c\cap B^c=\emptyset. $$ Hence $$ B=(A\cap B\cap C)\cup(A^c\cap B\cap C)=B\cap C. $$ By symmetry $$ C=B\cap C $$ Hence $B=C$.

$\endgroup$
1
$\begingroup$

Let $x\in B\setminus A$, then $x\in A\cup B$. Hence, $x\in A\cup C$. Since $x\notin A$, we must have $x\in C$. In other words, $B\setminus A\subseteq C\setminus A$. A symmetric argument shows that $C\setminus A\subseteq B\setminus A$.

Now, $$B=(A\cap B)\cup(B\setminus A)=(A\cap C)\cup(C\setminus A)=C.$$

$\endgroup$
1
$\begingroup$

Any element in $A\cup B$ is either in $A$ or $B\setminus A$ exclusively (xor). Likewise any element in $A\cup C$ is either in $A$ or $C\setminus A$ exclusively. When the unions are equal, then $B\setminus A=C\setminus A$.

$$A\cup B=A\cup C \vdash B\setminus A=C\setminus A$$

$B$ is the union of $B\setminus A$ and $B\cap A$. We have shown that $B\setminus A$ is $C\setminus A$, and $B\cap A = C\cap A$ is given. Then $B$ is the union of $C\setminus A$ and $C\cap A$; which is $C$.

Therefore $B=C$ when $A\cup B=A\cup C$ and $A\cap B=A\cap C$.

$$(A\cup B=A\cup C ) \wedge (A\cap B=A\cap C) \vdash (B=C)$$

$\endgroup$
1
$\begingroup$

enter image description here $$B=((A\cup B) \backslash A)\cup (A\cap B)=((A\cup C)\backslash A)\cup (A\cap C) = C.$$

$\endgroup$

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.