Prove $A \subseteq B \cap C$ if and only if $A \subseteq B$ and $A \subseteq C$

Question

Prove the following for any sets $A,B$ and $C$.

This is actually two sets that I'm trying the prove. The title character restriction wouldn't allow me to post both at the same time.

a. $A \subseteq B \cap C$ if and only if $A \subseteq B$ and $A \subseteq C$.

Definition 3.1.2 states that we should let A and B be sets. Then $A$ is a subset of $B$, $A \subseteq B$, and the statement $(\forall x)[x \in A \rightarrow \in B ]$ is true.

Proposition 3.1.4 states that $A, B$ and $C$ be sets. If $A \subseteq B$ and $B \subseteq C$, then $A \subseteq C$.

Edit: Proposition 3.1.4 isn't going to work at all.

Definition 3.2.1 states that we have to let A and B be sets.

The intersection of A and B, written as $A \cap B$ is the set $A \cap B$ = $[x: \in A \land x: \in B ]$

The union of A and B, written as $A \cup B$ is the set $A \cup B$ = $[x: \in A \lor x: \in B ]$

Given: P: $A \subseteq B \cap C$

$A$ is a subset of $B$ intersecting $C$

Q: $A \subseteq B$

A is a subset of B

R: $A \subseteq C$

$A$ is a subset of $C$

We have a bi-conditional statement.

1. If $A \subseteq B \cap C$ then $A \subseteq B$ and $A \subseteq C$

2. If $A \subseteq B$ and $A \subseteq C$ then $A \subseteq B \cap C$.

Edit:

1. If $A \subseteq B \cap C$ then $A \subseteq B$ and $A \subseteq C$

   Using Definition 3.2.1 for $A \subseteq B \cap C$ and Definition 3.1.2 $A \subseteq B$ and $A \subseteq C$, we get

$(\forall x)[x: x \in A \rightarrow x \in B \land x \in A \rightarrow x \in C]$

$(\forall x)[x: x \in A \rightarrow x \in B \land x \in C]$

$(\forall x)[x \in A \rightarrow x \in B]$

$(\forall x) [x \in A \rightarrow x \in C]$

1. For If $A \subseteq B$ and $A \subseteq C$ then $A \subseteq B \cap C$.

   Using Definition 3.1.2

for $A \subseteq B$ and $A \subseteq C$,

$(\forall x)[(x \in A \rightarrow x \in B)]$

$(\forall x)[(x \in A \rightarrow x \in C)]$

Also, by Definition 3.2.1

$(\forall x)[x : x \in A \rightarrow x \in B \land x \in C]$

$(\forall x)[ x \in A \rightarrow x \in B \land x \in A \rightarrow x \in C]$

---

b. $A \cup B \subseteq C$ if and only if $ A \subseteq C$ and $B \subseteq C$.

P:$A \cup B \subseteq C$

A unionized B is a subset of C

Q:$ A \subseteq C$

A is a subset of C

R:$B \subseteq C$

B is a subset of C

We have a bi-conditional statement.

1. If $A \cup B \subseteq C$, then $ A \subseteq C$ and $B \subseteq C$.

Using the union in Definition 3.2.1

$(\forall x)[ x \in A \rightarrow x \in C \rightarrow \lor x \in B \rightarrow x \in C]$

$(\forall x)[x \in A \lor x \in B \rightarrow x \in C$]

$(\forall x)[x \in A \rightarrow x \in C]$

$(\forall x) [x \in B \rightarrow x \in C]$

1. If $ A \subseteq C$ and $B \subseteq C$, then $A \cup B \subseteq C$.

Using Definition 3.1.2 for $ A \subseteq C$ and $B \subseteq C$

$(\forall x)[(x \in A \rightarrow x \in C)]$

$(\forall x)[(x \in B \rightarrow x \in C)]$

Then using Definition 3.2.1\

$(\forall x)[x \in A \lor x \in B \rightarrow x \in C$]

$(\forall x)[ x \in A \rightarrow x \in C \rightarrow \lor x \in B \rightarrow x \in C]$

Listing what is given to me is very easy. I even identified my P, Q, and R. The statements are in the form of $P \leftrightarrow Q \land R$

Edit: Truth tables won't work.

The problem is how do I go further with this proof?

Maybe after I find out which definition and proposition fits well to this problem, I have to use it to seek what the problem is looking for.

Answer 1

I will comment with a line-by-line approach, omitting superfluous comments (please, avoid too many words !) :

This is what we want to prove :

(a) $A \subseteq B \cap C$ if and only if $A \subseteq B$ and $A \subseteq C$

from Definition 3.1.2 --- $A \subseteq B$ is $(\forall x)[x \in A \rightarrow x \in B ]$.

from Definition 3.2.1 --- the intersection of $A$ and $B$, written as $A \cap B$, is the set $A \cap B := \{x: x \in A \land x \in B \}$

We have a bi-conditional statement; so, we need to prove two conditionals :

(a1) if $A \subseteq B \cap C$ then $A \subseteq B$ and $A \subseteq C$

(a2) if $A \subseteq B$ and $A \subseteq C$ then $A \subseteq B \cap C$.

Demonstration :

(a1)

If $A \subseteq B \cap C$ then $A \subseteq B$ and $A \subseteq C$

Using Definition 3.1.2 we have :

$\forall x ( x \in A \rightarrow x \in B \cap C )$

then, using Definition 3.2.1 and omitting the initial quantifier for brevity :

$( x \in A \rightarrow x \in B \land x \in C )$

$( x \in A \rightarrow x \in B ) \land ( x \in A \rightarrow x \in C )$

that is, using again Definition 3.1.2 :

$A \subseteq B$ and $A \subseteq C$

(a2)

If $A \subseteq B$ and $A \subseteq C$ then $A \subseteq B \cap C$.

Using the Definition 3.1.2 :

$(\forall x)(x \in A \rightarrow x \in B)$

$(\forall x)(x \in A \rightarrow x \in C)$

Omitting the initial quantifiers we have that :

$(x \in A \rightarrow x \in B) \land (x \in A \rightarrow x \in C)$

$x \in A \rightarrow ( x \in B \land x \in C)$

that is, by Definition 3.2.1 :

$x \in A \rightarrow ( x \in B \cap C)$

and finally, applying again Definition 3.1.2 :

$A \subseteq B \cap C$.

Added

Now for the second part.

(b) $A \cup B \subseteq C$ if and only if $ A \subseteq C$ and $B \subseteq C$.

We have a bi-conditional statement:

(b1)

If $A \cup B \subseteq C$, then $ A \subseteq C$ and $B \subseteq C$.

$( x \in A \cup B \rightarrow x \in C )$

but $A$ is a subset of $A \cup B$, so that :

$( x \in A \rightarrow x \in A \cup B)$

and, by transitivity of $\rightarrow$ :

$( x \in A \rightarrow x \in C )$ that is $A \subseteq C$;

the same with : $x \in B$, so that :

$( x \in B \rightarrow x \in C)$ that is $B \subseteq C$.

(b2)

If $ A \subseteq C$ and $B \subseteq C$, then $A \cup B \subseteq C$.

$(x \in A \rightarrow x \in C)$

$(x \in B \rightarrow x \in C)$

By definition of union :

$(x \in A \cup B \rightarrow (x \in A \lor x \in B) )$

this means that, if $x$ belongs to $A \cup B$, then $x$ belongs to $A$ or $x$ belongs to $B$; but in both cases $x$ belongs to $C$, because $A$ and $B$ are both subsets of $C$, so that :

$A \cup B \subseteq C$.

Answer 2

Element chasing, element chasing, element chasing. You are right in realizing that the truth table will do little for you. Since sets are uniquely determined by their elements, if you can show that an arbitrary element, say $x$ of one set is also in another you have shown set inclusion in one direction, show it in the other and you have equality. Since you do not need equality for this you just have to element chase in one direction (but you do still need to prove both directions in the biconditionals you have). Try translating the set notation into its boolean equivalent, e.g. $x\in A\cup B \iff (x\in A) \lor (x\in B)$.

For a): $(\implies)$ Let $x\in A$, then by the given condition, $x\in B\cap C$. How can you show $A\subseteq B$ and $A\subseteq C$ follow from this?

$(\impliedby)$ Suppose $A\subseteq B$ and $A\subseteq C$ and let $x\in A$. What follows from this?

For b): Let $x\in A\cup B$, can you show then that since $A\cup B\subseteq C$ that every element of $A$ (and $B$) is also in $C$? The converse?

Answer 3

I see that you have some difficulty at imagining those definition. A picture can help you very much.

Remember also that if

$$•\space A \subset B \implies \forall x\in A , x\in B$$

$$• \space A \subset B\cap C \implies \forall x \in A, x \in B \land x\in C$$

Answer 4

Here is how I would do this: starting at the most complex side we try to transform it into the other side, expanding the definitions, and simplifying.

This results in the following short and straightforward calculation: \begin{align} & A \subseteq B \;\land\; A \subseteq C \\ \equiv & \qquad \text{"definition of $\;\subseteq\;$, twice"} \\ & \langle \forall x : x \in A : x \in B \rangle \;\land\; \langle \forall x : x \in A : x \in C \rangle \\ \equiv & \qquad \text{"logic: $\;\forall\;$ distributes over $\;\land\;$ -- simplifying, bringing $\;B\;$ and $\;C\;$ closer"} \\ & \langle \forall x : x \in A : x \in B \;\land\; x \in C \rangle \\ \equiv & \qquad \text{"definition of $\;\cap\;$ -- this step is strongly suggested by our goal"} \\ & \langle \forall x : x \in A : x \in B \cap C \rangle \\ \equiv & \qquad \text{"definition of $\;\subseteq\;$"} \\ & A \subseteq B \cap C \\ \end{align} which proves the first statement (from the title).

Similarly, for the second statement \begin{align} & A \subseteq C \;\land\; A \subseteq C \\ \equiv & \qquad \text{"definition of $\;\subseteq\;$, twice"} \\ & \langle \forall x : x \in A : x \in C \rangle \;\land\; \langle \forall x : x \in B : x \in C \rangle \\ \equiv & \qquad \text{"logic: merge the ranges of two quantifications"} \\ & \langle \forall x : x \in A \;\lor\; x \in B : x \in C \rangle \\ \equiv & \qquad \text{"definition of $\;\cup\;$"} \\ & \langle \forall x : x \in A \cup B : x \in C \rangle \\ \equiv & \qquad \text{"definition of $\;\subseteq\;$"} \\ & A \cup B \subseteq C \\ \end{align} which completes the proof.