Proving no bijection

[patter2809]

Q. Either construct a bijection from X to Y, or show why one cannot exist. X = set of positive integers, Y = set of positive integers for which all the digits (base 10) are different.

A. If we show that |X| > |Y|, we can say that X cannot be injective by the pigeonhole principle and therefore certainly not bijective.

But, how do I show this? They are both infinite sets.

 

[HallsofIvy]

Q. Either construct a bijection from X to Y, or show why one cannot exist. X = set of positive integers, Y = set of positive integers for which all the digits (base 10) are different.

A. If we show that |X| > |Y|, we can say that X cannot be injective by the pigeonhole principle and therefore certainly not bijective.

But, how do I show this? They are both infinite sets.

You can't show it, |X|> |Y| is obviously not true. They are both infinite subsets of N and every infinite subset of N has cardinality \(\displaystyle \aleph_0\)

 

[patter2809]

So, how can I prove such a bijection?

 

[JeffM]

Q. Either construct a bijection from X to Y, or show why one cannot exist. X = set of positive integers, Y = set of positive integers for which all the digits (base 10) are different.

A. If we show that |X| > |Y|, we can say that X cannot be injective by the pigeonhole principle and therefore certainly not bijective.

But, how do I show this? They are both infinite sets.

I am obviously missing something here because both you and Halls are interpreting the question differently from me.

Is not the largest possible integer in set Y = 9,876,543,210? Any positive integer greater than 9,876,543,210 must repeat a digit already used and so is outside set Y. Thus the number of elements in set Y is not infinite. In fact, it is 9,876,543,210.

As I say, this answer may just show my confusion and be unhelpful. If so, I apologize.

 

[daon2]

Jeff, your idea is correct but you are including numbers like 11, 121, etc in your count (I think). My initial thought is the answer is 9*(1! + 2! + 3! + ... + 9!)+1 but it might be wrong and isn't important.

OP you have the right idea, let f be any function from X to Y. |Y| is finite as Jeff points out, of size m. Choosing m+1 elements in X results in a repeated image.

as i suspected i counted wrong (picked from too small a set), more along the lines of \(\displaystyle 9\sum_{i=1}^9{9 \choose i}(i)!+1\)

 

[JeffM]

Jeff, your idea is correct but you are including numbers like 11, 121, etc in your count (I think). My initial thought is the answer is 9*(1! + 2! + 3! + ... + 9!)+1 but it might be wrong and isn't important.

OP you have the right idea, let f be any function from X to Y. |Y| is finite as Jeff points out, of size m. Choosing m+1 elements in X results in a repeated image.

as i suspected i counted wrong (picked from too small a set), more along the lines of \(\displaystyle 9\sum_{i=1}^9{9 \choose i}(i)!+1\)

daon

You are right: I overcounted. However, the fundamental point is that the set is finite (if I have understood the problem).