Examples of Surjections from Uncountable Sets to Countable Sets

[honestrosewater]

Just to get a feel for surjections, I'm trying to think of some surjections from uncountable sets to countable sets. For R to N, I thought of using what I found out is called the ceiling function, but I can't think of any others. So, for instance, for the set of reals 0 < r < 1 to N, I can't think of any. Does anyone know of some examples?
BTW, I'll try to figure out next if it holds in general that if A is uncountable and B is countable, there exists a surjection from A to B, so if you can help it, please don't give me a proof :) Thanks.

 

[snoble]

you could always map the (0,1) interval to the entire reals by using the tan function then using the ceil function at that point. Or you could do something weird like right down a real number in decimal representation then take the digits until the first 8 (not taking that 8). Remove the 9's and use that as your integer base 8. If there are 9's that you removed map it to a negative number. If there are no eights in the decimal representaion map the element to 0. To make sure this is well defined you'll have to deal with the decimal rep ambiguity. Probably easier to just use the first surjection.

 

[AKG]

BTW, I'll try to figure out next if it holds in general that if A is uncountable and B is countable, there exists a surjection from A to B, so if you can help it, please don't give me a proof :) Thanks.

For a hint (I guess I can't help myself) think about what you know about functions between sets of equal cardinality, and think about the function you already know from R to N.

 

[honestrosewater]

snoble,
Thanks for the suggestions. I haven't learned trigonometry but, looking at the tan function's graph, I can see what you're saying. I can't think of how to prove that your second suggestion would be a surjection, but I'll keep it in mind as a problem down the road.

I did think of a surjection from (0, 1) to N, analogous to the ceiling function, using the set {1/1, 1/2, ..., 1/n, 1/(n+1), ...}. I'm not quite used to the notation, but if r is in (1/(n+1), 1/n], then (r, n) is in G, where G is the graph of the function.

AKG,
I think a proper proof is a bit beyond me for now. My definitions: A set C is countable if there exists a bijection from C to N. A set is uncountable if it is neither finite nor countable. I don't know enough about ordering to get the proof started, but your suggestion helped. Roughly, given an uncountable set U and a countable set C, if I assume that every uncountable set has at least one countable subset C_U, (I can prob prove this soon), since there exists a bijection from C_U to C, there exists a surjection from C_U to C. So I can just use that surjection and map every member of U that isn't in C_U to the same member of C.

Thanks to you both :)

 

[honestrosewater]

I think there's a similar proof for finite sets B and C, using something like modular arithmetic, with |C| as the modulus, but I don't know how to express it. Forgiving my liberal use of notation...
Conjecture: If B and C are finite sets and |B| > |C|, then there exists a surjection from B to C.
A set B is finite if it is empty or there exists a bijection from B to {1, 2, ..., n}, for some n in N (this n = |B|).
For nonempty B and C, arrange the members b of B into a |B|-tuple (b₁, b₂, ..., b_|B|), and do the same for C. Map b_i to c_j, where i = j (mod |C|). Does that makes sense? For example, if B = {2, 7, 12} and C = {4, 19}, then the tuples could be (2, 7, 12) and (4, 19) respectively, and the surjection's graph would be {(2, 4), (7, 19), (12, 4)}.
I'm not sure about empty sets. I remember someone mentioning the empty function, so I'll look it up. But if functions are defined for empty sets and C is empty, I imagine there exists a surjection from any set to C.

 

[snoble]

Yeah that finite proof makes sense to me. Although it would probably be easier if instead of creating tuples you just used the bijections between your set and {1,2,...,n}. You just want your set indexed and that's a natural way to do it.

As for the empty set I'm not so sure about that last statement. It looks like the definition of a function you are using is a subset of AxB where every element of A shows up in exactly one pair. That's the definition I would use at least. But if B is the null set then AxB is also the null set. So if there is an element 'a' in A the second axiom of a function doesn't seem to get satisfied; ie there are no subsets of AxB where 'a' shows up in exactly one pair. If A is empty as well then you should be fine.

But I'm not really a set theorist so someone may want to correct me.

And your Countable uncountable stuff seems to have merit. You just want to prove your assumption that every uncountable set has a countable subset. Personally I would do this by trying to showing there is an injection from N to U (by using only the fact that a set is uncountable if it is neither finite nor countable). Then what can you say about the image of this injection. I'll leave that thought with you if you want to develop it yourself.

Hope some of that helps
Steven

 

[matt grime]

There are obvioulsy infinitely many surjections from R to N.

Here are several ways to make some:

Send n to n, since N is a subset of R, now just send everyother element to something, who cares what, you could send 'em all to 1, or 2 or whatever, those that have a 7 in their decimal expansion could get sent to 4 and those without get sent to 1,400,354,333.

It appears, though that you want a nice explicit computable function, as any constructivist may deem appropriate.

And, yes, every infinite set has a countable subset (at least in my model of set theory), though someone may well tell me it requires the axiom of choice.

 

[honestrosewater]

Yeah that finite proof makes sense to me. Although it would probably be easier if instead of creating tuples you just used the bijections between your set and {1,2,...,n}. You just want your set indexed and that's a natural way to do it.

Yeah, that's all I meant to do with the tuples. How would I say that?

As for the empty set I'm not so sure about that last statement. It looks like the definition of a function you are using is a subset of AxB where every element of A shows up in exactly one pair. That's the definition I would use at least. But if B is the null set then AxB is also the null set. So if there is an element 'a' in A the second axiom of a function doesn't seem to get satisfied; ie there are no subsets of AxB where 'a' shows up in exactly one pair. If A is empty as well then you should be fine.

But I'm not really a set theorist so someone may want to correct me.

I think you're right. I was just thinking that f is a map from A to B if the domain of f = A and the range of f is a subset of B, and the only difference between a map and surjection is that, for the latter, the range of f = B. So if f is a map from A to B and B is empty, then f would also be a surjection from A to B. But looking at my definitions, it does seem that if the range of f is empty, the domain of f would also be empty.

And your Countable uncountable stuff seems to have merit. You just want to prove your assumption that every uncountable set has a countable subset. Personally I would do this by trying to showing there is an injection from N to U (by using only the fact that a set is uncountable if it is neither finite nor countable). Then what can you say about the image of this injection. I'll leave that thought with you if you want to develop it yourself.

I sure will- injections are next on the list ;)

Hope some of that helps
Steven

Sure does, and I appreciate the effort either way :)

 

[honestrosewater]

It appears, though that you want a nice explicit computable function, as any constructivist may deem appropriate.

I think I'm closer to a formalist than anything else, but eh, whatever. I was just looking for some different approaches.

And, yes, every infinite set has a countable subset (at least in my model of set theory), though someone may well tell me it requires the axiom of choice.

I'll still try for the other proof, but couldn't I just use a different definition: If U is infinite and every countable subset of U is a proper subset of U, then U is uncountable? It should then follow immediately that every uncountable set has a countable subset. But I guess I'm just making more work for myself since I would still have to prove that the two definitions were equivalent.

 

[matt grime]

dealing wiht surjections natrually leads to the axiom of choice, whereas with injections one doesn't need it.

The standard proof to show every infinite set has a countable subset is this:

B is infinite, and so not empty, let b(1) be some element of B. Then B \ {b(1)} is also not empty, and pick b(2) in it, since B is not finite, this process can be repeated to get a subset b(n) for all n in N.

 

[mansi]

here's an exercise you might find interesting...
find a bijection from the real line to the unit square in the plane...

 

[snoble]

Yeah, that's all I meant to do with the tuples. How would I say that?

I personally would say that something like this. B and C are finite with $$|B| =n \ge m =|C|$$. So there are bijections f,g st $$f:B\rightarrow \{1,2,\ldots ,n \}$$ and $$g:C\rightarrow \{1,2,\ldots ,m \}$$. So just use your argument so that you have a surjection that maps b to c such that $$f(b) \equiv g(c) (mod\,m)$$

Again that's how I would do it but I do tend to be a little overly wordy so it could probably be done a little more concisely.

Cheers,
Steven

 

[honestrosewater]

mansi,
Thanks- I don't know what that means ;) but I'll look it up.

matt,
Thanks, I'll keep that in mind. The AC isn't presented until later, and I can't read the definition yet.

snoble,
I didn't forget, just busy. The injection from N to U followed by induction on subsets of N, using only that U was infinite. I had to look up images, but I guess it's straightforward- the image of the injection is a countable subset of U. The image of the injection also provides a surjection from U to N, mapping the rest of U to whatever member(s) of N.

I would clean everything up, but the treatment in my book is informal, so I guess it's clean enough. I'll find a formal treatment though. Anyway, after playing with this for a while, the cardinalities seem to tell most of the story. The empty set aside, if |B| > |C|, there exists a surjection from B to C; if |B| < |C|, there exists an injection from B to C; bijections are surjections and injections, so if |B| = |C|, there exists a bijection from B to C. A bijection (=) is an equivalence relation; surjections (>) and injections (<) are both reflexive, non-symmetric, and transitive. Right? Does that sum it up well, or do I have a lot more to learn about them?

 

[AKG]

mansi

How about some hints on that problem. Thanks.

 

[mansi]

may be you could start by finding a one-one, onto map from [0,1] to [0,1] (cross) [0,1]. i mean a bijective map from [0,1] to the unit square in the plane.

 

[AKG]

Take the decimal expansion of a number. If there are two possibilities (e.g. 0.39999999... and 0.4) then take the one with repeating 9's. Then, the following map:

$$f : 0.x_1x_2x_3\dots \longrightarrow (0.x_1x_3x_5\dots, 0.x_2x_4x_6\dots )$$

is not a bijection, but may be close. Well, it's onto, because for any point on the square

$$(0.a_1a_2a_3\dots , 0.b_1b_2b_3\dots )$$

there is certainly a number x on [0,1] such that

$$x = 0.a_1b_1a_2b_2\dots$$

It's not 1-1 though, because the following 3 (and only those 3)

0.3490909090...
0.4309090909...
0.3399999999... = 0.34

would all map to the point (0.4, 0.4). The reason why 0.44000000... would not map to that point is because the original stipulation that 0.44000000... would have to be read as 0.43999999... which would map to (0.5, 0.4). I'll come back to this.