Proving Pigeonhole Principle in Set Theory

[houseurmusic]

Been working on this for 2 days and have gotten no where. Maybe someone out there can show me the light

U = {1, 2, 3, ... , n, ..., 2n} for some natural number n
Let P be a subset of U such that |P| = n + 1
show that there exists x, y in P where x not equal y such that x divides y or y divides x.

 

[JSuarez]

This one's a classic, and it's not obvious. Notice that:

(1) U has n odd elements; these will be the pigeonholes.

(2) The pigeons will be the elements of P.

(3) Each "pigeon" [tex]k \in P[/tex] may be written as [tex]k = 2^{e}m[/tex], where m is odd.

Now, there will be a pigeonhole, with at least how many pigeons?

 

[houseurmusic]

That was helpful, thank you.

The way I approached the problem and I am not sure if this is correct...

I split U into 2 subsets. An even subset and an odd subset.
I said that set P must contain at least 1 element from the even set by the pigeon hole principle. I also used these to facts which are easy to prove

-1- For any even number x and some odd number y. x=(2^C)(y) C is a natural number > 1
-2- If there is an even number x that shares the same odd multiple (excluding 1) as another even number y then x|y (x divides y) or y|x.

When choosing the even number(s) for set P we can make these 2 choices:

case 1: We choose an even number x that shares no odd multiple with another even number we have chosen before.

case 2: The even number x shares the same odd multiple as another even number y which we have already chosen from before.

Note that after we are done choosing set P if P contains 1 then we are done.

If we ever choose a x that falls under case 2 we are done by -2- of our above facts.

(This is where I it gets a little messy)

Then all that is left to consider is if all our choices of even number(s) fall under case 1.
By fact -1- any even number x is multiple of an odd number y(excluding 1). In other words our set P would have to have a one to one correspondence of odd to even numbers. But that's impossible because we have must have 1 more odd numbers then even numbers or vice versa.
So P must contain a x and a y such that x|y or y|x which was to be shown. QED

That look right?

 

[JSuarez]

You are overcomplicating: notice that, after you have defined the set of "holes" as the one who has the odd elements of U and the the "pigeons" has your set P, then there will be at least two of them who are multiples of the same odd element. What does this tells you about their divisibility?