# Thread: theorems of set theory

1. ## theorems of set theory

Prove by using elements prove:

A is a subset of B iff B' is a subset of A'

2. The proof of this is very, very simple.
$\displaystyle P \Rightarrow Q\,\text{ if and only if } \,\neg Q \Rightarrow \neg P$

3. ## Proof using elements

Hi -

A proof using elements will look something like this:

First, a reminder of the definition of a subset:

• A set P is a subset of a set Q if and only if every element of P is also an element of Q.

We need to prove A is a subset of B iff B' is a subset of A'.

• So let's assume first that A is a subset of B, and prove that B' is a subset of A'.

Choose an element x in B'. This means that x is not in B. In this case x can't be in A either, because, by definition of a subset if it were in A, then it would be in B. Now if x isn't an element of A, it is an element of A'.

We have just shown that whenever we choose an element x of B', it is also an element of A'. Therefore B' is a subset of A'.

This concludes the first half of the proof.

Now for the second half. We begin by saying:

• Let's assume that B' is a subset of A'; we now need to prove that A is a subset of B.

Choose an element x in A. This means that it's not in A'. So it can't be in B' either, because if it were it would be in A' (again because of the definition of a subset). Now if x isn't in B', it must be in B.

We have just shown that whenever we choose an element x of A, it is also an element of B. Therefore A is a subset of B.

That concludes the proof.

Hope that helps.