1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Help with a bijection proof involving sets

  1. May 19, 2012 #1
    1. The problem statement, all variables and given/known data
    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?

    2. Relevant equations

    3. The attempt at a solution

    Attached Files:

  2. jcsd
  3. May 19, 2012 #2
    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.
  4. May 19, 2012 #3
    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.
  5. May 19, 2012 #4
    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.
  6. May 19, 2012 #5
    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
  7. May 19, 2012 #6
    Is it still possible to prove this even with my teacher claiming that there is not a typo in question 3?
  8. May 19, 2012 #7
    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.

    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.
    Last edited: May 19, 2012
  9. May 19, 2012 #8
    Am I just going to have to talk to my teacher then?
  10. May 19, 2012 #9
    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.
  11. May 19, 2012 #10
    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.
  12. May 19, 2012 #11
    This is the message I sent him:

    And he simply responded No.
  13. May 19, 2012 #12
    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.
    Last edited: May 19, 2012
  14. May 19, 2012 #13
    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.
  15. May 19, 2012 #14
    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.
  16. May 19, 2012 #15
    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?
  17. May 19, 2012 #16
    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.
    Last edited: May 19, 2012
  18. May 19, 2012 #17
    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 lets 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.
  19. May 19, 2012 #18
    Isn't that what they're asking you to prove?

    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.

    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?

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

    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?
    Last edited: May 19, 2012
  20. May 19, 2012 #19
    Wait..............................so I solved the problem, assuming the typo is fixed?
  21. May 19, 2012 #20
    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.
    Last edited: May 19, 2012
  22. May 19, 2012 #21
    I read and replied to your post before you edited it.
  23. May 19, 2012 #22
    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].
  24. May 19, 2012 #23
    I know, he acknowledged that one.
  25. May 19, 2012 #24
    I think I got Union and Cartesian Product mixed up
  26. May 19, 2012 #25
    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.
    Last edited: May 19, 2012
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook