Help with a bijection proof involving sets

[SteveL27]

He just simply said no. This is an online course, so I had to e-mail him about it. I am going to see him Wednesday and point it out to him. However, I get the feeling he is going to be a blockhead unless I show him a counterexample, like you suggested.

Well because he's so certain, I have a nagging possibility in the back of my mind that I'm the one going nuts here. That is always a possibility. And nobody else has jumped into this thread, so we're on our own here :-)

Anyway, wouldn't hurt to write out in specific detail a counterexample to the problem as written. And then write out a complete proof to the fixed problem.

 

[EonsNearby]

So when the problem said that A and C have the same cardinality, that was a subtle way of saying that there is a bijection that maps A -> C (and a similar idea for B -> D, again assuming there is a typo), correct? If so, are you suggesting that I take those two already existing bijections (lets just call them f and g) and use those to construct the bijection I need to construct?

 

[SteveL27]

So when the problem said that A and C have the same cardinality, that was a subtle way of saying that there is a bijection that maps A -> C (and a similar idea for B -> D, again assuming there is a typo), correct?

Yes, but actually it wasn't subtle. Those two concepts are equivalent. If there's a bijection, the sets are cardinally equivalent and vice versa. And that's because by definition two sets have the same cardinality if there is a bijection between them.

I think your teacher's presentation is subtle, in the sense that there are a lot of concepts being thrown at you in one or two sentences. If you haven't seen this material before, it's perfectly ok that it takes some time to sink in.

If so, are you suggesting that I take those two already existing bijections (lets just call them f and g) and use those to construct the bijection I need to construct?

That's what I would do.

So, we need a bijection between A \bigcup B and C \bigcup D.

What is a bijection? A bijection is three things:

* It's a function between two sets.
* It's onto (also called a surjection)
* It's 1-1 (also called an injection).

So we need to come up with a function between these two sets. To define a function, we have to say what happens to a given element. So if we have an element x \in A \bigcup B, what element of C \bigcup D should we map it to?

And a hint is that since we need a bijection, we are going to have to use 1-1 and onto at some point.

 

[EonsNearby]

I'm just typing this while its fresh, so please excuse it if I'm still not getting it. Okay, there are 2 bijections that exist, f and g. We want to get a new bijection, let's just dub it h, that utilizes both f and g. So if we get an element x from A U B, is it possible to use both f and g on x and then use the results from those two bijections to figure out what the element y from C U D that x should be matched to (just a crude interpretation of what I am saying h(x) = f(x) + g(x) [I'm just using '+' to indicate some action that combines the results of f(x) and g(x)]?

 

[SteveL27]

I'm just typing this while its fresh, so please excuse it if I'm still not getting it. Okay, there are 2 bijections that exist, f and g. We want to get a new bijection, let's just dub it h, that utilizes both f and g. So if we get an element x from A U B, is it possible to use both f and g on x and then use the results from those two bijections to figure out what the element y from C U D that x should be matched to (just a crude interpretation of what I am saying h(x) = f(x) + g(x) [I'm just using '+' to indicate some action that combines the results of f(x) and g(x)]?

Trying to combine f and g is not the approach that will work here.

Start by working this out for finite sets.

Let A = {1,2,3}, B = {4,5,6,7,8}, C = {9,10,11}, D = {12,13,14,15,16}

Verify that the conditions of the problem are satisfied. Demonstrate specific bijections f and g. Then look at A union B and C union D, and see if you can use f and g to construct the bijection you need.

Once you do that in detail, you'll see how to do this for arbitrary sets.

 

[EonsNearby]

Okay, well since these are countably finite sets, I can verify that A and C have a cardinality of 3 and that B and D have a cardinality of 5. Since A and B do not have any elements that match, the intersection of these two sets is the empty set (the same goes for C and D). Anyway, a bijection for A -> C would be the f(x) = x + 8 where x is an element from A. This is one-to-one because every element in A will be matched to a unique element in C. This is also onto because the range of f is every element in C. To visually demonstrate:
Set A++++++Set C
1 -----------> 9
2 -----------> 10
3 -----------> 11

A bijection for B -> D would be g(x) = x + 8 where x is an element from B. This is one-to-one because every element in B will be matched to a unique element in D. This is also onto because the range of g is every element in D. To visually demonstrate:
Set B+++++++Set D
4 -----------> 12
5 -----------> 13
6 -----------> 14
7 -----------> 15
8 -----------> 16

Am I correct so far?

 

[EonsNearby]

I know this doesn't fully answer the question, but I just want to make sure my "basis" is correct so I don't try to fully answer the question when I didn't even get the "basis" right.

 

[gopher_p]

Well because he's so certain, I have a nagging possibility in the back of my mind that I'm the one going nuts here. That is always a possibility. And nobody else has jumped into this thread, so we're on our own here :-)

You're not crazy. The statement is incorrect. A simple counterexample is $A=\{a\}$, $B=\{b\}$, $C=\{c\}$, $D=\{d_1,d_2\}$.

 

[EonsNearby]

You're not crazy. The statement is incorrect. A simple counterexample is A={a}, B={b}, C={c}, D={d1,d2}.

So if I simply show this to him and explain that this does abide by the specifications the problem sets up, the thing he wants me to prove cannot be proven?

 

[gopher_p]

So if I simply show this to him and explain that this does abide by the specifications the problem sets up, the thing he wants me to prove cannot be proven?

Yes. Though you should note that there is a BIG difference between "cannot be proven" and "can be (has been) proven to be false".

 

[EonsNearby]

Okay, I will make a note of that.

 

[SteveL27]

Okay, well since these are countably finite sets, I can verify that A and C have a cardinality of 3 and that B and D have a cardinality of 5.

No. I didn't read any farther in this thread so forgive me if I missed anything.

I do not know what 3 is. We are operating at a more primitive level.

I want you to convince me that {1,2,3} and {9,10,11} have the same cardinality without referring to the number 3 or any other number. Because I do not know what the number 3 means. The only thing I know is the definition of a bijection; and the fact that two sets have the same cardinality if there's a bijection between them.

So show me that those two sets have the same cardinality. In detail, from first principles. Define what it means for two sets to have the same cardinality; and show that definition applies to the sets in question.

By the way ... is this by any chance your first exposure to proof-oriented math?

 

[SteveL27]

So if I simply show this to him and explain that this does abide by the specifications the problem sets up, the thing he wants me to prove cannot be proven?

You have to show him a clear and detailed counterexample; AND you have to solve the problem after making the fix.

Remember, teachers are people too. When they make mistakes, your job is to correct the mistake and still solve the problem.

In fact at some point in math classes they stop saying "Prove such and so," and they start saying "Prove or DISprove!" So you don't know ahead of time whether you're looking for a proof or a counterexample.

 

[EonsNearby]

Then doesn't the rest of my post answer the question?

Since A and B do not have any elements that match, the intersection of these two sets is the empty set (the same goes for C and D). Anyway, a bijection for A -> C would be the f(x) = x + 8 where x is an element from A. This is one-to-one because every element in A will be matched to a unique element in C. This is also onto because the range of f is every element in C. To visually demonstrate:
Set A++++++Set C
1 -----------> 9
2 -----------> 10
3 -----------> 11

A bijection for B -> D would be g(x) = x + 8 where x is an element from B. This is one-to-one because every element in B will be matched to a unique element in D. This is also onto because the range of g is every element in D. To visually demonstrate:
Set B+++++++Set D
4 -----------> 12
5 -----------> 13
6 -----------> 14
7 -----------> 15
8 -----------> 16

Am I correct so far?

 

[SteveL27]

Then doesn't the rest of my post answer the question?

Yes, all that's good. Excellent in fact. So we now have specific bijections between A and C, and between B and D, respectively. That's good. We'll use them. But also in the back of your mind, it will be helpful to realize that we don't actually care what the bijections are; only that they exist.

 

[EonsNearby]

Okay, so A U B = {1, 2, 3, 4, 5, 6, 7, 8} and C U D = {9, 10, 11, 12, 13, 14, 15, 16}. Now I have to somehow use f and g to construct a new bijection, h, for A U B -> C U D that shows that A U B and C U D have the same cardinality.

First attempt: h(x) = x + 8 where x is an element from A U B. This is one-to-one because every element of A U B is mapped to a unique element from C U D. This is also onto because the range of h is every element in C U D. To visually demonstrate:
Set A U B+++++++++++Set C U
1 ---------------------> 9
2 ---------------------> 10
3 ---------------------> 11
4 ---------------------> 12
5 ---------------------> 13
6 ---------------------> 14
7 ---------------------> 15
8 ---------------------> 16

Is this the bijection I'm looking for, even though h is almost the exact same function as f and g?

 

[SteveL27]

Okay, so A U B = {1, 2, 3, 4, 5, 6, 7, 8} and C U D = {9, 10, 11, 12, 13, 14, 15, 16}. Now I have to somehow use f and g to construct a new bijection, h, for A U B -> C U D that shows that A U B and C U D have the same cardinality.

First attempt: h(x) = x + 8 where x is an element from A U B. This is one-to-one because every element of A U B is mapped to a unique element from C U D. This is also onto because the range of h is every element in C U D. To visually demonstrate:
Set A U B+++++++++++Set C U
1 ---------------------> 9
2 ---------------------> 10
3 ---------------------> 11
4 ---------------------> 12
5 ---------------------> 13
6 ---------------------> 14
7 ---------------------> 15
8 ---------------------> 16

Is this the bijection I'm looking for, even though h is almost the exact same function as f and g?

Oh heck I gave you a bad example because the same formula happens to work for each function. That doesn't generalize.

Let D = {a,b,c,d,e} and redo your function g. The formula is totally irrelevant here. What's important is that there's a bijection. You're not looking for a formula. You're looking for a correspondence.

ps Do you understand why I made that change? In general, f and g will have nothing to do with each other; and all the sets might be completely different. The only thing we care about is the cardinalities. We are not concerned with any particular numeric relationship among the elements. Because we're trying to be as general as possible.

 

[EonsNearby]

That is one area where I am confused. If I am just looking for a correspondence, could a bijection for B -> D just look like g(x) = a if x is 4, b if x is 5, c if x is 6, d if x is 7, e if x is 8? This is one-to-one because every element in B will be matched to a unique element in D. This is also onto because the range of g is every element in D. To visually demonstrate:
Set B+++++++Set D
4 -----------> a
5 -----------> b
6 -----------> c
7 -----------> d
8 -----------> e

Or would I actually have to come up with a formula that logically maps the elements of B to the elements of D?

 

[SteveL27]

That is one area where I am confused. If I am just looking for a correspondence, could a bijection for B -> D just look like g(x) = a if x is 4, b if x is 5, c if x is 6, d if x is 7, e if x is 8? This is one-to-one because every element in B will be matched to a unique element in D. This is also onto because the range of g is every element in D. To visually demonstrate:
Set B+++++++Set D
4 -----------> a
5 -----------> b
6 -----------> c
7 -----------> d
8 -----------> e

Yes!

Or would I actually have to come up with a formula that logically maps the elements of B to the elements of D?

No! Because in general our sets might not be numbers. There might be no formula. But there still might be a bijection.

What we're doing is abstracting the concept of "how many" to the more general concept of cardinality.

Two sets are cardinally equivalent if there's a bijection between them; whether or not there's any formula that describes the bijection. If you map {horse, cow} to {chicken, dog} there is no formula for a bijection, but clearly there are a couple of bijections.

Now that you have f and g, see if you can map an arbitrary element x \in A \bigcup B to some element in C \bigcup D in such a way that your mapping is a bijection.

They don't want you to look for formulas; but to just use the fact that f and g are bijections.

 

[EonsNearby]

Okay...I hate abstracting but I will try my best...again.

So A U B = {1, 2, 3, 4, 5, 6, 7, 8} and C U D = {9, 10, 11, a, b, c, d, e}.

First attempt: h(x) = f(x) if x is element 1, 2, 3 OR g(x) if x is element 4, 5, 6, 7, 8. This is one-to-one because every element of A U B is mapped to a unique element from C U D. This is also onto because the range of h is every element in C U D. To visually demonstrate:
Set A U B+++++++++++Set C U
1 ---------------------> 9
2 ---------------------> 10
3 ---------------------> 11
4 ---------------------> 12
5 ---------------------> 13
6 ---------------------> 14
7 ---------------------> 15
8 ---------------------> 16

(Just a quick question, could I have instead said h(x) = f(x) if x is an element that is from A OR g(x) if x is an element from B?)

Is this a possible bijection?

 

[SteveL27]

Okay...I hate abstracting

Gonna be a long semester in this class then :-) That's what this exercise is about. Learning to write abstract proofs.

Question: Is this your first proof-based class? And if so, is that normal for this class? Or are you expected to already know how to do abstract proofs? If the latter, you will have to work extra hard for a while till you get the hang of this. Something to talk about when you meet w/the teacher.

So A U B = {1, 2, 3, 4, 5, 6, 7, 8} and C U D = {9, 10, 11, a, b, c, d, e}.

First attempt: h(x) = f(x) if x is element 1, 2, 3 OR g(x) if x is element 4, 5, 6, 7, 8.

Why does x have to be in one or the other? Answer: Because the elements of A union B are exactly those elements that are either in A or in B.

But what if x is in both A and B? Answer: That can't be, because A intersect B is empty. That's a given.

Those are the types of things I'm looking for if I'm grading this proof. I'm looking for understanding; and I'm looking to see if you are using the givens.

This is one-to-one because every element of A U B is mapped to a unique element from C U D.

Why?

This is also onto because the range of h is every element in C U D.

How do you know? How do you know everything in C union D gets hit? It is essential to say WHY something is true based on the givens and what you're allowed to assume. Of course we HOPE your mapping is onto; but you have to say WHY it's onto. What if I say, "Hey, I don't think your mapping is onto." What is the answer?

(Just a quick question, could I have instead said h(x) = f(x) if x is an element that is from A OR g(x) if x is an element from B?)

Is this a possible bijection?

Yes; of course, that's the bijection. And you can see that it's very general. We didn't assume the sets are finite; we didn't assume there are any formulas.

But, once you say that, you have to prove that it's well-defined. What if x is in both A and B, then how should I defined h(x)?

Once you handle that issue, then show that h is 1-1 and onto. But you have to nail down every little detail.

That is what they're looking for in a proof like this. Everything you claim is true or hope is true must be shown logically to be true.

 

[sponsoredwalk]

Okay...I hate abstracting but I will try my best...again.

So A U B = {1, 2, 3, 4, 5, 6, 7, 8} and C U D = {9, 10, 11, a, b, c, d, e}.

First attempt: h(x) = f(x) if x is element 1, 2, 3 OR g(x) if x is element 4, 5, 6, 7, 8. This is one-to-one because every element of A U B is mapped to a unique element from C U D. This is also onto because the range of h is every element in C U D. To visually demonstrate:
Set A U B+++++++++++Set C U
1 ---------------------> 9
2 ---------------------> 10
3 ---------------------> 11
4 ---------------------> 12
5 ---------------------> 13
6 ---------------------> 14
7 ---------------------> 15
8 ---------------------> 16

(Just a quick question, could I have instead said h(x) = f(x) if x is an element that is from A OR g(x) if x is an element from B?)

Is this a possible bijection?

Yeah, but you're already abstracting by saying x is an element of A & notice you're abstracting the situation now that you fully understand it. Can you abstract this situation even further so that it applies between countable sets where you couldn't possibly give any nice & neat formula like x + 8? Hopefully you'll see that abstracting in this situation isn't any different from what you've done so far, I'd say most of the time it's like this once you understand.

 

[EonsNearby]

Then I think I get it. The only possible elements that x can be is an element from A or B (as you stated in these two lines:

Why does x have to be in one or the other? Answer: Because the elements of A union B are exactly those elements that are either in A or in B.

But what if x is in both A and B? Answer: That can't be, because A intersect B is empty. That's a given.

Since that is the case, then no element that is not from the domain of A U B -> C U D can be used for x. Now, the method that h uses to map the element of A U B to an element of C U D is entirely dependent on what the element x is, since h basically chooses to use f if the element is from A or g if the element is from B. Since h uses f and g, which were both previously established bijections, and since x can only be an element from the domain of A U B, do these GIVENs prove that h is one-to-one? Also, since f and g can only result in an element from C or D respectively, can these GIVENs prove that h is onto?

Is this enough to show that h is a bijection, and thus show that A U B has the same cardinality of C U D because there is a bijection for A U B -> C U D?

 

[SteveL27]

Then I think I get it. The only possible elements that x can be is an element from A or B (as you stated in these two lines:

x must be in A or B by definition of union.

Since that is the case, then no element that is not from the domain of A U B -> C U D can be used for x.

True but very confusing to write it that way. We are defining a function whose domain is A union B. So we consider elements x in that union. You don't have to say any more about it.

Now, the method that h uses to map the element of A U B to an element of C U D is entirely dependent on what the element x is, since h basically chooses to use f if the element is from A or g if the element is from B.

How do you know such a choice can be made? What if x is in both A and B? What if f maps x to more than one thing? These things can't happen, but WHY?

Since h uses f and g, which were both previously established bijections, and since x can only be an element from the domain of A U B, do these GIVENs prove that h is one-to-one?

Do you know the definition of 1-1? In order to prove h is 1-1 you have to state the definition of 1-1 and then prove it applies to h. You haven't done that.

Also, since f and g can only result in an element from C or D respectively, can these GIVENs prove that h is onto?

Do you know the definition of onto? In order to prove h is onto you have to state the definition and then prove it applies to h. You haven't done that.

You have CLAIMED that h is 1-1 and onto but you have not proved those two assertions. You haven't even convinced me (in my role as picky grader) that you know what the terms mean. For example so what if f and g only hit element in C and D respectively? That does not establish that h is onto.

Is this enough to show that h is a bijection, and thus show that A U B has the same cardinality of C U D because there is a bijection for A U B -> C U D?

If you show three things:

* h is a function;
* h is 1-1;
* h is onto

then you've established the conclusion.

Although you've stated those three things, you have not proved them.

You have to carefully define h (you've done so correctly already) and then show that it makes sense to define it that way, and that the result is a function.

Then you have to show h is 1-1 and then you have to show h is onto.

 

[EonsNearby]

I am going to have to continue this tomorrow. Thanks for the help.

 

[EonsNearby]

Okay, then here is another attempt at answering the question from the assignment (assuming the typo is fixed).

What is given:
A and C have the same cardinality, so there must be a bijection for A -> C, which I will call f. B and D have the same cardinality, so there must be a bijection for B -> D, which I will call g. Sets A and B do not contain any elements that are the same because they are disjoint (the intersection of A and B is the empty set). Sets C and D do not contain any elements that are the same because they are also disjoint.

My attempt to prove that A U B has the same cardinality of C U D:
A U B and C U D have the same cardinality if there is a bijection that maps A U B -> C U D. Assume there is a function h that maps A U B -> C U D. The function looks like h(x) = f(x) if the element x is from A OR g(x) if the element x is from B. In order for h to be a bijection, it needs to be one-to-one and onto. For a function to be one-to-one, every element from the domain (in this case A U B) must be mapped to at most one element from the range (in this case C U D). For a function to be onto, the range must consist of every element in C U D (meaning that every element in C U D must have some other element mapped to it).
i) Proof that h is one-to-one: By the definition of union, x must be an element from A or B. Since it was given that A and B are disjoint, x can not be an element from A and B. Function h is equal to the result of the bijection f or the bijection g, and since I have proven that x can only be an element from A or B, every element in the domain will be mapped to every element in the range.
ii) Proof that h is onto: By the definition of a bijection, f will match every element in A to at most one element of C, and each element of C will have at most one element of A mapped to it (the same can be said with the bijection g for the sets B and D). The function h is equal to the result of bijection f or bijection g, and since I have proven that x can only be an element from A or B but not from both (and because sets C and D are disjoint, the result of h can not be an element from C and D), then every element in C U D will have at most one element from A U B mapped to it.

Is this sufficient enough (or at least close)?

 

[SteveL27]

Okay, then here is another attempt at answering the question from the assignment (assuming the typo is fixed).

What is given:
A and C have the same cardinality, so there must be a bijection for A -> C, which I will call f. B and D have the same cardinality, so there must be a bijection for B -> D, which I will call g. Sets A and B do not contain any elements that are the same because they are disjoint (the intersection of A and B is the empty set). Sets C and D do not contain any elements that are the same because they are also disjoint.

So far so good. I'd say that A and B have no elements in common because they're disjoint.

My attempt to prove that A U B has the same cardinality of C U D:
A U B and C U D have the same cardinality if there is a bijection that maps A U B -> C U D. Assume there is a function h that maps A U B -> C U D.

You can't assume that, because that's what you're trying to prove. What you mean is, "Let us define a function h ..."

The function looks like h(x) = f(x) if the element x is from A OR g(x) if the element x is from B.

Now: "This is well-defined because those two possibilities are mutually exclusive. Either x is in A or x is in B, but not both; because A and B are disjoint."

In order for h to be a bijection, it needs to be one-to-one and onto. For a function to be one-to-one, every element from the domain (in this case A U B) must be mapped to at most one element from the range (in this case C U D). For a function to be onto, the range must consist of every element in C U D (meaning that every element in C U D must have some other element mapped to it).

Good, stating what you need to prove. However, your definition of 1-1 is wrong. The property that each element of the domain gets mapped to at most one element of the range is the definingy propert of a function. Review the definition of 1-1.

i) Proof that h is one-to-one: By the definition of union, x must be an element from A or B. Since it was given that A and B are disjoint, x can not be an element from A and B.
Function h is equal to the result of the bijection f or the bijection g, and since I have proven that x can only be an element from A or B, every element in the domain will be mapped to every element in the range.

No, that's not right. Every element in the domain gets mapped to every element in the range? That can't be. h is a function, so every element in the domain must get mapped to at most one element of the range. Right? That's the definition of a function.

You need to review the definition of 1-1. A function h is 1-1 if

x \neq y \Rightarrow h(x) \neq h(y).

That's the textbook definition and that's what you need to prove.

ii) Proof that h is onto: By the definition of a bijection, f will match every element in A to at most one element of C,

No, that's the definition of a function.

and each element of C will have at most one element of A mapped to it (the same can be said with the bijection g for the sets B and D).

Yes. That's equivalent to the definition of 1-1. But you are still unclear about the definition of onto. Actually you stated the right definition earlier, but stated the wrong definition just now.

The function h is equal to the result of bijection f or bijection g, and since I have proven that x can only be an element from A or B but not from both (and because sets C and D are disjoint, the result of h can not be an element from C and D), then every element in C U D will have at most one element from A U B mapped to it.

Is this sufficient enough (or at least close)?

Much better, but your 1-1 and onto proofs need to be redone.

You should review the definition of function, 1-1, and onto; and clearly prove each of those three things.

Getting there!

I won't be around till later on but the proof is making progress.

 

[EonsNearby]

What is given:
A and C have the same cardinality, so there must be a bijection for A -> C, which I will call f. B and D have the same cardinality, so there must be a bijection for B -> D, which I will call g. Sets A and B have no elements in common because they are disjoint (the intersection of A and B is the empty set). Sets C and D have no elements in common because they are also disjoint.

My attempt to prove that A U B has the same cardinality of C U D:
A U B and C U D have the same cardinality if there is a bijection that maps A U B -> C U D. Let's us define a function h that maps A U B -> C U D. The function looks like h(x) = f(x) if the element x is from A OR g(x) if the element x is from B. In order for h to be a bijection, it needs to be one-to-one and onto. For a function to be one-to-one, then if an element from x and another element y from the domain (A U B) are not equal, then that must imply that h(x) is not equal to h(y). In order for a function to be onto, then for every element y in the range (C U D) there must be an element x in the domain (A U B) such that h(x) = y.

i) Proof that h is a function: The result of h is the result of bijection f or bijection g. Since f and g proven to be one-to-one and onto, f and g will result in a matching of an element from A U B to an element from C U B.

ii) Proof that h is one-to-one: Because of the definition of union, x has to be an element from A or B. Because A and B are disjoint, x cannot be an element from A and B. Since the result of h is the result of bijection f or bijection g, and since the input to x has to be an element from A or B but not both, two different elements from A U B will not be mapped to the same element in C U D by the definition of a bijection.

iii) Proof that h is onto: f and g are already established bijections for A -> C and B -> D respectively. The result of h is the result of f or g, depending on what set x came from. Since it has already been proven that x has to come from A or B but not both, then h will be equal to a valid computation of f or g (basically, h(x) = f(x) OR g(x)). Since C and D are being unioned together, and since they are disjoint, and since h is equal to the result of the established bijections for C and D respectively, every element in C U D will have an element from A U B mapped to it. So h is onto

Since h is a function that is one-to-one and onto, it is a bijection. Since there is a bijection for A U B -> C UD, then A U B has the same cardinality of B U D.

 

[SteveL27]

What is given:
A and C have the same cardinality, so there must be a bijection for A -> C, which I will call f. B and D have the same cardinality, so there must be a bijection for B -> D, which I will call g. Sets A and B have no elements in common because they are disjoint (the intersection of A and B is the empty set). Sets C and D have no elements in common because they are also disjoint.

My attempt to prove that A U B has the same cardinality of C U D:
A U B and C U D have the same cardinality if there is a bijection that maps A U B -> C U D. Let's us define a function h that maps A U B -> C U D. The function looks like h(x) = f(x) if the element x is from A OR g(x) if the element x is from B. In order for h to be a bijection, it needs to be one-to-one and onto. For a function to be one-to-one, then if an element from x and another element y from the domain (A U B) are not equal, then that must imply that h(x) is not equal to h(y). In order for a function to be onto, then for every element y in the range (C U D) there must be an element x in the domain (A U B) such that h(x) = y.

i) Proof that h is a function: The result of h is the result of bijection f or bijection g. Since f and g proven to be one-to-one and onto, f and g will result in a matching of an element from A U B to an element from C U B.

You've got all the essential facts but your presentation's confusing. Right here you made a statement but you didn't prove it. The proof's buried in your first paragraph way above but it's not connected to the proof of this statement.

The point is that we define

h:A \bigcup B \rightarrow C \bigcup D by

h(x) = f(x) if x \in A and

h(x) = g(x) if x \in B.

We know x must either be in A or B because x is in their union; and we know x can't be in BOTH because A and B are disjoint. So our definition of h is not ambiguous; h is a well-defined function.

You can just say it that way and delete all the extra verbiage.

ii) Proof that h is one-to-one: Because of the definition of union, x has to be an element from A or B. Because A and B are disjoint, x cannot be an element from A and B. Since the result of h is the result of bijection f or bijection g, and since the input to x has to be an element from A or B but not both, two different elements from A U B will not be mapped to the same element in C U D by the definition of a bijection.

Let's see if we can say this symbolically and not in so many words.

To prove h is 1-1 we have to show that if x \neq y then h(x) \neq h(y).

So, suppose we have x and y in A union B with x \neq y.

If x and y are both in A, then h(x) and h(y) are different because h(x) = f(x), and h(y) = f(y), and now f(x) is not equal to f(y) because f is 1-1.

Similarly if x and y are both in B, then h(x) is different than h(y) because g is 1-1.

But if x is in A and y is in B, then h(x) can not be the same as h(y) because then both h(x) and h(y) would have to be in C intersect D. Why is that? Well, h(x) = f(x) is in C; and h(y) = g(y) is in D. So if h(x) = h(y) then they must be in C intersect D.

But that can't be, because C intersect D is empty!

You see that last part? We used the given that C intersect D is empty. You always know you're on the right track when you use your givens. And if you get to the end of your proof and you haven't used one of the givens, there's probably something wrong with your proof.

iii) Proof that h is onto: f and g are already established bijections for A -> C and B -> D respectively. The result of h is the result of f or g, depending on what set x came from. Since it has already been proven that x has to come from A or B but not both, then h will be equal to a valid computation of f or g (basically, h(x) = f(x) OR g(x)). Since C and D are being unioned together, and since they are disjoint, and since h is equal to the result of the established bijections for C and D respectively, every element in C U D will have an element from A U B mapped to it. So h is onto

Since h is a function that is one-to-one and onto, it is a bijection. Since there is a bijection for A U B -> C UD, then A U B has the same cardinality of B U D.

What the heck is a "valid computation?" You are still thinking of functions as formulas. They are not. Try to rephrase this in symbols and not words. It's difficult to follow your logical argument here.

I think you probably have enough at this point so that a charitable grader will give you most of the points on this. Going forward you need to learn to work in symbols and write clear proofs. That will come with practice.

Try to redo the onto part. Assume y is an element of C union D. Show me symbolically that there must be some x with h(x) = y.

 

[EonsNearby]

Are you just using the symbols in the Quick Symbols box when you reply to a message? If not, then how are you getting the symbols?