1. Oct 20, 2015

### Master0fN0thing

1. The problem statement, all variables and given/known data
Give an element-wise proof for the following: If A⊆B and B⊆C', then A ∩ C = ∅

2. Relevant equations
A is a subset of B (written A ⊆ B) if every element in the set A is also an element in the set B. Formally, this means that fore every x, if x ∈ A, then x ∈ B.
A ∩ B = { x ∈ U : x ∈ A and x ∈ B }.
A set that contains no elements is called an empty set, and is denoted by { } or ∅.
A is equal to B (simply written A = B) means that A and B have exactly the same members. This is expressed formally by saying, “A ⊆ B and B ⊆ A.”

3. The attempt at a solution
Because there is an equal sign in the "then" statement, I know I have to show two case if each side being a subset of the other. So here is what I have so far...

Proof:
Let U be the universe that contain the sets A, B, and C. Let A and B be subsets of U such that A ⊆ B and let B and C' be subsets such that B ⊆ C'.

Case 1:
We will show that A ∩ C = ∅. Let x ∈ A ∩ C. Then x∈U, x∈A, and x∈C. Since x∈A, it follows that x∈B by our hypothesis. Also by our hypothesis, since x∈B, x∈C'. Since x∈C, and x∈C', ....

and this is where I'm getting lost. How do I go proving from here its the empty set? At this point isn't this saying that x is every element? Or am I thinking about this totally wrong?

2. Oct 20, 2015

### nuuskur

What you have is $A\subseteq B \land B\subseteq C'$, assuming $X'$ means complement of set $X$. You have shown that $..x\in C\land x\in C'...$, by definition of complement, such a situation can never occur, therefore ...? You can convert your initial formula to something that only consists of conjuctions. If there is an identically false "sub-conjunction", then the entire conjunction is identically false.
If you haven't learnt discrete math, yet, disregard what I said about converting things.

You have the right idea, a matter of analyzing the information you have gathered.