Unit 27: Collections

A set is a collection

A set is just a collection of things, written in curly brackets: {2, 4, 6, 8}.

Two rules make sets simpler than lists. Order does not matter — {1, 2} and {2, 1} are the same set. And repeats do not count — {1, 1, 2} is only {1, 2}.

The number of things in a set is its size.

Inside and underneath

We say 4 is a member of {2, 4, 6}.

A set entirely contained in another is a subset: {2, 4} is a subset of {2, 4, 6}.

And the empty set {} contains nothing at all. It is a subset of absolutely everything, which sounds like a trick and is not.

Union and intersection

The union of two sets is everything in either one — {1, 2} ∪ {2, 3} is {1, 2, 3}. The 2 is only written once.

The intersection is only what they share — {1, 2} ∩ {2, 3} is {2}.

And a Venn diagram draws them as two overlapping circles, so you can see both at a glance.

Do not count the overlap twice

In a class of 30, 18 play football and 15 play chess. Adding those gives 33 — more than the class.

The people who do both were counted twice. So:

size of union = size of A + size of B - size of overlap

Here the overlap must be 3, since 18 + 15 - 3 = 30.

Two ways to say which things

You can list a set: {2, 4, 6, 8}.

Or you can describe it: "the even numbers from 2 to 8". Same set.

Listing is clear but only works when the set is small. Describing works for infinite sets too — "all the whole numbers" cannot be listed, but it can be said in three words.

The families of numbers have names

The number families from unit 8 are sets, and they get short names.

The counting numbers, the integers, the rationals, the reals.

Each sits inside the next, so the integers are a subset of the rationals, which are a subset of the reals. A whole unit of number theory, restated in one sentence of set language.

Seven regions instead of three

Three overlapping circles cut the picture into seven regions: three for one set only, three for each pair, and one in the very middle for all three.

The safe way to fill it in is from the middle outwards. Put the all-three number in first, then work out each pair by subtracting the middle, then each single by subtracting everything inside it.

Starting from the outside almost always goes wrong.

Inclusion and exclusion, three at a time

With three sets the formula grows: add the three singles, take off the three pairs, then add the middle back.

Why add it back? It was counted three times by the singles and taken off three times by the pairs, leaving nothing. So it needs putting back once.

Add, subtract, add. The pattern continues for four sets and beyond.

Outcomes make a set

Everything that could happen forms a set — the sample space. Rolling a die, that is {1, 2, 3, 4, 5, 6}.

An event is a subset of it. "Even" is {2, 4, 6}.

So probability is the size of the subset over the size of the whole set. Unit 26 was set theory in disguise all along.

Or is union, and is intersection

"Even or over 4" is a union: {2, 4, 6} joined with {5, 6} gives {2, 4, 5, 6} — four outcomes, not five, because 6 appears in both.

"Even and over 4" is an intersection: just {6}.

That is exactly why the "or" rule needed the overlap subtracted in unit 26. Same idea, different vocabulary.

In or out, for each thing

To build a subset of {a, b, c}, decide for each item: in or out. Three decisions, two ways each, so 2^3 = 8 subsets.

That includes the empty set (everything out) and the whole set (everything in).

So a set of n things has 2^n subsets. It is the multiplication principle from unit 25, applied to a yes-or-no question.

Two answers to the same question

Count the subsets of a 4-item set two ways.

In or out: 2^4 = 16.
By size: choose(4,0) + choose(4,1) + choose(4,2) + choose(4,3) + choose(4,4) = 1 + 4 + 6 + 4 + 1 = 16.

Both give 16, so a whole row of Pascal’s triangle must add to a power of 2 — proved by counting the same thing twice, exactly as unit 20 suggested.

Everything outside

The complement of a set is everything that is *not* in it, out of whatever you are counting from.

If 30 children were asked and 22 like tea, then 8 do not.

Often the complement is far easier to count — the same trick as "at least one" in unit 26.