Proofs involving functions and sets. Related questions.

In summary, the author is trying to prove the theorem labeled "2" in the previous image and is having trouble with writing it down in a rigorous manner. The author also has a few questions concerning sets and functions for the experts.
  • #1
scorpion990
86
0
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 [Broken]

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.
 
Last edited by a moderator:
Physics news on Phys.org
  • #2
there are a number of things wrong with your first proof which is:

[tex]A, B\subset X[/tex]
[tex]f: X\rightarrow Y[/tex]

Prove: [itex]f(A\union B)= F(A)U F(B)[/tex]
first error (may be a typo): that should be [itex]f(A)U f(B)[/itex]

proof: is [itex]y\in f(A)U f(B)[/itex], then [itex]x\in A[/itex], [itex]x\in B[/itex]
Second error: you have not identified x. You should say "there exist x such that f(x)= y and [itex]x\in A[/itex], [itex]x\in B[/itex]. Actually, it would be better to first say there exist x in [itex]AU B[/itex] such that [itex]y= f(x)\in f(AU B)[/itex], therefore [itex]x\in A[/itex] so [itex]y= f(x)\in f(A)[/itex] and [itex]x\in B[/itex] so [itex]y= f(x)\in f(B)[/itex].

Similarly for
if [itex]y\in f(A)U f(B))[/itex]
You need to say [itex]y\in f(A)[/itex] and [itex]y\in f(B)[/itex]. From [itex]y\in f(A)[/itex] it follows that there exist [itex]x_1\in A[/itex] such that [itex]y= f(x_1)\in f(A)[/itex] and there exist [itex]x_2\in B[/itex] such that [itex]y= f(x_2)\in f(B)[/itex]. Notice that it does not follow that [itex]x_1= x_2[/itex]! However, that doesn't matter. Both [itex]x_1[/itex] and [itex]x_2[/itex] are in [itex]AU B[/itex] so [itex]y= f(x_1)= f(x_2)\in f(AU B)[/itex].
That would be important if this were [itex]\A\intersect B[/itex]!

As for the second problem:
[tex][tex]C\subset X[/itex]
[tex]f:X\rightarrow Y[/tex]
Prove: [itex]f(f^{-1}(C))\subset C[/itex]

Start by saying "if [itex]y\in f(f^{-1}(C))[/itex] then there exist [itex]x\in f^{-1}(C)[/itex] such that y= f(x). Since [itex]x\in f^{-1}(C)[/itex], then y= f(x) is in ?
 
  • #3
W hat do you mean by logical steps??
 
  • #4
scorpion990 said:
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.
 
  • #5
evagelos said:
W hat do you mean by logical steps??

I just didn't know how to convert my description into set notation.
 
  • #6
asdfggfdsa said:
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 2m. Since each of those functions corresponds to a subset of A, there are 2m subsets of A.

(I think that does it)
 
  • #7
scorpion990 said:
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 [Broken]

.

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
 
Last edited by a moderator:
  • #8
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 [Broken]
I didn't finish the second proof. I'd appreciate if somebody can look over what I've written so far.
 
Last edited by a moderator:
  • #9
in the 1st proof you missing steps the 2nd one is correct
 
  • #10
Anything specific?
 
  • #11
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
 
  • #12
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 [Broken]

If this one is all right, then I will go on and think about the others =/
Thanks!
 
Last edited by a moderator:
  • #13
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)
 
  • #14
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?
 
  • #15
evagelos said:
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.
 
  • #16
NoMoreExams said:
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.
 
  • #17
scorpion990 said:
Yes.

I was actually asking evagelos to make sure he understands. But I'm glad you agree!
 
  • #18
scorpion990 said:
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
 
  • #19
scorpion990 said:
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.

evagelos said:
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.
 
  • #20
HallsofIvy said:
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
 
  • #21
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)
 
  • #22
Didn't you only prove the one is a subset of the other, and not that they're equal?
 
  • #23
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
 

1. What is the definition of a function?

A function is a mathematical concept that describes the relationship between two sets of elements, where each element in the first set (called the domain) is paired with exactly one element in the second set (called the range).

2. How do you prove that a function is injective?

To prove that a function is injective, you need to show that no two elements in the domain map to the same element in the range. This can be done by assuming that there are two elements in the domain that map to the same element in the range, and then using logical steps to show that this assumption leads to a contradiction.

3. What is the difference between a one-to-one function and an onto function?

A one-to-one function is a function that is both injective and surjective, meaning that each element in the domain maps to a unique element in the range and every element in the range is mapped to by at least one element in the domain. An onto function, also known as a surjective function, only needs to have every element in the range mapped to by at least one element in the domain, but it does not necessarily have to be injective.

4. How can you prove that two sets have the same cardinality?

To prove that two sets have the same cardinality, you need to show that there exists a bijection (a one-to-one and onto function) between the two sets. This means that the elements from one set can be paired with the elements from the other set in a way that every element in one set has a unique partner in the other set.

5. Can a function have more than one inverse?

No, a function can only have one inverse. The inverse of a function is a new function that "undoes" the original function, meaning that applying the inverse function to the output of the original function will give you back the input. If a function had more than one inverse, it would not be well-defined and would not be a proper function.

Similar threads

  • Set Theory, Logic, Probability, Statistics
Replies
5
Views
108
  • Set Theory, Logic, Probability, Statistics
Replies
3
Views
1K
  • Set Theory, Logic, Probability, Statistics
Replies
9
Views
983
  • Set Theory, Logic, Probability, Statistics
Replies
10
Views
1K
  • Set Theory, Logic, Probability, Statistics
Replies
5
Views
1K
  • Set Theory, Logic, Probability, Statistics
Replies
20
Views
1K
  • Set Theory, Logic, Probability, Statistics
2
Replies
35
Views
259
  • Set Theory, Logic, Probability, Statistics
Replies
2
Views
1K
  • Set Theory, Logic, Probability, Statistics
Replies
4
Views
2K
Replies
2
Views
254
Back
Top