7
$\begingroup$

Let $A$, $B$, $C$ be sets. Prove that if $A \subseteq C$ and $B \subseteq C$ then $A \cup B \subseteq C$.

This is an exercise in mathematical logic.

My attempt to progress forward: This statement can be written as$$ (A \subseteq C) \land (B \subseteq C) → A \cup B \subseteq C\\ (x \in A → x \in C) \land (x \in B → x \in C) → A \cup B \subseteq C $$ But I am not even sure that is how I am supposed to do it so I am a bit stuck. Can anyone explain to me how to get through this proof? Thanks in advance.

$\endgroup$
  • $\begingroup$ ... intuitively it's obvious, right? ... $\endgroup$ – user202729 Sep 26 '18 at 15:32
  • 2
    $\begingroup$ @user202729 Intuitively many things are obvious, but proving them is another matter... ;) ex. A sphere bounds a given volume with minimal area... $\endgroup$ – Quintec Sep 27 '18 at 1:14
26
$\begingroup$

Take any $x\in A\cup B$. That means either $x\in A$ or $x\in B$. Anyway you get $x\in C$.

$\endgroup$
14
$\begingroup$

This answer is expanding a bit on the other answers to give a widely applicable outline on how to prove mathematical statements in general.
The final proof will be equal to Mark's answer, but hopefully this answer sheds a bit of light on what is actually going on in the thought process, at least I like to think in the terms defined below while I am proving.

In general you need a "proof calculus" which states how proofs can be constructed and which ones are valid. Unless you are doing logic and proof theory itself, in most settings in maths you are well off using the natural deduction proof calculus for first-order logic. In short — cut in light of this question:

  • To prove $\varphi \land \psi$, prove $\varphi$ and $\psi$ separately.
  • To prove $\varphi \lor \psi$, give a proof for $\varphi$ or alternatively for $\psi$. One proof for either $\varphi$ or $\psi$ is already sufficient.
  • To prove $\varphi → \psi$, assume $\varphi$ and prove $\psi$ under this assumption.

    The implication captures the notion of "if we have $\varphi$ and $\varphi → \psi$ established somewhere, then we can conclude $\psi$." Most, if not all, theorems can be seen as implications: if you fulfill the requirements, then you can use its consequences.
    Hence it makes sense to be allowed to assume $\varphi$ in the proof of $\varphi → \psi$.
  • To prove $\forall x. \varphi(x)$ ($\varphi$ may depend on $x$), introduce a fresh variable not used before (e.g. $c$) and prove $\varphi(c)$ (i.e. every occurrence of $x$ is filled with $c$).

    Introduction of a fresh variable is required to guarantee that your proof of $\varphi(c)$ does not depend on any previous assumptions on $x$. Hence, having proved $\varphi(c)$ really amounts to having proved the proposition $\varphi(x)$ for every possible $x$.

Now consider your statement:

$$\left((x \in A → x \in C) \land (x \in B → x \in C)\right) → A \cup B \subseteq C$$

You already did a good job translating it to more formal language! But we can even go a step further. Actually what the above line means is the following: $$\left((\forall x. x \in A → x \in C) \land (\forall x. x \in B → x \in C)\right) → (\forall x. x \in A \cup B → x \in C)$$

On the top level, we have a $\varphi → \psi$-kinded expression. Applying the corresponding rule, we begin with

(1) Assume $(\forall x. x \in A → x \in C) \land (\forall x. x \in B → x \in C)$.

Our proof goal, as stateted in the rule, is now the right side $$(\forall x. x \in A \cup B → x \in C).$$ This is of kind $\forall x. \varphi(x)$ with $\varphi(x) := x \in A \cup B → x \in C$. So,

(2) Let $y$ be a fresh variable.

I called it $y$ to avoid confusion with the set $C$. When one defines freshness more formally, one sees that $x$ would have worked as well as a fresh variable.
Now we have to show $\varphi(y)$, which is $y \in A \cup B → y \in C$. Again, apply the $→$ rule from above:

(3) Assume $y \in A \cup B$.

Our final proof goal is now: $y \in C$. This can be proved by case-by-case analysis:

(4) We know that $y$ is in $A$ or $B$. In the first case, $y \in A$ and per line (1) we especially know $y \in A → y \in C$. Since we have $y \in A$ just established, we can conclude $y \in C$. Case finished. The next and last case is $y \in B$ which works analogously.

$\endgroup$
12
$\begingroup$

If $A \subset C$, and $B \subset C$;

$A \cap C =A$; and $B \cap C = B$;

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

$C \cap (A \cup B) \subset C$

$\endgroup$
2
$\begingroup$

I haven't noticed one in the in the answers, so here's a proof by contradiction.

The statement we wish to prove is: $$(\forall x)(x \in A \cup B \implies x \in C) \tag{1} $$

It's negation is:

$$ (\exists x)(x \in {A} \cup {B} \wedge \neg(x \in C) ) \tag{2} $$ $$ x \in A \cup B \implies (x \in A \vee x \in B)$$ $$ x \in A \wedge A \subseteq C \implies x \in C \tag{3} $$ $$ or$$ $$ x \in B \wedge B \subseteq C \implies x \in C \tag{4} $$ Since both $(3)$ and $(4)$ are in contradiction with $(2)$, it must be false. Therefore our starting premise $(1)$ is correct.

$\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.