Curiosity about Infinite Sets

[Boltzmannbrain]

The two sets N (naturals) and I (integers) have a one-to-one correspondence and are said to have equal size/cardinality.  

But if we put them one-to-one in a specific way, such as the naturals to the naturals from I, we see that the naturals of I get used up leaving 0 and the negative integers.

This seems to show that a correspondence from N to I can also not be one-to-one.  

The curiosity I get from this is just too much.  It almost seems like this is an example of something that can be proved to be true and can be proved to be false. 

I would have to think that my problem is that I am not allowed to correspond the naturals to only the naturals of the integers, but why not?  

 

[wtf]

30 minutes ago, Boltzmannbrain said:

But if we put them one-to-one in a specific way, such as the naturals to the naturals from I, we see that the naturals of I get used up leaving 0 and the negative integers.

This seems to show that a correspondence from N to I can also not be one-to-one.  

Here is what's going on. 

One day Alice eats a cheeseburger. The next day her vegetarian friend Bob says to Alice, "Alice, you are a meat eater." Alice indignantly replies: "But no, TODAY I have not eaten any meat. I only eat meat sometimes." And Bob explains that a meat eater is anyone who SOMETIMES eats meat. A vegetarian is someone who NEVER eats meat. If someone is not a vegetarian, they are a meat eater. Since Alice sometimes eats meat, she is clearly not a vegetarian. She is by definition a meat eater, by virtue of the fact that she SOMETIMES eats meat.

Ok that's a bit of a shaggy dog story and if it's unclear I'll try to come up with a better example. But here is the relevant definition for our mathematical purposes:

* Definition: Two sets are said to have the same cardinality if THERE EXISTS a function between them that is a bijection. The fact that there happen to be functions between the sets that are NOT bijections doesn't matter. All it takes is the existence of a single bijection to satisfy the definition.

By this definition, we see that [math]\mathbb N[/math] and [math]\mathbb Z[/math] have the same cardinality. Because THERE EXISTS some function between them that is a bijection: namely, the function that corresponds them as follows:

0 <-> 0

1 <-> -1

2 <-> 1

3 <-> -2

4 <-> 2

5 <-> -3

6 <-> 3

and so forth.

It is certainly the case that there are SOME functions between [math]\mathbb N[/math] and [math]\mathbb Z[/math] that are NOT bijections. But that doesn't matter. To have the same cardinality, there only needs to be a single bijection between the two sets; just as to be a meat eater, you only have to have one cheeseburger.

Another example is a guy who is convicted of robbing a bank. For the rest of his life he'll be labeled a bank robber, even if he hasn't robbed a bank in years. Doing it once is enough to earn the label. Likewise, a single bijection between two sets is all it takes to declare the sets to have the same cardinality.

 

Edited August 30, 2023 by wtf

[Boltzmannbrain]

4 minutes ago, wtf said:

Here is what's going on. 

One day Alice eats a cheeseburger. The next day her vegetarian friend Bob says to Alice, "Alice, you are a meat eater." Alice indignantly replies: But no, TODAY I have not eaten any meat. I only eat meat sometimes. And Bob explains that a meat eater is someone who SOMETIMES eats meat. A vegetarian is someone who NEVER eats meat. If someone is not a vegetarian, they are a meat eater. Since Alice sometimes eats meat, she is clearly not a vegetarian. She is by definition a meat eater, by virtue of the fact that she SOMETIMES eats meat.

Ok that's a bit of a shaggy dog story and if it's unclear I'll try to come up with a bette example. But here is the relevant definition for our mathematical purposes:

* Definition: Two sets are said to have the same cardinality if THERE EXISTS a function between them that is a bijection. 

By this definition, we see that N and Z have the same cardinality. Because THERE EXISTS some function between them that is a bijection: namely, the function that corresponds them as follows:

0 <-> 0

1 <-> -1

2 <-> 1

3 <-> -2

4 <-> 2

5 <-> -3

6 <-> 3

and so forth. 

It is certainly the case that there are SOME functions between N and Z that are NOT bijections. But that doesn't matter. To have the same cardinality, there only needs to be a single bijection between the two sets; just as to be a meat eater, you only have to have one cheeseburger.

Another example is a guy who is convicted of robbing a bank. For the rest of his life he'll be labeled a bank robber, even if he hasn't robbed a bank in years. Doing it once is enough to earn the label. Likewise, a single bijection between two sets is all it takes to declare them to have the same cardinality.

 

I understand that there only needs to be some bijection.  But doesn't this seem a bit strange to you that we can exhaust all elements of I and we also can't exhaust all elements of I (using N)?  It is a yes and no answer.  I never see that in math.  Is it allowed?

 

[wtf]

8 minutes ago, Boltzmannbrain said:

I understand that there only needs to be some bijection.  But doesn't this seem a bit strange to you that we can exhaust all elements of I and we also can't exhaust all elements of I (using N)?  It is a yes and no answer.  I never see that in math.  Is it allowed?

 

Yes it's very strange. Yes it is allowed. In fact it's the defining property of infinite sets. We can't do that with a finite set! One way to define an infinite set is to say that it's a set that can be placed into bijection with a proper subset of itself. Only infinite sets have that property. And yes it is strange!

This was noticed by Galileo in 1638. He observed that we can correspond the natural numbers with the perfect squares: 0 <-> 0, 1 <->1, 2 <-> 4, 3 <-> 9, etc. 

So the whole numbers must at the same time be more numerous and equally numerous with the squares. 

https://en.wikipedia.org/wiki/Galileo's_paradox

If he had only stuck to math he would not have gotten into trouble with the Pope. There's a lesson in there somewhere.

Edited August 30, 2023 by wtf

[Boltzmannbrain]

On 8/29/2023 at 10:10 PM, wtf said:

Yes it's very strange. Yes it is allowed. In fact it's the defining property of infinite sets. We can't do that with a finite set! One way to define an infinite set is to say that it's a set that can be placed into bijection with a proper subset of itself. Only infinite sets have that property. And yes it is strange!

This was noticed by Galileo in 1638. He observed that we can correspond the natural numbers with the perfect squares: 0 <-> 0, 1 <->1, 2 <-> 4, 3 <-> 9, etc. 

So the whole numbers must at the same time be more numerous and equally numerous with the squares. 

https://en.wikipedia.org/wiki/Galileo's_paradox

If he had only stuck to math he would not have gotten into trouble with the Pope. There's a lesson in there somewhere.

Very interesting, thanks for this.  It is a little clearer.  However, I wouldn't be honest if I said that infinity makes sense to me now.

 

Edited August 31, 2023 by Boltzmannbrain

[Genady]

"If he had only stuck to math he would not have gotten into trouble with the Pope. There's a lesson in there somewhere."

Also, if he had only stuck to strength of materials he would not have gotten into trouble with the Pope. Galileo's Beam Experiment (lindahall.org)

Edited August 31, 2023 by Genady

[studiot]

On 8/30/2023 at 5:10 AM, wtf said:

Yes it's very strange. Yes it is allowed. In fact it's the defining property of infinite sets. We can't do that with a finite set! One way to define an infinite set is to say that it's a set that can be placed into bijection with a proper subset of itself. Only infinite sets have that property. And yes it is strange!

This was noticed by Galileo in 1638. He observed that we can correspond the natural numbers with the perfect squares: 0 <-> 0, 1 <->1, 2 <-> 4, 3 <-> 9, etc. 

So the whole numbers must at the same time be more numerous and equally numerous with the squares. 

First I would like to say +1 to wtf for some very clear presentation of the issue.

 

I would then like to add a little to the business of bijections and 'omitted elements'  as noted in the emboldened words.

[math]\begin{array}{*{20}{c}}
   1 \hfill & 2 \hfill & 3 \hfill & 4 \hfill & 5 \hfill & 6 \hfill & 7 \hfill & 8 \hfill & 9 \hfill & {10} \hfill  \\
   1 \hfill & 4 \hfill & 9 \hfill & {16} \hfill & {25} \hfill & {36} \hfill & {49} \hfill & {64} \hfill & {81} \hfill & {100} \hfill  \\
   2 \hfill & 3 \hfill & 5 \hfill & 6 \hfill & 7 \hfill & 8 \hfill & {10} \hfill & {11} \hfill & {12} \hfill & {13} \hfill  \\
\end{array}[/math]

 

Here is something even more interesting

The first line lists the natural numbers

The second line lists their squares as per Galileo.

The third line list the numbers missing in the second line from the first.

This can also be put into a bijection.

In fact we can derive any number of ever more complicated derived lines.

 

 

[Genady]

"... the whole numbers must at the same time be more numerous and equally numerous with the squares ..."

Just wanted to note that the whole numbers can also be at the same time less numerous than the squares.