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

[itex]A \cong C[/itex] and [itex]B \cong C[/itex], of course they meant [itex]B \cong D[/itex]. 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 be[itex]A\bigcup(B\bigcap C)[/itex].

 

[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 [itex]A \bigcup B[/itex] and [itex]C \bigcup D[/itex].

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 [itex]x \in A \bigcup B[/itex], what element of [itex]C \bigcup D[/itex] 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.