501 distinct coprime integers between 1 and 1000?
$[1,1000]$ can be partitioned through the following sets: $$ S_1=\{1,2,4,8,\ldots,512\}, $$ $$ S_3=\{3,6,12,24,\ldots,768\}, $$ $$ S_5=\{5,10,20,40,\ldots,640\}, $$ $$ \ldots $$ $$ S_{499}=\{499,998\} $$ plus the singletons $S_{501},S_{503},\ldots,S_{999}$. For short, $n\in[1,1000]$ belongs to $S_{n/2^{\nu_2(n)}}$.
These are $500$ sets: if $501$ elements are picked from $[1,1000]$, at least two elements must lie in the same $S_m$. But every $S_m$ is a chain in the POset given by $a"\leq"b\;\Leftrightarrow a\mid b$, so the claim is straightforward.
I know there's already two answers, but I came up with this last night and thought I'd share as I was very happy with the solution:
Suppose the proposition is false, i.e. there are sets of size 501 where for all a and b in the set, a and b non equal implies a does not divide b.
For each set satisfying this property (of which there are clearly a finite amount), we can find the smallest element in the set. Choose a set where this smallest element is maximal (i.e. there are no sets with this property where the smallest element if bigger than the smallest element in our chosen set). Call this set S, and the smallest element x.
Now we have x = 500, x = 2, or 2 < x < 500 (as if x > 500, there are not enough elements bigger than 500 between x and 1000 to find 501 numbers). If x = 500, then the set must be 500,...,1000 but clearly 500 divides 1000, a contradiction. If x = 2, then we can't have any even numbers in our set, so the only 500 numbers remaining are all odd ones, but then the set would contain 3 and 9, a contradiction.
Thus 2 < x < 500. Now does 2*x belong to our set? Clearly not, as our set satisfies the assumed property (as x divides 2*x and we assume there are no a, b distinct such that a divides b). But as x < 500, 2*x < 1000. Furthermore, 2*x does not divide any elements of our set as if it did, x would also divide that element. Lastly, no element in our set divides 2*x besides x, as x is the smallest element in the set and so if say y divides 2*x, i.e. n*y = 2*x, it implies n is less than 2 and so not an integer.
This means we can replace x by 2*x and our set still has all the required properties. But then we have a set with a bigger smallest element and we chose our set maximal, which is a contradiction.
Thus no set's with this property exist, and we are done.