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

41–50 of 153 posts

Re: The Axiom of Choice Is Wrong (2007)

#41

Post by CJefferson »

heinrichhartman wrote: post #38
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…

Are you aware of the concept of periods ? This is a quite fascinating, countable, ring of numbers, that captures all of the above: Kontsevich and Zagier introduce and develop this concept quite far: http://www.maths.ed.ac.uk/~aar/papers/kontzagi.pdf

No, but this looks interesting. Thanks for the reference!

Re: The Axiom of Choice Is Wrong (2007)

#42

Post by candiodari »

cygx wrote: post #37
fmap wrote: post #24

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…

There is no objective mathematical reality, because it cannot include a statements about its own consistency I'm assuming we're talking about Gödel's incompleteness theorems? Don't they just say that if there's such a thing as objective mathematical reality, it can't be effectively axiomatized?

> Don't they just say that if there's such a thing as objective mathematical reality, it can't be effectively axiomatized?

No they don't. Real space doesn't appear to be infinite, and Zn is not subject to Godel's incompleteness theorem.

If you drop the requirement of infinite numbers and "recursive" infinites (e.g. real numbers), as reality appears to do, there is no problem.

Re: The Axiom of Choice Is Wrong (2007)

#43

Post by heinrichhartman »

CJefferson wrote: post #33
heinrichhartman wrote: post #28

Earlier quoted context omitted.

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.

Why not, can you give an example. Most of the "common" derivatives and integrals I can think of would work just fine, unless I'm missing something obvious?

- Every real number can be represented as a limit of rational numbers, which are uncountable. - So for every countable subset you can find a (Cauchy) sequence of rationals that does not converge.

Hence, you loose one of the most important tools in Analyisis (Cauchy criterium for convergence). You can still work with the remaining set, but formulating and proving theorems, is going to be much harder.

- If integrals over f and g exists, then the integral over f * g does not need to exists. - E.g. Integrals over bounded regions will not always exists. - Theorem of Montonic convergence fails - Function spaces will not be complete (L2).

A nice theory of constructible "periods" has been developed by Kontsevich and Zagier (http://www.maths.ed.ac.uk/~aar/papers/kontzagi.pdf) but it relies heavily on the existing body of Analysis being available.

Re: The Axiom of Choice Is Wrong (2007)

#44

Post by im3w1l »

baddox wrote: post #16
im3w1l wrote: post #5

I'd assume that even if in every case the number of incorrect guesses is finite, the expected number of people that fail to guess their color is infinite. Am I right about this?

Im not sure what you mean by "expected number." Do you mean if you try to guess how many inmates the warden has managed to guarantee will fail? Per the article, the warden can guarantee that an "arbitrarily large finite number of them" will fail. But it's still always finite despite being unbounded. If you want to predict a lower bound on the number of failures the warden has guaranteed, you just have to guess a larg…

I mean if the warden picks a sequence randomly.

Re: The Axiom of Choice Is Wrong (2007)

#45

Post by rtpg »

I have a vague understanding of the Axiom of Choice, but I've always had trouble with some of the analogies people use to explain it.

Two things that have bugged me for a while:

- why is it usually talked about only in the context of infinite sets? Is there a general trick to building a choice function if all you have are finite sets?

- There's a saying like "you can choose from an infinite set of shoes, but not from an infinite set of socks without AC". Why exactly?

Re: The Axiom of Choice Is Wrong (2007)

#46

Post by cygx »

candiodari wrote: post #42
cygx wrote: post #37

Earlier quoted context omitted.

There is no objective mathematical reality, because it cannot include a statements about its own consistency I'm assuming we're talking about Gödel's incompleteness theorems? Don't they just say that if there's such a thing as objective mathematical reality, it can't be effectively axiomatized?

> Don't they just say that if there's such a thing as objective mathematical reality, it can't be effectively axiomatized? No they don't. Real space doesn't appear to be infinite, and Zn is not subject to Godel's incompleteness theorem. If you drop the requirement of infinite numbers and "recursive" infinites (e.g. real numbers), as reality appears to do, there is no problem.

Ok. Not sure I buy that (eg right now, we have no reason to believe that the lifetime of the universe is finite), but that's not what I was getting at:

My point is that at worst, the incompleteness theorems only imply that we won't be able to write down all the rules that govern the universe.

Re: The Axiom of Choice Is Wrong (2007)

#47

Post by vostok »

llamaz wrote: post #27
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-dampe…

> I used to think, for example, that the dirac delta function was mathematical fiction - a mathematical "hack".

Can you expand on this? The Dirac delta function is not a function from R to R for example.

Re: The Axiom of Choice Is Wrong (2007)

#48

Post by ramblenode »

What an interesting thought experiment. Lying in bed last night, the best I could come up with (before seeing the optimal solution this morning) was an average of 83 with a minimum of 66.

The prisoners agree that every third prisoner, beginning with the first, uses "white" to convey that the subsequent two prisoners are wearing the same color and "black" to convey different colors. Since the second prisoner in each triple knows the color of the third, he can deduce his own color, leaving the third prisoner to also deduce his own color. And of course there's a 50/50 chance the sacrificial first prisoner in the triple still gets out. I suppose this could be improved upon by later prisoners having a longer memory, but I've already seen the optimal solution. ;)

Interested to hear others' attempts.

Re: The Axiom of Choice Is Wrong (2007)

#49

Post by petteris »

rtpg wrote: post #45

I have a vague understanding of the Axiom of Choice, but I've always had trouble with some of the analogies people use to explain it. Two things that have bugged me for a while: - why is it usually talked about only in the context of infinite sets? Is there a general trick to building a choice function if all you have are finite sets? - There's a saying like "you can choose from an infinite set of shoes, but not from…

The axiom of choice is about making an infinite number of arbitrary choices simultaneously. If you can specify some rule, this rule is just one choice. Finitely many choices are always fine and don't need the axiom of choice.

If you have a finite set, you can number its elements and make rules by saying "let's take the element with the smallest number having this or that property", so you don't need the axiom of choice when dealing with finite sets.

The point of Russell's shoes versus socks analogy is that shoes are distinguishable while socks aren't: To choose one shoe from each of an infinite set of pairs of shoes, you can always choose the left shoe, or specify some pattern (so you don't need the axiom of choice), whereas when choosing socks, you have to make an arbitrary choice to select one from each pair (so you do need the axiom of choice).

Re: The Axiom of Choice Is Wrong (2007)

#50

Post by wolfgke »

heinrichhartman wrote: post #38
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…

Are you aware of the concept of periods ? This is a quite fascinating, countable, ring of numbers, that captures all of the above: Kontsevich and Zagier introduce and develop this concept quite far: http://www.maths.ed.ac.uk/~aar/papers/kontzagi.pdf

Just to give a little bit more attention to this link: Wikipedia link to one of the authors:

> https://en.wikipedia.org/wiki/Maxim_Kontsevich

Proof that one of the authors really is no other "M. Kontsevich" (I openly admit that I wanted to be sure since I associate Maxim Kontsevich mostly with other mathematical areas):

> http://www.ihes.fr/~maxim/publicationsanglais.html

Post reply on HN