Is This a Valid Proof by Contradiction for Set Theory?

  • Thread starter Thread starter pwhitey86
  • Start date Start date
  • Tags Tags
    Proof
AI Thread Summary
The discussion revolves around the validity of a proof by contradiction for the assertion A ∩ B = ∅ if and only if A ⊆ B^c. The initial proof attempt correctly identifies a contradiction but lacks clarity in presentation. Suggestions include explicitly stating the assumption at the beginning or directly showing the contrapositive. A more streamlined direct proof using biconditionals is proposed, emphasizing the importance of definitions in formal proofs. The consensus is that while the original proof is valid, it can be improved for clarity and efficiency.
pwhitey86
Messages
5
Reaction score
0
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?
 
Physics news on Phys.org
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
 
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).
 
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?
 
pwhitey86 said:
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.
 
Last edited:
I was reading documentation about the soundness and completeness of logic formal systems. Consider the following $$\vdash_S \phi$$ where ##S## is the proof-system making part the formal system and ##\phi## is a wff (well formed formula) of the formal language. Note the blank on left of the turnstile symbol ##\vdash_S##, as far as I can tell it actually represents the empty set. So what does it mean ? I guess it actually means ##\phi## is a theorem of the formal system, i.e. there is a...

Similar threads

Back
Top