Mathematics

The logic of science; coherence relations on quantitative degrees of belief.

• Well-calibrated probabilities

  Even if you’re fairly ignorant, you can still strive to ensure that when you say “70% probability”, it’s true 70% of the time.

• Bayesian reasoning

  A probability-theory-based view of the world; a coherent way of changing probabilistic beliefs based on evidence.

  • Bayesian update

    Bayesian updating: the ideal way to change probabilistic beliefs based on evidence.

    • Extraordinary claims require extraordinary evidence

      The people who adamantly claim they were abducted by aliens do provide some evidence for aliens. They just don’t provide quantitatively enough evidence.

      • Extraordinary claims

        What makes something an ‘extraordinary claim’ that requires extraordinary evidence?

    • Bayesian view of scientific virtues

      Why is it that science relies on bold, precise, and falsifiable predictions? Because of Bayes’ rule, of course.

    • Strength of Bayesian evidence

      From a Bayesian standpoint, the strength of evidence can be identified with its likelihood ratio.

    • Path: Insights from Bayesian updating

      A learning-path placeholder page for insights derived from the Bayesian rule for updating beliefs.

    • Ordinary claims require ordinary evidence

      Extraordinary claims require extraordinary evidence, but ordinary claims don’t.

  • Bayes' rule

    Bayes’ rule is the core theorem of probability theory saying how to revise our beliefs when we make a new observation.

    • Bayes' rule examples

      Interesting problems solvable by Bayes’ rule

      • Realistic (Math 1)

        Real-life examples of Bayesian reasoning

      • Introductory Bayesian problems

        Bayesian problems to try to solve yourself, before beginning to learn about Bayes’ rule.

        • Diseasitis

          20% of patients have Diseasitis. 90% of sick patients and 30% of healthy patients turn a tongue depressor black. You turn a tongue depressor black. What’s the chance you have Diseasitis?

        • Blue oysters

          A probability problem about blue oysters.

        • Sparking widgets
        • Sock-dresser search

          There’s a ⁴⁄₅ chance your socks are in one of your dresser’s 8 drawers. You check 6 drawers at random. What’s the probability they’ll be in the next drawer you check?

    • Waterfall diagram

      Visualizing Bayes’ rule as the mixing of probability streams.

      • Waterfall diagrams and relative odds

        A way to visualize Bayes’ rule that yields an easier way to solve some problems

    • Bayes' rule: Odds form

      The simplest and most easily understandable form of Bayes’ rule uses relative odds.

      • Introduction to Bayes' rule: Odds form

        Bayes’ rule is simple, if you think in terms of relative odds.

    • Proof of Bayes' rule

      Proofs of Bayes’ rule, with graphics

      • Proof of Bayes' rule: Probability form
    • Belief revision as probability elimination

      Update your beliefs by throwing away large chunks of probability mass.

    • Probability notation for Bayes' rule

      The probability notation used in Bayesian reasoning

      • Probability notation for Bayes' rule: Intro (Math 1)

        How to read, and identify, the probabilities in Bayesian problems.

    • Bayes' rule: Vector form

      For when you want to apply Bayes’ rule to lots of evidence and lots of variables, all in one go. (This is more or less how spam filters work.)

    • Bayes' rule: Log-odds form

      A simple transformation of Bayes’ rule reveals tools for measuring degree of belief, and strength of evidence.

    • Bayes' rule: Functional form

      Bayes’ rule for to continuous variables.

    • Bayes' rule: Proportional form

      The fastest way to say something both convincing and true about belief-updating.

    • Bayes' rule: Guide

      The Arbital guide to Bayes’ rule

      • Comprehensive guide to Bayes' Rule

        This is an arc that includes all Bayes content.

      • Introduction to Bayes' Rule odds form

        This is an arc that includes just enough content to teach about Bayes’s Rule odds form.

      • Bayes' Rule and its different forms

        This is an arc that includes different ways to look at Bayes’ Rule.

      • Bayes' Rule and its implications

        This is an arc that includes implications of the Bayes’s Rule.

      • Wants to get straight to Bayes
    • Path: Multiple angles on Bayes's Rule

      A learning-path placeholder page for learning multiple angles on Bayes’s Rule.

    • Shift towards the hypothesis of least surprise

      When you see new evidence, ask: which hypothesis is least surprised?

    • Bayes' rule: Definition
    • Bayes' rule: Probability form

      The original formulation of Bayes’ rule.

      • Odds form to probability form
      • Proof of Bayes' rule: Probability form
    • Frequency diagram

      Visualizing Bayes’ rule by manipulating frequencies in large populations

      • Frequency diagrams: A first look at Bayes

        The most straightforward visualization of Bayes’ rule.

    • Bayes' rule: Beginner's guide

      Beginner’s guide to learning about Bayes’ rule.

    • High-speed intro to Bayes's rule

      A high-speed introduction to Bayes’s Rule on one page, for the impatient and mathematically adept.

  • Prior probability

    What we believed before seeing the evidence.

  • Interest in mathematical foundations in Bayesianism

    “Want” this requisite if you prefer to see extra information about the mathematical foundations in Bayesianism.

  • Posterior probability

    What we believe, after seeing the evidence and doing a Bayesian update.

  • Humans doing Bayes

    The human use of Bayesian reasoning in everyday life

    • Explicit Bayes as a counter for 'worrying'

      Explicitly walking through Bayes’s Rule can summarize your knowledge and thereby stop you from bouncing around pieces of it.

  • Ignorance prior

    Key equations for quantitative Bayesian problems, describing exactly the right shape for what we believed before observation.

    • Inductive prior

      Some states of pre-observation belief can learn quickly; others never learn anything. An “inductive prior” is of the former type.

      • Solomonoff induction

        A simple way to superintelligently predict sequences of data, given unlimited computing power.

        • Solomonoff induction: Intro Dialogue (Math 2)

          An introduction to Solomonoff induction for the unfamiliar reader who isn’t bad at math

      • Laplace's Rule of Succession

        Suppose you flip a coin with an unknown bias 30 times, and see 4 heads and 26 tails. The Rule of Succession says the next flip has a ⁵⁄₃₂ chance of showing heads.

      • Universal prior

        A “universal prior” is a probability distribution containing all the hypotheses, for some reasonable meaning of “all”. E.g., “every possible computer program that computes probabilities”.

  • Strictly confused

    A hypothesis is strictly confused by the raw data, if the hypothesis did much worse in predicting it than the hypothesis itself expected.

  • Finishing your Bayesian path on Arbital

    The page that comes at the end of reading the Arbital Guide to Bayes’ rule

  • Prior

    A state of prior knowledge, before seeing information on a new problem. Potentially complicated.

  • Empirical probabilities are not exactly 0 or 1

    “Cromwell’s Rule” says that probabilities of exactly 0 or 1 should never be applied to empirical propositions—there’s always some probability, however tiny, of being mistaken.

  • Subjective probability

    Probability is in the mind, not in the environment. If you don’t know whether a coin came up heads or tails, that’s a fact about you, not a fact about the coin.

    • Probability distribution: Motivated definition

      People keep writing things like P(sick)=0.3. What does this mean, on a technical level?

  • Likelihood
    • Relative likelihood

      How relatively likely an observation is, given two or more hypotheses, determines the strength and direction of evidence.

    • Likelihood notation
    • Likelihood function
    • Likelihood ratio
• Odds

  Odds express a relative probability.

  • Odds: Introduction

    What’s the difference between probabilities and odds? Why is a 20% probability of success equivalent to 1 : 4 odds favoring success?

  • Odds: Refresher

    A quick review of the notations and mathematical behaviors for odds (e.g. odds of 1 : 2 for drawing a red ball vs. green ball from a barrel).

  • Odds: Technical explanation

    Formal definitions, alternate representations, and uses of odds and odds ratios (like a 1 : 2 chance of drawing a red ball vs. green ball from a barrel).

• Mutually exclusive and exhaustive

  The condition needed for probabilities to sum to 1

• Probability

  The degree to which someone believes something, measured on a scale from 0 to 1, allowing us to do math to it.

  • Joint probability

    The notation for writing the chance that both X and Y are true.

  • Conditional probability

    The notation for writing “The probability that someone has green eyes, if we know that they have red hair.”

    • Conditional probability: Refresher

      Is P(yellow | banana) the probability that a banana is yellow, or the probability that a yellow thing is a banana?

  • Interpretations of "probability"

    What does it mean to say that a fair coin has a 50% probability of coming up heads?

    • Subjective probability

      Probability is in the mind, not in the environment. If you don’t know whether a coin came up heads or tails, that’s a fact about you, not a fact about the coin.

      • Probability distribution: Motivated definition

        People keep writing things like P(sick)=0.3. What does this mean, on a technical level?

    • Correspondence visualizations for different interpretations of "probability"
    • Probability interpretations: Examples
  • Report likelihoods, not p-values
    • Likelihood functions, p-values, and the replication crisis

      What’s the whole Bayesian-vs.-frequentist debate about?

    • Report likelihoods not p-values: FAQ
• Normalization (probability)

  That thingy we do to make sure our probabilities sum to 1, when they should sum to 1.

• Sample space

  The set of possible things that could happen in a part of the world that you are uncertain about.

  • Sample spaces are too large

    Sample spaces are often large, so it is hard to do probabilistic computations using a raw distribution over the sample space.

  • Uncountable sample spaces are way too large

    We can’t define probability distributions over uncountable sample spaces by just assigning numbers to each point in the sample space.

• Probability distribution (countable sample space)

  A function assigning a probability to each point in the sample space.

• Square visualization of probabilities on two events
  • Square visualization of probabilities on two events: (example) Diseasitis

    But it seems like the patient with the black tongue depressor has diseasitis…

• Two independent events

  What do pair of dice, pair of coins, and pair of people on opposite sides of the planet all have in common?

  • Two independent events: Square visualization
• Probability distribution: Motivated definition

  People keep writing things like P(sick)=0.3. What does this mean, on a technical level?

Do you have sufficient mathematical ability that you can read a sentence that uses some algebra or invokes a mathematical idea, without slowing down too much?

The arithmetical hierarchy is a way of classifying logical statements by the number of clauses saying “for every object” and “there exists an object”.

• Arithmetical hierarchy: If you don't read logic

Can you read sentences symbolically stating “For all x: exists y: phi(x, y) or not theta(y)” without slowing down too much?

Are you not actively bad at math, nor traumatized about math?

Is math sometimes fun for you, and are you not anxious if you see a math puzzle you don’t know how to solve?

Do you work with math on a fairly routine basis? Do you have little trouble grasping abstract structures and ideas?

• Math 2 example statements

  If you can read these formulas, you’re in Math 2!

Can you read the sort of things that professional mathematicians read, aka LaTeX formulas with a minimum of explanation?

• Math 3 example statements

  If you can read these formulas, you’re in Math 3!

Can you take integral signs and differentiations in stride?

Some infinities are bigger than others. Uncountable infinities are larger than countable infinities.

• Uncountability: Intro (Math 1)

  Not all infinities are created equal. The infinity of real numbers is infinitely larger than the infinity of counting numbers.

• Uncountability: Intuitive Intro

  Are all sizes of infinity the same? What does “the same” even mean here?

• Uncountability (Math 3)

  Formal definition of uncountability, and foundational considerations.

• Real numbers are uncountable

  The real numbers are uncountable.

The formalism that mathematicians use to talk about arithmetic turns out to be able to talk about itself.

• Quine

  A computer program that prints (or does other computations to) its own source code, using indirect self-reference.

Playpen page for Math domain

The study of binary relations that are reflexive, transitive, and antisymmetic.

• Partially ordered set

  A set endowed with a relation that is reflexive, transitive, and antisymmetric.

  • Poset: Examples
  • Poset: Exercises
  • Greatest lower bound in a poset

    The greatest lower bound is an abstraction of the idea of the greatest common divisor to a general poset.

• Join and meet
  • Join and meet: Examples
  • Join and meet: Exercises
• Lattice (Order Theory)

  A poset that is closed under binary joins and meets.

  • Lattice: Examples
  • Lattice: Exercises
• Totally ordered set

  A set where all the elements can be compared as greater than or less than.

  • Well-ordered set

    An ordered set with an order that always has a “next element”.

• Monotone function

  An order-preserving map between posets.

  • Monotone function: examples
  • Monotone function: exercises
• Complete lattice

  A poset that is closed under arbitrary joins and meets.

What kinds of symmetry can an object have?

• Group

  The algebraic structure that captures symmetry, relationships between transformations, and part of what multiplication and addition have in common.

  • Order of a group
  • Abelian group

    A group where the operation commutes. Named after Niels Henrik Abel.

  • Group: Examples

    Why would anyone have invented groups, anyway? What were the historically motivating examples, and what examples are important today?

  • Group: Exercises

    Test your understanding of the definition of a group with these exercises.

  • Group homomorphism

    A group homomorphism is a “function between groups” that “respects the group structure”.

    • Kernel of group homomorphism
    • Image of the identity under a group homomorphism is the identity

      All group homomorphisms preserve the identity.

    • Under a group homomorphism, the image of the inverse is the inverse of the image

      The operations of “taking inverses” and “applying a group homomorphism” commute: it does not matter in which order we do them.

    • The image of a group under a homomorphism is a subgroup of the codomain

      Group homomorphisms take groups to groups, but it is additionally guaranteed that the elements they hit form a group.

    • The composition of two group homomorphisms is a homomorphism

      The collection of group homomorphisms is closed under composition.

  • Cyclic group

    Cyclic groups form one of the most simple classes of groups.

    • Cyclic Group Intro (Math 0)

      A finite cyclic group is a little bit like a clock.

  • Symmetric group

    The symmetric groups form the fundamental link between group theory and the notion of symmetry.

    • Cayley's Theorem on symmetric groups

      The “fundamental theorem of symmetry”, forging the connection between symmetry and group theory.

    • Cycle notation in symmetric groups

      Cycle notation is a convenient way to represent the elements of a symmetric group.

      • Disjoint cycle notation is unique

        Disjoint cycle notation provides a canonical way to express elements of the symmetric group.

      • Cycle type of a permutation

        The cycle type is an invariant of a permutation in the symmetric group.

    • Disjoint cycles commute in symmetric groups

      In cycle notation, if two cycles are disjoint, then they commute.

    • Conjugacy class is cycle type in symmetric group

      There is a neat characterisation of the conjugacy classes in the symmetric group on a finite set.

    • Conjugacy classes of the symmetric group on five elements

      The symmetric group on five elements is a group of just the right size to make a good example of a table of conjugacy classes.

    • Transposition (as an element of a symmetric group)

      A transposition is the simplest kind of permutation: it swaps two elements.

    • Every member of a symmetric group on finitely many elements is a product of transpositions

      This fact can often simplify arguments about permutations: if we can show that something holds for transpositions, and that it holds for products, then it holds for everything.

    • The sign of a permutation is well-defined

      This result is what allows the alternating group to exist.

    • Sign homomorphism (from the symmetric group)

      The sign homomorphism is how we extract the alternating group from the symmetric group.

  • Group isomorphism

    “Isomorphism” is the proper notion of “sameness” or “equality” among groups.

  • Order of a group element
  • Dihedral group

    The dihedral groups are natural examples of groups, arising from the symmetries of regular polygons.

    • Dihedral groups are non-abelian

      The group of symmetries of the triangle and all larger regular polyhedra are not abelian.

  • Group conjugate

    Conjugation lets us perform permutations “from the point of view of” another permutation.

  • Normal subgroup

    Normal subgroups are subgroups which are in some sense “the same from all points of view”.

    • Subgroup is normal if and only if it is the kernel of a homomorphism

      The “correct way” to think about normal subgroups is as kernels of homomorphisms.

    • Quotient by subgroup is well defined if and only if subgroup is normal
    • Subgroup is normal if and only if it is a union of conjugacy classes

      A useful way to think about normal subgroups, which meshes with their “closed under conjugation” interpretation.

  • Alternating group

    The alternating group is the only normal subgroup of the symmetric group (on five or more generators).

    • The collection of even-signed permutations is a group

      This proves the well-definedness of one particular definition of the alternating group.

    • Alternating group is generated by its three-cycles

      A useful result which lets us prove things about the alternating group more easily.

    • The alternating groups on more than four letters are simple

      The alternating groups are the most accessible examples of simple groups, and this fact also tells us that the symmetric groups are “complicated” in some sense.

    • The alternating group on five elements is simple

      The smallest (nontrivial) simple group is the alternating group on five elements.

      • The alternating group on five elements is simple: Simpler proof

        A proof which avoids some of the heavy machinery of the main proof.

    • Conjugacy classes of the alternating group on five elements

      \(A_5\) has easily-characterised conjugacy classes, based on a rather surprising theorem about when conjugacy classes in the symmetric group split.

      • Conjugacy classes of the alternating group on five elements: Simpler proof

        A listing of the conjugacy classes of the alternating group on five letters, without using heavy theory.

    • Splitting conjugacy classes in alternating group

      The conjugacy classes in the alternating group are usually the same as those in the symmetric group; there is a surprisingly simple condition for when this does not hold.

  • Group coset
    • Left cosets partition the parent group

      In a group, every element has a unique coset in which it lies, allowing us to compress some of the information about the group.

    • Left cosets are all in bijection

      The left cosets of a subgroup in a parent group are all the same size.

  • Simple group

    The simple groups form the “building blocks” of group theory, analogously to the prime numbers in number theory.

  • Prime order groups are cyclic

    This is the first step on the road to classifying the finite groups.

  • Lagrange theorem on subgroup size

    Lagrange’s Theorem is an important restriction on the sizes of subgroups of a finite group.

    • Lagrange theorem on subgroup size: Intuitive version

      Lagrange’s theorem strongly restricts the size a subgroup of a group can be.

  • Cauchy's theorem on subgroup existence

    Cauchy’s theorem is a useful condition for the existence of cyclic subgroups of finite groups.

    • Cauchy's theorem on subgroup existence: intuitive version
  • Group orbit
  • Cyclic Group Intro (Math 0)

    A finite cyclic group is a little bit like a clock.

  • Subgroup

    A group that lives inside a bigger group.

  • Group presentation

    Presentations are a fairly compact way of expressing groups.

  • Every group is a quotient of a free group
  • Free group

    The free group is “the purest way to make a group containing a given set”.

    • Free groups are torsion-free

      An easy way to determine that many groups are not free: free groups contain no non-identity elements of finite order.

    • Formal definition of the free group

      Van der Waerden’s trick lets us define the free groups in a slick but mostly incomprehensible way.

    • Free group universal property
• Group theory: Examples

  What does thinking in terms of group theory actually look like? And what does it buy you?

• Group action

  “Groups, as men, will be known by their actions.”

  • Group action induces homomorphism to the symmetric group

    We can view group actions as “bundles of homomorphisms” which behave in a certain way.

  • Orbit-stabiliser theorem

    The Orbit-Stabiliser theorem tells us a lot about how a group acts on a given element.

    • Orbit-Stabiliser theorem: External Resources

      External resources on the Orbit-Stabiliser theorem.

  • Stabiliser is a subgroup

    Given a group acting on a set, each element of the set induces a subgroup of the group.

  • Group orbits partition

    When a group acts on a set, the set falls naturally into distinct pieces, where the group action only permutes elements within any given piece, not between them.

  • Stabiliser (of a group action)

    If a group acts on a set, it is useful to consider which elements of the group don’t move a certain element of the set.

The study of groups, fields, vector spaces, arithmetics, algebras, and more.

• Algebraic structure
  • Group

    The algebraic structure that captures symmetry, relationships between transformations, and part of what multiplication and addition have in common.

    • Order of a group
    • Abelian group

      A group where the operation commutes. Named after Niels Henrik Abel.

    • Group: Examples

      Why would anyone have invented groups, anyway? What were the historically motivating examples, and what examples are important today?

    • Group: Exercises

      Test your understanding of the definition of a group with these exercises.

    • Group homomorphism

      A group homomorphism is a “function between groups” that “respects the group structure”.

      • Kernel of group homomorphism
      • Image of the identity under a group homomorphism is the identity

        All group homomorphisms preserve the identity.

      • Under a group homomorphism, the image of the inverse is the inverse of the image

        The operations of “taking inverses” and “applying a group homomorphism” commute: it does not matter in which order we do them.

      • The image of a group under a homomorphism is a subgroup of the codomain

        Group homomorphisms take groups to groups, but it is additionally guaranteed that the elements they hit form a group.

      • The composition of two group homomorphisms is a homomorphism

        The collection of group homomorphisms is closed under composition.

    • Cyclic group

      Cyclic groups form one of the most simple classes of groups.

      • Cyclic Group Intro (Math 0)

        A finite cyclic group is a little bit like a clock.

    • Symmetric group

      The symmetric groups form the fundamental link between group theory and the notion of symmetry.

      • Cayley's Theorem on symmetric groups

        The “fundamental theorem of symmetry”, forging the connection between symmetry and group theory.

      • Cycle notation in symmetric groups

        Cycle notation is a convenient way to represent the elements of a symmetric group.

        • Disjoint cycle notation is unique

          Disjoint cycle notation provides a canonical way to express elements of the symmetric group.

        • Cycle type of a permutation

          The cycle type is an invariant of a permutation in the symmetric group.

      • Disjoint cycles commute in symmetric groups

        In cycle notation, if two cycles are disjoint, then they commute.

      • Conjugacy class is cycle type in symmetric group

        There is a neat characterisation of the conjugacy classes in the symmetric group on a finite set.

      • Conjugacy classes of the symmetric group on five elements

        The symmetric group on five elements is a group of just the right size to make a good example of a table of conjugacy classes.

      • Transposition (as an element of a symmetric group)

        A transposition is the simplest kind of permutation: it swaps two elements.

      • Every member of a symmetric group on finitely many elements is a product of transpositions

        This fact can often simplify arguments about permutations: if we can show that something holds for transpositions, and that it holds for products, then it holds for everything.

      • The sign of a permutation is well-defined

        This result is what allows the alternating group to exist.

      • Sign homomorphism (from the symmetric group)

        The sign homomorphism is how we extract the alternating group from the symmetric group.

    • Group isomorphism

      “Isomorphism” is the proper notion of “sameness” or “equality” among groups.

    • Order of a group element
    • Dihedral group

      The dihedral groups are natural examples of groups, arising from the symmetries of regular polygons.

      • Dihedral groups are non-abelian

        The group of symmetries of the triangle and all larger regular polyhedra are not abelian.

    • Group conjugate

      Conjugation lets us perform permutations “from the point of view of” another permutation.

    • Normal subgroup

      Normal subgroups are subgroups which are in some sense “the same from all points of view”.

      • Subgroup is normal if and only if it is the kernel of a homomorphism

        The “correct way” to think about normal subgroups is as kernels of homomorphisms.

      • Quotient by subgroup is well defined if and only if subgroup is normal
      • Subgroup is normal if and only if it is a union of conjugacy classes

        A useful way to think about normal subgroups, which meshes with their “closed under conjugation” interpretation.

    • Alternating group

      The alternating group is the only normal subgroup of the symmetric group (on five or more generators).

      • The collection of even-signed permutations is a group

        This proves the well-definedness of one particular definition of the alternating group.

      • Alternating group is generated by its three-cycles

        A useful result which lets us prove things about the alternating group more easily.

      • The alternating groups on more than four letters are simple

        The alternating groups are the most accessible examples of simple groups, and this fact also tells us that the symmetric groups are “complicated” in some sense.

      • The alternating group on five elements is simple

        The smallest (nontrivial) simple group is the alternating group on five elements.

        • The alternating group on five elements is simple: Simpler proof

          A proof which avoids some of the heavy machinery of the main proof.

      • Conjugacy classes of the alternating group on five elements

        \(A_5\) has easily-characterised conjugacy classes, based on a rather surprising theorem about when conjugacy classes in the symmetric group split.

        • Conjugacy classes of the alternating group on five elements: Simpler proof

          A listing of the conjugacy classes of the alternating group on five letters, without using heavy theory.

      • Splitting conjugacy classes in alternating group

        The conjugacy classes in the alternating group are usually the same as those in the symmetric group; there is a surprisingly simple condition for when this does not hold.

    • Group coset
      • Left cosets partition the parent group

        In a group, every element has a unique coset in which it lies, allowing us to compress some of the information about the group.

      • Left cosets are all in bijection

        The left cosets of a subgroup in a parent group are all the same size.

    • Simple group

      The simple groups form the “building blocks” of group theory, analogously to the prime numbers in number theory.

    • Prime order groups are cyclic

      This is the first step on the road to classifying the finite groups.

    • Lagrange theorem on subgroup size

      Lagrange’s Theorem is an important restriction on the sizes of subgroups of a finite group.

      • Lagrange theorem on subgroup size: Intuitive version

        Lagrange’s theorem strongly restricts the size a subgroup of a group can be.

    • Cauchy's theorem on subgroup existence

      Cauchy’s theorem is a useful condition for the existence of cyclic subgroups of finite groups.

      • Cauchy's theorem on subgroup existence: intuitive version
    • Group orbit
    • Cyclic Group Intro (Math 0)

      A finite cyclic group is a little bit like a clock.

    • Subgroup

      A group that lives inside a bigger group.

    • Group presentation

      Presentations are a fairly compact way of expressing groups.

    • Every group is a quotient of a free group
    • Free group

      The free group is “the purest way to make a group containing a given set”.

      • Free groups are torsion-free

        An easy way to determine that many groups are not free: free groups contain no non-identity elements of finite order.

      • Formal definition of the free group

        Van der Waerden’s trick lets us define the free groups in a slick but mostly incomprehensible way.

      • Free group universal property
  • Ring
    • Ordered ring

      A ring with a total ordering compatible with its ring structure.

    • Irreducible element (ring theory)

      This is the appropriate abstraction of the concept of “prime number” to general rings.

    • Prime element of a ring

      Despite the name, “prime” in ring theory refers not to elements which are “multiplicatively irreducible” but to those such that if they divide a product then they divide some term of the product.

    • Integral domain

      An integral domain is a ring where the only way to express zero as a product is by having zero as one of the terms.

    • In a principal ideal domain, "prime" and "irreducible" are the same

      Principal ideal domains have a very useful property that we don’t need to distinguish between the informal notion of “prime” (i.e. “irreducible”) and the formal notion.

    • Unit (ring theory)

      A unit in a ring is just an element with a multiplicative inverse.

    • Principal ideal domain

      A principal ideal domain is a kind of ring, in which all ideals have a certain nice form.

    • Kernel of ring homomorphism

      The kernel of a ring homomorphism is the collection of things which that homomorphism sends to 0.

    • Ideals are the same thing as kernels of ring homomorphisms
    • Euclidean domains are principal ideal domains

      A Euclidean domain is one where we may somehow perform the division algorithm; this gives us access to some of the nicest properties of the integers.

    • Unique factorisation domain

      This is the correct way to abstract from the integers the fact that every integer can be written uniquely as a product of prime numbers.

  • Abelian group

    A group where the operation commutes. Named after Niels Henrik Abel.

  • Monoid
  • Algebraic structure tree

    When is a monoid a semilattice? What’s the difference between a semigroup and a groupoid? Find out here!

• Underlying set

• Associativity: Intuition
• Generalized associative law
• Associativity: Examples
• Associativity vs commutativity

• Commutativity: Intuition
• Commutativity: Examples
• Associativity vs commutativity

• Operator
• Arity (of a function)
• Domain (of a function)
• concat (function)
• Binary function
• Codomain (of a function)
  • Codomain vs image
• Image (of a function)
  • Codomain vs image
• Range (of a function)
• Codomain vs image
• Function: Physical metaphor
• Ceiling
• Ackermann function

  The slowest-growing fast-growing function.

• Bijective function

  A bijective function is a function with an inverse.

  • Bijective Function: Intro (Math 0)

    Two boxes are bijective if they contain the same number of items.

• Injective function
• Surjective function

  A surjective function is one which “hits everything in the codomain”.

• Inverse function

  The inverse of a function returns an input of the original function when fed the original’s corresponding output.

• Exponential

  Any function that constantly gets larger as a proportion of itself.

• Currying

  Transforms a function of many arguments into a function into a function of a single argument

• Convex function

  A function that only curves upward

• Partial function

  A partial function is one which “might not be defined everywhere one might expect it to be”.

An unordered collection of distinct objects.

• Set builder notation
• Cardinality

  The “size” of a set, or the “number of elements” that it has.

• Convex set

  A set that contains all line segments between points in the set

• Operations in Set theory
  • Cartesian product
  • Absolute Complement
  • Union

    The union of two sets is the set of elements which are in one or the other, or both

  • Intersection

    The intersection of two sets is the set of elements they have in common

  • Relative complement
• Cantor-Schröder-Bernstein theorem

  This theorem tells us that comparing sizes of sets makes sense: if one set is smaller than another, and the other is smaller than the one, then they are the same size.

• Disjoint union of sets

  One of the most basic ways we have of joining two sets together.

  • Universal property of the disjoint union

    Just as the empty set may be described by a universal property, so too may the disjoint union of sets.

• Empty set

  The empty set does what it says on the tin: it is the set which is empty.

  • Empty set
• Set product

  A fundamental way of combining sets is to take their product, making a set that contains all tuples of elements from the originals.

• Finite set

  A finite set is one which is not infinite. Some of these are the least complicated sets.

  • Category of finite sets

    The category of finite sets is exactly what it claims to be. It’s a useful training ground for some of the ideas of category theory.

• Extensionality Axiom

  If two sets have exactly the same members, then they are equal

• Logarithm: Examples
• Logarithm: Exercises
• Introductory guide to logarithms
• Logarithmic identities
• Logarithms invert exponentials
• Logarithm tutorial overview
• What is a logarithm?
• Log as generalized length

  To estimate the log (base 10) of a number, count how many digits it has.

• Logarithm base 1

  There is no log base 1.

• Exchange rates between digits

  In terms of data storage, if a coin is worth \(1, a digit wheel is worth more than \)3.32, but less than $3.33. Why?

• Why is log like length?
• Fractional digits
• Log as the change in the cost of communicating
• The characteristic of the logarithm
• Properties of the logarithm
• Log base infinity

  There is no log base infinity, but if there were, it would send everything to zero

• There is only one logarithm

  All logarithm functions are the same, up to a multiplicative constant.

• The log lattice
• Life in logspace
• The End (of the basic log tutorial)
• Why is the decimal expansion of log2(3) infinite?

  Because 2 and 3 are relatively prime.

• Equivalence relation

  A relation that allows you to partition a set into equivalence classes.

• Order relation

  A way of determining which elements of a set come “before” or “after” other elements.

• Transitive relation

  If a is related to b and b is related to c, then a is related to c.

• Reflexive relation
• Antisymmetric relation

  A binary relation where no two distinct elements are related in both directions

• Bit (of data)
  • Bit (of data): Examples
  • Fractional bits
    • Fractional bits: Expected cost interpretation
  • How many bits to a trit?
    • Encoding trits with GalCom bits
• Fractional bits
  • Fractional bits: Expected cost interpretation
• GalCom
  • GalCom: Rules
  • Encoding trits with GalCom bits
• n-message
• Decit

  Decimal digit

• How many bits to a trit?
  • Encoding trits with GalCom bits
• Trit

  Trinary digit

• Intradependent encodings can be compressed
• Intradependent encoding
• Dependent messages can be encoded cheaply
• Information
  • Shannon
• Data capacity
• Compressing multiple messages
• Communication: magician example
• Algorithmic complexity

  When you compress the information, what you are left with determines the complexity.

  • Most complex things are not very compressible

    We can’t prove it’s impossible, but it would be extremely surprising to discover a 500-state Turing machine that output the exact text of “Romeo and Juliet”.

Modern foundations for formal mathematics.

• Programming in Dependent Type Theory

  Working with simple types in Lean

• Eigenvalues and eigenvectors

  We applied this linear transformation to one of its eigenvectors; you won’t believe what happened next!

• Vector space
  • Subspace
  • Sum of vector spaces
  • Direct sum of vector spaces
• Subspace

The study of real numbers and real-valued functions.

Find out what the notation “f : X → Y” means that everyone keeps using.

Decimal digit

Trinary digit

• Bit (of data)
  • Bit (of data): Examples
  • Fractional bits
    • Fractional bits: Expected cost interpretation
  • How many bits to a trit?
    • Encoding trits with GalCom bits
• Bit (abstract)
• Shannon

The numbers we use to count: 0, 1, 2, 3, …

• Graham's number

  A fairly large number, as numbers go.

• A googolplex

  A moderately large number, as large numbers go.

• A googol

  A pretty small large number.

• Prime number

  The prime numbers are the “building blocks” of the counting numbers.

  • Proof that there are infinitely many primes

    Suppose there were finitely many primes. Then consider the product of all the primes plus 1…

The diagonal function and the halting problem

If and only if…

How things change

• Integers: Intro (Math 0)

  The integers are the whole numbers extended into the negatives.

• Pi is irrational

  The number pi is famously not rational, in spite of joking attempts at legislation to fix its value at 3 or ²²⁄₇.

Study of the computational resources needed to compute something

• Complexity theory: Complexity zoo

  Pass and see the exotic beasts coming from the lands of afar!

• P vs NP

  Is creativity purely mechanical?

  • P vs NP: Arguments against P=NP

    Why we believe P and NP are different

• Decision problem

  Formalization of general problems

• P (Polynomial Time Complexity Class)

  P is the class of problems which can be solved by algorithms whose run time is bounded by a polynomial.

Trying to assign value to an uncertain state? The weighted average of outcomes is probably the tool you need.

• Real number (as Cauchy sequence)

  There are several ways to construct real numbers; this is the most natural way to use them in computations.

  • The reals (constructed as classes of Cauchy sequences of rationals) form a field

    The reals are an archetypal example of a field, but if we are to construct them from simpler objects, we need to show that our construction does indeed have the right properties.

• Real number (as Dedekind cut)

  A way to construct the real numbers that follows the intuition of filling in the gaps.

  • The reals (constructed as Dedekind cuts) form a field

    The reals are an archetypal example of a field, but if we are to construct them from simpler objects, we need to show that our construction does indeed have the right properties.

• Real numbers are uncountable

  The real numbers are uncountable.

Is creativity purely mechanical?

• P vs NP: Arguments against P=NP

  Why we believe P and NP are different

In a group, the elements can be partitioned naturally into certain classes.

A thesis about computational models

• Strong Church Turing thesis

  A strengthening of the Church Turing thesis

• Church-Turing thesis: Evidence for the Church-Turing thesis

  Why do we believe in CT thesis?

How mathematical objects are related to others in the same category.

• Category (mathematics)

  A description of how a collection of mathematical objects are related to one another.

• Equaliser (category theory)
• Product (Category Theory)

  How a product is characterized rather than how it’s constructed

  • Universal property of the product

    The product can be defined in a very general way, applicable to the natural numbers, to sets, to algebraic structures, and so on.

    • Product is unique up to isomorphism

      If something satisfies the universal property of the product, then it is uniquely specified by that property, up to isomorphism.

• Object identity via interactions

  If we think of objects as opaque “black boxes”, how can we tell whether two objects are different? By looking at how they interact with other objects!

• Universal property

  A universal property is a way of defining an object based purely on how it interacts with other objects, rather than by any internal property of the object itself.

  • Universal property of the empty set

    The empty set can be characterised by how it interacts with other sets, rather than by any explicit property of the empty set itself.

    • The empty set is the only set which satisfies the universal property of the empty set

      This theorem tells us that the universal property provides a sensible way to define the empty set uniquely.

  • Universal property of the product

    The product can be defined in a very general way, applicable to the natural numbers, to sets, to algebraic structures, and so on.

    • Product is unique up to isomorphism

      If something satisfies the universal property of the product, then it is uniquely specified by that property, up to isomorphism.

  • Universal property of the disjoint union

    Just as the empty set may be described by a universal property, so too may the disjoint union of sets.

• Category of finite sets

  The category of finite sets is exactly what it claims to be. It’s a useful training ground for some of the ideas of category theory.

A morphism between two objects which describes how they are “essentially equivalent” for the purposes of the theory under consideration.

• Group isomorphism

  “Isomorphism” is the proper notion of “sameness” or “equality” among groups.

• Isomorphism: Intro (Math 0)

  Things which are basically the same, except for some stuff you don’t care about.

• Up to isomorphism

  A phrase mathematicians use when saying “we only care about the structure of an object, not about specific implementation details of the object”.

Want to see programming analogies and applications in your math explanations? Mark this as known.

The winning architecture for numerals

• 0.999...=1

  No, it’s not “infinitesimally far” from 1 or anything like that. 0.999… and 1 are literally the same number.

A representation of a value as a fraction or multiple of another value.

The rational numbers are “fractions”.

• The rationals form a field
• Rational numbers: Intro (Math 0)
• Arithmetic of rational numbers (Math 0)

  How do we combine rational numbers together?

  • Addition of rational numbers (Math 0)

    The simplest operation on rational numbers is addition.

    • Addition of rational numbers exercises

      Test and cement your understanding of how we add rational numbers!

  • Subtraction of rational numbers (Math 0)

    In which we meet anti-apples.

  • Division of rational numbers (Math 0)

    “Division” is the idea of “dividing something up among some people so that we can give equal amounts to each person”.

  • Rational arithmetic all works together

    The various operations of arithmetic all play nicely together in a certain specific way.

  • Order of rational operations (Math 0)

    Our shorthand for all the operations on rationals is very useful, but full of brackets; this is how to get rid of some of the brackets.

• Field structure of rational numbers

  In which we describe the field structure on the rationals.

  • Arithmetic of rational numbers (Math 0)

    How do we combine rational numbers together?

    • Addition of rational numbers (Math 0)

      The simplest operation on rational numbers is addition.

      • Addition of rational numbers exercises

        Test and cement your understanding of how we add rational numbers!

    • Subtraction of rational numbers (Math 0)

      In which we meet anti-apples.

    • Division of rational numbers (Math 0)

      “Division” is the idea of “dividing something up among some people so that we can give equal amounts to each person”.

    • Rational arithmetic all works together

      The various operations of arithmetic all play nicely together in a certain specific way.

    • Order of rational operations (Math 0)

      Our shorthand for all the operations on rationals is very useful, but full of brackets; this is how to get rid of some of the brackets.

Transforms a function of many arguments into a function into a function of a single argument

Although there are “lots and lots” of rational numbers, there are still only countably many of them.

The logic of boxes and bots.

• Standard provability predicate

  Encoding provability as a statement of arithmetic

• Normal system of provability logic
• Provability logic

  Learn how to reason about provability!

  • Fixed point theorem of provability logic

    Deal with those pesky self-referential sentences!

  • Solovay's theorems of arithmetical adequacy for GL

    Using GL to reason about PA, and viceversa

• Kripke model

  The semantics of modal logic

• Modalized modal sentence
• Modal combat

  Modal combat

An introduction to number sets for people who have no idea what a number set is.

Conventions used for disambiguating infix notation.

• Order of rational operations (Math 0)

  Our shorthand for all the operations on rationals is very useful, but full of brackets; this is how to get rid of some of the brackets.

Real numbers that are not rational numbers

• Pi is irrational

  The number pi is famously not rational, in spite of joking attempts at legislation to fix its value at 3 or ²²⁄₇.

• The square root of 2 is irrational

  The number whose square is 2 can’t be written is a quotient of natural numbers

A monotonic function from the real numbers to the open unit interval.

Löb’s theorem

• Proof of Löb's theorem

  Proving that I am Santa Claus

• Löb's theorem and computer programs
• Gödel II and Löb's theorem

In other words, no power of a rational number that is not an integer is ever an integer.

A way to write down numbers using powers of two.

A value in logic that evaluates to either “true” or “false”.

Constructing self-referential sentences

• Quine

  A computer program that prints (or does other computations to) its own source code, using indirect self-reference.

The theorem that destroyed Hilbert’s program

• Proof of Gödel's first incompleteness theorem

“Multiplication” is the idea of “now do the same as you just did, but instead of doing it to one apple, do it to some other number”.

The number of ways you can order things. (Alternately subtitled: Is that exclamation point a factorial, or are you just excited to see me?)

• Factorial

“Freely reduced” captures the idea of “no cancellation” in a free group.

Why \(Y^X\) is good notation for the space of maps from \(X\) to \(Y\)

A very basic but vitally important property of the prime numbers is that they “can’t be split between factors”: if a prime divides a product then it must divide one of the individual factors.

The greatest common divisor of two natural numbers is… the largest number which is a divisor of both. The clue is in the name, really.

• Bézout's theorem

  Bézout’s theorem is an important link between highest common factors and the integer solutions of a certain equation.

A metric is a function that defines a distance between elements in a set and follows some basic rules.

Addition as traveling around a circle, instead of along a line.

A Turing Machine is a simple mathematical model of computation that is powerful enough to describe any computation a computer can do.

• Rice's Theorem

  Rice’s Theorem tells us that if we want to determine pretty much anything about the behaviour of an arbitrary computer program, we can’t in general do better than just running it.

  • Rice's theorem and the Halting problem
  • Proof of Rice's theorem

    A standalone proof of Rice’s theorem, including one surprising lemma.

  • Rice's Theorem: Intro (Math 1)

    You can’t write a program that looks at another programs source code, and tells you whether it computes the Fibonacci sequence.

• Turing machine: External resources

How do we know if one lot of apples is “more apples” than another lot?

The FTA tells us that natural numbers can be decomposed uniquely into prime factors; it is the basis of almost all number theory.

A mathematical object is “well-defined” if we have given it a completely unambiguous definition.

An ordered ring with division.

• Mapsto notation

  There’s an arrow called \mapsto in LaTeX. What does it mean?

• In notation

  There’s a weird E-looking symbol called \in in LaTeX. What does it mean?

• Bag
• List
• Number

  An abstract object that expresses quantity or value of some sort.

  • Complex number
  • Whole number

    A term that can refer to three different sets of “numbers that are not fractions”.

  • Transcendental number

    A transcendental number is one which is not the root of any integer-coefficient polynomial.

• Identity element

  An element in a set with a binary operation that leaves every element unchanged when used as the other operand.

• Proof by contradiction

  Discover what ‘reductio ad absurdum’ means!

• Mathematical induction

  Proving a statement about all positive integers by knocking them down like dominoes.

A category-theoretic generalization of the notion of element of a set.

Logic, provability, Löb, Gödel and more!

• Axiom of Choice

  The most controversial axiom of the 20th century.

  • Axiom of Choice: Guide

    Learn about the most controversial axiom of the 20th century.

  • Axiom of Choice: Introduction

    What is the axiom of choice and why do I care?

  • Axiom of Choice: Definition (Formal)

    Mathematically speaking, what does the Axiom of Choice say?

    • Axiom of Choice Definition (Intuitive)

      Definition of the Axiom of Choice, without using heavy mathematical notation.

  • Axiom of Choice: History and Controversy

    Really? The most controversial axiom of the 20th century? Yes.

  • Axiom of Choice Definition (Intuitive)

    Definition of the Axiom of Choice, without using heavy mathematical notation.

Some infinities are bigger than others. Countable infinities are the smallest infinities.

Some Arbital pages we think are great!

What does it mean to add things together forever?

A minimal, inefficient, and hard-to-read, but still interesting and useful, programming language.

What is the opposite of multiplying a number by itself?