It's a problem from a test which I'm having hard time to understand. A partial ordered set A is given, and |A| is greater than MAX{2, |<|}. ( |A|> MAX{2, |<|} ). When |<|, as i understand it, is the cardinality of asymmetric and non-reflexive relations on A. The problem is to prove that A, is not linear ordered.
I tried to figure the cardinality of |<|, from combinatoric aspects and found out (I might be wrong here), that the cardinality is 2^((1/2 (|A|^2−|A|)) ), When the number of ways to choose pairs without order consideration ((a,b) and (b,a) are considered the same due to asymmetric), is (|A| choose 2). So, the number of relations which are formed from those pairs is 2^(|A| choose 2).
Well the problem is that for every |A|>= 3, |A| < |<|, it also occurs when A is an infinite set.
An other shot, trying to use the characteristics of a linear ordered set. To assure reflexivity there are |A| pairs (a,a). For a finite set, for every element to relate to all others we need the pairs (a1,ai) when ai in A, (a2,ai\a1) ans so on. Which leads to arithmetic series means (|A|^2 +|A|)/2 elements. For infinite sets we get |A|^2 =|A| pairs. So if |A|> |<| when |<| cardinality is generally 2^|A| leads to a conclusion that |A| is too large to be linearly ordered?
I've been struggling with it for a while, and I would really appreciate your help.
HINT: You’re tangling yourself up in irrelevancies. You’re given a specific strict partial order $<$ on $A$; that’s the only one that you need to consider, and you’re to show that if $|A|>\max\left\{2,|{<}|\right\}$, then $<$ is not a (strict) linear order. Start by supposing that $<$ is a strict linear order on $A$; your goal will be to get a contradiction. In that case for each $2$-element subset $\{x,y\}$ of $A$ exactly one of the pairs $\langle x,y\rangle$ and $\langle y,x\rangle$ is in $<$, so
$$|{<}|=\binom{|A|}2\;.$$
We’re told that $|A|>\max\left\{2,|{<}|\right\}$, so in particular $|A|>2$, i.e., $|A|\ge 3$. Express $\binom{|A|}2$ in more elementary terms and use the fact that $|A|\ge 3$. to get your contradiction.
This argument assumes that $A$ is finite, but that’s a harmless assumption, because if $A$ is infinite, and $<$ is a strict linear order on $A$, then $|A|=|{<}|$, and we don’t have $|A|>\max\{2,|{<}|\}$ in the first place. (You should try to show that $|A|=|{<}|$ in this case. Recall that $|A|=|A\times A|$ for infinite $A$.)