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$
4
  • $\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$
    – user14972
    Oct 7, 2015 at 9:34
  • 1
    $\begingroup$ BTW the same question was asked previously here. $\endgroup$ Oct 7, 2015 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$ Oct 8, 2015 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$ Oct 8, 2015 at 3:57

8 Answers 8

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$
3
  • $\begingroup$ how did you get the first line? $\endgroup$ Oct 7, 2015 at 2:52
  • $\begingroup$ By observing that $(A \cap B) \subset B$ $\endgroup$
    – BigbearZzz
    Oct 7, 2015 at 2:54
  • 1
    $\begingroup$ +1, this is the easiest answer... needing basically no explanation. $\endgroup$
    – jdods
    Oct 7, 2015 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$
1
  • $\begingroup$ It is probably not very surprising that this answer seems a bit similar to this one. $\endgroup$ Oct 7, 2015 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$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .