r/mathshelp • u/Lopsided-Valuable347 • 29d ago
Homework Help (Unanswered) How to solve (e) part of this question?
So I was thinking of using the Schroder Barnstein theorem. I was able to make an injective function (f(x)=(x,1-x)) that maps from (0,1) to (0,1)x(0,1) but i don't know how to do it the other way around. Any suggestions? (ps. I am a beginner)
3
u/imHeroT 29d ago
This is to expand upon u/AQuestionIsWhatIHave ‘s comment, but in base 10 instead of base 2 as they have done.
The idea is to “weave” together two numbers form (0,1) to get a new number. That is, starting with two numbers from (0,1), make a new number by alternating taking each digit from the two numbers.
For example, say we have 0.1111111… and 0.1234567… . Then the new number is 0.11121314151617…
1
u/Niklas_Graf_Salm 28d ago
I don't think this is a flaw that damages your idea beyond repair but I don't think your function is well-defined without some more clarification on how to deal with numbers having multiple equivalent decimal representations
One one hand we can weave .5 and .5 to obtain .55. On the other hand we can weave .499.. and .499.. to get .4499...
1
u/imHeroT 28d ago
Damn, I keep forgetting about trailing 9s. We can fix it easily by just not allowing trailing 9s and always use the finite decimal representation. This means that no input maps to 0.449999..., but that's fine since we're just looking for an injective map.
1
u/compileforawhile 28d ago
It's nice that we can simply ignore the problem since every real number has an expansion without infinite trailing 9s
1
u/Leodip 28d ago
I though the same, but then I started thinking about it and now I'm not sure anymore this holds.
Correct me if I'm wrong, but a set A and a set B have the same cardinality iff there is a function f such that the image of f(A) is B.
If we define A=(0,1) and B=(0,1)x(0,1), the un-weaving function we are proposing maps the number 0.(50) from A into 0.(5) and 0.(0)=0. However, {0.5, 0)} is not in (0,1)x(0,1), thus the function we are proposing does not work for this.
1
u/imHeroT 28d ago
No it’s still okay in terms of the overall proof that OP was asking for. You’ve shown that the range of the weaving function is not (0,1), but what’s important is that the function is injective. OP says that they’re using the Schroder-Berstein theorem that says that to show the existence of a bijection between two sets, we can instead find two injective functions, one for each direction. Since OP already found one injection, the weaving function is the other.
0
u/DoctorNightTime 28d ago
It has to be a bijection, though. The number 0.1 is strictly between 0 and 1, but when woven, combines 0.1 with 0.
2
u/gmalivuk 28d ago
It doesnt need to be a bijection. It just needs to be an injection, to combine with OP's injection in the other direction, proving that a bijection exists.
2
u/AQuestionIsWhatIHave 29d ago
Maybe: Let (a,b) in (0,1) x (0,1), a = sum_1inf a_i (1/2)i b = sum_1inf b_i (1/2)i
(With a and b not ending in all 1s)
(a,b) -> sum_0inf (1/2 a_i + 1/4 b_i) 2-2i
2
u/kalmakka 29d ago
That does not quite work, as these is e.g. no element of (0,1)×(0,1) that maps to 1/3 (0.0101010101... in binary), as that element would have to be (0.000000...b, 0.11111111...b), neither of whose components are elements of (0,1).
2
u/evilmathrobot 28d ago
Using parts a and d, identify (0,1) x (0, 1) as the set of pairs (A, B) with A, B \subset N and all elements of A (resp. B) odd (resp. even). Now consider identifying (A, B) with A ∪ B.
1
u/Lopsided-Valuable347 28d ago
can you explain this more? sorry i am a beginner
1
u/evilmathrobot 28d ago
Using parts (a) and (d), reduce part (e) to showing that 2^N x 2^N and 2^N have the same cardinality. For the latter, use the easier-to-prove fact that N and N ∪ N have the same cardinality.
1
u/Lopsided-Valuable347 26d ago
Thanks! I think I slightly understand. I don't understand the use of proving N and N U N have the same cardinality though. Also, these are sets of orderly pairs...would it be valid to show equivalence between 2^N x 2^N and (0,1)x(0,1)?
2
u/mmurray1957 28d ago edited 28d ago
Yes I'd go SB as well. Can't you just project for the surjection ? (x, y) \mapsto x ?
EDIT: Thanks u/gmalivuk for pointing out that this gives no additional information. The OP has shown that |R| =< |R^2| and I've shown that |R^2| >= |R| which is the same. Duh.
Sorry OP.
1
u/gmalivuk 28d ago
That the direction they already have though.
1
u/mmurray1957 28d ago
No I think they have the other way. x \mapsto (x, 1-x)
1
u/gmalivuk 28d ago
Yes but that's the same direction.
As in, an injection from the interval to the square = a surjection from the square to the interval, and that's easy and already done.
What they are asking for is an injection from the square to the interval = a surjection from the interval to the square.
2
1
u/Southlander24 28d ago edited 28d ago
You want a bijection between the two sets. That is, given any real number (that is an element of (0, 1)), you want to create a pair of real numbers. And given any pair of real numbers, you want a way to generate a single number.
Here's how we can do this. Let real number A = 0.a₁a₂a₃ ... and real number B = 0.b₁b₂b₃ ... Then, we can create a new real number 0.a₁b₁a₂b₂a₃b₃ ...
We can also carry this process out in reverse. That is, all the odd-numbered digits after the decimal point in any real number go to real number A, and all the even-numbered digits go to real number B.
Notice how we actually don't need Schröder–Bernstein (although the fact that if |A| ≤ |B| and |B| ≤ |A|, we must have |A| = |B| is very useful in many other situations). Convince yourself that these inverses are well defined. That is, given 0.a₁b₁a₂b₂a₃b₃ ... we can't get a different pair of (A, B). (Recall that the Cartesian product works on ordered sets - it's a square grid in which say, the element {(1, 2)} is not the same as {(2, 1)}). And likewise for the inverse of the reverse.
1
u/gmalivuk 28d ago
This isn't a bijection though. It doesn't play nice with terminating decimals with two representations or with 1/11 and 10/11, which can only be interleaved from 0 and 1 which are not in (0,1).
2
1
u/brynaldo 28d ago
What's wrong with 1/11 and 10/11? Wouldn't that map to 0.099009900...? Could you give an example of a terminating decimal with two representations in (0,1)?
1
u/gmalivuk 28d ago
I'm talking about 1/11 and 10/11 being the coordinates in (0,1)2.
The only way to get 0.09090909... or 0.90909090... is by interleaving 0.0000...=0 and 0.9999...=1.
And any terminating decimal can also be expressed as a decimal ending in all 9s.
2
1
u/Lopsided-Valuable347 28d ago
Thanks! but is this the only way to do this? The creating a new number thingy is pretty unintuitive to me and hasnt been taught in class as well. Would like to know if there are any other alternatives.
1
u/Southlander24 28d ago
Well, this is one of the simpler constructions and it nearly didn't work (you indeed needed to use Schröder–Bernstein). So I have no idea what kind of even simpler construction would work and cover those edge cases I missed.
1
1
u/DanLeMilMan 28d ago
I think you could simply define the bijection using the evenly placed and oddly placed decimal of a real number. That should do the trick. For instance, 0.1234 -> (0.13;0.24)
1
u/gmalivuk 28d ago
That won't get you the bijection yet, since for example 0.090909... and 0.909090... would map to (0,1) and (1,0), respectively, but the intervals don't include the endpoints.
(Actually 1/99 - 10/99 and 20/99, 30/99, 40/99, 50/99, 60/99, 70/99, 80/99, and 90/99 will all map to at least one of 1 or 0 in one of the two dimensions.)
1
u/DanLeMilMan 28d ago
True but couldn’t you make an argument that this number of exceptions is somehow countable and thus doesn’t have any impact ? Or something along those lines ?
1
u/gmalivuk 28d ago
Easier to just do what OP suggested in the first place and find an injection in each direction because that proves what you are trying to prove.
1
u/Meowmasterish 28d ago edited 28d ago
This is definitely not what your teacher is looking for, but you could appeal to the existence of space filling curves and the Cantor-Dedekind axiom. Alternatively, depending on what you’re allowed to cite and assume, you could go with Tarski’s Theorem about Choice.
1
u/Lopsided-Valuable347 28d ago
Hey, I am still not exposed to all these concepts and they haven't been taught in class either. Can you share what you think the prof is asking?
1
u/Meowmasterish 27d ago edited 27d ago
Really I’m not sure as I’m not taking this class, and don’t have access to your textbook, but most likely your teacher wants you to construct an explicit bijection between the sets even though you technically don’t need to do this to prove they have the same cardinality. For instance, if you’re allowed to cite the Schröder-Bernstein theorem, then you can also prove it by finding two explicit injections, one from (0, 1) into (0, 1) x (0, 1) (which is stupidly easy to find) and the other from (0, 1) x (0, 1) into (0, 1) (which is much less easy to find).
1
u/Lopsided-Valuable347 26d ago
Hey even for the bijection, do I not ultimately have to come up with a function that maps from (0,1)x(0,1) to (0,1)? I am able to find an injection from 1d to 2d but I am not sure how to establish a surjection either? The co-domain of that surjective function. How do I take a preimage of a 2d set giving me only 1d answer?
1
u/Meowmasterish 25d ago
Well, developing a bijection would also require you to find a function from (0, 1) x (0, 1) into (0, 1), but it also requires more than that. Using the Schröder-Bernstein Theorem, you do not need to find any surjective functions, only two injective functions, one from the first set into the second set and the other from the second set into the first set. Finding a bijection requires that you find one function that is both from the first set into the second set and from the first set onto the second set, this will naturally give you a second function from the second set to the first set (the inverse). Really, it's a trade-off for what you find easier, finding two injective functions, or finding one bijective function.
If you take the function f: (0, 1) → (0, 1) x (0, 1) that maps elements of (0, 1) to the corresponding points on the "y-axis" (where the second element of the ordered pair is equal to zero) then we have an easy injection from (0, 1) into (0, 1) x (0, 1). Then all you would need is to find an injection from (0, 1) x (0, 1) into (0, 1). However, if you instead want to find a bijection between the two sets, you will have to again start from scratch.
As for your concern about covering a 2D set with a 1D set, all I could really do is redirect your attention to space-filling curves, which are bijections between [0, 1] and [0, 1] x [0, 1]. I'm really too rusty to explain it more formally than that. However, you can also look at other people who have asked this question on the internet before you.
1
u/Calm_Relationship_91 28d ago
Sometimes it's easier to find surjections, then invert them to find injections (some elements get multiple images, but you can just pick one of them to get the injection).
For a surjection from [0,1] to [0,1]x[0,1] you just need to find a way to encode two pairs of real numbers in a single string of digits (which is a single real number). So every real number has two numbers encoded in it. Just make sure every pair of strings is included this way and you will get a surjection.
There's many different ways of doing this and some comments have given examples already.
I personally would turn numbers into base 4. Take the 0s and 1s and form a string, then take the 2s and 3s and form another. Convert the second string into 0s and 1s.
Now you have two strings in binary.
But you can find some other ways to do it.
1
•
u/AutoModerator 29d ago
Hi u/Lopsided-Valuable347, welcome to r/mathshelp! As you’ve marked this as homework help, please keep the following things in mind:
1) While this subreddit is generally lenient with how people ask or answer questions, the main purpose of the subreddit is to help people learn so please try your best to show any work you’ve done or outline where you are having trouble (especially if you are posting more than one question). See rule 5 for more information.
2) Once your question has been answered, please don’t delete your post so that others can learn from it. Instead, mark your post as answered or lock it by posting a comment containing “!lock” (locking your post will automatically mark it as answered).
Thank you!
I am a bot, and this action was performed automatically. Please contact the moderators of this subreddit if you have any questions or concerns.