# Proof Questions!

1. Jan 16, 2008

### TheMathsDude

Hey guys,

I've got two sets of questions here both requiring proofs.

Here is a little progress I made with Question Two part c)
f=({a,1},{b,1},{c,2},{d,2}) , A={a,c} & B={b,d}
f(A)/f(B) = emptyset & f(A/B)={1,2}

Any help with the other two parts to Question Two/Three would be great.

Many Thanks,
The Maths Dude

#### Attached Files:

File size:
28.9 KB
Views:
120
• ###### maths2.JPG
File size:
33.4 KB
Views:
110
2. Jan 16, 2008

### HallsofIvy

Staff Emeritus
For problem 1, two parts ask you to prove a set is subset of another set and one asks you to prove two sets are equal. The standard method is to use the definitions: A is a subset of B if and only if every member of A is a member of B. Two sets A and B are equal if each is a subset of the other: if every member of A is a member of B and vice-versa.

For example, the second question that f(A intersect B) is a subset of f(A) intersect f(B). Okay, start by saying "If y is in f(A intersect) then there exist x in A intersect B such that y= f(x). Since x is in A intersect B, then either x is in A or x is in B. If x is in A, then f(x)= y is in f(A) and so in f(A) intersect f(B). If x is in A, then f(x)= y is in f(B) and so in f(A) intersect f(B).

The second problem asks about "injective" and "surjective": use the definitions! A function, f:A->B is injective (also called "one to one") if and only if f(x)= f(y) only if x= y. f:A->B is surjective (also called "onto") if and only if for every y in B, there exist x in A such that f(x)= y.

For example, with f:A->B, g:B-> C, a) i) asks you to prove "If g o f is injective, then f is injective."
I might do this by "indirect proof" or "proof by contradiction". Suppose f is not injective. Then there exist x, y in A, $x\ne y$, such that f(x)= f(y) (in B). Call that common value u: f(x)= f(y)= u. Since g is a function, g(u) is a single value. Call that v. Then g o f(x)= g(f(x))= g(u)= v and g o f(y)= g(f(y))= g(u)= v. That is, g o f(x)= g o f(y) contradicting the fact that g o f is injective.

The second part of this is basically the same except that we have "is NOT injective" or "is NOT surjective". Use the fact that the contrapositive of a theorem is true if and only if the theorem is true. The contrapositive of the statement "if p then q" is "if NOT q then NOT p". The contrapositive of the statement "if NOT p then NOT q" is "if q then p".

Last edited: Jan 16, 2008
3. Jan 16, 2008

### al-mahed

supose $$A =\left\{a_1,a_2,a_3,...,a_n\right\} \ and \ B=\left\{b_1,b_2,b_3,...,b_m\right\}$$

the elements of $$A\cup B$$ are the domain of the function, while the elements of $$f(A\cup B)$$ are obviously the image

definition of function:

For each element of the domain there are only one element of the image
for any element of the image there is one or more than one element of the domain

Now its easy to see that if all elements of A and B are different, the image of A + the image of B = the image of $$A\cup B$$.

For the equal elements, if $$a_i = b_j$$ for some i,j = 1,2,3,4,5..., they must have the same image

Now its easy to see that if all elements of A and B are the same, the image of A + the image of B = the image of $$A\cup B$$.

4. Jan 16, 2008

### al-mahed

To make more clear, if some of the elements of A and B are equal, and some of them are different, we can think in 3 different sub-sets such that the sub-set C contain only the elements in A that are not in B, the subset D contain only the elements in both A and B, and the sub-set E contain only the elements that are not in A.

$$A\cup B = C\cup D\cup E$$ and by the definitions above you are able to conclude that $$f(A\cup B) = f(A) + f(B)$$

5. Sep 14, 2010

### kolalight

How do we prove:
If A is a subset of B then f(A) is subset of f(B) ?

6. Sep 14, 2010

### kolalight

How do we prove:
If A is a subset of B then f(A) is subset of f(B) ?

7. Sep 14, 2010