3 ms·
How many sets of natural numbers are there? An uncountable number. Of course, you could throw out some axioms so that you create an axiom system in which I can
by zodiac 10y ago
How many sets of natural numbers are there? An uncountable number.
Of course, you could throw out some axioms so that you create an axiom system in which I can't define such a thing as "a subset of the natural numbers", but such a world doesn't feel "real" (in a platonic sense) to me.
- pherq 10y agoIn this case, what you "throw out" are uncomputable (or non-recursive, depending on terminology you like) sets; i.e. sets for which the membership function is not decidable. Yes, there are an uncountable number of these sets, but they can't be defined in any useful way.
- baddox 10y agoIndeed, if you consider a real number to just be a decimal representation formed by concatenating all the natural numbers in a set (not at all a rigourous construction of the reals, but hopefully sufficient for this argument), the equivalence is clear.
- zodiac 10y agoI've always found dedekinds construction (where sqrt 2 is represented by the set of rationals {x in Q : x^2 < 2}) to be a nice natural place where powersets of countable infinite sets come up (in addition to being a great way to construct R)
- pherq 10y agoI tend to prefer considering the sets to encode bitstrings (encode a set as sum(2 ^ -x for x in X)), but yes the equivalence between computable sets and computable numbers is straightforward.
- zodiac 10y agoFor sure - as I understand it in most formulations you throw out lots of sets but keep all the finite sets of natural numbers, the set of even numbers, the set of prime numbers etc One thing I never found satisfactory is that any axiom system like this has to define things in terms of decidability etc, so it's "more verbose" (or less axiomlike) than ZFC
- pherq 10y agoThis is a fair point. I think the only axiom you need to rethink from ZF is powersets (since I think that's the only axiom that produces uncomputable sets from computable ones (ignoring the AC, briefly)). What you'd replace it with (some sort of one based on comprehension, presumably) I couldn't say though.
- skissane 10y ago> How many sets of natural numbers are there? An uncountable number. But, at most countably many of those sets will ever be individually thought about by any human being. So there are only countably many (and maybe more strongly finitely many) subsets which any human being could ever possibly think about, and an uncountable remainder which are unthinkable. In order to do mathematics, do we really need to posit the existence of an uncountable number of objects no human mind will ever be able to individually consider? > Of course, you could throw out some axioms so that you create an axiom system in which I can't define such a thing as "a subset of the natural numbers", but such a world doesn't feel "real" (in a platonic sense) to me. You could introduce a set theory where from a countable set you can only infer the existence of its computable subsets, or its first order definable subsets, or something like that. Not sure why that should feel any less "real" than an uncountable infinity of mathematical objects about which no one will ever individually think.
- baddox 10y ago> But, at most countably many of those sets will ever be individually thought about by any human being. If your arguments are tied to such physical constraints, then there aren't even countably infinite natural numbers unless the Universe is infinite in space or in time (such that there can be infinite humans or "thinkers").
- skissane 10y agoIndeed, that's why I'm an ultrafinitist. https://en.wikipedia.org/wiki/Ultrafinitism https://en.wikipedia.org/wiki/Ultrafinitism