How to show that if $(A\cup C)\subset (A\cup B)$ and $(A\cap C)\subset (A\cap B)$ then $C\subset B$

Question

I have a question stating

Show that the relations, $(A\cup C)\subset (A\cup B)$ and $(A\cap C)\subset (A\cap B)$ when combined imply that $C\subset B$.

I'm not quite sure about how to go about showing this. I started by saying that each relation suggests: $$(\forall x\in A\cap C) x\in A\cap B \Rightarrow x\in A \ \text{and} \ x\in B \ \text{and} \ x\in C \\ \\ (\forall y\in A\cup C) y\in A\cup B \Rightarrow y\in A \ \text{or $y\in B$ or $y\in C$} $$ I don't know where to go from here. I know that I need to show that $(\forall x\in C)x\in B$ but how do I get to that? I also feel like it should be possible to do with one variable $x$, and me adding the $y$ is just confusing things.

Answer 1

Assume that there is a $x\in C$ and $x\notin B$

If $x\in A$ then $x\in A\cap C$ so $x\in A\cap B $ and so $x\in B$ a contradiction.

So $x\notin A$ but $x\in A\cup C$ so $x\in A\cup B$. But then $x\in B$ since $x\notin A$. A contradiction again.

Answer 2

Let $x\in C$. Then either $x\in A$ or $x\in B$. If the former, then $x\in A\cap C$, hence $x\in A\cap B$. Can you finish?

Answer 3

A solution using indicatior function which turns the problem into manipulation of equalities and inequalities of real numbers. The proof uses the fact that the map $ A\to I(A)$ is a bjection from $P(\Omega)$ to $2^{\Omega}$ where $\Omega$ is a universe and that $A\subset B\iff I(A)\leq I(B)$. Further the identities $I(A\cap B)=I(A)I(B)$ and finally $I(A\cup B)=I(A)+I(B)-I(A)I(B)$ will be of use.

The assumption $$ (A\cup C)\subset (A\cup B)\implies I(A)+I(C)-I(A)I(C)\leq I(A)+I(B)-I(A)I(B)\tag{1}. $$ The assumption $$ (A\cap C)\subset (A\cap B)\implies I(A)I(C)\leq I(A)I(B). \tag{2} $$ Combining both pieces of information we get that $$ I(C)-I(B)\leq I(A)I(C)-I(A)I(B)\leq0 $$ as desired.

Answer 4

$\tiny\begin{split}(A\cap C)\subset (A\cap B) &\iff [\forall x: (x\in A\wedge x\in C\to x\in A\wedge x\in B)]\wedge [\exists x:(x\in A\wedge x\in B\wedge (x\notin A\vee x\notin C)] \\&\iff [\forall x:(x\in A\to (x\in C\to x\in B))]\wedge [\exists x:(x\in A\wedge x\in B\wedge x\notin C)]\\ (A\cup C)\subset (A\cup B) &\iff [\forall x: (x\in A\vee x\in C\to x\in A\vee x\in B)]\wedge [\exists x:((x\in A\vee x\in B)\wedge (x\notin A\wedge x\notin C)] \\&\implies [\forall x:(x\notin A\to (x\in C\to x\in B))]\wedge [\exists x:(x\notin A\wedge x\in B\wedge x\notin C)]\\ \end{split}$

From $(A\cap C)\subset (A\cap B)$ we can infer that any thing in $A$ will be in $B$ if it is in $C$, but there is some thing that is in $A$ and in $B$ but not in $C$.

From $(A\cup C)\subset (A\cup B)$ we can infer that any thing not in $A$ will be in $B$ if it is in $C$, but there is some thing that is in $B$ but not in $C$ and not in $A$.

So from $(A\cap C)\subset (A\cap B)$ and $(A\cup C)\subset (A\cup B)$ together we can infer that ...

Answer 5

For providing a different viewpoint in a different style, here is a 'logical' proof that shows that even equivalence holds.$% \require{begingroup} \begingroup \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{\true}{\text{true}} \newcommand{\false}{\text{false}} \newcommand{\then}{\Rightarrow} \newcommand{\when}{\Leftarrow} \newcommand{\equiv}{\Leftrightarrow} %$

We calculate as follows:

$$\calc A \cap C \subset A \cap B \;\land\; A \cup C \subset A \cup B \op\equiv\hint{definitions of $\;\subset,\cap,\cup\;$} (\forall x)(x \in A \land x \in C \then x \in A \land x \in B) \\&\land\; (\forall x)(x \in A \lor x \in C \then x \in A \lor x \in B) \op\equiv\hints{logic: write $\;P \then Q\;$ as $\;\lnot P \lor Q\;$, and DeMorgan, twice}\hint{-- $\;\then\;$ is often more difficult to manipulate} (\forall x)(x \not\in A \lor x \not\in C \lor (x \in A \land x \in B)) \\&\land\; (\forall x)((x \not\in A \land x \not\in C) \lor x \in A \lor x \in B) \op\equiv\hints{logic: distribute $\;\lor\;$ over $\;\land\;$, and simplify }\hint{using $\;x \not\in A \lor x \in A \equiv \true\;$, twice} (\forall x)(x \not\in A \lor x \not\in C \lor x \in B) \\&\land\; (\forall x)(x \not\in C \lor x \in A \lor x \in B) \op\equiv\hint{logic: combine $\;\forall \land \forall\;$; extract common $\;x \not\in C \lor x \in B\;$} (\forall x)( (x \not\in A \land x \in A) \lor x \not\in C \lor x \in B ) \op\equiv\hint{logic: simplify using $\;x \not\in A \land x \in A \equiv \false\;$;} (\forall x)( x \not\in C \lor x \in B ) \op\equiv\hint{write $\;\lnot P \lor Q\;$ as $\;P \then Q\;$; definition of $\;\subset\;$} C \subset B \endcalc$$

This calculation may look a bit daunting. But note how, up to the last step, all we are doing is expanding the definitions, and using the laws of logic to simplify as much as possible.

So as least for me, this doesn't feel really as a proof, it is more a fairly straightforward calculation.

$% \endgroup %$