[HN Gopher] How can some infinities be bigger than others?
___________________________________________________________________
How can some infinities be bigger than others?
Author : digital55
Score : 19 points
Date : 2023-04-19 20:47 UTC (2 hours ago)
(HTM) web link (www.quantamagazine.org)
(TXT) w3m dump (www.quantamagazine.org)
| version_five wrote:
| I'd recommend "Journey through genius" by William Dunham. There's
| a bunch of great stuff in there including two chapters about
| Georg Cantor and his explorations of infinity, including how he
| showed there is no 1:1 correspondence between integers and real
| numbers, while there is one between integers and rationals.
| Someone wrote:
| I think the mystery is not that some infinities can be larger
| than others, but that there are infinite sets of equal 'size'
| that conflict with intuition.
|
| Some examples that 'prove' some infinities are larger than others
| to laymen:
|
| - there are twice as many integers as odd integers
|
| - there are more points on a plane then on a line
|
| - there are more points on a line than on a circle
|
| - there are more points on a plane then on a semiplane
|
| - there are more rationals than integers
|
| - there are more reals than rationals
|
| It's only in the intermediate state of a mathematician's
| education, where they have just accepted that, for infinite sets,
| 'more' isn't the best way to determine size equivalence that it
| becomes a surprise that for the last one, "the size of the set of
| reals is larger than that of the rationals" is true, and can be
| proven to be.
| jltsiren wrote:
| Isn't that more like first-year material in mathematics and in
| more theoretically oriented CS programs? Once you start talking
| about injections, surjections, and bijections, you may as well
| prove some basic results about the sizes of sets of numbers.
| yodsanklai wrote:
| There are basically no prerequisites to get a grasp of these
| ideas. I remember being introduced to this in one of Raymond
| Smullyan's book when I was a kid.
| rtkwe wrote:
| > there are twice as many integers as odd integers
|
| > there are more rationals than integers
|
| Both of these are incorrect you can create a 1-1 mapping
| between all of these sets so they are the same "size". Things
| get unintuitive when you're dealing with infinites things that
| feel like they should be larger aren't when you examine them
| rigorously.
|
| For integers to odd integers the mapping is easy for each
| natural number n map n -> 2n+1. Mapping integers to rational
| numbers is more difficult to write into an equation but if you
| lay them out in a a grid defined by numerators and denominators
| x/y you can snake along this grid to eventually map every
| rational number to a corresponding natural number (ie positive
| integers which has the same cardinality as integers).
|
| http://www.cwladis.com/math100/Lecture5Sets.htm#:~:text=the%...
|
| > there are more points on a plane then on a line
|
| Going further R (points on a line) to R^2 (points on a plane)
| is also the same cardinality. The proofs are over my head as a
| 10 years past math minor but they're out there. Including this
| one that goes from R^3 to R.
|
| https://math.stackexchange.com/posts/183383/revisions
| neonskies wrote:
| > Going further R (points on a line) to R^2 (points on a
| plane) is also the same cardinality. The proofs are over my
| head but they're out there.
|
| It's just a matter of finding a suitable set of functions.
| For example, you can try proving |R^2| = |(0, 1) x (0, 1)| =
| |(0, 1)| = |R| where R stands for reals.The middle equality
| can be proven using Schroder-Bernstein theorem.
| hallucy wrote:
| This is literally the point of the comment.
|
| To a layperson not familiar with this approach to measuring
| infinities, all of the examples are "correct".
|
| To a mathematician that hasn't heard of uncountability, all
| are "incorrect". (And learning the last is actually "correct"
| is surprising).
| sleepyams wrote:
| Good points, a large chunk of math is different formalizations
| of the notion of size, for example (in order of increasing
| absurdity):
|
| https://en.wikipedia.org/wiki/Cardinality
|
| https://en.wikipedia.org/wiki/Measure_(mathematics)
|
| https://en.wikipedia.org/wiki/Ultrafilter_(set_theory)
|
| https://en.wikipedia.org/wiki/Euler_characteristic
|
| https://golem.ph.utexas.edu/category/2008/02/metric_spaces.h...
|
| https://golem.ph.utexas.edu/category/2006/10/euler_character...
| dwater wrote:
| It's been a long time since my number theory class, but aren't
| there the same number of integers and odd integers?
|
| Take the set of odd integers {... -3, -1, 1, 3, 5, ...}
|
| For each item, subtract one and divide the result by 2. Now you
| have the set of all integers without any insertions or
| deletions: {... -2, -1, 0, 1, 2, ...}
|
| Therefore the set of odd integers can be mapped 1:1 onto the
| set of all integers so they are of equal length.
| ShamelessC wrote:
| They have the same cardinality.
| renewiltord wrote:
| Your proof is correct.
| [deleted]
| vacuumcl wrote:
| Half your examples are wrong, but maybe it is your point.
| Although it wasn't clear to me the first time I read your
| comment.
|
| - The cardinality of the odd and even integers is the same.
|
| - It is true there are more points on a plane then on a line
| (Cantor's theorem.)
|
| - The circle is the compactified real line, i.e. it can be
| represented as the real numbers with one additional point (the
| point at infinity). In terms of cardinality they are the same
| since they just differ by one point which does not change the
| cardinality.
|
| - There are not more points on a plane than a half-plane, you
| can find a bijective mapping between them easily.
|
| - There are more rationals than integers: not true, they are
| both countable sets of the same cardinality.
|
| - There are more reals than rationals, this is true (again
| Cantor.)
| function_seven wrote:
| Parent is making the same point you are. It's a surprise to
| the intermediate mathematician when the last bullet point
| turns out to be true.
| tinglymintyfrsh wrote:
| https://en.wikipedia.org/wiki/Aleph_number
|
| EDIT: The computer science program was 2 courses from a
| mathematics major. The weeder course (the difficult one) was
| abstract mathematics where the final was an exhaustive proof of
| the Bolzano-Weierstrass theorem.
|
| https://en.wikipedia.org/wiki/Bolzano%E2%80%93Weierstrass_th...
| version_five wrote:
| Something I found interesting, once you understand the proof of
| why there are "more" real numbers than integers, it becomes easy
| to see that the p-adic numbers[0], which can have infinite digits
| to the _left_ of the decimal, but finite digits to the right,
| have the same cardinality as the real numbers (there are more of
| them than integers).
|
| This was unintuitive to me when I first thought about it, because
| I pictured a whole number (no fractional part) even with infinite
| digits, to be in the natural numbers, but in fact it's not. Or
| put another way, whole numbers with infinite non-terminating non-
| repeating digits are not natural numbers
|
| [0] https://divisbyzero.com/2008/11/24/what-are-p-adic-numbers/
| w0mbat wrote:
| The way to answer all these questions is that infinity is not a
| number, it's the absence of a limit.
| daxfohl wrote:
| There's also the projectively extended definition, where positive
| and negative infinity are defined to be the same thing. It has
| some nice properties like division by zero is defined, but you
| lose total ordering of course. In a way that's a good thing
| though because you don't have to worry about how "big" an
| infinity is: it's just a symbol.
| https://en.wikipedia.org/wiki/Projectively_extended_real_lin...
| hn_throawlles wrote:
| i thoguth there are two types of infinities:
|
| by there being no bigger number (classic logic infinity?)
|
| and by 'construction' which boils down to cycles in graphs. even
| two nodes bouncing can do so forever. so then "bigger infinities"
| would mean that there are more nodes in the cycle.
|
| i suppose this gets more and more interesting when adding
| geometry (which involves a basic logic), and then having cycles
| within cycles.
| mopierotti wrote:
| There are many comments saying that one infinity can be larger
| than another because a bijective mapping can't be formed, but why
| does the presence of a mapping imply anything about the "size" of
| an infinity? For any infinite set, you could select unique values
| out of them indefinitely.
|
| From my uninformed perspective, this seems like a co-opting of
| the word "size" to mean something different than its typical
| usage.
| thfuran wrote:
| >For any infinite set, you could select unique values out of
| them indefinitely.
|
| Yes, but if you have a bijection between elements of that set
| and another, they're still the same size. Consider the strictly
| positive integers and the strictly negative integers: for any
| x, there's exactly one corresponding -x. Both sets are
| infinite, but they're the same size. Contrast that with, for
| example, the reals and the natural numbers: for each natural
| number n, there's not a corresponding real number but rather an
| infinite number of reals in [n, n+1). The sets are not the same
| size.
| ufo wrote:
| For finite sets, bijection is equivalent to counting the number
| of elements. A set of size N has an 1-to-1 mapping to the set
| {1,...,N}. For infinite sets, counting no longer makes sense
| but bijection does. From this point of view, the bijection
| trick is a way to extend the usual notion of set size, so that
| it also works for infinite sets.
|
| That said, it's certainly not an "obvious" idea and in fact it
| took many years until it was widely adopted by the mathematical
| community.
| TexanFeller wrote:
| If you couldn't count, you could still figure out that both of
| your hands had the same number of fingers by matching each with
| a corresponding finger on the other hand. In other words there
| exists a bijection between the set of fingers on your right
| hand and the set of fingers on your left hand. Same reasoning
| can be applied to arbitrary sets, including infinite ones.
| contravariant wrote:
| There is a reason mathematicians prefer to talk about
| 'cardinality' rather than size.
|
| Anyway if you want a set to be at least as big as its subsets
| and consider them to be of equal size when they're isomorphic
| then you kind of end up with cardinality as a notion of size.
| In some sense it's simply the best notion of size we have if
| all you have is the structure of sets.
|
| There are of course other structures you could choose, like
| topological spaces, vector spaces etc. Those can fail to be
| isomorphic even when the underlying sets are, so you get a
| richer notion of 'size'.
| kccqzy wrote:
| Once you get to infinities, you can no longer denote the "size"
| of a set using naturals numbers, which is the typical usage of
| the word "size" (there are three apples in my basket and three
| is a natural number).
|
| So to me this is just quibbling about the definition of the
| word "size" which isn't a productive conversation. Stop calling
| it "size" and give it a specific terminology ("cardinality")
| instead and the whole unintuitive naming problem is
| sidestepped.
| throwawaymaths wrote:
| How would you well-define the "typical" usage of "size". The
| bijective mapping is completely consistent with our daily
| understanding for finite quantities, it's only in the infinite
| realm where it "feels weird" but those are just feels man.
| mopierotti wrote:
| I would say the number of items in a set, so by that logic
| the number of items in every type of infinite set would each
| seem to be infinity.
|
| Maybe where I'm struggling is that I'm not familiar with why
| this notion of differently sized infinities is useful.
| kccqzy wrote:
| Defining the number of items in a set requires the
| existence of natural numbers in the first place. (In
| typical set theory, people start with the existence of sets
| and then define natural numbers from sets.) And it doesn't
| help when dealing with sets that are as numerous as the
| natural numbers, or more.
|
| That said it's not wrong to lump together all infinite sets
| and say their size is infinite. That's how third graders
| understand the size of a set anyways. It just isn't
| precise.
| _bohm wrote:
| The reals are a superset of the integers, and a bijective
| mapping cannot be formed between the two, thus there are "more"
| elements in the set of reals than the set of integers.
| akomtu wrote:
| It's worth noting that R=2^N: reals is the set of all subsets
| of integers, simply because any real in binary form appears
| as a sequence of 1s and 0s that select a subset of N. And for
| some reason it's not possible to know if there's anything in
| between N and 2^N. This makes me think that infinite sets
| grow in discrete exponential jumps: N, 2^N, 2^R and so on. N
| seems to be the smallest infinite set.
| bigmattystyles wrote:
| I still can't wrap my head around why this isn't just all
| semantics around indexing.
|
| Take the infinities of all numbers > 0 and then all even numbers
| > 0.
|
| So you have
|
| 1,2,3,4,5,6,.... 2,4,6,8,........
|
| Why can't we just consider both infinities to be the same size
| (they go on forever), but the item in a given position simply
| differs.
|
| The only way I can reason it, is that if I exclude the second
| from the first, I still have infinite items, whereas if I exclude
| the first from the second, then I'm left with nothing.
|
| Is that how to think about it? I don't why, it doesn't compute in
| my head.
| version_five wrote:
| We do consider both of those sets to be the same size - for
| infinite sets, size equality means being able to uniquely put a
| members from one set in correspondence with members I n
| another. In your example, n -> 2n provides a unique mapping so
| the sets are equal size (cardinality)
| roarcher wrote:
| Not all infinities can be indexed.
|
| Take all the real numbers between 0 and 1, for example. If you
| pick one and call it N, there's an infinite quantity of real
| numbers between 0 and N and between N and 1. Therefore it's
| impossible to assign an index to N.
|
| Now take rational numbers, which are a subset of real numbers.
| There's an infinite number of those between 0 and 1 as well,
| but because it's a subset, there are "fewer" of them.
|
| Edit: It appears my sloppy language has ruffled some
| mathematical feathers. My apologies.
| contravariant wrote:
| Depends what you mean by 'indexed'. If you accept the axiom
| of choice then you can index the real numbers with some
| uncountable ordinal.
| roarcher wrote:
| I meant it in the sense that I assume GP meant it, i.e.,
| the index of an element in an ordered set is an integer
| corresponding to its position in that set, starting at 0 or
| 1 for the first element (depending on your indexing scheme
| of choice).
| roywiggins wrote:
| That doesn't explain why rationals and reals are different.
| Rationals are a _countable subset_ of the reals, to prove
| that you need to produce a method of enumerating them, not
| just say "they're a subset so they're smaller."
|
| Lots of subsets of the reals are uncountable, most notably if
| the rationals are countable and you split the reals into
| rationals and irrationals, the irrationals have to be
| uncountable. Otherwise you'd be forced to say that the union
| of two countable sets could be uncountable, which isn't true
| (if you have two countable sets you can automatically produce
| an enumeration of the union).
| roarcher wrote:
| I don't see how your point about countability invalidates
| what I said. Irrationals are uncountable, but there are
| fewer of them between 0 and 1 than reals between 0 and 1,
| by virtue of the fact that all irrationals are reals but
| not all reals are irrationals.
|
| I admit I'm using "subset" in the colloquial sense, meaning
| "a set that's missing some of the elements in its
| superset", which is not quite the correct definition (a
| subset doesn't _have_ to be missing anything, i.e., every
| set is a subset of itself). So technically a subset does
| not imply fewer elements. Is that what you 're getting at?
|
| I'm not particularly well versed in set theory, so maybe
| I'm just misunderstanding your point about countability.
| roywiggins wrote:
| You didn't say anything incorrect! But the important bit
| when it comes to talking about sizes of infinity is that,
| while both irrationals and rationals are smaller than the
| reals in one sense (they're both proper subsets), they're
| _very different_ in another sense: you actually can index
| the rationals by the natural numbers whereas you can 't
| do the same with the irrationals.
| [deleted]
| neonskies wrote:
| > Take the infinities of all numbers > 0 and then all even
| numbers > 0.
|
| Define your number first, then we'll work it out from there.
| From the looks of it, you are considering the integers.
|
| > So you have
|
| > 1,2,3,4,5,6,.... 2,4,6,8,........
|
| > Why can't we just consider both infinities to be the same
| size (they go on forever), but the item in a given position
| simply differs.
|
| These sets have the same size. Two sets have the same size if
| you can find a function from one to the other which is
| bijective meaning if two sets match exactly element for
| element(elements don't have to be the same ones), they have the
| same size. For example, the sets {1, 2, 3} and {a, b, c} have
| the same size because we can match 1 to a, 2 to b and 3 to c.
| Or we can match 1 to c, 2 to a and 3 to b. So these two
| "matching" examples constitute two bijective functions. Going
| back to your example, the function f from {1,2,3,4,5,6,....} to
| {2,4,6,8,........} given by f(x) = 2x for x in
| {1,2,3,4,5,6,....} is bijective and therefore lines up the two
| sets in one to one correspondence. To prove f is bijective, we
| can find the inverse for f, multiply f and its inverse and get
| an identity or show f is surjective and injective. These are
| slightly technical, but not too bad. Any intro to discrete math
| textbook contains this material.
| srcreigh wrote:
| For one, a set has unique elements, so listing duplicates won't
| increase the size.
|
| But the idea is that some sets can't be indexed. Decimal
| numbers/ real numbers. Basically, if you try to list them all,
| you can always find one that isn't in the list. Make the ith
| digit of the number different than the ith digit of the ith
| number in your list. That proves that decimal numbers can't be
| put on a list, so there's more decimal numbers than list-able
| numbers, even if they're both infinite.
___________________________________________________________________
(page generated 2023-04-19 23:00 UTC)