defining natural numbers in ZF and new foundations
taffer
the natural number n to be the set of all sets with n elements.
Lets assume that we know what it means for a set to be finite. Let F
be the set of all finite sets. Then partition F into equivalence
classes, where the equivalence relation is defined so that two sets
are equivalent if and only if they have the same cardinality. Then we
call the equivalence classes natural numbers.
I read something about this not working in ZF and some other set
theories, but that it does work in new foundations. Why is this?
MoeBlee
I replied to this in sci.logic but it didn't copy to sci.math.
Anyway, there's no set of all the finite sets in ZF.
MoeBlee
Michael Stemper
>On Sep 2, 12:09=A0pm, taffer <djr...@bath.ac.uk> wrote:
>> The Bertrand Russell definition of number, roughly speaking, defines
>> the natural number n to be the set of all sets with n elements.
>> I read something about this not working in ZF and some other set
>> theories, but that it does work in new foundations. Why is this?
>
>I replied to this in sci.logic but it didn't copy to sci.math.
>
>Anyway, there's no set of all the finite sets in ZF.
Is there a set of all singletons?
A set of all sets equipollent with { 0, {0} }?
If not, is it a case of "a set doesn't exist in ZF unless we can
prove its existence", or is it a case of "the existence of such a
set would lead to the following contradiction"?
--
Michael F. Stemper
#include <Standard_Disclaimer>
Visualize whirled peas!
Arturo Magidin
wrote:
> In article <ebadd27a-bd1f-443e-a00f-eec054d73...@l20g2000yqe.googlegroups.com>, MoeBlee <jazzm...@hotmail.com> writes:
>
> >On Sep 2, 12:09=A0pm, taffer <djr...@bath.ac.uk> wrote:
> >> The Bertrand Russell definition of number, roughly speaking, defines
> >> the natural number n to be the set of all sets with n elements.
> >> I read something about this not working in ZF and some other set
> >> theories, but that it does work in new foundations. Why is this?
>
> >I replied to this in sci.logic but it didn't copy to sci.math.
>
> >Anyway, there's no set of all the finite sets in ZF.
>
> Is there a set of all singletons?
Not in ZF.
> A set of all sets equipollent with { 0, {0} }?
Not in ZF.
>
> If not, is it a case of "a set doesn't exist in ZF unless we can
> prove its existence", or is it a case of "the existence of such a
> set would lead to the following contradiction"?
The latter.
Suppose the collection of all singletons is a set, X. Define f:P(X)--
>X by f(A)={A}. Then f is a one-to-one function from P(X) to X, so |
P(X)| <= |X| < |P(X)| (the latter by Cantor's Theorem), which yields a
contradiction. So the collection of all singletons cannot be a set.
(There are many other ways of proving it).
If the collection Y of all sets equipollent to {0,{0}} is a set,
define g:P(Y)-->Y as follows: if A is not empty, then g(A) =
{emptyset, A}. Then define g(emptyset) = {{emptyset}, {{emptyset}}}..
I claim that g is one-to-one: if A is not empty, then g(A)=/
=g(emptyset), since emptyset is an element of g(A), but not of
g(emptyset).
if A=/=B and neither is empty, then A is in g(A), but A is not in
g(B)={emptyset,B}, because A=/=emptyset and A=/=B.
Thus, g is one-to-one, and we get the same contradiction as with the
"set of all singletons".
--
Arturo Magidin
Arturo Magidin
> A set of all sets equipollent with { 0, {0} }?
>
> If not, is it a case of "a set doesn't exist in ZF unless we can
> prove its existence", or is it a case of "the existence of such a
> set would lead to the following contradiction"?
Alternatively: if X is a set of all singletons, then \/X is the set of
all sets (given a set A, {A} is in X). Likewise, if Y is a set of all
sets equipollent to {0,{0}}, then \/Y would be the set of all sets
(given any nonempty set A, {emptyset,A} is equipollent to {0,{0}}, and
{emptyset,{emptyset}} is equipollent to {0,{0}} so emptyset is an
element of \/Y.
--
Arturo Magidin
MoeBlee
> > there's no set of all the finite sets in ZF.
> Is there a set of all singletons?
There's no set that has all the singletons in it.
> A set of all sets equipollent with { 0, {0} }?
There's no such set.
> If not, is it a case of "a set doesn't exist in ZF unless we can
> prove its existence", or is it a case of "the existence of such a
> set would lead to the following contradiction"?
A contradiction.
Toward a contradiction, suppose Ay(z in x <-> y equipotent with {0
{0}}). Then, for all non-empty z, we have {0 z} in x. So 0 in Ux and
for all non-empty z, we have z in Ux. So, for all z whatsoever, we
have z in Ux. Then, by separation, let R = {z | z in Ux & z not in z}.
Then for all z, we have z in R if and only if z not in Z. Then R in R
if and only if R not in R.
MoeBlee
Transfer Principle
> The Bertrand Russell definition of number, roughly speaking, defines
> the natural number n to be the set of all sets with n elements.
> theories, but that it does work in new foundations. Why is this?
Ah yes, Quine's New Foundations, one of my favorite theories to
discuss since it is a counterexample to the claims of posters who
label challengers to Cantor with five-letter insults.
Let me answer the second part of the OP's question -- namely why
Russell's natural numbers _do_ work in NF(U) -- by explaining
where MoeBlee's and Magidin's proofs break down in NF(U).
MoeBlee constructs a set R using the Separation Schema, but its
definition is not stratified. Thus, one ultimately proves in NF(U)
that R isn't a set.
Similarly, Magidin defines a function f with domain P(1) and
codomain 1 (using Russell's definition of 1), but its definition
is not stratified either. Thus, one ultimately proves in NF(U)
that f doesn't exist either.
For more information about NF, click the following link:
http://math.boisestate.edu/~holmes/holmes/nf.html
Scroll down to "The Paradoxes" to see why the definitions of
MoeBlee's R and Magidin's f aren't stratified.
Jesse F. Hughes
> Ah yes, Quine's New Foundations, one of my favorite theories to
> discuss since it is a counterexample to the claims of posters who
> label challengers to Cantor with five-letter insults.
No, it isn't.
--
"Yeah, I know, it's quantum [computing], and all kind of interesting physics
associated with what is to many a mystical word, but I have a B.Sc. in physics,
and I know that you're just talking about specialized mechanical devices when
you talk about quantum computing." -- James S. Harris
Tim Little
> Is there a set of all singletons? A set of all sets equipollent
> with { 0, {0} }?
Neither of those. The union of either of these would be the universal
set, leading straight into Russell's paradox.
> If not, is it a case of "a set doesn't exist in ZF unless we can
> prove its existence", or is it a case of "the existence of such a
> set would lead to the following contradiction"?
It is the latter. ZF proves the nonexistence of such sets.
- Tim
Michael Stemper
>On Sep 2, 4:00=A0pm, mstem...@walkabout.empros.com (Michael Stemper) wrote:
>> In article <ebadd27a-bd1f-443e-a00f-eec054d73...@l20g2000yqe.googlegroups.com>, MoeBlee <jazzm...@hotmail.com> writes:
>> >> The Bertrand Russell definition of number, roughly speaking, defines
>> >> the natural number n to be the set of all sets with n elements.
>> >> I read something about this not working in ZF and some other set
>> >> theories, but that it does work in new foundations. Why is this?
>>
>> >I replied to this in sci.logic but it didn't copy to sci.math.
>>
>> >Anyway, there's no set of all the finite sets in ZF.
>>
>> Is there a set of all singletons?
>
>Not in ZF.
>> If not, is it a case of "a set doesn't exist in ZF unless we can
>> prove its existence", or is it a case of "the existence of such a
>> set would lead to the following contradiction"?
>
>The latter.
>
>Suppose the collection of all singletons is a set, X. Define f:P(X)--
>>X by f(A)=3D{A}. Then f is a one-to-one function from P(X) to X, so |
>P(X)| <=3D |X| < |P(X)| (the latter by Cantor's Theorem), which yields a
>contradiction. So the collection of all singletons cannot be a set.
>(There are many other ways of proving it).
Got it. In fact, { {x} | x is a set } is perilously close to having
a set of all sets, isn't it?
Thanks for the explanation.
I was surprised by this revelation because I'd thought that what was
given above *was* the standard definition of cardinal. Reviewing my
Suppes, I see that he does clearly state that this only works in
Frege-Russell, as taffer noted above.
--
Michael F. Stemper
#include <Standard_Disclaimer>
COFFEE.SYS not found. Abort, Retry, Fail?