Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Suppose that $A \subseteq \mathbb N _{2n-1}$ and |$A$| = $n$. Prove that $\exists m \in A$ such that $m \le n.$

So A is a set that contains $n$ elements, and it is a subset of the set {$0, 1, 2, ... , 2n-1$}. I think I am supposed to prove it by contradiction, so I need to show that $ \forall m \in A, n > m$ is a contradiction, but I have no idea how to do that.

I am confused about the relationship between the cardinality of $A$ being $n$ and $A$ being a subset of the set {$0, 1, 2, ... , 2n-1$}. This means $A$ has $n$ elements, but it doesn't mean $n$ is an element of $A,$ right? Is it just saying that $A$ is a subset of a set containing twice the number of elements of $A$, minus 1? I don't see any way to use that information in order to show that $n > m$ is a contradiction. Can anyone give me a hint please?

share|improve this question
    
Hint: in $\mathbf N_{2n - 1}$, there are only $n - 1$ integers which are strictly greater than $n$. –  user25784 Nov 4 '12 at 18:45
add comment

1 Answer

Even if you take $A$ to be the $n$ greatest elements of $\{0,1,2,...,2n-1\}$, the smallest element of $A$ would be $n\leq n$. Then, show that every other subset $A$ must contain a smaller element so the conclusion still holds.

share|improve this answer
    
"the smallest element of A would be n−1" Sorry for being dense, but where are you getting that from? –  user1356910 Nov 4 '12 at 19:15
    
If it was the highest element, we would have 2n-1 as the least element, if it was the two highest elements, we would have 2n-2 as the least element. In general, if we had the n highest elements, then we would have 2n-n=n as the smallest element. –  Jebruho Nov 4 '12 at 19:32
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.