# More Homework Help

• Oct 12th 2009, 03:22 PM
minkyboodle
More Homework Help
Let C be the set of cities in the US with populations greater than 200,000 and let L be the relation on C defined by xLy (i.e., (x,y) are members of L) if and only if the population of x is not greater than the population of y. According to one website, |C|=107. Assume, we are looking at the official 2000 census figures

(a) Is the following statement true or false? explain :
There exists an n such that for every x then xLn

(b) Prove or disprove that L is a partial order. There is one sublte issue here; use common sense in dealing with it.
• Oct 13th 2009, 02:09 AM
Defunkt
Quote:

Originally Posted by minkyboodle
Let C be the set of cities in the US with populations greater than 200,000 and let L be the relation on C defined by xLy (i.e., (x,y) are members of L) if and only if the population of x is not greater than the population of y. According to one website, |C|=107. Assume, we are looking at the official 2000 census figures

(a) Is the following statement true or false? explain :
There exists an n such that for every x then xLn

(b) Prove or disprove that L is a partial order. There is one sublte issue here; use common sense in dealing with it.

(a) $\displaystyle \exists n : xLn \ \forall x \in C$ means that there is one city with the largest population. Since C is a finite set, this must be true.

(b) Reflexiveness: $\displaystyle \forall x \in C, xLx$ since the population of any city is certainly not greater than its own population.

Anti-symmetry: Assume that there exist $\displaystyle x,y \in C : x \leq y, y \leq x$. Then, the population of town x is not greater than the population of town y, but the population of town y is also not greater than the population of town x. If you may, this gives us that $\displaystyle Pop(x) \leq Pop(y), Pop(y) \leq Pop(x) \Rightarrow Pop(x) = Pop(y)$, so the populations of x and y are equal, however this certainly doesn't guarantee us that they are the same city, seeing as two cities may have the same population. Hence, there is no anti-symmetry.

Can you do transitivity?