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.