Understanding Proofs Involving Subsets

[laminatedevildoll]

Hi, I am having trouble with these proofs; I don't know if I am doing these right. I'd appreciate some help. Thank you.

If X---> y is a map, then let B1, B2, B \subseteq X.

i. f(B1 U B2) = f(B1) U f(B2)

To prove this I have:
f(B1 U B2)=f(B1) U f(B2)
Since B1 U B2 \subseteq B1, we find that f(B1 U B2) \subseteq f(B1) by this rule B1 \subseteq B2 implies that f(B1) U f(B2).
Simarlarly, f(B1 U B2) \subseteq f(B2). Hence f(B1 U B2) \subseteq f(B1) U f(B2).
We have to assume that f is one to one, and y \in f(B1) U f(B2) . So there are elements x1 \in B1 and x2 \in B2 with y=f(x1) and y=f(x2). Since f is one=to one, we conclude that x1=x2 \in B1 U B2. Hence y \in f(B1) U f(B2)
Assume equality holds for all choices of B1 and B2, and that f(x1)=f(x2). To show that x1=x2. Let B1={x1} and B2={x2}

f(B1) = {f(x1)}
= {f(x2)}
= f(B2)
Therefore,
f(B1 U B2) = f(B1) U f(B2) = {f(x1)} is not equal to the empty set
B1 U B2 is not equal to the empty set because x1=x2

ii.
B \subseteq f^-1(f(B))
assume that f is one-to-one y \in f^-1(f(B))
so there are elements x \in B with y = f^-1(f(x)) implies that y \in x
f is one to one, x \in B, hence y \in B.

iii.
f(X\B) \subseteq Y\f(B) holds for all subsets B \subseteq X if and only if f is one-to-one.

y \in (Y\f(B) implies that y \in Y and y \notin f(B)
x \in (X\f(B) implies that x \in Y or f(x) and y \notin f(B)
Therefore, x \in f(x) and not in f(B) for all subsets B \subseteq X. Thereore f(x) \subseteq y

 

[neurocomp2003]

i think your missing stuff for us to help you
[]B1 U B2 subset B1 how did you get this relationship?
[]assume 1-1, is this part fo the question?

 

[laminatedevildoll]

i think your missing stuff for us to help you
[]B1 U B2 subset B1 how did you get this relationship?
[]assume 1-1, is this part fo the question?

I added more stuff to the first one. Yes, we have to prove it and show that it is one-to-one. Thank you.

 

[HallsofIvy]

"If X---> y is a map"

What is the definition of "map"?

"B1 U B2 \subseteq B1"?
Unless B2\subseteq B1 itself, that just isn't true.

 

[laminatedevildoll]

Well, we were given that B1 is subset of B2 implies that f(B1) U f(B2) as a rule. Our teacher actually proved the intersection of the same rule that way, so I was wondering if the same thing applies to the union.

 

[honestrosewater]

Your notation always confuses me a bit.
i) Let f be a map from X to Y, and let B1 and B2 be subsets of X. f is a set of pairs (x, y) such that x is in X and y is in Y (with the uniqueness requirement, of course). You want to restrict f to B1, B2, and their union. So you have the following sets:
f_B1 = {(x, y) : x is in B1 and y is in Y}
f_B2 = {(x, y) : x is in B2 and y is in Y}
f_B12 = {(x, y) : x is in (B1 U B2) and y is in Y}
And you want to know if f_B12 = (f_B1 U f_B2). Is that right?
If you don't like working from axioms, you might want to try an example and see if you can find what's at work. For simplicity, say f just maps everything to the same member of Y, say to 1. Let B1 = {1, 2} and B2 = {2, 3, 4}. Then (B1 U B2) = {1, 2, 3, 4}. f_B1 = {(1, 1), (2, 1)}. What are the others? Just a suggestion.

 

[Galileo]

You can usually do these proofs by showing one is an element of the first then it is an element of the other. (Going both ways if you have equalities).

f(x)\in f(A \cup B) \iff x\in A\cup B \iff ... \iff x\in f(A) \cup f(B)

Fill in the rest.

 

[BicycleTree]

Shouldn't that be, at the last there, f(x)\in f(A) \cup f(B) instead of just x?

 

[laminatedevildoll]

Your notation always confuses me a bit.
i) Let f be a map from X to Y, and let B1 and B2 be subsets of X. f is a set of pairs (x, y) such that x is in X and y is in Y (with the uniqueness requirement, of course). You want to restrict f to B1, B2, and their union. So you have the following sets:
f_B1 = {(x, y) : x is in B1 and y is in Y}
f_B2 = {(x, y) : x is in B2 and y is in Y}
f_B12 = {(x, y) : x is in (B1 U B2) and y is in Y}
And you want to know if f_B12 = (f_B1 U f_B2). Is that right?
If you don't like working from axioms, you might want to try an example and see if you can find what's at work. For simplicity, say f just maps everything to the same member of Y, say to 1. Let B1 = {1, 2} and B2 = {2, 3, 4}. Then (B1 U B2) = {1, 2, 3, 4}. f_B1 = {(1, 1), (2, 1)}. What are the others? Just a suggestion.

The other one from f_B1 might be (2,2)
The others from f_B2 = {(2,2), (2,3), (2,4), (3,3), (4,4)}

 

[honestrosewater]

The other one from f_B1 might be (2,2)
The others from f_B2 = {(2,2), (2,3), (2,4), (3,3), (4,4)}

No, but I'm not sure where you're going wrong. (I'll put the domain on the bottom to keep track.) f_X is a map from X to Y. Let X = {1, 2, 3, 4, 5} and Y = {1}. So f_X maps 1 to 1, 2 to 1, 3 to 1, etc. Let's lay everything out:
X = {1, 2, 3, 4, 5}
Y = {1}
f_X = {(1, 1), (2, 1), (3, 1), (4, 1), (5, 1)}
B1 = {1, 2}
B2 = {2, 3, 4}
(B1 U B2) = {1, 2, 3, 4}
f_B1 = {(x, y) : x is in B1 and (x, y) is in f_X}
For f_B1, you just want to change the domain of f_X to B1. The members of f_X don't change. But because B1 does not contain all the members of X, f_B1 will not contain all the members of f_X - you've restricted the domain. IOW, because B1 is a proper subset of X, f_B1 is a proper subset of f_X. B1 contains 1 and 2. So find the pairs in f_X whose first terms are 1 and 2. Those pairs are (1, 1) and (2, 1). So
f_B1 = {(1, 1), (2, 1)}
Now just do the same for f_B2, and f_B12.
f_B2 = {(x, y) : x is in B2 and (x, y) is in f_X}
f_B12 = {(x, y) : x is in (B1 U B2) and (x, y) is in f_X}

 

[laminatedevildoll]

Now just do the same for f_B2, and f_B12.
f_B2 = {(x, y) : x is in B2 and (x, y) is in f_X}
f_B12 = {(x, y) : x is in (B1 U B2) and (x, y) is in f_X}

f_B2 = {(3,1) (4,1)}
f_B12 = {(1, 1), (2, 1), (3,1), (4,1)}

 

[honestrosewater]

f_B2 = {(3,1) (4,1)}
f_B12 = {(1, 1), (2, 1), (3,1), (4,1)}

Sort of- you forgot the 2 in B2.
f_B1 = {(1, 1), (2, 1)}
f_B2 = {(2, 1), (3, 1), (4, 1)}
f_B12 = {(1, 1), (2, 1), (3, 1), (4, 1)}
So does f_B12 = f_B1 U f_B2? What is f_B1 U f_B2?
Can you see how this works and try what Galileo suggested? If (x, y) is in f_B12, does this mean x is in (B1 U B2)? Look at the definitions.
Prove the rest:

(x, y) \in f_{B12} \Leftrightarrow x \in B1 \ \cup \ B2 \Leftrightarrow [x \in B1 \ \vee \ x \in B2] \Leftrightarrow [(x, y) \in f_{B1} \ \vee \ (x, y) \in f_{B2}] \Leftrightarrow (x, y) \in f_{B1} \ \cup \ f_{B2}

("\vee" means "or" BTW) You may (should) already know

x \in B1 \ \cup \ B2 \Leftrightarrow [x \in B1 \ \vee \ x \in B2] and [(x, y) \in f_{B1} \ \vee \ (x, y) \in f_{B2}] \Leftrightarrow (x, y) \in f_{B1} \ \cup \ f_{B2}

They are just instances of the definition of union.

 

[laminatedevildoll]

Sort of- you forgot the 2 in B2.
f_B1 = {(1, 1), (2, 1)}
f_B2 = {(2, 1), (3, 1), (4, 1)}
f_B12 = {(1, 1), (2, 1), (3, 1), (4, 1)}
So does f_B12 = f_B1 U f_B2? What is f_B1 U f_B2?
Can you see how this works and try what Galileo suggested? If (x, y) is in f_B12, does this mean x is in (B1 U B2)? Look at the definitions.
Prove the rest:

(x, y) \in f_{B12} \Leftrightarrow x \in B1 \ \cup \ B2 \Leftrightarrow [x \in B1 \ \vee \ x \in B2] \Leftrightarrow [(x, y) \in f_{B1} \ \vee \ (x, y) \in f_{B2}] \Leftrightarrow (x, y) \in f_{B1} \ \cup \ f_{B2}

("\vee" means "or" BTW) You may (should) already know

x \in B1 \ \cup \ B2 \Leftrightarrow [x \in B1 \ \vee \ x \in B2] and [(x, y) \in f_{B1} \ \vee \ (x, y) \in f_{B2}] \Leftrightarrow (x, y) \in f_{B1} \ \cup \ f_{B2}

They are just instances of the definition of union.

I think I understand it now. y=f(x) implies that y is a member of f(B1 U B2). Therefore, y=f(x) ^ x is a member of B1 U B2 also implies that y=f(x).
I need to fix the rest.

 

[honestrosewater]

y=f(x) implies that y is a member of f(B1 U B2).

This is one reason I don't like the notation f(B1 U B2). Normally f(x) denotes the value of f at x, where x is a member of the domain of f. To also use f(x) to denote the function with domain x is just confusing, IMO. Anyway, look at what you've said again. f(x) is a member of the range of f. f_B12 is a set of pairs (x, f(x)) such that x is in B1 U B2. You're saying that f(x) = (x, f(x)).

Therefore, y=f(x) ^ x is a member of B1 U B2 also implies that y=f(x).
I need to fix the rest.

Premise: If x is a cat, then x is a mammal.
Conclusion: Therefore, if x is a mammal, then x is a cat.
The premise is true, but the conclusion is clearly false.
Let P and Q denote any formula whatsoever. P \leftrightarrow Q is the same as saying (P \rightarrow Q)\ \mbox{and}\ (Q \rightarrow P). Whenever you are trying to prove P \leftrightarrow Q, you need to prove both (P \rightarrow Q) AND (Q \rightarrow P).
The first equivalence you need to prove is
(x, y) \in f_{B12} \Leftrightarrow x \in B1 \ \cup \ B2.
So first prove
(x, y) \in f_{B12} \Rightarrow x \in B1 \ \cup \ B2.
The definition, f_B12 = {(x, y) : x is in (B1 U B2) and (x, y) is in f_X}, tells you that for every (x, y) in f_B12, x is in (B1 U B2). So that's all there is to this part of the proof. Now you need to prove
x \in B1 \ \cup \ B2 \Rightarrow (x, y) \in f_{B12}.
Does the definition also tell you that for every x in (B1 U B2), (x, y) is in f_B12?

 

[laminatedevildoll]

Now you need to prove
x \in B1 \ \cup \ B2 \Rightarrow (x, y) \in f_{B12}.
Does the definition also tell you that for every x in (B1 U B2), (x, y) is in f_B12?

This is what I came up with.

\ y=f(x) \vee [x \in B1 \vee x\in B2]
\leftrightarrow [y=f(x) \vee x \in B1] \vee [y=f(x) \vee x \in b2]
\leftrightarrow y \in f(B1) \vee y \in f(B2)
\leftrightarrow y \in f(B1) \cup f(B2)

 

[honestrosewater]

Okay, you're having the same major problem. Yes, f(x) = y. This is just a definition. But f(x) is not in any f. f(x) is a member of the range of f. f is a set of pairs (x, f(x)).

x \in B1 \cup B2 \Rightarrow (x, y) \in f_{B12}
To prove a statement of the form P -> Q, you assume P and try to derive Q. (Or assume ~Q and try to derive ~P.) So assume

x \in B1 \cup B2.

Does it then follow that

(x, y) \in f_{B12}?

The definition says, in other words:

[(x, y) \in f_{B12}] \Leftrightarrow [(x \in B1 \cup B2)\ \wedge \ ((x, y) \in f_{X})]

Just looking at the form:

P \Leftrightarrow Q \wedge R

You already know R: (x, y) \in f_{X}. So if you assume Q: x \in B1 \cup B2...

 

[laminatedevildoll]

Does that mean if y \in f(B1), then y=f(x), where x \in B1? Since B1 \subseteq B2, and y \in f(B1). Does that imply that f(B1 \cup B2) \subseteq f(B1)? Sorry if I am not getting this right.

 

[honestrosewater]

Does that mean if y \in f(B1), then y=f(x), where x \in B1? Since B1 \subseteq B2, and y \in f(B1). Does that imply that f(B1 \cup B2) \subseteq f(B1)?

Why do you think y can be a member of f_B1?

 

[laminatedevildoll]

Why do you think y can be a member of f_B1?

Because B1 \subseteq B2

 

[honestrosewater]

Because B1 \subseteq B2

1) B1 is not a subset of B2. A set S is a subset of set T iff every member of S is also a member of T.
B1 = {1, 2}
B2 = {2, 3, 4}
1 is not a member of B2, so B1 is not a subset of B2.

2) A function has a domain and a range, right? Can the set {1, 2, 3} be a function? No. Why not? Because a function is a set of pairs! Can 2 be a member of a function? No. Why not? Because a function is a set of pairs! And a function is not just any set of pairs, but a set of pairs (x, y) where x is a member of the domain, y is a member of the range, and every x is paired with a unique y. (x, y) is a member of the function. Every member of a function is a pair (x, y). Is this part clear?

3) y is also called the value of f at x, denoted f(x). Sometimes it's more convenient to use y, sometimes it's more convenient to use f(x). But y and f(x) are just two ways of denoting the same thing: the member of the range that the function f pairs with some member of the domain. Is this part clear?

4) I don't want to confuse you, so make sure you understand the stuff above first. It can happen that y and (x, y) are both members of a function. Consider a function whose domain is {1, 2} and whose range is {2, (1, 2)}. Say this function is {(1, 2), (2, (1, 2))}. So (1, 2) is both a member of the function and a member of the range. This is what stopped me from saying that y and (x, y) are never both members of a function. But it certainly doesn't hold in general; y and (x, y) cannot be members of any function. You just need to remember that a function is a set of pairs (x, y) where x is a member of the domain, y is a member of the range, and every x is paired with a unique y. Is this part clear?

 

[laminatedevildoll]

1) B1 is not a subset of B2. A set S is a subset of set T iff every member of S is also a member of T.
B1 = {1, 2}
B2 = {2, 3, 4}
1 is not a member of B2, so B1 is not a subset of B2.

This part is clear.

2) A function has a domain and a range, right? Can the set {1, 2, 3} be a function? No. Why not? Because a function is a set of pairs! Can 2 be a member of a function? No. Why not? Because a function is a set of pairs! And a function is not just any set of pairs, but a set of pairs (x, y) where x is a member of the domain, y is a member of the range, and every x is paired with a unique y. (x, y) is a member of the function. Every member of a function is a pair (x, y). Is this part clear?

This part is clear.

3) y is also called the value of f at x, denoted f(x). Sometimes it's more convenient to use y, sometimes it's more convenient to use f(x). But y and f(x) are just two ways of denoting the same thing: the member of the range that the function f pairs with some member of the domain. Is this part clear?

This part is clear.

4) I don't want to confuse you, so make sure you understand the stuff above first. It can happen that y and (x, y) are both members of a function. Consider a function whose domain is {1, 2} and whose range is {2, (1, 2)}. Say this function is {(1, 2), (2, (1, 2))}. So (1, 2) is both a member of the function and a member of the range. This is what stopped me from saying that y and (x, y) are never both members of a function. But it certainly doesn't hold in general; y and (x, y) cannot be members of any function. You just need to remember that a function is a set of pairs (x, y) where x is a member of the domain, y is a member of the range, and every x is paired with a unique y. Is this part clear?

Yes this part is clear. It sometimes can get confusing when you're not laying everything out on the table.

 

[laminatedevildoll]

You already know R: (x, y) \in f_{X}. So if you assume Q: x \in B1 \cup B2...

Does f_{X} denote f(x)?

 

[honestrosewater]

Does f_{X} denote f(x)?

No, it may not be as clear in the tex, but that X is a subscript. I have been using subscripts to denote the domain of the function (because the domains change). So f_X denotes the function whose domain is X, f_B1 denotes the function whose domain is B1, etc. Of course, the range is the same for all of them.

I'll give you a hint. The proof of

x \in B1 \cup B2 \Rightarrow (x, y) \in f_{B12}

is really just one line. But it doesn't hurt to know the general way to prove such a statement.