Math Help - Proof (A-B)'=B'-A'

1. Proof (A-B)'=B'-A'

I want to prove or disprove (A-B)'=B'-A'.
So, let x be an element of (A-B)'
Then x is not an element of A-B

This is where I get confused...
Do I say x is an element of A', x is an element of -B'?

2. Originally Posted by kathrynmath
I want to prove or disprove (A-B)'=B'-A'.
So, let x be an element of (A-B)'
Then x is not an element of A-B

This is where I get confused...
Do I say x is an element of A', x is an element of -B'?

I F xε(A-B) <====> xεA & ~xεB.

Hence ~xε(A-B) <======> ~(xεA & ~xεB) <=====> ~xεA v xεB BY de morgan. WHICH is equivalent to xεA====> xεB

3. Originally Posted by poutsos.B
I F xε(A-B) <====> xεA & ~xεB.

Hence ~xε(A-B) <======> ~(xεA & ~xεB) <=====> ~xεA v xεB BY de morgan. WHICH is equivalent to xεA====> xεB
Is there a way to do this proof without the ~? I don't know but that's making it harder for me. So, is this a contradiction? I did it by venn diagrams and it wasn't equal.

4. Originally Posted by kathrynmath
Is there a way to do this proof without the ~? I don't know but that's making it harder for me. So, is this a contradiction? I did it by venn diagrams and it wasn't equal.
I agree that that is not very helpful!
Mathematicians usually hate such proofs done with logic.
You ought to know that the statement is formal false.

Counterexample:
$\begin{gathered}
U = \left\{ {1,2,3,4,5} \right\},\,A = \left\{ {1,3,4,5} \right\}\,\& \,B = \left\{ {2,3,5} \right\} \hfill \\
\left( {A\backslash B} \right)^\prime = \left( {\left\{ {1,4} \right\}} \right)^\prime = \left\{ {2,3,5} \right\} \hfill \\
B'\backslash A' = B' \cap A = \left\{ {1,4} \right\} \hfill \\
\end{gathered}$

BTW: We use this $\left( {A - B} \right) = \left( {A\backslash B} \right)$ it is called "setminus".

5. Originally Posted by Plato
I agree that that is not very helpful!
Mathematicians usually hate such proofs done with logic.
You ought to know that the statement is formal false.

Counterexample:
$\begin{gathered}
U = \left\{ {1,2,3,4,5} \right\},\,A = \left\{ {1,3,4,5} \right\}\,\& \,B = \left\{ {2,3,5} \right\} \hfill \\
\left( {A\backslash B} \right)^\prime = \left( {\left\{ {1,4} \right\}} \right)^\prime = \left\{ {2,3,5} \right\} \hfill \\
B'\backslash A' = B' \cap A = \left\{ {1,4} \right\} \hfill \\
\end{gathered}$

BTW: We use this $\left( {A - B} \right) = \left( {A\backslash B} \right)$ it is called "setminus".
Ok, that helps a little more, but I'm trying to do a formal proof without numbers. I'm trying to figure out what to say if I let x be an elemnt of (A-B)'. This is the correct way to start, right?

6. Originally Posted by kathrynmath
Ok, that helps a little more, but I'm trying to do a formal proof without numbers. I'm trying to figure out what to say if I let x be an elemnt of (A-B)'. This is the correct way to start, right?
if I say x is an element of (A-B)', could I saw x is an elemnt of B becuase x is an element of not (A-B), so x must be an element of B. Am I on the right track?

7. Originally Posted by kathrynmath
Ok, that helps a little more, but I'm trying to do a formal proof without numbers.
That is impossible!
One cannot do a formal proof of a false statement (not in mathematics anyway).
All we do is give a counterexample in the statement is shown to be false.

8. Originally Posted by Plato
That is impossible!
One cannot do a formal proof of a false statement (not in mathematics anyway).
All we do is give a counterexample in the statement is shown to be false.
can't you do a formal proof and show that it equals something else, thus a contradiction?

9. You need to have a sit down with a live tutor and discuss your confusion about proofs. When it says, “prove or disprove”, you are to give a formal proof if it is a true statement or give a counterexample if it is false.

10. That's just how my teacher taught us.

11. Originally Posted by kathrynmath
That's just how my teacher taught us.
i assure you, that is not what your teacher taught. as Plato said, to disprove something, all you have to do is give a counter-example. if you can find one instance where a claim is false, then the claim is considered false in general. anything else is just giving yourself ideas as to why something might be false. as you said, you drew Venn Diagrams and found that the claim might not be true. so then you know you should start looking for a counter-example. you could also notice that the left hand side, using the defintion of set minus and DeMorgan's laws, simplifies to $\neg A \cup B$, which is not equal to the other side.

these are not proofs that the claim is false, however, to disprove something, you must give a counter example

12. Originally Posted by kathrynmath
That's just how my teacher taught us.
What does "how" mean?
I do not follow what this response means.
Are you saying that your teacher thinks that there is a formal proof for a false statement?
It is a very say fact that many mathematics teachers are not really train in mathematics.

13. Originally Posted by kathrynmath
Ok, that helps a little more, but I'm trying to do a formal proof without numbers. I'm trying to figure out what to say if I let x be an elemnt of (A-B)'. This is the correct way to start, right?

To have that (A-B)' IS equal to B'-A' THIS must hold for all A AND B.

However if this equality does not hold then there must be an A or B or both such that :

(A-B)' IS not equal to B'-A' AND Plato already gave you an example.

Perhaps an example not using Nos is the following:

Let B= Φ ( the empty set), and if substitute Φ ΙΝ (Α-Β)' we have:

( A-Φ)'= (A)'= A' BECAUSE A-Φ=Α.Αnd substituting Φ in B'-A' we have:

Φ'-A' = U- A' =A BECAUSE Φ'=U WHERE U is the set of which A, B are subsets.

Hence we have A'= A NOT true.

But we can give a proof in propositional calculus without using a counter example by the following procedure:

Let xε( A-B)' <===> ~xεΑ v xεB as it was shown

Let xε(B'-A') <===> ~xεB & ~xεA' <====> ~xεB & xεA.

Now put xεA=p and xεB=q. So if we want (A-B)' = B'-A' W must have ,by the axiom of extensionality :

xε(A-B)' <====> xε(B'-A') or ~xεΑ v xεB <=====>~xεB & xεA or

~p v q <=====> p & ~q which means that ~p vq logicaly implies p & ~q and p & ~q logicaly implies ~p v q,which means that ;

The conditional ~p v q ------> p & ~q must be a tautology and,

The conditional p & ~q ------->~p v q must also be a tautology.

Now by forming the true tables of the above we see that none of the above is a tautology.

Now by a theorem in propositional logic that states:

A formula is a theorem ( hence provable ) of the propositional logic if and only if it is a tautology.

And the fact that the above two conditionals are not tautologies we conclude:

~p v q <=====> p & ~q is not provable ,hence xε(A-B)' <====> xε(B'-A') is not provable and ,

(A-B)' Is not equal to B'-A'

Note ~xεΑ x does not belong to A, AND ~p means not p

14. Originally Posted by poutsos.B
To have that (A-B)' IS equal to B'-A' THIS must hold for all A AND B.

However if this equality does not hold then there must be an A or B or both such that :Let B= Φ ( the empty set), and if substitute Φ ΙΝ (Α-Β)' we have:
( A-Φ)'= (A)'= A' BECAUSE A-Φ=Α.Αnd substituting Φ in B'-A' we have:
Φ'-A' = U- A' =A BECAUSE Φ'=U WHERE U is the set of which A, B are subsets.
Hence we have A'= A NOT true.
But we can give a proof in propositional calculus without using a counter example by the following procedure:
Let xε( A-B)' <===> ~xεΑ v xεB as it was shown
Let xε(B'-A') <===> ~xεB & ~xεA' <====> ~xεB & xεA.
Now put xεA=p and xεB=q. So if we want (A-B)' = B'-A' W must have ,by the axiom of extensionality :
xε(A-B)' <====> xε(B'-A') or ~xεΑ v xεB <=====>~xεB & xεA or
~p v q <=====> p & ~q which means that ~p vq logicaly implies p & ~q and p & ~q logicaly implies ~p v q,which means that ;
The conditional ~p v q ------> p & ~q must be a tautology and,
The conditional p & ~q ------->~p v q must also be a tautology.
Now by forming the true tables of the above we see that none of the above is a tautology.
Now by a theorem in propositional logic that states:
A formula is a theorem ( hence provable ) of the propositional logic if and only if it is a tautology.
And the fact that the above two conditionals are not tautologies we conclude:
~p v q <=====> p & ~q is not provable ,hence xε(A-B)' <====> xε(B'-A') is not provable and ,
(A-B)' Is not equal to B'-A'
Note ~xεΑ x does not belong to A, AND ~p means not p
All of that is truly preposterous. Only a logician could have produced that.
For a mathematical statement it is totally meaningless.
I think that is a perfect example why “Symbolic Logic” is dieing as a separate subject.
The American Symbolic Logic Society meets at the joint meeting of the American Mathematical Society and The Mathematical Association of America. Over the last thirty years I have tried to attend sessions of the Logical Association, but lately the average session has no more that five in attendance