Purchase Solution

Prove that there is no bijection between any set A and its power set P(A) of A.

Not what you're looking for?

Ask Custom Question

There is no bijection between any set A and its power set P(A) of A.

For finite sets, proof is trivial since |A| = n and |P(A)| = 2^n. For finite sets, this is done by contradiction. Suppose there is a bijection $ between a set A and its power set P(A). Consider the set B={x|x is a member A where x is not a member $(x)}For each element x A, since $ is a function from A to the power set of A, &(x) ia a subset of A. By our earlier assumption on set theory that every element is either in a set or ot in a set, for each x A, w can certainly ask if x is a member of $(x). Therefore, the set B is well definedB. We know B is a subset of A and $ is a bijection from A to its power set P(A). For this subset B of A, there exists an element y is a member of A such that $(y)=B.

Where is y? is y a member of B ? or is y is not a member of B? in both cases we will obtain a contradiction. Therefore, our earlier claim that there is a bijection between A and its power set P(A) is false.

Attachments
Purchase this Solution
Solution Summary

It is proven that there is no bijection between any set A and its power set P(A) of A.

Solution Preview

Here I want to clarify some points of the proof.

1. $ is a map from A to its power set P(A). According to the assumption, $ is a bijection. This means, for each element B in P(A), we can find an element y in A, such that $(y)=B. B is a subset of A and B is also an element of P(A). y is an ...

Purchase this Solution
Free BrainMass Quizzes
Geometry - Real Life Application Problems

Understanding of how geometry applies to in real-world contexts

Graphs and Functions

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

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.

Probability Quiz

Some questions on probability

Exponential Expressions

In this quiz, you will have a chance to practice basic terminology of exponential expressions and how to evaluate them.

View More Free Quizzes
Related BrainMass Solutions

  • Question about group theory, cardinality and isomorphic

    One way to show that there is no ismorphism between Z_3 x Z_3 and Z_9 is to notice that Z_9 is a cyclic group generated by the element [1], and Z_3 x Z_3 is not a cyclic group, i.e. there is no element of Z_3 x Z_3 that generates the entire group.

  • Topology : Past Exam Paper

    QB5 a. A homomorphism between topological space and is a continuous bijection such that is also continuous.

  • uncountable or countable

    Also, remember that if X and Y are countable, then the cartesian product X x Y (the set of pairs (x,y)) is also countable. We will establish a bijection between P and a subset of the cartesian product of Q and N. Let f be a function from P.

  • preserve distance

    Show T_c is a bijection by finding its inverse. (c.) Show T_c is distance preserving (using vectors). We have for any , where is a fixed point. (a) I claim that is a bijection.

  • Discrete Math: Matching Zeros

    Prove: Given a collection of 513 Social Security numbers, there must be two that match zeros. 25.16: Let f: N -> Z by f(n) = set of -n/2 if n is even and (n+1)/2 if n is odd. Prove that f is bijection.

  • Equivalence Relation on the set R of all Real Numbers

    Define the mapping %:A== -> [1, 0), and prove that it is well-defined and a bijection between A== and [1, 0). a.

  • Mathematics - Algebraic Number Theory - Pigeonhole Principle

    The solution file is attached. Let us prove this by contradiction. Let P be the set of pigeons and H be the set of holes. Assume that every hole has at most one pigeon in it.

  • Bijections, Denumerability, Tautologies, Sets, Logic and Proofs (7 Problems)

    Given the following sets A = {1.2,3.4}, B = {2,3,4,5}, and C= {2,4,6} a) Find .... 4. Prove that if ... are bijections....then...is a bijection... 5. Prove that the set of Gausian integers is denumerable.

  • Cantor Ternary Set : Countable or Not?

    Thus, given that f is a bijection between the ternary expansions and the cantor set, the cantor set has the same cardinality as the ternary expansions.

View More Related Solutions