Mathematical Existence and the Axiom of Choice

https://billwadge.com/2022/11/28/to-be-or-not-to-be-mathematical-existence-and-the-axiom-of-choice/

by herodotus • 4 years ago

83 100 4 years ago

mr_gibbins4• 4 years ago

I like Bill Wadge's stuff and this is a great explanation of the axiom of choice. I spent a fair bit of time on ZF set theory + AC working in databases, and AC is essential for data-driven set-theory to function.

Bit confused about the unit sphere explanation but then again I'm unfamiliar with the underlying paper.

algon33• 4 years ago

By database do you mean a finite 2d array with column headings? Or something that can be represented by such an object? And its entries are elements of some countable sets? If so, what are you doing using ZFC there?

mr_gibbins4• 4 years ago

Thanks - see comment above.

zomglings• 4 years ago

I'm confused why you would need the Axiom of Choice when working with computable programs.

Unless you were proving theorems about possible contents of a database? But even that seems like you wouldn't need the Axiom of Choice.

Could you elaborate on what you were doing with ZFC with databases?

mr_gibbins4• 4 years ago

Not to cop out but a HN reply isn't the best place to provide a full explanation. Suffice to say I use the ZF axioms as a basis to teach how sets both differ from and are similar to tables, particularly using the more accessible parts of Stoll's textbook on axiomatic set theory. To give a single example, the axiom schema of replacement is a good analogy for how the output of a SELECT command over a set will also result in a set.

In terms of AC, the comment below about how this is actually the AFC is correct, since the sets I am talking about are finite. Of course, set projections or selections are arguably choice functions themselves, which makes them relevant, and ZFC includes AC in order to infer well-orderedness, which tables (after all, collections of sets) can indeed be.

lupire6• 4 years ago

That's the Axiom of Finite Choice, not the full Axiom of Choice.

https://en.m.wikipedia.org/wiki/Axiom_of_finite_choice

mr_gibbins4• 4 years ago

Yes - you are correct :)

sylware2• 4 years ago

I have always had mixed feelings about this axiom. It feels "2nd level", like it should build upon simpler axioms related to the mathematical object "set" and the mathematical object "function".

lupire6• 4 years ago

What do you mean?

The Axiom of Choice is a statement about a function on sets.

In context, of ZF, it's equivalent to the Well Ordering Principle/Axiom and Zorn's Lemma/Axiom.

Koshkin• 4 years ago

Then it wouldn’t be an axiom, which it, in fact, is, being logically independent from the rest. It is considered somewhat special though, and mathematicians, being nice people, usually indicate whether they rely on it in a proof.

sylware2• 4 years ago

Yep, this is what I meant by "2nd level": it feels like it is not an axiom but a theorem.

less_less4• 4 years ago

My favorite application of choice, known as ultrafilters:

You know those "mathematicians wearing hats" games, where the solution is a Hamming code or some kind of modular arithmetic thing? Here's one where there's no winning strategy.

You have N mathematicians wearing hats whose colors are chosen uniformly and independently at random from a set C. They can see each others' hats but not their own. Simultaneously and without communication, each mathematician must guess their own hat color. Everyone who guesses right wins, and everyone who guesses wrong loses. A strategy maps (other mathematicians -> hat color) -> guess of your hat color, or if you're guessing randomly, then a distribution of guesses.

No matter what strategy is chosen, N/|C| players win in expectation. There's no trick to improve this, though you can change the distribution of how many players win. For example, you can guarantee that at least floor(N/|C|) of them win. This is neat in that it works even in a derandomized setting, where the strategy must be deterministic and the hats are assigned maliciously by an opponent who knows the strategy. (This setting is easier to work with for infinite C, because you don't need to worry about probability distributions on infinite objects.) But if |C| > N, then you can't guarantee that anyone wins.

OK, but what if there are infinitely many mathematicians, and you have the axiom of choice? In that case, there exists a strategy which guarantees that all but finitely many players will win — that is, the overwhelming majority of them will win. This works no matter how big C is, even if C is infinite, even if it's vastly larger than the set of players (eg if it's uncountable but the players are countable).

Why? Well, consider the relation that two hat assignments are "almost the same" iff they differ in only finitely many places. This is an equivalence relation, so we can divide the space of hat assignments into equivalence classes. Assuming choice, there is a function F which maps an equivalence class to some element of it. Since these equivalence classes ignore finite differences, everyone can tell what equivalence class E has been assigned even without knowing their own hat color, so can guess their own color according to F(E). By construction this is in E, so it differs from the true assignment in only finitely many places, so all but finitely many players win.

(The same holds for finitely many players too, but a strategy where all but finitely many players win is less impressive there.)

mananaysiempre• 4 years ago

everyone can tell what equivalence class E has been assigned even without knowing their own hat color

As is usual for such AC-dependent things, telling the class here is not (Turing) computable, right?

lupire6• 4 years ago

Yes. It requires the Axiom of Uncountable Choice.

less_less4• 4 years ago

Nothing here is Turing computable because it's infinite, but telling what class you're in is the easy part. The class is just all assignments (player -> hat color) that are the same as what you see except in finitely many places.

The hard part is F, which maps each equivalence class to some member of the class.

halpmeh3• 4 years ago

What does it mean to differ by finitely many places when C is infinite? Imaging C is all the rational numbers from 0 to 1. The size of each equivalence class would be exactly 1. There must be some other condition on C for this to work.

less_less4• 4 years ago

Suppose you have two hat color assignments. These are maps U,V from eg the natural numbers (countably many players) to C, where C in this example is all rationals in [0,1]. On some inputs, U and V may output the same value, and on other inputs they may output different values. Call this latter set Diff(U,V) := { x in Naturals such that U(x) != V(x) }.

U and V are "almost the same" if Diff(U,V) is a finite set.

This is an equivalence relation because if Diff(U,V) is finite, and Diff(V,W) is finite, then Diff(U,W) is also finite: it's a subset of the union of the other two.

The same relation exists, and is an equivalence relation, for any set of players and for any set C of hat colors. It even exists if there are only finitely many players, but it isn't interesting: in that case all assignments are equivalent.

HelloNurse• 4 years ago

A single step (deciding the equivalence class) requiring infinite knowledge (equivalence classes of infinite hat types) and infinite data (the observable hats) instead of the more usual infinite sequence of finite steps. Interesting, but still impossible.

openasocket• 4 years ago

This is the problem I was given in my set theory class that convinced me that the axiom of choice is really doing something weird. There's also the Banach-Tarski paradox, but the proof for ultafilters is very simple and approachable.

syzarian11• 4 years ago

The weirdness comes from uncountable sets. Where choice fails you can have models that have equally bizarre results.

halpmeh3• 4 years ago

At least in my understanding, some of the weirdness of this specific problem comes from the fact that the mathematicians "know" the function. The AoC doesn't necessarily let you know what the function is, it just lets you know that it exists. So if you were to really play the game with infinite mathematician, nearly everyone would lose even with the AoC.

guerrilla• 4 years ago

AC by itself implies only vapourware. However these zombie-like objects like the voting scheme are necessary for the smooth functioning of the mathematical universe. Without them the universe is chaotically irregular.

So, considering we just covered a bunch of reductio ad absurdum proofs, AC is false and the universe is chaotically irregular. I'm just being rhetorical, as I suspect it's more technical than that but why do people not see things that way? Whenever people talk about AC, all I hear is a bunch of reasons why ZFC is inconsistent or at the very least incoherent in some weaker sense. How is the Banach–Tarski paradox not just a refutation of the ZFC axioms taken as a whole?

lupire6• 4 years ago

Yes, the computable, countbale universe is incompatible with ZFC.

But ZFC is math, not computation or physics. ZFC is consistent with itself, which is good enough for math.

You don't even need AoC to run into this. Even the "tame" smooth functions of classical physics (like f(x)=x^2) are a non-physical approximation to discrete reality.

red_trumpet2• 4 years ago

Bold to assume that reality is discrete.

Tainnor3• 4 years ago

ZFC is consistent with itself, which is good enough for math.

That's what we believe, but we don't know it. Nor do we have any hope of proving it in some reasonable way (via Gödel's second incompleteness theorem).

tom-thistime• 4 years ago

I think he's talking about the mathematical 'universe,' not the universe we live in. Apparently it's not so obvious what's absurd in the mathematical universe.

Alternatively, maybe you and I can define 'absurd' very solidly, then go and overturn large portions of current mathematics. But I'm guessing that's more difficult than it sounds.

tromp• 4 years ago

majority rule. If the voters are v0, v1, v2, … vn-1 then the proposal is accepted if at least n/2+1 are in favour.

That's not quite correct for odd n, where a proposal is accepted if at least (n+1)/2 are in favour...

Karellen• 4 years ago

I also don't get:

    Then we require the following properties to hold:
    [...]
    * The result of removing a single voter from a majority is still a majority.

I'm not sure how that property always holds.

danbruc3• 4 years ago

But what if there are infinitely many voters v0, v1, v2, … ? What does it mean for there to be a majority in favour? AC implies that there exists an infinitary voting scheme but supplies not a hint about how it could work.

This already leaves me confused. I thought the axiom of choice says that it is possible to obtain an [infinite] set of votes from an [infinite] set of voters each with a non-empty set of choices, not that there is a way of combining a single [infinite] set of votes into a voting result. I guess it also says that there is a way to pick one of the votes from the [infinite] set of votes, but how does it imply that this choice can or must conform with the properties we want from a voting scheme?

carstimon• 4 years ago

I thought the axiom of choice says that it is possible to obtain an [infinite] set of votes from an [infinite] set of voters each with a non-empty set of choices

The axiom of choice does say this but,

1) This is not where we are applying the axiom of choice

2) You don't need the axiom of choice here: you can always just pick the "voting set" where everyone votes for choice # 1.

The axiom of choice says that the product of infinitely many non-empty sets is empty. This is needed only when you might have a different and non-computable set of choices to make at each step.

Where we are applying the axiom of choice here is: the voting scheme is just a rephrasing of an "Ultrafilter on the power set of a set": https://en.wikipedia.org/wiki/Ultrafilter#Ultrafilter_on_the... This is implied by the axiom of choice in a way that requires some working out (and is sketched in wikipedia). But you can roughly see how the axiom of choice comes about if you start trying to construct a voting scheme (the following is just intuition):

1) We know the result if the number of "Nays" or "Yays" is finite.

2) Pick any set of "Yays" so the number of "Nays" and "Yays" is both infinite. Declare this set (arbitrarily) as a victory for either "Nay" or "Yay"

3) The set in (2) implies that a bunch of other sets are either Nay or Yay by the axioms in the article (e.g. flipping all votes flips the outcome, etc)

4) While there are sets we haven't decided on, repeat steps (2) and (3).

Of course (4) is the whole tricky part, since you have to describe with this "looping forever" means rigorously... but you can see how the idea of "making infinitely distinct choices" comes up.

bmacho5• 4 years ago

The axiom of choice says that the product of infinitely many non-empty sets is empty.

You mean non-empty.

afiori2• 4 years ago

In this context I believe that the author is thinking of AC as Zorn's Lemma.

I will try to make a draft of a possible expansion of the reasoning.

Take the set V of functions P(N) -> {Ma,Mi,Un} that for each subset of the naturals classifies it as a majority, a minority, or undecided respecting the conditions in the article.

P(A) = Ma ⇔ P(A') = Mi

P(A) = Ma ⇔ P(A ∪ B) = Ma

P(A) = Ma ⇒ P(A \ {n}) = Ma

P(A) = Ma ∧ P(B) = Ma => P(A ∩ B) = Ma

It is easy to prove that such a function exists f_0 (A) = Mi if |A| ∈ N, f_0 (A) = Ma if |A| = ∞, and f_0 (A) = Un otherwise.

It is harder to prove that there is a such a function that also respects P(A) = Ma ∨ P(A) = Mi for subsets of the naturals.

I believe that to prove this you pretty much have to use Zorn's Lemma with the order f ≤ g ⇔ (f(A) ≤ g(A)) for all A where Un ≤ Ma, Un ≤ Mi, but Mi ≰ Ma and Ma ≰ Mi.

I feel like you can prove that the hypothesis of Zorn's Lemma are satisfied in this case.

But is is easy to see how without ZL or something similar you would have to decide one-by-one how whether each non-finite non-cofinite set maps to Mi or Ma, but there are uncountably many of them to do by simple induction.

danbruc3• 4 years ago

Would the odd end even numbers not both be classified as Ma by f_0 and therefore violate the first condition?

danbruc3• 4 years ago

Okay, I got this, the axiom of choice is not even needed for finite sets of choices, it comes into play elsewhere. But there are quite a few more points where I can not understand the reasoning behind. Not saying that they are incorrect, only that they are not obvious to me.

Given any set of voters, either it or its complement is a majority, but not both

Why no draws, like the odd numbered voters versus the even numbered voters?

The result of removing a single voter from a majority is still a majority.

This is not true for finite sets of voters, why would we require it for infinite sets of voters? This seems more like a possible consequence of dealing with an infinite set of voters than something one would require in advance.

The intersection of two majorities is a majority

Also not true for finite sets of voters, so the same question as above.

PaulHoule2• 4 years ago

With his constructivist program I wish Steve Wolfram would just grow some balls and firmly reject the Axiom of Choice. (e.g. Mathematica at best can represent a measure subset 0 set of the phony numbers, the numbers that Mathematica can represent are more real than the rest of them.)

His whole approach of throw a lot of things at the wall and seeing what sticks is never going to sample all of the objects requiring an infinite choice procedure to find.

hackandthink3• 4 years ago

And we should switch to constructive reals in software.

IEEE floats suck and mathematicals reals are in general not computable.

PaulHoule2• 4 years ago

I've long held that floating point with a decimal exponent would help a lot more people feel like computing is something they can be a part of. That is, I think the non-professional programmer finds that

  0.1 + 0.2 != 0.3

is one of many little problems that adds up to them giving up the possibility of using software to put their skills on wheels. Like many reforms in computing, performance is used as an excuse to maintain the status quo of the priesthood. IBM is the only company in the industry that's taken this seriously, see

https://en.wikipedia.org/wiki/Decimal_floating_point

cvoss• 4 years ago

But equality over the constructible reals is not decidable either.

A constructible real number is essentially a suspendable computer program that outputs the next digit of the number whenever you ask for it, in finite time. With some work you can define operations like addition and multiplication of such objects. But if you try to define an equality test, you will find that the algorithm will correctly differentiate distinct numbers in finite time, but will not terminate on equal numbers (how many digits have to agree before you know they are the same?). Deciding equality here requires a halting oracle.

constantcrying2• 4 years ago

IEEE floats

Having a fixed size datatype which can emulate the reals to a degree satisfying most applications is really amazing. They are one of the best designed datatypes.

You can also use just floats to calculate mathematical true results.

hackandthink3• 4 years ago

This is a nice article:

https://aperiodical.com/2022/03/now-im-calculating-with-cons...

syzarian11• 4 years ago

There are a lot of seemingly bizarre consequences of the Axiom of Choice. This is well known. Sometimes people haven’t seen a list of bizarre consequences when the Axiom of Choice is dropped. Here’s a nice write up of this:

https://mathoverflow.net/questions/20882/most-unintuitive-ap...

ithinkso• 4 years ago

This is not exactly a list when AC is dropped but if one takes as an axiom 'Axiom of Choice is false'

syzarian11• 4 years ago

In a given model the axiom is either true or false. When I say “dropped” I mean “false” in that model. It isn’t true that in all models where choice fails we have fields with no algebraic closure.

ouid• 4 years ago

my favorite joke about this is:

"the axiom of choice is obviously true, and the well ordering principle is obviously false, but Zorn's lemma? who can say?"

bmacho5• 4 years ago

Imagine having countable infinite many prisoners, put hats on them colored with 0-1 real numbers, and let them to guess their own colors. And then all but finite many prisoners guess their color correctly.

Would you believe in axiom of choice now, wouldn't you?

syzarian11• 4 years ago

I don’t understand your point. There are seemingly bizarre consequences of choice and of the negation of choice. They revolve around uncountable sets. For me, the bizarre thing is uncountable sets. I’m fine with them existing in ZFC and use them when doing mathematics but uncountability is bizarre.

Brigand• 4 years ago

How would that work?

sharpneli• 4 years ago

This seems very weird. Where does this come from?

I'd assume none will guess correctly because you have countably infinite guesses from uncountably infinite set (the colors) so the set of guesses is very sparse, meaning pretty much none will hit it.

How on earth can almost all hit a point in a continuum exactly with random chance?

phs• 4 years ago

“The Axiom of Choice is obviously true, the Well–ordering theorem is obviously false; and who can tell about Zorn’s Lemma?" -- Jerry Bona

yamrzou• 4 years ago

Are all bizarre consequences related to infinity or infinite sets?

syzarian11• 4 years ago

Yes. I’m not an expert in this area but the intuition for finite sets is well modeled by the standard axioms of set theory and I’ve never heard of an issue with finite sets. Things like Russell’s Paradox had to do with constructing sets when the foundations for doing this weren’t well established. Countably infinite sets are fine too, for the most part. The truly weird results come from uncountably infinite sets.

hackandthink3• 4 years ago

The constructive axiom of choice is fine.

It's quite subtle, Per Martin-Löf:

"There is therefore a need to investigate how the constructive axiom of choice, validated by the Brouwer-Heyting-Kolmogorov interpretation, is related to Zermelo’s axiom of choice ..."

https://michaelt.github.io/martin-lof/One-hundred-years-of-Z...

MarkPNeyer• 4 years ago

What are the things that “break” if the axiom of choice is false?

I’ve been wondering if the axiom of choice has some relationship to an argument for the existence of free will. Not just because they share a name, but because you can think of physics as being a multiplayer game.

ogogmad• 4 years ago

This is coming from the opposite extreme. In constructive mathematics, abandoning Countable Choice may allow:

- The complex numbers to not be closed under square roots.

- Space-filling curves to no longer exist.

And subtle complications around:

- The definition of a real number. The Dedekind and Cauchy real numbers may become non-isomorphic.

As it stands, the following has not been validated in constructive mathematics without countable choice:

- That the Dedekind real numbers are uncountable.

- That if a function over the Dedekind reals has derivative 0 everywhere, then it's constant.

On the other hand, the Approximate Intermediate Value Theorem has been proven, but with a weird proof.

See here [1] for more. [1] - https://ncatlab.org/nlab/show/countable+choice

loicd3• 4 years ago

The idea that the axiom of choice is guilty of all the non-constructible, weird stuff in mathematics is incorrect. The actual source of non-constructibility is always the law of excluded middle (aka the difference between classical and intuitionistic logics). What is true however is that the axiom of choice amplifies in a non-trivial way the non-constructibility of the law of excluded middle.

To pick an analogy, consider the 2022 world cup. There will be a winner, but we don't know it yet. Thus, in a sense, the existence of the winner is non-constructible. In classical logic, we accept as true the following statement:

    Either France is the winner or the 2022 world cup, or it is not,

even though we cannot tell which it is now. This is not a problem, because if we wait a bit, we will be able to determine which it is. The axiom of choice in that analogy amplifies the above non-constructive problem by allowing us to wait an infinite amount of time.

In the end, the reason why the axiom of choice 'won' is the same as the reason why classical logic 'won' over intuitionistic logic: because constructibility gets in the way.

whatshisface• 4 years ago

I don't think you can say that classical logic won over intuitionistic logic when the former is thousands of years older and the latter is a growing area of research interest.

agalunar• 4 years ago

It's interesting that although you can't prove "forall P, P or not P" in intuitionistic logic, you can prove "forall P, not (not (P or not P))". In other words, it can't possibly be the case that P is not either true or false.

This is particularly easy to do in Coq:

  Theorem lem : forall (p : Prop), ~ ~ (p \/ ~p).
  Proof.
    tauto.
  Qed.

I personally like the distinction between "this is true" and "this can't possibly be false". If you have a proof of the second, you know why something must be true; if you have a proof of the first, you know how something is true.

The rejection of double-negation elimination is more or less the (rather intuitive) idea that knowing why something must be true doesn't automatically mean you know how it's true.

loicd3• 4 years ago

The rejection of double-negation elimination is more or less the (rather intuitive) idea that knowing why something must be true doesn't automatically mean you know how it's true.

Exactly. There is also the matter of efficiency: it is easier to know why something must be true than to know how it's true. Constructibility in mathematics usually means proving things the hard way.

infogulch• 4 years ago

The actual source of non-constructibility is always the law of excluded middle

I gotta ask, are there alternative formulations of LEM that are still useful but cause fewer problems for constructibility?

loicd3• 4 years ago

There are weaker forms, those accepted in intuitionistic logic. The law of excluded middle usually appears in mathematical proofs in the form of reasoning by contradiction:

  To prove A, assume not-A and reach a contradiction

This is the non-constructible reasoning par excellence, but the following weaker form is constructible:

  To prove not-A, assume A and reach a contradiction

Intuitionistic logic also allows so-called Ex Falso:

  To prove A, reach a contradiction (without assuming not-A)

Now, if what you wanted is a form of LEM that is non-constructible but 'less' non-constructible than LEM, then I don't know.

bmitc3• 4 years ago

Regarding mathematical existence, one thing that I have thought about before and don't have an answer for or understanding of is the concept of infinities. In set theory, there are cardinalities that are "infinities of infinities". This is all fine and makes sense within the world of mathematics, as the study of idealized structures. But what makes me curious is that the universe is finite, and thus presumably, contains a finite amount of information. That is, the universe has a finite amount of bits that can be used to represent information.

How does this work then? We can represent these sets of cardinality infinities of infinities in our brain and on paper, but representing these sets with all the available bits in the universe is not possible. This seems like a paradox, because our brains and paper are part of the universe.

Does anyone have some thoughts on this? Is this a well-discussed problem? Any good references?

sapiol4• 4 years ago

We can encode the idea of infinite sets and their relationship to one another with a finite set of symbols. But we can't enumerate those sets. Edit: How is there a paradox?

bmitc3• 4 years ago

We can encode the idea of infinite sets and their relationship to one another with a finite set of symbols.

I have thought about this, but it isn't entirely clear to me. For example, what is the bit encoding of the real numbers? Is it really accurate to say we have an encoding of them by just saying we have the set R?

But we can't enumerate those sets.

Well, that's kind of the point of my question. Is this not an issue?

feoren• 4 years ago

Why should the limits of our universe have anything to do with the limits of math? Math is bigger than our universe. If our universe were completely different, math would still be the same.

We can represent these sets of cardinality infinities of infinities in our brain and on paper, but representing these sets with all the available bits in the universe is not possible. This seems like a paradox, because our brains and paper are part of the universe.

Eh, I can write a recipe that calls for multiple universes-worth of flour and 600 trillion years in the oven, and I can write that recipe in a minute on an index card that weighs a couple grams. I can write small programs that loop infinitely or (attempt to) use infinite memory. I can write a song that repeats ad infinitum that nobody can ever sing to completion in the entire lifetime of the universe. That's not much different than the words "the Integers" requiring 2 words but describing something that could not possibly be "fully materialized" in any finite universe. Who cares?

What those all have in common is that despite being very big or long in some sense, they have low Kolmogorov complexity. It's very easy to describe "recipes" for infinite things that would exceed the bounds of the universe if they were ever fully realized; you don't even need higher cardinalities for that.

https://en.wikipedia.org/wiki/Kolmogorov_complexity

What higher cardinalities do tell us is that there must be some real numbers that have infinite Kolmogorov complexity, and in fact 100% of the real numbers have this property. (Of course all the numbers you have/will ever have heard of are in the remaining 0%.) There are only countably many (the smallest infinity) descriptions in any language (programming or natural), so most reals must not be "describable" at all. We will never be able to meaningfully use any of those numbers, because we couldn't possibly "compute" them -- we can't run the infinitely long program. It's not clear to me that we'd ever be able to learn anything at all about such numbers, or indeed that they "exist" in any meaningful sense.

bmitc3• 4 years ago

Why should the limits of our universe have anything to do with the limits of math?

Mathematics is a human activity, and humans are part of the universe.

Math is bigger than our universe.

What does that mean?

If our universe were completely different, math would still be the same.

That is more than debatable.

Eh, I can write a recipe that calls for multiple universes-worth of flour and 600 trillion years in the oven, and I can write that recipe in a minute on an index card that weighs a couple grams. I can write small programs that loop infinitely or (attempt to) use infinite memory. I can write a song that repeats ad infinitum that nobody can ever sing to completion in the entire lifetime of the universe. That's not much different than the words "the Integers" requiring 2 words but describing something that could not possibly be "fully materialized" in any finite universe. Who cares?

I think you're skipping over the point. No one is going to argue with you about "multiple universes-worth of flour" existing because to our current knowledge, the universe is finite and thus there is a finite maximum to how much flour can exist. My question revolves around the philosophical question of the existence of mathematical objects and whether they can or cannot be actually realized with the given information in the universe. This is not a question out of left field. The acceptance of the real number continuum is not even settled.

Thanks for the reference to Kolmogorov complexity.

edanm• 4 years ago

How does this work then? We can represent these sets of cardinality infinities of infinities in our brain and on paper, but representing these sets with all the available bits in the universe is not possible. This seems like a paradox, because our brains and paper are part of the universe.

The "paradox" arises because you're using the word "represents" in two different meanings.

For example, the number TREE(3) is extremely big (to put it mildly.) If you haven't heard of it you can search Youtube, there's a few Numberphile videos on it that are wonderful.

Anyway, TREE(3) is extremely big but finite. I can explain exactly what TREE(3) is. You can understand what it is. I can therefore "represent" it, and you can have an exact picture of your head of how to write a computer program that calculates it.

It is, of course, much too big to "represent" it by writing down all its digits in base 10. There's not enough bits in the Universe.

But these are two different senses of the word "represent".

In a similar way, I can "represent" sets of infinites very easily, in the sense that I can explain to you what they are and how they behave. I mean, every schoolchild knows about a set that's infinite - just the regular old counting numbers. The set of counting numbers if infinite - there is no way to actually write down all of these numbers, within our universe.

But I can still explain to you what that set is, and how it behaves. Everyone understands that the behavior of it is that you can keep pulling out more numbers from it. That's all that "representing" it is in this context.

Mathematical Existence and the Axiom of Choice

Related Stories