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

111–120 of 153 posts

Re: The Axiom of Choice Is Wrong (2007)

#111

Post by pron »

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.

That doesn't really matter. If all you care about is physical reality, you have to apply its implications on everything, and Gödel's incompleteness reappears in a different form. First, consider that undecidability is more general -- i.e., stronger -- than incompleteness, as undecidability implies incompleteness but not vice-versa. If you admit infinity, then you have undecidability and therefore incompleteness. If you don't have infinity because you decide to only care about physical reality, then you don't have undecidability, but then you must treat time as physical (and therefore finite) as well.

While you no longer have undecidability (and therefore no incompleteness, either), you do have its finite form, namely infeasibility (due to computational complexity), which, given an assumption that time is finite, amounts to precisely the same result. Almost every theorem about undecidability can be generalized to infeasibility. For example, instead of undecidability of the halting problem, we get infeasibility of the bounded halting problem (that's the basis for the hierarchy theorems, which gave birth to the notion of computational complexity, just as the halting problem gave birth to the notion of computability). Similarly, by bounded halting, instead of a consequence of incompleteness, i.e. "there are statements that can neither be proven nor falsified", you get "there are statements that can be neither feasibly proven nor falsified" -- this is a direct corollary of the hierarchy theorems -- and the problem remains the same. The only question is whether you're willing to admit infinity (or what kinds of infinity you're willing to admit) as a convenience, or as an approximation of large finite quantities. But choosing not to admit infinity doesn't really make anything simpler (on the contrary, things may get more tedious).

Re: The Axiom of Choice Is Wrong (2007)

#112

Post by monochromatic »

skissane wrote: post #109
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 Godel's first theorem says no formal system with recursively enumerable axioms and which is powerful enough to express elementary arithmetic can be both consistent and complete. Most people adopt the response – alas, that means no formal systems we can devise can ever be complete (except for systems too weak…

Having only read the wiki page about dialetheism, it seems a lot more like philosophy than math or logic. Meh.

Re: The Axiom of Choice Is Wrong (2007)

#113

Post by kmill »

twic wrote: post #39

The axiom of choice always seemed intuitively wrong to me. You can't just take a set and arbitrarily pick something out of it! Making a choice requires information, and you can't pluck information out of thin air at whim; applying the axiom amounts to creating information out of nothing. I suppose this is because i'm not a mathematician, but have a natural sciences background. In the physical universe, memorably, "th…

The axiom isn't exactly about being able to pick an arbitrary element out of an arbitrary set. It says that if you have a collection of nonempty sets, then there is a function f from the collection X of sets to the union of the collection of sets, with f(A) an element of A, for A in X. To say each A is nonempty is kind of already saying that we can pick out an element from each set. The axiom just goes on to say that there is an actual function which does the picking out.

I think of it as taking the meta-level (a statement that every set in a collection of sets is nonempty) to the set level (there exists a function which picks out one of those elements for each set in the collection).

The axiom doesn't actually say what the function is. It just says that the set of functions with the given picking-out property is nonempty.

A similar statement to the axiom is that every sequence of nonempty sets A_1,A_2,... has at least one sequence a_1,a_2,... with a_i in A_i.

A consequence of the axiom of choice is that every vector space has at least one basis. I'm not sure whether every vector space having a basis is equivalent to the axiom of choice, though.

Re: The Axiom of Choice Is Wrong (2007)

#114

Post by skissane »

monochromatic wrote: post #112
skissane wrote: post #109

Earlier quoted context omitted.

> There is no objective mathematical reality, because it cannot include a statements about its own consistency Godel's first theorem says no formal system with recursively enumerable axioms and which is powerful enough to express elementary arithmetic can be both consistent and complete. Most people adopt the response – alas, that means no formal systems we can devise can ever be complete (except for systems too weak…

Having only read the wiki page about dialetheism, it seems a lot more like philosophy than math or logic. Meh.

The whole topic has both its more philosophical aspects and its more mathematical aspects. If you want to explore the more mathematical aspects, you probably want to start here https://en.wikipedia.org/wiki/Paraconsistent_mathematics and then end up reading something like https://www.amazon.com/Inconsistent-Mathematics-Its-Applicat...

EDIT: see also https://ir.canterbury.ac.nz/bitstream/handle/10092/5626/1263...

Re: The Axiom of Choice Is Wrong (2007)

#116

Post by amelius »

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…

Wikipedia ([1]) describes some ways around Godel's incompleteness theorem.

[1] https://en.wikipedia.org/wiki/Hilbert's_program#Hilbert.27s_...

Re: The Axiom of Choice Is Wrong (2007)

#117

Post by kmill »

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 main problem is taking a statement about a set ("for every A in X, A is nonempty") to the existence of a set ("there is a function f [which in ZFC is considered to be a set] such that for all A in X, f(A) is in A").

If you are able to create a statement P(A,a) that for every A in X is true for exactly one a in A, then it follows from the axiom of replacement that there is such a choice function. The axiom of choice seems to say that it suffices to make a statement P(A,a) that for every A in X is true for at least one a in A.

The axiom of replacement helps actually construct such a choice function, whereas the axiom of choice just asserts one ought to exist since "at least one" seems good enough.

To use the axiom of replacement, you have to use some structure for A. For instance, with the finite set example, it might be that each A is not just a set, but a set which is in bijective correspondence with a natural number, where there is a distinguished bijection. Then, you could just say that P(A,a) is true exactly when a is the image of 0 under the bijection.

Re: The Axiom of Choice Is Wrong (2007)

#118

Post by breuleux »

akud wrote: post #101
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?

Was going to say the same thing. Most of my professors were secretly platonists, though they had to pass as formalists to get respect in polite society. It's hard to make absolute claims about the nature of mathematical reality; the formalists need to explain why math is so successful in the real world, and the platonists need to give an account of the ontological nature of mathematical objects.

> why math is so successful in the real world

Well, math is a universal approximator -- if there are patterns in what we observe of reality, math can fit them, but that's a far cry from them "being" math. Other formal systems like Turing machines or Lambda calculus can also approximate anything (including each other, naturally) with different primitives... and they have an easier ontology (as far as I can tell). I mean, if you posit that fundamental reality is a computer of sorts, you get your ontology, and you get math as a very good formalism to describe the particular program we're in.

Re: The Axiom of Choice Is Wrong (2007)

#119

Post by hackinthebochs »

twic wrote: post #103
hackinthebochs wrote: post #89

Earlier quoted context omitted.

> You can't just take a set and arbitrarily pick something out of it! Making a choice requires information True, but how can you "have a set", i.e. reference a set in any way, without having information about that set? There seems to be a requirement of some bare minimum of information enough to specify the set, and so enough to pick out a member of the set.

Having enough information to specify the set isn't enough to pick out one particular member. For example, if i say "the colours teal, maroon, and taupe", you have enough information to know what's in the set, but no extra information that would let you pick one element out of it.

Well the issue is whether its possible in principle to define such a function for all possible sets. But if you can enumerate the elements of the set, such a function is simply to pick the first element.

So the issue is how much information is necessary to guarantee that its possible in principle to construct such a function. It should be clear that enough information to enumerate each set is enough to create a decision function. The remaining question seems to be whether one can specify a countable set of countable sets without specifying enough info about each member set to enumerate the set's members. It seems trivial that a set with countable elements is enumerable, but I might be missing some subtlety.

Re: The Axiom of Choice Is Wrong (2007)

#120

Post by Jweb_Guru »

naasking wrote: post #105
Jweb_Guru wrote: post #98

Earlier quoted context omitted.

> Real space doesn't appear to be infinite Citation needed. People keep saying things like this ("real space isn't infinite" or "real spacetime must be discrete") but never show their work.

Google "Bekenstein Bound".

That doesn't prove anything about the continuity (or lack thereof) of spacetime, just indicates that energy is discretized. Also has no bearing on the original statement about infinity.

It's also worth pointing out that the original statement is nonsensical because the theory of real closed fields doesn't suffer from incompleteness in the first place, so there's no need to "save" it from paradox the way you have to save Peano arithmetic.

Post reply on HN