# Set

A set is a collection of objects called elements. Sets are the subject of set theory. Two sets are the same if they contain the same elements, regardless of the order they are in. Sets are written in set notation, such as {1,2} indicating the set containing the elements 1 and 2. This is the same as the set {2,1} because order does not matter when comparing sets.

Also, repetition of elements is irrelevant, so the set {1,2,2} is the same as the set {1,2}.

An important concept in set theory is cardinality. In the case of finite sets, this is simply the number of elements of the set. So {1,2} has a cardinality of 2. However, the theory is more complicated in the case of infinite sets.

It was thought that an informal concept of sets (Naive set theory) was sufficient, however Russell's Paradox shows that this can lead to a contradiction if sets are allowed to contain themselves. Modern set theory is more formal, and disallows such paradoxical sets.

## Examples

Let S be the set {a,b,d,f,h}, and let T be the set {d,e,f}

• The cardinality of S is 5.
• The cardinality of T is 3.
• The intersection, $S \cap T$ is the set {d,f}. This is because d and f are the only two elements in both S and T.
• The union, $S \cup T$ is the set {a,b,d,e,f,h}. These six elements are in the union because they belong to S, to T, or to both S and T.
• The set-theoretic difference $S \setminus T$ (alternative notation: ST) is the set {a,b,h} containing all the elements in S that are not in T.
• The power set of T, $\mathcal{P}(T)$, consists of all subsets of T including the empty set and T itself. One can check that $\mathcal{P}(T) = \{\emptyset, \{d\}, \{e\}, \{f\}, \{d, e\}, \{d, f\}, \{e, f\}, \{d, e, f\}\}$. Exercise: How many elements are in $\mathcal{P}(S)$?

Let A be the set of all prime numbers, and let B be the set of all even numbers. What is the intersection, $A \cap B$? It is a set containing one element, 2. Since any even number greater than 2 has two as a proper factor, no even number aside from 2 belongs to A. However, 2 is a prime number. Thus, the intersection is {2}.

Let C be the set of all positive integers that are multiples of 3, and let D be the set of all positive integers that have a remainder of 1 when divided by 3. The intersection, $C \cap D$, is the empty set, because no positive integer that is a multiple of 3 will have remainder 1 when divided by 3. However, if we take B to be the set of even numbers, as before, then $C \cap B$ is not empty. Exercise: What are the elements of $C \cap B$?

## Examples of sets in the real world

There is the set of unborn children who were aborted, about which striking conclusions can be drawn. Given the large and diverse number of elements of this set, it would likely include many who could surpass existing athletic and intellectual achievements. Indeed, many of the world records and Nobel Prize achievements recognized today would have been outdone by members of this set.

Another striking example is the how traditional marriage provides a greater set than otherwise: the union of $A = \{a, b, c, d\}\,$ and $B = \{a, b, c, e\}\,$ is merely $\{a, b, c, d, e\}\,$, while the union of a man, $M = \{a, b, c, d\}\,$ and a woman $W = \{e, f, g, h\}\,$, is $\{a, b, c, d, e, f, g, h\}\,$, which is a broader and more diverse set.

Define "A" as the set of all false assertions, and "B" as the set of all the Bible passages. Since there are no Counterexamples to the Bible, the intersection between set A and set B is the empty set. On the other hand, if "C" is set of evolutionary assertions, then the intersection between set A and set C is not empty because it contains Counterexamples to Evolution.

## Application -- Combinatorics

Sets, and their cardinalities, are used in some very important aspects of combinatorics, that is, the study of combinations. Let

$X = \{a,b,c\}\,$ and $Y = \{p,q,r\}\,$.

The cardinalities of both are $\|X\| = \|Y\| = 3$.

Let $S = \{\{x,y\}\ |\ x \in X\,\textrm{ and }\,y \in Y\}$. The vertical bar means "such that", and the epsilon-like symbol $\in$ means "is an element of". So this means that S is the collection of sets[1] which are pairs x and y such that x is in X and y is in Y.

We can enumerate this.

$S = \{\{a,p\}, \{a,q\}, \{a,r\}, \{b,p\}, \{b,q\}, \{b,r\}, \{c,p\}, \{c,q\}, \{c,r\}\}\,$.

Its cardinality is $\|S\| = 9$.

Now try a harder example, based on the same two sets. Let

$G = \{F\ |\ F \subset (X \cup Y)\,\textrm{ and }\,\|F\|=2\}$.

Now $X \cup Y = \{a,b,c,p,q,r\}$, so

$\|X \cup Y\| = 6$.

The problem of finding the number of subsets of a set that has some particular cardinality is the combination choosing problem, and shows up in many areas of probability and statistics. In this case, it's the problem of choosing 2 elements out of a set of 6 elements. The number of such choices is often written ${}_6C_2\,$ or $6 \choose 2$, and is often pronounced "six choose two". These numbers are also called the binomial coefficients because they appear as coefficients in the expansion of $(x+y)^n\,$. In this case, $6 \choose 2$ is the coefficient of $x^2y^4\,$ in $(x+y)^6\,$.

There is a simple formula for $n \choose k$. It is

${n \choose k} = \frac{n!}{k! (n-k)!}$.

In the case of the set $G = \{F\ |\ F \subset \{a,b,c,p,q,r\}\,\textrm{ and }\,\|F\|=2\}$, the set is

$G = \{\{a,b\}, \{a,c\}, \{a,p\}, \{a,q\}, \{a,r\}, \{b,c\}, \{b,p\}, \{b,q\}, \{b,r\}, \{c,p\}, \{c,q\}, \{c,r\}, \{p,q\}, \{p,r\}, \{q,r\}\}\,$.

Its cardinality is 15.

We can check that ${6 \choose 2} = \frac{6!}{2! (6-2)!} = \frac{720}{2 \cdot 24} = 15$.

## References

1. Mathematicians don't like to use the phrase "set of sets", since this can lead to some unpleasant paradoxes. So they say "collection of sets." A "collection" is really just a set.