Theory of Computation: Sets

• The material is an introduction to the Theory of Computation
• References the book "Introduction to the Theory of Computation" (3rd Edition) by Michael Sipser
• Outlines mathematical preliminaries, including sets, sequences, functions, graphs, boolean logic, proofs, and languages

Sets

• A collection of objects.
• $a \in A$ indicates "a" is a member of set A.
• $a \notin A$ indicates "a" is not a member of set A.
• $A = {1, 2, 3}$: A is a set containing the elements 1, 2, and 3
• $B = {x | x \text{ é um inteiro par}}$: B is the set of all even integers
• $C = {1, 2, 3,...}$: C is the set of all positive integers

Common Sets

• $\mathbb{N} = {1, 2, 3,...}$: Set of natural numbers
• $\mathbb{Z} = {..., -2, -1, 0, 1, 2,...}$: Set of integers
• $\mathbb{R}$: Set of real numbers
• $\emptyset = {}$: Empty set

Subsets

• A is a subset of B ($A \subseteq B$) if every member of A is also a member of B.
• A is a proper subset of B ($A \subset B$) if A is a subset of B and $A \neq B$.

Set Operations

• Union: $A \cup B = {x | x \in A \text{ ou } x \in B}$
• Intersection: $A \cap B = {x | x \in A \text{ e } x \in B}$
• Difference: $A - B = {x | x \in A \text{ e } x \notin B}$
• Complement: $\overline{A} = {x | x \notin A}$
• Power Set: $P(A) = {B | B \subseteq A}$
• Cartesian Product: $A \times B = {(a, b) | a \in A \text{ e } b \in B}$

Cardinality

• The cardinality of a set A ($|A|$) is the number of elements in A.
• For $A = {1, 2, 3}$, $|A| = 3$.

Sequences and Tuples

• A sequence is an ordered list of objects, denoted as $(a_1, a_2,..., a_n)$ with length n.
• A tuple is a finite sequence of objects, with a k-tuple containing k elements.

Cartesian Product

• The Cartesian product of k sets $A_1, A_2,..., A_k$ is the set of all k-tuples $(a_1, a_2,..., a_k)$ where $a_i \in A_i$ for $i = 1, 2,..., k$.
• Denoted as: $A_1 \times A_2 \times... \times A_k$

Functions and Relations

• A function takes an input and produces an output
• Notation for f being a function from A to B: $f: A \rightarrow B$
• A is the domain, B is the codomain, and for $a \in A$, $f(a)$ is the image of a under f.
• The image of f is the set ${f(a) | a \in A}$.

Types of Functions

• Injective (one-to-one): If $f(a_1) = f(a_2)$, then $a_1 = a_2$
• Surjective (onto): For every $b \in B$, there exists an $a \in A$ such that $f(a) = b$
• Bijective (one-to-one and onto): It is both injective and surjective

Relations

• A relation is a set of tuples.
• A binary relation between A and B is a subset of $A \times B$.

Graphs

• A graph is a set of nodes (vertices) connected by edges.
• Represented as $G = (V, E)$, where V is the set of vertices and E is the set of edges.

Types of Graphs

• Undirected: Edges have no direction
• Directed: Edges have a direction
• Labeled: Vertices and/or edges have labels

Graph Terminology

• Degree: Number of edges incident to a vertex
• Path: Sequence of vertices connected by edges
• Cycle: A path that starts and ends at the same vertex
• Connected Graph: There is a path between any pair of vertices
• Tree: Connected graph without cycles

Boolean Logic

• A system for manipulating truth values (true and false).
• Negation: $\neg P$ (NOT P)
• Conjunction: $P \land Q$ (P AND Q)
• Disjunction: $P \lor Q$ (P OR Q)
• Implication: $P \rightarrow Q$ (P IMPLIES Q)
• Equivalence: $P \leftrightarrow Q$ (P IFF Q)

Truth Tables

Proofs

• Deduction: Conclusion is a logical consequence of premises
• Contradiction: Assume the conclusion is false and show it leads to a contradiction
• Induction: Used for proving statements about integers

Mathematical Induction

• Base Case: Show the statement is true for $n = 1$
• Inductive Step: Assume the statement is true for $n = k$ and show that it is true for $n = k + 1$

Strings and Languages

• An alphabet is a finite set of symbols.
• A string is a finite sequence of symbols from an alphabet.
• The empty string is denoted by $\epsilon$.
• The length of a string w is the number of symbols in w, denoted by $|w|$.

String Operations

• Concatenation: Appending strings: $w_1w_2$
• Reverse: Reversing the string: $w^R$

Languages

• A language is a set of strings over an alphabet.