Is This a Valid Proof by Contradiction for Set Theory?

[pwhitey86]

Hi. I am new to formal proofs. Is the following a legitimate method for proving this assertion by contradiction.

Show A\cap B = \{\} \Leftrightarrow A \subseteq B^c

If A\cap B \neq \{\} then \exists \ x \ ST \ x \in A \ AND \ x \in B

Since x \in A \ \ \ A \subseteq B^c \Rightarrow x \in B^c

\Rightarrow x \in U \ AND \ x \notin B

This is a contradiction and thus no such x exists and therefore

A\cap B = \{\} \Leftarrow A \subseteq B^c

is this half the proof?

 

[Moo Of Doom]

Yes, that proof is valid, but it could be cleaned up a bit.

Either you should state that you are assuming A \subseteq B^c at the beginning of the proof, or simply directly show the contrapositive (which is what you've done - no contradiction there).

I would write it as follows:

Assume A \subseteq B^c.
Now suppose A\cap B \neq \{\}. Then there is an x such that x \in A and x \in B.
But, by our assumption, x \in A implies x \in B^c, which implies x \notin B. This is a contradiction, so our supposition must be in error. Therefore, A\cap B = \{\} \Leftarrow A \subseteq B^c

 

[fopc]

In your problem, I think the most economical proof is direct, and carried out through a chain of biconditionals.
Anytime you have a choice between direct proof and any of the indirect methods, the direct method should be taken (unless of course it turns into a nightmare).

 

[pwhitey86]

Here is a go at a direct proof:

A\cap B = \{\} \Leftrightarrow \forall x \in U \ \ x \notin A\cap B
\Leftrightarrow x \in (A\cap B)^c
\Leftrightarrow x \in A^c\cup B^c
Now suppose x \in A then x \in B^c and
\Leftrightarrow A \subseteq B^c

is this correct? is this what you meant by bidirectional fopc?

 

[fopc]

Here is a go at a direct proof:

A\cap B = \{\} \Leftrightarrow \forall x \in U \ \ x \notin A\cap B
\Leftrightarrow x \in (A\cap B)^c
\Leftrightarrow x \in A^c\cup B^c
Now suppose x \in A then x \in B^c and
\Leftrightarrow A \subseteq B^c

is this correct? is this what you meant by bidirectional fopc?

A complete chain of biconditionals in a proof makes the proof "bidirectional".

Remember these proofs are all about definition. Use the definitons immediately.

Below is an informal derivation that follows what I've tried to say about the importance of definitions.
Sorry about notation, but I haven't found time to learn tex stuff.

Let (x) denote "given any x in U", where U is domain of discussion. ~ denotes "not".
-> denotes "only if". ' denotes set complement. <-> denotes "if and only if".

[A intersect B = {}] <->
(x)[~(x in A and x in B)] <->
(x)[~(x in A) or ~(x in B)] <->
(x)[x in A -> ~(x in B)] <->
[A subset of B'].

Edit: (correction to poorly worded remarks)
Certainly, definitions are important and must be used, but equally important are the "identities" of the (presupposed) underlying logic.