# Proofs involving subsets

1. May 17, 2005

### 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

Last edited: May 18, 2005
2. May 17, 2005

### neurocomp2003

[]B1 U B2 subset B1 how did you get this relationship?
[]assume 1-1, is this part fo the question?

3. May 18, 2005

### laminatedevildoll

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

4. May 18, 2005

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

5. May 18, 2005

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

Last edited: May 18, 2005
6. May 19, 2005

### 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:
fB1 = {(x, y) : x is in B1 and y is in Y}
fB2 = {(x, y) : x is in B2 and y is in Y}
fB12 = {(x, y) : x is in (B1 U B2) and y is in Y}
And you want to know if fB12 = (fB1 U fB2). 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}. fB1 = {(1, 1), (2, 1)}. What are the others? Just a suggestion.

7. May 19, 2005

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

8. May 19, 2005

### BicycleTree

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

9. May 20, 2005

### laminatedevildoll

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

10. May 20, 2005

### honestrosewater

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

Last edited: May 20, 2005
11. May 22, 2005

### laminatedevildoll

fB2 = {(3,1) (4,1)}
fB12 = {(1, 1), (2, 1), (3,1), (4,1)}

12. May 22, 2005

### honestrosewater

Sort of- you forgot the 2 in B2.
fB1 = {(1, 1), (2, 1)}
fB2 = {(2, 1), (3, 1), (4, 1)}
fB12 = {(1, 1), (2, 1), (3, 1), (4, 1)}
So does fB12 = fB1 U fB2? What is fB1 U fB2?
Can you see how this works and try what Galileo suggested? If (x, y) is in fB12, 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.

Last edited: May 22, 2005
13. May 28, 2005

### laminatedevildoll

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.

14. May 28, 2005

### honestrosewater

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. fB12 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)).
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, fB12 = {(x, y) : x is in (B1 U B2) and (x, y) is in fX}, tells you that for every (x, y) in fB12, 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 fB12?

15. May 30, 2005

### laminatedevildoll

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)$$

Last edited: May 30, 2005
16. May 30, 2005

### 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$$.

$$(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$...

17. May 31, 2005

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

Last edited: May 31, 2005
18. Jun 1, 2005

### honestrosewater

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

19. Jun 1, 2005

### laminatedevildoll

Because $$B1 \subseteq B2$$

20. Jun 1, 2005

### honestrosewater

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?