The Empty Set (or lack thereof)

[TuringAI]

What I just gave is the diagonal argument. I gave it semi-formally, since that seemed to be the context of the discussion at the time. And the poster wanted to see exactly what axioms are used. Also, I want to impress the fact that there is a proof that is indeed a formal mathematical object, so that 'proof' is taken in that context and not necessarily in certain other senses of the word. The semi-formal proof I gave is sufficient to see that there is a formal mathematical proof of the statement.

For just a relaxed natural language rendering:

Theorem: There is no function from x onto Px.

Proof: Suppose f is a function from x to Px.

Let d be the set of b such that b in x and b not in f(.

d is a subset of x.

Suppose for some b, we have d is f(.

So b in f( iff b not in f(, which is a contradiction.

So, for no b do we have that d is f(.

So d is not in the range of f.

Is there any plainer english version of this proof? I know what injective and surjective and bijective mean. I don't need help there. What I need help with is understanding why we suppose that for some b, d is in f(. It seems to me that if we do not suppose such a thing, we could have a function that maps x onto Px.

Edited August 16, 2008 by TuringAI

[Hodge'sPodges]

Is there any plainer english version of this proof? I know what injective and surjective and bijective mean. I don't need help there. What I need help with is understanding why we suppose that for some b, d is in f(. It seems to me that if we do not suppose such a thing, we could have a function that maps x onto Px.

No, we don't suppose that for some b we have d in f(. Rather, we suppose that for some b we have that d IS f(. That is simply the supposition that d is in the range of f, which is required if f is onto Px.

I'll restate the proof with more detail:

Theorem: There is no function from x onto Px.

Proof: Suppose f is a function from x to Px.

Let d be the set of b such that b in x and b not in f(.

d is a subset of x.

If f is onto Px, then, since d is in Px, we have d in the range of f, so for some b in x we have d is f(.

Suppose b in f(, then since f( is d, we have b in d, but then b not in f(.

So if b in f( then b not in f(.

Suppose b not in f(, then since f( is d, we have b not in d, so, since b in x, we have b in f(.

So if b not in f( then b in f(.

So b in f( iff b not in f(, which is a contradiction. So f is not onto Px.

The proof uses only minimal logic (which is even weaker than intuitionistic logic), identity theory, and the axiom schema of separation. Any other proof from axioms of ZFC set theory that there exists a set x and function f from x onto Px would prove that ZF is inconsistent (since if ZFC is inconsistent then ZF is inconsistent). ZF has been under intensely detailed examination by mathematicians of all kinds going on about 90 years now, which makes it at least seem unlikely that any time soon you'll prove that ZF is inconsistent.

Edited August 18, 2008 by Hodge'sPodges

[skippy]

... I think it boils down to the purpose of the empty set.

Precisely. Formal set theory (ZF or ZFC) was an attempt to codify all of mathematics into a few comprehensible axioms. There is no possible proof of the consistency of these axioms although a century of searching (by a lot of really clever people) has yet to display an inconsistency. The existence of the empty set is proven using the Axiom of Separation and the Axiom of Infinity (see, for example, chapter 1 of "Set Theory" by Thomas Jech). The purpose or use of the empty set is to be able to actually construct mathematical objects like numbers and functions and everything else. Mathematics does not concern itself with sets of apples or oranges; only sets that it can construct in a precise way. Real proofs in formal set theory can contain thousands of steps for quite simple theorems.

As a simple example, the natural numbers can be defined in terms of the empty set by identifying Zero with the empty set {}, One with {{}}, the set containing the empty set,

Two with { {}, {{}} }. In general each natural number is the set containing all natural numbers less that it.

Now, you don't have to accept set theory at all. Some professional mathematicians do not "believe" in sets. The natural numbers can be constructed in a very intuitive way with the Peano axioms, or in very unintuitive way using the methods of Principia Mathematica (Russel & Whitehead). None of these methods can be proven consistent.

While 99.9% of all mathematicians ignore these issues the few that concern themselves with the foundations of mathematics fall into roughly three groups:

Formalists. Mathematics is a game played by clever manipulation of axioms (set theory or otherwise).

Platonists. Mathematical truths, in particular the natural numbers, EXIST independently of any intelligent creatures which might use or study them.

Ultrafinitists. Something like Platonists except that they only believe in the existence of a FINITE quantity of natural numbers. They probably number about 0.01% of the 0.1% that actually care about these things.

So, pick your poison. If you don't want to accept set theory, don't talk about the continuum or things like differentiable functions, they don't exist.

Cheers, Skippy

[Hodge'sPodges]

Formal set theory (ZF or ZFC) was an attempt to codify all of mathematics into a few comprehensible axioms.

Probably the first formal set theory was a proposal of Zermelo (though it was not yet fully formal). His primary purpose was to prove the well ordering theorem. ZF came later and was a refinement (closer to full formalization) and an expansion of Zermelo's proposal.

There is no possible proof of the consistency of these axioms although a century of searching (by a lot of really clever people) has yet to display an inconsistency.

If ZFC is consistent, then the consistency of ZFC cannot be proven by ZFC (nor, perforce, by a theory weaker than ZFC). However, there are theories that do prove the consistency of ZFC. Of course, the epistemological value of such proofs may not be great; nevertheless, they are formal proofs.

The existence of the empty set is proven using the Axiom of Separation and the Axiom of Infinity (see, for example, chapter 1 of "Set Theory" by Thomas Jech).

In some treatments, the axiom of infinity is used, but this is not necessary; the existence of an empty set can be derived from the axiom schema of separation and uniqueness from the axiom of extensionality.

The natural numbers can be constructed in a very intuitive way with the Peano axioms,

I don't know what sense of construction you have in mind. Rather, the natural numbers and the basic operations on them are a MODEL of first order Peano arithmetic.

Formalists. Mathematics is a game played by clever manipulation of axioms (set theory or otherwise).

That does not really capture the range of thinking that comes under the formalist school. Most reasonable formalists (say, of the Hilbertian bent) do not consider mathematics to be ONLY such a game, but rather that there is an ASPECT of mathematics that is as definite in its rules as those of games such as chess.

Platonists. Mathematical truths, in particular the natural numbers, EXIST independently of any intelligent creatures which might use or study them.

Ultrafinitists. Something like Platonists except that they only believe in the existence of a FINITE quantity of natural numbers.

Formalists. Mathematics is a game played by clever manipulation of axioms (set theory or otherwise).

There are also many other schools of thought, including finitism (related to formalism on one end and to intuitionsim on the other end), constructivism, intuitionism (a form of constructivism), predicativism (related also to constructivism), Russian constructivism, Bishop constructivism, structuralism, consequentialism, fictionalism, instrumentalism, logicism, variations on realism other than full-fledged platonism, etc.

There were several other points in your posts that are correct; I did not include them but rather I only commented on those points I felt in need of comment.

Edited March 13, 2009 by Hodge'sPodges

[aleph_0]

So I don't have the time or inclination to read most of this topic, and while I don't have any philosophical objection to set theory (the null set is just defined as that set which is in all sets, and has no members--no big deal, just a definition of a term, a creation of a language-game), if anyone is interested in alternatives to set theory, there is category theory which takes the mapping relation as primitive (I'm not sure how, but whatever) and there is present-day research going into replacements of set theory based on formal ontology. Namely, there is a formal ontology which is trying to reproduce the successes of set theory but without having a most basic element (motivated by the mereological theory in which there is no basic unit of matter but which is instead gunky). That is to say, it effectively does away with the null-set, which in set theory is like a most-basic set. FYI.