Finite Sets Injectivity

Question

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.

Answer 1

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.

EXAMPLE

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.

Comments

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?