Help with a bijection proof involving sets

[SteveL27]

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?

I'm learning LaTeX as I go. Actually I've been lazy and written "A union B" too many times when I should go

A \bigcup B

I'm a little confused by your question ... haven't you been using LaTeX all along?

 

[EonsNearby]

No, that's is the first I've ever heard of LaTex. When we submit our homework to him, we have the option of typing up our answers in a document and submitting that to him, or by doing the work on notebook paper, scanning it, and then e-mailing him the scans. I've been doing the homework on paper since I figured typing up proofs in words would have been very confusing.

 

[EonsNearby]

I'm basically asking how you were able to input symbols like ∈ into your responses (I just copied that from your previous post btw). If I had known how to put symbols like that (and others) into my responses, I would have done so instead of trying to explain everything using words and very few symbols (like "A U B", which is just the capital letters 'A', 'B', and 'U').

 

[SteveL27]

I'm basically asking how you were able to input symbols like ∈ into your responses (I just copied that from your previous post btw). If I had known how to put symbols like that (and others) into my responses, I would have done so instead of trying to explain everything using words and very few symbols (like "A U B", which is just the capital letters 'A', 'B', and 'U').

Physicsforums has a good writeup.

https://www.physicsforums.com/showthread.php?t=546968

If you need some particular piece of markup you can google "latex arrows" or "latex element of" or whatever, and it will usually bring up a reference. And of course as you noted, you can Edit anyone's post and look at their LaTeX code. That's the best way to learn.

In terms of doing LaTeX with a word processor for class, you'll have to ask your classmates what they do. You can download various LaTeX editors online.

 

[EonsNearby]

Well, I will try to re-write the last part using more basic symbols.

In order for a function to be onto, for each element y in the range (in this case C U D) there is an element x in the domain (in this case A U B) such that h(x) = y. Now, assume that y ∈ (C U D). y has to be an element from C and D by the definition of union, and y cannot be from both C and D because C and D are disjoint. As previously defined, h(x) = f(x) if x ∈ A OR g(x) if x ∈ B, so I can replace h(x) with f(x) and g(x). Since f and g are bijections, they are onto. So that means every element y in C U D there is an element x such that h(x) = y because h(x) will always equal f(x) or g(x) (but never will it equal both f(x) and g(x)).

Is that better, or did am I still off?

 

[SteveL27]

Well, I will try to re-write the last part using more basic symbols.

In order for a function to be onto, for each element y in the range (in this case C U D) there is an element x in the domain (in this case A U B) such that h(x) = y. Now, assume that y ∈ (C U D). y has to be an element from C and D by the definition of union, and y cannot be from both C and D because C and D are disjoint. As previously defined, h(x) = f(x) if x ∈ A OR g(x) if x ∈ B, so I can replace h(x) with f(x) and g(x). Since f and g are bijections, they are onto. So that means every element y in C U D there is an element x such that h(x) = y because h(x) will always equal f(x) or g(x) (but never will it equal both f(x) and g(x)).

Is that better, or did am I still off?

Yes you got it.

However (just being picky now) I still think the wording's a little imprecise. For example when you say "I can replace h(x) with f(x) and g(x)" that's imprecise. Better would be:

Suppose y in C union D. Then by definition of union, either y in C or y in D; and since the union's disjoint, exactly one of those possibilities is true.

Say y in C. Then we have a bijection f from A to C, so there's a in A such that f(a) = y; and by definition of h, we have h(a) = y. [You don't have to repeat the definition of h; we already defined it earlier and the reader is expected to remember]

On the other hand suppose y in D. Then by the same logic, there's some b in B with g(b) = y, so that h(b) = y. Either way, y gets hit; so h is onto.

The idea here is to be very detailed and explicit about one case; then you can make the analogy with the other case.

But basically you've got it now.

 

[EonsNearby]

Thank you so much with this, and when I actually write this on notebook paper, I am going to use more symbols.

But regarding the counter-example I'm going to show him, someone previously posted the following:

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

I was thinking of using that one, and basically saying something like the following to him:

"Okay, as written, the problem states that A, B, and C have the same cardinality, and that A and B are disjoint and C and D are disjoint. Then we have to prove that A U B and C U D have the same cardinality. However, based on the GIVENs in the problem, the following sets would be valid:
A={a}, B={b}, C={c}, D={d1,d2}

However, regardless of how you look at that, A U B and C U D will never have the same cardinality. Since this counter example exists, it is impossible to prove that A U B and C U D have the same cardinality. That is why I think there is a typo in question three, in that part I pointed out to you in the e-mail. Because if that is changed to say that A and C have the same cardinality and B and D have the same cardinality (and the rest is unchanged), then I can prove that A U B and C U D have the same cardinality."

Do you think that will be enough to convince him? I doubt he is a difficult teacher and he should listen to reason (otherwise I doubt he would be the department head).

 

[SteveL27]

Thank you so much with this, and when I actually write this on notebook paper, I am going to use more symbols.

But regarding the counter-example I'm going to show him, someone previously posted the following:I was thinking of using that one, and basically saying something like the following to him:

Yes that's a great example.

"Okay, as written, the problem states that A, B, and C have the same cardinality, and that A and B are disjoint and C and D are disjoint. Then we have to prove that A U B and C U D have the same cardinality. However, based on the GIVENs in the problem, the following sets would be valid:
A={a}, B={b}, C={c}, D={d1,d2}

However, regardless of how you look at that, A U B and C U D will never have the same cardinality. Since this counter example exists, it is impossible to prove that A U B and C U D have the same cardinality. That is why I think there is a typo in question three, in that part I pointed out to you in the e-mail. Because if that is changed to say that A and C have the same cardinality and B and D have the same cardinality (and the rest is unchanged), then I can prove that A U B and C U D have the same cardinality."

Do you think that will be enough to convince him? I doubt he is a difficult teacher and he should listen to reason (otherwise I doubt he would be the department head).

Well you are using words and not symbols. So if you are using this to learn, you should see if you can greatly condense your argument. What you wrote is very hand-wavy and vague. I don't doubt that you have all the pieces in there but you need to try to make a tighter logical and symbolic argument.

I don't think your teacher will need convincing, he'll suddenly see it and feel silly. So the exercise of tightening up this argument is for you, not the teacher.

I would also ask him if he expects people to already know how to do these kinds of proofs; or if you are expected to learn that set of skills in the course. So I wouldn't go in armed with logic ... the logic part is for your own learning. But you need to find out whether everyone else in class knocked out this exercise in five minutes or if they were expected to struggle with it. So that you can find out whether you need to put in some extra work going forward.

Can you tell me what class this is for? I googled "computer science 4200/5200" and found several offerings in various schools, all different.

But I gather this is an upper-division/graduate level computer science class. So it's possible that your teacher is assuming you've seen things you haven't seen. It's important for you to find out early on if that's the case. And it's important for your teacher to find out too! That's what I'd try to get some insight on when you meet with the teacher.

 

[EonsNearby]

I actually sent an e-mail out to everyone in my class asking for help like 3 days ago, but only one person responded and he didn't know how to solve any of the problems in the assignment.

 

[SteveL27]

I actually sent an e-mail out to everyone in my class asking for help like 3 days ago, but only one person responded and he didn't know how to solve any of the problems in the assignment.

So maybe it's the teacher who's assuming knowledge that the class doesn't have. I sort of believe that because of the nature of the problem. He defines a bijection then expects you to be able to walk through the proof that we did.

It takes some level of experience before you can see that you have to name the two bijections f and g, then put them together the way we did, and then do all the little mini-proofs about 1-1 and onto, nailing down the details.

I would not expect someone who just heard the definition of bijection five minutes ago to be able to bang through this proof without a little help. Perhaps your teacher needs to spend a couple of lectures on how to do proofs.

If you don't mind my asking, what class is this? I'm just curious what aspect of computer science it is.

 

[EonsNearby]

The class is Automata, Complexity, and Compatability. I'm a CPSC Information Security and Assurance major, and this is counts as an elective that I need to take to graduate.

 

[SteveL27]

The class is Automata, Complexity, and Compatability. I'm a CPSC Information Security and Assurance major, and this is counts as an elective that I need to take to graduate.

That's pretty interesting stuff. Should be fun. You'll definitely see some formal proofs.

 

[EonsNearby]

Well, I'm hoping it is better than this rocky stuff, because this problem has not been kind to my sleep schedule.

 

[fader84]

I am also in this class and just recently started following the discussion, which is why I haven't contributed anything. In response to the earlier post about:
"I would also ask him if he expects people to already know how to do these kinds of proofs; or if you are expected to learn that set of skills in the course." (I don't really know how to do the quoting thing y'all were doing earlier so I just did it this way). I really have no idea how to do these proofs and would have had no idea where to start if EonsNearby hadn't asked the questions in the first place.

 

[EonsNearby]

Yeah, I typically find flaws/typos in assignments first since I try to do them as soon as they are assigned. I'm assuming that everyone waited till this day or yesterday to start looking at the assignment.

 

[SteveL27]

I am also in this class and just recently started following the discussion, which is why I haven't contributed anything. In response to the earlier post about:
"I would also ask him if he expects people to already know how to do these kinds of proofs; or if you are expected to learn that set of skills in the course." (I don't really know how to do the quoting thing y'all were doing earlier so I just did it this way). I really have no idea how to do these proofs and would have had no idea where to start if EonsNearby hadn't asked the questions in the first place.

Just hit "Edit" on my post and it will show you all the markup I used. Or just hit "Quote" and it will quote the entire post for you.

Maybe you should all go see him at once. He needs to know that he's losing people from the getgo. Sometimes professors can forget all about what it's like to see this material for the first time.

Yeah, I typically find flaws/typos in assignments first since I try to do them as soon as they are assigned. I'm assuming that everyone waited till this day or yesterday to start looking at the assignment.

You did well to jump on the assignment right away. This is a class where you want to stay ahead of the text, ahead of the lectures, and jump on the HW the moment you get it.

 

[fader84]

Hopefully I did this right.

Maybe you should all go see him at once. He needs to know that he's losing people from the getgo. Sometimes professors can forget all about what it's like to see this material for the first time.

Is a good idea but not sure how the professor would react. Possibly mentioning that multiple students that EonsNearby has talked to are having problems with the assignment would have about the same effect as multiple people coming to his office at once. If it doesn't, then the multiple people at once option can be explored.

You did well to jump on the assignment right away. This is a class where you want to stay ahead of the text, ahead of the lectures, and jump on the HW the moment you get it.

I started looking at it when first assigned as well and tried to do the ones that I understood enough to at least get a partial answer for before I tried to do the ones that I didn't have a clue how to do. I'm a graduate student which means I have more of the problems to do, which is why it has taken me until now to look at this question. I am also rather bad at math which means it takes longer than normal for me to figure these things out.

 

[EonsNearby]

I started looking at it when first assigned as well and tried to do the ones that I understood enough to at least get a partial answer for before I tried to do the ones that I didn't have a clue how to do. I'm a graduate student which means I have more of the problems to do, which is why it has taken me until now to look at this question. I am also rather bad at math which means it takes longer than normal for me to figure these things out.

I wasn't trying to imply anything bad, like I think the other students are lazy or procrastinators or anything, when I said I assumed most people waited until recently to do this homework. I just thought that since hardly anyone responded, and when I did get a response, it was 2 days ago.

 

[fader84]

I didn't think you were trying to imply anything. I withheld replying in the hopes that he would realize that there was a mistake and inform us like he did for question 1. I must have missed it when you ask about the other questions, to which my response would have been I just put down logic and hoped that he was satisfied with that. Well, logic and some of the definitions out of the book.

 

[justink2006]

I am also in this class, I figured out there was a error in the assignment, but I was not sure about it.

 

[justink2006]

I didn't think you were trying to imply anything. I withheld replying in the hopes that he would realize that there was a mistake and inform us like he did for question 1. I must have missed it when you ask about the other questions, to which my response would have been I just put down logic and hoped that he was satisfied with that. Well, logic and some of the definitions out of the book.

He realized the mistake after someone told him there is a mistake.