# 2. Methodical guidelines / Методичні вказівки

This section is **self-contained**: it collects all the theory needed for the
theme — finite sets, their operations, diagrams, and algebra — together with the
techniques used to solve the tasks in [3classroom.md](3classroom.md). No outside
material is required.

## 2.1 Sets and how to write them

A **set** is an unordered collection of **distinct** objects, called its
*elements*. We write $x \in A$ if $x$ is an element of $A$, and $x \notin A$
otherwise. Two properties define what a set *is*:

- **Distinctness** — repeating an element changes nothing:
  $\{1,2,2,3\} = \{1,2,3\}$;
- **No order** — the elements have no positions: $\{1,2,3\} = \{3,1,2\}$.

There are two standard ways to describe a set:

- **Roster form** — list the elements between braces: $A = \{2,4,6,8\}$;
- **Set-builder form** — state a defining property:
  $A = \{\, x \mid x \in \mathbb{N} \ \text{and}\ x \ \text{is even} \,\}$,
  read "the set of all $x$ such that …".

Useful named sets: the **natural numbers** $\mathbb{N} = \{1,2,3,\dots\}$ and the
**empty set** $\varnothing = \{\,\}$, which has no elements. The **cardinality**
$|A|$ is the number of distinct elements of $A$; $|\varnothing| = 0$.

**Subset and equality.** $A \subseteq B$ ("$A$ is a subset of $B$") means every
element of $A$ is also in $B$. Two sets are **equal**, $A = B$, exactly when they
have the same elements — equivalently, when $A \subseteq B$ **and** $B \subseteq
A$. This "prove both inclusions" idea is one way to establish a set identity
(§2.5).

**Universal set.** Many problems fix in advance a set $U$ of *all* elements under
consideration — the **universe**. It is the reference domain against which a
**complement** is taken (§2.2). On a diagram the universe is the bounding
rectangle.

## 2.2 The operations on sets

Let $A$ and $B$ be sets inside a universe $U$.

| Operation | Notation | Definition | Example |
|---|:--:|---|---|
| **Union** | $A \cup B$ | $\{\, x : x \in A \ \text{or}\ x \in B \,\}$ | $\{1,2,3\}\cup\{3,4\}=\{1,2,3,4\}$ |
| **Intersection** | $A \cap B$ | $\{\, x : x \in A \ \text{and}\ x \in B \,\}$ | $\{1,2,3\}\cap\{3,4\}=\{3\}$ |
| **Difference** | $A \setminus B$ | $\{\, x : x \in A \ \text{and}\ x \notin B \,\}$ | $\{1,2,3\}\setminus\{3,4\}=\{1,2\}$ |
| **Complement** | $\overline{A}$ | $U \setminus A = \{\, x \in U : x \notin A \,\}$ | $\overline{\{1,2\}}=\{3,4,5\}$ if $U=\{1,\dots,5\}$ |

Two facts used constantly:

- **Complement is relative.** $\overline{A}$ has no meaning without a universe;
  always state $U$ before taking a complement.
- **Difference is directed.** In general $A \setminus B \neq B \setminus A$. Sets
  with $A \cap B = \varnothing$ are **disjoint**.

The single most useful bridge between the operations is

$$A \setminus B = A \cap \overline{B},$$

i.e. "everything in $A$ that is not in $B$" equals "$A$ intersected with the
complement of $B$". It converts differences into intersections and complements,
which is what makes the algebraic proofs in §2.5 work.

## 2.3 Euler and Venn diagrams

A **Venn diagram** draws each set as a circle inside the rectangle $U$, arranging
the circles so that **every possible overlap is shown**. For two sets there are
four regions; for three sets, eight:

- **Two sets** $A,B$: *only $A$* ($A\setminus B$), *the overlap* ($A\cap B$),
  *only $B$* ($B\setminus A$), and *outside both* ($\overline{A\cup B}$).
- **Three sets** $A,B,C$: the three "petals" $A,B,C$, the three pairwise lenses
  ($A\cap B$, $A\cap C$, $B\cap C$), the central region $A\cap B\cap C$, and the
  outside region.

![Two-set Venn diagram inside the universe U, showing its four regions](img/method_2set.png)

An **Euler diagram** is the same idea but shows **only the relationships that
actually occur** — for example, if $A \subseteq B$ it draws circle $A$ *inside*
circle $B$ with no spurious overlap. Venn diagrams fix the layout and shade;
Euler diagrams tailor the layout to the situation.

**How to shade an expression (work inside-out).** To draw the region a formula
denotes, evaluate it the way you would arithmetic — innermost operation first:

1. shade each parenthesised sub-expression on a scratch copy;
2. combine: **union** shades the *union* of the two regions; **intersection**
   keeps only the *common* part; **difference** $X\setminus Y$ keeps the part of
   $X$ *outside* $Y$; **complement** shades everything *outside* the region.

For example, to shade $A \setminus (B \cup C)$: first shade $B \cup C$ (both of
those circles), then keep only the part of $A$ that lies **outside** that shaded
area.

**How to read a formula off a diagram.** Name the shaded region by the simplest
combination of circles that produces it — e.g. "the parts of $A$ and $B$ but not
$C$" reads as $(A \cup B)\setminus C$.

## 2.4 The algebra of sets

The operations obey algebraic laws. They let you simplify expressions and prove
identities by symbol manipulation, without drawing.

| Law | Statement |
|---|---|
| Commutativity | $A \cup B = B \cup A,\quad A \cap B = B \cap A$ |
| Associativity | $(A \cup B) \cup C = A \cup (B \cup C)$, and likewise for $\cap$ |
| Distributivity | $A \cap (B \cup C) = (A \cap B) \cup (A \cap C)$, and dually $A \cup (B \cap C) = (A \cup B) \cap (A \cup C)$ |
| Identity | $A \cup \varnothing = A,\quad A \cap U = A$ |
| Domination | $A \cup U = U,\quad A \cap \varnothing = \varnothing$ |
| Complement | $A \cup \overline{A} = U,\quad A \cap \overline{A} = \varnothing,\quad \overline{\overline{A}} = A$ |
| De Morgan | $\overline{A \cup B} = \overline{A} \cap \overline{B},\quad \overline{A \cap B} = \overline{A} \cup \overline{B}$ |
| Difference | $A \setminus B = A \cap \overline{B}$ |

Note especially **De Morgan** (a complement of a union/intersection flips the
operation and complements each part) and the **difference** law — these two do
most of the work in the proof tasks.

## 2.5 Proving a set identity

To show two expressions denote the **same** set, use either method:

- **Diagram / membership method.** Shade the region for each side on its own Venn
  diagram. If the two shaded regions coincide, the identity holds. (Formally, this
  is checking that an arbitrary element lies in the left side exactly when it lies
  in the right side — a *membership* argument.)
- **Algebraic method.** Rewrite one side step by step using the laws of §2.4 until
  it becomes the other side, citing one law per step. Rewriting
  $A \setminus B$ as $A \cap \overline{B}$ is usually the first move, after which
  De Morgan and distributivity finish the job.

Both methods are legitimate; the diagram makes the result *visible*, the algebra
makes it *rigorous*. Where practical, do both and check that they agree.

## 2.6 The power set

The **power set** $\mathcal{P}(A)$ is the set of **all subsets** of $A$,
including the empty set $\varnothing$ and $A$ itself. For example,

$$\mathcal{P}(\{1,2\}) = \{\, \varnothing,\ \{1\},\ \{2\},\ \{1,2\} \,\}.$$

Each element of $A$ is independently **in or out** of a given subset, so an
$n$-element set has

$$|\mathcal{P}(A)| = 2^{|A|}$$

subsets. To list a power set without omissions, enumerate subsets **by size**:
first $\varnothing$, then all singletons, then all pairs, and so on up to $A$
itself.

## 2.7 Working checklist

- Write sets in a **consistent order** (e.g. increasing) so equal sets are easy to
  compare, even though order does not matter formally.
- Before any complement, **write down $U$**.
- For a diagram task, shade **inside-out** and label the final region.
- For a proof task, prefer converting $\setminus$ to $\cap\overline{\;\cdot\;}$
  first, then apply **De Morgan** and **distributivity**.
- For a listing task, translate the **set-builder** condition into a test applied
  to each candidate, then collect those that pass.

## 2.8 Symmetric difference, Cartesian product, and inclusion–exclusion

Three further tools appear in the counting and product tasks.

- **Symmetric difference** $A \triangle B = (A \setminus B) \cup (B \setminus A)$: the
  elements in **exactly one** of $A$ and $B$ — the "exclusive or" of sets. Equivalently
  $A \triangle B = (A \cup B) \setminus (A \cap B)$.
- **Cartesian product** $A \times B = \{\,(a,b) : a \in A,\ b \in B\,\}$: the set of all
  **ordered pairs** whose first component lies in $A$ and second in $B$. Its size is
  $|A \times B| = |A|\cdot|B|$.
- **Inclusion–exclusion (two sets).** $|A \cup B| = |A| + |B| - |A \cap B|$: adding
  $|A|$ and $|B|$ counts the overlap $A \cap B$ twice, so it is subtracted once. For
  three sets, $|A \cup B \cup C| = |A|+|B|+|C| - |A\cap B| - |A\cap C| - |B\cap C| +
  |A\cap B\cap C|$.