Suppose X, Y are nonempty sets such that |X| ≤ |Y|. Prove that |P(X)| ≤ |P(Y)|.

Hint: you have to think about injective functions, since X and Y may not be finite sets.
in Other Math Topics by
reshown ago by

Your answer

Your name to display (optional):
Privacy: Your email address will only be used for sending these notifications.
Anti-spam verification:
To avoid this verification in future, please log in or register.

1 Answer

If n1=|X| and n2=|Y|, their power sets will be P(X) and P(Y).

The number of elements in P(X)=|P(X)|=2ⁿ¹ and similarly |P(Y)|=2ⁿ².

So if n1≤n2 then 2ⁿ¹≤2ⁿ². However, this requires the sets to be finite, that is, n1 and n2 can be defined.


If Y is the set of all natural numbers up to 100 and X is the set of odd natural numbers up to 100, and the injective function F(x)=(x+1)/2 maps x∈X to y∈Y, then X={1,3,5,...,99}, n1=50, and Y={1,2,3,...,100), n2=100. In this example, Y contains all the elements of X (X⊂Y) plus {51,52,53,...100}. Since n1 and n2 are finite numbers, so are |P(X)|=2⁵⁰ and |P(Y)|=2¹⁰⁰. The upper limit of 100 was arbitrary, so whatever the limit, |P(X)|<|P(Y)|. We conclude that, if Y is the set of all natural numbers, X is the set of odd natural numbers, and F(x)=(x+1)/2 maps X to Y, then |P(X)|<|P(Y)|.

In general we can say that for any injective function F, Y will consist of the sum of two sets A and B, where A={F(x), ∀x∈X} and B is the set of unmapped elements of Y. When B={}, |P(X)|=|P(Y)|, even when X and Y are infinite sets.

by Top Rated User (839k points)

In this example, Y contains all the elements of X (X⊂Y) plus {51,52,53,...100}?


I thought If X contain all the odd numbers, then Y must contain all the even numbers.

Where do you get {51,52,53,...100}?


For this assumpton,F(x)=(x+1)/2 maps X to Y, then |P(X)|<|P(Y)|. Is is not supposed to be maps Y to X if ,F(x)=(x+1)/2 for any given y we have the odd integers in X?

X is not specifically a subset of Y, although, coincidentally, it happens to be so because the example uses natural numbers as an infinite set. X={1, 3, 5, ..., 99}; Y ={1, 2, 3, ..., 100}. Only the Y subset {1, 2, 3, ..., 50} is mapped by the function, leaving {51, 52, 53, ..., 100} unmapped. The question doesn’t include the requirement X⊂Y. Have I missed something?


Related questions

0 answers
asked Jun 27, 2012 in Algebra 1 Answers by jashells Level 1 User (120 points) | 213 views
0 answers
asked 1 day ago in Other Math Topics by Thatsd12 | 10 views
1 answer
asked Mar 25 in Other Math Topics by anonymous | 47 views
0 answers
asked Nov 29, 2020 in Other Math Topics by Rapht | 178 views
1 answer
asked Dec 5, 2014 in Other Math Topics by ruth | 1.8k views
1 answer
Welcome to, where students, teachers and math enthusiasts can ask and answer any math question. Get help and answers to any math problem including algebra, trigonometry, geometry, calculus, trigonometry, fractions, solving expression, simplifying expressions and more. Get answers to math questions. Help is always 100% free!
86,303 questions
92,362 answers
23,927 users