# Cardinality of 1-1 mappings of integers to themselves

I think the cardinality of the set M of all 1-1 mappings of the integers to themselves should be the same as the cardinality of the real numbers, which I'll denote by $\aleph_1$. My naive reasoning is:

The cardinality of all subsets of the integers is $\aleph_1$. A subset of the integers can be identified with 1-1 mapping of the integers onto the set consisting of only two integers {0,1}. So the cardinality of M should be at least that large.

A 1-1 function is a set of ordered pairs of numbers that satisfy certain conditions. The set of all ordered pairs of integers has a cardinality $\aleph_0$. The set S of all possible subsets of that set has cardinality $\aleph_1$. The set M is proper subset of S so the cardinality M should be at most $\aleph_1$.

Perhaps I need some famous "optional" assumption of mathematics, such as the continuum hypothesis, to justify some of those statements.

## Answers and Replies

Gold Member
Both of these sets have the same cardinality as you suggested and no other assumptions are necessary. Also, you should denote the cardinality of the real numbers by $2^{\aleph_0}$

Thank you for the confirmation.

I'm looking for a way to cheat the devil and define a "uniform" distribution on the set of non-negative integers. My proposal:

Let M be the set of 1-to-1 mappings of the non-negative integers onto themselves. Let F be a 1-to-1 mapping between the elements of M and the real numbers in the interval [0,1]. Let G be a probability distribution defined on the non-negative integers (such as a Poisson distribution). Consider the following process of sampling from the integers. Pick an integer k from the distribution G. Pick a real number x from the uniform distribution on [0,1]. Find the map f = F(x). Let the value chosen from the integers be f(k).

If that method works then it is "uniform" in the sense that no integer has a special status. Of course it isn't "uniform" in other senses of that word.

Nice example Stephen Tashi, but I have one question: have you got an analogue to sample a particular value?

ImaLooser
I think the cardinality of the set M of all 1-1 mappings of the integers to themselves should be the same as the cardinality of the real numbers, which I'll denote by $\aleph_1$. My naive reasoning is:

The cardinality of all subsets of the integers is $\aleph_1$. A subset of the integers can be identified with 1-1 mapping of the integers onto the set consisting of only two integers {0,1}. So the cardinality of M should be at least that large.

A 1-1 function is a set of ordered pairs of numbers that satisfy certain conditions. The set of all ordered pairs of integers has a cardinality $\aleph_0$. The set S of all possible subsets of that set has cardinality $\aleph_1$. The set M is proper subset of S so the cardinality M should be at most $\aleph_1$.

Perhaps I need some famous "optional" assumption of mathematics, such as the continuum hypothesis, to justify some of those statements.

The continuum hypothesis is this: that the smallest set that has a cardinality greater than the integers is the real numbers. Another way to write this is that the real numbers have the cardinality $\aleph_1$. It was shown (amazingly enough) that this is neither true nor false. Assume it if you like, deny it if you like.

ImaLooser
Thank you for the confirmation.

I'm looking for a way to cheat the devil and define a "uniform" distribution on the set of non-negative integers. My proposal:

Let M be the set of 1-to-1 mappings of the non-negative integers onto themselves. Let F be a 1-to-1 mapping between the elements of M and the real numbers in the interval [0,1]. Let G be a probability distribution defined on the non-negative integers (such as a Poisson distribution). Consider the following process of sampling from the integers. Pick an integer k from the distribution G. Pick a real number x from the uniform distribution on [0,1]. Find the map f = F(x). Let the value chosen from the integers be f(k).

If that method works then it is "uniform" in the sense that no integer has a special status. Of course it isn't "uniform" in other senses of that word.

Aha. Well, in order to pick a real number x from the uniform distribution on [0,1) you have to assume the axiom of choice. It isn't possible to actually do it. So you might as well use the axiom of choice to assume that you can pick a natural number from a uniform distribution.

have you got an analogue to sample a particular value?

If you're asking if I can sample an exact value from the uniform distribuiton on the reals in [0,1], my answer is no. But in the example, I'll assume this is possible, just as statistics texts do!

I'm hoping that this method method remains enitrely theoretical and un-approximable by any form of actual sampling. I'm still on my mission to make the world develop useful definitions of what it means for a probability distribution to be aproximable by sampling from discrete distributions. No takers, so far. So perhaps if I produce a pathological example someone will resent it enough to create a precise definition and , using that definition, prove he can approximate all reasonable probability distsributions.