0

Prove the following theorem by direct proof.

Theorem: For all sets $A, B,$ and $C$, if $A ∩ C ⊆ B ∩ C$ and $A ∪ C ⊆ B ∪ C,$ then $A ⊆ B$.

Asaf Karagila
  • 393,674
Bengü ı
  • 1
  • 1
    What have you tried? – Riemann'sPointyNose Apr 13 '21 at 22:57
  • I do not have much information but I tried decomposing assumptions and found nothing – Bengü ı Apr 13 '21 at 22:58
  • Use a Venn (or Karnaugh) diagram. – Jean Marie Apr 13 '21 at 23:02
  • Suppose $a \in A$. There are two possibilities: either $a \in C$ also or $a \notin C$. Examine each case separately and what do you find? – butter-imbiber Apr 13 '21 at 23:03
  • I do not think we are allowed to use venn – Bengü ı Apr 13 '21 at 23:03
  • 2
    Let's see. You are given that $A\subseteq B\cup C$ and $A\cap C\subseteq B$. You have to show that $A\subseteq B$, i.e., assuming $x\in A$, you have to show that $x\in B$. Consider two cases: $x\in C$ or $x\notin C$ . . . – bof Apr 13 '21 at 23:04
  • First, you should try element chasing, and let us know where you get stuck. Second, I believe you only need the one portion of the hypothesis. – Pavan C. Apr 13 '21 at 23:06
  • If I take two cases I can find the solution thanks a lot but how did we choose these cases can you explain? – Bengü ı Apr 13 '21 at 23:07
  • Here's a really cool way you can show this. Define statements $p,q,r$ by $$p:x\in A$$ $$q:x\in B$$ $$r:x\in C$$ Now use a truth table to show that the compound statement $$\Bigg(\Big[(p \lor r) \implies (q \lor r)\Big] \land \Big[(p \land r) \implies (q \land r)\Big]\Bigg) \implies \Big(p \implies q\Big)$$ is a tautology. – Matthew H. Apr 13 '21 at 23:20
  • You actually could do it without needing to come up with an instance of excluded middle to use to split into cases: if $x \in A$, then $x \in A \cup C$, so $x \in B \cup C$. Now from there, it's natural to split into cases $x \in B$ (in which case you already have what you wanted) or $x \in C$ (which case you say you've done). – Daniel Schepler Apr 13 '21 at 23:22
  • Thanks a lot I learned a lot from you guys – Bengü ı Apr 13 '21 at 23:25

0 Answers0