Subsets and functions math help

[playboy]

Suppose f:A--->B and S and T are subsets of A. Prove or give a counter example.

(a) if S\subseteqT, then f(S)\subseteqf(T)
(b) if f(S)\subseteqf(T), then S\subseteqT

I know for a fact that (a) is true. The reason I say this is because if S\subseteqT ... then for example: Let S be the set of all Real numbers and let T be the set {-3 -2 -1 0 1 2 3} and let f be the funtion defined by f(x)=x-1. If you apply all the elements in S and T to this function, then f(S)\subseteqf(T). I don't think their is a counterexample out their.

I could use the same reasoning to argue that (b) is true as well.

So I've spent an hour on this and i thought perhaps i could use the contrapositve to proove this.

Does this statements exist?

"if f(S) is NOT contained in f(T), then S is NOT contained in T"

I mean, NOT contained can have different meanings.

For example: S = {1 2 3 4} and T = {2 3 4 5 6}. Here, S is NOT contained in T, but it does have an intersetion.

Or S = {1 2 3} and T = {4 5 6} are disjoint.

So is their such thing as NOT contained in?

 

[VietDao29]

For a, You can think this way:
If an element x₀ is in S, is it also in T?
So if f(x₀) is in f(S), is it also in f(T)?
From there, is a true? And can you prove that a is true?
For b, What if you have a function:
f: R ---> R⁺
{ } \quad x \mapsto x ^ 2, and S := ]0, 1[, T := ]-0.5, 0[ ??
Can you go from here?

 

[matt grime]

You are allowed to make counter examples as trivial as you want. What's the easiest way to deal with functions? Think of finite sets. What are the easiest things to deal with for b)? How about a really small A with two distinct subsets S and T (from 'a' we know anything in SnT must be sent to f(T) so we may as well assume that not only are we looking for S not contained in T but S in fact disjoint from T). Further we won't care about bits of S mapped outside f(T), so we may as well assume that f maps S into f(T).So let A be the set {0,1} S={0) T={1}, now can you find a really trivial function to a set even smaller than A? (I am using trivial not as a derisory comment on you but in its mathematical context.)

 

[playboy]

Suppose f:A--->B and S and T are subsets of A. Prove or give a counter example.

(b) if f(S)\subseteqf(T), then S\subseteqT

Let A = {0,1} S={0} T={1}
Let f:R---->R defined by f(x) = 3

Thus, f(S)=3 and f(T)=3 and therefore; f(S)\subseteqf(T), which shows that S\subseteqT does not have to occur.

Is this a legit counterexample? It seems that i did it backwards (something i would not usually do.) since i started by assuming S and T are disjoint and shoing that f(S)\subseteqf(T).

i would think that you would start by assuming f(S)\subseteqf(T) and showing that S does not have to contain T

 

[0rthodontist]

That's right except f(S) = {3} not 3. (the image of a set is a set) Also f should be A-->R (or else let A = R) because of what you're trying to prove.

 

[playboy]

Thanks for checking!

You see, I am having a lot of difficulties starting proofs that have \subseteq symbols in them. Perhaps someone can help explain to me how to start off/begin writing proofs for them.

For example: With a question like this:

Suppose that f:A---->B and suppose that C\subseteqA and D\subseteqB

(a) Prove or give a counterexample: f(C)\subseteqD iff C\subseteqf^-1(D).
(b) What condition on f will ensure that f(C)\subseteqD iff C\subseteqf^-1(D)? Prove your answer.

My problem here is how do i know if i should prove or look for a counterexample? I mean, i spent hours on (a) and eventually drew out a diagram for it, i still don't know if their is a counterexample (well, by looking at what (b) is asking, I am sure i need a counterexample - but that's not helping me unfortunatly.)

I mean, its not only the \subseteq symbolls that are getting me, its also that functions are involved - i read the textbook over and over and did the practise examples, so i know that i understand everything, its just getting a start. I came accros many different ways to start proofs... but does anybody know any easy way (or rule) on starting a proof like this?

For the above, I know you have to start by proving f(C)\subseteqD \subseteq C\subseteqf^-1(D) ... and then do the opposit.

So i would start by saying let y\inf(C)\subseteqD ... then there exists a point x in f(C)\subseteqD such that f(x) =y ... etc...??

 

[matt grime]

Experience is what you need. Think about your favourite functions if you must, like sin, it takes all multiples of pi to 0, so functions can be many to one, that is allowed. That is all I used for the counter example. I just gave a simple counter example by construction. And no I didn't work backwards, I just used the simple notion that the range set of a function does not in depend upon the domain at all. If I tell you that two function lands in the set {0,1} then you cannot tell me what the domains are, whether they are even the same set or completely different. As it happens, I think a) is true.

What is f^{-1}(D)? It is the set of all points that map to D, if C is in that set then f(C) is contained in D. Conversely if C is mapped into D, it lies in the inverse image of D (the set of all points mapped into D).

 

[0rthodontist]

Well, by the way the question is asked a) is probably not true, because in part b) they ask what additional condition you can impose to make it true. Maybe they mean you can't assume f is invertible, so a counterexample would be a non-invertible function and the condition for part b) would be that the function must be invertible.

I think that the best way to think about these things is with the domain-codomain diagrams and just thinking of all the possible ways the function could be set up. To prove it you don't say y is an element of "f(C) is a subset of D"... you say y is an element of f(C). And that means there's an x in C, not f(C), such that f(x) = y. Anyway, I think that's the wrong way to approach it: instead, suppose x is an element of C, so f(x) = y is an element of D, and show that x is an element of f^(-1)(D) according to how Matt Grime did it.

 

[playboy]

Suppose that f:A---->B and suppose that C\subseteqA and D\subseteqB

(a) Prove or give a counterexample: f(C)\subseteqD iff C\subseteqf^-1(D).
(b) What condition on f will ensure that f(C)\subseteqD iff C\subseteqf^-1(D)? Prove your answer.

Okay, i tried to disprove this by doing specific fuctions which are injective, surjective, bijective, or neither ... unfortunatly, i failed to find a counter example, so i set out to prove it. (Matt Grimm was right)

f(C)\subseteqD iff C\subseteqf^-1(D).

You want to show it both ways:

1) If f(C)\subseteqD then C\subseteqf^-1(D).

Thank you Orthodontist and Matt Grimm for your help. I tried what you said, but it was difficult because I am trying to show "If f(C)\subseteqD then C\subseteqf^-1(D)." This means that i have to start off with f(C)\subseteqD and show that it arrives to C\subseteqf^-1(D).

Suppose that y\inf(C). Then f^-1(y)=x\inc. Also, f(C)y\inD and thus, y\inD which implies that f^-1(y)y\inf^-(D). But f^-1(y)=x and therefor, x\inf-1(D). Since x\inC this means that C\inf^-1(D)

Boy that looks messy

2) If C\subseteqf^-1(D) then f(C)\subseteqD

Suppose that x\inC, then x\inf^-1(D). Therefore, f(x)=y\inD. Therefore, y\inD and thus... f^-1(y)\inf^-1(D). But, f^-1(y)=x ... thefroe, x\inf^-1(D). But, x\inC and so, f(C) lies in D.

this second part looks like i went in a circle.. so that's not much of proof :(

 

[0rthodontist]

If the function is f: {1, 2, 3} --> {1, 2, 3} defined as {(1, 1), (2, 1) (3, 2)}, then f^(-1) does not exist so the equivalence of a) cannot be true without an added condition.

But assuming that f is invertible, your first proof does not make any sense.

Suppose that y\inf(C). Then f^-1(y)=x\inc. Also, f(C)y\inD and thus, y\inD which implies that f^-1(y)y\inf^-(D). But f^-1(y)=x and therefor, x\inf-1(D). Since x\inC this means that C\inf^-1(D)

I'll rewrite what I think you mean:

"Suppose that y\inf(C). Then f^-1(y)\inC. Also, y\inD which implies that f^-1(y)\inf^-1(D). Since f^-1(y)\inC this means that C\subseteqf^-1(D)"

The conclusion doesn't follow. What you've shown is there is an element of C that is also an element of f^-1(D). Specifically, this element is f^-1(y) for some y in f(C). What you need to show is that if _anything_ is an element of C, then it _must_ be an element of f^-1(D). Start by saying "Suppose that x\inC."


The notation on your second proof is better:

Suppose that x\inC, then x\inf^-1(D). Therefore, f(x)=y\inD. Therefore, y\inD and thus... f^-1(y)\inf^-1(D). But, f^-1(y)=x ... thefroe, x\inf^-1(D). But, x\inC and so, f(C) lies in D.

Yes, that is circular. You started by supposing x\inC, proved by supposition that x\inf^-1(D), and then did some convolutions to prove it again. What you need to prove in this case is that if anything is an element of f(C), then it is an element of D.

 

[playboy]

Suppose that f:A---->B and suppose that C\subseteqA and D\subseteqB

(a) Prove or give a counterexample: f(C)\subseteqD iff C\subseteqf^-1(D).
(b) What condition on f will ensure that f(C)=D iff C=f^-1(D)? Prove your answer.

Notice that my part (b) above changed from )\subseteq to = signs. I didn't notice that until now. I guess i have to pay very close attention when doing these problems... i feel so...dumb

Check it both ways:

1) If f(C)\subseteqD, then C\subseteqf^-1(D)

Suppose x\inC. then f(x)\inf(C). Since f(x)=y, then y\inf(C). Since f(c)\subseteqD, y\inD. Thus, f^-1(y)\inf^-1(D). But f^-1(y)=x. Therefore, x\inf^-1(D). But, x\inC. Therefore, C\subseteqf^-1(D).

2) If C\subseteqf^-1(D), then f(C)\subseteqD

Suppose that y\inf(C). Then f^-1(y)\inC. But f^-1(y)=x. Therefor, x\inC. But C\subseteqf^-1(D). Therefore, x\inf^-1(D). this means that f(x)\inD. But f(x)=y... and therefore y\inD. But y\inf(C). this implies that f(C)\subseteqD

 

[0rthodontist]

Those look right.

I don't see how the change in part b) alters anything. If f is invertible, it should satisfy those properties with no additional condition.

 

[matt grime]

It is perfectly possible to use f^{-1} without f being invertible, as this question does. It is defined on subsets of the image. f^{-1}(D) is the set of elements mapped to D.

Now, playboy, this means that when you write y=f(x) this does not allow you to use f^{-1}(y)=x since that is not true, f^{-1}(y) is the set of points mapped to y, of which x is *just one*.

I already gave you the proof, of a). It was two lines:

What is f^{-1}(D)? It is the set of all points that map to D, if C is in that set then f(C) is contained in D. Conversely if C is mapped into D, it lies in the inverse image of D (the set of all points mapped into D).

You do not have to use long proofs, proofs with lots of notation, a mere simple explanation wil do.

 

[playboy]

Now, playboy, this means that when you write y=f(x) this does not allow you to use f^{-1}(y)=x since that is not true, f^{-1}(y) is the set of points mapped to y, of which x is *just one*.

I already gave you the proof, of a). It was two lines:

What is f^{-1}(D)? It is the set of all points that map to D, if C is in that set then f(C) is contained in D. Conversely if C is mapped into D, it lies in the inverse image of D (the set of all points mapped into D).

You do not have to use long proofs, proofs with lots of notation, a mere simple explanation wil do.

Matt Grime, when they say "Prove," it seems that an explanation is just not what they mean... it seems like you need to do it algebraically. The examples in the textbook use x's and functions etc... in their proof's. Not that I am aruging with you, i allways thought algebra has to be involved.

Like this question in the book: Let f:A--->B and suppose that there exists a function g:B---->A such that (g of f) =Ia and (f of g)=Ib
Prove that f is bijective.
Prove that g=f^-1

Like this proof, you would simply state that it is indeed byjective since the function f has an inverse (and that is by definition.)

and g=f^-1 since (g of f) and (f of g) gives the identity. (and that too is by defintion.)

No algebra was used in the above, just definitions.

Oh and you know how you explained how if f(x)=y, you cannot say that f^-1(y)=x. I suppose f^-1(y)=y would work... that makes more sense to me.

 

[matt grime]

Matt Grime, when they say "Prove," it seems that an explanation is just not what they mean... it seems like you need to do it algebraically.

erm, definitely not. a proof is a series of logical arguments that, well, prove something. there is no need to use symbols alone if that is unnecessary and confusing. picking the correct way to describe something is half the difficulty in maths.

The examples in the textbook use x's and functions etc... in their proof's. Not that I am aruging with you, i allways thought algebra has to be involved.

no, not at all, as long as your argument is cogent. that is where symbols have an advantage, it is harder to miscommunicate in symbols, but it is harder to understand when written. besides, you're asking how you're supposed to think of these things. and how i think of f^{-1}(D) is as the set of elements mapped to D, not {x in A: f(x)=y for some y in D}. there is a definite over emphasis on manipulation of strings of symbols in too many maths courses, when there are better ways to think of these things to aid understanding.

Like this question in the book: Let f:A--->B and suppose that there exists a function g:B---->A such that (g of f) =Ia and (f of g)=Ib
Prove that f is bijective.
Prove that g=f^-1

Like this proof, you would simply state that it is indeed byjective since the function f has an inverse (and that is by definition.)

and g=f^-1 since (g of f) and (f of g) gives the identity. (and that too is by defintion.)

i think it would depend upon your precise definitions of inverse since there are two equivalent ways of doing it (at least).

No algebra was used in the above, just definitions.

Oh and you know how you explained how if f(x)=y, you cannot say that f^-1(y)=x. I suppose f^-1(y)=y would work... that makes more sense to me.

well, that makes no sense to me, at all. since it implies f(y)=y, where did you get that from? the f^{-1} thing in the question acts on *subsets* not elements, it gives the preimage of a subset, possibly a subset with only one element but subset nonetheless.

 

[0rthodontist]

It is perfectly possible to use f^{-1} without f being invertible, as this question does. It is defined on subsets of the image. f^{-1}(D) is the set of elements mapped to D.

Oh, I see. I didn't know.