Comprehensive Notes on Sets, Functions, Sequences, and Matrices in Discrete Mathematics

Foundations of Discrete Structures: Sets, Functions, Sequences, Sums, and Matrices

Discrete mathematics is fundamentally concerned with discrete structures used to represent discrete objects. Many of these structures, including combinations, relations, graphs, and finite-state machines, are constructed using sets. Sets are collections of objects. Functions, which assign elements of one set to exactly one element of another set, are equally vital, playing roles in representing computational complexity, counting objects, and studying the size of sets. Sequences and strings represent special types of functions. Matrices are employed to represent discrete structures like relations and graphs and are manipulated through matrix arithmetic to solve complex problems.

Set Theory Fundamentals

A set is an unordered collection of objects, referred to as elements or members. A set is said to contain its elements. The notation $a \in A$ denotes that $a$ is an element of set $A$, while $a \notin A$ signifies that it is not.

Describing Sets

There are several methods for describing a set:

1. Roster Method: Listing all members between braces.

   • Example: The set of vowels in the English alphabet is $V = \{a, e, i, o, u\}$.

   • Example: The set of odd positive integers less than $10$ is $O = \{1, 3, 5, 7, 9\}$.

   • Sets can contain unrelated elements, such as $\{a, 2, \text{Fred}, \text{New Jersey}\}$.

   • Ellipses ($...$) are used when the pattern is obvious. The set of positive integers less than $100$ is $\{1, 2, 3, \dots, 99\}$.

2. Set Builder Notation: Characterizing elements by stating the properties they must possess.

   • Example: $O = \{x \mid x \text{ is an odd positive integer less than } 10\}$.

   • Example: The set of positive rational numbers $\mathbb{Q}^+ = \{x \in \mathbb{R} \mid x = \frac{p}{q}, \text{ for some positive integers } p \text{ and } q\}$.

Important Sets in Discrete Mathematics

• $\mathbb{N} = \{0, 1, 2, 3, \dots\}$, the set of natural numbers. (Note: Some authors exclude $0$, but it is included here).

• $\mathbb{Z} = \{\dots, -2, -1, 0, 1, 2, \dots\}$, the set of integers.

• $\mathbb{Z}^+ = \{1, 2, 3, \dots\}$, the set of positive integers.

• $\mathbb{Q} = \{p/q \mid p \in \mathbb{Z}, q \in \mathbb{Z}, \text{ and } q \neq 0\}$, the set of rational numbers.

• $\mathbb{R}$, the set of real numbers.

• $\mathbb{R}^+$, the set of positive real numbers.

• $\mathbb{C}$, the set of complex numbers.

Intervals

For real numbers $a$ and $b$ with a < b:

• Closed interval: $[a, b] = \{x \mid a \le x \le b\}$

• Left-closed, right-open: [a, b) = \{x \mid a \le x < b\}

• Left-open, right-closed: (a, b] = \{x \mid a < x \le b\}

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

Set Equality and Types

• Definition of Equality: Two sets are equal if and only if they have the same elements. $A = B$ if and only if $\forall x(x \in A \leftrightarrow x \in B)$.

• The order of elements does not matter: $\{1, 3, 5\} = \{3, 5, 1\}$.

• Repetition does not matter: $\{1, 3, 3, 3, 5, 5, 5\} = \{1, 3, 5\}$.

• Empty Set: Also called the null set, denoted by $\emptyset$ or $\{\}$, it contains no elements.

• Singleton Set: A set with exactly one element. Note that $\emptyset \neq \{\emptyset\}$; the latter is a singleton set containing the empty set.

Relationships Between Sets

Subsets

Set $A$ is a subset of $B$ ($A \subseteq B$) if and only if every element of $A$ is also an element of $B$. This is expressed by the quantification $\forall x(x \in A \rightarrow x \in B)$.

• To show $A \subseteq B$, show that if $x \in A$, then $x \in B$.

• To show $A \not\subseteq B$, find a single counterexample $x \in A$ such that $x \notin B$.

• Theorem 1: For every set $S$, (i) $\emptyset \subseteq S$ and (ii) $S \subseteq S$.

• Proper Subsets: $A \subset B$ if $A \subseteq B$ but $A \neq B$. This requires $\forall x(x \in A \rightarrow x \in B) \land \exists x(x \in B \land x \notin A)$.

Venn Diagrams

Named after John Venn ($1881$), these represent sets graphically.

• The Universal Set $U$ is represented by a rectangle.

• Sets are represented by circles within the rectangle.

• Points may represent specific elements.

Size and Power Sets

• Cardinality: If a set $S$ contains exactly $n$ distinct elements where $n$ is a nonnegative integer, $S$ is finite and its cardinality is $|S| = n$.

• An infinite set is one that is not finite (e.g., $\mathbb{Z}^+$).

• Power Set: The set of all subsets of $S$, denoted $\mathcal{P}(S)$.

  • Example: if $S = \{0, 1, 2\}$, $\mathcal{P}(S) = \{\emptyset, \{0\}, \{1\}, \{2\}, \{0, 1\}, \{0, 2\}, \{1, 2\}, \{0, 1, 2\}\}$.

  • If a set has $n$ elements, its power set has $2^n$ elements.

Cartesian Products

• Ordered n-tuple: $(a_1, a_2, \dots, a_n)$ is an ordered collection. Two $n$-tuples are equal if every corresponding pair of elements is equal.

• Cartesian Product ($A \times B$): The set of all ordered pairs $(a, b)$ where $a \in A$ and $b \in B$. $A \times B = \{(a, b) \mid a \in A \land b \in B\}$.

  • $A \times B \neq B \times A$ unless $A = B$, $A = \emptyset$, or $B = \emptyset$.

• Relations: A subset $R$ of the Cartesian product $A \times B$ is a relation from $A$ to $B$.

Set Operations

Basic Operations

1. Union ($A \cup B$): $\in A \lor \in B$. Shaded as the area in either circle in a Venn diagram.

2. Intersection ($A \cap B$): $\in A \land \in B$. Shaded as the overlapping area.

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

3. Principle of Inclusion-Exclusion: For finite sets, $|A \cup B| = |A| + |B| - |A \cap B|$.

4. Difference ($A - B$): Elements in $A$ but not in $B$. Also called the complement of $B$ with respect to $A$.

5. Complement ($\overline{A}$): Elements in the universal set $U$ not in $A$. $\overline{A} = U - A$.

Set Identities

• Identity Laws: $A \cup \emptyset = A$; $A \cap U = A$

• Domination Laws: $A \cup U = U$; $A \cap \emptyset = \emptyset$

• Idempotent Laws: $A \cup A = A$; $A \cap A = A$

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

• Commutative Laws: $A \cup B = B \cup A$; $A \cap B = B \cap A$

• Associative Laws: $A \cup (B \cup C) = (A \cup B) \cup C$; $A \cap (B \cap C) = (A \cap B) \cap C$

• Distributive Laws: $A \cup (B \cap C) = (A \cup B) \cap (A \cup C)$; $A \cap (B \cup C) = (A \cap B) \cup (A \cap C)$

• De Morgan's Laws: $\overline{A \cap B} = \overline{A} \cup \overline{B}$; $\overline{A \cup B} = \overline{A} \cap \overline{B}$

• Absorption Laws: $A \cup (A \cap B) = A$; $A \cap (A \cup B) = A$

• Complement Laws: $A \cup \overline{A} = U$; $A \cap \overline{A} = \emptyset$

Generalized Unions and Intersections

• $\bigcup_{i=1}^n A_i = A_1 \cup A_2 \cup \dots \cup A_n$

• $\bigcap_{i=1}^n A_i = A_1 \cap A_2 \cap \dots \cap A_n$

Computer Representation of Sets

A subset $A$ of a finite universal set $U = \{a_1, a_2, \dots, a_n\}$ can be represented by a bit string of length $n$. The $i$th bit is $1$ if $a_i \in A$ and $0$ otherwise.

• Union: Bitwise OR.

• Intersection: Bitwise AND.

• Complement: Bitwise NOT (flips bits).

Functions

Definitions

• Function $f: A \rightarrow B$: Assignments of exactly one element of $B$ to each element of $A$. If $f(a) = b$, $b$ is the unique element assigned to $a$.

• Domain: The set $A$.

• Codomain: The set $B$.

• Image/Preimage: If $f(a) = b$, $b$ is the image of $a$ and $a$ is the preimage of $b$.

• Range: The set of all images of elements of $A$.

Function Arithmetic

For real-valued functions $f_1, f_2$:

• $(f_1 + f_2)(x) = f_1(x) + f_2(x)$

• $(f_1 f_2)(x) = f_1(x) f_2(x)$

Injections, Surjections, and Bijections

• One-to-One (Injective): $f$ is injective if $f(a) = f(b) \rightarrow a = b$ for all $a, b$ in the domain.

• Onto (Surjective): $f$ is surjective if for every $b \in B$, there exists $a \in A$ such that $f(a) = b$.

• One-to-One Correspondence (Bijective): both injective and surjective.

Inverse and Composition

• Inverse Function ($f^{-1}$): If $f$ is a bijection, $f^{-1}(b) = a$ when $f(a) = b$.

• Composition ($f \circ g$): $(f \circ g)(a) = f(g(a))$. Range of $g$ must be a subset of the domain of $f$.

Floor and Ceiling Functions

• Floor Function (Greatest Integer Function) ($\lfloor x \rfloor$): The largest integer less than or equal to $x$.

• Ceiling Function ($\lceil x \rceil$): The smallest integer greater than or equal to $x$.

• Example Calculations:

  • $\lfloor 0.5 \rfloor = 0$

  • $\lceil 0.5 \rceil = 1$

  • $\lfloor -0.5 \rfloor = -1$

  • $\lceil -0.5 \rceil = 0$

• Properties:

  • \lfloor x \rfloor = n \iff n \le x < n + 1

  • \lceil x \rceil = n \iff n - 1 < x \le n

  • x - 1 < \lfloor x \rfloor \le x \le \lceil x \rceil < x + 1

  • $\lfloor -x \rfloor = -\lceil x \rceil$

  • $\lceil -x \rceil = -\lfloor x \rfloor$

Sequences and Summations

Sequences

A sequence is an ordered list, formally a function from a subset of integers to a set $S$.

• Geometric Progression: $a, ar, ar^2, \dots, ar^n, \dots$ where $a$ is the initial term and $r$ is the common ratio.

• Arithmetic Progression: $a, a+d, a+2d, \dots, a+nd, \dots$ where $a$ is the initial term and $d$ is the common difference.

Recurrence Relations

An equation expressing $a_n$ in terms of previous terms (e.g., $a_0, a_1, \dots, a_{n-1}$).

• Fibonacci Sequence: defined by $f_0 = 0, f_1 = 1$ and $f_n = f_{n-1} + f_{n-2}$ for $n \ge 2$.

• Iteration: A method to solve recurrences by forward or backward substitution.

Summations

The sum of terms $a_m, a_{m+1}, \dots, a_n$ is denoted by $\sum_{j=m}^n a_j$.

• Geometric Series Formula:     $\sum_{j=0}^n ar^j = \begin{cases} \frac{ar^{n+1} - a}{r - 1} &amp; \text{if } r \neq 1 \\ (n+1)a &amp; \text{if } r = 1 \end{cases}$

• Important Finite Sums:

  • $\sum_{k=1}^n k = \frac{n(n+1)}{2}$

  • $\sum_{k=1}^n k^2 = \frac{n(n+1)(2n+1)}{6}$

  • $\sum_{k=1}^n k^3 = \frac{n^2(n+1)^2}{4}$

• Infinite Series: For |x| < 1, $\sum_{k=0}^{\infty} x^k = \frac{1}{1 - x}$.

Cardinality and Infinite Sets

Countability

• Two sets have the same cardinality if there is a one-to-one correspondence between them.

• Countable Set: Finite or has the same cardinality as the positive integers ($|S| = \aleph_0$, read as "aleph null").

• Uncountable Set: Not countable.

• Surprising Results:

  • The set of all integers is countable ($0, 1, -1, 2, -2, \dots$).

  • The set of positive rational numbers is countable (shown via a grid traversal excluding repeats).

  • The set of real numbers $\mathbb{R}$ is uncountable. This is proven via Cantor's Diagonalization Argument.

Schröder-Bernstein Theorem

If $|A| \le |B|$ and $|B| \le |A|$, then $|A| = |B|$. Equivalently, if there are injections from $A$ to $B$ and $B$ to $A$, there is a bijection.

Uncomputable Functions

A function is uncomputable if no program can calculate all its values. Because the set of computer programs is countable but the set of functions from $\mathbb{Z}^+$ to $\mathbb{Z}^+$ is uncountable, such functions must exist.

Continuum Hypothesis

Asserts there is no cardinal number $X$ such that \aleph_0 < X < c, where $c = |\mathbb{R}|$. It has been shown that this hypothesis can neither be proven nor disproven under standard set theory axioms (Zermelo-Fraenkel).

Matrices

A matrix is a rectangular array of numbers. An $m \times n$ matrix has $m$ rows and $n$ columns.

Matrix Operations

• Addition: For two $m \times n$ matrices $A$ and $B$, the sum $A + B = [a_{ij} + b_{ij}]$.

• Multiplication ($AB$): Defined when the number of columns in $A$ equals the number of rows in $B$. If $A$ is $m \times k$ and $B$ is $k \times n$, $AB$ is an $m \times n$ matrix where $c_{ij} = \sum_{s=1}^k a_{is}b_{sj}$.

  • Matrix multiplication is not commutative ($AB \neq BA$ in general).

• Identity Matrix ($I_n$): Square matrix with $1$s on the main diagonal and $0$s elsewhere. $AI_n = I_m A = A$.

• Transpose ($A^t$): Obtained by swapping rows and columns ($b_{ij} = a_{ji}$).

• Symmetric Matrix: Square matrix where $A = A^t$.

Zero-One Matrices

Matrices with only $0$ and $1$ as entries.

• Join ($A \lor B$): Entrywise Boolean OR.

• Meet ($A \land B$): Entrywise Boolean AND.

• Boolean Product ($A \odot B$): Similar to matrix multiplication but with OR ($\lor$) replacing addition and AND ($\land$) replacing multiplication.

• Boolean Powers ($A^{[r]}$): The Boolean product of $r$ factors of $A$.