Higher Mathematics · Class 9-10 · Chapter 1 · Sets and functions
Set laws, De Morgan, and counting.
This section is the proving part of the chapter. Nothing new gets built here; what the earlier operations obey is set out, and a shape for proving it is handed over. At the end comes counting, where a Venn diagram turns into an instrument for arithmetic.
1. The laws, and what they are called
Swapping the two sets changes nothing for union and intersection: A ∪ B = B ∪ A and A ∩ B = B ∩ A. That is the commutative law. Keep in mind that it fails for difference, where A \ B and B \ A are usually different; so the commutative law always means union and intersection.
With three sets it makes no difference where the brackets go: (A ∪ B) ∪ C = A ∪ (B ∪ C), and the same for intersection. That is the associative law, and it is why a union of three sets can be written with no brackets at all.
There are two distributive laws: A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C), and A ∪ (B ∩ C) = (A ∪ B) ∩ (A ∪ C). They look like multiplication over addition, but there is one large difference. With numbers only multiplication distributes over addition, not the other way about; with sets it works both ways. Forget that and the second law looks like a mistake.
And the two De Morgan laws, which turned themselves up in the picture in the last section: (A ∪ B)′ = A′ ∩ B′ and (A ∩ B)′ = A′ ∪ B′. Sort the eight laws under their four names.
sort thema law, then a bin
Which law is which
Pick up a law, then drop it in a bin. What changed between the two sides is what names it.
Right. Next one.
Not there. Look at what actually moved between the two sides: the order, the brackets, or the symbol?
All in place. A quick way to tell them apart: order swapped means commutative, brackets moved means associative, one symbol spreading over the other means distributive, and the complement mark moving inside and turning the symbol over means De Morgan.
Alongside these sit a few small truths that need no memorising but come up constantly in working: A ∪ ∅ = A, A ∩ ∅ = ∅, A ∪ U = U, A ∩ U = A, and A ∪ A = A ∩ A = A. Each drops out of the definitions in a line.
2. A proof means showing both directions
What does it take to prove two sets equal? The definition from an earlier section comes back as the tool: X = Y exactly when X ⊆ Y and Y ⊆ X. So every proof of a set identity has three parts: show one direction, show the other, then declare them equal.
And showing X ⊆ Y has a fixed shape too. Start with “let x ∈ X”, open out the definitions one at a time, and arrive at “therefore x ∈ Y”. Nothing is ever assumed along the way; definitions are only unpacked. See it as a picture first, then in writing.
step by steppress next
De Morgan, in a picture
First shade A ∪ B, that is anywhere in either circle. Three regions light up.
Now its complement: turn the shading inside out. (A ∪ B)′ is what lies outside both circles but inside U. Notice it is a single region.
Now begin again, separately. A′ is everything outside A, which is the B only region together with the outer one. It is hatched leaning one way.
Then B′, the A only region with the outer one, hatched leaning the other way. Now look where both hatchings fall together: only on the outer region. That is A′ ∩ B′.
The picture at step 2 and the doubly hatched region at step 4 are the same. So (A ∪ B)′ = A′ ∩ B′. That is what proving with a Venn diagram means: draw two pictures, not one.
The picture convinces, but an exam will often ask for the proof in writing. The seven steps below are out of order; tap them in sequence and build the proof.
which firsttap the steps in order
Put the proof in order: (A ∪ B)′ = A′ ∩ B′
A proof starts by taking hold of one element. Which step does that?
Yes. And then?
Not yet. Which one follows straight from the step before?
That is the proof. Notice the shape: show one direction, show the other, then declare them equal. Every set identity is proved in those three parts, with only the definitions in the middle changing. And notice that every step only unpacks a definition; nothing is ever assumed.
check yourself
One question
What does (A ∩ B′)′ simplify to?
De Morgan turns ∩ into ∪, so the sign in the middle has to change.
Right. Two steps: De Morgan gives (A ∩ B′)′ = A′ ∪ (B′)′, then the double complement cancels, (B′)′ = B. So it is A′ ∪ B. The trap is forgetting the second step and writing A′ ∪ B′.
The complements are the wrong way round. The mark lands on A, and the one on B cancels.
The outer complement has not been applied at all. It acts on both sides.
3. Counting counts some of them twice
How many are in the union of two sets? Adding n(A) and n(B) seems enough, and it is not. Those in the overlap are in both sets, so adding counts them twice. Taking them off once puts it right.
n(A ∪ B) = n(A) + n(B) - n(A ∩ B)
Change the numbers below. Watch in particular how moving the size of the overlap moves everything else, and try putting in numbers that cannot go together.
calculatorchange the numbers
Take off what was counted twice
check yourself
Another question
Of 40 students in a class, 25 play cricket, 18 play football and 7 play both. How many play neither?
Close, but one short. 25 + 18 - 7 = 36, and 40 - 36 = 4.
Right. At least one sport is played by 25 + 18 - 7 = 36. Out of 40 that leaves 40 - 36 = 4 playing neither. Without taking the 7 off you would get 43, which is more than the class holds.
That is a 40 - 25 - 7 sort of sum. The 18 who play football have been left out.
That is 40 - 25, the ones who do not play cricket. But many of them play football.
4. Reading numbers off a three set diagram
With three sets the formula gets longer while the reasoning stays the same. Add the three, take off the three pairwise overlaps, then give the triple overlap back once. It has to come back because taking off the three pairs removes the middle region three times, and it was only added three times to begin with.
In practice, though, filling numbers into the picture is safer than remembering the formula, and it has one rule: always start in the middle. Put the triple overlap in first, then the pairs, then the regions on their own, and the outside last. That has been done for the problem below; tap each number and see where it came from.
A class has 30 students. The maths olympiad is taken by 18, physics by 15, chemistry by 12. Both maths and physics are taken by 8, physics and chemistry by 6, maths and chemistry by 7, and all three by 4.
numberstap a number
Reading the numbers off the picture
All three: 4. This region is the centre of the whole calculation, and where you have to start. It sits inside all of n(G ∩ P), n(P ∩ R) and n(G ∩ R), which is why the formula takes it off three times and gives it back once.
Maths and physics but not chemistry: 4. Of the 8 in n(G ∩ P), four take chemistry too, so 8 - 4 = 4. Keep hold of this: n(G ∩ P) does not mean “exactly those two”; the ones taking all three are inside it.
Maths and chemistry but not physics: 3. 7 - 4 = 3, by the same reasoning.
Physics and chemistry but not maths: 2. 6 - 4 = 2.
Maths only: 7. Taking the two pairwise overlaps (8 and 7) off 18 removes the triple overlap twice, so the 4 has to come back: 18 - 8 - 7 + 4 = 7.
Physics only: 5. 15 - 8 - 6 + 4 = 5.
Chemistry only: 3. 12 - 6 - 7 + 4 = 3.
None of the three: 2. At least one is taken by 7 + 5 + 3 + 4 + 2 + 3 + 4 = 28, out of 30. So 30 - 28 = 2 take none at all. They are outside the circles but inside the rectangle.
All eight regions seen. Add them: 7 + 5 + 3 + 4 + 2 + 3 + 4 + 2 = 30, exactly n(U). The formula agrees: 18 + 15 + 12 - 8 - 6 - 7 + 4 = 28, with 2 outside.
The mistake in questions like this nearly always lands in one place: reading n(G ∩ P) = 8 as “maths and physics only”. The picture has 4 in that region while the question gave 8; two different numbers for two different things. The last question is about a trap of another kind.
check yourself
Last question
Can n(A) = 20, n(B) = 15 and A ⊆ B all hold at once?
If A ⊆ B the union is B itself, not 35. But the real trouble comes earlier: the three facts cannot hold together.
If A ⊆ B the intersection is A itself, so n(A ∩ B) would be 20. Which is exactly what shows the numbers do not fit.
Right. A ⊆ B means every member of A is in B, so B must hold at least 20. It was given as 15. Questions are sometimes set with numbers that cannot fit, so check them against each other before starting any working.
Knowing the universal set would not help. A big box does not fit inside a smaller one.
The lines from this note you will need for writing proofs and checking sums are cut onto the cards below.
cut from the notetap to turn over
Four cards
frontWhat is the shape of a proof that two sets are equal?
backShow X ⊆ Y, show Y ⊆ X, then declare them equal. Three parts, always.
frontWrite the two De Morgan laws.
back(A ∪ B)′ = A′ ∩ B′ and (A ∩ B)′ = A′ ∪ B′. The complement goes in, the symbol turns over.
frontWhy is there a subtraction in the formula for n(A ∪ B)?
backThe overlap is in both sets, so adding counts it twice. It has to come off once.
frontWhere do you start filling numbers into a Venn diagram?
backFrom the middle. The triple overlap first, then the pairs, then the single regions, and the outside last.