14 ms·

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 corresp

• hprotagonist 4y ago
  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 4y ago
  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.
• xtagon 4y ago
  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 4y ago
    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.
• IIAOPSW 4y ago
  >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.
  • xchkr1337 4y ago
    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 4y ago
      thanks, I fucked up the easy part lol
    • pfortuny 4y ago
      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.
  • cjohnson318 4y ago
    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.
• stiglitz 4y ago
  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.
• aidos 4y ago
  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 4y ago
    To clarify. There is no mapping from natural numbers to all the irrational numbers. And that’s why there are different sized infinities
    • nico 4y ago
      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 4y ago
        You can count natural numbers. Elementary school children do it every day. Now, try to count the real numbers. What comes after 1?
        • nico 4y ago
• deleted 4y ago
  [deleted]
• pfortuny 4y ago
  Thinking of actions leads you astray. Maps look like actions but they are not.
• ironSkillet 4y ago
  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.
  • Dylan16807 4y ago
    Though it's weirder than that. If you can actually put a number on the number line, then you have a computable number. And those are countable. Uncountable reals only exist as abstract thought experiments.
    • Viliam1234 4y ago
      > Uncountable reals only exist as abstract thought experiments. Technically, sufficiently large natural numbers, such as 10^10^10 also exist only as thought experiments. Technically, if we require the number to refer to some number of objects, there is such as thing as a largest natural number - it is the number of all particles that exist in the universe. If you add +1 to it, the result of that addition exists only as a thought experiment.
      • Dylan16807 4y ago
        As natural numbers get huge, they become gradually harder to use. Though no, I wouldn't require a number to represent some physical quantity, as long as the number itself fits in some kind of moderate physical boundary. But real numbers are wonky right from the start. Picking a single random real out of a range is infeasible.
    • AstixAndBelix 4y ago
      You are mixing up definitions. Pi is computable, meaning we can calculate one by one its digits, but is not rational. If you can compute a number in a finite time, you can put it om the number line, but the only numbers that can be finitely computed are the rationals which are countable
      • 4y ago
• bryanrasmussen 4y ago
  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_buffalo_buffalo_buffalo_Buffalo_buffalo https://en.wikipedia.org/wiki/Buffalo_buffalo_Buffalo_buffal...
  • bryanrasmussen 4y ago
    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 4y ago
      Those two infinite statements have the same cardinality.
      • bryanrasmussen 4y ago
        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.
        • srean 4y ago
          If one of them, presumably the buffalo sentence, indeed has more letters, then could you give us a invertible scheme that maps to each letter of the police sentence, a letter in the buffalo sentence, that covers all the letters in the police sentence, but has letters in the buffalo sentence still left over.
        • deleted 4y ago
          [deleted]
  • 4y ago
• scythe 4y ago
  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".
  • denton-scratch 4y ago
    > we don't normally, in our physical world, encounter infinite amounts of anything. I may be missing your meaning, but we encounter distances (e.g. line-segments) all the time; the number of points on a line-sement is equal to the cardinality of the reals. The physical world is full of infinite sets, most of which are uncountable.
• btilly 4y ago
  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.
• mike_hock 4y ago
  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.