Prove that (A ∩ B) ⊆ A, when A and B are sets.

Question

I've learnt that in order to prove that X is a subset of Y, you have to show that if $x$ is an element of X, $x$ is also an element of Y. I am stuck on how to elegantly show that if $x$ is an element of (A ∩ B), it is also an element of A.

This is what I have come up with until now:

$ x \in (A \cap B) \equiv x \in A \wedge x \in B $

For $ x \in A \wedge x \in B $ to be true, $ x \in A $ has to be true as well.

Therefore, $ x \in (A \cap B) \implies x \in A $

Answer 1

You are right! Straight-forward, direct from definition proof!

Sometimes, when we talk about this "advanced" mathematical subjects, we expect proofs to be long, complex and perhaps even tedious. When facts can be proven in such a simple way, we have the feeling that we may be missing some detail.

However, if you think about it, the fact you are trying to prove is "obvious", not only from a set theory perspective, but even from the underlying logical one (if both conditions A and B are verified, then contidion A is verified) Simple facts should be easy to proof!

With experience, you will learn that it's precisely the other way around. What should bring you towards suspicion is long, complicated proofs for conclusions that are "clearly true" from the premises.

As an exercise to gain confidence, can you proof $(A \cap B) \subseteq (A \cup B)$ with a similar from scratch one-liner? And can you proof it in a slightly different way, taking the result you've just proven as a starting point?

Answer 2

Since set inclusion is defined via a conditional statement (universally quantified) what is to be proved here is a conditional.

In order to prove a conditional, one has to use the " conditional proof rule" which can be stated as follows : suppose that H is true; derive , under this hypothesis the conclusion C; infer from this that : H implies C, that is, that : H ---> C is true.

( This rule relies on the parallelism between syntax and semantics : saying that a conditional is valid, true, is equivalent to saying that the conclision is derivable froim the antecedent).

So, let's consider an arbitrary object x. And let's suppose that x belongs to the set " A Inter B".

This hypothesis means that : x belongs to A AND x belongs to B ( in virtue of the definition of " intersection" in set theory).

But, there is a rule of inference called " & elimination" that says : from (X & Y), infer X.

So, the &-elimination rule allows us to infer x belongs to A from : x belongs to A AND x belongs to B.

Let's then infer : x belongs to A.

Since we have derived x belongs to A from x belongs to A AND x belongs to B , the " conditional proof rule" allows us infer that the whole conditional :

      x belongs to A Inter B --> x belongs to A 

is true.

Since the object x was arbitrary, we are allowed to generalize and to say :

     for all x , (x belongs to A Inter B --> x belongs to A). 

But we recognize here the definition of set inclusion. So let us conclude :

      The set A Inter B is included in the set A. 

Note : the consequent of the conditional has been derived hypothetically, but the whole conditional itself holds categorically ( or absolutely).