MTH1001: Mathematical Structures Study Notes

MTH1001: MATHEMATICAL STRUCTURES

Summary of the Module (Term 1, 2025–2026)

• Definition of Pure Mathematics:

  • Concerned with developing the theory of abstract mathematical objects such as numbers, functions, and sets.

  • Involves starting from precise definitions and proving general results about these objects.

  • Critical focus on reading and writing mathematics and constructing valid logical arguments.

• Topics Covered in Term 1:

  • Sets and logic

  • Functions

  • Number theory (including prime factorization)

  • Groups

• Syllabus Plan/Reading List: Can be found in the module descriptor.

Contents

1. SETS AND LOGIC
   1.1 Sets
   - Definitions and basic operations
   1.2 Writing proofs with sets
   1.3 Propositional Calculus
   1.4 General Methods of Proof

2. FUNCTIONS
   2.1 Defining Functions
   2.2 Surjective and Injective Functions
   2.3 Algebra of Functions

3. ELEMENTARY NUMBER THEORY
   3.1 Proof by Induction
   3.2 Prime Numbers and Divisibility
   3.3 Modular Arithmetic
   3.4 Greatest Common Divisors
   3.5 Uniqueness of Prime Factorization

4. GROUPS
   4.1 Binary Operations
   4.2 Axioms of a Group
   4.3 Dihedral Groups
   4.4 Cardinality of a Group and Order of an Element
   4.5 Subgroups
   4.6 Cosets and Lagrange’s Theorem
   4.7 Isomorphisms and Homomorphisms

1 SETS AND LOGIC

1.1 Sets

• Definition of a Set:

  • A set is a collection of objects called its elements or members.

  • Specified by listing elements in braces: e.g., A = {John, Susan, Ahmed}.

  • Notation:

    • Cardinality of a set: $|S|$,

    • Membership: $x ext{ ∈ A}$ (x is an element of A) and $x <br>otin A$ (x is not an element of A).

  • Example Sets:

    • A = {2, π, √7, eπ}, B = {{1, 2}, {3, 4}} etc.

• Cardinality:

  • Cardinality represents the number of elements: e.g., $|A| = 3$, $|B| = 2$.

1.1.1 Set Constructor Notation

• Specify sets based on existing sets.

  • Example: if $A = ext{ {3, 5, 6, 8, 9}}$, then

  • $B = ext{ {n ∈ A: n is odd}} = {3, 5, 9}$,

  • $C = ext{ {√n : n ∈ A}} = { ext{√3, √5, √6, √8, 3}}$.

1.1.2 The Empty Set

• Defined as the set with no elements, denoted as $∅$.

1.1.3 Notation for Standard Systems of Numbers

• Natural numbers: $N = ext{ {1, 2, 3, …}}$.

• Integers: $Z = ext{ {…, -3, -2, -1, 0, 1, 2, 3, …}}$.

• Rationals: $Q = ext{ {n/m : n, m ∈ Z, } ext{ where } m <br>eq 0}$.

• Reals: $R$.

• Complex: $C = ext{ {x + iy : x, y ∈ R }}$.

1.1.4 Subsets

• Definition of a Subset (Definition 1.1):

  • A subset B of a set A: every element of B is also an element of A.

  • Denoted as $B ext{ ⊆ A}$ or $B ext{ ⊂ A}$ (if B is a proper subset).

  • Examples of subsets:

    • For $A = ext{ {1, 2, 3}}$, subsets are: $∅, ext{ {1}, ext{ {2}, ext{ {3}, ext{ {1, 2}, ext{ {1, 3}, ext{ {2, 3},, ext{ {1, 2, 3}} } } } } } }$.

  • General rule: if A has n elements, it has $2^n$ subsets.

1.1.5 Operations on Sets

• Union (Definition 1.3):

  • $A ∪ B = {x : x ∈ A ext{ or } x ∈ B}$.

• Intersection:

  • $A ∩ B = {x : x ∈ A ext{ and } x ∈ B}$.

• Set Difference:

  • $A \backslash B = {x ∈ A : x <br>otin B}$.

• Examples:

  • Let $A = ext{ {1, 2, 3}}$, $B = ext{ {2, 3, 4}}$, $C = ext{ {4, 5, 6}}$

  • Then: $A ∩ B = ext{ {2, 3}}, A ∪ B = ext{ {1, 2, 3, 4}}$, and similarly for other operations.

1.1.6 The Powerset of a Set

• The powerset of set S, denoted $P(S)$, is the set of all subsets of S.

  • Example: if $A = ext{ {1, 2, 3}}$ then $P(A) = {∅, {1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3}, {1, 2, 3}}$.

  • For finite set S of cardinality n, $P(S) = 2^n$ since each element can either be in or out of a subset.

1.1.7 Cartesian Products

• For sets A and B: $A × B$ is the set of ordered pairs where the first element comes from A and the second from B.

  • Example: if $A = ext{ {3, 4, 5}}$ and $B = ext{ {London, Manchester}}$, then

  • $A × B = { (3, London), (4, London), (5, London), (3, Manchester), (4, Manchester), (5, Manchester)}$.

1.2 Writing Proofs with Sets

• Proof: A logically correct argument explaining why a result is true.

1.2.1 Proving One Set is a Subset of Another

• Proof format for showing $A ⊆ B$:

  • Start with any element $x ∈ A$ and show that $x ∈ B$.

• Example: Let A = ext{ {x ∈ R: x^2 < 5}} and $B = ext{ {x ∈ R: x ≤ 4}}$, we would show for all $x ext{ in } A$, $x ext{ must also be in } B$.

1.2.2 Proving Two Sets are Equal

• Show that $A ⊆ B$ and $B ⊆ A$.

2 FUNCTIONS

2.1 What is a Function?

• Definition: A function $f$ from set A to set B is a rule associating every element $a ∈ A$ to one and only one element $f(a)$ in B.

• Notation: $f: A o B$.

  • Example: $f(x) = x^2$ for $x ∈ R$ defines a function from R to R.

2.2 Surjective and Injective Functions

• Surjective (Onto): A function is surjective if for every $b ∈ B$ there exists at least one $a ∈ A$ such that $f(a) = b$.

• Injective (One-to-One): A function is injective if for every $b ∈ B$ there is at most one $a ∈ A$ with $f(a) = b$.

2.3 The “Algebra” of Functions

• Composition of Functions: If $f: A o B$ and $g: B o C$, then the composition $g \circ f: A o C$ is defined as $g \ (a) = g(f(a))$.

• Identity Functions: For a set A, $id_A(a) = a$ for all $a ∈ A$.

- Inverse Functions: For $f: A o B$ with an inverse if $g: B o A$ such that $g(f(a)) = a$ and $f(g(b)) = b$.

3 ELEMENTARY NUMBER THEORY

3.1 Proof by Induction

• Principle of Mathematical Induction:

  • If P is a predicate, and:

    1. P(1) is true,

    2. P(k) implies P(k + 1)

  • Then, P(n) is true for all natural numbers n.

• Example of Induction:

  • Prove for n ≥ 1, $1 + 3 + 5 + … + (2n - 1) = n^2$.

3.2 Prime Numbers and Divisibility

• Definition of a Prime Number: A prime number is a natural number greater than 1 that is divisible only by 1 and itself.

• Divisibility: An integer n is divisible by m if $n = ma$ for some integer a.

3.3 Modular Arithmetic

• Definition: Integers a and b are congruent modulo n if $(a - b)/n$ is an integer.

• Properties of congruences:

  • Reflexive, Symmetric, Transitive.

3.4 Greatest Common Divisors

• Definition: The greatest common divisor $ext{gcd}(m, n)$ is the largest integer that divides both m and n.

3.5 Uniqueness of Prime Factorization

- Theorem: Every natural number greater than 1 has a unique representation as a product of prime numbers (Fundamental Theorem of Arithmetic).

4 GROUPS

4.1 Binary Operations

• Definition: A binary operation is a rule that combines two elements to produce a third.

• Examples include operations like addition and multiplication on sets.

4.2 Axioms of a Group

• Definition: A set G with a binary operation is a group if:

  1. The operation is associative.

  2. There exists an identity element e such that for every a in G, $e ∗ a = a ∗ e = a$.

  3. Each element a has an inverse such that $a ∗ a' = e$.

4.3 Dihedral Groups

• Example: The symmetry group of a square has rotations and reflections forming the dihedral group D_n.

4.4 Cardinality of Groups

• Definition: The cardinality is the number of elements in the group. If the number is finite, it's considered a finite group.

4.5 Subgroups

• Definition: A subset of a group is a subgroup if it contains the identity, is closed under the group operation, and every element has an inverse.

4.6 Cosets and Lagrange’s Theorem

• Lagrange’s Theorem states that the order of a subgroup divides the order of the group.

4.7 Isomorphisms and Homomorphisms

- Isomorphism is a structure-preserving map between two groups.

Appendix

• Index:

  • Contains terms and their definitions relevant to Mathematical Structures, to assist in easier navigation of key concepts covered in the course.