Why N is greater than N*2

A more intuitive way of comparing sets

R. Harvey
IntuitionMath
4 min readJul 5, 2023

--

Many years ago I took part in a math contest and there was this question:

Which is larger: the set of natural numbers or the set of even natural numbers?

Me at this point said: Isn’t it obvious that the natural numbers are more, because for every even number n we have two natural numbers n and n+1. For me, this was a perfectly valid answer which made total sense, but I was shocked when they told me that that was actually not the case — I was wrong. The solution was supposed to be that the even numbers have the same mightiness as the natural numbers, and the sets are therefore equal in size.

But who decided that the size of sets should be compared by the mightiness? Well, I don’t know who, but it might have been a bad idea.

The Problem

The problem is that many rules that apply to finite sets don’t apply to infinite sets when using this method. But as humans, we will try to apply those rules anyway, and therefore it makes a lot of sense to develop a new method that possibly is more intuitive to the average human.

Let’s just go through some examples:

  • If we have a set A and take some members away to build B, then B must be smaller than A
  • On the other hand, if we have a set A and add some members to build B, then B most be larger than A.

Firstly, these rules always apply to finite sets, but interestingly they also give much more natural results for infinite sets. Just ask a normal person whether N is more or less than N\{5}. Most people will naturally agree that N\{5} is less.

The Method

So now we understood what we should do with strict subsets, but what happens when we have other kinds of sets. Like for example 2*N vs 3*Z. I suggest the following rule that works with all totally ordered universes:

A is greater than B if there is some positive n₀ so that for every n ≥ n₀ |A ⋂ [-n, n]| is greater than |B ⋂ [-n, n]|.

NZ

With this method, 2*N is smaller than 3*Z. As an example, let's choose n₀ = 9:

  • n = 9, 2*N: {0,2,4,6,8}, 3*Z: {-9,-6,-3,0,3,6,9}
  • n=10, 2*N: {0,2,4,6,8,10}, 3*Z: {-9,-6,-3,0,3,6,9}
  • n=11, 2*N: {0,2,4,6,8,10}, 3*Z: {-9,-6,-3,0,3,6,9}
  • n=12, 2*N: {0,2,4,6,8,10,12}, 3*Z: {-12,-9,-6,-3,0,3,6,9,12}

We could probably do some kind of proof by induction, but I think it is pretty obvious that 3*Z grows faster than 2*N. And, if you are a computer scientist, maybe now that I said “grows faster”, you might be thinking of computational complexity theory and most importantly comparing the complexities of different algorithms. In this field of study, one analyzes how many resources an algorithm needs depending on the size of an input. This is pretty similar, but we don’t look at the resources of an algorithm but instead the size of a finite set.

QR

What’s up with Q and R? Our method doesn’t real work with them because in any range of numbers there are infinitely many more numbers. I would for example suggest taking another number like d that limits the number of decimal places:

A is greater than B if there is some positive number r₀ so that for every r≥r₀ there is some natural number d₀ so that for every d≥d the following is true:

|{a|a∈A; a≤r; a*10**d ∈ N}| > |{b|b∈B; b≤r; b*10**d ∈ N}|

This makes it possible to, for example, prove that A is smaller than B with

A: {q | q∈Q; third decimal digit is a 1}

B: {q | q∈Q; third decimal digit is not a 1}

This is left as an exercise for the reader

C

You might think that sets from the complex numbers cannot be compared with this method, but C is to R in many ways what Z is to N. So instead of a range, we can use an ever expanding circle.

Problems with our new method

The biggest problem is when of two sets, one never definitely triumphs over the other. In this case, we can either fall back to the old method or simply declare them as equal. An example could be:

A: {n | n∈N; n has an even number of digits}

B: {n | n∈N; n has an odd number of digits}

Other problems that will come to my or your mind, will appear here. Please leave me your thoughts here as a comment.

Conclusion

We developed a new method that allows us to compare the size of infinite sets by comparing the limits of their sizes instead of comparing their mightiness. This method seams to work well, especially in comparison to what a human thinks intuitively.

Signing out

Rashid Harvey

--

--

R. Harvey
IntuitionMath

I am a computer science student and here I write mostly about computer science, maths and physics