Cardinality of 1-1 mappings of integers to themselves

In summary: I don't know...another method?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
  • #1
Stephen Tashi
Science Advisor
7,861
1,598
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 [itex] \aleph_1 [/itex]. My naive reasoning is:

The cardinality of all subsets of the integers is [itex] \aleph_1 [/itex]. 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 [itex] \aleph_0 [/itex]. The set S of all possible subsets of that set has cardinality [itex] \aleph_1 [/itex]. The set M is proper subset of S so the cardinality M should be at most [itex] \aleph_1 [/itex].

Perhaps I need some famous "optional" assumption of mathematics, such as the continuum hypothesis, to justify some of those statements.
 
Physics news on Phys.org
  • #2
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 [itex]2^{\aleph_0}[/itex]
 
  • #3
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.
 
  • #4
Nice example Stephen Tashi, but I have one question: have you got an analogue to sample a particular value?
 
  • #5
Stephen Tashi said:
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 [itex] \aleph_1 [/itex]. My naive reasoning is:

The cardinality of all subsets of the integers is [itex] \aleph_1 [/itex]. 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 [itex] \aleph_0 [/itex]. The set S of all possible subsets of that set has cardinality [itex] \aleph_1 [/itex]. The set M is proper subset of S so the cardinality M should be at most [itex] \aleph_1 [/itex].

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 [itex] \aleph_1 [/itex]. It was shown (amazingly enough) that this is neither true nor false. Assume it if you like, deny it if you like.
 
  • #6
Stephen Tashi said:
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.
 
  • #7
chiro said:
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.
 
  • #8
Maybe later on you're going to get a statistical paradox named after you ;)
 
  • #9
ImaLooser said:
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.
 
Last edited:

1. What does "cardinality" mean in this context?

Cardinality refers to the number of elements in a set. In this case, it refers to the number of unique one-to-one mappings between integers and themselves.

2. What is a "1-1 mapping"?

A 1-1 mapping, also known as a one-to-one correspondence, is a relationship between two sets where each element in the first set is paired with exactly one element in the second set, and vice versa.

3. How do you determine the cardinality of 1-1 mappings of integers to themselves?

The cardinality of 1-1 mappings of integers to themselves is equal to the number of integers in the set. This is because each integer can be mapped to itself, creating a one-to-one correspondence.

4. Is the cardinality of 1-1 mappings of integers to themselves infinite?

Yes, the cardinality of 1-1 mappings of integers to themselves is infinite. This is because there is an infinite number of integers, and each one can be mapped to itself, creating an infinite number of one-to-one correspondences.

5. What is the significance of the cardinality of 1-1 mappings of integers to themselves?

The cardinality of 1-1 mappings of integers to themselves is a fundamental concept in set theory and mathematics. It helps us understand the concept of infinity and the relationship between different sets. It also has applications in computer science and data analysis.

Similar threads

  • Set Theory, Logic, Probability, Statistics
Replies
9
Views
1K
  • Set Theory, Logic, Probability, Statistics
Replies
7
Views
1K
  • Set Theory, Logic, Probability, Statistics
Replies
16
Views
1K
  • Set Theory, Logic, Probability, Statistics
Replies
6
Views
1K
  • Set Theory, Logic, Probability, Statistics
Replies
2
Views
1K
  • Set Theory, Logic, Probability, Statistics
Replies
4
Views
2K
Replies
1
Views
910
  • Set Theory, Logic, Probability, Statistics
Replies
1
Views
1K
  • Set Theory, Logic, Probability, Statistics
Replies
24
Views
6K
  • Set Theory, Logic, Probability, Statistics
Replies
2
Views
2K
Back
Top