6 ms·

In what sense are there more rational numbers than prime numbers? They can be put into bijection with each other, so we generally think of them as being same i

by pcmonk 10y ago

In what sense are there more rational numbers than prime numbers? They can be put into bijection with each other, so we generally think of them as being same infinity. There are more real nubmers, of course, by Cantor's diagonalization, so your basic point is true.

Retric 10y ago
The set of all prime numbers is contained within the set of rational numbers, but they are rational numbers that are not within the set of prime numbers. Cantor's diagonalization is simply demonstrating that same inequality by showing a number in set A is not in set B. Just because you can map two infinity's to each other does not mean they are of the same size consider: Limit(0->inifinity) of (x - (x/2)) algebraically that's clearly Limit(0->inifinity) of X/2 which is infinity. PS: What makes Cantor's diagonalization interesting is you can repeat it recursively an infinite number of times. This is more obvious in base 2.
- JBiserkov 10y ago
  >Cantor's diagonalization is simply demonstrating that same inequality by showing a number in set A is not in set B. If that were true, why go to all the trouble, just show 1/2 which is not a natural number, or sqrt(2) which is not a rational number. Cantor's diagonalization is proving that no mapping exists between the natural numbers and the real numbers in [0, 1]; that no matter what mapping you (try to) come up, there will be a number you would miss. The primes and rationals have the same size (cardinality) as the natural numbers, namely countably infinite. See https://en.wikipedia.org/wiki/Countable_set#Formal_overview_without_details https://en.wikipedia.org/wiki/Countable_set#Formal_overview_...
  - Retric 10y ago
    So, you can show the Real numbers between 0 and 1 is larger than the number of Natural numbers. There are an infant number of points between 0 and 1 and an infinite number of points between 0 and 2. The distance between 0 and 2 is larger. The number of points between 0 and 1 is smaller than the number of points on the unit circle AND they are a different class of infinity.
    - pcmonk 10y ago
      "The distance between 0 and 2 is larger" is a question about the metric of the space, not size of sets. There are the same number of points in both sets, since f(x) = 2x is a bijection between them. Try to make arguments from axioms and definitions rather than asserting things from intuition. Intuition is often a useful tool, but (1) it's not an argument, and (2) it's not very helpful once you step into the infinite realm. Incidentally, that's why I went for programming: it's like math, but with no infinity (unless you're using floats, but that's a much easier infinity).
      - Retric 10y ago
        You say same number, you mean same flavor. Either the 'number' is not in R and thus it's not a number or you end up with a host of contradictions. But, I have had my fun poking people who don't really get set theory.
        JackFr 10y ago
        Best trolling on HN in weeks.
- pcmonk 10y ago
  Where in math is the subset partial ordering used to describe one set as larger than another? Diagonalization isn't showing that a number in set A isn't in set B - that's obviously true for reals and integers, but it's also true for rationals and integers. It's showing that there does not exist a mapping from B to A where there's an element in B for each element in A. We're obviously not using the same definition of "size". I generally think in terms of cardinality, what are you thinking of?
  - Retric 10y ago
    Cardinality is the number of elements in a set. If every element in set A is in set B, and there are elements in set A left over it's larger because that's what larger means. {A,B} < {A,B,C} There are countable and uncountable infinite set's. All countable set's have a bijection with N. However, there are more than two sizes of infinite sets. Real numbers < Imaginary numbers.
    - pcmonk 10y ago
      That's not what larger means, that's what (maps into a) strict subset means. In finite numbers, that's the same as larger (greater cardinality), but it's very much not the case for infinite numbers. There are more than two sizes of infinite sets, but there are just as many real numbers as imaginary numbers for the same reason there's just as many integers as rational numbers. Try reading this: https://en.wikipedia.org/wiki/Cardinality#Infinite_sets https://en.wikipedia.org/wiki/Cardinality#Infinite_sets
      - Retric 10y ago
        We agree that {A,B,C} has a lower cardinality than {A,B}. Now, feel free to try and map the set of Real numbers to the set of irrational numbers. ex: e + ei.
        yongjik 10y ago
        1. e + ei is not real. 2. f(x) = x + sqrt(2) if there exists an integer k>=0 such that x - k * sqrt(2) is rational; f(x) = x otherwise. This function maps all real numbers to irrational numbers, 1-to-1.
- pherq 10y ago
  The existence of a bijection between two sets is what "same size" means in set theory. Yes, there are non-prime integers, but you can establish a bijection between the two, so their cardinalities are equal (both have a cardinality of aleph zero). The reals, on the other hand, cannot be placed in a bijection with the natural numbers, and there are therefore "more" reals than naturals (i.e. there is an injection from the naturals to the reals, but not from the reals to the naturals -- any function from reals to naturals must have some pair x ≠ y with f(x) = f(y)).
  - Retric 10y ago
    You're confusing a classification system with size. Is the set of Real Numbers larger, smaller, or the same size as the set of points in a finite 2d object? Can you setup a bijection in either direction?
    - pherq 10y ago
      Assuming you consider the dimensions/axes/whatever of the 2d space to be indexed by reals (which is conventional), then yes one can construct a bijection: - normalise x and y coordinates in the shape into the interval (0, 1) - interleave the bits of the normalised x and y coordinates This gives a single real value in the interval (0, 1), which exists and is unique for every point in the space (so it is an injection), and it covers every real number in that interval (so it is a surjection). This gives you a bijection between points in (a) 2-dimensional space and a segment of the real line (which, in turn, has a bijection with the whole real line if you want to specify that). Once again, cardinality in set theory is based on injections and bijections. If there is an injection from X into Y, then Y is at least as big as X. If there is a bijection between them (i.e. injections in both directions), then they are the same size. (Also, bijections are inherently bidirectional.)
      - Retric 10y ago
        You used a countable infinity to tile an uncountable one. The set of 0 to 1 line segments being a countable infinity. 0 to 1 maps 1, 1 to 2 maps to 2 ect.

by pcmonk 10y ago

Retric 10y ago

The set of all prime numbers is contained within the set of rational numbers, but they are rational numbers that are not within the set of prime numbers. Cantor's diagonalization is simply demonstrating that same inequality by showing a number in set A is not in set B. Just because you can map two infinity's to each other does not mean they are of the same size consider: Limit(0->inifinity) of (x - (x/2)) algebraically that's clearly Limit(0->inifinity) of X/2 which is infinity. PS: What makes Cantor's diagonalization interesting is you can repeat it recursively an infinite number of times. This is more obvious in base 2.

JBiserkov 10y ago
>Cantor's diagonalization is simply demonstrating that same inequality by showing a number in set A is not in set B. If that were true, why go to all the trouble, just show 1/2 which is not a natural number, or sqrt(2) which is not a rational number. Cantor's diagonalization is proving that no mapping exists between the natural numbers and the real numbers in [0, 1]; that no matter what mapping you (try to) come up, there will be a number you would miss. The primes and rationals have the same size (cardinality) as the natural numbers, namely countably infinite. See https://en.wikipedia.org/wiki/Countable_set#Formal_overview_without_details https://en.wikipedia.org/wiki/Countable_set#Formal_overview_...
- Retric 10y ago
  So, you can show the Real numbers between 0 and 1 is larger than the number of Natural numbers. There are an infant number of points between 0 and 1 and an infinite number of points between 0 and 2. The distance between 0 and 2 is larger. The number of points between 0 and 1 is smaller than the number of points on the unit circle AND they are a different class of infinity.
  - pcmonk 10y ago
    "The distance between 0 and 2 is larger" is a question about the metric of the space, not size of sets. There are the same number of points in both sets, since f(x) = 2x is a bijection between them. Try to make arguments from axioms and definitions rather than asserting things from intuition. Intuition is often a useful tool, but (1) it's not an argument, and (2) it's not very helpful once you step into the infinite realm. Incidentally, that's why I went for programming: it's like math, but with no infinity (unless you're using floats, but that's a much easier infinity).
    - Retric 10y ago
      You say same number, you mean same flavor. Either the 'number' is not in R and thus it's not a number or you end up with a host of contradictions. But, I have had my fun poking people who don't really get set theory.
      - JackFr 10y ago
        Best trolling on HN in weeks.
pcmonk 10y ago
Where in math is the subset partial ordering used to describe one set as larger than another? Diagonalization isn't showing that a number in set A isn't in set B - that's obviously true for reals and integers, but it's also true for rationals and integers. It's showing that there does not exist a mapping from B to A where there's an element in B for each element in A. We're obviously not using the same definition of "size". I generally think in terms of cardinality, what are you thinking of?
- Retric 10y ago
  Cardinality is the number of elements in a set. If every element in set A is in set B, and there are elements in set A left over it's larger because that's what larger means. {A,B} < {A,B,C} There are countable and uncountable infinite set's. All countable set's have a bijection with N. However, there are more than two sizes of infinite sets. Real numbers < Imaginary numbers.
  - pcmonk 10y ago
    That's not what larger means, that's what (maps into a) strict subset means. In finite numbers, that's the same as larger (greater cardinality), but it's very much not the case for infinite numbers. There are more than two sizes of infinite sets, but there are just as many real numbers as imaginary numbers for the same reason there's just as many integers as rational numbers. Try reading this: https://en.wikipedia.org/wiki/Cardinality#Infinite_sets https://en.wikipedia.org/wiki/Cardinality#Infinite_sets
    - Retric 10y ago
      We agree that {A,B,C} has a lower cardinality than {A,B}. Now, feel free to try and map the set of Real numbers to the set of irrational numbers. ex: e + ei.
      - yongjik 10y ago
        1. e + ei is not real. 2. f(x) = x + sqrt(2) if there exists an integer k>=0 such that x - k * sqrt(2) is rational; f(x) = x otherwise. This function maps all real numbers to irrational numbers, 1-to-1.
pherq 10y ago
The existence of a bijection between two sets is what "same size" means in set theory. Yes, there are non-prime integers, but you can establish a bijection between the two, so their cardinalities are equal (both have a cardinality of aleph zero). The reals, on the other hand, cannot be placed in a bijection with the natural numbers, and there are therefore "more" reals than naturals (i.e. there is an injection from the naturals to the reals, but not from the reals to the naturals -- any function from reals to naturals must have some pair x ≠ y with f(x) = f(y)).
- Retric 10y ago
  You're confusing a classification system with size. Is the set of Real Numbers larger, smaller, or the same size as the set of points in a finite 2d object? Can you setup a bijection in either direction?
  - pherq 10y ago
    Assuming you consider the dimensions/axes/whatever of the 2d space to be indexed by reals (which is conventional), then yes one can construct a bijection: - normalise x and y coordinates in the shape into the interval (0, 1) - interleave the bits of the normalised x and y coordinates This gives a single real value in the interval (0, 1), which exists and is unique for every point in the space (so it is an injection), and it covers every real number in that interval (so it is a surjection). This gives you a bijection between points in (a) 2-dimensional space and a segment of the real line (which, in turn, has a bijection with the whole real line if you want to specify that). Once again, cardinality in set theory is based on injections and bijections. If there is an injection from X into Y, then Y is at least as big as X. If there is a bijection between them (i.e. injections in both directions), then they are the same size. (Also, bijections are inherently bidirectional.)
    - Retric 10y ago
      You used a countable infinity to tile an uncountable one. The set of 0 to 1 line segments being a countable infinity. 0 to 1 maps 1, 1 to 2 maps to 2 ect.