Mathematics for Computer Science 201-N11 • CEGEP, Montreal

Revision sheet: set theory and relations (201-N11)

Set theory looks abstract until the first test, where you discover that half the marks are lost on two symbols: $\in$ and $\subseteq$ . Writing $3\subseteq A$ is not clumsy notation, it is a sentence with no meaning.

This sheet gathers the moves that decide: telling the two levels apart, filling in a Venn diagram from the center, and disproving a property of a relation with a single well-chosen counterexample. It is written for CEGEP students taking 201-N11 in a computer science program, and the corrected exercise set on the same chapter then puts every reflex to the test.

Mark this sheet as read or add it to your favourites: a free account, no password, keeps your read sheets and favourites from one visit to the next, tells you which chapter to tackle next and lets you ask for the method or exercise you are missing. Create your space, an email is enough.

The thread of the chapter

Almost every error in the chapter comes from mixing up LEVELS: the level of elements and the level of sets, in other words membership and inclusion.

This chapter is part of 201-N11, Mathematics for Computer Science

The essentials

Two levels: elements and sets

• $x\in A$ links an ELEMENT to a set; $A\subseteq B$ links two SETS.
• $3$ and $\{3\}$ are not the same thing: the second is a set that contains the first.
• $\varnothing\subseteq A$ always, and $\varnothing\in\mathcal{P}(A)$ always; but $\varnothing\in A$ almost never.
• $|\mathcal{P}(X)|=2^{|X|}$ : each element is taken or left out, which makes two choices per element.

The set

A

contains the elements

1

2

and the set

\{3\}

: so

\{3\}\in A

and

3\notin A

The test to run before writing a symbol: is what stands on the left an element or a set? The answer picks the symbol, never the other way around.

Operations, De Morgan and counting

• De Morgan: $\overline{A\cup B}=\overline{A}\cap\overline{B}$ and $\overline{A\cap B}=\overline{A}\cup\overline{B}$ .
• Difference: $A\setminus B=A\cap\overline{B}$ , which turns any difference into an intersection.
• Inclusion-exclusion with two sets: $|A\cup B|=|A|+|B|-|A\cap B|$ .
• With three sets: subtract the three pairwise intersections, then ADD BACK the triple intersection, which was removed three times.

The blue part on the left is

\overline{A\cup B}

: outside

A

AND outside

B

\overline{A}\cap\overline{B}

. On the right,

\overline{A\cap B}

: outside the lens,

\overline{A}\cup\overline{B}

Filling in a Venn diagram ALWAYS starts with the central region, then the pairwise intersections, then the single regions: in that order, no subtraction is done blindly.

The four properties of a relation

• REFLEXIVE: all the pairs $(x,x)$ are in it. SYMMETRIC: if $(x,y)$ is in it, then so is $(y,x)$ .
• ANTISYMMETRIC: if $(x,y)$ and $(y,x)$ are both in it, then $x=y$ . TRANSITIVE: if $(x,y)$ and $(y,z)$ are in it, then so is $(x,z)$ .
• Reflexive, antisymmetric and transitive: an ORDER relation. Reflexive, symmetric and transitive: an EQUIVALENCE relation.
• A relation is described by its ordered pairs, by its Boolean matrix or by its directed graph: three ways of writing the same object.

A loop on every vertex (reflexive); every arrow has its return (symmetric); no round trip between distinct vertices (antisymmetric); every two-arrow path has its green shortcut (transitive).

A property is PROVED on every case, but DISPROVED by a single counterexample. That is what makes disproving three times faster, and it is what the marking scheme expects.

Classes, partitions and transitive closure

• The classes of an equivalence relation form a PARTITION: nonempty, pairwise disjoint, with the whole set as their union.
• Two classes are therefore equal or disjoint: they never partly overlap.
• Transitive closure: the union of all the powers $S$ , $S^{2}$ , $S^{3}$ ... A pair $(i,j)$ belongs to it if there is a PATH from $i$ to $j$ , of any length.

Modulo

3

, the set

\{0,\ldots,8\}

splits into three classes

[0]

[1]

[2]

: nonempty, disjoint, and whose union is the whole set.

On a set with $n$ elements, going up to $S^{n-1}$ is enough: a longer path would go back through a vertex already visited, adding nothing.

The mistakes that cost marks

These are the errors I correct most often in session. Each one costs marks on a paper, even when the reasoning behind it is right.

1. Writing an inclusion where membership is needed

0.5 mark per occurrence, and there are several per test

What not to write

“ $3\subseteq A$ , since $3$ is in $A$ .”

What to write

“ $3\in A$ : $3$ is an element. You would write $\{3\}\subseteq A$ to say the same thing at the level of sets.”

Why: The two symbols link objects of different kinds. One of the two is always wrong, and the grader spots it before even reading the reasoning.

2. Making the empty set belong to everything

1.5 marks, and two lines of the true-or-false table

What not to write

“ $\varnothing\in A$ for every set $A$ .”

What to write

“ $\varnothing\subseteq A$ always, and $\varnothing\in\mathcal{P}(A)$ always; but $\varnothing\in A$ only if it was explicitly put into $A$ .”

Why: The empty set is a subset of everything because it has no element that could make the inclusion fail. Belonging is something else entirely: it would have to be listed as an element.

3. Counting subsets as a square

1.5 marks, and a whole count to redo

What not to write

“ $X$ has $5$ elements, so $\mathcal{P}(X)$ has $25$ .”

What to write

“ $|\mathcal{P}(X)|=2^{5}=32$ : each element is taken or left out.”

Each element is taken or left out: three elements give

2\times 2\times 2=8

subsets, from

\varnothing

\{a,b,c\}

, and not

3^{2}=9

Why: The choice is made element by element, independently: two possibilities per element give a power of two, never a square. The check: $\mathcal{P}(\varnothing)$ has exactly one subset.

4. Adding the counts of two overlapping sets

2 marks, and a total that can exceed the number of people surveyed

What not to write

“ $65$ know Python and $45$ know Java, so $110$ know at least one of the two.”

What to write

“ $|P\cup J|=65+45-25=85$ : the $25$ who know both were counted twice.”

The

25

who know both languages are in both circles (red):

65+45

counts them twice, hence

40+25+20=85

Why: The check is immediate: a subtotal larger than the whole population is impossible. It is the first checking reflex of the chapter.

5. Filling in a Venn diagram from the outside

2 marks, and a whole diagram to redo

What not to write

“I put $65$ in the Python zone, $45$ in Java, then I adjust.”

What to write

“I start with the CENTRAL region, $10$ , then work outward: $P\cap J$ alone is $25-10=15$ , and $P$ alone is $65-25-20+10=30$ .”

The filling order: first the center (1), then the three pairwise intersections (2), finally the zones of a single set (3); each zone is deduced from the previous ones.

Why: Each outer zone is deduced from inner zones already known. Starting from the edge, every number written has to be corrected afterwards, and the corrections get tangled.

6. Mistaking antisymmetry for the absence of symmetry

2 marks, and the classification as order or equivalence collapses

What not to write

“The relation is not symmetric, so it is antisymmetric.”

What to write

“Antisymmetric means: if $(x,y)$ AND $(y,x)$ are in it, then $x=y$ . A relation can be neither.”

On the left, the two arrows between

a

and

b

: symmetric. On the right, only one: antisymmetric. The absence of the second arrow is not enough to conclude in the other direction.

Why: The two properties are not complementary. The relation $\{(1,2),(2,1),(2,3)\}$ is neither symmetric, since $(3,2)$ is missing, nor antisymmetric, since $(1,2)$ and $(2,1)$ coexist with $1\neq 2$ .

7. Proving a property by checking a single favourable case

2 marks, and the conclusion is reversed

What not to write

“ $(1,2)$ and $(2,3)$ are in $R$ , and so is $(1,3)$ , so $R$ is transitive.”

What to write

“You must check ALL the pairs that chain together; a single chain without a shortcut is enough to disprove transitivity.”

A path from

1

3

through

2

, with no direct arc: the relation is not transitive, and this drawing alone proves it.

Why: A universal property is proved on every case and disproved by a single one. Checking one favourable case proves nothing at all.

8. Believing that equivalence classes can overlap

2 marks, and the question on the partition

What not to write

“The class of $2$ and the class of $5$ have an element in common, but they remain distinct.”

What to write

“Two classes with an element in common are EQUAL: the classes form a partition.”

Why: If $z$ belongs to both classes, transitivity links every element of one to every element of the other. So no partial overlap is possible.

9. Stopping the transitive closure at paths of length two

1.5 marks, and pairs missing from the final matrix

What not to write

“I add the pairs obtained from $S^{2}$ and I am done.”

What to write

“The closure is the union of $S$ , $S^{2}$ , up to $S^{n-1}$ : a path can cross three arcs or more.”

S

links

1

2

3

4

in a chain;

S^{2}

adds

(1,3)

and

(2,4)

(orange); stopping there misses

(1,4)

, a path of three arrows (red).

Why: Adding the length-two shortcuts creates new chains, which create others. On $n$ vertices, a useful path never exceeds $n-1$ arcs, but it can reach that many.

Which method to choose

Testing the four properties of a relation

List the ordered pairs, then test in this order, trying to DISPROVE first.

If an element $x$ does not have its pair $(x,x)$ → the relation is not reflexive, and you are done

Example: on a three-element set, the pair 3-3 is missing

it is the fastest test: it is read on the diagonal of the matrix
If a pair $(x,y)$ is in it without $(y,x)$ → it is not symmetric

Example: $(1,2)$ present, $(2,1)$ absent
If two pairs $(x,y)$ and $(y,x)$ are in it with $x\neq y$ → it is not antisymmetric

Example: $(1,2)$ and $(2,1)$ with $1\neq 2$
If two pairs $(x,y)$ and $(y,z)$ are in it without $(x,z)$ → it is not transitive

Example: $(1,2)$ and $(2,3)$ without $(1,3)$
If no counterexample turns up → prove the property in the general case, starting from the hypotheses

Example: “let $(x,y)$ and $(y,z)$ be in $R$ ; then...”

The order matters: reflexivity first, because it is read at a glance on the diagonal and immediately rules out an order as well as an equivalence.

Which counting tool

Look at what the problem asks you to count.

If the elements of a union of two overlapping sets → $|A|+|B|-|A\cap B|$

Example: $65+45-25=85$
If the elements of a union of three sets → the three counts, minus the three double intersections, plus the triple intersection

Example: $65+45+30-25-20-15+10=90$
If the elements that are in NONE of the sets → total count minus the cardinality of the union

Example: $100-90=10$
If the subsets of a set → $2^{|X|}$ , including the empty set and $X$ itself

Example: $2^{5}=32$
If the ordered pairs of a Cartesian product → $|A|\times|B|$ , order mattering in a pair

Example: $4\times 3=12$ pairs

A Venn diagram makes inclusion-exclusion unnecessary: once the seven regions are filled in, everything is read by simple addition. It is also what lets you check the formula.

How the answer is expected to be written

A marker ticks steps. Here they are in order, with the concluding sentence expected word for word.

Proving an equality of sets by double inclusion

When to use it: The problem asks you to show that two set expressions are equal, such as one of De Morgan's laws.

1 Announce the method: “I prove both inclusions.”
2 First direction: “Let $x\in$ left-hand side”, then unfold the definitions until you reach the right-hand side.
3 Second direction: start again from “Let $x\in$ right-hand side”.
4 Conclude: the two inclusions give the equality.

Concluding sentence

“Let $x\in\overline{A\cup B}$ . Then $x\notin A$ and $x\notin B$ , so $x\in\overline{A}\cap\overline{B}$ . The converse is proved in the same way, so the two sets are equal.”

The trap: Proving only one inclusion and concluding equality: the marking scheme counts the two directions separately.

Marking: 1.5 marks per inclusion, 0.5 mark for the conclusion. A chain of equivalences earns all three marks if it is written with “if and only if”.

Classifying a relation as an order or an equivalence

When to use it: The problem gives a relation and asks what kind it is.

1 Write the list of ordered pairs, or the Boolean matrix if it is given.
2 Test reflexivity on the diagonal, and conclude at once if it fails.
3 Test symmetry and antisymmetry, giving an explicit counterexample when the property fails.
4 Test transitivity on every chain, then name the kind of relation.

Concluding sentence

“ $R$ is reflexive, symmetric and transitive: it is an equivalence relation, and its classes form a partition of $E$ .”

The trap: Concluding “it is not an order relation” without saying which of the three properties fails or giving the counterexample.

Marking: 0.5 mark per property correctly settled with its justification, 1 mark for the named conclusion.

Check before you hand in

Five minutes of checking recover more marks than one more problem started in a hurry.

The total does not exceed the population

After an inclusion-exclusion, compare the cardinality obtained with the total number of people surveyed.

$110$ for a union in a group of $100$ : an intersection was forgotten.
The sum of the regions of the diagram

Add up the seven regions of the Venn diagram: you must get the cardinality of the union back, and by adding the outside, the total count.

$30+15+5+15+10+5+10=90$ , plus $10$ outside, that is, $100$ .
The number of subsets is a power of two

Check that the number of subsets found is indeed $2^{|X|}$ , and that it includes the empty set and $X$ .

A set with $4$ elements has $16$ subsets, including $\varnothing$ and itself.
The counterexample is written down

Each property disproved must come with the precise pair that breaks it, not with a general sentence.

“Not transitive” with no pair earns nothing; “ $(1,2)$ and $(2,3)$ without $(1,3)$ ” earns the mark.

The typical problem, taken apart

A survey on programming languages

Out of $100$ students, $65$ know Python, $45$ Java, $30$ the C language. In addition, $25$ know Python and Java, $20$ Python and C, $15$ Java and C, and $10$ know all three.

How many know none of them, and how many know only one?

The three languages and their seven regions, still empty: fill them in starting from the center, before answering.

Step 1

Central region: $10$ students know all three languages.

Why

It is the only figure that needs no subtraction. All the other regions will be deduced from it, which forces you to start here.

Step 2

Exclusive double intersections: $25-10=15$ for Python and Java only, $20-10=10$ for Python and C, $15-10=5$ for Java and C.

Why

The $25$ of the problem include the $10$ who also know the third language. So the central region is removed once, and only once.

Step 3

Python only: $65-25-20+10=30$ .

Why

Removing the two intersections takes away the $10$ in the center twice; so they are put back once. It is inclusion-exclusion applied to a single zone.

Step 4

Java only: $45-25-15+10=15$ . C only: $30-20-15+10=5$ .

Why

The same pattern repeats, with the two intersections that involve each set. Three calculations of the same form, so three chances to check the pattern.

Step 5

Union: $65+45+30-25-20-15+10=90$ , so $100-90=10$ know none of the three.

Why

The formula gives the union directly, and the complement is read by subtraction from the total count. The two routes, formula and diagram, must agree.

Step 6

Exactly one language: $30+15+5=50$ students.

Why

“Exactly one” is read only on the exclusive regions, never on the raw figures of the problem, which count each student several times.

Step 7

Check: $30+15+5+15+10+5+10=90$ , and $90+10=100$ .

Why

The sum of the seven regions plus the outside gives back the total count. A gap of one signals a subtraction done twice.

The conclusion, written out

“ $10$ students know none of the three languages, and $50$ know only one.”

The classic mistake on this problem: Answering $65$ to the question “how many know only Python”: that number also counts those who know two or three.

Learn by heart

• $\in$ links an element to a set, $\subseteq$ links two sets. $3$ and $\{3\}$ are two different objects.
• $\varnothing\subseteq A$ always; $\varnothing\in A$ almost never.
• $|\mathcal{P}(X)|=2^{|X|}$ : two choices per element, taken or left out.
• $|A\cup B|=|A|+|B|-|A\cap B|$ ; with three sets, subtract the three doubles, then ADD BACK the triple.
• A Venn diagram is filled in from the CENTRAL region.
• Order: reflexive, antisymmetric, transitive. Equivalence: reflexive, symmetric, transitive.
• Equivalence classes form a PARTITION: equal or disjoint, never partly shared.
• A property is disproved by ONE counterexample, and proved on every case.

Frequently asked questions

What is the difference between belonging to a set and being a subset of it?

Belonging links an element to a set, being a subset links two sets. The number three belongs to a set that contains it, whereas the set made up of the number three alone is a subset of it. Writing the wrong symbol does not give a clumsy sentence but a meaningless one.

How many subsets does a set with five elements have?

Thirty-two, that is, two to the power of five. Each element is independently taken or left out, which makes two possibilities per element. This count includes the empty set and the whole set. The empty set therefore has exactly one subset, itself.

How do you fill in a Venn diagram with three sets?

Always start with the central region, the elements common to all three. Then move out to the pairwise intersections by removing the center, then to the single zones by removing the two intersections that touch them and putting the center back. In that order, no number written ever needs to be corrected afterwards.

Is a relation that is not symmetric antisymmetric?

No, the two notions are not complementary. Antisymmetry requires that the presence of both pairs forces the two elements to be equal. A relation can perfectly well be neither symmetric nor antisymmetric, for example if it contains the pairs one to two, two to one, and two to three.

Can two equivalence classes have an element in common?

Only if they are equal. As soon as an element belongs to both, transitivity links every element of the first to every element of the second, and the two classes coincide. That is what makes the classes a partition: they are nonempty, pairwise disjoint, and their union is the whole set.

Practise it

Corrected exercises: Set theory and relations, 201-N11

A method is proved on a paper, not on a sheet. The set for the same chapter takes each of these traps into a problem, with the solution written out step by step.

10 corrected exercises
100 points
150 minutes

Do the exercises

Something missing from this sheet? A method, a trap, an exercise to practise it, a mistake you spotted: tell me, I read every request.

Sending goes through your free space: that is how I can answer you and tell you when the exercise is added. An email is enough, no password. Create your space. Rather not create an account? Write to me directly.

Previous sheet Modular arithmetic Next sheet Injective, surjective and bijective functions

© Ahmed Squalli Houssaini. Revision sheet published at www.letuteurscientifique.ca/en/fiches/cegep-n11-sets-and-relations. Free for personal and classroom use; republishing it elsewhere requires written permission (legal notice).

Looking for a 201-N11 tutor in Montreal?

Get in touch for a first session. With a B.Sc. in computer science from McGill and an M.Sc. in applied computer science from Concordia, I connect sets and relations to what they become next: SQL queries, hash tables and graphs.

Book a session WhatsApp

Site by Studio Squalli

Revision sheet: set theory and relations (201-N11)

The essentials

Two levels: elements and sets

Operations, De Morgan and counting

The four properties of a relation

Classes, partitions and transitive closure

The mistakes that cost marks

1. Writing an inclusion where membership is needed

2. Making the empty set belong to everything

3. Counting subsets as a square

4. Adding the counts of two overlapping sets

5. Filling in a Venn diagram from the outside

6. Mistaking antisymmetry for the absence of symmetry

7. Proving a property by checking a single favourable case

8. Believing that equivalence classes can overlap

9. Stopping the transitive closure at paths of length two

Which method to choose

Testing the four properties of a relation

Which counting tool

How the answer is expected to be written

Proving an equality of sets by double inclusion

Classifying a relation as an order or an equivalence

Check before you hand in

The typical problem, taken apart

A survey on programming languages

Learn by heart

Frequently asked questions

What is the difference between belonging to a set and being a subset of it?

How many subsets does a set with five elements have?

How do you fill in a Venn diagram with three sets?

Is a relation that is not symmetric antisymmetric?

Can two equivalence classes have an element in common?

Corrected exercises: Set theory and relations, 201-N11

See also

Looking for a 201-N11 tutor in Montreal?