Question

Let X be a finite set with |X| > 1. What is the difference between P1 = X ×X and P2 = {S ∈ P(X) | |S| = 2}? Which set, P1 or P2, has more elements?

Answer 1

Answer on Question #75205, Math / Discrete Mathematics.

Task. Let $X$ be a finite set with $|X| > 1$. What is the difference between $P_1 = X \times X$ and $P_2 = \{S \in P(X) : |S| = 2\}$? Which set, $P_1$ or $P_2$, has more elements?

Solution. So,

$$P_1 = X \times X = \{(a, b) : a, b \in X\},$$ $$P_2 = \{S \in P(X) : |S| = 2\} = \{\{a, b\} : a, b \in X, a \neq b\}.$$

Example,

if $a \in X$ then $(a, a) \in P_1$ but $\{a, a\} \notin P_2$;

if $a, b \in X$, then $(a, b), (b, a) \in P_1$ (two elements) and $\{a, b\} = \{b, a\} \in P_2$ (one element).

Therefore, the set $P_1$ has more elements than the set $P_2$.

More detail, let $|X| = n$. So,

$$|P_2| = \binom{n}{2} = \frac{n!}{2! \cdot (n - 2)!} = \frac{n(n - 1)}{2} \quad \text{and} \quad |P_1| = |X \times X| = |X|^2 = n^2.$$

Then $|P_1| - |P_2| = n^2 - \frac{n(n - 1)}{2} = \frac{2n^2 - n(n - 1)}{2} = \frac{2n^2 - n^2 + n}{2} = \frac{n^2 + n}{2} = \frac{n(n + 1)}{2}$.