Sets and Tuples

To learn the language of sets and tuples:

• You will be able to define sets with braces, (\(\{\}\)), tuples with parentheses, \(((\,))\), sets of tuples with Cartesian product, \((\times)\), and sets of strings with concatenation.
• You will be able to name common sets (including the natural numbers \((\mathbb{N})\), integers \((\mathbb{Z})\), and the empty set \((\emptyset=\{\})\)), and use notation for testing element inclusion in a set \(( \in )\), and its negation \((\notin)\), and for testing whether a set is a subset of another, \((\subseteq )\).
• You will be able to count elements in sets using the sum and product rules
• You will meet several extensions (to lists, sequences, vectors, matrices, strings, and languages) that are common abstractions in computer science. These are just sets and tuples with special operations. (In fact, even tuples can be reduced to sets -Extension 3.14 in the text.)

A set is a finite set if it has a finite number of elements.

Any set that is not finite is an infinite set.

Let \(A\) be a finite set. The number of different elements in \(A\) is called its cardinality.

The cardinality of a finite set is denoted \(|A|\).

A set is a finite set if it has a finite number of elements.

Any set that is not finite is an infinite set.

Let \(A\) be a finite set. The number of different elements in \(A\) is called its cardinality.

The cardinality of a finite set is denoted \(|A|\).

Examples

\(\{1,2,3\}\) is a finite set. Its cardinality is \(3\).

A set is a finite set if it has a finite number of elements.

Any set that is not finite is an infinite set.

Let \(A\) be a finite set. The number of different elements in \(A\) is called its cardinality.

The cardinality of a finite set is denoted \(|A|\).

Examples

\(\{1,2,3\}\) is a finite set. Its cardinality is \(3\).

“all multiples of 7” is an infinite set. Cardinality here is a little more complicated… We will get back to that!

Let \(A = \{\)“apples”, “bananas”, “oranges”\(\}\)

“apples” \(\in A\)

“blueberries” \(\notin A\)

\(A \cap B\) is the set of elements that are both in \(A\) and in \(B\).

Example

\(A = \{\)Apples, Bananas\(\}\)
\(B= \{\)Bananas, Oranges\(\}\)
\(A \cap B =\) {Bananas}

• Note how this ties into logic… \(x \in A \cap B\) iff \(x \in A \land x \in B\)

\(A \cup B\) is the set of elements that are in either \(A\) or \(B\).

Example

\(A = \{\)Apples, Bananas\(\}\)
\(B= \{\)Bananas, Oranges\(\}\)
\(A \cup B =\) {Apples, Bananas, Oranges}

• Note how this ties into logic… \(x \in A \cup B\) iff \(x \in A \lor x \in B\)

• There are some standard symbols that represent specific sets you will see:
• The set of Natural Numbers \(\mathbb{N}\) is the set of all whole numbers \(\geq 0\), \(\{0,1,2,3,4,\ldots\}\).*
• The set of Integers \(\mathbb{Z}\) is the set of all whole numbers, \(\{\ldots, -3, -2, -1, 0, 1, 2, 3, \ldots\}\).
• The set of Rational Numbers \(\mathbb{Q}\) are numbers that can be represented as a quotient of whole numbers, \(\{\frac{p}{q} \mid p,q \in \mathbb{Z}\}\)
• The set of Real Numbers \(\mathbb{R}\) is all real numbers.

A \(k\)-tuple is an ordered sequence of \(k\) elements, which we write down in parentheses, \((a_1,a_2,\ldots,a_k)\).

The most common tuple seen in math is the coordinate pair \((x,y)\) on a graph.

A 2-tuple is commonly called an ordered pair.

Two tuples are equal if and only if all of their corresponding elements are equal. \((a_1,a_2,\ldots,a_k)\) iff for all \(i\in[1,\ldots,k]\) we have \(a_i=b_i\).

• You have a set of six different math books, five different philosophy books, and three different religion books. How many books do you have?
• The sum rule says, “Add them up. \(6 + 5 + 3 = 14\).”

• You have a set of 6 different math books, 5 different philosophy books, and 3 different religion books. We want to know the number of ways to arrange three of the 14 books on the shelf and get one of each type.
• Let’s break this down…
• Let’s say you just want three books, one of each type, from the shelf. How many possible combinations are there?
• Our product rule tells us there are \(6 \cdot 5 \cdot 3\) possible combinations.
• Let’s say you just want to know how many times you can arrange a set of \(3\) books, regardless of type. This is the same as counting how many permutations there are of a set of size \(3\), so the answer is \(3!\).
• Now we can combine these two answers: \(3! \cdot 6 \cdot 5 \cdot 3\)

• Now let’s say you want to know how many different ways you can arrange your \(14\) books. That’s pretty straightforward. You have \(14!\) possible permutations of your set of books.
• Say you just wanted to know how many ways you can order any three of those fourteen books. We just stop our factorial early. \(14 \cdot 13 \cdot 12\).
• There’s actually a way we can mathematically express this. It can be written as \(\frac{14!}{(14-3)!}\).

Let’s draw out why this works…

• Now let’s say you want to know how many different ways you can arrange your \(14\) books. That’s pretty straightforward. You have \(14!\) possible permutations of your set of books.
• Say you just wanted to know how many ways you can order any three of those fourteen books. We just stop our factorial early. \(14 \cdot 13 \cdot 12\).
• There’s actually a way we can mathematically express this. It can be written as \(\frac{14!}{(14-3)!}\).
• If you want to stop \(n\) factorial after \(k\) terms (you can call this a \(k\)-permutation), you can express this as \(\frac{n!}{(n-k)!}\).

A \(k\)-combination is a set with \(k\) elements chosen from a set of \(n\) possible items with no repeats.

(Since these are sets, order does not matter!)

Example

Compute all \(2\)-combinations of \(\{a,b,c\}\).
\(\{a,b\},\{a,c\}, \{b,c\}\)

Permutations vs. Combinations

The \(2\)-permutations of \(\{a,b,c\}\) would be \((a,b), (b,a), (a,c), (c,a), (b,c), (c,b)\).

The number of \(k\)-combinations of a set of size \(n\) is \({n \choose k}\), read as “\(n\) choose \(k\)”.

Other ways you may see “\(n\) choose \(k\)” written:

• \(C(n,k)\)
• \(_nC_k\)
• \(COMB(n,k)\)

How to Compute n choose k

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

Why does this formula work? Some reasoning behind this by example…

• Compute the number of \(2\)-permutations of \(\{a,b,c\}\).
• We’re going to do this the long way. Let’s consider all possible sets of size 2 we can make from \(\{a,b,c\}\).
• All sets of size 2 of \(\{a,b,c\}\): \(\{a,b\},\{a,c\}, \{b,c\}\).
• Now for permutations, order matters, so we have to consider all orderings of these new sets.
• All permutations of \(\{a,b\}\): \((a,b), (b,a)\).
• All permutations of \(\{a,c\}\): \((a,c), (c,a)\).
• All permutations of \(\{b,c\}\): \((b,c), (c,b)\).

• So, the number of \(k\)-permutations is the number of all sets of size \(k\) times the number of possible permutations for one of those sets of size \(k.\)
• Notice the number of all sets of size \(k\) is the same thing as the number of \(k\)-combinations.
• And we know that the number of possible permutations for one of those sets of size \(k\) is \(k!\).
• So, the number of \(k\)-permutations is equal to the number of \(k\)-combinations times \(k!\).
• Equivalently, we can say that the number of \(k\)-combinations is equal to the number of \(k\)-permutations divided by \(k!\).
• The number of \(k\) permutations \(= \frac{n!}{(n-k)!}\)
• The number of \(k\) permutations \(= \frac{n!}{(n-k)!} \cdot \frac{1}{k!} = \frac{n!}{k!(n-k)!} = {n \choose k}\)