# Proof involving basic set theory

1. Apr 22, 2014

### vrble

1. Suppose A \ B$\subseteq$C$\cap$D and x$\in$A. Prove that if x $\notin$D then x$\in$B

2. None

3. Proof: Suppose A \ B$\subseteq$C$\cap$D, x$\in$A, and x$\notin$D. It follows that our first assumption is equivalent to A due to our third assumption. Thus, B$\subseteq$C$\cap$D is disjoint and either x$\notin$B$\subseteq$C or x$\notin$D. Let us temporarily assume that it is the case that x$\notin$B$\subseteq$C, then this may be expressed equivalently as x$\in$B and x$\notin$C, a contradiction with the definition of subsets, thus x must be an element of B and C provided x$\notin$D

I'm not entirely sure if all of my reasoning is correct.

Last edited by a moderator: Apr 22, 2014
2. Apr 22, 2014

### Dick

Yes, the reasoning is rubbish and it's not even very grammatical. I think the easiest way to prove this is to assume that given x is in A and x is NOT in D, assume that x is NOT in B. Can you show that leads to a contradiction? That's something like what you were doing, but could you express it more clearly?

Last edited by a moderator: Apr 22, 2014
3. Apr 23, 2014

### vrble

Thank you for your response, I thought that would be the case. The set of exercises this problem comes from are specifically of the form, "If P, then Q. Assume P then prove Q." so I'd prefer to stick to that method of attack. Could you point out some of the things that are incorrect about my reasoning? That would be extremely helpful. I'll attempt to express the proof more clearly after I get a bit of sleep.

4. Apr 23, 2014

### Dick

Let's start with the first sentence. "It follows that our first assumption is equivalent to A due to our third assumption." What does that mean?

And let's stick with the indirect proof for just a bit. Can you show that if you assume that given x is in A and x is NOT in D and x is NOT in B, then x is in A\B and x is not in C∩D?

Last edited: Apr 23, 2014
5. Apr 23, 2014

### Staff: Mentor

Is there a mistake in the problem statement? It seems to me that the last statement should be $x \in C$, not $x \in B$.

6. Apr 23, 2014

### Dick

That wouldn't be true. Pick A={1,2,3}, B={2,3}, C={1,2}, D={1}. Now pick x=3.

Last edited: Apr 23, 2014
7. Apr 24, 2014

### vrble

I believe that first sentence is a result of my confusion between free and bound variables while examing the definition of intersections. I thought of it as, "For all x, x is in C and x is in D. x is not in D. Therefore, there is not an x such that x is in C and x is in D." Then that lead me to the conclusion that C intersect D is equal to the null set. Also, assuming x was not in D then wouldn't x not be present in the intersection set as well as B due to B being a subset of C intersect D?

Last edited: Apr 24, 2014
8. Apr 24, 2014

### Dick

I don't understand why you think those things. Why do you think A is a subset of C intersect D? A\B is. Not A. Pick some example sets like I did before.

Last edited: Apr 24, 2014
9. Apr 24, 2014

### vela

Staff Emeritus
Are you misreading the problem statement? The first assumption says that the set $A\backslash B$ is a subset of $C\cap D$. It sounds like you're somehow parsing the expression as $A \backslash (B \subset C \cap D)$ (whatever that's supposed to mean) otherwise why do you think B is a subset of the intersection of C and D?

10. Apr 24, 2014

### vrble

That is exactly what I did, thank you so much. Will post new proof shortly.

Last edited: Apr 24, 2014
11. Apr 24, 2014

### Dick

Well that's perceptive. I never would have thought of reading it that way, since it's wrong. That does explain a lot of strange notions.

12. Apr 24, 2014

### vrble

Theorem: Suppose that $A\backslash B$ is a subset of $C\cap D$, and x is an element of $\large A$. If x is not an element of $\large D$, then x is an element of $\large B$

Proof:
Suppose that $A\backslash B$ is a subset of $C\cap D$, x is an element of $\large A$, and x is not an element of $\large D$. By our assumptions, x is not an element of $C\cap D$ by definition. Thus, x must not be an element of $A\backslash B$ and, in this case, occurs when x is an element of $\large A$ as well as $\large B$. We assume x is an element of $\large A$ so it must be the case that x is an element of $\large B$ provided x is not an element of $\large D$. Therefore, If x is not an element of $\large D$, then x is an element of $\large B$ as was to be proved.

13. Apr 24, 2014

### Dick

Yes, that works. Well done.