Basic Structures

Sets, Functions, Sequences, Sums, and Matrices

Chapter 2 - Discrete Mathematics

Table of Contents

1. Sets

Definition: A set is an unordered collection of objects. The objects in a set are called elements or members of the set.

1.1 Set Basics

Notation:
  • a ∈ A denotes that a is an element of set A
  • a ∉ A denotes that a is not an element of set A

1.2 Describing Sets

Roster Method

List all members of the set explicitly.

Examples:
  • S = {a, b, c, d}
  • V = {a, e, i, o, u}
  • O = {1, 3, 5, 7, 9}
Note: Order does not matter, and repeating elements doesn't change the set.
S = {a,b,c,d} = {b,c,a,d} = {a,b,c,b,c,d}

Set-Builder Notation

Specify properties that all members must satisfy.

Examples:
  • S = {x | x is a positive integer less than 100}
  • O = {x ∈ ℤ⁺ | x is odd and x < 10}
  • Q⁺ = {x ∈ ℝ | x = p/q, for some positive integers p,q}

Interval Notation

Notation Set-Builder Form Type
[a, b] {x | a ≤ x ≤ b} Closed interval
(a, b) {x | a < x < b} Open interval
[a, b) {x | a ≤ x < b} Half-open interval
(a, b] {x | a < x ≤ b} Half-open interval

1.3 Important Sets in Mathematics

ℕ - Natural Numbers

{0, 1, 2, 3, 4, ...}

ℤ - Integers

{..., -3, -2, -1, 0, 1, 2, 3, ...}

ℤ⁺ - Positive Integers

{1, 2, 3, 4, ...}

ℚ - Rational Numbers

Numbers expressible as p/q where p, q are integers

ℝ - Real Numbers

All rational and irrational numbers (√2, π, e)

ℝ⁺ - Positive Real Numbers

All positive real numbers

ℂ - Complex Numbers

{a + bi : a, b ∈ ℝ}

Special Sets

Universal Set (U): The set containing everything currently under consideration.
Empty Set (∅ or {}): The set with no elements.

1.4 Set Equality and Subsets

Set Equality: Two sets are equal if and only if they have the same elements.
A = B if and only if ∀x (x ∈ A ↔ x ∈ B)
Examples:
  • {1, 3, 5} = {3, 5, 1}
  • {1, 5, 5, 5, 3, 3, 1} = {1, 3, 5}
Subset (A ⊆ B): Set A is a subset of B if every element of A is also an element of B.
A ⊆ B if and only if ∀x (x ∈ A → x ∈ B)
Proper Subset (A ⊂ B): If A ⊆ B but A ≠ B, then A is a proper subset of B.
Important Properties:
  • ∅ ⊆ S for every set S
  • S ⊆ S for every set S
  • A = B if and only if A ⊆ B and B ⊆ A

Cardinality

Cardinality: If there are exactly n distinct elements in set S where n is a nonnegative integer, then S is a finite set and |S| = n is the cardinality of S.
Examples:
  • |∅| = 0
  • |{1, 2, 3}| = 3
  • |{∅}| = 1
  • |{English alphabet}| = 26

Power Sets

Power Set P(A): The set of all subsets of set A.
If |A| = n, then |P(A)| = 2ⁿ
Example: If A = {a, b}, then
P(A) = {∅, {a}, {b}, {a, b}}
|P(A)| = 4 = 2²

Cartesian Product

Cartesian Product (A × B): The set of all ordered pairs (a, b) where a ∈ A and b ∈ B.
A × B = {(a, b) | a ∈ A and b ∈ B}
Example: Let A = {a, b} and B = {1, 2, 3}
A × B = {(a,1), (a,2), (a,3), (b,1), (b,2), (b,3)}

2. Set Operations

2.1 Union and Intersection

Union (A ∪ B)

A ∪ B = {x | x ∈ A or x ∈ B}
Example:
{1, 2, 3} ∪ {3, 4, 5} = {1, 2, 3, 4, 5}

Intersection (A ∩ B)

A ∩ B = {x | x ∈ A and x ∈ B}
Example:
{1, 2, 3} ∩ {3, 4, 5} = {3}

Note: If A ∩ B = ∅, then A and B are disjoint.

2.2 Complement and Difference

Complement (Ā)

Ā = U - A = {x ∈ U | x ∉ A}
Example:
If U = {positive integers < 100}
and A = {x | x > 70}
then Ā = {x | x ≤ 70}

Difference (A - B)

A - B = {x | x ∈ A and x ∉ B} = A ∩ B̄
Example:
{1, 2, 3, 4, 5} - {4, 5, 6, 7, 8} = {1, 2, 3}

Symmetric Difference (A ⊕ B)

A ⊕ B = (A - B) ∪ (B - A) = (A ∪ B) - (A ∩ B)
Example:
A = {1, 2, 3, 4, 5}, B = {4, 5, 6, 7, 8}
A ⊕ B = {1, 2, 3, 6, 7, 8}

Cardinality of Union

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

2.3 Set Identities

Identity Name
A ∪ ∅ = A
A ∩ U = A		 Identity Laws
A ∪ U = U
A ∩ ∅ = ∅		 Domination Laws
A ∪ A = A
A ∩ A = A		 Idempotent Laws
(Ā) = A Complementation Law
A ∪ B = B ∪ A
A ∩ B = B ∩ A		 Commutative Laws
(A ∪ B) ∪ C = A ∪ (B ∪ C)
(A ∩ B) ∩ C = A ∩ (B ∩ C)		 Associative Laws
A ∪ (B ∩ C) = (A ∪ B) ∩ (A ∪ C)
A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C) 		Distributive Laws
(A ∪ B) = Ā ∩ B̄
(A ∩ B) = Ā ∪ B̄		 De Morgan's Laws
A ∪ (A ∩ B) = A
A ∩ (A ∪ B) = A		 Absorption Laws
A ∪ Ā = U
A ∩ Ā = ∅		 Complement Laws

3. Functions

Definition: A function f from A to B, denoted f: A → B, is an assignment of each element of A to exactly one element of B.

Function Terminology

Key Terms:
  • Domain: The set A (where function starts)
  • Codomain: The set B (where function can go)
  • Image of a: The value f(a) = b
  • Preimage of b: The value a such that f(a) = b
  • Range: f(A) = {f(a) | a ∈ A}, the set of all images

3.1 Types of Functions

Injective (One-to-One)

A function f is injective if:
f(a) = f(b) implies a = b
OR equivalently: a ≠ b implies f(a) ≠ f(b)

Each element in the codomain has at most one preimage.

Surjective (Onto)

A function f: A → B is surjective if:
∀b ∈ B, ∃a ∈ A such that f(a) = b

Every element in the codomain has at least one preimage.

Bijective (One-to-One Correspondence)

A function is bijective if it is both injective and surjective.

Each element in the codomain has exactly one preimage.

Examples with f: ℝ → ℝ:
  • f(x) = x: Injective, Surjective, Bijective ✓
  • f(x) = x²: Not injective (f(-2) = f(2)), Not surjective (no x where f(x) = -1) ✗
  • f(x) = x³: Injective, Surjective, Bijective ✓
  • f(x) = |x|: Not injective, Not surjective ✗

Inverse Functions

Inverse Function f⁻¹: If f is a bijection from A to B, then the inverse function f⁻¹: B → A is defined by:
f⁻¹(b) = a if and only if f(a) = b
Important: An inverse function exists if and only if f is a bijection!
Example: Let f: ℤ → ℤ where f(x) = x + 1
Then f⁻¹(y) = y - 1

Function Composition

Composition (f ∘ g): Let g: A → B and f: B → C. The composition is:
(f ∘ g)(x) = f(g(x))
Example: Let f(x) = 2x + 3 and g(x) = 3x + 2
  • (f ∘ g)(x) = f(g(x)) = f(3x + 2) = 2(3x + 2) + 3 = 6x + 7
  • (g ∘ f)(x) = g(f(x)) = g(2x + 3) = 3(2x + 3) + 2 = 6x + 11

3.2 Special Functions

Floor Function ⌊x⌋

The largest integer less than or equal to x
Examples:
  • ⌊3.7⌋ = 3
  • ⌊-0.5⌋ = -1
  • ⌊5⌋ = 5

Ceiling Function ⌈x⌉

The smallest integer greater than or equal to x
Examples:
  • ⌈3.2⌉ = 4
  • ⌈-0.5⌉ = 0
  • ⌈5⌉ = 5

Factorial Function (n!)

n! = 1 × 2 × 3 × ... × (n-1) × n for n ≥ 1
0! = 1
Examples:
  • 3! = 1 × 2 × 3 = 6
  • 5! = 1 × 2 × 3 × 4 × 5 = 120
  • 10! = 3,628,800

4. Sequences and Summations

Sequence: A function from a subset of integers (usually {0, 1, 2, 3, ...} or {1, 2, 3, ...}) to a set S. We denote the image of n as aₙ.

Types of Sequences

Geometric Progression

a, ar, ar², ar³, ar⁴, ...
where a is the initial term and r is the common ratio
Examples:
  • a = 2, r = 5: 2, 10, 50, 250, 1250, ...
  • a = 6, r = 1/3: 6, 2, 2/3, 2/9, 2/27, ...

Arithmetic Progression

a, a+d, a+2d, a+3d, a+4d, ...
where a is the initial term and d is the common difference
Examples:
  • a = -1, d = 4: -1, 3, 7, 11, 15, ...
  • a = 7, d = -3: 7, 4, 1, -2, -5, ...

Fibonacci Sequence

Definition:
  • Initial conditions: f₀ = 0, f₁ = 1
  • Recurrence relation: fₙ = fₙ₋₁ + fₙ₋₂ for n ≥ 2
First terms: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...

Recurrence Relations

Recurrence Relation: An equation that expresses aₙ in terms of one or more previous terms of the sequence (a₀, a₁, ..., aₙ₋₁).
Example: Let aₙ = aₙ₋₁ + 3 with a₀ = 2
  • a₁ = a₀ + 3 = 2 + 3 = 5
  • a₂ = a₁ + 3 = 5 + 3 = 8
  • a₃ = a₂ + 3 = 8 + 3 = 11
  • General solution: aₙ = 2 + 3n

Summations

Σ (from j=m to n) aⱼ = aₘ + aₘ₊₁ + aₘ₊₂ + ... + aₙ
Notation:
  • j is the index of summation
  • m is the lower limit
  • n is the upper limit

Important Summation Formulas

Formula Result
Σ (k=1 to n) k n(n+1)/2
Σ (k=1 to n) k² n(n+1)(2n+1)/6
Σ (k=1 to n) k³ [n(n+1)/2]²
Σ (k=0 to n) rᵏ (rⁿ⁺¹ - 1)/(r - 1), r ≠ 1
Σ (k=1 to ∞) xᵏ 1/(1-x), |x| < 1
Example: Find Σ (k=1 to 100) k
Solution: Using the formula: 100(100+1)/2 = 100(101)/2 = 5,050

5. Matrices

Matrix: A rectangular array of numbers. A matrix with m rows and n columns is called an m × n matrix.

Matrix Equality

Two matrices A and B are equal if they have the same dimensions and corresponding entries are equal:
A = B if and only if aᵢⱼ = bᵢⱼ for all i, j

Matrix Operations

Matrix Addition

If A and B are m × n matrices, then A + B is the m × n matrix where:
(A + B)ᵢⱼ = aᵢⱼ + bᵢⱼ
Example: 
[1  2]   [4  5]   [5  7]
[3  4] + [6  7] = [9  11]

Scalar Multiplication

If A is an m × n matrix and c is a scalar, then cA is the m × n matrix where:
(cA)ᵢⱼ = c · aᵢⱼ
Example: 
    [1  2]   [3   6]
3 × [3  4] = [9  12]

Matrix Multiplication

If A is an m × k matrix and B is a k × n matrix, then AB is an m × n matrix where:
(AB)ᵢⱼ = Σ (p=1 to k) aᵢₚ · bₚⱼ
Important: The number of columns in A must equal the number of rows in B!

Special Matrices

Identity Matrix (Iₙ)

An n × n matrix with 1's on the main diagonal and 0's elsewhere. 
I₃ = [1  0  0]
     [0  1  0]
     [0  0  1]

Zero Matrix

A matrix where all entries are 0.
O₂ₓ₃ = [0  0  0]
       [0  0  0]

Matrix Transpose

Transpose (Aᵀ): The transpose of an m × n matrix A is the n × m matrix obtained by interchanging rows and columns:
(Aᵀ)ᵢⱼ = aⱼᵢ
Example: 
If A = [1  2  3]    then Aᵀ = [1  4]
       [4  5  6]              [2  5]
                              [3  6]
Symmetric Matrix: A matrix A is symmetric if A = Aᵀ (must be square).

Matrix Powers

For a square matrix A:
  • A⁰ = I (identity matrix)
  • A¹ = A
  • Aⁿ = A · A · ... · A (n times)

Zero-One Matrices

Zero-One Matrix: A matrix where all entries are either 0 or 1.

Boolean Product (A ⊙ B)

For zero-one matrices, the Boolean product uses OR and AND operations:
(A ⊙ B)ᵢⱼ = (aᵢ₁ ∧ b₁ⱼ) ∨ (aᵢ₂ ∧ b₂ⱼ) ∨ ... ∨ (aᵢₖ ∧ bₖⱼ)

Replace multiplication with AND (∧) and addition with OR (∨)

Boolean Powers

  • A⁽⁰⁾ = I
  • A⁽ⁿ⁾ = A⁽ⁿ⁻¹⁾ ⊙ A

Summary

This comprehensive report covered the fundamental structures in discrete mathematics:

  • Sets: Foundation of mathematics, including operations, identities, and cardinality
  • Functions: Mappings between sets, including injective, surjective, and bijective functions
  • Sequences: Ordered lists including arithmetic and geometric progressions, with summation formulas
  • Matrices: Rectangular arrays with operations essential for linear algebra and computer science