28
$\begingroup$

This question already has an answer here:

In our 6th grade math class we got introduced to the concept of integers. With all the talk about positive and negative, it got me wondering. Is the amount of elements in $\mathbb{Z^+}$ less than the amount of elements in $\mathbb{Z}$?

Here is how I thought of it. If we have $\mathbb{Z^+}$ and add one element to the "back" of it ($\mathbb{Z}^{\geq-1}$) there are certainly more elements in that new set, so there must be more elements in $\mathbb{Z}$ than in $\mathbb{Z}^+$ but on the other side if we try to express the amount of elements in them "numerically" (In a loose sense of the word) they both have $\infty$ elements.

So what is the right answer? Is there even one?

(Please note I am a bit of a layman when it comes to mathematics)

Edit: About the possible duplicate, I am not looking for a bijection between the two sets, I am looking for if they even have the same number of elements and why a bijection shows that they do/don't

$\endgroup$

marked as duplicate by N. F. Taussig, user147263, Claude Leibovici, Mike Pierce, Daniel Robert-Nicoud Jun 27 '15 at 1:52

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • $\begingroup$ Here's a similar question $\endgroup$ – Umashankar Sasikumar Jun 25 '15 at 18:32
  • 5
    $\begingroup$ How would you suggest to measure "amount of elements" in an infinite set? I'm curious. $\endgroup$ – Asaf Karagila Jun 25 '15 at 18:32
  • $\begingroup$ What does it mean to "express the amounts of element in them 'numerically'?" Unlike the finite case, there's no reason to assume (or define, absent a general notion of cardinality) that an injection $A \to B$ implies that $A$ has 'fewer elements' than $B$. We can, for example, embed $\mathbb{Z}$ in $2\mathbb{Z}$ by the map $n \to 2n$. $\endgroup$ – anomaly Jun 25 '15 at 19:20
  • $\begingroup$ Yes, since a bijection exists between the set of positive integers and the set of all integers, they both have the same cardinality of aleph-null $\endgroup$ – 1110101001 Jun 26 '15 at 0:21
  • 2
    $\begingroup$ @EngineerToast this is yet another point where we have to be precise when talking about infinity - what you're remembering are indeterminate forms, which are a different sort of thing even though they use the language of infinity. (But also super interesting and important - actually, arguably more important to a lot of math.) $\endgroup$ – Noah Schweber Jun 26 '15 at 15:39
39
$\begingroup$

Great question!

Before I address it directly, let me make a general point:

When talking about infinity, it's important to make all your notions precise.

Basically, a lot of the time, if we ask vague questions the answer winds up being "it depends." And this isn't to say that these vague questions are uninteresting; on the contrary, the point is that they're so interesting, that they are really many questions secretly rolled into one.

So on to your question. Basically, this comes down to what you mean by "amount;" I'm going to answer for the usual sense of the word "amount" in set theory.


Cardinality. Say two sets $A$ and $B$ have the same size if and only if there is a bijection between them - that is, if there is a function $f: A\rightarrow B$ (takes in an element of $A$, spits out an element of $B$) which "pairs up" elements of $B$ with elements of $A$: that is, $f(a)=f(b)\implies a=b$ (the function is injective) and for each $c\in B$, there is some $a\in A$ with $f(a)=c$ (the function is surjective).

This is a lovely notion of size! It makes sense no matter what sort of sets $A$ and $B$ are, we can still ask whether there is a bijection between them or not. Also, for finite sets it agrees with our usual notion of "same size".

At the same time, it is somewhat subtle: for example, there is a bijection between the set of all integers and the set of even integers, even though we might think there are "more" of the former. The bijection is just $$f(x)=2x.$$ Similarly, there is a bijection between $\mathbb{N}$ and $\mathbb{Z}$, so in this sense they have the same size.

One natural response at this point is to ask, "Wait a minute! If bijections can't even distinguish between the evens and the integers, can they tell the difference between any pair of infinite sets?" That is, are there different kinds of infinity, in the bijections sense? The answer, perhaps surprisingly, is yes! This is Cantor's diagonal theorem, and was the beginning of modern set theory: Cantor's diagonal argument.


One natural question at this point is, "Are bijections the right tool for measuring the sizes of infinite sets?" Based on the following facts, it's quite reasonable to be skeptical:

  • There are bijections between each of the following sets: $\mathbb{N},\mathbb{Z},\mathbb{Q}$.

  • There is a bijection between $(0, 1)$ and $\mathbb{R}$.

  • There is a bijection between the set of integers and the set of finite strings of integers.

  • There is a bijection between the set of real numbers and the set of infinite sequences of real numbers. (Fine, by "infinite sequence" I mean "$\omega$-sequence.")

It's impossible to argue mathematically that bijections are the "best" way to get a notion of sizes of infinity, since "size of infinity" is an informal concept. But we can give some good arguments for why it's at least the best notion we have so far:

  • It really is how we count finite sets. If I give you two giant piles of marbles, and ask you to tell me if there are the same number of marbles in each pile, you would probably figure this out by removing one marble from each pile at the same time, and keep doing this until one or both piles ran out of marbles. If they run out at the same time, they had the same size, otherwise they didn’t. In case they run out at the same time, what you’ve done is build a bijection between the two piles!

  • The "sizes of infinity" are things we can study. If we assume the axiom of choice, we can show that given any two sets, either they have the same size or one is "bigger" than the other (i.e., there is an injection from one to the other). This really is something that bijections give us: without the language of bijections, which would you say is larger, the set of even integers or the set of odd integers?

  • We’re already interested in bijections. There are lots of theorems in mathematics that basically are talking about sizes in terms of bijections already. For example, if $A$ is a set of real numbers, is there some function $f$ whose local extrema are exactly the points in $A$? The answer turns out to be, “Yes, if and only if $A$ is either finite or in bijection with $\mathbb{N}$.” There are plenty of other examples of this sort of thing. So, size in terms of bijection is already mathematically interesting.


By the way, Alex S has given an explicit example of a bijection between $\mathbb{Z}^+$ and $\mathbb{Z}$. I can't resist giving one of my own favorite bijections, between $\mathbb{N}$ and the set $\mathbb{N}^2$ of ordered pairs of natural numbers: the Cantor pairing function! Note: for me, $0$ is a natural number - there are no kangaroos in my refrigerator!

EXERCISE: using the Cantor pairing function, come up with a bijection between $\mathbb{N}$ and $\mathbb{Q}$. It won't look nearly so nice, but you can do it!

FINAL NOTE: what if we restrict attention to "nice" bijections, whatever that means? This turns out to be super interesting, and leads (at least in one direction) to descriptive set theory, but that's a topic for another question.

$\endgroup$
  • $\begingroup$ Note that in my last bullet point, I'm allowing discontinuous $f$. $\endgroup$ – Noah Schweber Jun 25 '15 at 18:53
  • $\begingroup$ Great answer! But by that logic, isn't the set of integers from -10 to 10 the same size as integers 0 to 10? There exists a bijective function between them, but just by counting we know that one has more elements than the other. $\endgroup$ – user169330 Jun 25 '15 at 19:09
  • 9
    $\begingroup$ No, there isn't a bijection between them! If for example you send -5 and 5 both to 5, then this isn't a bijection because it's not injective. $\endgroup$ – Noah Schweber Jun 25 '15 at 19:11
  • 1
    $\begingroup$ Well, now $f(1)=-1$, so $f$ isn't sending the integers between -10 and 10 to the integers between 0 and 10: 1 is going somewhere it shouldn't. $\endgroup$ – Noah Schweber Jun 25 '15 at 19:30
  • 5
    $\begingroup$ It will be easier to see if you work with smaller numbers: is there a bijection between $\{-1, 0, 1\}$ and $\{0, 1\}$? (This is the same question as "integers between -10 and 10" vs "integers between 0 and 10," but it is easier to see.) $\endgroup$ – Noah Schweber Jun 25 '15 at 20:12
10
$\begingroup$

Good Question! When we talk about the size of sets, we say that the sets $A$ and $B$ are the same if there exists a function $f$ which takes elements in $A$ and outputs elements in $B$ that has two properties:

  • if $a$ is an element of $A$, and $f(a)=b$, where $b$ is an element of $b$, then no other element of $A$ maps to $b$. In other words, there is no $a'$ in $A$ such that $f(a')=b$ unless $a=a'$
  • For all $b$ in $B$, there exists an $a$ in $A$ such that $f(a)=b.$

A function with both of these properties is called a bijective function. Can you see why two finite sets are the same size if and only if there is a bijective function between them? Mathematicians extend this idea to infinite sets.

Now let's see if there is a bijective function from $\mathbb Z^+$ to $\mathbb Z$. Consider $$f(x)=\cases{x/2 & \text{ if $x$ is even}\\-(x-1)/2 & \text{ if $x$ is odd}}.$$

Thus, $$f(1)=0$$ $$f(2)=1$$ $$f(3)=-1$$ $$f(4)=2$$ $$f(5)=-2$$ $$\vdots$$ The list goes on. Can you see why $f$ is bijective? Every integer gets mapped to exactly one time. Thus, $\mathbb Z^+$ and $\mathbb Z$ are the same size.

$\endgroup$
3
$\begingroup$

Your intuition fails you here because you are starting to consider what happens with infinite sets. Everything you've learned about numbers really applies to finite sets.

The set of all positive integers is actually the same size as the set of all integers. This is because I can find a way to "pair" all the elements of one set with a unique element of the other set.

Eventually, you will be able to say:

The cardinality of the infinite set of positive integers is the same as the cardinality of the infinite set of integers because there exists a bijection between the two sets.

$\endgroup$
  • $\begingroup$ What would the bijective function be? I can't think of any function that could "pair" all the elements from $\mathbb{Z}^+$ to $\mathbb{Z}$ $\endgroup$ – user169330 Jun 25 '15 at 18:44
  • $\begingroup$ @NicoA See the answer of Alex S. $\endgroup$ – Eff Jun 25 '15 at 18:45
2
$\begingroup$

Here's an attempt at a more intuitive answer:

First, you need to realize that the common intuitive reasoning you have (such as "if we add one more element, we get more elements") is limited to finite sets, and doesn't quite work for infinite sets. In some sense, dealing with infinity requires you to "forget" what you know and start fresh.

One great way to look at the problem is to consider Hilbert's paradox of the Grand Hotel, which I will briefly describe here:

There's a hotel with an infinite number of rooms, numbered 1, 2, 3, ... (never ending). Currently, every room is occupied by a guest. Then a new guest comes and asks for a room. Is the hotel really full? Basically, it is, but the receptionist sends a message to every guest to move to the next room (at the same time), and suddenly room 1 is available. You still have the same number of rooms, but now you can add one more guest.
Does the hotel have more guests now? If you look at the guests, you apparently have one more, but the rooms are just as occupied as they were before.

What if there's an infinite number of new guests rather than just one? Let's call them N1, N2, N3, etc, and the old guests O1, O2, O3, etc. Well, simple: ask every old guest On to move from room n to room 2n, then you can fit every new guest Nn in room 2n-1. Again, you still have the same number of rooms, and every room is occupied by one guest, just as it was before.

The first situation matches your $\mathbb{Z}^{\geq-1}$ case, and the second situation matches your full $\mathbb{Z}$ case, as when you compare $\mathbb{Z^+}$ with $\mathbb{Z}$, you can associate the left side ($\mathbb{Z^+}$) with the rooms, the positive numbers on the right side with the old guests, and the negative numbers with the new guests.

So there are just as many positive integers as all integers. In layman terms, $\infty$ + 1 = $\infty$ and $\infty$ + $\infty$ = $\infty$; don't try to subtract them though, as they are not actual numbers.

Finally, the matching between guests and rooms (when the hotel is full) is a bijection, and all the infinities I discussed above are "countable"; there are other, "bigger" kinds of infinities which are uncountable and don't have a bijection with $\mathbb{Z}$, one example being $\mathbb{R}$.

$\endgroup$
1
$\begingroup$

As mentioned in the other answers, the sets $\Bbb{N},\Bbb{Z}$ have the same "size" because there is a bijection between them. However, another measure of size of infinite sets, density, can be used. Density is defined as $\lim_{n\to\infty} \frac{A(n)}{n}$, where $A_n$ is the number of elements in your set. We find that the density is $\frac 12$.

$\endgroup$
0
$\begingroup$

There are many wonderful answers already, but I want to show you one additional point, that's often neglected. The issue is that the word "more" becomes ambiguous when you start speaking about infinite sets.

Look at the set of all nonnegative integers (N0) and set of all positive integers (N*). It is completely correct (though misleading) to say that N0 has one element more than N*. After all, N0 = N* U {0}, the union is disjoint, and {0} certainly has one element. And there is a precise way to formulate these things: equation k(N0) = k(N*) + 1 is completely mathematically correct.

But there is another sense in which "more" can be understood: that the number of nonnegative natural numbers is greater (and different) than the number of positive natural numbers. That's obviously untrue, and the easiest way to see this is to consider the infinite sequence of pieces of paper. First one has 0 on one side, and 1 on the other. Second one has 1 on one side, and 2 on the other. Third one has 2 on one side, and 3 on the other. And so on... I'm sure you get the pattern.

Now, if I ask you how many pieces of paper there are, it's obvious you'd be correct to say there are as many as nonnegative integers. And after you turn them around, you'd be correct to say there are as many as positive integers. If you now realize that turning each individual piece of paper around didn't change their number, you'll have to agree there are as many nonnegative integers as there are positive integers.

How is it possible? Simply, as I said, the phrase "there are more As than Bs" might mean "there are x more As than Bs", that is, a = b + x; and it might mean "the number of As is greater than that of Bs", that is, a > b. The first simply doesn't imply the second. Even for finite sets this doesn't have to be true, if x is zero. It's just that for infinite sets, there are more "negligible" values of x.

$\endgroup$