Help with a bijection proof involving 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?

 

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