Explore BrainMass
Share

# Discrete Math: Proving a theorem

This content was COPIED from BrainMass.com - View the original, and get the already-completed solution here!

(a) Proof. Let f be onto. Consider any C is a subset of Y. Let y E f(f^-1(C)). Then y=f(x) for some x E F^-1(C). But the fact that x E f^-1(C) implies that f(x) E C. Moreover, f(x)=y. Therefore y E C. Thus we have proved that f(f^-1(C)) is a subset of C. For the converse, consider any c E C. Since f is onto, there exists an element x E X, such that c = f(x). Then x E f^-1(C), and c E f(f^-1(C). Therefore, C is a subset of f(f^-1(C)) = C. Thus we have proved both f(f^-1(C)) is a subset of C and C is a subset of f(f^-1(C)) . This implies that f(f^-1(C)) = C.

Let f(f^-1(C)) = C, for any C subset of Y. Let us show that f is onto. Consider any y E Y, and assume that f^-1{y} is empty. Then f(f^-1{y}) is also empty. But by the assumption, f(f^-1{y}), a contradiction. Therefore, f^-1{y} is not empty. So, there exists x E f^-1{y}, and hence f(x) = y. Thus, f is onto.

(b) Let X = Y = {1,2}. Let f: X ---> Y be defined as follows: f(1) = f(2) = 1. Let C = {2}. Then f^-1(C) is empty. Therefore f(f^-1(C)) is also empty, and hence is not equal to C.

https://brainmass.com/math/discrete-math/discrete-math-proving-theorem-446767

#### Solution Preview

See the attachment.

(a) Proof. Let f be onto. Consider any . Let . Then for some . But the fact that implies that . Moreover, . Therefore . Thus we have proved ...

#### Solution Summary

This solution helps with a discrete math problem that involves proving a theorem.

\$2.19