Skip to content

1. Set Theory and Basics of Counting

Introduction

  • The foundation of set theory was laid by the German Mathematician Georg Cantor in the later part of the 19th century 1.
Symbol Reads Meaning Name
\(P \wedge Q\) \(P\) and \(Q\) Conjunction
\(P \vee Q\) \(P\) or \(Q\) Disjunction
\(P \implies Q\) \(P\) implies \(Q\) If P then Q Implication
\(P \iff Q\) \(P\) if and only if \(Q\) \(P\) is equivalent to \(Q\) BiConditional
\(\neg P\) not \(P\) Negation
\(A = \{a, b\}\) Set
\(a \in A\) \(a\) is in \(A\) \(a\) is an element in (belongs to) \(A\) Is In
\(a \notin A\) \(a\) is not in \(A\) Is Not In
\(\colon\) such that sometimes \(\mid\) or \(\ni\) may be used as alternatives to \(\colon\) Such That
\(\emptyset\) the empty set \(\emptyset = \{\}\) Empty Set
\(\mathcal{u}\) the universe set The set of all elements Universe Set
\(\mathbb{N}\) the natural numbers \(\mathbb{N} = \{0, 1, 2, 3, ...\}\), all positive integers Natural Set
\(\mathbb{P}\) the positive integers \(\mathbb{P} = \{ N \setminus \{0\}\}\), all \(\mathbb{N}\) except 0 Positive Set
\(\mathbb{Z}\) the integers \(\mathbb{Z} = \{..., -1, 0, 1, ...\}\), all positive and negative integers Integer Set
\(\mathbb{Q}\) the rational numbers \(\mathbb{Q} = \{p/q : p,q \in \mathbb{Z}, q \neq 0\}\) Rational Set
\(\mathbb{R}\) the real numbers Real Set
\(\mathbb{C}\) the complex numbers \(\mathbb{C} = \{a + bi : a,b \in \mathbb{R}, i^2=-1\}\) Complex Set
\(\mathcal{p}(A)\) the power set of \(A\) The set of all subsets of A. Power Set
\(\subseteq\) is a subset of Subset
\(\subset\) is a proper subset of Proper Subset
\(\bigcup\) union Union
\(\bigcap\) intersection Intersection
\(\setminus\) set difference Set Difference
\(\times\) cartesian product Cartesian Product
\(\bar{A}\) complement of \(A\) Complement
\(\vert A \vert\) cardinality of \(A\) Cardinality
  • Examples:
  • \(A = \{x \in \mathbb{N} : \exists n \in \mathbb{N} ( x = 2n) \}\) which:
    • Reads as A is the set of all natural numbers such that there exists a natural number n such that x is equal to 2n.
    • Means A is a set of all even natural numbers (x=2n indicates the number is even).
  • The Cartesian Plane is the set of all ordered pairs of real numbers \(CP=\{(x, y): x \in \mathbb{R} \wedge y \in \mathbb{R} \}\).
  • \(\mathbb{N} ⊆ \mathbb{Z} ⊆ \mathbb{Q} ⊆ \mathbb{R} ⊆ \mathbb{C}\)

2 More on Sets

4.1 Methods of Proof for Sets

  • If \(A, B, C\) are arbitrary sets, is it always true that \(A \cap (B \cup C) = (A \cap B) \cup (A \cap C)\) ?
  • We’ll prove the distributive law above in different methods
  • Theses methods include using:
    1. Examples and Counter Examples.
    2. Ven Diagrams.
    3. Set-Membership tables.
    4. Definitions.
    5. Previously proven theorems.
    6. Indirect proofs (proof by contradiction).
  • Method 1: Examples and Counter Examples
    • We start by simple example and verify the statement for this particular example.
    • Example, we try the distributive law for \(A = \{1,2\}, B = \{5,8,10\}, C = \{3,2,5\}\)
    • This is no acceptable as a proof, but it is a good start so that if did not work for a case, there is no need to continue.
    • Any example that disapproves the statement is called a counter example.
  • Method 2: Proof using Ven Diagrams:
    • We represent sets by circles and shade the regions that correspond to the two sides of the equation, and verify that the shaded regions are the same.
    • In our case, we represent the sets \(A, B, C\) by circles and shade the regions that correspond to the sets \(A \cap (B \cup C)\) and \((A \cap B) \cup (A \cap C)\), and verify that the shaded regions are the same.
    • Advantages of this method: 1. quick and easy to do, 2. gives a visual representation of the proof.
    • Disadvantages of this method: 1. only works in sets with small number of elements.

  • Method 3: Proof using Set-Membership tables

    • \(let \, A ∈ U\) where A is a subset of a universal set U. and \(let \, u \in U\) be an arbitrary element of U. There are only two possibilities: \(u \in A\) or \(u \notin A\).
    • We construct the Set-membership table by denoting 1 if \(u \in A\) and 0 if \(u \notin A\).

    • The set table for \(A ∪ B\) is as follows:

      \(u ∈ A\) \(u ∈ B\) \(u ∈ A ∪ B\)
      1 1 1
      1 0 1
      0 1 1
      0 0 0

    • To prove a statement, write the membership-set table for each side of the equation and verify that the two tables are the same.

  • Method 4: Proof using Definitions:

    • This is the most useful method of proof.
    • This method has various techniques:
      1. State and restate the theorem so you understand what is given (the hypotheses) and what is to be proved (the conclusion).

  • Proof using State and restate:

    • Theorem: The Distributive Law of Intersection over Union. For all sets \(A, B, C\), \(A \cap (B \cup C) = (A \cap B) \cup (A \cap C)\).

    • Comments:

      • We need to verify that the left hand side (LHS) is equal to the right hand side (RHS).
      • Both sides are sets, so we need to proof that the two sets are equal LHS = RHS.
      • To proof that two sets are equal, we must proof that:
        • (a) \(LHS \subseteq RHS\)
        • (b) \(RHS \subseteq LHS\)
      • To proof (a) and (b), we need to prove that every element of \(LHS\) is an element of \(RHS\) and vice versa.
      • prof (a):
      \[ \begin{aligned} \text{let} \, x ∈ A ∩ (B ∪ C) \\ x ∈ A ∩ (B ∪ C) & ⟹ x ∈ A \, and \, (x ∈ B \, or \, x ∈ C) \, [\text{definition of union and intersection}] \\ & ⟹ (x ∈ A \, and \, x ∈ B) \, or \, (x ∈ A \, and \, x ∈ C) \, [\text{distributive law of logic}] \\ & ⟹ (x ∈ A ∩ B) \, or \, (x ∈ A ∩ C) \, [\text{definition of intersection}] \\ & ⟹ x ∈ (A ∩ B) ∪ (A ∩ C) \, [\text{definition of union}] \\ \end{aligned} \]
      • prof (b): we start by \(x ∈ (A ∩ B) ∪ (A ∩ C)\) and show that \(x ∈ A ∩ (B ∪ C)\) by using the same steps as above but in reverse order.

4.2 Laws of Set Theory

Law Name Union Intersection
Commutative Laws \(A ∪ B = B ∪ A\) \(A ∩ B = B ∩ A\)
Associative Laws \(A ∪ (B ∪ C) = (A ∪ B) ∪ C\) \(A ∩ (B ∩ C) = (A ∩ B) ∩ C\)
Distributive laws \(A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C)\) \(A ∪ (B ∩ C) = (A ∪ B) ∩ (A ∪ C)\)
Identity laws \(A ∪ ∅ = ∅ ∪ A = A\) \(A ∩ U = U ∩ A = A\)
Complement laws \(A ∪ A' = U\) \(A ∩ A' = ∅\)
Idempotent laws \(A ∪ A = A\) \(A ∩ A = A\)
Null laws \(A ∪ U = U\) \(A ∩ ∅ = ∅\)
Absorption laws \(A ∪ (A ∩ B) = A\) \(A ∩ (A ∪ B) = A\)
De Morgan’s laws \((A ∪ B)' = A' ∩ B'\) \((A ∩ B)' = A' ∪ B'\)
Involution law \((A')' = A\)

4.3 Minsets

  • If \(B1, B2\) are subsets of a set \(A\), then their intersection \(B1 ∩ B2\) produces few minsets (as shown in the image above).
  • \(A1 = B1 ∩ B2'\)
  • \(A2 = B1 ∩ B2\)
  • \(A3 = B1' ∩ B2\)
  • \(A4 = B1' ∩ B2'\)
  • Each of these minsets produced by an intersection of either \(B1\) or \(B2\) or \(B1'\) or \(B2'\).

4.4 The Duality Principle

  • The Duality Principle states for every law of set theory, there is a dual laws obtained by changing ∪ to ∩ and vice versa, and changing U to ∅ and vice versa, and leaving complements unchanged.

3 Introduction and Preliminaries

Implications

  • The implication \(P \implies Q\) is false only when \(P\) is true and \(Q\) is false, but true in all other cases.
  • There is no meaningful connection or relationship between the hypothesis \(P\) and the conclusion \(Q\) of an implication \(P \implies Q\) (3 Levin, 2021, p.7).
  • If the hypothesis \(P\) is false, then the implication \(P \implies Q\) is true regardless of the truth value of \(Q\) (3 Levin, 2021, p.9).
  • To prove an implication:
    • Direct prove: assume \(P\), and from it, deduce \(Q\) to be true.
    • Converse and Contrapositive:
      • Converse: \(Q \implies P\), It is not logically equivalent to the original implication \(P \implies Q\).
      • ContraPositive: \(\neg Q \implies \neg P\), It is logically equivalent to the original implication \(P \implies Q\) (either both are true or both are false).

If and Only If

  • For an implication \(P \implies Q\), and its converse \(Q \implies P\), if both are true, then the implication is equivalent to its converse, and the truth is bidirectional and we can write \(P \iff Q\).
  • \(P ⟺ Q\) is logically equivalent to \((P ⟹ Q) ∧ (Q ⟹ P)\).

Necessary and Sufficient

  • \(P\) is necessary for \(Q\) means \(Q \implies P\).
  • \(P\) is sufficient for \(Q\) means \(P \implies Q\).
  • \(P\) is sufficient and necessary for \(Q\) means \(P \iff Q\).

Predicates and Quantifiers

  • Predicate: it is a sentence that contains a variable.
  • Statement: it is a sentence that is either true or false (can be evaluated without ambiguity).
  • Quantifier: it is a symbol that indicates how many elements in a set satisfy a predicate.
    • Universal Quantifier: \(\forall\) read as “for all” or “for every”. example: \(\forall x (x \geq 0)\) means for every \(x\) that is greater than or equal to zero.
    • Existential Quantifier: \(\exists\) read as “there exists” or “there is”. example: \(\exists x (x \geq 0)\) means there is an \(x\) that is greater than or equal to zero.

Sets

  • Set Builder Notation tells the reader to construct the set elements by indicating some conditions that the elements must satisfy.
    • example: \(A = \{x : x \geq 0\}\) means \(A\) is the set of all \(x\) such that \(x\) is greater than or equal to zero.
  • A Perfect Square is defined as \(x = n^2\) where \(n\) is an integer, which includes all possible results of \(n^2\).
  • The Set of Perfect Squares is defined as \(S = \{x : \forall n \in \mathbb{Z}(x = n^2)\}\) which includes all the perfect squares.
  • The Power Set is the set of all possible subsets.
  • The Subset: \(A \subseteq B\) means \(A\) is a subset of \(B\), that is, every element of \(A\) is also an element of \(B\).
  • The Proper Subset: \(A \subset B\) means \(A\) is a subset of \(B\), and \(A\) is not equal to \(B\) (the two sets are not identical).
  • The Intersection of two sets \(A \bigcap B\): is the set of all elements that are in both \(A\) and \(B\).
  • The Union of two sets \(A \bigcup B\): is the set of all elements that are in either \(A\) or \(B\).
  • The Cartesian Product of two sets \(A \times B\): is the set of all ordered pairs \((a, b)\) where \(a \in A\) and \(b \in B\).
  • The Difference of two sets \(A \setminus B\): is the set of all elements that are in \(A\) but not in \(B\).
  • The Complement of a set \(A'\) or \(\bar{A}\): is the set of all elements that are not in \(A\).
  • The Cardinality of a set \(|A|\): is the number of elements in the set.
  • The empty set is a subset of every set.
  • \(A \setminus B = A \cap \bar{B}\).
  • \(\emptyset \cup A = A\). (always).
  • \(\emptyset \cap A = \emptyset\). (always).

4 Counting

Additive and Multiplicative Principles

  • Disjoint: two sets are disjoint if they have no elements in common.
  • Disjoint events: two events are disjoint if they cannot both occur at the same time.
  • Additive Principle:
    • If there are \(n\) ways to do task \(A\) and \(m\) ways to do task \(B\), and the tasks cannot be done at the same time, then there are \(n + m\) ways to do one of the tasks.
    • In another words: if event \(A\) occurs in \(n\) ways, and event \(B\) occurs in m disjoint ways, the the event \(A\) or \(B\) occurs in \(n + m\) ways.
  • Multiplicative Principle:
    • If an event \(A\) occurs in \(m\) ways, and each possibility of \(A\) allows for exactly \(n\) ways for event \(B\) to occur, then the event \(A\) and \(B\) occurs in \(m \times n\) ways.

Counting with sets

  • \(|A ∪ B| = |A| + |B|\) as long as \(|A ∩ B| = \emptyset\) (Additive Principle with sets).
  • If sets are not disjoint, then \(|A ∪ B| = |A| + |B| - |A ∩ B|\) (Cardinality of a union (2 sets), only works for two sets).
  • In fact if the sets are disjoint, then \(|A ∩ B| = \emptyset\) and \(|A ∪ B| = |A| + |B| - 0\).
  • \(|A \times B| = |A| \times |B|\) as long as \(A\) and \(B\) are finite sets.

Principle of Inclusion/Exclusion

  • If the sets are not disjoint, then we can use the Principle of Inclusion/Exclusion to count the number of elements in the union of the sets.
  • When the sets are not disjoint, we need the Cardinality of A, B, and A ∩ B to calculate the Cardinality of A ∪ B, or we must know the exact elements of the sets.
  • If sets are not disjoint, then \(|A ∪ B| = |A| + |B| - |A ∩ B|\) (Cardinality of a union (2 sets)).
  • For 3 non-disjoint sets:
\[ |A ∪ B ∪ C| = |A| + |B| + |C| - |A ∩ B| - |A ∩ C| - |A ∩ C| + |A ∩ B ∩ C| \]
  • The rule gets more complicated as the number of sets increases.

5 Set Theory

  • \(\bar{U} = \emptyset\) where \(U\) is the universal set (complement of the universal set is the empty set).
  • \(\bar{\emptyset} = U\) (complement of the empty set is the universal set).
  • In the natural numbers, the complement of the set of even numbers is the set of odd numbers.
  • Symmetric Difference of two sets \(A \bigoplus B\):
    • Is the set of all elements that are in either \(A\) or \(B\) but not in both.
    • In another words, all elements that are in exactly one of the sets.
    • Also, all elements of A and all elements of B that are not in the intersection of A and B.
    • \(A \oplus B = (A ∪ B) - (A ∩ B)\).

More Resources

References

  1. UoPeople. (2023). MATH1302: Discrete Mathematics. Unit1. Introduction. ↩

  2. Doerr, A., & Levasseur, K. (2022). Applied discrete structures (3rd ed.). licensed under CC BY-NC-SA. Chapter 4: More on Sets. ↩

  3. Levin, O. (2021). Discrete mathematics: An open introduction (3rd ed.). licensed under CC 4.0. Chapter 0: Introduction. ↩↩↩

  4. Levin, O. (2021). Discrete mathematics: An open introduction (3rd ed.). licensed under CC 4.0. Chapter 1: Counting. ↩

  5. Doerr, A., & Levasseur, K. (2022). Applied discrete structures (3rd ed.). licensed under CC BY-NC-SA. Chapter 1: Set Theory. ↩