# Proof or disproof the following

• Apr 2nd 2011, 05:35 AM
gordo151091
Proof or disproof the following
I have been asigned this problem in class.

$\displaystyle C\subseteq A \Rightarrow (A \cup B) \cap C \subseteq A$

Can you aid me in how should i start. I thought of puting it in terms of propositional logic, then proving it. The propositional logic equivalent I came up with

$\displaystyle (C \Rightarrow A) \Rightarrow (A \vee B) \wedge (C \Rightarrow A )$

Is this correct?
• Apr 2nd 2011, 06:04 AM
Plato
Quote:

Originally Posted by gordo151091
I have been asigned this problem in class.
$\displaystyle C\subseteq A \Rightarrow (A \cup B) \cap C \subseteq A$

For any two sets $\displaystyle C~\&~B$ it is true that $\displaystyle B\cap C\subseteq C$.
What is there to prove then?
• Apr 2nd 2011, 06:10 AM
DrSteve
Quote:

Originally Posted by gordo151091
I have been asigned this problem in class.

$\displaystyle C\subseteq A \Rightarrow (A \cup B) \cap C \subseteq A$

Can you aid me in how should i start. I thought of puting it in terms of propositional logic, then proving it. The propositional logic equivalent I came up with

$\displaystyle (C \Rightarrow A) \Rightarrow (A \vee B) \wedge (C \Rightarrow A )$

Is this correct?

Let $\displaystyle x\in (A \cup B) \cap C$. Then $\displaystyle x\in C$. Since $\displaystyle C\subseteq A$, $\displaystyle x\in A$. Since $\displaystyle x$ was arbitrary, $\displaystyle (A \cup B) \cap C \subseteq A$.
• Apr 3rd 2011, 12:56 PM
gordo151091
Which reason o inference rule do i use here, i know that if $\displaystyle x \in A$ and $\displaystyle x \in C$ and $\displaystyle x \in (A \cup B) \cap C$ then $\displaystyle (A \cup B) \cap C \subseteq A$, but i dont know the reason that allows me to do this.
• Apr 3rd 2011, 01:03 PM
Plato
Quote:

Originally Posted by gordo151091
Which reason o inference rule do i use here, i know that if $\displaystyle x \in A$ and $\displaystyle x \in C$ and $\displaystyle x \in (A \cup B) \cap C$ then $\displaystyle (A \cup B) \cap C \subseteq A$, but i dont know the reason that allows me to do this.

Now you should that we have no way in the world to know what inference rules you are using much less what they might be called.
Prove that $\displaystyle A\cap C\subseteq C$.
Then there is nothing more to prove to have then $\displaystyle (A \cup B) \cap C \subseteq A$.