Explore BrainMass
Share

Explore BrainMass

    Providing proof about Cardinality

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

    Let A, B, C be sets. Show that the sets (A^B)^C and A^(BxC) have equal cardinality by constructing an explicit bijection between the two sets. Conclude that (a^b)^c=a^bc for any natural numbers a, b, c. Use a similar argument to also conclude a^b x a^c= a^b+c

    © BrainMass Inc. brainmass.com October 10, 2019, 4:22 am ad1c9bdddf
    https://brainmass.com/math/discrete-math/providing-proof-about-cardinality-457751

    Solution Preview

    (i) Consider the mapping F:(A^B)^C-->A^(BxC) given as follows. It sends f:C-->(A^B) to F(f):BxC-->A defined by F(f)(b,c)=f(c)(b).

    Let us show that F is injective. To this end, let us consider f,f':C-->(A^B) such that F(f)=F(f'). Let us show that f(c)=f'(c), for any c from C. For that it is sufficient to show that f(c)(b)=f'(c)(b). But f(c)(b)=F(f)(b,c), and similarly, f'(c)(b)=F(f')(b,c). Since F(f)=F(f'), F(f)(b,c)=F(f')(b,c). Therefore, f(c)(b)=f'(c)(b), and hence F is injective.

    Let us now show that F is surjective. Consider any g:BxC-->A. Construct f:C-->(A^B) as follows. f(c):B-->A ...

    Solution Summary

    This solution helps with a proof about cardinality. It helps show that sets have equal cardinality by constructing an explicit bijection between two sets.

    $2.19