2
$\begingroup$

I try to prove that if $A \subset B \cap C$, then $A \subset B$ and $A \subset C$. I go through:

(1) For all $x \in A, x \in B \cap C$.

(2) For all $x \in A, x \in B$ and $x \in C$

(3) For all $x \in A, x \in B$ and for all $x \in A, x \in C$

(4) So $A \subset B$ and $A \subset C$

I'm not sure if step 2 to 3 is sound. But my real question is why I can't replace all "$\cap$"s with "$\cup$"s and all "and"s with "or"s and prove the obviously false $A \subset B \cup C \implies A \subset B$ or $A \subset C$.

$\endgroup$
2
$\begingroup$

Suppose $A \subseteq B \cap C$, and take an arbitrary element $x \in A$. Since $A \subseteq B \cap C$, you know that $x \in B \cap C$, so that $x \in B$ and $x \in C$. As such, from the hypothesis that $A \subseteq B \cap C$, from the sole knowledge that $x \in A$, you can deduce that $x \in B$ (and hence $A \subseteq B$) and $x \in C$ (and hence $A \subseteq C$).

However, suppose now that $A \subseteq B \cup C$. If you wanted to prove that $A \subseteq B$ or $A \subseteq C$, you'd need every element of $A$ to be an element of $B$, or you'd need every element of $A$ to be an element of $C$. But given the hypothesis, you know that for each $x \in A$, either $x \in B$ or $x \in C$, but you don't know which—it's possible for some elements of $A$ to be in $B$, and some elements of $A$ to be in $C$, without necessitating that each element of $A$ be in only one of the sets $B$ or $C$. So the argument doesn't carry over.

And, indeed, there are counterexamples; take $A = \{ 0, 1 \}$, $B = \{ 0 \}$ and $C = \{ 1 \}$. Then $A \subseteq B \cup C$, but $A \nsubseteq B$ and $A \nsubseteq C$.

The crux of why you can't just replace $\cap$ by $\cup$ has to do with a duality in propositional logic: if $p \to (q \wedge r)$, then $p \to q$ and $p \to r$; but $p \to (q \vee r)$ does not imply $p \to q$ and it does not imply $p \to r$.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ I guess that helps. Maybe could someone really symbolically flesh out why, in the union/or case, step 2 doesn't imply step 3? $\endgroup$ – SomeNewCoderMan666 Sep 5 '17 at 5:08
  • $\begingroup$ @SomeNewCoderMan666: I thought my answer did flesh that out. (There's even a counterexample!) Another way of thinking about this is to ask yourself: why should it be true for unions instead of intersections? In mathematical arguments, it's almost never the case that a proof remains true if you replace one symbol by another. (For example, $x+3=3+x$ does not imply $x-3=3-x$.) $\endgroup$ – Clive Newstead Sep 5 '17 at 5:16
1
$\begingroup$

Your argument is sound. What fails in the case of union is the passage from $1$ to $2$. In $2$ you would get $x \in B$ or $x \in C$. You could have some of $A$ in $B$ and the rest of $A$ in $C$, so you can't reach step $4$. An example is $A=\{1,2\}$, $B$ is the even numbers and $C$ is the odd numbers.

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

Yes.   You can also express it thusly:

$$\begin{array}{l:l}(0) & A\subseteq (B\cap C) \\ (1) &\forall x~(x \in A \to x \in B \cap C)\\(2) &\forall x~(x \in A \to (x \in B\wedge x \in C))\\(2.5) &\forall x~((x \in A \to x \in B)\wedge (x \in A\to x \in C))\\(3) &\forall x~(x \in A \to x \in B)~\wedge~\forall x~(x \in A\to x \in C)\\(4) & \text{So $A \subseteq B$ and $A \subseteq C$}\end{array}$$

For union, we start the same:

$$\begin{array}{l:l}(1) &\forall x~(x \in A \to x \in B \cup C)\\(2) &\forall x~(x \in A \to (x \in B\vee x \in C))\\(2.5) &\forall x~((x \in A \to x \in B)\vee (x \in A\to x \in C))\end{array}$$

But we cannot go any further because $\forall x~(P(x)\vee Q(x))$ does not infer that $(\forall x~P(x))\vee( \forall x~Q(x))$.

("All royal women are princesses or queens" does not infer that "All royal women are princesses, or all royal women are queens".)

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Thanks a lot! this makes a lot of sense. Could someone prove why the second to last statement (the propositional statement) is true? $\endgroup$ – SomeNewCoderMan666 Sep 5 '17 at 5:20
  • $\begingroup$ I guess I don't understand why (symbolically) distributing the universal quantifier doesn't work. (I get that it doesn't, I just don't know why formally.) Also, why does it distribute in the intersection/and case? $\endgroup$ – SomeNewCoderMan666 Sep 5 '17 at 5:23
  • $\begingroup$ If everything is both $P$ and $Q$, then both everything is $P$, and everything is $Q$. $\endgroup$ – Graham Kemp Sep 5 '17 at 5:25
  • $\begingroup$ If everything is either $P$ or $Q$, then ... there may be some things which are $P$ but not $Q$, and some which are $Q$ but not $P$. $\endgroup$ – Graham Kemp Sep 5 '17 at 5:28
  • $\begingroup$ I know. It makes sense. Is there a symbolic proof of why this works but the union/or case doesn't work? Perhaps using truth tables? $\endgroup$ – SomeNewCoderMan666 Sep 5 '17 at 5:30
0
$\begingroup$

If you would try the same proof for unions, you get the following:

Choose $x\in A$. Since $A\subset B\cup C$ we have $x\in B\cup C$. Hence $x\in B$ or $x\in C$. Hence we get the statement:

$$\forall x\in A: (x\in B \text{ or } x\in C).$$ This is not equivalent to $$\forall x\in A: x\in B \text{ or } \forall x\in A:x\in C.$$ Thus this step doesn't work anymore.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Can someone show why this is not equivalent? Thanks! $\endgroup$ – SomeNewCoderMan666 Sep 5 '17 at 5:03
  • $\begingroup$ The best way to see this is to reformulate the statements in propositional logic and make their truth tables. Comparing the two will show they are different. (See the last three sentences of Clive's answer). $\endgroup$ – Mathematician 42 Sep 5 '17 at 5:08
  • $\begingroup$ Take for example $B = {1,2,3,4} $ , $C={2,3,5,6}$ and $A={1,2,3,6}$ then see for all $x$ in $A$ , either $x$ is in $B$ or in $C$ , i.e to say that for all $x$ in $A$ : $x$ is in $B$ or $x$ is in $C$ is not true. $B $ contains elements which is not in $A$ . $\endgroup$ – hiren_garai Sep 5 '17 at 5:14
  • $\begingroup$ But isn't p implies (q or r) equivalent to (p implies q) or (p implies r)? $\endgroup$ – SomeNewCoderMan666 Sep 5 '17 at 5:15
  • $\begingroup$ For any $x$ you have statements $P(x), Q(x) $ and $R(x)$. Don't forget the quantors. $\endgroup$ – Mathematician 42 Sep 5 '17 at 5:36

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.