6
$\begingroup$

I am currently refreshing my knowledge in naive set theory, and would like to prove that for all sets $A,B,C$ we have $$A\cap(B \cup C) = (A \cap B) \cup (A \cap C).$$

I understand that this can be done by proving both $$A\cap(B \cup C) \subset (A \cap B) \cup (A \cap C) \ \text{and} \ (A \cap B) \cup (A \cap C) \subset A\cap(B \cup C) $$ hold true.

We can do this by letting $x$ be an arbitrary element of $A\cap(B \cup C)$ and showing that it is an element of $(A \cap B) \cup (A \cap C)$, and vice versa.

But what about when $A \cap (B \cup C)$ is the empty set? Then I would think we can't let $x$ be an arbitrary element of $A \cap (B \cup C)$ since there are none. However, I am aware that $A \cap (B \cup C) \subset (A \cap B) \cup (A \cap C)$ is trivially true in this case.

In the discrete mathematics course I took at my university, I did not see such cases be brought to attention. Should they be mentioned in proofs of such identities? Why / why not?

If so, some suggestions as to how to incorporate them into proofs would be helpful :-).

$\endgroup$
  • 5
    $\begingroup$ Because some of the two sides being the empty set is no problem. Your claim is: for any element here, I prove it also is an element there. If there is no element at all then that is not your problem (mathematicalwise, of course): the proof still holds! Anyway, if you still feel something else must be done (though it really mustn't), then you can make a separate case: if this side is empty then so and so. and also the other side is, and the other way around, too. But you really don't need that, $\endgroup$ – DonAntonio Dec 22 '18 at 18:35
  • $\begingroup$ Words to live by: "vacuous truth". I am almost tempted to say this is a duplicate of many other questions that were asked before. For example, math.stackexchange.com/questions/734418/… math.stackexchange.com/questions/2723860/… math.stackexchange.com/questions/1953218/… and there are many others which are similar. $\endgroup$ – Asaf Karagila Dec 23 '18 at 10:24
11
$\begingroup$

In order to show that for two sets $X$ and $Y$ it holds that $X\subseteq Y$, you have to prove that

for every $x$, if $x\in X$, then $x\in Y$.

Note that a statement of the form “if $\mathscr{A}$ then $\mathscr{B}$” is true when

either $\mathscr{A}$ is false or both $\mathscr{A}$ and $\mathscr{B}$ are true

If $X$ is the empty set, then “$x\in X$” is false for every $x$; hence “if $x\in X$ then $x\in Y$” is true.

The phrase “take an arbitrary element $x\in X$” is possibly misleading, but its intended meaning is “suppose $x\in X$”.

| cite | improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ Ah, so if we write "suppose $x \in X$" and successfully deduce that "$x \in Y$" , we have shown that "if $x \in X$, then $x \in Y$" is true. But, if "$x \in X$" is always false, we have still shown "if $x \in X$ then $x \in Y$" is true, since as you wrote, the implication would be true for all $x$ in that case. I.e. we are allowed to suppose things are true, even when they may never be. Is my understanding correct? $\endgroup$ – user445909 Dec 22 '18 at 19:39
  • $\begingroup$ @E-mu Basically so $\endgroup$ – egreg Dec 22 '18 at 20:27
6
$\begingroup$

If $D$ is the empty set then the following statement is always true:$$\text{If }x\in D\text{ then }\cdots$$no matter what the dots are standing for.

It is false that $x\in D$ and "ex falso sequitur quodlibet". A false statement implies whatever you want.

So the assumption will not bring you into troubles, but - on the contrary - will give you freedom to accept whatever you want.

| cite | improve this answer | |
$\endgroup$
3
$\begingroup$

Since the empty set is a subset of any set, there is no need of including that in a formal proof. However it is a good idea to be aware of the fact that the equality holds even in the case of empty sets .

| cite | improve this answer | |
$\endgroup$

Your Answer

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