Notes/Discrete Structures/Mathematical Data Structures.md

type
theoretical

Sets

A set is an unordered collection of unique objects (elements) with no duplicates.

Notation

• x \in A: "x is an element of set A."
• x \notin A: "x is not an element of set A."

Intervals of \mathbb{R}

An interval is a subset of \mathbb{R} (the real numbers) defined by two endpoints a and b. Any real number between a and b belongs to the interval.

Cardinality

The cardinality of a set S is the number of elements it contains, denoted |S|.

• Finite Set: A set with a finite number of elements. Example: S = \{a, b, c\}, |S| = 3.
• Infinite Set: A set that is not finite. Example: \mathbb{N}, \mathbb{Z}, \mathbb{R}.
• Power Set: For a finite set S, the cardinality of its power set P(S) (set of all subsets of S) is 2^{|S|}.

Example: For S = \{a, b, c\}, P(S) contains 8 = 2^3 subsets.

---

Set Operations

Let U be the universal set, and let A and B be subsets of U:

• Union: A \cup B = \{x \mid x \in A \lor x \in B\}
• Intersection: A \cap B = \{x \mid x \in A \land x \in B\}
• Set Difference: A \setminus B = \{x \mid x \in A \land x \notin B\}
• Complement: \bar{A} = U \setminus A, the set of all elements not in A.

---

Proof Styles for Set Properties

Annotated Linear Proof (ALP)

A chain-of-equivalences proof involves showing the equivalence of two sets step by step.

Example: Prove A \cup (B \cup C) = (A \cup B) \cup C.

• Start from x \in A \cup (B \cup C) and simplify:

  
  x \in A \cup (B \cup C) \iff x \in A \lor (x \in B \lor x \in C) \iff (x \in A \lor x \in B) \lor x \in C \iff x \in (A \cup B) \cup C.
  

• Conclude that the left-hand side equals the right-hand side.

---

Sequences

A sequence is an ordered list of objects where repetition is allowed, and the order matters.

Examples

1. Finite sequence: 1, 2, 3, 5, 7 (length 5).
2. Infinite sequence: 0, 2, 4, 6, \ldots (continues indefinitely).
3. A sequence differs from a set: 1, 2, 3 is not the same as 3, 2, 1.

Specifying Sequences

1. Recursive Definition:
   • Example: s_0 = 3, s_n = 2 \cdot s_{n-1} + 7, defines 3, 13, 33, \ldots.
2. Explicit Definition:
   • Example: s_n = n^2 defines 0, 1, 4, 9, 16, \ldots.

---

Characteristic Function

The characteristic function of a set A \subseteq U is a function f_A : U \to \{0, 1\}:

f_A(x) =
\begin{cases} 
1, & \text{if } x \in A, \\
0, & \text{if } x \notin A.
\end{cases}

Purpose

Characteristic functions represent sets mathematically and are useful for computations.

Example:

• U = \{a, b, c, d, e\}, A = \{b, d\}.
• Representation of U: (1, 1, 1, 1, 1).
• Representation of A: (0, 1, 0, 1, 0).

---

Strings and Languages

Formal Languages

1. Alphabet (\Sigma): A non-empty set of symbols (letters).
2. Word (String): A finite sequence of symbols from \Sigma.
   • Example: \Sigma = \{a, b\}, string: babab.
3. Empty String (\epsilon): A string with no symbols (|\epsilon| = 0).
4. Language (L): A subset of \Sigma^*, the set of all possible strings over \Sigma. Regex. Used for Pattern matching

Regular Sets and Expressions

1. \alpha \cdot \beta (concatenation): Combine two sets of strings.
2. \alpha | \beta (union): Combine strings from either set.
3. \alpha^* (Kleene star): All strings formed by repeatedly concatenating elements of \alpha.

Example:

• Let L correspond to (a | b)^*(c | \epsilon).
  • True/False:
    • abbac \in L: True.
    • abccc \in L: False.
    • abaa \in L: False.

---

Integers

Primes

• Prime Number: A positive integer greater than 1 with only two divisors: 1 and itself.
  • Examples: 2, 3, 5, 7.
• Euclid's Theorem: There are infinitely many primes.

Proof Sketch:

1. Assume a finite list of primes p_1, p_2, \ldots, p_n.
2. Let q = (p_1 \cdot p_2 \cdot \ldots \cdot p_n) + 1.
3. If q is prime, it’s not in the list.
4. If q is not prime, it must be divisible by some prime not in the list.

Prime Factorization

Every integer n > 1 can be uniquely expressed as a product of primes:

n = p_1^{k_1} \cdot p_2^{k_2} \cdot \ldots \cdot p_s^{k_s}.

Examples:

1. 60 = 2^2 \cdot 3 \cdot 5.
2. 168 = 2^3 \cdot 3 \cdot 7.

---

Matrices and Boolean Operations

Boolean Operations

• OR (\lor): a \lor b = \max(a, b).
• AND (\land): a \land b = \min(a, b).

Example: For a, b \in \{0, 1\}:

• 1 \lor 0 = 1.
• 1 \land 0 = 0.

---

Mathematical Structures

Arity and Notation

• Arity: The number of arguments an operation takes.
  • Unary: Takes one argument (e.g., complement of a set).
  • Binary: Takes two arguments (e.g., addition: x + y).
  • Nullary: Takes no arguments (e.g., constant: 1).

Prefix/Infix/Postfix Notation:

• Prefix: Operator first (e.g., + x y).
• Infix: Operator between arguments (e.g., x + y).
• Postfix: Operator last (e.g., x y +).