Set theory is one of the most fundamental areas of mathematics, serving as a foundation for all other mathematical disciplines. On the YÖS exam, problems about sets test your understanding of logic, your ability to work with Euler-Venn diagrams, and your application of the inclusion-exclusion formulas.
Definition: A set is a collection of well-defined, distinct objects called elements or members of the set. Each element either belongs to the set or does not belong to it.
Notation: A set is denoted by capital letters: $A$, $B$, $C$, ...The elements of a set are denoted by lowercase letters: $a$, $b$, $c$, ...
Membership of an element in a set:- If the element $x$ belongs to the set $A$, we write: $x \in A$- If the element $x$ does not belong to the set $A$, we write: $x \notin A$
#### Method 1: Listing the elementsA set is specified by explicitly listing all of its elements within curly braces.
Examples:- $A = \{1, 2, 3, 4, 5\}$ — the set of the first five natural numbers- $B = \{red, yellow, green\}$ — the set of the main colors of a traffic light- $C = \{a, e, i, o, u\}$ — the set of vowel letters of the English alphabet
#### Method 2: Describing a propertyA set is specified by stating a property that all of its elements must satisfy.
Notation: $A = \{x \mid P(x)\}$ or $A = \{x : P(x)\}$
Read as: "the set of all $x$ such that $P(x)$ is true"
Examples:- $A = \{x \in \mathbb{N} \mid x < 10\}$ — the set of natural numbers less than 10- $B = \{x \in \mathbb{R} \mid x^2 = 4\}$ — the set of all real numbers whose square equals 4 (this is $\{-2, 2\}$)- $C = \{x \mid x \text{ — чётное число}\}$ — the set of all even numbers
Definition: The empty set is a set that contains no elements at all.
Notation: $\emptyset$ or $\{\}$
Property: The empty set is a subset of every set.
Example: $A = \{x \in \mathbb{R} \mid x^2 + 1 = 0\}$ — this is the empty set, since there is no real number whose square plus 1 equals 0.
Definition: The universal set (or universe) is a set that, in the given context, contains all the elements under consideration.
Notation: $U$ or $\mathbb{U}$
Example: If we are working with sets of natural numbers, the universal set may be $U = \mathbb{N}$.
Important: The universal set depends on the context of the problem.
Definition: A set $A$ is called a subset of a set $B$ if every element of the set $A$ is also an element of the set $B$.
Notation: $A \subseteq B$
Formally: $A \subseteq B \Leftrightarrow \forall x: (x \in A \Rightarrow x \in B)$
Properties:1. $\emptyset \subseteq A$ for any set $A$ (the empty set is a subset of every set)2. $A \subseteq A$ for any set $A$ (reflexivity)3. If $A \subseteq B$ and $B \subseteq C$, then $A \subseteq C$ (transitivity)
Definition: A set $A$ is called a proper subset of a set $B$ if $A \subseteq B$ and $A \neq B$.
Notation: $A \subset B$ or $A \subsetneq B$
Example: The set $\{1, 2\}$ is a proper subset of the set $\{1, 2, 3\}$.
Definition: Two sets $A$ and $B$ are called equal if they contain the same elements.
Notation: $A = B$
Formally: $A = B \Leftrightarrow (A \subseteq B \text{ и } B \subseteq A)$
Examples:- $\{1, 2, 3\} = \{3, 2, 1\}$ (the order of elements does not matter)- $\{1, 1, 2\} = \{1, 2\}$ (duplicates count as a single element)- $\{x \in \mathbb{N} \mid x \text{ — чётно и } x < 10\} = \{2, 4, 6, 8\}$
Definition: The union of sets $A$ and $B$ is the set of all elements that belong to at least one of the sets $A$ or $B$.
Notation: $A \cup B$
Formally: $A \cup B = \{x \mid x \in A \text{ или } x \in B\}$
Example:If $A = \{1, 2, 3\}$ and $B = \{2, 3, 4, 5\}$, then $A \cup B = \{1, 2, 3, 4, 5\}$
Properties of union:1. Commutativity: $A \cup B = B \cup A$2. Associativity: $(A \cup B) \cup C = A \cup (B \cup C)$3. Idempotency: $A \cup A = A$4. With the empty set: $A \cup \emptyset = A$5. With the universal set: $A \cup U = U$
Definition: The intersection of sets $A$ and $B$ is the set of all elements that belong simultaneously to both the set $A$ and the set $B$.
Notation: $A \cap B$
Formally: $A \cap B = \{x \mid x \in A \text{ и } x \in B\}$
Example:If $A = \{1, 2, 3, 4\}$ and $B = \{2, 3, 4, 5\}$, then $A \cap B = \{2, 3, 4\}$
Properties of intersection:1. Commutativity: $A \cap B = B \cap A$2. Associativity: $(A \cap B) \cap C = A \cap (B \cap C)$3. Idempotency: $A \cap A = A$4. With the empty set: $A \cap \emptyset = \emptyset$5. With the universal set: $A \cap U = A$
Definition: The sets $A$ and $B$ are called disjoint if $A \cap B = \emptyset$.
Definition: The difference of sets $A$ and $B$ (or the complement of $B$ in $A$) is the set of all elements that belong to $A$ but do not belong to $B$.
Notation: $A \setminus B$ or $A - B$
Formally: $A \setminus B = \{x \mid x \in A \text{ и } x \notin B\}$
Example:If $A = \{1, 2, 3, 4, 5\}$ and $B = \{2, 4\}$, then $A \setminus B = \{1, 3, 5\}$
Properties of the difference:1. $A \setminus A = \emptyset$2. $A \setminus \emptyset = A$3. $\emptyset \setminus A = \emptyset$4. The difference is not commutative: $A \setminus B \neq B \setminus A$ (in general)
Definition: The complement of a set $A$ (relative to the universal set $U$) is the set of all elements of the universal set that do not belong to $A$.
Notation: $A'$ or $\overline{A}$ or $A^c$ or $U \setminus A$
Formally: $A' = \{x \in U \mid x \notin A\}$
Example:If $U = \{1, 2, 3, 4, 5, 6\}$ and $A = \{2, 4, 6\}$, then $A' = \{1, 3, 5\}$
Properties of the complement:1. $(A')' = A$ (double complement)2. $A \cup A' = U$ (the complement together with the original set gives the universe)3. $A \cap A' = \emptyset$ (the complement does not intersect with the original set)4. $U' = \emptyset$ and $\emptyset' = U$
Definition: The symmetric difference of sets $A$ and $B$ is the set of elements that belong to either $A$ or $B$, but not to both at once.
Notation: $A \triangle B$ or $A \oplus B$
Formally: $A \triangle B = (A \setminus B) \cup (B \setminus A) = (A \cup B) \setminus (A \cap B)$
Example:If $A = \{1, 2, 3\}$ and $B = \{2, 3, 4, 5\}$, then:- $A \setminus B = \{1\}$- $B \setminus A = \{4, 5\}$- $A \triangle B = \{1, 4, 5\}$
Properties of the symmetric difference:1. Commutativity: $A \triangle B = B \triangle A$2. Associativity: $(A \triangle B) \triangle C = A \triangle (B \triangle C)$3. $A \triangle A = \emptyset$4. $A \triangle \emptyset = A$
Euler-Venn diagrams are a graphical way of representing sets and operations on them. Sets are depicted as circles or other closed curves placed inside a rectangle that represents the universal set $U$.
For sets $A$ and $B$, the diagram shows four regions:1. Elements belonging only to $A$: $A \setminus B$2. Elements belonging to both $A$ and $B$: $A \cap B$3. Elements belonging only to $B$: $B \setminus A$4. Elements belonging to neither $A$ nor $B$: $(A \cup B)'$
For sets $A$, $B$, and $C$, the diagram shows eight regions, corresponding to all possible combinations of membership of elements in these three sets.
Application of diagrams in solving problems:- Diagrams help visualize the problem- They allow you to verify the correctness of set operations- They make it easier to count the elements in various regions
Definition: The cardinality of a set is the number of elements in the set. The cardinality is denoted by $|A|$ or $n(A)$ or $\#A$.
Examples:- $|\{1, 2, 3\}| = 3$- $|\emptyset| = 0$- $|\{a, b, c, d, e\}| = 5$
A finite set is a set with a finite number of elements.
An infinite set is a set with an infinite number of elements.
Examples:- Finite: $A = \{1, 2, 3, 4, 5\}$, $|A| = 5$- Infinite: $\mathbb{N} = \{1, 2, 3, 4, ...\}$ (the set of natural numbers)
Theorem: For any finite sets $A$ and $B$, the following formula holds:
$$|A \cup B| = |A| + |B| - |A \cap B|$$
Proof:The set $A \cup B$ can be represented as the union of three disjoint subsets:- Elements only in $A$: $A \setminus B$, of size $|A \setminus B|$- Elements in the intersection: $A \cap B$, of size $|A \cap B|$- Elements only in $B$: $B \setminus A$, of size $|B \setminus A|$
$$|A \cup B| = |A \setminus B| + |A \cap B| + |B \setminus A|$$
Also note that:- $|A| = |A \setminus B| + |A \cap B|$, hence $|A \setminus B| = |A| - |A \cap B|$- $|B| = |B \setminus A| + |A \cap B|$, hence $|B \setminus A| = |B| - |A \cap B|$
Substituting:$$|A \cup B| = (|A| - |A \cap B|) + |A \cap B| + (|B| - |A \cap B|) = |A| + |B| - |A \cap B|$$
Examples of use:
Example 1: In a class there are 30 students. 18 study English, 15 study French, and 8 study both languages. How many students study neither English nor French?
Solution:Let $A$ be the set of students who study English, and $B$ the set of students who study French.- $|A| = 18$- $|B| = 15$- $|A \cap B| = 8$
By the inclusion-exclusion formula:$$|A \cup B| = 18 + 15 - 8 = 25$$
Therefore, 25 students study at least one of these languages.
Students who study neither language: $30 - 25 = 5$
Answer: 5 students
Theorem: For any finite sets $A$, $B$, and $C$, the following formula holds:
$$|A \cup B \cup C| = |A| + |B| + |C| - |A \cap B| - |A \cap C| - |B \cap C| + |A \cap B \cap C|$$
Mnemonic rule:- Add the cardinalities of all the sets- Subtract the cardinalities of the pairwise intersections- Add the cardinality of the intersection of all three
Example 2: In a group of 100 students, 60 do sports, 45 attend the drama club, and 50 sing in the choir. 25 do sports and participate in drama, 20 do sports and sing in the choir, and 15 participate in drama and sing in the choir. 10 students do sports, participate in drama, and sing in the choir. How many students participate in at least one of these activities?
Solution:Let:- $S$ be the set of students who do sports- $D$ be the set of students in the drama club- $H$ be the set of students in the choir
Given:- $|S| = 60$- $|D| = 45$- $|H| = 50$- $|S \cap D| = 25$- $|S \cap H| = 20$- $|D \cap H| = 15$- $|S \cap D \cap H| = 10$
By the inclusion-exclusion formula:$$|S \cup D \cup H| = 60 + 45 + 50 - 25 - 20 - 15 + 10 = 155 - 60 + 10 = 105$$
But this number is greater than 100, which is impossible. This means that the given data contain an error, since the numbers of students in the various groups are inconsistent.
Note: When working with such problems, always check the correctness of the given data.
Definition: The set of all subsets of a set $A$ is called the power set, the Boolean, or the set of subsets of $A$.
Notation: $P(A)$ or $2^A$ or $\mathcal{P}(A)$
Example: If $A = \{1, 2, 3\}$, then the subsets of the set $A$ are:- $\emptyset$ (the empty set)- $\{1\}$, $\{2\}$, $\{3\}$ (one-element subsets)- $\{1, 2\}$, $\{1, 3\}$, $\{2, 3\}$ (two-element subsets)- $\{1, 2, 3\}$ (the set itself)
In total: $P(A) = \{\emptyset, \{1\}, \{2\}, \{3\}, \{1, 2\}, \{1, 3\}, \{2, 3\}, \{1, 2, 3\}\}$
Theorem on the cardinality of the power set:
If the set $A$ has cardinality $|A| = n$, then the cardinality of the power set equals:
$$|P(A)| = 2^n$$
Proof: For each element of the set $A$, we decide whether to include it in a subset or not. This gives us 2 choices for each of the $n$ elements. By the product rule, we obtain $2^n$ different subsets.
Example 3: How many subsets in total does the set $B = \{a, b, c, d\}$ have?
Solution:The cardinality of the set $B$ equals 4.The total number of subsets: $|P(B)| = 2^4 = 16$
Verification:- 0 elements: $C(4, 0) = 1$ (the empty set)- 1 element: $C(4, 1) = 4$- 2 elements: $C(4, 2) = 6$- 3 elements: $C(4, 3) = 4$- 4 elements: $C(4, 4) = 1$
In total: $1 + 4 + 6 + 4 + 1 = 16 = 2^4$ ✓
Definition: The Cartesian product of sets $A$ and $B$ is the set of all ordered pairs $(a, b)$ where $a \in A$ and $b \in B$.
Notation: $A \times B$
Formally: $A \times B = \{(a, b) \mid a \in A, b \in B\}$
Example 4: Find the Cartesian product $A \times B$ if $A = \{1, 2\}$ and $B = \{a, b, c\}$.
Solution:$$A \times B = \{(1, a), (1, b), (1, c), (2, a), (2, b), (2, c)\}$$
Cardinality: $|A \times B| = |A| \cdot |B| = 2 \cdot 3 = 6$
Example 5: The standard Cartesian coordinate system in the plane is $\mathbb{R} \times \mathbb{R} = \mathbb{R}^2$, where each point of the plane corresponds to an ordered pair $(x, y)$ of real numbers.
In a survey of 120 people, 75 people like coffee and 60 people like tea. How many people like both coffee and tea, if only 20 people like neither coffee nor tea?
Solution:
Let $K$ be the set of people who like coffee, and $T$ the set of people who like tea.
Given:- Total people: 120- $|K| = 75$- $|T| = 60$- People who like neither coffee nor tea: 20
Hence, people who like at least one drink: $120 - 20 = 100$
By the inclusion-exclusion formula:$$|K \cup T| = |K| + |T| - |K \cap T|$$$$100 = 75 + 60 - |K \cap T|$$$$|K \cap T| = 75 + 60 - 100 = 35$$
Answer: 35 people like both coffee and tea
Given the set $A = \{x \in \mathbb{N} \mid 3 < x \leq 7\}$.
a) Find the cardinality of the set $A$b) Find the cardinality of the power set $P(A)$c) How many subsets of the set $A$ contain the element 5?
a) The set $A = \{4, 5, 6, 7\}$, so $|A| = 4$
b) Cardinality of the power set: $|P(A)| = 2^4 = 16$
c) The subsets containing 5 have the form $\{5\} \cup X$, where $X$ is a subset of the set $\{4, 6, 7\}$.
The cardinality of the set $\{4, 6, 7\}$ equals 3, so the number of its subsets equals $2^3 = 8$.
Answer: a) 4; b) 16; c) 8 subsets
Given the sets: $A = \{1, 2, 3, 4, 5\}$, $B = \{2, 4, 6, 8\}$, $C = \{1, 3, 5, 7\}$.
Find:a) $A \cap B$b) $A \cup C$c) $A \setminus B$d) $(A \cap B) \cup C$e) $(A \cup B) \cap C$
a) $A \cap B = \{2, 4\}$ (elements common to $A$ and $B$)
b) $A \cup C = \{1, 2, 3, 4, 5, 7\}$ (all elements from $A$ and $C$)
c) $A \setminus B = \{1, 3, 5\}$ (elements of $A$ that are not in $B$)
d) $(A \cap B) \cup C = \{2, 4\} \cup \{1, 3, 5, 7\} = \{1, 2, 3, 4, 5, 7\}$
e) $(A \cup B) \cap C = \{1, 2, 3, 4, 5, 6, 8\} \cap \{1, 3, 5, 7\} = \{1, 3, 5\}$
Given the sets $X = \{2, 3\}$ and $Y = \{a, b, c\}$. Find $Y \times X$ and its cardinality.
$$Y \times X = \{(a, 2), (a, 3), (b, 2), (b, 3), (c, 2), (c, 3)\}$$
Cardinality: $|Y \times X| = |Y| \cdot |X| = 3 \cdot 2 = 6$
Answer: The Cartesian product contains 6 ordered pairs
Given: $U = \{1, 2, 3, 4, 5, 6, 7, 8\}$ — the universal set, $A = \{1, 3, 5, 7\}$, $B = \{2, 3, 6, 7\}$.
Find:a) $A'$b) $(A \cup B)'$c) $A' \cap B'$d) Show that $(A \cup B)' = A' \cap B'$ (one of De Morgan's laws)
a) $A' = U \setminus A = \{2, 4, 6, 8\}$
b) $A \cup B = \{1, 2, 3, 5, 6, 7\}$ $(A \cup B)' = U \setminus (A \cup B) = \{4, 8\}$
c) $A' = \{2, 4, 6, 8\}$, $B' = \{1, 4, 5, 8\}$ $A' \cap B' = \{4, 8\}$
d) From b) and c) we see that $(A \cup B)' = \{4, 8\} = A' \cap B'$ ✓
This illustrates De Morgan's law: $(A \cup B)' = A' \cap B'$
### Mistake 1: Confusing union and intersectionIncorrect: For a problem "find the elements that are in $A$ or in $B$", applying the intersection $A \cap B$.Correct: This is the union $A \cup B$. The keyword "or" indicates a union, while "and" indicates an intersection.
### Mistake 2: Forgetting the empty setIncorrect: Claiming that $\emptyset$ is not a subset of a set $A$.Correct: The empty set is a subset of every set: $\emptyset \subseteq A$ for all $A$.
### Mistake 3: Incorrect application of the inclusion-exclusion formulaIncorrect: $|A \cup B| = |A| + |B|$ (forgetting to subtract the intersection)Correct: $|A \cup B| = |A| + |B| - |A \cap B|$
### Mistake 4: Confusing the cardinality of a set and its power setIncorrect: If $|A| = 5$, then the number of subsets equals 5.Correct: The number of subsets equals $2^5 = 32$.
### Mistake 5: Misunderstanding the complementIncorrect: $A' = \{$all elements that are not in $A\}$ (without regard to the universal set)Correct: $A' = \{x \in U \mid x \notin A\}$ (only elements of the universal set)
### Mistake 6: Order in ordered pairsIncorrect: $(a, b) = (b, a)$Correct: $(a, b) = (b, a)$ only if $a = b$. In general, ordered pairs differ.
### Mistake 7: Carelessness in using Venn diagramsIncorrect: Ignoring regions of the diagram that appear "empty".Correct: All eight regions of the diagram for three sets may contain elements, even if they are not shown explicitly in the diagram.
### Tip 1: Visualization with Venn diagramsAlways draw a Venn diagram when working on set problems. This helps avoid mistakes and clearly shows what needs to be found.
### Tip 2: Verification with concrete examplesIf you are unsure about the correctness of a set operation, verify the result on a simple example with concrete numbers.
### Tip 3: Understanding De Morgan's lawRemember the two versions:- $(A \cap B)' = A' \cup B'$- $(A \cup B)' = A' \cap B'$
These laws frequently appear in problems.
### Tip 4: Logical analysis of the problem textRead the problem statement carefully and determine:- Which sets are given- Which operations need to be performed- What needs to be found
### Tip 5: Checking boundary casesIf the problem mentions "people not in the group", do not forget to include this information in your calculations.
### Tip 6: An organized approachWhen solving complex problems:1. Denote the sets by variables2. Write down all the known data3. Choose the appropriate formula or method4. Check the result
### Tip 7: Attention to modifiersDistinguish:- $A \subseteq B$ (subset, including the possibility of equality)- $A \subset B$ or $A \subsetneq B$ (proper subset, $A \neq B$)- $A = B$ (equality)
### Tip 8: Practice with numerical setsOn the exam, numerical sets are often used. Practice with:- Sets of even/odd numbers- Sets of prime numbers- Sets defined by inequalities
### Tip 9: Time managementSimple set problems are usually solved in 1-2 minutes. If you have spent more time, check whether you have understood the problem correctly.
### Tip 10: Maintaining an algebraic approachDo not always rely on diagrams alone. Use an algebraic approach with formulas, especially when working with large numbers or abstract sets.
---
Conclusion
Set theory is a fundamental area that requires a clear understanding of definitions and careful application of operations. Regular practice with a variety of problems will help you confidently solve problems on the YÖS exam.
All course topics · Practice problems
Please enable JavaScript to use the practice app.