Intereting Posts

Is it always true that $(A_1 \cup A_2) \times (B_1 \cup B_2)=(A_1\times B_1) \cup (A_2 \times B_2)$
Very elementary proof of that Euler's totient function is multiplicative
Comparing Eigenvalues of Positive Semidefinite Matrices
Compact $n$-manifold has same integral cohomology as $S^n$?
What is the difference between “filtration for a Brownian motion” and “filtration generated by a Brownian motion”?
Convergence of $x_{n+1} = \frac12\left(x_n + \frac2{x_n}\right).$
Tensors as matrices vs. Tensors as multi-linear maps
Proving that $\sqrt{2}+\sqrt{3}$ is irrational
Proving Thomae's function is nowhere differentiable.
Frobenius element in cyclotomic extension
Boundaries of finite intersections and unions of sets
When is a metric space Euclidean, without referring to $\mathbb R^n$?
Prove if $|a_{n+1}|/|a_n| \leq |b_{n+1}|/|{b_n}|$ and $\sum |b_n|$ is convergent, then $\sum |a_n|$ is convergent
Bernoulli polynomial root symmetry
How do I prove this method of determining the sign for acute or obtuse angle bisector in the angle bisector formula works?

We will call the set of all positive even numbers `E`

and the set of all positive integers `N`

.

At first glance, it seems obvious that `E`

is smaller than `N`

, because for `E`

is basically `N`

with half of its terms taken out. The size of `E`

is the size of `N`

divided by two.

You could see this as, for every item in `E`

, two items in `N`

could be matched (the item x and x-1). This implies that `N`

is **twice as large as E**

- Show that $A∩B∩C= ∅$ is only true when $A∩B = ∅, A∩C = ∅$ or $B∩C = ∅$ or show a counterexample.
- Why do we distinguish between infinite cardinalities but not between infinite values?
- If $(f\circ g)(x)=x$ does $(g\circ f)(x)=x$?
- The cardinality of $\mathbb{R}/\mathbb Q$
- Does continuity depend on the distance function?
- When does it make sense to define a generator of a set system?

On second glance though, it seems less obvious. Each item in `N`

could be mapped with *one* item in `E`

(the item x*2).

Which is larger, then? Or are they both equal in size? Why?

(My background in Set theory is quite extremely scant)

- Logical Form - Union of a Set containing the Power Set with Predicate/Propositional Function
- Number of $\sigma$ -Algebra on the finite set
- If the union of two sets is contained in the intersection, then one is contained in the other ($\implies A \subseteq B$)
- Is it always true that $(A_1 \cup A_2) \times (B_1 \cup B_2)=(A_1\times B_1) \cup (A_2 \times B_2)$
- Complement of a set and inverse image.
- Limit to infinity and infinite logarithms?
- Rigorous proof that surjectivity implies injectivity for finite sets
- Cardinal equality: $\;\left|\{0,1\}^{\Bbb N}\right|=\left|\{0,1,2,3\}^{\Bbb N}\right|$
- The Intersection of Ordered Pairs
- First year calculus student: why isn't the derivative the slope of a secant line with an infinitesimally small distance separating the points?

Mathematics is the art of clever forgetting. The first mathematical breakthrough, numbers, came about when people realized that if you just forgot about whether it was 5 cows + 3 cows, or 5 rocks + 3 rocks or whatever you always got 8. Numbers are what you get when you look at collections of objects and *forget what kind of object they are*.

When you say “as sets” you mean you’re forgetting a lot of information, in particular you don’t care about what the names of the elements in that set are or what properties those elements have. As sets the positive numbers and the positive even numbers are “the same” (that is are in bijection) because you can take 1,2,3,… and just *rename* 1 to 2, and 2 to 4, and n to 2n, and you’ve just renamed all the elements and got the even numbers!

However, if you want to remember more about these sets, for example that they’re not arbitrary sets they’re both subsets of the natural numbers, then they become distinguishable. Depending on how you want to measure “size of a subset of the natural numbers” they might be different sizes. For example, a common way to measure “size of a subset of the natural numbers” is by its “density.” That is you look at the first N numbers and calculate what fraction of them are in your set, and then take the limit as N goes to infinity (warning for sufficiently complicated sets this limit might not exist). So for your two examples, one has density 1 and the other has density 1/2, which is one way to make precise the intuition that the former is bigger *as a subset of the natural numbers* (though not *as a set*) than the latter.

The word ‘size’ doesn’t have a intuitive meaning for set of infinite items.

Mathematicians defined cardinality by one-to-one correspondence(bijection), and it’s generally what it means by ‘size’.

If there **exist** a bijection between A and B, then the two sets have the same cardinality. You have shown the existence of a bijection, therefore E and N have the same cardinality.

You might mean the ‘density’ of N is twice as large as E. density of A(a subset of natural number) is limit of |{a<=n|a\in A}|/n as n goes to infinity.

They are both the same size, the size being ‘countable infinity’ or ‘aleph-null’. The reasoning behind it is exactly that which you have already identified – you can assign each item in E to a single value in N. This is true for the Natural numbers, the Integers, the Rationals but not the Reals (see the Diagonal Slash argument for details on this result).

— Added explanation from comment —

The first reasoning is invalid because the cardinality of infinite sets doesn’t follow ‘normal’ multiplication rules. If you multiply a set with cardinality of aleph-0 by 2, you still have aleph-0. The same is true if you divide it, add to it, subtract from it by any finite amount.

Almost all of this misses the idea that you can’t do traditional arithmetic with infinity that way that most of us think of it. 10/2 = 5, five is half of 10, no problem. If Judy has five apples and Joe has 10 apples, then it is proper to say “Judy has half as many apples as Joe.” But to say “there are half as many even positive integers as there are positive intergers” is to infer something about infinity/2, or half of infinity, which is not entirely kosher.

Each item in N could be mapped with one item in E (the item x*2).

Yes. Both sets have cardinality aleph-0.

Your example is an example of a countable sets: http://en.wikipedia.org/wiki/Countable_set

As others have explained, if you find a bijection between these two sets then they are of the same cardinality or have the same number of elements.(I hope that statement is true :)) But in this case you have found one with N which is what makes it a countable set. f(x)=2x would be an example of a bijection between N and 2N. Since for every x in the set of natural numbers there is a corresponding number in the set of 2N (only one) then you can say that they have the same cardinality.

A cooler example would be the interval of the real numbers (0, 1) and R itself, those are not countable but their cardinality is the same.

Other notes, if you are wondering what aleph is: http://en.wikipedia.org/wiki/Aleph_number

You can also get it the other way around — N is (kind of) a subset of E.

Map each integer n into 4n. Then there’s a bijection (1-1, onto function) between N and (let’s call it) N4, the set of all integers divisible by 4, so N and N4 are, in your intuition, of the same “size”. But N4 is a proper subset of E ! Of course, you could just as well have mapped N directly to E with bijection f(n) = 2n.

Anyway, that shows you how slippery it is to apply concepts of finite size to infinite sets, and why bijection is the way to go.

The density argument above is not quite to the point, since it involves not only a set but an ordering.

In fact, if you play with orderings, you can get even stranger results, such as the integers and rationals can both be ordered as a continuum (according to the ordering, between any two members in the set there is another member) and a non-continuum (there are two members with no other member in between). Or worse, between any two members is at most a finite set of other members (non-continuum) or an infinite set of other members (continuum). That’s kind of an extreme form of density.

How about a proof by induction? Start with n = 2. Let n’ = n + 2 = 4. Then there are n’ / 2 = 4 / 2 = 2 positive even integers <= 4. Repeat. Now n = n’ = 4, n’ = n + 2 = 6. There are n’ / 2 = 6 / 2 = 3 positive even integers <= 6. This process may be continued indefinitely, so that there will always be n’ / 2 positive even integers <= n’. Therefore there must be twice as many positive integers as there are positive even integers, hence the set of positive integers is larger than the set of positive even integers.

- Fundamental group of the product of 3-tori minus the diagonal
- If a Matrix Has Only Zero as an Eigen-Value Then It Is Nilpotent
- line at infinity
- Prove XOR is commutative and associative?
- If I have that $X$ is a random variable satisfying $0\leq X \leq 1$, how can I show that $P\left(X \geq \frac{E(X)}{2}\right) \geq \frac{E(X)}{2}$?
- Is Kaplansky's theorem for hereditary rings a characterization?
- Reference for Gauss-Manin connection
- Diagonalisable or not?
- Zero Sectional Curvature implies exp is a local isometry
- If $4^n + 2^n + 1$ is prime, then $n$ must be a power of $3$
- Confused about complex numbers
- Explain Carmichael's Function To A Novice
- Is the group isomorphism $\exp(\alpha x)$ from the group $(\mathbb{R},+)$ to $(\mathbb{R}_{>0},\times)$ unique?
- Inverse of this $3$-by-$3$ matrix using the Cayley–Hamilton theorem
- Unit and counit are close to being inverses