Cardinality of 1-1 mappings of integers to themselves

[Stephen Tashi]

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.

 

[jgens]

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}

 

[Stephen Tashi]

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.

 

[chiro]

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.

 

[Stephen Tashi]

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.

 

[chiro]

Maybe later on you're going to get a statistical paradox named after you ;)

 

[mXSCNT]

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.

Not true. The axiom of choice is only needed for choosing one element from each of an uncountably infinite number of sets. You don't need it to choose an element of a single set such as the real numbers (or any countable number of sets).

Stephen, I suspect the problem with your scheme is that f(k) is not going to be unbiased. A simpler but basically equivalent scheme would be to just let the result be f(1). (Your scheme reduces to this scheme whenever your distribution over the natural numbers has P(1) = 1). There's no guarantee that f(1) will be unbiased, and I believe any F you construct would be biased so that certain integers come up on f(1) (or f(k) if you prefer) more often than others.