Elements of the Theory of Computation - Chapter 1 Sets, Relations, and Languages



  • an unordered collection of elements

subsets and proper subsets

  • Subset notation: $\subseteq$

  • Proper subset $\subset $

Set Operations and Its Identities

  • Union, Intersection, Difference, Symmetric difference, complement
  • Commutative Law, Associative Law, Distributive law, Absorption, DeMorgan’s Law, Idempotent law

Power Set

  • $2^S$ = set of all subset of $S$


A partition of nonempty set $A$ is a subset $\sqcap$ of $2^A$ such that

  1. $\phi\notin \sqcap $
  2. $\forall S,T \in \sqcap.$ and $S\neq T, S \cap T = \phi$
  3. $\cup \sqcap = A$

Relations and Functions

Ordered Pair and Binary Relation

  • Ordered Pair: $(a,b)$

  • Cartesian Product: $A \times B$

  • Binary Relation $A$ and $B$

Ordered Tuple and n-ary Relation

Operations of Relations

  • Inverse

  • Composition


Definition: A function $f: A\rightarrow B$ must satisfy:

  • $f \subseteq A \times B$
  • $\forall a \in A, \exists$ exactly one $b \in B$ with $(a,b) \in f$

Note: We write $(a,b)\in f$ as $f(a) = b$

  • one-to-one function: $\forall a,b \in A \land a \neq b \Rightarrow f(a) \neq f(b)$
  • onto function: $\forall b \in B, \exists a\in A$ such that $f(a)=b$
  • bijection function: one-to-one + onto

Special Types of Binary Relations

Representation of Relations

  • Directed graph: node, edge, path
  • Matrix: Adjacency matrix

Properties of Relations ($R \subseteq A\times A$)

  • reflexive: $\forall a\in A \Rightarrow (a,a) \in R$
  • symmetric: $(a,b) \in R \land a \neq b \Rightarrow (b,a)\in R$, antisymmetric: $(a,b) \in R \Rightarrow (b,a) \notin R$
  • transitive: $(a.b)\in R, (b,c)\in R \Rightarrow (a,c)\in R$

Equivalence Relation

  • reflexive, symmetric, transitive

  • equivalence classes

Theorem Let $R$ be an equivalence relation on a nonempty set $A$. Then the equivalence classes of $R$ constitute a partition of $A$.

Partial Order

  • reflexive, symmetric, transitive
  • total order
  • minimal element and maximal element

Finite and Infinite sets


  • Sets $A$ and $B$ equinumerous $\Leftrightarrow \exists$ bijection $f:A\rightarrow B$
  • Cardinality and generalized Cardinality
  • Finite and Infinite sets

Countable and Uncountable Infinite

  • A set is said to be countably infinite $\Leftrightarrow$ it is equinumerous with $\mathbb{N}$
  • S is an uncountable set $\Leftrightarrow |S|>|\mathbb{N}|$
  • The union of a countably infinite collection of countably infinite sets is countably infinite.

Example: Show that $\mathbb{N} \times \mathbb{N}$ is countably infinite.

Theorem: $|\mathbb{R}|>|\mathbb{N}|$ (diagonalization)

Question: Is $|\mathbb{R}| > |(0,1)|$?

Continuum Hypothesis

$|\mathbb{N}|=\aleph_0, |\mathbb{R}|=\aleph_1$