Proving Function Properties with Subsets

[Enjoicube]

Alright, 2+1/2 problems here:

First:

36. Let F be a function from the set A to the set B. Let S and T be subsets of A. Show that:

a) f(S$$\cup$$T)=f(S)$$\cup$$f(T)
b)f(S$$\cap$$T)$$\subseteq$$ f(S)$$\cap$$f(T)

Note: This must be done using a membership proof. i.e. prove that f(S$$\cup$$T)$$\subseteq$$f(S)$$\cup$$f(T) AND f(S)$$\cup$$f(T)$$\subseteq$$f(S$$\cup$$T)


40. Let f be a function from A to B. Let S be a subset of B. We define the inverse image of S to be the subset of A whose elements are precisely all pre images of all elements of S. We denote the inverse image of S by f$$^{-1}$$(S) so f$$^{-1}$$(S)={a$$\in$$A| f(a)$$\in$$S}

Prove parts a and b of 36 substituting the inverse image for f, and an equality in both parts (rather than subset)

1) (not a question from the text). This was not covered in the lecture or in the book, but how do most people go about proving that a function is surjective from the definition?

Homework Equations

f$$^{-1}$$(S)={a$$\in$$A| f(a)$$\in$$S}
f(S)={f(s)|s$$\in$$S}

The Attempt at a Solution

Alright, I only have an idea of how to do 36, 40 I am lost. The professor said to use proof by case for 36, so here is how I thought it would go:

a) prove:f(S$$\cup$$T)=f(S)$$\cup$$f(T)

Proof:

1) assume x$$\in$$ f(SUT), then, by definition x$$\in$${f(s)|s$$\in$$SUT}

2) If x$$\in$${f(s)|s$$\in$$SUT}, then x$$\in$${f(s)|s$$\in$$S or T} by definition of union.

3) If x$$\in$${f(s)|s$$\in$$S}, then x$$\in$$f(S), and since f(S)$$\subseteq$$f(S)Uf(T), thus if x$$\in$${f(s)|s$$\in$$S} then x$$\in$${f(s)|s$$\in$$S}$$\cup$${f(s)|s$$\in$$T}.

4)If x$$\in$${f(s)|s$$\in$$T}, then x$$\in$$f(T), and since f(T)$$\subseteq$$f(S)Uf(T), thus if x$$\in$${f(s)|s$$\in$$T} then x$$\in$${f(s)|s$$\in$$S}$$\cup$${f(s)|s$$\in$$T}.

4)Therefore if x$$\in$$f(SUT) then x$$\in$$f(S)Uf(T)

5 Now we must prove that f(S)$$\cup$$f(T)$$\subseteq$$f(S$$\cup$$T, to do this, just invert the steps of this proof (obviously I wouldn't put this on a test but to cut length, this is reasonable)

b)f(S$$\cap$$T)$$\subseteq$$ f(S)$$\cap$$f(T)

proof:

1) assume x$$\in$$ f(S$$\cap$$T), then, by definition x$$\in$${f(s)|s$$\in$$S$$\cap$$T}

2) Then x$$\in$${f(s)|s$$\in$$S and T}.

3) Thus s$$\in$$S and s$$\in$$T and so, through simplification, we can say:

4) s$$\in$$S, if s$$\in$$S then x$$\in$${f(s)|s$$\in$$S}

5) We can also say s$$\in$$T, and if s$$\in$$T then x$$\in$${f(s)|s$$\in$$T}.

6) Therefore, if s$$\in$$S and s$$\in$$T, which are true, we have x$$\in$${f(s)|s$$\in$$S} and x$$\in$${f(s)|s$$\in$$T} (we can say through addition).

7) Note that by the definition of intersection, x$$\in$${f(s)|s$$\in$$S}$$\cap$${f(s)|s$$\in$$T}.

8) Therefore, if x$$\in$${f(s)|s$$\in$$S$$\cap$$T} then x$$\in$${f(s)|s$$\in$$S}$$\cap$${f(s)|s$$\in$$T}.

9)if x$$\in$${f(s)|s$$\in$$S$$\cap$$T} then x$$\in$${f(s)|s$$\in$$S}$$\cap$${f(s)|s$$\in$$T}.


10)This means f(S$$\cap$$T)$$\subseteq$$f(S)$$\cap$$f(T).

For Problem 40, I am wondering whether the proofs follow the same steps, or is there something else I have to worry about?

 

[Enjoicube]

To make this easier, forget problem 36, and 40, I can go in for help for that. Now my main question is on proving surjectivity: How is this done. I understand, you must pick a random member y0 of the codomain and prove that there is some value x0 from the domain such that f(x0)=y0, in practice however, this gives me trouble. For example, f(x)=x^2 isn't surjective on R-->R, however, it is surjective on R-->R+, how would one guarantee that the y0 value picked from the codomain reflects the restrictions put on it?

 

[HallsofIvy]

To make this easier, forget problem 36, and 40, I can go in for help for that. Now my main question is on proving surjectivity: How is this done. I understand, you must pick a random member y0 of the codomain and prove that there is some value x0 from the domain such that f(x0)=y0, in practice however, this gives me trouble. For example, f(x)=x^2 isn't surjective on R-->R, however, it is surjective on R-->R+, how would one guarantee that the y0 value picked from the codomain reflects the restrictions put on it?

By saying so? If you want to prove that f(x)= x²:R-->R⁺ is surjective, you would start by saying "Let y be in R⁺." Then you are looking for x in R such that x²= y. Since y is in R⁺, x= y^1/2 exists.

 

[Enjoicube]

Aha, thank you, why it couldn't be explained as clearly as that in my text is beyond me.