Considered the power set $\mathcal{P}(\{ 1,...,n \})$ with the following relation. The set $A$ is said to be dominated by the set $B$ iff there is a $k$ such that $|\{ 1,...,k \} \cap A| < |\{ 1,...,k \} \cap B|$ and, for all $l<k$, we have $|\{ 1,...,l \} \cap A| = |\{ 1,...,l \} \cap B|$. Define $A \leq B$ iff $A = B$ or $A$ is dominated by $B$.
How do I prove that it is an ordered set?
Somebody help me please.
Notice that, if $$|\{1,\ldots,k\} \cap A| < |\{1,\ldots,k\} \cap B|,$$ while $$|\{1,\ldots,l\} \cap A| = |\{1,\ldots,l\} \cap B|,$$ for $l<k$, then $k \in B \setminus A$.
Let us now prove that the relation is reflexive, anti-symmetric, and transitive.
Reflexivity is trivial, since $A=A$ for every subset $A$ of $\{ 1,\ldots,n \}$.
For anti-symmetry, suppose $A \leq B$ and $B \leq A$.
I'll leave the trivial case in which $A=B$, and show that if $A< B$ and $B < A$ then we get a contradiction.
So suppose that $$|\{1,\ldots,k_1\} \cap A| < |\{1,\ldots,k_1\} \cap B|,$$ while $$|\{1,\ldots,l\} \cap A| = |\{1,\ldots,l\} \cap B|,$$ for $l < k_1$, and that $$|\{1,\ldots,k_2\} \cap B| < |\{1,\ldots,k_2\} \cap A|,$$ while $$|\{1,\ldots,l\} \cap A| = |\{1,\ldots,l\} \cap B|,$$ for $l < k_2$.
If $k_1 < k_2$ then, in particular, $$|\{1,\ldots,k_1\} \cap A| = |\{1,\ldots,k_1\} \cap B|,$$ a contradiction.
A similar contradiction is obtained if we suppose that $k_1 > k_2$, and if $k_1=k_2$, then the contradiction follows from $k_1 \in B\setminus A$ and $k_2 \in A \setminus B$.
Hence $A=B$.
For transitivity, suppose $A \leq B \leq C$. Leaving out the immediate cases where $A=B$ or $B=C$, we get $A<B<C$, and for some $k_1,k_2$, $$|\{1,\ldots,k_1\} \cap A| < |\{1,\ldots,k_1\} \cap B|,$$ while $$|\{1,\ldots,l\} \cap A| = |\{1,\ldots,l\} \cap B|,$$ for $l < k_1$, and $$|\{1,\ldots,k_2\} \cap B| < |\{1,\ldots,k_2\} \cap C|,$$ while $$|\{1,\ldots,l\} \cap B| = |\{1,\ldots,l\} \cap C|,$$ for $l < k_2$. Since $k_1 \in B$ and $k_2 \in C\setminus B$, we get $k_1 \neq k_2$.
If $k_1 < k_2$, then for $l < k_1$, $$|\{1,\ldots,l\} \cap A| = |\{1,\ldots,l\} \cap B| = |\{1,\ldots,l\} \cap C|,$$ while $$|\{1,\ldots,k_1\} \cap A| < |\{1,\ldots,k_1\} \cap B| = |\{1,\ldots,k_1\} \cap C|.$$ If $k_2 < k_1$, then for $l < k_2$, $$|\{1,\ldots,l\} \cap A| = |\{1,\ldots,l\} \cap B| = |\{1,\ldots,l\} \cap C|,$$ while $$|\{1,\ldots,k_2\} \cap A| = |\{1,\ldots,k_2\} \cap B| < |\{1,\ldots,k_1\} \cap C|.$$ Therefore $A \leq C$.