Proofs involving functions and sets. Related questions.

[scorpion990]

Hey everybody... I have a few quick questions concerning sets and functions for the experts... I've been trained in applied mathematics, so I'm not really used to this kind of formalism.

1. Can somebody look at my "proposed proof" of this elementary theorem for me? I have a feeling that it is correct, although it's not giving the satisfaction of truly understanding the basics. In the very least, I'm skipping steps that are otherwise important to include in order to see exactly what's going on. I won't feel right continuing on without having the absolute basics down cold. Here it is:
http://img205.imageshack.us/img205/5286/proofqy7.png

2. I'm also trying to prove the theorem labeled "2" in the previous image. I understand the logic behind it, but I'm having trouble writing it down in a rigorous manner. At best, I can describe it by an example.
Let:
B = {1,2,3}
C = {2,4,6,8}
f: X --> Y
f(x) = 2x
The function f maps the set X into the set Y. The function is one-to-one because there exists a unique x for a given by. It is not "onto" because there exists elements in Y which do not correlate to the set X under f.
f inverse of the set C is the set B. However, the element "8" in C does not correlate to B. Applying f on the set B returns C' = {2, 4, 6}, which is a subset of the original set C.

I have absolutely no idea how to convert that into logical steps involving set theory and the definitions of functions. The book that I'm using gives no example proofs =/

Here are a few quick questions that I'm having trouble on. Any insight is appreciated.

3. "How many subsets are there of the set {1,2,3,...,m}? How many maps of this set into itself? How many maps of this set onto itself?
The first answer is clearly "an infinite number of subsets". I'm not quite so sure about the latter two questions. I don't really understand the difference between the two, so that makes it even more complicated. For the first, if they assume that X is the set of integers, and so is Y, then there would be one function that maps one into the second: f: X-->y. f(x) = x

4. This question kind of goes along with the third one. I'm really confused, though.
a. "How many functions are there from the nonempty set S into the empty set?"
I guess... one? f: X-->Y such that for all x, y = undefined
b. "How many functions are there from the empty set into an arbitrary set S?"
An infinite number of functions? Any defined function with the domain of "no elements" will map into an arbitrary set S.

Any help with any of the questions posed above are appreciated. Thanks.

 

[HallsofIvy]

there are a number of things wrong with your first proof which is:

A, B\subset X
f: X\rightarrow Y

Prove: f(A\union B)= F(A)U F(B)[/tex]

<br /> first error (may be a typo): that should be f(A)U f(B)<br /> <br /> <blockquote data-attributes="" data-quote="" data-source="" class="bbCodeBlock bbCodeBlock--expandable bbCodeBlock--quote js-expandWatch"> <div class="bbCodeBlock-content"> <div class="bbCodeBlock-expandContent js-expandContent "> proof: is y\in f(A)U f(B), then x\in A, x\in B </div> </div> </blockquote> Second error: you have not identified x. You should say &quot;there exist x such that f(x)= y and x\in A, x\in B. Actually, it would be better to first say there exist x in AU B such that y= f(x)\in f(AU B), therefore x\in A so y= f(x)\in f(A) and x\in B so y= f(x)\in f(B).<br /> <br /> Similarly for <br /> <blockquote data-attributes="" data-quote="" data-source="" class="bbCodeBlock bbCodeBlock--expandable bbCodeBlock--quote js-expandWatch"> <div class="bbCodeBlock-content"> <div class="bbCodeBlock-expandContent js-expandContent "> if y\in f(A)U f(B)) </div> </div> </blockquote> You need to say y\in f(A) and y\in f(B). From y\in f(A) it follows that there exist x_1\in A such that y= f(x_1)\in f(A) and there exist x_2\in B such that y= f(x_2)\in f(B). Notice that it does <b>not</b> follow that x_1= x_2! However, that doesn&#039;t matter. Both x_1 and x_2 are in AU B so y= f(x_1)= f(x_2)\in f(AU B).<br /> That <b>would</b> be important if this were \A\intersect B!<br /> <br /> As for the second problem:<br /> <blockquote data-attributes="" data-quote="" data-source="" class="bbCodeBlock bbCodeBlock--expandable bbCodeBlock--quote js-expandWatch"> <div class="bbCodeBlock-content"> <div class="bbCodeBlock-expandContent js-expandContent "> C\subset X </div> </div> </blockquote>

&lt;br /&gt; f:X\rightarrow Y&lt;br /&gt; Prove: f(f^{-1}(C))\subset C&lt;br /&gt; &lt;br /&gt; Start by saying &amp;quot;if y\in f(f^{-1}(C)) then there exist x\in f^{-1}(C) such that y= f(x). Since x\in f^{-1}(C), then y= f(x) is in ?

 

[evagelos]

W hat do you mean by logical steps??

 

[asdfggfdsa]

3. "How many subsets are there of the set {1,2,3,...,m}?

How many functions are there which map from A={1,2,3,...,m} to subsets of A? Using the definition of a function, you can count up those functions; since the range of each function is a subset of A, you will have counted up all the subsets of A.

Studying the definitions helps (carefully making note of logical quantifiers and connectives). Each of these questions is really just an application of the definition of a function in disguise.

 

[scorpion990]

W hat do you mean by logical steps??

I just didn't know how to convert my description into set notation.

 

[asdfggfdsa]

How many functions are there which map from A={1,2,3,...,m} to subsets of A? Using the definition of a function, you can count up those functions; since the range of each function is a subset of A, you will have counted up all the subsets of A.

Sorry, I goofed :embarrassed:

for a particular subset, each element of A={1,2,...,m} is either in it or isn't in it: the two states can be thought of as the range of a function which maps each element of the domain A to {a,b}, where a corresponds to the case when the object(s) which map(s) to a is in that fixed subset and b corresponds to the case when it isn't (the preimage of a is the subset). Call the set of all such functions f:A->{a,b} F. each function can then be thought of as a tuple of size equal to the size of the domain A in which each entry corresponds to one element of A and is either a or b. There are only two choices for each entry, so the size of F is 2^m. Since each of those functions corresponds to a subset of A, there are 2^m subsets of A.

(I think that does it)

 

[evagelos]

Hey everybody... I have a few quick questions concerning sets and functions for the experts... I've been trained in applied mathematics, so I'm not really used to this kind of formalism.

1. Can somebody look at my "proposed proof" of this elementary theorem for me? I have a feeling that it is correct, although it's not giving the satisfaction of truly understanding the basics. In the very least, I'm skipping steps that are otherwise important to include in order to see exactly what's going on. I won't feel right continuing on without having the absolute basics down cold. Here it is:
http://img205.imageshack.us/img205/5286/proofqy7.png

.

scorpion 990 could you not find this 'elementary theorem' in a book and learn it from there ?
Or you did find it in a book and although you study it hard you still do not understand it,
because the proof that you wrote it has not even one correct step

 

[scorpion990]

My book contains no example proofs for this kind of thing. This was an example problem at the end of the chapter.

EDIT:
Well... here is a slight update. I'm still pretty sure that it's wrong, but at least I'm giving it a shot...

http://img107.imageshack.us/img107/1046/proofim6.png
I didn't finish the second proof. I'd appreciate if somebody can look over what I've written so far.

 

[evagelos]

in the 1st proof you missing steps the 2nd one is correct

 

[scorpion990]

Anything specific?

 

[evagelos]

Since by definition :

f(AUB)={f(x): xεA or xεB} hence yε f(AUB) =====> y=f(x) and (xεA or xεB)=====>

(y=f(x) and xεA) or (y=f(x) and xεB) and now try to examine each case i.e let's say

(y=f(x) and xεA) 1st and then (y=f(x) and xεB) 2nd.

Each case must lead you to yεf(A)Uf(B).If you succeed in proving that then you will have no problems with the converse.

For question No 4 now i can give you a theorem from the book classical mathematics page 44
by H.B.GRIFFITHS& P.J.HILTON that say:

Given the function f:X--->Y,then if X is non empty,so is Y.If X is empty,so is f ( i.e,f=Φ which is a subset of XxY=Φ).

That together with the fact that the empty set is unique should answer No 4

 

[scorpion990]

Hey... I've been thinking about this for a little bit, and I think that I came up with a proof. It's very... long. It's probably about twice as long as it should be, but I made sure to make no assumptions at all. Any feedback would be appreciated.

http://img229.imageshack.us/img229/3513/proofcj7.png

If this one is all right, then I will go on and think about the others =/
Thanks!

 

[evagelos]

You write and i quote: By definition yεf(A) Therefor,yεf(A)Uf(B) .

how did you jump from yεf(A) to yεf(A)Uf(B) .?? what fact allowed you to do so?

now for the converse:

You write and i quote :if yεf(A)Uf(B) then y=f(x) and yεf(A) or yεf(B)
case1.y=f(x) and yεf(A)

if .yεf(A)Uf(B) .then yεf(A) or yεf(B) 0nly.... And the cases you have to consider are 1) yεf(A)......2)yεf(B)

And not.................... 1) y=f(x) and yεf(A) ......2) y=f(x) and yεf(B)

 

[NoMoreExams]

Because U means OR basically. So if x \in A then x \in (A U B). Basically for A U B to be True only one of them must be True right?

 

[scorpion990]

You write and i quote: By definition yεf(A) Therefor,yεf(A)Uf(B) .

how did you jump from yεf(A) to yεf(A)Uf(B) .?? what fact allowed you to do so?

now for the converse:

You write and i quote :if yεf(A)Uf(B) then y=f(x) and yεf(A) or yεf(B)
case1.y=f(x) and yεf(A)

if .yεf(A)Uf(B) .then yεf(A) or yεf(B) 0nly.... And the cases you have to consider are 1) yεf(A)......2)yεf(B)

And not.................... 1) y=f(x) and yεf(A) ......2) y=f(x) and yεf(B)

If x is an element of A, then x is an element of A union any other set. It's easily proven, and my book doesn't bother proving it every time. I'm not really sure I understand the problem in the "converse". Thanks.

 

[scorpion990]

Because U means OR basically. So if x \in A then x \in (A U B). Basically for A U B to be True only one of them must be True right?

Yes.

 

[NoMoreExams]

Yes.

I was actually asking evagelos to make sure he understands. But I'm glad you agree!

 

[evagelos]

If x is an element of A, then x is an element of A union any other set. It's easily proven, and my book doesn't bother proving it every time. I'm not really sure I understand the problem in the "converse". Thanks.

how do you prove it

 

[HallsofIvy]

If x is an element of A, then x is an element of A union any other set. It's easily proven, and my book doesn't bother proving it every time. I'm not really sure I understand the problem in the "converse". Thanks.

how do you prove it

If x is an element of A then x is an element of AUB. What is the DEFINITION of "AUB"?

The "converse" to "If P then Q" is "If Q then P". In particular, the "converse" of "If x is an element of A then x is an element of AUB" is "If x is an element of AUB then x is an element of A" and is NOT true.

 

[evagelos]

If x is an element of A then x is an element of AUB. What is the DEFINITION of "AUB"?

.

if x is an element of A then x is an element of AUB,it is not by definition but it is so

by the law called disjunction introduction:...p====>pvq and then by definition

I was trying to make him understand a step in his proof.Anyway the right steps for the
above are;

xεA====> xεA v xεB <======> xε(AUB).

the 1st step is by disjunction introduction and the 2nd is by definition

 

[evagelos]

a short right proof that....f(AUB) = f(A)Uf(B) is the following:

...yεf(AUB) <====> [y=f(x) & (xεA v xεB)] <====> [(y=f(x) & xεA) v (y=f(x) & xεB)] <======> yεf(A) v xεf(B) <======> yεf(A)Uf(B)

hence ......f(AUB)=f(A)Uf(B)

 

[scorpion990]

Didn't you only prove the one is a subset of the other, and not that they're equal?

 

[evagelos]

no because the implications are double implications .

The forward implications prove ... yεf(AUB) ====>yεf(A)Uf(B) hence f(AUB) is a subset of f(A)Uf(B) and:

The backward prove...... yεf(AUB) <======yεf(A)Uf(B) hence f(A)Uf(B) is a subset of f(AUB)

Now proof using double implications is correct if at any point along the proof you can turn the proof back wards and check if your backward implications are correct.

And certainly this kind of proof has a logical explanation