Register to reply

Examples of surjections

by honestrosewater
Tags: examples, surjections
Share this thread:
honestrosewater
#1
May1-05, 04:28 AM
PF Gold
honestrosewater's Avatar
P: 2,330
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.
Phys.Org News Partner Science news on Phys.org
Sapphire talk enlivens guesswork over iPhone 6
Geneticists offer clues to better rice, tomato crops
UConn makes 3-D copies of antique instrument parts
snoble
#2
May1-05, 09:28 AM
P: 127
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
#3
May1-05, 12:45 PM
Sci Advisor
HW Helper
P: 2,586
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
#4
May2-05, 02:18 AM
PF Gold
honestrosewater's Avatar
P: 2,330
Examples of surjections

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 CU, (I can prob prove this soon), since there exists a bijection from CU to C, there exists a surjection from CU to C. So I can just use that surjection and map every member of U that isn't in CU to the same member of C.

Thanks to you both :)
honestrosewater
#5
May2-05, 03:59 AM
PF Gold
honestrosewater's Avatar
P: 2,330
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 (b1, b2, ..., b|B|), and do the same for C. Map bi to cj, 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
#6
May2-05, 07:00 AM
P: 127
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
#7
May2-05, 08:17 AM
Sci Advisor
HW Helper
P: 9,398
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
#8
May2-05, 09:00 AM
PF Gold
honestrosewater's Avatar
P: 2,330
Quote Quote by 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.
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
#9
May2-05, 09:26 AM
PF Gold
honestrosewater's Avatar
P: 2,330
Quote Quote by matt grime
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
#10
May2-05, 09:40 AM
Sci Advisor
HW Helper
P: 9,398
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
#11
May2-05, 11:11 AM
P: 58
here's an exercise you might find interesting...
find a bijection from the real line to the unit square in the plane...
snoble
#12
May2-05, 01:06 PM
P: 127
Quote Quote by honestrosewater
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 [tex]|B| =n \ge m =|C| [/tex]. So there are bijections f,g st [tex] f:B\rightarrow \{1,2,\ldots ,n \} [/tex] and [tex] g:C\rightarrow \{1,2,\ldots ,m \} [/tex]. So just use your argument so that you have a surjection that maps b to c such that [tex]f(b) \equiv g(c) (mod\,m)[/tex]

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
#13
May3-05, 12:58 AM
PF Gold
honestrosewater's Avatar
P: 2,330
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
#14
May3-05, 02:44 PM
Sci Advisor
HW Helper
P: 2,586
mansi

How about some hints on that problem. Thanks.
mansi
#15
May4-05, 01:55 AM
P: 58
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
#16
May6-05, 05:17 PM
Sci Advisor
HW Helper
P: 2,586
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:

[tex]f : 0.x_1x_2x_3\dots \longrightarrow (0.x_1x_3x_5\dots, 0.x_2x_4x_6\dots )[/tex]

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

[tex](0.a_1a_2a_3\dots , 0.b_1b_2b_3\dots )[/tex]

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

[tex]x = 0.a_1b_1a_2b_2\dots [/tex]

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.


Register to reply

Related Discussions
Composites of injections/surjections/bijections Calculus & Beyond Homework 8
Limit definition examples Set Theory, Logic, Probability, Statistics 10
Can't think of 2 examples Introductory Physics Homework 1
Trouble w/ injections, surjections, bijections.. Set Theory, Logic, Probability, Statistics 5
Need examples Classical Physics 1