Purchase Solution

Discrete Math: Proving a theorem

Not what you're looking for?

Ask Custom Question

(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.

Purchase this Solution

Solution Summary

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

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 ...

Purchase this Solution

Free BrainMass Quizzes
Geometry - Real Life Application Problems

Understanding of how geometry applies to in real-world contexts

Solving quadratic inequalities

This quiz test you on how well you are familiar with solving quadratic inequalities.

Know Your Linear Equations

Each question is a choice-summary multiple choice question that will present you with a linear equation and then make 4 statements about that equation. You must determine which of the 4 statements are true (if any) in regards to the equation.

Graphs and Functions

This quiz helps you easily identify a function and test your understanding of ranges, domains , function inverses and transformations.

Probability Quiz

Some questions on probability