Prove that for each natural number n, any set with n elements has $\frac{n(n-1)}{2}$ two-element subsets

Question

Prove that for each natural number n, any set with n elements has $\frac{n(n-1)}{2}$ two-element subsets.

I'm just confused by what this is asking, I haven't learned about two-element subsets yet.

Answer 1

Some answers don't seem to be addressing the OP's concern that they don't understand what the question is asking, rather than not knowing how to proceed with the question.

The idea of the terms in the question are as follows: In mathematics, we call a collection of objects a set. You can have sets of very concrete objects, like the set of things on a table, or very mathy ones, like the set of integers between $0$ and $7$ inclusive. We would write the last one $$\{0,1,2,3,4,5,6,7\}$$ The curly brackets indicate that we have a set of the objects inside. Now, a subset A of a set $B$ is a set so that every member of $A$ is also a member of $B$. What this means is that $A$ and $B$ are collections of objects and $B$ contains every object that $A$ contains, and possibly more. A two element subset is a subset that has two things in it. If we let $B$ be the set of integers between $0$ and $7$ inclusive above, then $ \{1,2,3\}$ is a subset but not a two element subset, and $\{4,6\}$ is both a subset and has two elements, hence it is a two element subset.

So, your question is asking that if you start with a set $S$ that has $n$ things in it, how many two element subsets of $S$ are there? You can do some small examples yourself explicitly. For instance if $S$ has 1 element, then it has no two element subsets, and if $S$ has 2 elements, then $S$ has exactly one two element subset: $S$ itself. Now suppose $S$ has three elements, say $S=\{1,2,3\}$ can you list all the 2 element subsets? What about larger $n$?

Answer 2

HINT

Note that for the first element we can consider $(n-1)$ subsets: $$\{1,2\},\{1,3\},\ldots,\{1,n\}$$

for the second element we can consider $(n-2)$ subsets: $$\{2,3\},\{2,4\},\ldots,\{2,n\}$$

and so on.

Answer 3

For your first element you have $n$ choices and for each choice you have $n-1$ choices for the second one.

That makes $n(n-1) $choices but since order does not matter the actual number of subsets are $n(n-1)/2$

Answer 4

Let $S$ be a set with $n$ elements.

We can map ordered pairs from the Cartesian product $S \times S$ into subsets of $S$ as follows:

$\tag 1 (x,y) \mapsto \{x.y\} \text{ for every } x,y \in S$

The output of this function is a subset of $S$ with either one element or two elements.

With $a \ne b$, we get a subset with two elements,

$\quad (a,b) \mapsto \{a.b\}$

But we get the same subset when we switch the coordinates:

$\quad (b,a) \mapsto \{b.a\}$

So the mapping is $2:1$ when it is 'hitting' two element subsets. If $t$ is the number of subsets with two elements, this happens two times $t$.

We get a subset with one element like this:

$\quad (d,d) \mapsto \{d.d\} = \{d\}$

Here it is $1:1$, one ordered pair 'on the diagonal' for each singleton subset of $S$; this happens exactly $n$ times.

Now we know that the set $S \times S$ has $n^2$ elements. But the above analysis allows us to also count up these elements as follows:

$\tag 2 n^2 = 2 t + n \text{, where } t \text{ is the number of subsets of } S \text{ containing exactly } 2 \text{ elements}$

Solving we get

$\tag 3 t = \frac{n^2 -n}{2}$