Where is this wrong?

[KrazyHorse]

Originally posted by civman2000
It has nothing to do with Godel or incompleteness. It is all about inconsistency. All you've done is shown that a certain logical system--namely the form of naive set theory that allows such descriptions as "cannot be defined in fewer than twenty english words". Alternatively, you have proven that if set theory is consistent, then the predicate "cannot be defined in fewer than twenty english words" cannot be expressed in the language of set theory.

Wrong. This does not demonstrate an "inconsistency". It demonstrates an incompleteness.

If you know some set theory, here's a similar paradox: Say that a set is definable if, well, we can define it in some way. There are clearly only countably many definable sets, since any description must be finite in length. Thus there exist some undefinable ordinals. Let alpha be the least undefinable ordinal. But we just defined it!

?

There are only countably many cardinals. But thanks for trying.

What this shows is that the concept of "definability" cannot itself be definable.

No, it shows that "definability" cannot itself be definable as long as you want completeness.

[civman2000]

Originally posted by KrazyHorse


Wrong. This does not demonstrate an "inconsistency". It demonstrates an incompleteness.

It does show inconsistency. You can make the following argument in naive set theory:
1. Any nonempty set of natural numbers has a unique least element.
2. There are only finitely many strings of <20 English words.
3. Therefore the set of natural numbers that are not described by a string of <20 English words is nonempty.
4. By (1), there is a unique least element of the set in (3).
5. But that number is "the least number that is not described by a string of less than 20 English words"; contradiction.

The only way you could turn this into a proof of omega-incompleteness or some other kind of completeness would be to either deny (1) or to deny the passage from (1) to (4), both of which would be leaving the realm of standard naive set theory/logic.

If you know some set theory, here's a similar paradox: Say that a set is definable if, well, we can define it in some way. There are clearly only countably many definable sets, since any description must be finite in length. Thus there exist some undefinable ordinals. Let alpha be the least undefinable ordinal. But we just defined it!

?

There are only countably many cardinals. But thanks for trying.

. Either you misunderstood me or you know nothing about set theory. First of all, I was talking about ordinals, not cardinals. Secondly, there are uncountably many cardinals anyways. See http://en.wikipedia.org/wiki/Cardinal_number and http://en.wikipedia.org/wiki/Ordinal_number.

No, it shows that "definability" cannot itself be definable as long as you want completeness.

Again, it has nothing to do with completeness. The argument above proves a contradiction from the premise that "definability" is definable.

Formally, let "P(x)" be a formula that says x is definable by a formula (ie there exists a formula phi such that phi(y) iff x=y). Let X={x:P(x)}, and let omega_1 be the set of all countable ordinals. Since there are only countably many formulas, X is countable, but omega_1 is uncountable. Let "phi(x)" be the formula "x is an element of omega_1 and not an element of X and if y is an element of omega_1 and not an element of X, x<=y". Then since omega_1-X is nonempty (omega_1 is uncountable and X is countable), phi(x) defines some unique set alpha. Hence alpha is in X. But by definition, alpha is not in X; contradiction.

I suppose you could say that I presupposed that X was countable. Certainly if we can prove P(x) holds iff x is definable, then we can prove X is countable. Thus i guess you could say we have the following incompleteness: definability might be definable, but we couldn't prove that any formula defines it. However, this seems like a rather strange way to view it.

[KrazyHorse]

Originally posted by civman2000

It does show inconsistency. You can make the following argument in naive set theory:
1. Any nonempty set of natural numbers has a unique least element.
2. There are only finitely many strings of <20 English words.
3. Therefore the set of natural numbers that are not described by a string of <20 English words is nonempty.
4. By (1), there is a unique least element of the set in (3).
5. But that number is "the least number that is not described by a string of less than 20 English words"; contradiction.

The only way you could turn this into a proof of omega-incompleteness or some other kind of completeness would be to either deny (1) or to deny the passage from (1) to (4), both of which would be leaving the realm of standard naive set theory/logic.

No, the problem is in creating the actual set of numbers. I'm refuting the claim that you can put any specific numbers in your set of undefinable numbers because their undefinability is an undecidable statement. And I didn't say that it was w-incomplete; I said that the w-completeness created the incompleteness.

First of all, I was talking about ordinals, not cardinals. Secondly, there are uncountably many cardinals anyways

Sorry; misread you as talking about cardinals. And while the cardinals are uncountable, my understanding of your argument had you necessarily restricting the sets you were talking about. To the point where the set of cardinals contained was countable. Second reading makes more sense. Same problem here as above, though.

[civman2000]

No, the problem is in creating the actual set of numbers. I'm refuting the claim that you can put any specific numbers in your set of undefinable numbers because their undefinability is an undecidable statement. And I didn't say that it was w-incomplete; I said that the w-completeness created the incompleteness.

But naive set theory, as it usually is formulated, is not restricted to any constructivist framework--on the contrary, it allows an enormous (so enormous it's inconsistent) universe of sets. Thus even if we can't "construct" any undefinable number (ie "put a specific number in your set"), we can prove that the set of undefinable numbers is nonempty. But then by well-ordering, we can prove there exists a least undefinable number, yielding a contradiction.

[civman2000]

To clarify my point, I am asserting that it is not necessary to "create the actual set of numbers". We can still prove it's nonempty even if we can't prove any individual number is in it or construct/create it in any "real" way. This may lead to a form of incompleteness, but it also leads to inconsistency via Kuciwalker's argument, and if a theory is inconsistent it's meaningless to ask whether it's complete.

[KrazyHorse]

Originally posted by civman2000

But naive set theory, as it usually is formulated, is not restricted to any constructivist framework--on the contrary, it allows an enormous (so enormous it's inconsistent) universe of sets.

If you look at it as being that unrestricted in its statements, then yes, it does allow a contradiction (if you let yourself talk about a set of unconstructable numbers). I suppose I don't use "completely" naive set theory when I think about it. More like "semi" naive.

[civman2000]

If you look at it as being that unrestricted in its statements, then yes, it does allow a contradiction (if you let yourself talk about a set of unconstructable numbers). I suppose I don't use "completely" naive set theory when I think about it. More like "semi" naive.

The entire framework of modern mathematics relies on such nonconstructive formulations, even in axiomatic set theory (although it has been shown that almost all of mathematics can be formulated in a more constructive setting; see http://math.wustl.edu/~nweaver/conceptualism.html, for example). Take, for example, the axiom of choice. Very few people remain who would deny its legitimacy as a mathematical tool, but it allows us to assert a lot about sets even if we can't identify or construct a single element of them. In fact, in a much more subtle way, talking about the power set of an infinite set is just as nonconstructive, since you can show that there are some subsets that cannot be "constructed" unless you have already constructed the entire power set.

[KrazyHorse]

I hate the ****ing Axiom of Choice. Even though I've used it.