Can Basic Set Theory Explain Why an Element Belongs to a Set?

[vrble]

1. Suppose A \ B\subseteqC\capD and x\inA. Prove that if x \notinD then x\inB
2. None
3. Proof: Suppose A \ B\subseteqC\capD, x\inA, and x\notinD. It follows that our first assumption is equivalent to A due to our third assumption. Thus, B\subseteqC\capD is disjoint and either x\notinB\subseteqC or x\notinD. Let us temporarily assume that it is the case that x\notinB\subseteqC, then this may be expressed equivalently as x\inB and x\notinC, a contradiction with the definition of subsets, thus x must be an element of B and C provided x\notinDI'm not entirely sure if all of my reasoning is correct.

 

[Dick]

1. Suppose A \ B\subseteqC\capD and x\inA. Prove that if x \notinD then x\inB
2. None
3. Proof: Suppose A \ B\subseteqC\capD, x\inA, and x\notinD. It follows that our first assumption is equivalent to A due to our third assumption. Thus, B\subseteqC\capD is disjoint and either x\notinB\subseteqC or x\notinD. Let us temporarily assume that it is the case that x\notinB\subseteqC, then this may be expressed equivalently as x\inB and x\notinC, a contradiction with the definition of subsets, thus x must be an element of B and C provided x\notinDI'm not entirely sure if all of my reasoning is correct.

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?

 

[vrble]

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?

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.

 

[Dick]

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.

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?

 

[Mark44]

1. Suppose A \ B\subseteqC\capD and x\inA. Prove that if x \notinD then x\inB

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$.

 

[Dick]

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$.

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

 

[vrble]

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?

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?

 

[Dick]

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?

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.

 

[vela]

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?

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?

 

[vrble]

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?

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

 

[Dick]

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?

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.

 

[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.

 

[Dick]

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.

Yes, that works. Well done.