Home > Math for DS > Week 1 Notes

Week 1 - Mathematics for Data Science 1

Professor: Madhavan Mukund | Institution: Chennai Mathematical Institute

Week 1 of 4 completed

1. Natural Numbers and Integers

1.1 Natural Numbers (โ„•)

โš ๏ธ CRITICAL COURSE-SPECIFIC CONVENTION

In this course, natural numbers INCLUDE 0.

$$\mathbb{N} = \{0, 1, 2, 3, 4, ...\}$$

Note: Some textbooks exclude 0 from natural numbers, but THIS COURSE INCLUDES IT.

Key Concepts

  • Natural numbers are used for counting
  • They represent abstract quantities
  • The number 0 is of Indian origin and is crucial for our place value numbering system
  • Numbers like 7 represent what is common between different collections (7 balls, 7 pencils)

1.2 Integers (โ„ค)

Definition

$$\mathbb{Z} = \{..., -3, -2, -1, 0, 1, 2, 3, ...\}$$
Key Properties
  • Integers extend natural numbers with negative numbers
  • All natural numbers are integers (โ„• โŠ† โ„ค)
  • Integers are discrete: every integer has a unique "next" and "previous" integer

Arithmetic Operations on Integers

  1. Addition (+): Combining quantities
  2. Subtraction (โˆ’): Finding difference
  3. Multiplication (ร—): Repeated addition
  4. Division (รท): Splitting into equal parts
  5. Exponentiation (m^n): Repeated multiplication

Division with Quotient and Remainder

For integers a and b (b โ‰  0):

$$a = b \times q + r, \text{ where } 0 \leq r < b$$
  • Quotient (q): The integer number of times b goes into a
  • Remainder (r): What's left over
Modulo Operation

a mod b = remainder when a is divided by b

Example: 17 mod 5 = 2 (since 17 = 5 ร— 3 + 2)

Divisibility

We say a | b (a divides b) if a mod b = 0

Factors of a number n are all numbers that divide n

Example: Factors of 24 are {1, 2, 3, 4, 6, 8, 12, 24}

1.3 Rational Numbers (โ„š)

Definition

A rational number is any number that can be expressed as p/q where:

  • p, q โˆˆ โ„ค (both are integers)
  • q โ‰  0 (denominator cannot be zero)
$$\mathbb{Q} = \left\{\frac{p}{q} \mid p, q \in \mathbb{Z}, q \neq 0\right\}$$

Examples: 3/5, 6/10, -7/4, 18/60

Non-Unique Representation

Rational numbers do NOT have unique representations

Example: 3/5 = 6/10 = 30/50 = ...

Why? Multiplying both numerator and denominator by the same non-zero number gives an equivalent fraction

Greatest Common Divisor (GCD)

Definition: gcd(m, n) is the largest number that divides both m and n

Finding GCD using Prime Factorization
  1. Find prime factorization of both numbers
  2. Identify common prime factors
  3. Multiply the common primes
Example
  • 18 = 2 ร— 3 ร— 3
  • 60 = 2 ร— 2 ร— 3 ร— 5
  • Common factors: 2 ร— 3 = 6
  • Therefore, gcd(18, 60) = 6

Reducing to Lowest Terms: 18/60 = (18รท6)/(60รท6) = 3/10

Density of Rational Numbers

Theorem: Rational numbers are dense

Definition of Density: Between any two rational numbers, there exists another rational number

Proof: For any r < r', the average (r + r')/2 lies between them

Implication: There is NO "next" rational number - unlike integers, we cannot find the immediate successor

1.4 Real Numbers (โ„)

Beyond Rationals

Motivation: Not every point on the number line is a rational number

Example - Square Roots:

  • Perfect squares: 1, 4, 9, 16, 25, ..., 256, ...
  • Their square roots: 1, 2, 3, 4, 5, ..., 16, ...
  • But what about โˆš2, โˆš3, โˆš5, โˆš6?

Real Numbers (โ„)

Definition: โ„ = โ„š โˆช {all irrational numbers}

  • Real numbers include ALL rational and irrational numbers
  • Every point on the number line is a real number
Hierarchy
$$\mathbb{N} \subseteq \mathbb{Z} \subseteq \mathbb{Q} \subseteq \mathbb{R}$$
  • Every natural number is an integer
  • Every integer is a rational number (can write as n/1)
  • Every rational number is a real number

2. Sets

Basic Definition

Informal Definition: A set is a collection of items

Examples
  • Days of week: {Sunday, Monday, Tuesday, Wednesday, Thursday, Friday, Saturday}
  • Factors of 24: {1, 2, 3, 4, 6, 8, 12, 24}
  • Prime numbers below 15: {2, 3, 5, 7, 11, 13}

Standard Number Sets

  • โ„•: Natural numbers = {0, 1, 2, 3, ...}
  • โ„ค: Integers = {..., -3, -2, -1, 0, 1, 2, 3, ...}
  • โ„š: Rational numbers = {p/q | p, q โˆˆ โ„ค, q โ‰  0}
  • โ„: Real numbers = all rationals and irrationals

Set Comprehension (Set Builder Notation)

General Form: {x | x โˆˆ S, P(x)}

Read as: "the set of all x such that x belongs to S and x satisfies property P"

Examples
  • Even natural numbers: {n | n โˆˆ โ„•, n mod 2 = 0}
  • Integers between -6 and 6: {z | z โˆˆ โ„ค, -6 โ‰ค z โ‰ค 6}
  • First 500 natural numbers: X = {n | n โˆˆ โ„•, n < 500} = {0, 1, 2, ..., 499}

Intervals (for Real Numbers)

  • Closed Interval [a, b]: Includes endpoints - [0, 1] = {r | r โˆˆ โ„, 0 โ‰ค r โ‰ค 1}
  • Open Interval (a, b): Excludes endpoints - (0, 1) = {r | r โˆˆ โ„, 0 < r < 1}
  • Half-Open Intervals: [a, b) or (a, b]

Visual Representation:

  • Filled dot (โ—) means included
  • Open dot (โ—‹) means excluded

3. Relations

Definition

Binary Relation: A relation R on sets A and B is a subset of A ร— B

Cartesian Product A ร— B: A ร— B = {(a, b) | a โˆˆ A, b โˆˆ B}

Notation: If (a, b) โˆˆ R, we often write a R b

Example: Divisibility

R = {(a, b) | a, b โˆˆ โ„•, a ร— b = 63}

Elements: (1, 63), (3, 21), (7, 9), (9, 7), (21, 3), (63, 1)

Properties of Relations

  • Reflexivity: Every element relates to itself
  • Symmetry: If a relates to b, then b relates to a
  • Transitivity: If a relates to b and b relates to c, then a relates to c

4. Functions

Definition

Function: A rule that maps inputs to outputs

Notation:

  • x โ†ฆ xยฒ (maps x to x squared)
  • f(x) = xยฒ (function named f)
  • f: X โ†’ Y (function from set X to set Y)
Requirements for Functions
  1. Defined on entire domain: Every input must have an output
  2. Single-valued: Each input maps to exactly ONE output

Key Terminology

  • Domain: The set of all possible inputs
  • Codomain: The set of all possible output values
  • Range: The actual set of values the function achieves (range โŠ† codomain)

Example: f(x) = xยฒ, domain = โ„, codomain = โ„

Range = โ„โ‰ฅ0 = {r | r โˆˆ โ„, r โ‰ฅ 0} (only non-negative reals)

Range โ‰  Codomain (codomain includes negative numbers too)

Types of Functions

Injective Functions (One-to-One)

Definition: Different inputs produce different outputs

If xโ‚ โ‰  xโ‚‚, then f(xโ‚) โ‰  f(xโ‚‚)

โœ“ Injective: f(x) = 3x + 5

โœ— Not Injective: f(x) = xยฒ (since f(5) = f(-5) = 25)

Surjective Functions (Onto)

Definition: Range = Codomain

Every element in codomain has a pre-image

โœ“ Surjective: f(x) = -7x + 10 (with codomain โ„)

โœ— Not Surjective: f(x) = xยฒ (with codomain โ„, only produces non-negative values)

Bijective Functions (One-to-One Correspondence)

Definition: BOTH injective AND surjective

Establishes perfect pairing between domain and codomain

Important: Used to compare sizes of infinite sets

5. Prime Numbers

Definition

Prime Number: A number p is prime if:

  • It has exactly two factors: 1 and p
  • p โ‰  1 (1 is NOT prime - it only has one factor)

Examples: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, ...

First Prime: 2 (only even prime)

Fundamental Theorem of Arithmetic

Every integer greater than 1 can be decomposed into a unique product of prime factors

  • 12 = 2 ร— 2 ร— 3 = 2ยฒ ร— 3
  • 126 = 2 ร— 3 ร— 3 ร— 7 = 2 ร— 3ยฒ ร— 7

Infinity of Primes

Theorem: There are infinitely many prime numbers

  • No largest prime exists
  • Primes continue forever
  • Gaps between primes can be arbitrarily large

6. Irrational Numbers

Historical Context

Ancient Greeks:

  • Pythagoras and followers believed all numbers were rational
  • Knew diagonal of unit square has length โˆš2
  • Spent years trying to prove โˆš2 was rational

Hippasus (around 500 BCE):

  • First to prove โˆš2 is irrational
  • Shocked Pythagorean community
  • Legend: Pythagoreans drowned him to suppress this discovery

Proof that โˆš2 is Irrational

Geometric Insight: In a unit square (sides of length 1), the diagonal has length โˆš2 by Pythagorean theorem

Proof by Contradiction
  1. Assume โˆš2 = p/q in lowest terms
  2. Square both sides: 2 = pยฒ/qยฒ
  3. Therefore: pยฒ = 2qยฒ
  4. This means pยฒ is even โ†’ p is even
  5. Let p = 2k
  6. Then (2k)ยฒ = 2qยฒ โ†’ 4kยฒ = 2qยฒ โ†’ 2kยฒ = qยฒ
  7. This means qยฒ is even โ†’ q is even
  8. But if both p and q are even, they weren't in lowest terms!
  9. Contradiction โ†’ โˆš2 is irrational

Famous Irrational Numbers

  • โˆšn: irrational if n is not a perfect square
  • ฯ€ (Pi): ฯ€ = 3.1415927... (ratio of circumference to diameter)
  • e (Euler's number): e = 2.7182818... (base of natural logarithm)

Properties: Infinite, non-repeating decimal expansions

7. Degrees of Infinity

The Question

Are some infinities larger than others?

Studied by Georg Cantor (1870s)

Tool: Use bijections to compare infinite sets

Countable Sets

Definition: A set X is countable if there exists a bijection f: โ„• โ†’ X

This means X can be "counted" or enumerated as {f(0), f(1), f(2), ...}

Surprising Results

โ„ค is Countable!

Despite having negative numbers, โ„ค has same cardinality as โ„•

Bijection: Interleave positive and negative integers

โ„•: 0, 1, 2, 3, 4, 5, 6, 7, 8, ...

โ„ค: 0, 1, -1, 2, -2, 3, -3, 4, -4, ...

โ„š is Countable!

Despite being dense, โ„š has same cardinality as โ„•

Strategy: Diagonal enumeration of โ„• ร— โ„•

โ„ is NOT Countable!

Cantor's Diagonalization: Proved no enumeration of โ„ exists

Construct a real number that differs from every number in any assumed enumeration

Cardinality Hierarchy

$$|\mathbb{N}| = |\mathbb{Z}| = |\mathbb{Q}| < |\mathbb{R}|$$

Important: Since โ„š is countable and โ„ is uncountable, irrational numbers must be uncountable

There are VASTLY more irrational numbers than rational numbers!

Continuum Hypothesis

Question: Is there a set whose cardinality is strictly between |โ„•| and |โ„|?

Resolution by Paul Cohen (1960s): The Continuum Hypothesis is independent of set theory axioms

Cannot be proved OR disproved within standard set theory - both "yes" and "no" are consistent!

Key Formulas and Notation Summary

Number Sets

  • โ„• = {0, 1, 2, 3, ...}
  • โ„ค = {..., -2, -1, 0, 1, 2, ...}
  • โ„š = {p/q | p, q โˆˆ โ„ค, q โ‰  0}
  • โ„ = all rational and irrational

Set Operations

  • A โŠ† B: A is subset of B
  • A ร— B: Cartesian product
  • |A|: cardinality of A

Functions

  • Injective: xโ‚ โ‰  xโ‚‚ โ‡’ f(xโ‚) โ‰  f(xโ‚‚)
  • Surjective: range = codomain
  • Bijective: both injective & surjective

Cardinality

  • |โ„•| = |โ„ค| = |โ„š| (countable)
  • |โ„| > |โ„š| (uncountable)
  • Irrationals are uncountable
Take Quiz