[Retric]

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.

[pherq]

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)).

[taneq]

I didn't go far into set theory but, informally, it seems to me that for any given natural number N, there will be N natural numbers less than or equal to N (obviously) and P prime numbers less than or equal to N, and P < N. Doesn't taking the limit as N goes to infinity show that there are fewer primes than there are natural numbers? Where am I going wrong?

[chimeracoder]

It might be easier to think of it this way: Are there more natural numbers than there are even natural numbers?

The answer is no, as illustrated by the Hotel paradox[0], in which we have a infinitely many rooms and want to accommodate a (possibly infinite) number of guests.. To summarize: For any finite number of guests, you can always find an even-numbered room to correspond to that guest (assume the guests are numbered sequentially, then double their number and put them in the room that has that number.). This creates a one-to-one correspondence, which means that the sets are the same size.

You might say, 'well, that only works because we're dealing with a finite number of guests. But we're talking about infinity'. There are a few different ways of answering that question. In my opinion, the easiest way to look at it is to remember that there is no such number as 'infinity' - when we say 'infinity', we're really trying to express the concept of growing without bound. So, the above strategy (double the person's number) works for any arbitrarily large group. At no point does it stop working, even as the group size grows larger and larger, so we can say that the two sets have the same size.

On the other hand, we have no such strategy for putting every irrational number in one-to-one correspondence with the counting numbers. That proof is a little harder, and the analogy with the hotel guests breaks down, unfortunately, so it's a bit tougher to explain.

[0] https://en.wikipedia.org/wiki/Hilbert's_paradox_of_the_Grand...

[masterzora]

> Where am I going wrong?

In short, infinities are complicated and intuition doesn't work well.

In slightly longer, you're talking about the difference of the rate of growth of two functions rather than actually about the cardinalities of the sets.

We define two sets as having the same cardinality when we can create a bijection between them. We can list the primes in order from smallest to largest and number them with the natural numbers. So we'll have 2 match up with 0, 3 with 1, 5 with 2, 7 with 3, etc. Every single prime number will correspond with a natural number AND every single natural number will correspond with a prime number, no exceptions. So they must be the same size. They are also the same size as the integers and the rational numbers but the set of real numbers is a bigger infinity.

[Retric]

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]

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]

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.

[jbclements]

I believe you misread the text you're replying to. The bijection is between the points in the 2d space and the points in the line segment. Both of these are uncountably infinite.

[JBiserkov]

>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_...

[Retric]

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]

"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]

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]

Best trolling on HN in weeks.

[pcmonk]

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]

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]

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

[Retric]

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.

[pcmonk]

{A,B,C} is of greater cardinality than {A,B}. However, the argument that "a rule works for finite numbers, so it must work for infinite numbers" is clearly false.

For a your mapping, see: http://math.stackexchange.com/questions/512397/is-there-a-si...

[Retric]

The distance between 0 and 1 is smaller than the distance between 0 and 2. The number of points between 0 and 1 is larger than the number of rational numbers.

[yongjik]

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.

[Retric]

e is real, e + ei is irrational.

[stouset]

The cardinality of the set of prime numbers and of rationals are both aleph-null[1]. Same with the list of all integers, the list of all positive integers, and the list of all even integers. They all have the same cardinality, and that cardinality is aleph-null.

But please, continue to argue with mathematical definitions that have been established for over a century.

[1]: https://en.wikipedia.org/wiki/Aleph_number#Aleph-naught