0
$\begingroup$

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?

  • 0
    Hint: in $\mathbf N_{2n - 1}$, there are only $n - 1$ integers which are strictly greater than $n$.2012-11-04

1 Answers 1

1

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.

  • 0
    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.2012-11-04