2
$\begingroup$

For proving vacuous truths for empty sets, Halmos in his Naive Set Theory mentions that

To prove that something is true about the empty set, prove that it cannot be false.

But now consider Russell's paradox where $A$ is the set of all sets not contained in it. $A \notin A$ being false there doesn't imply that $A\in A$.

So how does Halmos' method work?

$\endgroup$
1
  • $\begingroup$ It can be something, what we don't know yet $\endgroup$ – Dr. Sonnhard Graubner Jun 9 '19 at 14:32
4
$\begingroup$

I don't know what point you're trying to make about Russell's paradox, but all Halmos is doing is reminding you to try proof by contradiction. Answering your title question with "yes" is equivalent to asserting the law of the excluded middle, which is assumed in classical logic. If you had instead asked, "If something is not true, is it false?", an answer if "yes" would be equivalent to the law of non-contradiction. This law, which Halmos wants you to use, applies even in some non-classical logics (it fails in paraconsistent logics).

$\endgroup$
2
  • $\begingroup$ Good answer! What is paraconsistent logic? $\endgroup$ – manooooh Jun 9 '19 at 15:01
  • 1
    $\begingroup$ @manooooh As explained here, such logics don't require a contradiction to imply all statements. $\endgroup$ – J.G. Jun 9 '19 at 15:15
2
$\begingroup$

In classical logic, if something is not false, it is true.

Russell's paradox is resolved by noticing that in ZF, $A$ by your definition is not a set and thus not contradiction arises.

I don't see why you're bringing in Russell's paradox into the example statement given -- the statement talks about vacuous truths for empty sets (I'm assuming truths such as $\forall x\in\phi,P(x)$ for any predicate $P$ type thing).

$\endgroup$
0
$\begingroup$

Russell's Paradox did not call into question the Law of the Excluded Middle. In the early 1900's, it called into question an early axiomatization of Cantor's set theory by G. Frege. These axioms were shown to be inconsistent in that it was possible, using Frege's axioms, to both prove and disprove that there exists a set of those and only those sets that are not elements of themselves.

$$\exists k: \forall a: [a\in k \iff a\notin a] \land \neg\exists k: \forall a: [a\in k \iff a\notin a]$$

Various patches were put forward to make it impossible to derive this contradiction, the most popular solution being the Zermelo-Fraenkel Axioms of Set Theory. They, too, are based on classical logic including the Law of the Exclude Middle.

Note that, by using the ordinary rules of logic (including LEM) and any binary predicate $R$ (not just $\in$) we still have

$$\neg\exists: k:\forall a:[R(a,k) \iff\neg R(a,a)]$$

No contradications arise here.

$\endgroup$
-1
$\begingroup$

Russell's paradox is a pathology that arises because the definition of "set" is too vague in traditional set theory. That is, the problem is with the "definition" of $A$ as "the set of all sets that don't contain themselves" and furthermore assuming that the symbols "$A\in A$" and "$A \not\in A$" can be interpreted with the same semantics as usual for this specific object $A$.

This is different than the law of the excluded middle, which is the principle in classical logic that $p\vee \lnot p$ is a tautology for all propositions $p$. Hence we have the universally valid inference $(p \vee \lnot p) \wedge \lnot(\lnot p) \Rightarrow p$.

The point that Halmos is making is that due to the law of the excluded middle, you can do proofs by contradiction. For some of the facts about the empty set, this is very useful.

Not all systems of logic accept the law of the excluded middle. Non-classical systems like intuitionist or paraconsistent logic do not accept it. In mathematics, there is a school called constructivism that rejects the law of the excluded middle, but most mathematicians accept it.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.