Basic Structures: Sets, Functions, Sequences, Sums, and Matrices

Sets

• Sets are fundamental building blocks in discrete mathematics, crucial for counting and implemented in programming languages through set operations.

• Set theory is a significant branch of mathematics with various axiomatic systems, employing a naïve approach in this context.

Definition

• A set is an unordered collection of objects, referred to as elements or members.

• Notation:

  • $a ∈ A$ denotes that $a$ is an element of set $A$.

  • $a \notin A$ indicates $a$ is not a member of $A$.

Describing Sets

Roster Method

• Listing elements within braces: e.g., $S = {a, b, c, d}$.

• Order is not important: ${a, b, c, d} = {b, c, a, d}$.

• Duplicate elements do not change the set: ${a, b, c, d} = {a, b, c, b, c, d}$.

• Ellipses can represent clear patterns: $S = {a, b, c, d, …, z}$.

Examples

• Vowels: $V = {a, e, i, o, u}$.

• Odd positive integers less than 10: $O = {1, 3, 5, 7, 9}$.

• Positive integers less than 100: $S = {1, 2, 3, …, 99}$.

• Integers less than 0: $S = {…, -3, -2, -1}$.

Important Sets

• $\mathbb{N}$ = Natural numbers = ${0, 1, 2, 3, …}$

• $\mathbb{Z}$ = Integers = ${…, -3, -2, -1, 0, 1, 2, 3, …}$

• $\mathbb{Z^+}$ = Positive integers = ${1, 2, 3, …}$

• $\mathbb{R}$ = Real numbers

• $\mathbb{R^+}$ = Positive real numbers

• $\mathbb{C}$ = Complex numbers

• $\mathbb{Q}$ = Rational numbers

Set-Builder Notation

• Specifies properties members must satisfy:

  • $S = {x | x \text{ is a positive integer less than 100} }$

  • $O = {x | x \text{ is an odd positive integer less than 10} }$

  • O = {x ∈ \mathbb{Z^+} | x \text{ is odd and } x < 10}

• Using a predicate: $S = {x | P(x)}$ (e.g., ${x | Prime(x)}$).

• Positive rational numbers: $\mathbb{Q^+} = {x ∈ \mathbb{R} | x = p/q, \text{ for some positive integers } p, q}$

Interval Notation

• Closed interval: $[a, b] = {x | a ≤ x ≤ b}$

• Half-open interval: [a, b) = {x | a ≤ x < b}

• Half-open interval: (a, b] = {x | a < x ≤ b}

• Open interval: (a, b) = {x | a < x < b}

Universal and Empty Sets

• Universal set $U$ contains everything under consideration, either implicit or explicitly stated, depending on context.

• Empty set $∅$ contains no elements, also represented as ${}$.

Russell’s Paradox

• If $S$ is the set of all sets not members of themselves, the question "Is $S$ a member of itself?" leads to a paradox.

• Related to the barber paradox: Henry shaves all who don't shave themselves. Does Henry shave himself?

Key Reminders

• Sets can contain sets: ${{1, 2, 3}, a, {b, c}}$, ${N, Z, Q, R}$.

• Empty set vs. set containing the empty set: $∅ ≠ {∅}$.

Set Equality

• Two sets are equal if they contain the same elements: $A = B ↔ ∀x(x ∈ A ↔ x ∈ B)$.

• Examples: ${1, 3, 5} = {3, 5, 1}$, ${1, 5, 5, 5, 3, 3, 1} = {1, 3, 5}$.

Subsets

• Set $A$ is a subset of $B$ if every element of $A$ is also in $B$: $A ⊆ B ↔ ∀x(x ∈ A → x ∈ B)$.

• $∅ ⊆ S$ for every set $S$.

• $S ⊆ S$ for every set $S$.

Showing Subsets

• To prove $A ⊆ B$, show if $x ∈ A$, then $x ∈ B$.

• To prove $A \nsubseteq B$, find an $x ∈ A$ such that $x \notin B$.

Equality of Sets Revisited

• $A = B$ if and only if $\forall x (x \in A \leftrightarrow x \in B)$.

• Equivalently, $A = B$ if and only if $A ⊆ B$ and $B ⊆ A$.

Proper Subsets

• If $A ⊆ B$ but $A ≠ B$, then $A$ is a proper subset of $B$, denoted by $A ⊂ B$.

• $A ⊂ B$ if and only if $\forall x (x \in A \rightarrow x \in B) \land \exists x (x \in B \land x \notin A)$.

Set Cardinality

• If $S$ has exactly $n$ distinct elements, it is finite. Otherwise, it is infinite.

• Cardinality of a finite set $A$, denoted by $|A|$, is the number of distinct elements in $A$.

• Examples: $|∅| = 0$, alphabet $|S| = 26$, $|{1, 2, 3}| = 3$, $|{∅}| = 1$.

Power Sets

• Power set $P(A)$ is the set of all subsets of $A$.

• Example: If $A = {a, b}$, then $P(A) = {∅, {a}, {b}, {a, b}}$.

• If $|A| = n$, then $|P(A)| = 2^n$.

Tuples

• Ordered $n$-tuple $(a<em>1, a</em>2, …, a_n)$ is an ordered collection.

• Two $n$-tuples are equal if corresponding elements are equal.

• 2-tuples are ordered pairs: $(a, b) = (c, d)$ if and only if $a = c$ and $b = d$.

Cartesian Product

• Cartesian product of $A$ and $B$ is $A × B = {(a, b) | a ∈ A \text{ and } b ∈ B}$.

• Example: If $A = {a, b}$ and $B = {1, 2, 3}$, then $A × B = {(a, 1), (a, 2), (a, 3), (b, 1), (b, 2), (b, 3)}$.

• A relation from $A$ to $B$ is a subset of $A × B$.

Cartesian Product of Multiple Sets

• $A<em>1 × A</em>2 × … × A<em>n = {(a</em>1, a<em>2, …, a</em>n) | a<em>i ∈ A</em>i \text{ for } i = 1, …, n}$.

• Example: If $A = {0, 1}$, $B = {1, 2}$, $C = {0, 1, 2}$, then $A × B × C = {(0, 1, 0), (0, 1, 1), (0, 1, 2), (0, 2, 0), (0, 2, 1), (0, 2, 2), (1, 1, 0), (1, 1, 1), (1, 1, 2), (1, 2, 0), (1, 2, 1), (1, 2, 2)}$.

Truth Sets of Quantifiers

• Truth set of predicate $P(x)$ over domain $D$ is the set of elements in $D$ for which $P(x)$ is true.

• Example: If $P(x)$ is $|x| = 1$ and the domain is integers, the truth set is ${-1, 1}$.

Set Operations

• Set operations include union, intersection, complementation, and difference.

Boolean Algebra

• Both propositional calculus and set theory are instances of Boolean Algebra.

• Set theory operators are analogous to propositional calculus operators within a universal set $U$.

Union

• The union of sets $A$ and $B$, denoted by $A ∪ B$, is ${x | x ∈ A \text{ or } x ∈ B}$.

• Example: ${1, 2, 3} ∪ {3, 4, 5} = {1, 2, 3, 4, 5}$.

Intersection

• The intersection of sets $A$ and $B$, denoted by $A ∩ B$, is ${x | x ∈ A \text{ and } x ∈ B}$.

• If the intersection is empty, $A$ and $B$ are disjoint.

• Example: ${1, 2, 3} ∩ {3, 4, 5} = {3}$, ${1, 2, 3} ∩ {4, 5, 6} = ∅$.

Complement

• The complement of set $A$, denoted by $\overline{A}$, is ${x ∈ U | x \notin A}$.

• Example: If $U$ is positive integers less than 100, then the complement of {x | x > 70} is ${x | x ≤ 70}$.

Difference

• The difference of $A$ and $B$, denoted by $A – B$, is ${x | x ∈ A \text{ and } x \notin B} = A ∩ \overline{B}$.

Cardinality of Union

• Inclusion-Exclusion Principle: $|A ∪ B| = |A| + |B| - |A ∩ B|$.

• To count students in math or CS, add math majors and CS majors, then subtract joint majors.

Review Questions

• Given $U = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10}$, $A = {1, 2, 3, 4, 5}$, $B = {4, 5, 6, 7, 8}$:

  • $A ∪ B = {1, 2, 3, 4, 5, 6, 7, 8}$

  • $A ∩ B = {4, 5}$

  • $\overline{A} = {0, 6, 7, 8, 9, 10}$

  • $\overline{B} = {0, 1, 2, 3, 9, 10}$

  • $A – B = {1, 2, 3}$

  • $B – A = {6, 7, 8}$

Symmetric Difference (Optional)

• The symmetric difference of $A$ and $B$, denoted by $A \oplus B$, is $(A - B) ∪ (B - A)$.

• Example: With the same $A$ and $B$ as above, $A \oplus B = {1, 2, 3, 6, 7, 8}$.

Set Identities

• Identity laws, domination laws, idempotent laws, complementation law, commutative laws, associative laws, distributive laws, De Morgan's laws, absorption laws, complement laws.

• Examples:

  • $A \cup \emptyset = A$ (Identity Law)

  • $A \cap U = A$ (Identity Law)

  • $A \cup U = U$ (Domination Law)

  • $A \cap \emptyset = \emptyset$ (Domination Law)

  • $A \cup A = A$ (Idempotent Law)

  • $A \cap A = A$ (Idempotent Law)

  • $\overline{(\overline{A})} = A$ (Complementation Law)

  • $A \cup B = B \cup A$ (Commutative Law)

  • $A \cap B = B \cap A$ (Commutative Law)

  • $A \cup (B \cup C) = (A \cup B) \cup C$ (Associative Law)

  • $A \cap (B \cap C) = (A \cap B) \cap C$ (Associative Law)

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

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

  • $\overline{A \cup B} = \overline{A} \cap \overline{B}$ (De Morgan's Law)

  • $\overline{A \cap B} = \overline{A} \cup \overline{B}$ (De Morgan's Law)

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

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

  • $A \cup \overline{A} = U$ (Complement Law)

  • $A \cap \overline{A} = \emptyset$ (Complement Law)

Proving Set Identities

• Methods: Prove each side is a subset of the other, use set-builder notation and propositional logic, or use membership tables.

Proof of De Morgan's Law

• To prove $\overline{A \cap B} = \overline{A} \cup \overline{B}$, show that $\overline{A \cap B} \subseteq \overline{A} \cup \overline{B}$ and $\overline{A} \cup \overline{B} \subseteq \overline{A \cap B}$.

Set-Builder Notation Example: Second De Morgan Law

• $\overline{A \cap B} = {x | x \notin A \cap B} = {x | \neg (x \in A \cap B)} = {x | \neg (x \in A \land x \in B)} = {x | \neg (x \in A) \lor \neg (x \in B)} = {x | x \notin A \lor x \notin B} = {x | x \in \overline{A} \cup \overline{B}} = \overline{A} \cup \overline{B}$.

Membership Tables

• Use 1 to indicate membership, 0 to indicate non-membership. Useful to verify identities.

Generalized Unions and Intersections

• For indexed collection of sets $A<em>1, A</em>2, …, A_n$:

  • $\bigcup<em>{i=1}^{n} A</em>i = A<em>1 \cup A</em>2 \cup … \cup A_n$

  • $\bigcap<em>{i=1}^{n} A</em>i = A<em>1 \cap A</em>2 \cap … \cap A_n$

• For $A<em>i = {i, i+1, i+2, …}$, $\bigcup</em>{i=1}^{\infty} A<em>i = {1, 2, 3, …}$ and $\bigcap</em>{i=1}^{\infty} A_i = \emptyset$.

Functions

• A function $f: A → B$ assigns each element of $A$ to exactly one element of $B$. If $f(a) = b$, $b$ is the image of $a$ and $a$ is the preimage of $b$.

Terminology

• $f$ maps $A$ to $B$.

• $A$ is the domain, $B$ is the codomain.

• The range of $f$ is the set of all images of points in $A$, denoted by $f(A)$.

• Two functions are equal if they have the same domain, codomain, and mapping.

Representing Functions

• Explicit statement, formula, computer program.

• Examples: $f(x) = x + 1$, a program to generate Fibonacci numbers.

Questions on Functions

• Given $f: A → B$ where $A = {a, b, c, d}$ and $B = {x, y, z}$ with assignments.

Functions and Sets

• If $f: A → B$ and $S ⊆ A$, then $f(S) = {f(s) | s \in S}$.

Injections (One-to-One)

• A function $f$ is injective if $f(a) = f(b)$ implies $a = b$ for all $a, b$ in the domain of $f$.

Surjections (Onto)

• A function $f: A → B$ is surjective if for every element $b$ in $B$, there is an element $a$ in $A$ with $f(a) = b$.

Bijections

• A function is a bijection if it is both injective (one-to-one) and surjective (onto).

Showing Injective and Surjective Properties

• To show $f$ is injective, prove if $f(x) = f(y)$ then $x = y$.

• To show $f$ is not injective, find $x ≠ y$ such that $f(x) = f(y)$.

• To show $f$ is surjective, find an $x$ in $A$ for arbitrary $y$ in $B$ such that $f(x) = y$.

• To show $f$ is not surjective, find a $y$ in $B$ such that $f(x) ≠ y$ for all $x$ in $A$.

Inverse Functions

• If $f$ is a bijection from $A$ to $B$, the inverse of $f$, denoted $f^{-1}$, is the function from $B$ to $A$ such that $f^{-1}(b) = a$ when $f(a) = b$.

• Inverses only exist for bijections.

Composition

• Let $f: B → C$ and $g: A → B$.

• The composition of $f$ with $g$, denoted $f ∘ g$, is the function from $A$ to $C$ defined by $(f ∘ g)(a) = f(g(a))$.

Graphs of Functions

• The graph of $f: A → B$ is the set of ordered pairs $({a, b} | a ∈ A \text{ and } f(a) = b)$.

Important Functions

• Floor function: $\lfloor x \rfloor$ is the largest integer less than or equal to $x$.

• Ceiling function: $\lceil x \rceil$ is the smallest integer greater than or equal to $x$.

Properties of Floor and Ceiling Functions

• (1a) $\lfloor x \rfloor = n$ if and only if n ≤ x < n + 1

Factorial Function

• $f: N → Z^+$, $f(n) = n! = 1 ∙ 2 ∙ … ∙ (n – 1) ∙ n$, $f(0) = 0! = 1$.

Partial Functions (Optional)

• A partial function $f$ from $A$ to $B$ assigns each element in a subset of $A$ to a unique element in $B$.

• The subset of $A$ is the domain of definition.

• If the domain of definition is $A$, $f$ is a total function.

Sequences and Summations

• Sequences are ordered lists of elements that appear throughout mathematics and computer science.

Sequences Definition

• A sequence is a function from a subset of integers to a set $S$.

• The notation $a_n$ denotes the image of the integer $n$.

Geometric Progression

• A sequence of the form ${a, ar, ar^2, ar^3, …, ar^n}$, where $a$ is the initial term and $r$ is the common ratio.

Arithmetic Progression

• A sequence of the form ${a, a+d, a+2d, a+3d, …, a+nd}$, where $a$ is the initial term and $d$ is the common difference.

Strings

• A finite sequence of characters from a finite set (alphabet).

• The empty string is represented by $λ$.

Recurrence Relations

• An equation that expresses $a<em>n$ in terms of previous terms $a</em>0, a<em>1, …, a</em>{n-1}$ for $n ≥ n_0$.

• Initial conditions specify terms preceding the first term.

Fibonacci Sequence

• Initial Conditions: $f<em>0 = 0$, $f</em>1 = 1$. Recurrence Relation: $f<em>n = f</em>{n-1} + f_{n-2}$.

Solving Recurrence Relations

• Finding a formula for the $n$th term is called solving the recurrence relation; such a formula is called a closed formula.

Useful Sequences

• Examples: $n^2, n^3, n^4, 2^n, 3^n, n!, f_n$

Summations

• The sum of terms from a sequence is represented using summation notation.

• $\sum<em>{j=m}^{n} a</em>j = a<em>m + a</em>{m+1} + … + a_n$

Product Notation (Optional)

• $\prod<em>{j=m}^{n} a</em>j = a<em>m * a</em>{m+1} * … * a_n$

Useful Summation Formulas

• Geometric Series, etc.

Matrices

• Matrices are rectangular arrays of numbers used in linear transformations, graph representations, and models of various systems.

Definition

• An $m × n$ matrix has $m$ rows and $n$ columns.

• A square matrix has the same number of rows and columns.

• Two matrices are equal if they have the same dimensions and corresponding entries are equal.

Notation

• $A = [a<em>{ij}]$, where $a</em>{ij}$ is the element in the $i$th row and $j$th column.

Matrix Arithmetic: Addition

• $A + B = [a<em>{ij} + b</em>{ij}]$ for $m × n$ matrices $A$ and $B$. Matrices must have the same dimensions to be added.

Matrix Multiplication

• If $A$ is an $m × k$ matrix and $B$ is a $k × n$ matrix, then $AB = [c<em>{ij}]$ is an $m × n$ matrix with $c</em>{ij} = \sum<em>{r=1}^{k} a</em>{ir}b_{rj}$.

• The product is undefined if the number of columns in the first matrix doesn't match the number of rows in the second matrix.

Identity Matrix and Powers of Matrices

• The identity matrix of order $n$ is $I<em>n = [δ</em>{ij}]$, where $δ<em>{ij} = 1$ if $i = j$ and $δ</em>{ij} = 0$ if $i ≠ j$.

• $AI<em>n = I</em>mA = A$ when $A$ is an $m × n$ matrix.

• $A^0 = I_n$, $A^r = AAA…A$ ($r$ times) for a square matrix $A$.

Transposes of Matrices

• The transpose of $A = [a<em>{ij}]$ is $A^t = [b</em>{ij}]$ where $b<em>{ij} = a</em>{ji}$.

Symmetric Matrices

• A square matrix $A$ is symmetric if $A = A^t$, i.e., $a<em>{ij} = a</em>{ji}$.

Zero-One Matrices

• Matrices with entries either 0 or 1, used in Boolean arithmetic.

Joins and Meets

• The join of $A$ and $B$ is $A ∨ B = [a<em>{ij} ∨ b</em>{ij}]$

• The meet of $A$ and $B$ is $A ∧ B = [a<em>{ij} ∧ b</em>{ij}]$.

Boolean Product

• For $m × k$ matrix $A$ and $k × n$ matrix $B$, the Boolean product $A ⊙ B = [c<em>{ij}]$ has $\text{cij} = (a</em>{i1} ∧ b<em>{1j}) ∨ (a</em>{i2} ∧ b<em>{2j}) ∨ … ∨ (a</em>{ik} ∧ b_{kj})$.

Boolean Powers

• $A^{[r]}$ is the Boolean product of $r$ factors of $A$; $\text{A}^{[0]} = I_n$.