Help with a bijection proof involving sets

[EonsNearby]

Homework Statement

I was given a pdf document containing questions that require me to prove set rules. However, the third question (the one that starts at the bottom of the first page and runs into the second page) is giving me problems. I might be able to prove it if he wants a proof by example, but I do not think that is what he wants. Can someone give me some help?

Homework Equations

The Attempt at a Solution

 

[SteveL27]

Homework Statement

I was given a pdf document containing questions that require me to prove set rules. However, the third question (the one that starts at the bottom of the first page and runs into the second page) is giving me problems. I might be able to prove it if he wants a proof by example, but I do not think that is what he wants. Can someone give me some help?

Did you notice that there's a typo? When they wrote

A \cong C and B \cong C, of course they meant B \cong D. Did you get that far?

FWIW my personal opinion is that instead of posting a PDF, students should write out the question they're having trouble with. Because most of the time, just writing down a clear statement of the problem and saying clearly where you got stuck, gives you the insight to complete the problem.

So ... how far have you gotten, and where are you stuck? This is the homework section so it's reasonable for you to say what you've done so far. The problem statement gave you a pretty good hint.

 

[EonsNearby]

I figured there was a typo, but here's the thing, the question is supposed to be over the content from Chapter 1, but no where in Chapter 1 (I don't even think it is covered anywhere in the book) are bijections, or proofs involving the equality of cardinality of sets mentioned. As such, this is my first experience with them, so I wasn't sure if there was a typo or not. As for your question, I don't know where to start and I don't know how I am to use the given hint.

 

[SteveL27]

I figured there was a typo, but here's the thing, the question is supposed to be over the content from Chapter 1, but no where in Chapter 1 (I don't even think it is covered anywhere in the book) are bijections, or proofs involving the equality of cardinality of sets mentioned. As such, this is my first experience with them, so I wasn't sure if there was a typo or not. As for your question, I don't know where to start and I don't know how I am to use the given hint.

The exercise gives the definition of bijection. Can you repeat it? Do you understand what a bijection is? If not, that's the place to start. Write out the definition of bijection given in the problem; and see if you can think of some examples.

 

[EonsNearby]

I just got a message from my teacher, and he claims that there is not a typo in that question. So he meant exactly what he wrote

 

[EonsNearby]

Is it still possible to prove this even with my teacher claiming that there is not a typo in question 3?

 

[SteveL27]

I just got a message from my teacher, and he claims that there is not a typo in that question. So he meant exactly what he wrote

It's false as stated unless you replace 'C' with 'D' at the point I indicated. The counterexample is just to take D as a set with larger cardinality than B.

(edit)
For example let A be the negative integers; let B be the positive integers; let C be the rationals; and let D be the irrationals.

Then card(A) = card(B) = card(C) but card(D) is larger than the other ones.

I'm sure you and your teacher are not looking at the same line. I'm looking at the first line on page 2.

 

[EonsNearby]

Am I just going to have to talk to my teacher then?

 

[SteveL27]

Am I just going to have to talk to my teacher then?

Well, you would learn something just by making the change I suggested and doing the proof.

And then making sure you understand the counterexample to the problem that I gave, showing that the typo makes the conclusion false.

So you should do both those things first. The typo's simple, I'm sure your teacher will smack his head when he sees it. But don't let the typo stop you here till you understand the mathematical content of the discussion so far.

 

[EonsNearby]

When I e-mailed him about it, I was very specific as to what the typo would be, and he claims that he meant to write that, so I do not think it is a typo.

 

[EonsNearby]

This is the message I sent him:

Also, on question 3 where you put A≅C and B≅C , did you mean to put B≅D instead of B≅C ?

And he simply responded No.

 

[SteveL27]

This is the message I sent him:
And he simply responded No.

The conclusion is false with the counterexample I gave. Do you understand why?

Just look at the statement of the problem. D comes out of nowhere. There are no restrictions on its cardinality. If you choose D with larger cardinality than the other sets, the conclusion's obviously false.

 

[EonsNearby]

I understand what you are saying, and I understand what a bijection is. In your example, you made sure that each set had different values, so there intersection is the empty set. And while A, B, and C have the same cardinality (number of elements), then the first part of the condition is true. However, as you have stated and as I realize, nothing is really known about the cardinality of D, so even if the intersection of C and D is empty, D could be a different size than all of the rest of the sets, so the thing he wants me to prove cannot be proven.

 

[SteveL27]

I understand what you are saying, and I understand what a bijection is. In your example, you made sure that each set had different values, so there intersection is the empty set. And while A, B, and C have the same cardinality (number of elements), then the first part of the condition is true. However, as you have stated and as I realize, nothing is really known about the cardinality of D, so even if the intersection of C and D is empty, D could be a different size than all of the rest of the sets, so the thing he wants me to prove cannot be proven.

Yes. He's having a simple brain fart. He'll smack his head when he sees this. Happens to all of us. Some of us more than others :-)

But in terms of the math itself, I would be happier if you would articulate the exact reason that my counterexample works. What you said is correct, but a little too vague for me. In other words, work through the specific counterexample I suggested. And you could try making up your own counterexamples too. There are lots of them. For example you could make three of the sets finite.

Also of course you should work out the solution given the typo fix.

 

[EonsNearby]

Okay, assuming that there is a typo where you specified, would the following be an acceptable bijection for A U B → C U D:

The set A contains the even numbers less than 10 (0, 2, 4, 6, 8)

The set B contains the odd numbers less than 10 (1, 3, 5, 7, 9)

The set C contains the even numbers greater than or equal to 10 but less than 20 (10, 12, 14, 16, 18)

The set D contains the odd numbers greater than or equal to 10 but less than 20 (11, 13, 15, 17, 19)

So far, the card(A) = card(C) and the card(B) = card(D), and the intersection of A and B is the empty set and the intersection of C and D is the empty set. A U B = {(0, 1), (0, 3), (0, 5), (0, 7), (0, 9), (2, 1), (2, 3), (2, 5), (2, 7), (2, 9), (4, 1), (4, 3), (4, 5), (4, 7), (4, 9), (6, 1), (6, 3), (6, 5), (6, 7), (6, 9), (8, 1), (8, 3), (8, 5), (8, 7), (8, 9)}. C U D = {(10, 11), (10, 13), (10, 15), (10, 17), (10, 19), (12, 11), (12, 13), (12, 15), (12, 17), (12, 19), (14, 11), (14, 13), (14, 15), (14, 17), (14, 19), (16, 11), (16, 13), (16, 15), (16, 17), (16, 19), (18, 11), (18, 13), (18, 15), (18, 17), (18, 19)}. The function would be f(x, y) = (x + 10, y + 10). Thus the mapping would be the following:
(0, 1) → (10, 11)
(0, 3) → (10, 13)
(0, 5) → (10, 15)
(0, 7) → (10, 17)
(0, 9) → (10, 19)
(2, 1) → (12, 11)
(2, 3) → (12, 13)
(2, 5) → (12, 15)
(2, 7) → (12, 17)
(2, 9) → (12, 19)
(4, 1) → (14, 11)
(4, 3) → (14, 13)
(4, 5) → (14, 15)
(4, 7) → (14, 17)
(4, 9) → (14, 19)
(6, 1) → (16, 11)
(6, 3) → (16, 13)
(6, 5) → (16, 15)
(6, 7) → (16, 17)
(6, 9) → (16, 19)
(8, 1) → (18, 11)
(8, 3) → (18, 13)
(8, 5) → (18, 15)
(8, 7) → (18, 17)
(8, 9) → (18, 19)

It is one-to-one because each element of A U B is mapped to, at most, one element of C U D. It is onto because the range includes every value of C U D.

Would this be an acceptable bijection?

 

[SteveL27]

Would this be an acceptable bijection?

You haven't proved anything. You haven't given a counterexample to the problem as stated; and you haven't proven the conclusion given the typo fix.

First state exactly what you're trying to prove. Remember we now have two separate problems.

1) Make the typo fix and supply the proof requested in the problem. You are required to show that this is true for all possible assignments of sets to A, B, C, and D. What you did is show one example where it works. But how do you know it always works?

Example. Suppose I asked you to prove that all even numbers are divisible by 2. You can't just say, well, 14 is divisible by 2. You have to prove that ALL even numbers are divisible by 2. You're being asked to prove something for all possible interpretations of A, B, C, and D.

2) Without the typo fix, find a counterexample that disproves the conclusion.

Secondly, it's rarely practical to show a bijection by listing every element. It would be better to find a rule or formula, rather than listing all the elements.

 

[EonsNearby]

My example was just to make sure I understood something about bijections. Regarding 1), the only real things I know is that both A U B and C U D have the same cardinality. The problem states, assuming the typo is fixed, that the card(A) = card(C), so let's assume that the card(A) = card(C) = n. Similar idea with card(B) = card(D) = m. Whenever to sets are union-ed together, the total number of elements in the new set is equal to the product of the cardinality of both sets. So in this case, card(A U B) = n * m, and the card (C U D) = n * m. So I know that A U B and C U D are going to have the same cardinality. Also, the problem specifies that the sets that are to be union-ed do not have the same elements. So the only real conclusions I can draw is that A U B and C U D have the same cardinality and both have different elements. I don't know what to do from here though.

 

[SteveL27]

My example was just to make sure I understood something about bijections. Regarding 1), the only real things I know is that both A U B and C U D have the same cardinality.

Isn't that what they're asking you to prove?

The problem states, assuming the typo is fixed, that the card(A) = card(C), so let's assume that the card(A) = card(C) = n. Similar idea with card(B) = card(D) = m.

What if the sets are infinite? Are n and m supposed to be integers? Then how will you handle an infinite set? You are being asked to think about bijections, not about specific cardinal numbers.

Whenever to sets are union-ed together, the total number of elements in the new set is equal to the product of the cardinality of both sets.

No, that's false.

Do you understand what a union is?

If A = {1,2,3} and B = {4,5,6} then what is the cardinality of A union B?

If A = {1,2,3} and B = {1,2,5} then what is the cardinality of A union B?

Do you understand that the empty intersection condition is essential?

So in this case, card(A U B) = n * m, and the card (C U D) = n * m.

As indicated, that's not right. Where'd you get that idea? Do you know what a union is? Have you tried some examples?

So I know that A U B and C U D are going to have the same cardinality. Also, the problem specifies that the sets that are to be union-ed do not have the same elements. So the only real conclusions I can draw is that A U B and C U D have the same cardinality and both have different elements. I don't know what to do from here though.

1) Figure out what a union is.

2) Use bijections -- not specific cardinal numbers -- to do the proof, just as the problem suggests.

Can you think of how to construct a bijection from A union B to C union D?

 

[EonsNearby]

Wait........so I solved the problem, assuming the typo is fixed?

 

[SteveL27]

Wait........so I solved the problem, assuming the typo is fixed?

Not if I'm the grader.

Did you read my previous post? You don't seem to understand what a union is and you don't understand how to construct a bijection out of the information you've been given. And you also don't understand that you need to use a bijection to solve this problem. And you don't understand that you need to prove the conclusion for all possible assignments of sets to A, B, C, and D; and that it's insufficient to simply demonstrate one such assignment that happens to work.

Not piling on criticisms here ... just pointing out the "elements of understanding" that a grader is going to be looking for in this problem.

 

[EonsNearby]

I read and replied to your post before you edited it.

 

[meldraft]

Just a small interjection, question (1)(ii) also has a mistake, the left hand side of the equation should beA\bigcup(B\bigcap C).

 

[EonsNearby]

I know, he acknowledged that one.

 

[EonsNearby]

I think I got Union and Cartesian Product mixed up

 

[SteveL27]

I think I got Union and Cartesian Product mixed up

Yes, that's ok.

But you still haven't given a proof. Even if you used an n+m proof, you'd still not be getting the point of the problem, which is to use a bijection; which will make your proof valid for all sets, not just finite ones.

So if you need to construct a bijection between A union B and C union D, how would you do that?

Hint: Draw a picture. Put arrows between things you know already have bijections between them.

 

[EonsNearby]

I have to do something else for the time being, so I can't resume doing this till tomorrow. Thanks for the help anyways.

 

[SteveL27]

I have to do something else for the time being, so I can't resume doing this till tomorrow. Thanks for the help anyways.

Likewise. Glad to help. To be fair, I think this is a bit of a sophisticated problem for someone brand new to bijections. You're being asked in essence to show that the bijection between two unions is the union of the bijections.

I note that this is an upper division / graduate course; so I believe you are being asked to spend some time thinking about what all the terms mean and how to get this problem organized. It's not intended to be easy if you just learned what a bijection is for the first time.

 

[EonsNearby]

Hint: Draw a picture. Put arrows between things you know already have bijections between them.

What do you mean draw arrows between things that already have bijections between them?

 

[SteveL27]

What do you mean draw arrows between things that already have bijections between them?

Unfortunately the forum software collapses spaces, so I can't draw this in ASCII.

But if you write

A ------------- B

C ------------- D

in a square, then you know that A and C are bijectively equivalent; and so are B and D. This will be helpful when you try to construct a bijection between A union B and C union D. Some people like visual representations. Just a thought. My horizontal lines are just for spacing, pretend they're not there. But put A union B to the right of the A/B line, and C union D to the right of the C/D line. You already have bijections between A and C and B and D, respectively. Wouldn't even hurt to label them f and g. Then you'll have some notation to help you construct the bijection needed to solve the problem. This approach isn't mandatory, it's just one way to look at it.

It's something like this:

A ------------- B ===> A union B
| ------------- |
| ------------- |
f --------------g
| ------------- |
| ------------- |
C ------------- D ===> C union D

where all the horizontal lines ---- can be ignored, they're just there to fool the forum software into giving me the spacing I want. Just a visual aid if it helps; ignore it if not.

So I am really curious. What did your teacher say about the typo?

 

[EonsNearby]

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.

 

[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?