Chapter 1 - Sets, Relations and Languages

1. Sets

Definition

• A set is a collection of distinct objects
• Examples of sets:
  • The set of integers, denoted by $\mathbb{Z}$
  • The set of non-negative integers (natural numbers), denoted by $\mathbb{N}$
  • The set of truth values, denoted by $B = \{T, F\}$
  • The set of students in this classroom

Set Membership

• The elements or members of a set are the objects comprising it
• If $b$ is an element of a set $L$, then we write $b \in L$
  • ภาษาอังกฤษอ่านว่า a member of!

Ways to Display a Set

There are two ways to display a set:

1. Explicit listing: List the elements belonging to it

   • Example: $B = \{T, F\}$ (set of truth values)

2. Property specification: Specify the properties that characterize the elements

   • Example: The set of even integers: $\{x | x \in \mathbb{Z} \text{ and } x \bmod 2 = 0\}$
   • Alternative notation: $\{x \in \mathbb{Z} | x \bmod 2 = 0\}$
     • อ่านได้ว่า $x$ is an integer where x mod 2 = 0

Set Equality

• Two sets are equal if they have the same elements
  $\boxed{X = Y \text{ iff } (\forall x \in X : x \in Y) \text{ and } (\forall x \in Y : x \in X)}$

ต้องโชว์ each member in x must be in y && each member in y must be in x

Special Sets

• Empty set: A set without any element, denoted by $\emptyset$
• Finite set: A set with finitely many elements
  • A set $A$ is finite if and only if there is a one-to-one correspondence between elements of $A$ and $\{1, 2, \ldots, n\}$ for some natural number $n$ (ยังไม่ต้องเข้าใจตอนนี้ก็ได้)
• Infinite set: A set with infinitely many elements
  • Countably infinite sets: e.g., $\mathbb{N}$
  • Uncountably infinite sets: e.g., $[0, 1]$

Subsets

• Subset: A set $X$ is a subset of a set $Y$, written $X \subseteq Y$, if each element of $X$ is also an element of $Y$
  $\boxed{X \subseteq Y \text{ iff } \forall x \in X : x \in Y}$

• Proper subset: $X$ is a proper subset of $Y$, written $X \subset Y$, if $X$ is a subset of $Y$ but $X$ and $Y$ are not equal
  $\boxed{X \subset Y \text{ iff } X \subseteq Y \text{ and } X \neq Y}$

• Examples:

  • The set of natural numbers $\mathbb{N}$ is a proper subset of the set of integers $\mathbb{Z}$

อันนี้มีให้พิสูจน์เช่นกัน

Basic Facts about Subsets

• For any set $A$:
  • The empty set $\emptyset$ is a subset of $A$: $\emptyset \subseteq A$
  • $A$ is a subset of itself: $A \subseteq A$
• If $A \subseteq B$ and $B \subseteq A$, then $A = B$ (USED FREQUENTLY)

2. Set Operations: Union, Difference, Intersection

Union

• The union of two sets $A, B$ is the set of elements which belongs to at least one of them, denoted $A \cup B$
  $\boxed{\forall x : x \in A \vee x \in B \Leftrightarrow x \in A \cup B}$

Intersection

• The intersection of two sets $A, B$ is the set of elements which belongs to both of them, denoted $A \cap B$
  $\boxed{\forall x : x \in A \wedge x \in B \Leftrightarrow x \in A \cap B}$

Disjoint Sets

• Two sets $A, B$ are disjoint if $A \cap B = \emptyset$

Set Difference

• The set difference of two sets $A, B$ is the set of those elements in $A$ that are not in $B$, denoted $A \setminus B$ (or $A - B$)
  $\boxed{\forall x : x \in A \wedge x \notin B \Leftrightarrow x \in A \setminus B}$

Laws for Set Operations

Idempotent Laws

• $A \cup A = A$
• $A \cap A = A$

Commutative Laws

• $A \cup B = B \cup A$
• $A \cap B = B \cap A$

Associative Laws (The Grouping is Not Important)

• $(A \cup B) \cup C = A \cup (B \cup C)$
• $(A \cap B) \cap C = A \cap (B \cap C)$

General Union and Intersection

Due to these rules, we can define:

• General union: $\bigcup\{A_1, A_2, A_3, \ldots\} = A_1 \cup A_2 \cup A_3 \cup \ldots$
• General intersection: $\bigcap\{A_1, A_2, A_3, \ldots\} = A_1 \cap A_2 \cap A_3 \cap \ldots$

Set Complement

Suppose there is a big set $U$ such that both $A$ and $B$ are subsets of $U$.

• Complement of $A$: $\overline{A} = U \setminus A$
• Complement of $B$: $\overline{B} = U \setminus B$

Then:

• $A \setminus B = A \cap \overline{B}$
• $\overline{A \cap B} = \overline{A} \cup \overline{B}$
• $\overline{A \cup B} = \overline{A} \cap \overline{B}$

Absorption Law

• $A \cup (A \cap B) = A$
• $A \cap (A \cup B) = A$

Distributivity Law

#MidtermExam will show up (proving question) + DeMorgan’s

• $\boxed{A \cup (B \cap C) = (A \cup B) \cap (A \cup C)}$
• $\boxed{A \cap (B \cup C) = (A \cap B) \cup (A \cap C)}$

DeMorgan's Laws

• $\boxed{A \setminus (B \cup C) = (A \setminus B) \cap (A \setminus C)}$
• $\boxed{A \setminus (B \cap C) = (A \setminus B) \cup (A \setminus C)}$

Proof of Distributivity Law

To prove: $A \cup (B \cap C) = (A \cup B) \cap (A \cup C)$

We need to prove both directions:

1. $A \cup (B \cap C) \subseteq (A \cup B) \cap (A \cup C)$
2. $(A \cup B) \cap (A \cup C) \subseteq A \cup (B \cap C)$

Part 1: Consider $x \in A \cup (B \cap C)$. There are two cases:

• Case 1: If $x \in A$, then $x \in A \cup B$ and $x \in A \cup C$, hence $x \in (A \cup B) \cap (A \cup C)$
• Case 2: If $x \in B \cap C$, then $x \in B$ and $x \in C$. Hence $x \in A \cup B$ and $x \in A \cup C$. Therefore $x \in (A \cup B) \cap (A \cup C)$

Hence $A \cup (B \cap C) \subseteq (A \cup B) \cap (A \cup C)$

Part 2: Consider $x \in (A \cup B) \cap (A \cup C)$. So $x \in A \cup B$ and $x \in A \cup C$.
In other words, $(x \in A \text{ or } x \in B)$ and $(x \in A \text{ or } x \in C)$.

• Case 1: If $x \in A$, then $x \in A \cup (B \cap C)$
• Case 2: If $x \notin A$, then $x \in B$ and $x \in C$, i.e., $x \in B \cap C$ and hence $x \in A \cup (B \cap C)$

So in any case $x \in A \cup (B \cap C)$. Hence $(A \cup B) \cap (A \cup C) \subseteq A \cup (B \cap C)$

Proof of DeMorgan's Laws

มาแน่เลยว่ะ ๆ

To prove: $A \setminus (B \cup C) = (A \setminus B) \cap (A \setminus C)$

Let $U$ be a set such that all sets $A, B, C$ are subsets of $U$. We have:

$A \setminus (B \cup C)$
$= A \cap \overline{(B \cup C)}$ (applying the law: $X \setminus Y = X \cap \overline{Y}$)
$= A \cap (\overline{B} \cap \overline{C})$ (DeMorgan's law for complements)
$= (A \cap \overline{B}) \cap (A \cap \overline{C})$ (distributivity)
$= (A \setminus B) \cap (A \setminus C)$ (definition of set difference)

Exercise: Prove $A \setminus (B \cap C) = (A \setminus B) \cup (A \setminus C)$ (EASY)

General Union

• If $S$ is a collection of sets, then $\bigcup S$ is the set whose elements are the elements of the sets in $S$

Examples:

• If $S = \{\{a, b\}, \{c\}, \{a, d\}\}$, then $\bigcup S = \{a, b, c, d\}$
• If $S = \{\{a, b\}, \{c\}, \{a, \{d, a\}\}\}$, then $\bigcup S = \{a, b, c, \{d, a\}\}$

How about $\bigcap$s?

The Power Set

• If $S$ is a set, then $2^S$, called the power set of $S$, is the set of all subsets of $S$

Examples:

• $S = \{a\}$, $2^S = \{\emptyset, \{a\}\}$
• $S = \{a, b\}$, $2^S = \{\emptyset, \{a\}, \{b\}, \{a, b\}\}$

Partition

A partition of a set $S$ is a set $\Pi$ of subsets of $S$ (i.e., $\Pi \subseteq 2^S$) such that:

• Each element of $\Pi$ is not empty
• Distinct members of $\Pi$ are disjoint
• $\bigcup \Pi = S$ (covers the entire set)

Example: $S = \{a, b, c\}$

• $\Pi = \{\{a\}, \{b, c\}\}$ is a partition of $S$
• $A = \{\{a\}, \{a, b\}, \{c\}\}$ is not a partition (overlapping sets)
• $B = \{\{a\}, \{b, c\}, \emptyset\}$ is not a partition (contains empty set)

3. Relations and Functions

Ordered Pairs

• An ordered pair is written as $(a, b)$ where $a$ is the first component and $b$ is the second
• An ordered pair $(a, b)$ can be understood as a set $\{a, \{a, b\}\}$
• Similarly $(b, a)$ as a set $\{b, \{a, b\}\}$

Note: $\{a, b\} = \{b, a\}$ but $(a, b) \neq (b, a)$

Cartesian Product

• The Cartesian product of two sets $A, B$, denoted $A \times B$, is the set of all ordered pairs $(a, b)$ with $a \in A, b \in B$
  $\boxed{A \times B = \{(a, b) | a \in A, b \in B\}}$

Examples:

• $\{a, b\} \times \{a\} = \{(a, a), (b, a)\}$
• The plane can be represented as a Cartesian product $\mathbb{R} \times \mathbb{R}$ where $\mathbb{R}$ is the set of all real numbers

Functions

• A map or function from a set $A$ to a set $B$, denoted $f : A \to B$, is an assignment to each element $a \in A$ a single element, denoted by $f(a)$, in $B$

Function Components:

• $A$ is called the domain of $f$
• $B$ is called the co-domain of $f$
• $f(a)$ is called the image of $a$ under $f$
• The range of $f$ is denoted by $f(A) = \{f(a) | a \in A\}$
• For $A' \subseteq A$, $f(A') = \{f(a) | a \in A'\}$ is called the image of $A'$ under $f$

Example: $+ : \mathbb{N} \times \mathbb{N} \to \mathbb{N}$ where $+(1, 2) = 3$

Function Exercises

1. If $A = \emptyset$, how many possible functions are there from $A$ to $B$?
2. If $B = \emptyset$, how many functions are there from $A$ to $B$?
3. If $A$ contains exactly one element, how many functions are there from $A$ to $B$?

Types of Functions

• A function $f : A \to B$ is one-to-one (injective) if for any two distinct elements $a, a' \in A$, $f(a) \neq f(a')$
  
• A function $f : A \to B$ is onto $B$ (surjective) if $B = f(A)$
  
• A function $f : A \to B$ is a bijection between $A$ and $B$ if it is both one-to-one and onto $B$
  
• Let $A$ and $B$ be two finite sets. $A$ and $B$ have the same number of elements iff there is a bijection between $A$ and $B$

Function Composition

• Given a function $f : A \to B$ and $g : B \to C$, the composition $f \circ g : A \to C$ is defined by:
• $\boxed{(f \circ g)(a) = g(f(a))}$

Example:

• $f : \mathbb{N} \times \mathbb{N} \to \mathbb{N}$ where $f(m, n) = m + n$
• $g : \mathbb{N} \to \mathbb{N}$ where $g(k) = 2k$
• $(f \circ g)(m, n) = 2(m + n)$

Relations

• A binary relation on two sets $A, B$ is a subset of $A \times B$
• Example: The greater or equal relation $\geq$ in the set of integers: $R = \{(m, n) | m \geq n\} \subseteq \mathbb{Z} \times \mathbb{Z}$

n-tuples and n-ary Relations

• An ordered n-tuple is written as $(a_1, a_2, \ldots, a_n)$ where $a_i$ is the $i$-th component
• The n-fold Cartesian product of sets $A_1, \ldots, A_n$, denoted by $A_1 \times \cdots \times A_n$, is the set of all ordered $n$-tuples with $a_i \in A_i$ for $i = 1, \ldots, n$
• An n-ary relation on sets $A_1, \ldots, A_n$ is a subset of $A_1 \times \cdots \times A_n$

Terminology:

• Binary = 2-ary (double = 2-tuple)
• Ternary = 3-ary (triple = 3-tuple)
• Quaternary = 4-ary (quadruple = 4-tuple)

Functions vs Relations

• A function is a special relation
• A function from a set $A$ to a set $B$ is a binary relation $R$ on $A, B$ such that:
  • For each $a \in A$ there is exactly one ordered pair in $R$ with first component $a$

Tip: How to tell if $R$ is a function:

• There must be only one outgoing link for each node on the left-hand side

Relation Operations

• A binary relation $R \subseteq A \times B$ has an inverse $R^{-1} \subseteq B \times A$ defined by:

• $\boxed{(b, a) \in R^{-1} \text{ if and only if } (a, b) \in R}$

• For binary relations $Q \subseteq A \times B$ and $R \subseteq B \times C$, the composition $Q \circ R$ is defined by:

• $\boxed{Q \circ R = \{(a, c) | \exists b \in B \text{ such that } (a, b) \in Q \text{ and } (b, c) \in R\}}$

Exercise: Show that if $f : A \to B$ is a bijection, then $f^{-1}$ is also a bijection from $B$ to $A$.

Types of Relations

For a relation $R \subseteq A \times A$:

• Reflexive: if for each $a \in A$, $(a, a) \in R$ (self loops)
• Symmetric: if $(a, b) \in R$ whenever $(b, a) \in R$ (back and forth)
• Transitive: if whenever $(a, b) \in R$ and $(b, c) \in R$ then $(a, c) \in R$
• Equivalence relation: if it is reflexive, transitive, and symmetric

Examples of relation types:

• Married relationship: symmetric
• Ancestor relationship: transitive
• Same nationality: equivalence relation

Equivalence Classes

• Let $R$ be an equivalence relation on a set $A$. For each $a \in A$, the equivalence class of $a$ with respect to $R$ is:
• $\boxed{[a]_R = \{b | (a, b) \in R\}}$
• When the relation $R$ is understood, we simply write $[a]$ for $[a]_R$

Property: Let $R$ be an equivalence relation on a set $A$. Then for any two elements $a, b \in A$, either $[a]_R = [b]_R$ or $[a]_R, [b]_R$ are disjoint.

• A modulo R: $A/R = \{[a]_R | a \in A\}$

Theorem: Let $R$ be an equivalence relation on a set $A$. Then $A/R$ is a partition of $A$.

Example of Equivalence Relations

• Let $\mathbb{Z}^+$ be the set of positive integers
• Define an equivalence relation $\sim \subseteq (\mathbb{Z}^+ \times \mathbb{Z}^+) \times (\mathbb{Z}^+ \times \mathbb{Z}^+)$ as follows:
• $(p, q) \sim (r, s)$ iff $ps = qr$
• The $\sim$ is an equivalence relation characterizing the rational numbers
• The set $(\mathbb{Z}^+ \times \mathbb{Z}^+)/\sim$ is the set of rational numbers

Orders

• A relation $R \subseteq A \times A$ is antisymmetric if whenever $(a, b) \in R$ and $a \neq b$ then $(b, a) \notin R$
• A relation that is reflexive, transitive and antisymmetric is called a partial order
• A partial order $R \subseteq A \times A$ is called a total order if for all $a, b \in A$, either $(a, b) \in R$ or $(b, a) \in R$

Paths and Cycles

• A path from $a$ to $b$ in a binary relation $R \subseteq A \times A$ is a sequence $a_1, \ldots, a_n, n \geq 1$ such that:
  • $a = a_1$, $b = a_n$
  • For each $i \in \{1, \ldots, n-1\}$, $(a_i, a_{i+1}) \in R$
• A path $a_1, \ldots, a_n$ is a cycle if $a_1 = a_n$ and all $a_i

4. Finite Sets and Infinite Sets

Counting

• Equinumerous sets: Two sets $A, B$ are equinumerous if there is a bijection $f : A \to B$
• Cardinality: We say that the cardinality of $A$ is $n$ if $A$ is equinumerous with the set $\{1,..., n\}$
• Countably infinite: $A$ is countably infinite if it is equinumerous with the set of natural numbers $\mathbb{N} = \{0, 1, 2,...\}$
• Uncountably infinite: $A$ is uncountably infinite if it is infinite and not equinumerous with the set of natural numbers

Think of cardinality as a way to measure "how many" elements are in a set. It's like counting, but extended to infinite sets too.

Examples and Properties

• Positive odd numbers: $A = \{1, 3, 5, 7, ...\}$ is countably infinite
  • Can map each element to a distinct integer using $f(n) = 2n - 1$
• Positive even numbers: $B = \{2, 4, 6, 8, ...\}$ is countably infinite
  • Can map using $f(n) = 2n$

Key Theorems

• Every subset of a finite set is finite
• Every subset of a countably infinite set is finite or countably infinite
• The set $\mathbb{N} \times \mathbb{N}$ is countably infinite (using dovetailing technique)
• Union theorem: The union of countably infinite collection of countably infinite sets is again countably infinite

The dovetailing technique is like systematically traversing a grid - you can count all pairs $(i,j)$ by going diagonally through the infinite grid.

5. Three Fundamental Proof Techniques

1. Principle of Mathematical Induction

Statement: Let $A$ be a set of natural numbers such that:

1. $0 \in A$
2. For each natural number $n$, if $\{0, 1,..., n\} \subseteq A$ then $n + 1 \in A$

Then $A = \mathbb{N}$

Mathematical induction is like climbing an infinite ladder - if you can get on the first rung (base case) and you can always step from one rung to the next (inductive step), then you can reach any rung.

Example 1: Sum Formula

Prove: $\boxed{1 + 2 + \cdots + n = \frac{n(n + 1)}{2}}$

Base case: $n = 1$: $1 = \frac{1(1 + 1)}{2} = 1$ ✓

Inductive step: Assume true for $n$, prove for $n + 1$:
$1 + 2 + \cdots + n + (n+1) = (1 + 2 + \cdots + n) + (n+1)$
$= \frac{n(n+1)}{2} + (n+1) \text{ (by induction hypothesis)}$
$= \frac{n(n+1) + 2(n+1)}{2} = \frac{(n+1)(n+2)}{2}$

Example 2: Power Set Cardinality

Prove: For any finite set $A$, $\boxed{|2^A| = 2^{|A|}}$

Base case: $|A| = 0$, then $A = \emptyset$, and $2^A = \{\emptyset\}$, so $|2^A| = 1 = 2^0$

Inductive step: Let $|A| = n + 1$. Pick element $a \in A$, let $B = A - \{a\}$.

• By induction hypothesis: $|2^B| = 2^n$
• The power set $2^A$ can be partitioned into:
  • Sets not containing $a$: these are exactly $2^B$
  • Sets containing $a$: these are $\{C \cup \{a\} : C \in 2^B\}$
• Therefore: $|2^A| = |2^B| + |2^B| = 2 \cdot 2^n = 2^{n+1}$

2. The Pigeonhole Principle

Statement: $\boxed{\text{If } A, B \text{ are finite sets and } |A| > |B|, \text{ then there is no one-to-one function from } A \text{ to } B}$

If you have more pigeons than pigeonholes, at least one pigeonhole must contain more than one pigeon.

Exercises

• 79 students, 70 chairs: Is it possible to give each student a separate chair?

  • Answer: No, by pigeonhole principle since $79 > 70$

• Society problem: $5 \times 10^6$ men and $5 \times 10^6 + 1$ women. Can each woman get her own man?

  • Answer: No, since there are more women than men

Proof by Induction

Base case: $|B| = 0$, so $B = \emptyset$. No function $f: A \to B$ exists at all.

Inductive hypothesis: Assume true when $|B| \leq n$

Inductive step: Let $|B| = n + 1$ and $|A| > |B|$. Pick $a \in A$.

• If another element $a' \in A$ satisfies $f(a) = f(a')$, then $f$ is not one-to-one
• Otherwise, consider $g: A - \{a\} \to B - \{f(a)\}$ that agrees with $f$
• Since $|A - \{a\}| = |A| - 1 > |B| - 1 = |B - \{f(a)\}|$, by induction hypothesis $g$ is not one-to-one
• Therefore $f$ is not one-to-one

Application: Path Length Theorem

Theorem: Let $R$ be a binary relation on a finite set $A$, and let $a, b \in A$. If there is a path from $a$ to $b$ in $R$, then there is a path of length at most $|A|$.

Proof: If the shortest path has length $> |A|$, then by pigeonhole principle, some element repeats in the path. We can remove the cycle to get a shorter path, contradiction.

3. The Diagonalization Principle

อาจจะให้โชว์ D เฉย ๆ นะ

Statement: Let $R$ be a binary relation on a set $A$, and let:

• $D = \{a : a \in A \text{ and } (a, a) \notin R\}$ (diagonal set)
• For each $a \in A$: $R_a = \{b : b \in A \text{ and } (a, b) \in R\}$ (row set)

Then $\boxed{D \text{ is distinct from each } R_a}$

Imagine $R$ as a grid/table where rows and columns are labeled with elements of $A$. The diagonal set $D$ is constructed by "flipping" the main diagonal - if there's a cross, remove it; if there's no cross, add one. This new diagonal will be different from every row.

Example

Let $A = \{1, 2, 3, 4, 5\}$ and
$R = \{(1, 3), (2, 4), (3, 5), (5, 1), (2, 3), (1, 1), (4, 2), (4, 4)\}$

Finding the sets:

• $R_1 = \{1, 3\}$ (elements related to 1)
• $R_2 = \{3, 4\}$ (elements related to 2)
• $R_3 = \{5\}$ (elements related to 3)
• $R_4 = \{2, 4\}$ (elements related to 4)
• $R_5 = \{1\}$ (elements related to 5)
• $D = \{2, 3, 5\}$ (elements not related to themselves)

You can verify that $D$ doesn't match any $R_i$.

Variations

• Column sets: $C_a = \{b : b \in A \text{ and } (b, a) \in R\}$

  • Would the diagonal principle still hold? (Exercise for consideration)

• Complement diagonal: $D' = \{a : a \in A \text{ and } (a, a) \in R\}$

  • Would the diagonal principle still hold? (Exercise for consideration)

Major Application: Uncountability of Power Set

Theorem: $\boxed{\text{The set } 2^{\mathbb{N}} \text{ is uncountably infinite}}$

Proof by contradiction:

1. Assume $2^{\mathbb{N}}$ is countably infinite
2. Then there exists a bijection $f: \mathbb{N} \to 2^{\mathbb{N}}$
3. Define relation $R = \{(n, m) : m \in f(n)\}$
4. By diagonalization principle, the diagonal set $D = \{n : n \notin f(n)\}$ is different from every $R_n = f(n)$
5. But this means $D$ is not in the range of $f$, contradicting that $f$ is onto
6. Therefore, $2^{\mathbb{N}}$ is uncountably infinite

This proof shows there are "more" subsets of natural numbers than there are natural numbers themselves - a profound result about the nature of infinity.

Summary

These three proof techniques are fundamental tools in mathematics:

• Mathematical Induction: Proves statements about all natural numbers by establishing a base case and inductive step
• Pigeonhole Principle: Shows impossibility of certain mappings when there are more objects than containers
• Diagonalization Principle: Constructs objects that differ from all objects in a given collection, often used to prove impossibility results

Each technique has its own domain of application and together they form a powerful toolkit for mathematical reasoning.

6. Alphabet and Languages

[This section would be covered in subsequent pages of the document]