Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

The Axiom of Choice Is Wrong (2007)

cornellmath.wordpress.com

Post reply on HN
Print view View original

21–30 of 153 posts

Re: The Axiom of Choice Is Wrong (2007)

#21

Post by zodiac »

pherq wrote: post #9
zodiac wrote: post #8

Earlier quoted context omitted.

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.

In 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.

For 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

Re: The Axiom of Choice Is Wrong (2007)

#22

Post by zodiac »

mrob wrote: post #20

Infinities aren't real, so you shouldn't be surprised if unrealistic things happen when you invoke infinities. That you can duplicate a sphere by cutting it into a finite number of pieces and reassembling it is a "fact" in the same sense as "Luke Skywalker destroyed the Death Star". It might be interesting and culturally important, but it's talking about fictional entities. Both spheres and arbitrarily detailed piece…

There are a small number of people who think it's obviously false! (I'm not one of them). And a larger number who think it's not obviously true nor obviously false.

Re: The Axiom of Choice Is Wrong (2007)

#23

Post by zodiac »

skissane wrote: post #11
zodiac wrote: post #8

Earlier quoted context omitted.

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.

> 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 ex…

I meant it doesn't feel real to me in a subjective sense, and of course I acknowledge other people might not feel the same way.

Re: The Axiom of Choice Is Wrong (2007)

#24

Post by fmap »

The problem solution in the article uses the axiom of choice to construct a "nonprincipal ultrafilter" on the natural numbers. This is actually weaker than the full axiom of choice, but you can still show that no such object is computable. It's a nice exercise to show that with the same assumptions as in the article you can decide the halting problem. (hint: consider the boolean sequence where the nth element is true iff the Turing machine halts within n steps)

As for the axiom of choice, the real problem is trying to claim that it is right or wrong in the first place. Mathematics as a whole has never quite recovered from the failure of Hilbert's program... The bottom line is that there is no complete and consistent notion of "truth". There is no objective mathematical reality, because it cannot include a statements about its own consistency (and it's easy to translate this into "statements about certain hard problems", by exactly the same process we use to show that some problems are NP complete by reduction from another NP complete problem).

On the other hand, this is not actually detrimental to mathematical practice. It only means that you have a lot more freedom in modeling your problem domain. For instance, it turns out that set theory with the axiom of choice is a horrible place to do probability theory in (non-measurable sets and functions are a direct consequence, and you have to go to a lot of trouble to exclude them everywhere). If ZFC was part of some objective mathematical reality, then this would in some sense be unavoidable, since ultimately you want to make statements describing reality. On the other hand, once we realize that this assumption is just plainly false, we can start looking for more refined models.

Re: The Axiom of Choice Is Wrong (2007)

#25

Post by pherq »

baddox wrote: post #14
pherq wrote: post #9

Earlier quoted context omitted.

In 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.

Indeed, 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.

I 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.

Re: The Axiom of Choice Is Wrong (2007)

#26

Post by pherq »

zodiac wrote: post #21
pherq wrote: post #9

Earlier quoted context omitted.

In 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.

For 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

This 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.

Re: The Axiom of Choice Is Wrong (2007)

#27

Post by llamaz »

mrob wrote: post #20

Infinities aren't real, so you shouldn't be surprised if unrealistic things happen when you invoke infinities. That you can duplicate a sphere by cutting it into a finite number of pieces and reassembling it is a "fact" in the same sense as "Luke Skywalker destroyed the Death Star". It might be interesting and culturally important, but it's talking about fictional entities. Both spheres and arbitrarily detailed piece…

Mathematics is formalised is to avoid this sort of philosophizing.

I used to think, for example, that the dirac delta function was mathematical fiction - a mathematical "hack". But then in an engineering control systems class, we did an experiment where we used a step function to approximate a dirac delta function. I could see the results both on the computer screen and in physical reality through a mass-spring-damper system. From that moment on I saw the dirac delta function in the same way that I see cosine/sine: The reason it works in math is because it has a basis in physical reality.

The lesson to be learned here, is that you don't know in advance whether something is obvious or not. To me, it doesn't make sense to decide whether the axiom of choice can be justified by looking at the axiom itself. You have to look at where it's used and required, and whether the proofs convey something that matches your physical intuition.

Re: The Axiom of Choice Is Wrong (2007)

#28

Post by heinrichhartman »

CJefferson wrote: post #3

As time goes by, I increasingly view things like uncountable infinities and the axiom of choice as "a fun maths game", rather than having any intrinsic truth or falsity. Other's view may differ. Here is an interesting thing I've never seen anyone write down (I should do it myself) -- we don't need uncountable infinities. * How many natural numbers are there? Countable * How many rational numbers are there? Countable…

Good luck developing analysis with only countable infinities. Limits will take you out of the realm of countable spaces.

Most of your derivatives and integrals won't exists, if you force them to take values in countable sets.

Re: The Axiom of Choice Is Wrong (2007)

#29

Post by Ceezy »

YOUR MATH ARE WRONG

If prisonners follow the last strategy, the dude number 0 as a probability of finding his hat of 50% and the dude number 1 000 000 50%. Why? because nobody knows how many times they will lose. Those who are sure to win are those close to infinity... This have nothing to do with Axiom of Choice. But only because almost all the mass of your distribution is near infinty. With or without Axiom of Choice this things exist.

Re: The Axiom of Choice Is Wrong (2007)

#30

Post by CJefferson »

joatmon-snoo wrote: post #17
CJefferson wrote: post #3

As time goes by, I increasingly view things like uncountable infinities and the axiom of choice as "a fun maths game", rather than having any intrinsic truth or falsity. Other's view may differ. Here is an interesting thing I've never seen anyone write down (I should do it myself) -- we don't need uncountable infinities. * How many natural numbers are there? Countable * How many rational numbers are there? Countable…

the solution to any problem any could ever have That's a pretty tall claim to make. Once upon a time people thought irrationals and transcendentals like pi and e didn't even exist . It wasn't until the past century that people realized abstract algebra and its ilk had practical applications. The same goes for chaos theory and fractals as well. Admittedly it's hard for me to envision a world where notions of countabil…

The reason I say "the solution to any problem anyone could ever make" is a maths argument!

If you can write down a problem as a finite string, then the set of all problems must be countable.

Post reply on HN