Let $R$ be a symmetric relation on set $S$ of length $n$. Let $b \in S$ and let $\beta_b = \{a | b R a \wedge a \neq b\}$. Let $k(b)=|\beta_b|$ be the cardinality of $b$.
Theorem:
$\exists a,b \in S : k(a) = k(b)$
Proof:
Assume there doesn't exist such a and b. Then all our elements in $S$ has different cardinalities. We have $n$ elements so we need $n$ different cardinalities. Maximum cardinality possible is $n-1$. So our cardinalities range from $0$ to $n-1$. If there is element $y$ whose cardinality $n-1$ then $\exists_{n-1} a : y R a$, i.e. all other elements than $y$ has cardinality $\geq 1$. Hence there is no element with cardinality $0$. And then we don't have $n$ different cardinalities, contradiction. The theorem holds $\qed$
No comments:
Post a Comment