Algebraic Numbers

Algebraic numbers are complex numbers that are roots of non-zero polynomials with rational coefficients.

Definition and Minimal Polynomials

A number $\alpha \in \mathbb{C}$ is algebraic if there exists a polynomial $P(x) \in \mathbb{Q}[x]$ such that $P(\alpha) = 0$. The unique monic polynomial of lowest degree that $\alpha$ satisfies is called its minimal polynomial.

def evaluate_rational_poly(coeffs, x):
  res = 0
  for i, c in enumerate(coeffs):
      res += c * (x**i)
  return res

# Check if i (sqrt(-1)) is algebraic
# Minimal poly: x^2 + 1
coeffs_i = [1, 0, 1]
import math
val = evaluate_rational_poly(coeffs_i, 1j)
print(f"p(i) = {val}")

# Check if sqrt(2) + sqrt(3) is algebraic
# It satisfies x^4 - 10x^2 + 1 = 0
alpha = math.sqrt(2) + math.sqrt(3)
coeffs_alpha = [1, 0, -10, 0, 1]
print(f"p(sqrt(2)+sqrt(3)) = {evaluate_rational_poly(coeffs_alpha, alpha)}")

Algebraic Integers

An algebraic integer is a root of a monic polynomial with integer coefficients. For example, $\sqrt{2}$ is an algebraic integer, but $1/2$ is not (it is an algebraic number, but its minimal polynomial is $2x - 1$, which is not monic).

Transcendental Numbers

Numbers that are not algebraic are called transcendental. Proving a number is transcendental is usually much harder. Famous examples include $\pi$ and $e$.

import math

# Liouville's constant is transcendental
liouville = sum(10**(-math.factorial(n)) for n in range(1, 10))
print(f"Liouville's constant approx: {liouville}")
print("Transcendental numbers are 'uncountably' more common than algebraic ones.")

Axiomatic Systems

Mathematics is not built on thin air; it is built on Axioms. An axiom is a statement that is taken to be true, to serve as a premise or starting point for further reasoning.

1. ZFC: The Foundation of Set Theory

Almost all modern mathematics is built on Zermeio-Fraenkel Set Theory (ZFC). Think of these as the “low-level assembly instructions” of math.

The Axiom of Extensionality

Two sets are equal if they have the same elements.

• Example: $\{1, 2\}$ is the same as $\{2, 1\}$. The order and repetition don’t matter.
• Code Analogy: In Python, a set behaves exactly like this.

# Demonstrating Extensionality
set_a = {1, 2, 3}
set_b = {3, 2, 1, 1, 2}

print(f"Set A: {set_a}")
print(f"Set B: {set_b}")
print(f"Are they equal? {set_a == set_b}")

The Axiom of Infinity

There exists an infinite set. Without this, we couldn’t formally prove that the set of Natural Numbers ($\mathbb{N}$) exists in its entirety. It allows us to build the infinite sequence $\{0, 1, 2, \dots\}$.

The Axiom of Choice (the C in ZFC)

If you have a collection of bins, you can choose one item from each bin. This seems obvious, but for infinitely many bins, it leads to strange results like the Banach-Tarski Paradox, where you can disassemble a sphere and reassemble it into two identical spheres.

2. Russell’s Paradox

Before ZFC, mathematicians used “Naive Set Theory.” Bertrand Russell showed this was broken with a simple logical trap:

Consider the set $S$ of all sets that do not contain themselves. Does $S$ contain itself?

# The Logic of Russell's Paradox
def check_membership(contains_self):
  # Definition of S: x is in S if x does NOT contain itself.
  # If we check if S is in S:
  return not contains_self

# There is no stable answer!
print(f"If we assume True -> {check_membership(True)}")
print(f"If we assume False -> {check_membership(False)}")

ZFC fixes this by making it impossible to define “the set of all sets.” You can only create sub-sets of existing sets (the Axiom of Specification).

3. Why Formalize?

We formalize mathematics to ensure that our proofs are not just “convincing” but mechanically certain. If our foundational axioms have a contradiction, everything we build on top of them (calculus, physics, computer science) would collapse.

Exercises

Cardinality and Infinite Sets

Cardinality is a measure of the “number of elements” of a set. For finite sets, this is just a natural number, but for infinite sets, things become more complex.

Equinumerosity

Two sets $A$ and $B$ have the same cardinality, $|A| = |B|$, if there exists a bijection $f: A \to B$.

A set is countably infinite if it has the same cardinality as the natural numbers $\mathbb{N}$. Surprisingly, the set of rational numbers $\mathbb{Q}$ is countable, while the set of real numbers $\mathbb{R}$ is not.

def count_to_infinity(limit):
  # Demonstrating that Even numbers are equinumerous to Natural numbers
  # f(n) = 2n
  evens = [(n, 2*n) for n in range(limit)]
  return evens

print("Mapping N to Evens (First 5):")
for pair in count_to_infinity(5):
  print(f"n={pair[0]} maps to even={pair[1]}")

Cantor’s Diagonal Argument

Georg Cantor proved that the cardinality of the real numbers (the Continuum, $\mathfrak{c}$) is strictly greater than the cardinality of the natural numbers ($\aleph_0$). He used a technique called diagonalization.

import random

def cantors_diagonal(rows):
  """Given a list of decimal expansions, create a number that isn't in the list."""
  new_number = "0."
  for i in range(len(rows)):
      # Take the i-th digit of the i-th row and change it
      digit = int(rows[i][i+2]) # offset for "0."
      new_digit = (digit + 1) % 10
      new_number += str(new_digit)
  return new_number

sequences = ["0.12345", "0.55555", "0.98765", "0.11111", "0.00000"]
print(f"Generated number not in list: {cantors_diagonal(sequences)}")

Cantor’s Theorem

Cantor’s Theorem states that for any set $A$, the cardinality of its power set $\mathcal{P}(A)$ is strictly greater than the cardinality of $A$: $|A| < |\mathcal{P}(A)|$ This results in an infinite hierarchy of infinities: $\aleph_0, \aleph_1, \aleph_2, \dots$

Category Theory

Category theory formalizes mathematical structure and its concepts in terms of a collection of objects and arrows (morphisms).

Categories and Morphisms

A category $\mathcal{C}$ consists of:

• A class $ob(\mathcal{C})$ of objects.
• A class $hom(\mathcal{C})$ of morphisms (arrows) between objects.
• A composition law $\circ$ that is associative and has identity morphisms.

Examples include Set (sets and functions), Grp (groups and homomorphisms), and Top (topological spaces and continuous maps).

class Category:
  def __init__(self, name):
      self.name = name
      self.objects = set()
      self.morphisms = {} # (A, B) -> list of f

  def add_object(self, obj):
      self.objects.add(obj)

  def add_morphism(self, source, target, name):
      if (source, target) not in self.morphisms:
          self.morphisms[(source, target)] = []
      self.morphisms[(source, target)].append(name)

# Modeling a simple Finite Category
C = Category("SimpleFinite")
C.add_object("A")
C.add_object("B")
C.add_morphism("A", "B", "f")
C.add_morphism("B", "B", "id_B")

print(f"Objects in {C.name}: {C.objects}")
print(f"Morphisms: {C.morphisms}")

Functors

A Functor $F: \mathcal{C} \to \mathcal{D}$ is a mapping that preserves the category structure:

1. It maps objects in $\mathcal{C}$ to objects in $\mathcal{D}$.
2. It maps morphisms $f: A \to B$ in $\mathcal{C}$ to morphisms $F(f): F(A) \to F(B)$ in $\mathcal{D}$.
3. It preserves identity and composition.

Natural Transformations

A natural transformation provides a way of transforming one functor into another while respecting the internal structure of the categories involved. It is often described as a “morphism between functors.”

Yoneda Lemma

The Yoneda Lemma suggests that an object is entirely determined by its relationships (morphisms) with other objects in the category. This is a foundational result that allows one to embed any category into a category of functors.

Chaos Theory and Fractals

Chaos theory explores systems that are highly sensitive to initial conditions—a concept popularly known as the “Butterfly Effect.” Fractals are complex geometric shapes that exhibit self-similarity across different scales.

Sensitive Dependence on Initial Conditions

In a chaotic system, small differences in initial state lead to vastly different outcomes over time. This makes long-term prediction impossible, even for deterministic systems.

def logistic_map(x, r):
  return r * x * (1 - x)

r = 3.9 # Chaotic regime
x1 = 0.5
x2 = 0.500001
dt = []

print("Comparison of two nearly identical starting points:")
for i in range(10):
  x1 = logistic_map(x1, r)
  x2 = logistic_map(x2, r)
  print(f"Iteration {i}: x1={x1:.4f}, x2={x2:.4f}, diff={abs(x1-x2):.6f}")

Bifurcation

As a system parameter (like $r$ in the logistic map) changes, the qualitative behavior of the system can change abruptly at certain values, called bifurcation points.

Fractals and Hausdorff Dimension

Fractals are objects with non-integer dimensions. The Hausdorff dimension measures how a set fills space as it is scaled. For the Cantor set or the Koch snowflake, this dimension is a fraction.

import numpy as np

def mandelbrot(c, max_iter=100):
  z = 0
  for n in range(max_iter):
      if abs(z) > 2:
          return n
      z = z*z + c
  return max_iter

# Testing a few points
points = [complex(0, 0), complex(1, 1), complex(-1, 0)]
for p in points:
  res = mandelbrot(p)
  status = "Inside" if res == 100 else f"Escaped at iter {res}"
  print(f"Point {p}: {status}")

Strange Attractors

A strange attractor is an attractor that exhibits chaotic behavior. The most famous example is the Lorenz Attractor, which arises from a simplified model of atmospheric convection.

Complex Numbers

Complex numbers expand the real number system by introducing the imaginary unit $i$, where $i^2 = -1$.

Arithmetic in the Complex Plane

A complex number $z$ is written as $x + iy$, where $x$ is the real part and $y$ is the imaginary part. Addition and multiplication follow standard algebraic rules, with $i^2 = -1$.

# Python supports complex numbers natively using 'j'
z1 = 3 + 4j
z2 = 1 - 2j

# Addition
print(f"z1 + z2 = {z1 + z2}")

# Multiplication (3+4j)*(1-2j) = 3 - 6j + 4j - 8j^2 = 3 - 2j + 8 = 11 - 2j
print(f"z1 * z2 = {z1 * z2}")

# Magnitude (Absolute Value)
print(f"|z1| = {abs(z1)}")

Polar Form and Euler’s Formula

Complex numbers can be represented in polar coordinates $(r, \theta)$. Euler’s Formula connects the exponential function to trigonometry: $e^{i\theta} = \cos \theta + i \sin \theta$ Thus, $z = r e^{i\theta}$.

import cmath
import math

z = 1 + 1j
r, theta = cmath.polar(z)
print(f"r: {r:.3f}, theta: {theta:.3f} rad")

# Euler's Identity: e^(i*pi) + 1 = 0
identity = cmath.exp(1j * math.pi) + 1
print(f"e^(i*pi) + 1 = {identity.real:.1f} + {identity.imag:.1f}j")

Fundamental Theorem of Algebra

The Fundamental Theorem of Algebra states that every non-constant polynomial of degree $n$ with complex coefficients has exactly $n$ complex roots (counting multiplicity).

Diophantine Equations

Diophantine equations are polynomial equations for which only integer or rational solutions are sought.

Linear Diophantine Equations

A linear Diophantine equation has the form $ax + by = c$. This has integer solutions if and only if $\gcd(a, b)$ divides $c$.

def extended_gcd(a, b):
  if a == 0: return b, 0, 1
  gcd, x1, y1 = extended_gcd(b % a, a)
  x = y1 - (b // a) * x1
  y = x1
  return gcd, x, y

def solve_linear_diophantine(a, b, c):
  gcd, x0, y0 = extended_gcd(a, b)
  if c % gcd != 0:
      return None, "No solution"
  m = c // gcd
  return (x0 * m, y0 * m), f"gcd({a}, {b}) = {gcd}"

# Solve 12x + 15y = 9
print(f"Solution to 12x + 15y = 9: {solve_linear_diophantine(12, 15, 9)}")
# Solve 12x + 15y = 10
print(f"Solution to 12x + 15y = 10: {solve_linear_diophantine(12, 15, 10)}")

Pythagorean Triples

The equation $x^2 + y^2 = z^2$ is one of the most famous Diophantine equations. Primitive solutions can be generated using Euclid’s formula: $x = m^2 - n^2, y = 2mn, z = m^2 + n^2$ for $m > n > 0$.

def generate_pythagorean_triples(limit):
  triples = []
  for m in range(2, int(limit**0.5) + 2):
      for n in range(1, m):
          x = m**2 - n**2
          y = 2 * m * n
          z = m**2 + n**2
          if z <= limit:
              triples.append((x, y, z))
  return triples

print(f"Triples up to 30: {generate_pythagorean_triples(30)}")

Fermat’s Last Theorem

Fermat’s Last Theorem states that $x^n + y^n = z^n$ has no positive integer solutions for $n > 2$. This was conjectured by Pierre de Fermat in 1637 and finally proven by Andrew Wiles in 1994 using the theory of modular forms.

Elliptic Curves

Diophantine equations of the form $y^2 = x^3 + ax + b$ are known as Elliptic Curves. They have profound applications in modern cryptography and were crucial in the proof of Fermat’s Last Theorem.

Distributions and Generalized Functions

In many physical applications, we encounter objects like the Dirac delta function that are not “functions” in the classical sense. Distribution theory provides a rigorous mathematical framework for these entities.

The Problem with Classical Functions

A classical function $f: \mathbb{R} \to \mathbb{R}$ has a value at every point. However, an idealized point mass or a sudden impulse has a “value” of infinity at a point and zero elsewhere, yet its integral is finite.

Distributions as Linear Functionals

A distribution $T$ is a continuous linear functional on the space of test functions $D$ (smooth functions with compact support). We denote the action of a distribution $T$ on a test function $\phi$ as $\langle T, \phi \rangle$.

The Dirac Delta Distribution

The Dirac delta $\delta$ is defined by its effect under an integral (or pairing): $\langle \delta, \phi \rangle = \phi(0)$ For any test function $\phi$.

import numpy as np

def gaussian_approximation(x, epsilon):
  """The Dirac delta can be viewed as the limit of a zero-centered Gaussian."""
  return (1.0 / (epsilon * np.sqrt(np.pi))) * np.exp(-(x/epsilon)**2)

x_vals = np.linspace(-1, 1, 100)
# As epsilon -> 0, the peak gets higher and narrower
peak_01 = gaussian_approximation(0, 0.1)
peak_001 = gaussian_approximation(0, 0.01)

print(f"Peak with epsilon=0.1:  {peak_01:.2f}")
print(f"Peak with epsilon=0.01: {peak_001:.2f}")
print("The area under these curves is always 1.")

Weak Derivatives

Distribution theory allows us to define the derivative of any locally integrable function. If $f$ is a distribution, its weak derivative $f'$ is defined by: $\langle f', \phi \rangle = -\langle f, \phi' \rangle$ This formula is inspired by the integration by parts formula where boundary terms vanish for test functions.

Sobolev Spaces

Sobolev spaces are spaces of functions whose weak derivatives exist and belong to $L^p$ spaces. They are essential in the study of partial differential equations.

Divisibility and Congruence

Divisibility is the fundamental relation of number theory. We say $a$ divides $b$ ($a \mid b$) if there exists an integer $k$ such that $b = ak$.

1. The Division Algorithm

For any integers $a$ and $b$ (with $b > 0$), there exist unique integers $q$ (quotient) and $r$ (remainder) such that: $a = bq + r, \quad 0 \le r < b$

def division_demo(a, b):
  q = a // b
  r = a % b
  print(f"{a} = {b} * {q} + {r}")
  return q, r

division_demo(103, 7)

2. Congruence Relations

Gauss introduced the notation $a \equiv b \pmod{n}$ to signify that $a$ and $b$ have the same remainder when divided by $n$. This is an equivalence relation, meaning it is reflexive, symmetric, and transitive.

Properties of Congruence:

1. If $a \equiv b$ and $c \equiv d$, then $a + c \equiv b + d \pmod{n}$.
2. If $a \equiv b$ and $c \equiv d$, then $ac \equiv bd \pmod{n}$.
3. $a^k \equiv b^k \pmod{n}$ for any $k \ge 0$.

3. Fast Modular Exponentiation

In cryptography, we often calculate $a^b \bmod n$ where $b$ is a massive number. We use the “Square and Multiply” algorithm to do this in logarithmic time.

def fast_pow(base, power, mod):
  result = 1
  while power > 0:
      if power % 2 == 1:
          result = (result * base) % mod
      base = (base * base) % mod
      power //= 2
  return result

# Calculate 7^100 mod 13
print(f"7^100 mod 13: {fast_pow(7, 100, 13)}")
# Compare with Python's built-in pow()
print(f"Verify with pow(7, 100, 13): {pow(7, 100, 13)}")

4. Fermat’s Little Theorem

If $p$ is prime and $a$ is not divisible by $p$, then $a^{p-1} \equiv 1 \pmod{p}$. This provides a fast way to check if a number is probably prime (the Fermat Primality Test).

5. Summary Check

Dynamical Systems

A Dynamical System is a triplet $(T, M, \Phi)$ where $T$ is the time domain, $M$ is the Phase Space (manifold of possible states), and $\Phi: T \times M \to M$ is an evolution function satisfying:

1. $\Phi(0, x) = x$ (Identity)
2. $\Phi(t, \Phi(s, x)) = \Phi(t+s, x)$ (Group property)

Discrete Dynamics: Iterated Maps

In a discrete system, the state is updated by a map $f: M \to M$: $x_{n+1} = f(x_n)$

The sequence $\{x_n\}_{n=0}^\infty$ is called the Orbit of $x_0$.

def logistic_map(x, r):
  return r * x * (1 - x)

def iterate(f, x0, n):
  curr = x0
  for _ in range(n):
      curr = f(curr)
  return curr

# Test logistic map at r=2.5 (Stable fixed point)
r = 2.5
f = lambda x: logistic_map(x, r)
print(f"Iteration 10: {iterate(f, 0.5, 10):.3f}")
print(f"Iteration 50: {iterate(f, 0.5, 50):.3f}")
print("At r=2.5, the system settles to a single point.")

Fixed Points and Stability

A fixed point $x^*$ satisfies $f(x^*) = x^*$.

• A point is Lyapunov Stable if for every $\epsilon > 0$, there exists $\delta > 0$ such that $d(x_0, x^*) < \delta \implies d(x_n, x^*) < \epsilon$ for all $n > 0$.
• For a differentiable map $f: \mathbb{R} \to \mathbb{R}$, $x^*$ is Asymptotically Stable if $|f'(x^*)| < 1$.

def check_stability(f_prime, x_star):
  derivative_val = f_prime(x_star)
  is_stable = abs(derivative_val) < 1
  return is_stable, derivative_val

# For logistic map, f'(x) = r(1 - 2x)
# Fixed point x* = 1 - 1/r
r = 3.2
x_star = 1 - 1/r
f_prime = lambda x: r * (1 - 2 * x)

print(f"Is fixed point stable at r=3.2? {check_stability(f_prime, x_star)}")
print("At r=3.2, |f'(x*)| > 1, so the fixed point is unstable (leads to limit cycles).")

Continuous Dynamics: Flow

Continuous systems are defined by a vector field $\mathbf{V}: M \to TM$ and an autonomous differential equation: $\dot{\mathbf{x}} = \frac{d\mathbf{x}}{dt} = \mathbf{f}(\mathbf{x})$

The solution through $x_0$ is the Integral Curve or Flow Line. Stability is determined by the eigenvalues of the Jacobian Matrix $J = \nabla \mathbf{f}$. If all eigenvalues have negative real parts, the equilibrium is stable.

Mathematics: Recap and Future Directions

We have traveled from the building blocks of set theory and logic, through the structures of algebra and the continuity of calculus, to the advanced landscapes of topology and manifolds.

The Unity of Mathematics

Mathematics is not a collection of isolated subjects but a deeply interconnected web. The tools you learned in linear algebra are used to solve differential equations, which in turn describe the curvature of manifolds in topology.

import numpy as np

# A final synthesis: Linear Algebra + Numerical Methods
def solve_system(A, b):
  """Solving a linear system is the core of most applied mathematics."""
  return np.linalg.solve(A, b)

A = np.array([[3, 1], [1, 2]])
b = np.array([9, 8])
sol = solve_system(A, b)
print(f"System Solution: {sol}")

Unsolved Problems

Despite centuries of progress, many fundamental questions remain unanswered. Solving any of these would revolutionize our understanding of the universe:

• The Riemann Hypothesis: Concerning the distribution of prime numbers.
• P vs NP: Whether every problem whose solution can be quickly verified can also be quickly solved.
• Navier-Stokes Existence and Smoothness: Describing the motion of fluid flow.

Continuing the Journey

Mathematics is a creative endeavor. The skills of abstraction, logical deduction, and problem-solving you’ve developed are applicable far beyond the textbook. Whether you pursue theoretical research or apply these principles in engineering, finance, or data science, the language of mathematics will remain your most powerful tool.

# Final challenge: Can you write a function for your favorite math concept?
print("Success. Mathematics is an open field for exploration.")

Homological Algebra

Homological algebra is the branch of mathematics that studies homology in a general algebraic setting. It is a powerful tool used in algebraic topology, algebraic geometry, and number theory.

Chain Complexes

A chain complex $(C_\bullet, d_\bullet)$ is a sequence of abelian groups (or modules) and homomorphisms: $\dots \xrightarrow{d_{n+1}} C_n \xrightarrow{d_n} C_{n-1} \xrightarrow{d_{n-1}} \dots$ such that the composition of any two consecutive maps is zero: $d_n \circ d_{n+1} = 0$.

This condition implies that the image of $d_{n+1}$ is contained in the kernel of $d_n$: $im(d_{n+1}) \subseteq ker(d_n)$.

import numpy as np

def is_chain_complex(matrices):
  """Check if a sequence of boundary matrices forms a chain complex."""
  for i in range(len(matrices) - 1):
      # Result of d_n * d_{n+1} should be zero matrix
      prod = np.matmul(matrices[i], matrices[i+1])
      if not np.allclose(prod, 0):
          return False, i
  return True, None

# Example: d1 * d2 = 0
d1 = np.array([[1, -1, 0], [0, 1, -1]]) # Edges to vertices
d2 = np.array([[1], [1], [1]])          # Triangle face to edges

is_valid, index = is_chain_complex([d1, d2])
print(f"Is chain complex: {is_valid}")

Homology Groups

The $n$-th homology group is the quotient group: $H_n(C) = \frac{ker(d_n)}{im(d_{n+1})}$ Elements of $ker(d_n)$ are called cycles, and elements of $im(d_{n+1})$ are called boundaries. Homology measures the extent to which the complex is not “exact.”

Exact Sequences

A sequence is exact if the image of each map is exactly the kernel of the next. A short exact sequence is a sequence of the form: $0 \to A \xrightarrow{f} B \xrightarrow{g} C \to 0$ which implies that $f$ is injective, $g$ is surjective, and $im(f) = ker(g)$.

Diagram Chasing and the Snake Lemma

Diagram chasing is a method of proof used in homological algebra to establish properties of morphisms by tracing elements through commutative diagrams. The Snake Lemma is a fundamental result that relates the kernels and cokernels of two morphisms between short exact sequences.

The Nature of Mathematics

Mathematics is the science of structure, order, and relation that has evolved from elemental practices of counting, measuring, and describing the shapes of objects. It deals with logical reasoning and quantitative calculation.

Abstraction

The power of mathematics lies in its ability to abstract. By stripping away the specific details of a problem, we can find universal patterns that apply to many different situations. For example, the number “3” is an abstraction that represents the commonality between 3 apples, 3 planets, and 3 ideas.

def count_elements(iterable):
  """Abstraction: Counting works the same way regardless of what we count."""
  count = 0
  for _ in iterable:
      count += 1
  return count

apples = ["fuji", "gala", "granny smith"]
planets = ["Mercury", "Venus", "Earth"]

print(f"Apples: {count_elements(apples)}")
print(f"Planets: {count_elements(planets)}")

Formalism and Proof

Mathematics is not just about calculation; it is about rigorous proof. A mathematical truth is one that follows logically from a set of starting assumptions (axioms). Once a theorem is proven, it remains true forever.

Applied Mathematics

While pure mathematics focuses on the intrinsic properties of mathematical structures, applied mathematics uses these structures to model the world around us—from the motion of stars to the behavior of financial markets.

import numpy as np

def simple_growth_model(initial_pop, growth_rate, time):
  """Mathematical model of exponential growth."""
  return initial_pop * (1 + growth_rate)**time

print(f"Population after 10 years (5% growth): {simple_growth_model(100, 0.05, 10):.2f}")

Advanced Logic

Once we have the rules of deduction, we must ask ourselves about the power and reliability of the system itself. This is the domain of Meta-logic.

Soundness and Completeness

• Soundness: A logic system is sound if everything that can be proved is actually true. If you can derive $Q$ from $P$, then $P \implies Q$ is a tautology.
• Completeness: A logic system is complete if everything that is true can be proved. If $P \implies Q$ is a tautology, there exists a sequence of steps to derive $Q$ from $P$.

Propositional logic is both sound and complete. This means the “mechanical” process of manipulation perfectly matches the “semantic” truth of the universe.

Model Theory

Model theory studies the relationship between formal languages and their interpretations. A Model is a mathematical structure that makes the statements of a theory true.

If a set of statements has at least one model, it is Satisfiable. If it is true in all models, it is Valid.

Let’s use Python to check if a simple set of constraints is satisfiable (the SAT problem).

# A primitive SAT Solver
# We want to find A, B such that:
# (A OR B) AND (NOT A OR B) AND (A OR NOT B)

def check_constraints(A, B):
  c1 = A or B
  c2 = (not A) or B
  c3 = A or (not B)
  return c1 and c2 and c3

# Brute force all possibilities
possibilities = [(False, False), (False, True), (True, False), (True, True)]
solutions = [p for p in possibilities if check_constraints(p[0], p[1])]

print(f"Combinations: {possibilities}")
print(f"Valid Solutions (A, B): {solutions}")

In computer science, solving this efficiently ($P$ vs $NP$) is one of the most important open questions in mathematics.

Exercises

Gödel’s Incompleteness

In 1900, David Hilbert challenged the world to find a complete and consistent set of axioms for all of mathematics. He wanted a “Master Algorithm” that could prove or disprove any statement. In 1931, Kurt Gödel proved this dream was impossible.

1. The First Theorem: Truth vs. Provability

Gödel showed that in any system capable of arithmetic, there are statements that are True but Unprovable.

He did this by creating a “Gödel Sentence” ($G$), which states:

“This statement cannot be proved within this axiomatic system.”

Let’s look at the logical trap:

• If the system can prove $G$, then $G$ is false (because $G$ says it can’t be proved). This means the system proves something false—it is Inconsistent.
• If the system cannot prove $G$, then $G$ is true (because it correctly says it can’t be proved). This means there is a truth the system can’t reach—it is Incomplete.

We prefer Consistency over Completeness. Thus, math is incomplete.

2. A Coding Analogy: The Halting Problem

The Halting Problem in computer science is the direct descendant of Gödel’s work. It proves that you cannot write a program will_halt(code) that correctly predicts if any given piece of code will eventually stop or run forever.

# A simplified demonstration of the 'Turing Trap'
def will_halt(func):
  # Imagine this is a perfect predictor...
  pass

def paradox():
  if will_halt(paradox):
      while True: # If it says I halt, I run forever
          pass
  else:
      return # If it says I run forever, I halt

# The logic of the predictor must fail here.

3. The Second Theorem: Trusting the Foundation

Gödel’s second theorem is even more startling: A system cannot prove its own consistency.

If you use a system (like ZFC) to prove that ZFC has no contradictions, you are essentially “grading your own homework.” To prove ZFC is consistent, you need a stronger system with more axioms. But that stronger system then needs an even stronger one to prove its consistency, and so on, forever.

4. Summary of the Course

We have climbed the ladder of abstraction:

1. Propositional Logic: Computing with Bits.
2. Predicate Logic: Quantifying the World.
3. Boolean Algebra: Designing Circuits.
4. Axioms: The Rules of the Game.
5. Incompleteness: The limits of the Game.

Exercises

Propositional Logic

Propositional logic is the branch of logic that deals with propositions—statements that are either definitely True (T) or definitely False (F). It is the language that computers reflect in their hardware, where every signal is high (1) or low (0).

1. What is a Proposition?

A proposition must have a fixed truth value.

• Propositions:
  • “The sun is a star.” (True)
  • “2 + 2 = 5.” (False)
• Non-Propositions:
  • “Close the door!” (Command)
  • “What time is it?” (Question)
  • “This sentence is false.” (The Liar’s Paradox - it cannot be consistently True or False)

2. Logical Operators in Code

In programming, we use operators to combine these truth values. Let’s see how the basic connectives behave using Python’s boolean logic.

# Logical Truth Tables in Python
def truth_table():
  print("P      | Q      | P AND Q | P OR Q | NOT P")
  print("-" * 45)
  for P in [True, False]:
      for Q in [True, False]:
          res_and = P and Q
          res_or = P or Q
          res_not = not P
          print(f"{str(P):<6} | {str(Q):<6} | {str(res_and):<7} | {str(res_or):<6} | {str(res_not):<5}")

truth_table()

3. The Implication ($\implies$)

The implication “If $P$, then $Q$” is a promise. It is only broken (False) if $P$ is True but $Q$ fails to happen (is False).

Example: “If you pass the exam ($P$), I will buy you a car ($Q$).”

• If you pass ($P=T$) and you get the car ($Q=T$): Promise kept.
• If you pass ($P=T$) but you don’t get the car ($Q=F$): Promise broken.
• If you fail ($P=F$): It doesn’t matter if I buy you a car or not; the promise wasn’t triggered. Therefore, the statement is vacuously true.

4. De Morgan’s Laws in Action

De Morgan’s laws allow us to simplify complex logic. In code, this is vital for readability.

• not (A and B) is the same as (not A) or (not B)
• not (A or B) is the same as (not A) and (not B)

# Testing De Morgan's Law
A = True
B = False

# Left side: not (A and B)
lhs = not (A and B)
# Right side: (not A) or (not B)
rhs = (not A) or (not B)

print(f"not (A and B): {lhs}")
print(f"(not A) or (not B): {rhs}")
print(f"They are equal: {lhs == rhs}")

Exercises

Mathematical Notation and Logic

Mathematics uses a concise symbolic language to express complex ideas. Understanding this notation is essential for reading and writing formal proofs.

Logical Operators

The building blocks of mathematical logic are propositions and operators:

• Negation ($\neg P$): “Not $P$“.
• Conjunction ($P \land Q$): ”$P$ and $Q$“.
• Disjunction ($P \lor Q$): ”$P$ or $Q$“.
• Implication ($P \implies Q$): “If $P$, then $Q$“.
• Equivalence ($P \iff Q$): ”$P$ if and only if $Q$“.

def logical_implication(p, q):
  # P => Q is equivalent to (not P) or Q
  return (not p) or q

print("Truth Table for P => Q")
print("P | Q | P => Q")
for p in [True, False]:
  for q in [True, False]:
      print(f"{p} | {q} | {logical_implication(p, q)}")

Quantifiers

Quantifiers allow us to make statements about sets of elements:

• Universal Quantifier ($\forall$): “For all”.
• Existential Quantifier ($\exists$): “There exists”.

numbers = [1, 2, 3, 4, 5]

# For all x in numbers, x > 0
all_positive = all(x > 0 for x in numbers)
print(f"Universal (forall x > 0): {all_positive}")

# There exists x in numbers such that x is even
exists_even = any(x % 2 == 0 for x in numbers)
print(f"Existential (exists x even): {exists_even}")

Set Notation

• $x \in A$: ”$x$ is an element of $A$“.
• $A \subseteq B$: ”$A$ is a subset of $B$“.
• $A \cap B$: Intersection.
• $A \cup B$: Union.

Number Theory: The Queen of Mathematics

Number theory is the study of the set of integers $\mathbb{Z}$. While the objects of study are simple, the problems are among the most difficult and beautiful in all of mathematics.

1. Prime Numbers and Factorization

A prime number is an integer $p > 1$ whose only divisors are $1$ and itself. The Fundamental Theorem of Arithmetic states that every integer $n > 1$ has a unique prime factorization.

Primes are the “atoms” of the number system. We can find them efficiently using the Sieve of Eratosthenes.

def sieve(n):
  primes = [True] * (n + 1)
  p = 2
  while (p * p <= n):
      if (primes[p]):
          for i in range(p * p, n + 1, p):
              primes[i] = False
      p += 1
  return [p for p in range(2, n + 1) if primes[p]]

# Find all primes up to 100
print(f"Primes up to 100: {sieve(100)}")

2. Greatest Common Divisor (GCD)

The GCD of two integers $a$ and $b$ is the largest positive integer that divides both. The Euclidean Algorithm calculates this by repeatedly applying the remainder operation: $\text{gcd}(a, b) = \text{gcd}(b, a \bmod b)$.

def gcd(a, b):
  while b:
      a, b = b, a % b
  return a

print(f"GCD of 48 and 18: {gcd(48, 18)}")
print(f"GCD of 101 and 103: {gcd(101, 103)}")

3. Modular Arithmetic: “Clock Math”

In modular arithmetic, we work with remainders. We say $a \equiv b \pmod{n}$ if $n$ divides $(a-b)$. This system forms a Ring, which is the basis for modern cryptography (like RSA).

4. Bezout’s Identity and Modular Inverses

Bezout’s Identity states that for any non-zero $a, b$, there exist integers $x, y$ such that $ax + by = \text{gcd}(a, b)$. We can find these coefficients using the Extended Euclidean Algorithm. This is how we find Modular Inverses, which allow us to “divide” in modular arithmetic.

def extended_gcd(a, b):
  if a == 0:
      return b, 0, 1
  gcd, x1, y1 = extended_gcd(b % a, a)
  x = y1 - (b // a) * x1
  y = x1
  return gcd, x, y

# Find modular inverse of 3 mod 11
# We need x such that 3x = 1 (mod 11)
g, x, y = extended_gcd(3, 11)
if g == 1:
  print(f"Modular inverse of 3 mod 11 is: {x % 11}")

5. Summary Check

Number Systems and Arithmetic

The study of mathematics begins with numbers. We build complex systems from simple foundations, starting with the natural numbers.

The Hierarchy of Numbers

1. Natural Numbers ($\mathbb{N}$): $\{0, 1, 2, 3, \dots\}$ (counting numbers).
2. Integers ($\mathbb{Z}$): $\{\dots, -2, -1, 0, 1, 2, \dots\}$.
3. Rational Numbers ($\mathbb{Q}$): Fractions $p/q$ where $p, q \in \mathbb{Z}$ and $q \neq 0$.
4. Real Numbers ($\mathbb{R}$): Includes irrational numbers like $\sqrt{2}$ and $\pi$.
5. Complex Numbers ($\mathbb{C}$): Numbers of the form $a + bi$.

import numpy as np

def classify_number(n):
  if isinstance(n, complex):
      return "Complex"
  if n % 1 == 0:
      return "Integer/Natural"
  return "Fractional/Real"

test_cases = [42, 3.1415, complex(1, 2)]
for n in test_cases:
  print(f"{n} is {classify_number(n)}")

Peano Axioms

The natural numbers are rigorously defined by the Peano axioms, which use a single constant $0$ and a successor function $S(n)$.

• $0$ is a natural number.
• For every $n$, $S(n)$ is a natural number.
• No two numbers have the same successor.
• $0$ is not the successor of any number.

Fundamental Theorem of Arithmetic

Every integer greater than 1 either is a prime number itself or can be represented as a unique product of prime numbers.

def prime_factors(n):
  i = 2
  factors = []
  while i * i <= n:
      if n % i:
          i += 1
      else:
          n //= i
          factors.append(i)
  if n > 1:
      factors.append(n)
  return factors

print(f"Factors of 12: {prime_factors(12)}")
print(f"Factors of 37: {prime_factors(37)}")

Numerical Root Finding

Numerical root finding is the process of finding an approximate value $x$ such that $f(x) = 0$ for a given continuous function $f$.

The Bisection Method

The Bisection method is a robust but slow root-finding algorithm. It works by repeatedly bisecting an interval and then selecting a subinterval in which a root must lie for further processing. It requires that the function values at the endpoints of the interval have opposite signs (Bolzano’s Theorem).

def f(x):
  return x**3 - x - 2

def bisection(a, b, tol=1e-5):
  if f(a) * f(b) >= 0:
      return "Bisection fails (no sign change)."
  
  while (b - a) / 2 > tol:
      midpoint = (a + b) / 2
      if f(midpoint) == 0:
          return midpoint
      elif f(a) * f(midpoint) < 0:
          b = midpoint
      else:
          a = midpoint
  return (a + b) / 2

root = bisection(1, 2)
print(f"Bisection root: {root:.6f}")
print(f"f(root): {f(root):.6e}")

Newton-Raphson Method

The Newton-Raphson method uses the first two terms of the Taylor series to iteratively improve an estimate. $x_{n+1} = x_n - \frac{f(x_n)}{f'(x_n)}$

def f(x):
  return x**3 - x - 2

def df(x):
  return 3*x**2 - 1

def newton(x0, tol=1e-5, max_iter=100):
  x = x0
  for i in range(max_iter):
      delta = f(x) / df(x)
      x = x - delta
      if abs(delta) < tol:
          return x, i
  return x, max_iter

root, iterations = newton(1.5)
print(f"Newton root: {root:.6f} found in {iterations} iterations")

Convergence and Stability

Newton’s method converges quadratically ($e_{n+1} \approx C e_n^2$), meaning the number of correct digits roughly doubles each iteration. However, it can fail or diverge if $f'(x)$ is near zero or if the initial guess is far from a root.

Predicate Logic (First-Order Logic)

Propositional logic is great for simple true/false statements, but it can’t handle variables. We cannot say “x is even” in propositional logic because $x$ is unknown. Predicate Logic solves this by introducing variables and Quantifiers.

1. Predicates as Functions

A Predicate is a statement whose truth depends on one or more variables. In programming, a predicate is simply a function that returns a Boolean.

# A Predicate function in Python
def is_even(n):
  return n % 2 == 0

# Test the predicate with different values
numbers = [1, 2, 3, 4, 5]
for n in numbers:
  print(f"Is {n} even? {is_even(n)}")

The expression ”$x$ is even” is written as $P(x)$. It is not true or false until you provide an $x$.

2. Quantifiers: For All and There Exists

Quantifiers describe the scope of a predicate over a Domain (a set of objects).

1. Universal ($\forall x$): Reads “For all x…“. The statement is true only if the predicate holds for every element in the domain.
2. Existential ($\exists x$): Reads “There exists an x…“. The statement is true if there is at least one element that satisfies the predicate.

In Python, we use the all() and any() functions to represent these quantifiers.

# Domain of integers
domain = [2, 4, 6, 8, 10]

# Universal Quantifier: Are ALL numbers even?
forall_even = all(n % 2 == 0 for n in domain)

# Existential Quantifier: Does there exist a number > 5?
exists_greater_5 = any(n > 5 for n in domain)

print(f"Domain: {domain}")
print(f"For all n, n is even: {forall_even}")
print(f"Exists n such that n > 5: {exists_greater_5}")