[HN Gopher] A Bad Trip to Infinity
___________________________________________________________________
A Bad Trip to Infinity
Author : herodotus
Score : 40 points
Date : 2023-03-25 17:57 UTC (5 hours ago)
(HTM) web link (billwadge.com)
(TXT) w3m dump (billwadge.com)
| Adraghast wrote:
| > The average intelligent viewer will be left confused and
| intimidated
|
| I'm not qualified to know if your post is better or worse than
| Netflix's documentary, Bill, but this is an egregious example of
| a pot calling a kettle black.
| btilly wrote:
| I am qualified to figure that out.
|
| The post may be confusing, but it gets its math correct. And
| describes the documentary getting it wrong. So the post is
| probably better.
| mike_hock wrote:
| To be fair, it does a decent job of plowing through set theory
| in only a short rant about why the documentary is bad,
| forgetting to rant about the documentary because there's so
| much math to cover.
|
| It only commits the cardinal sin of trimming it down so much
| that it makes sense if and only if the reader is already
| familiar with it, leaving other intelligent readers confused
| and intimidated.
| hgsgm wrote:
| What's the ordinal sin?
| jpcfl wrote:
| It's been a while since I took a theoretical math class, so I'm
| struggling to remember how some infinite sets can be larger than
| others. The "one-to-one correspondence" definition given in the
| article is throwing me off.
|
| If you have two infinite sets, then isn't it always possible to
| map an element from one to a new element in the other, because
| there's an unlimited number of elements to pick from?
| mike_hock wrote:
| Whether a set is finite or infinite, its power set is always
| bigger.
|
| Let S be any set and assume f: S -> P(S) exhaustively
| enumerates the subsets of S using only elements of S.
|
| Then define a new subset L of S: For each s in S, we decide
| whether to include s in L as follows: If f(s) contains s, then
| L shall NOT contain s, if f(s) does not contain s, then L DOES
| contain it.
|
| No s in S can be a preimage of L under f, since L disagrees
| with f(s) about whether it contains s or not, by construction.
| So f must have missed L. So P(S) is strictly larger than S.
|
| Nothing about infinities in there. You can't have a surjective
| mapping from any set to its power set, ever.
| hprotagonist wrote:
| it isn't always possible, and cantor's proof demonstrates that
| neatly, by giving an algorithm to construct (an infinite number
| of) counter-examples of non-mappable elements of the larger
| set.
| andybak wrote:
| I'm no expert but I think the trick is to say "give me a
| function that for any element in Set A, returns a matching
| element in Set B".
|
| For mapping integers to even numbers it's f(x)->x*2
|
| But for mapping integers to real numbers - there is no possible
| mapping.
|
| Cantor's Diagonal Argument is really easy to follow - watch a
| YouTube vid or two on the topic. Also Hilbert's Hotel is well
| covered.
| [deleted]
| xtagon wrote:
| Is the set of all odd numbers smaller than the set of all even
| and odd numbers together? If not, then if you were to merge the
| set of all even numbers to the set of all odd numbers, did you
| really merge anything since the set didn't grow?
| syzarian wrote:
| Intuition tends to breakdown when dealing with infinite sets.
| This is especially true for uncountable sets. Instead
| thinking about enlarging or merging sets think of indexing
| things. The odd numbers can index in a unique way just as
| many things as the set of all integers.
| ironSkillet wrote:
| The real numbers (everything on the number line, including
| things like 1, 0, 4/237, and pi) and the integers have no such
| correspondence. The reals are an "uncountable" infinity.
| aidos wrote:
| It's been a while for me but the main thing you need to
| consider is bijections. If you can find a mapping for each A ->
| B and conversely each B -> A then they're the same size.
|
| Consider the rational numbers. They can all be written as x/y.
| It's clear that you can map from rational to natural as x/1 ->
| x. Now imagine a 2d grid of natural numbers on each axis. You
| can spiral out from (0,0), (0,1), (1,1), (1,0) etc in a loop.
| Now you have a way of mapping from the natural numbers to the
| rational numbers. So they must be the same size.
| aidos wrote:
| To clarify. There is no mapping from natural numbers to all
| the irrational numbers. And that's why there are different
| sized infinities
| nico wrote:
| Why not?
|
| There's no case in which you can have a complete map
| anyways.
|
| If you say one infinity is larger/smaller than another,
| you'd be saying that the complete map for one is
| larger/smaller than for the other one.
|
| But if they are both infinite, you will never stop
| counting, so you just can't know.
|
| I know the diagonalization argument. But reality is that
| you can't even count natural numbers.
|
| So if you have finite time to count any set, the set will
| be finite, and so it's countable.
|
| But if you have infinite amount of time, any set for which
| there's a formula to produce an element of, will always
| produce infinite elements at whatever speed you are able to
| produce them.
|
| If one formula is faster than another (eg n=(n-1)+1 vs
| n=(n-1)!), then you will count more of one than the other
| in the same amount of time, but that is processing power,
| not the size of the sets.
| haneul wrote:
| You can count natural numbers. Elementary school children
| do it every day. Now, try to count the real numbers. What
| comes after 1?
| nico wrote:
| > What comes after 1?
|
| Whatever I want.
|
| Why do you have to produce them in some predefined order?
|
| You could generate random real numbers, one at a time,
| and sort them as you add them to your set.
|
| When you stop, you will have a set of real numbers in
| order. If you want to know where a new one goes, you just
| generate it, add it to the set and sort it (or just add
| it in the proper position).
|
| And you will have a finite set of real numbers.
|
| If you never stop, you will keep forever generating real
| numbers, exactly the same as you would with natural
| numbers.
|
| The only thing that matters is whether you stop counting
| or not.
|
| If you stop counting, you get a finite set.
|
| If you don't stop counting, you get an infinite one (but
| you'd never finish generating it).
|
| There is no way for a human to count for infinite time...
| so we can only speculate about that case.
|
| The only case that will ever occur in reality for us, is
| the finite case.
| roywiggins wrote:
| The idea behind Cantor's diagonalization proof is that
| you can't find _any_ way to assign "first", "second,"
| "third", etc to the reals. The proof assumes that you
| can, and that you've already assigned every real number a
| unique natural number.
|
| It then derives a contradiction by proving that there
| must be reals that aren't in that ordering, without
| making any assumptions about the ordering. So _any_
| ordering has this problem and none of them work.
| LegionMammal978 wrote:
| > There is no way for a human to count for infinite
| time... so we can only speculate about that case.
|
| We can talk about whether or not a countably infinite
| sequence S contains a given element x. We iterate through
| each element s of S one-by-one. If x is contained in S,
| then eventually we will find an element s such that s =
| x. But if x is not contained in S, then we will keep
| iterating for all eternity.
|
| For all countably infinite sets, we can always produce
| such a sequence, where the iteration will eventually halt
| if and only if the element is contained in the set. But
| for the set of real numbers, _no matter what sequence we
| choose_ , we will never ever find the diagonalized number
| in our sequence. That's why we call the set of real
| numbers uncountable.
|
| You dispute that we can't physically count through all of
| the infinite elements in the real world. But math has no
| problem talking about what would hypothetically happen if
| we were to try. It lets us prove ahead of time that
| certain events will eventually happen if we iterate long
| enough, and other events will never ever happen.
| nico wrote:
| > But for the set of real numbers, no matter what
| sequence we choose, we will never ever find the
| diagonalized number in our sequence.
|
| So then it's only proving that if you choose the ordering
| ahead of time, you won't be able to do it, because real
| numbers don't have a predefined order. You can only order
| them as you produce them.
|
| If you re-sort after each iteration (or insert them in
| order), you can count as many real numbers as you want.
|
| In any case, for practical applications, you could never
| count anything infinite, at some point you'd run out of
| physical storage to keep the count.
|
| How many bits can be encoded in the universe? That will
| give the limit of what could ever be counted. And it's
| not infinite.
| hgsgm wrote:
| We're talking about infinity, not practical
| considerations.
|
| > (or insert them in order),
|
| There is no order. You can't describe one, and it is
| proven that no order exists.
|
| > you can count as many real numbers as you want
|
| No, you can't count more than 0% of them, even in
| infinite steps.
| LegionMammal978 wrote:
| > So then it's only proving that if you choose the
| ordering ahead of time, you won't be able to do it,
| because real numbers don't have a predefined order. You
| can only order them as you produce them.
|
| What's the problem? You just produce the diagonalized
| number at the same time as you produce your order. Every
| order you produce them in has its own corresponding
| diagonalized number that will never be produced.
|
| > If you re-sort after each iteration (or insert them in
| order), you can count as many real numbers as you want.
|
| You can count as many real numbers as you want, but none
| of them will ever be equal to the diagonalized number.
| (That is, in finite time, you will always be able to find
| a digit that differs between the two numbers.)
|
| > How many bits can be encoded in the universe? That will
| give the limit of what could ever be counted. And it's
| not infinite.
|
| How do you know the universe isn't infinite?
|
| Regardless, I don't see why we shouldn't consider formal
| systems in which infinite amounts of information can be
| manipulated. Even in our finite light cone, mathematical
| statements about infinite sets can help us separate the
| possible from the impossible. For instance, mathematics
| tells us that adding 1 to any integer will never produce
| the same integer. There are infinitely many integers, so
| we can't experimentally verify this in the real world.
| But if we accept that abstract statement, then we know
| what to expect when we do try to physically add one
| object to a group of objects.
| haneul wrote:
| If as you say, the infinity of the real numbers lacks the
| property of predefinable order, whereas the infinity of
| the natural numbers does have that property, does it not
| strike you that those infinities may be fundamentally
| different in some way relating to size, and therefore
| mapability?
| haneul wrote:
| You're avoiding the difference. You can count (for
| example via generator function), the natural numbers,
| though you may never finish. Typically, people generate
| via numerical order, so 1, 2, 3, 4,...
|
| Now try doing that with the real numbers. You explicitly
| said you can sort them after. So, tell me, what comes
| immediately after 1, so I can attempt to convince you
| that it does not.
|
| In other words, that the real numbers only have local
| sorting, not global sorting, whereas the natural numbers
| have both.
| roywiggins wrote:
| It's not obvious how to order the rationals either, but
| there are of course loads of orderings that work, and it
| turns out that they can easily be put into correspondence
| with the naturals. Such orderings are not from lowest to
| highest, obviously, but they exist, and you might
| naturally assume there's one for the reals.
|
| The thing with the reals is that _no_ orderings work,
| that 's what Cantor's diagonalization proof does.
| nmilo wrote:
| Countable (roughly) means that you can count from one
| element to any other in a finite amount of time, it
| doesn't mean you can count the whole set in a finite
| amount of time.
| nico wrote:
| Think about counting as three operations:
|
| 1. Produce a number 2. Add it to the set of numbers I'm
| counting 3. Sort the numbers
|
| Usually when you produce a number, you produce it in
| order (eg. 1, 2, 3, 4). But you could also count like: 4,
| 1, 3, 2 and then sort the set.
|
| As long as you have an algorithm/function to keep
| producing numbers for "each iteration", you can always
| keep counting one at a time.
|
| The case you say: "count from one element to any other"
| is equivalent to a finite operation, it has a very clear
| beginning and end. But an infinite set doesn't, unless
| you stop counting.
| nmilo wrote:
| I think you're mixing up math and natural language. A
| "countable set" in math, by definition, means what I said
| it means, (or more precisely means it is 1-to-1 with the
| natural numbers). You can argue that the word itself is
| misleading/unclear, but that's a semantic argument and
| you should make clear that that's your stance.
| cscurmudgeon wrote:
| > Think about counting as three operations: > 1. Produce
| a number 2. Add it to the set of numbers I'm counting 3.
| Sort the numbers
|
| Missing in your definition is the operation has to
| produce all numbers that you are counting over.
|
| If you are counting something, you don't leave out
| elements.
| nico wrote:
| If you are counting a set that is larger than your count,
| you will always leave elements out.
|
| The only way you won't leave elements out for an infinite
| set is if you keep counting forever.
| scythe wrote:
| We can say a lot about infinity. But for people who don't study
| advanced math by choice, the first question is _why_ are we
| talking about infinity, when we don 't normally, in our
| physical world, encounter infinite amounts of anything.
|
| The answer is pretty simple: it is easier to work with infinity
| than with a large finite number, and by working with infinity,
| you discover similarities among situations in which you
| encounter different "large finite numbers". So, for example, it
| is easier to study a circle than a polygon with a million
| sides. In statistical physics we say that the heat capacity
| "diverges" at a phase transition, but of course a real material
| must absorb a finite amount of heat at a phase transition;
| nonetheless, we treat "macroscopic" as "infinite" freely,
| knowing that any errors will be far below measurement
| limitations.
|
| In the above cases, we are dealing with infinity as the limit
| of a particular process. But in order to make the ideas in
| calculus convenient, we want to consider _all_ of the limits of
| _all_ sequences which converge, because it allows us to use the
| concept of _limit_ freely. This leads to the definition of the
| "real numbers" by Dedekind cuts (the topological closure of the
| rationals); it is how we define the "bigger infinity". When we
| say the real numbers are "bigger" than the integers, we can
| explain this in finite-sounding terms as: we cannot define a
| "sequence of all sequences".
| IIAOPSW wrote:
| >If you have two infinite sets, then isn't it always possible
| to map an element from one to a new element in the other,
| because there's an unlimited number of elements to pick from?
|
| No. Consider the set of integers vs the set of real numbers.
| Suppose I have a 1 to 1 mapping from integers to reals. Lets
| pick an example of such a mapping to demonstrate.
| 1 - .152345... 2 - .897454... 3 - .908345...
| ...
|
| Now I can always construct a new real number by going down the
| diag, taking the first digit of the first number, second digit
| of the second, etc, and selecting a different number than that
| (say, by doing +1 mod 10). In the example this new number would
| be .209... By construction, this number doesn't match any real
| number already on the list.
|
| Therefore, after mapping all the integers to real numbers,
| there's still left over real numbers. Hence the reals are a
| larger infinity than the ints.
| cjohnson318 wrote:
| I always explain this with binary digits. You can always
| construct a new one from the diagonal by flipping each bit. I
| think the smaller domain {0,1} instead of
| {0,1,2,3,4,5,6,7,8,9} keeps people from getting distracted
| and trying to find a loophole.
| hgsgm wrote:
| Binary is the only base where that proof does not work well
| easily, because 100000... = 011111... in a metric system.
| btilly wrote:
| Responding as a constructivist would.
|
| Let's define real numbers in a concrete way where they
| certainly exist, such as by equivalence classes of Cauchy
| sequences. Where a Cauchy sequence is a computer program that
| takes in a natural number, and returns a rational, complete
| with a proof that the rationals that it spits out will
| converge at a calculable rate.
|
| Your mapping can now be constructed from an enumeration of
| such programs. (A single real may appear many times because
| many programs are equivalent. That's just a detail.) For each
| program we can put in a large enough number that we get the
| decimal place down to one of two. (The old 0.9999.... = 0
| problem is a small complication here.) And then we pop out a
| clearly different digit. Given the mapping, this program can
| be easily written. And so we can produce our number which
| starts off in your example as the sequence .6, .64, .643, ...
| .
|
| So far, so good. But what goes wrong?
|
| Well we have a program that we assert produces a real. It
| certainly seems to do so. But proving that it represents a
| real requires proving that the program will always give the
| next digit. That requires proving that it works as
| advertised. That requires proving that the logic we used to
| make all of our decisions is consistent. But by Godel's
| Incompleteness Theorem, we can only prove that if our logic
| is INCONSISTENT. And therefore our nice program doesn't have
| a proof that when ask for the n'th rational that it will ever
| return anything. And therefore it doesn't represent a real
| number!
|
| This is why Cantor's diagonalization argument fails in
| constructivism. The impossibility of making a one-to-one map
| between naturals and reals becomes a statement about the
| self-referential logic embedded in the definition of real
| numbers, and NOT a proof that there exist an uncountable
| number of real numbers that we can never write down any
| meaningful description of!
|
| Even if you don't subscribe to constructivism, I think it is
| important to recognize that the confident statements we make
| about infinity in classical mathematics rest on unprovable
| philosophical assumptions of a potentially dubious nature.
| sorokod wrote:
| The "therefore" is not quite right.
|
| You have shown that that the original assumption leads to a
| contradiction and so doesn't hold.
| hgsgm wrote:
| That's incorrect. The assumption was that there was a 1:1
| (injective) mapping, and the proof was that it (regardless
| of it's exact value) wasn't onto (surjective) and so isn't
| bijective.
| sorokod wrote:
| True when replacing "1 to 1 mapping" with "1:1 injective
| mapping"
| xchkr1337 wrote:
| Just picking digits from the diagonal might not work, you
| have to make sure the digits of the new number aren't equal
| to the ones on the diagonal, one way is to add 1 mod 10, in
| the case you showed it would result with 0.209...
| IIAOPSW wrote:
| thanks, I fucked up the easy part lol
| pfortuny wrote:
| Also (this is a very very minor detail) it is best to inly
| consider numbers without the digit eight. Otherwise you
| might end up with 0.99999999 which is one.
|
| This is the tiniest of details but important for precision.
| bryanrasmussen wrote:
| let's consider two potentially infinite sentences:
|
| Buffalo buffalo buffalo buffalo -> infinite
|
| and
|
| Police Police Police Police -> infinite
|
| certainly Buffalo and Police sentences can both be infinite but
| the Buffalo sentence is obviously larger than the Police
| sentence because Buffalo has 7 letters and Police only 6.
|
| https://en.wikipedia.org/wiki/Buffalo_buffalo_Buffalo_buffal...
| CrazyStat wrote:
| This is a bad example. In fact those sentences have the same
| cardinality, much like the set of even natural numbers has
| the same cardinality as the set of all natural numbers even
| though only half the natural numbers are even.
| bryanrasmussen wrote:
| they may have the same cardinality, but one infinite
| sentence is obviously longer than the other infinite
| sentence.
|
| on edit: noting depends on if we consider as elements the
| words, or the letters.
| bryanrasmussen wrote:
| there are some amusing other parts to this of course.
|
| Since Buffalo -> is infinite and Police -> is infinite, but
| Buffalo is larger than Police how much larger is it?
|
| It is obviously infinitely larger.
| jdkee wrote:
| Those two infinite statements have the same cardinality.
| bryanrasmussen wrote:
| they may have the same cardinality, but one infinite
| sentence is obviously longer than the other infinite
| sentence.
|
| on edit: noting depends on if we consider as elements the
| words, or the letters.
| pfortuny wrote:
| Thinking of actions leads you astray. Maps look like actions
| but they are not.
| btilly wrote:
| You can construct a mapping where an infinite number in the one
| are mapped to an infinite number in the other.
|
| You can't always construct a mapping where all of one maps to
| all of the other.
|
| Classical mathematics concludes from this that one set truly
| has more things than the other does. These presentations always
| assume that classical mathematics is right. But it ACTUALLY
| depends on philosophical assumptions that are both unprovable,
| and questionable.
|
| In particular, classical mathematics assumes that it makes
| sense to talk about whether a statement is absolutely true or
| false. And to build constructions that require a series of
| decisions based on the absolute truth value of the statement.
| This despite the fact that we do not know whether it is true,
| have no procedures to determine it, and in some cases the
| statement is independent of our axioms.
|
| Attempts to create finite parallels to this type of reasoning
| inevitably run into self-referential paradoxes and
| contradictions. It appears that classical mathematics avoids
| such paradoxes from the simple fact that nobody can actually
| carry out these impossible procedures. If we could, then we
| would certainly find similar contradictions.
|
| People have attempted to figure out what mathematics would look
| like if we limited ourselves to things we can prove true and
| false, instead of making statements about the truth value of
| things that we have (and may never have) any proof of. The
| results go by names such as "constructivism" and
| "intuitionism". In those systems some infinite sets have more
| self-referential structure, but none has "more" elements than
| any other.
|
| There is no logical reason to choose classical mathematics over
| these alternatives. Only arguments about philosophy and
| convenience help us choose. I wish that this fact was more
| often acknowledged.
| stiglitz wrote:
| You can always "take an element from each set" over and over,
| but for this mapping to be shown to be a 1:1, you need to be
| more specific.
|
| Example: the set of all natural numbers (0, 1, ...) is the same
| "size" as the set of all even numbers, because you can map any
| number N to the number 2N. It's obvious that any natural number
| N is uniquely accounted for by this mapping, since you can
| double any natural number (with a unique even result), and it's
| obvious that any even number is uniquely accounted for, because
| any even number divided by 2 is a (unique) natural number.
|
| But if your mapping is defined as "take an arbitrary rational
| number and arbitrary irrational number, over and over forever",
| then there's no guarantee that, given an arbitrary irrational
| number, your mapping has defined a unique associated rational
| number.
| photochemsyn wrote:
| The 1977 film Powers of Ten is short and simple but gives one a
| better feeling for what infinity represents (40 orders of
| magnitude isn't much in contrast to infinity, but is very large):
|
| https://youtu.be/0fKBhvDjuy0
|
| There's also an hour-long talk by Prof. Raymond Flood on Cantor's
| Infinities on YT that covers all the mathematical history.
| dullcrisp wrote:
| This is a somewhat glib but forty orders of magnitude, being a
| finite number, has no more to do with infinity that any other
| finite number. The nature of infinity is that you can't get
| meaningfully closer to it.
| mcphage wrote:
| > The car shot forward straight into the circle of light, and
| suddenly
|
| > Arthur had a fairly clear idea of what infinity looked
| like.
|
| >
|
| > It wasn't infinity in fact. Infinity itself looks flat and
| uninteresting.
|
| > Looking up into the night sky is looking into infinity -
| distance is
|
| > incomprehensible and therefore meaningless. The chamber
| into
|
| > which the aircar emerged was anything but infinite, it was
| just very
|
| > very big, so that it gave the impression of infinity far
| better than
|
| > infinity itself.
| kmtrowbr wrote:
| This is from one of the Hitchhiker's Guide to the Galaxy
| books. They're with Slartibartfast driving onto the factory
| floor for creating planets. Slartibartfast, as you recall,
| is a famous "world designer" who won an award for designing
| the Fjords of Norway.
| douglee650 wrote:
| _le sigh_ ... still talking about infinities in semantic of
| quantity and size. For me, a better mental model is "relative
| density"
| ilovecurl wrote:
| "They show the equation [?] + 1 = [?], which is true if [?] is an
| infinite cardinal, then proceed to subtract [?] from both sides,
| giving 0=1, a howling contradiction. And that's where they leave
| it."
|
| This reminds me of Terrance Howard's statement that 1 multiplied
| by 1 equals 2:
| https://twitter.com/terrencehoward/status/925754491881877507
| andybak wrote:
| > Instead they're speculating about an orange in a box ... which
| supposedly disintegrates then reassembles itself.
|
| Haven't watched it but that sounds like they were attempting to
| cover the Banach-Tarski Theorem?
| c1ccccc1 wrote:
| I have watched it, and it was actually talking about this:
| https://en.wikipedia.org/wiki/Poincar%C3%A9_recurrence_theor...
|
| Ironically Banach-Tarski would have been better suited for a
| movie about infinity. Poincare recurrence is relevant for
| amounts of time that are merely exponentially large, not
| infinite.
|
| I agree with Wadge that the movie was not very good, but I'm
| not actually sure what his objection is to the bit with the
| orange in a box, it seems fairly reasonable based on our
| current understanding of physics.
___________________________________________________________________
(page generated 2023-03-25 23:00 UTC)