3. Basic Structures

Using sets as our basic object, and guided by the logic we have established since Section 1, this chapter will build up more complex objects. Although more complex, these so-called basic structures are still very “basic” and fundamental to the mathematical foundations of computer science.

In this chapter we will explore functions, sequences, sums, series, and matrices.

• 3.1. Functions
  • 3.1.1. A Formal Definition
  • 3.1.2. Representing Functions
  • 3.1.3. Properties of Functions
    • Equality
    • Partial functions
    • Plots of functions
    • Injective, Surjective, Bijective
  • 3.1.4. Special Functions
    • Identity function
    • Constant function
    • Floor and Ceiling
    • Factorial function
  • 3.1.5. Inverse functions
  • 3.1.6. Function Composition
  • 3.1.7. Proofs with Functions
    • Cardinality of Sets
      • Uncountably Infinite
  • 3.1.8. Exercises
• 3.2. Sequences and Series
  • 3.2.1. Sequences
    • Progressions
    • Strings as Sequences
  • 3.2.2. Recurrence Relations
    • Solving a recurrence relation
  • 3.2.3. Series
    • Closed-form formulas for Summations
  • 3.2.4. Exercises
• 3.3. Matrices
  • 3.3.1. Definitions
  • 3.3.2. Operations on Matrices
    • Scalar Multiplication
    • Addition and Subtraction
    • Matrix Multiplication
    • The zero and identity matrices
    • Powers of Matrices
    • Matrix Transpose
  • 3.3.3. Zero-One Matrices
    • Join and Meet
    • Boolean Product
  • 3.3.4. Relations as Matrices
    • Relational Properties and Matrices
  • 3.3.5. Exercises