# 'random' maps between infinite sets

1. Jan 22, 2009

### tgt

Say we want to map elements from one infinite set into another. But there is no function or formula to which all elements can be assigned hence we will need to specify or list the elements one by one. However this process of listing will never finish since we have infinite sets. Has anyone come across this problem before? How do people go about it?

2. Jan 22, 2009

### Hurkyl

Staff Emeritus
This is the sort of question that tends to have a straightforward answer... but only if you are exceedingly clear and precise about what exactly you mean to ask.

3. Jan 23, 2009

### tgt

Isn't it clear?

Some maps are functions where the input is clearly defined and the output can be calculated straight forwardly. But what happens if there is no function to assign the elements? Then defining the map would be on an element by element basis only. Since there is no rule and there are an infinite number of elements, listing it all is impossible so there will always be some elements that we don't know will get mapped to what.

i.e Say we map elements from the natural numbers into the Natural Numbers. But there is no rule or formula for assigning arbitrary elements. So one can only list 1->4, 2->45, 3->90, ... one is only mapping elements across individually. If you're wondering why 4, 45, 90, ... it's because that's what I felt like these numbers should be associated to at that time. Hence you can see the lack of order in assigning the numbers and no wonder why no function can be found.

4. Jan 23, 2009

### signerror

There is a famous (?) paradox here, in that there is (for example) no uniform real-valued measure over the real numbers such that the measure of the entire real line is finite. In particular there is no uniform probability measure, such that p((-inf, +inf)) = 1.

5. Jan 23, 2009

### wsalem

Asking "is it straight forward to calculate the function at a point" is different from "is it defined at that point".
There's always a "total" function mapping a set (whether infinite or not, except perhaps for the empty set, which is a partial function) to something. Take the identity function(for a one-to-one onto function), or a constant function for instance.
Of course when you take two different sets and start asking whether a one-to-one or an onto function can exist there might be some limitations, but that doesn't seem to be the issue here!

Defining a function is not limited to an equation or by an element by element basis, they can be defined set theoretically merely by satisfying certain properties.

The result of your feelings is a partial mapping, i.e a mapping which misses some elements from the domain. This is quite different from a (total) function, but nonetheless, you can turn this into a function! Let p: A ->B be a partial map from A to B, where it's defined for at least one element of A, denoted the set of such elements D. Then it's not hard to see that f:D->B is a function, where f is defined similar to p!

Last edited: Jan 23, 2009
6. Jan 23, 2009

### Werg22

The idea of a mapping between infinite sets is an abstract idea and is manipulated without concern for the things you're worried about. The way you use "function, formula" indicates that to deal with a function we need to know an association rule which defines it. This is not the case, at least not in contemporary mathematics.

7. Jan 23, 2009

### Hurkyl

Staff Emeritus
No. "Function" and "map" are synonymous, along with rule (I think). If you have a function, then you have a map as well as a rule. Functions need not be (uniquely) expressed by a formula. If you have a function expressed by a formula, there is no guarantee that you can do "computation", even in principle.

For example, consider the annoying function from the set {0} to the set {1, 2}, defined by the following formula:

$$f(0) = \begin{cases} 1 & |\mathbb{R}| = |\mathcal{P}(\mathbb{N})| \\ 2 & |\mathbb{R}| \neq |\mathcal{P}(\mathbb{N})| \end{cases}$$

The proposition $f(0) = 1$ is undecidable in ZFC -- it is strictly impossible* to determine whether this statement is true or false.

Furthermore, there is no problem dealing with indeterminate functions; using the indeterminate variable f to denote a real-valued function of the reals operates on exactly the same principle as letting the indeterminate variable x denote a real number.

Any of these answers can change dramatically, just by making a small change in the particulars of the question you're asking.

*: Assuming ZFC is consistent

8. Jan 25, 2009

### Citan Uzuki

I thought $|\mathbb{R}| = |\mathcal{P}(\mathbb{N})|$ was an easily proved theorem of ZFC. Are you sure you don't mean $|\mathbb{R}| = \aleph_1$?

9. Jan 25, 2009

### Hurkyl

Staff Emeritus
Yes, that's what I meant.

10. Jan 25, 2009