How do you prove things with null

  • Thread starter Thread starter pwhitey86
  • Start date Start date
AI Thread Summary
The discussion focuses on proving that the intersection of sets A and (B-A) is empty, expressed as A ∩ (B-A) = ∅. The initial proof attempts to show that if an element x is in A, it cannot be in (B-A), leading to the conclusion that A ∩ (B-A) is empty. However, a crucial point is raised about considering elements not in A, which is necessary for a complete proof. The argument concludes that since no element can simultaneously belong to both A and (B-A), the intersection must indeed be empty. This reinforces the importance of addressing all cases in formal proofs.
pwhitey86
Messages
5
Reaction score
0
For instance, the following seems obvious but I don't know how to state the proof formally (and directly):

Show A \cap (B-A) = \{\}

Here is a try:
For any x \in U \ if \ x \in A then x \notin (B-A)
therefore A \cap (B-A) = \{\}

there is something missing...
 
Physics news on Phys.org
Well, by definition (of set exclusion),
x \in B-A \leftrightarrow x \in B \wedge x \notin A
Also by definition (of set intersection),
x \in A \cap (B-A) \leftrightarrow x \in A \wedge x\in B-A
Substituting the first statement into the second, you get
x \in A \cap (B-A) \leftrightarrow x \in A \wedge x \in B \wedge x \notin A
But the RHS is clearly false (x is not simultaneously in A and not in A), meaning that the LHS is also false. Therefore, for all x,
x \notin A \cap (B-A)

Therefore, A \cap (B-A) satisfies the defining property of the empty set.
 
pwhitey86 said:
For instance, the following seems obvious but I don't know how to state the proof formally (and directly):

Show A \cap (B-A) = \{\}

Here is a try:
For any x \in U \ if \ x \in A then x \notin (B-A)
therefore A \cap (B-A) = \{\}

there is something missing...
You have shown that if x is in A then it is not in A \cap (B-A) What if x is not in A? That's what's missing. (Yes, it's trivial but you should say it.)
 
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...
Back
Top