Arbital на русском

Переведено:

• Индукция Соломонова
  
  Как просто и сверхразумно предсказывать последовательности данных, имея неограниченную вычислительную мощность.
• Теория вероятностей
  
  Логика науки; когерентные отношения численных степеней уверенности.
• Интерпретации «вероятности»
  
  Что _означает_, что честная монета имеет 50% вероятность выпасть решкой?
• Ожидаемое значение
  
  Пытаетесь присвоить значение неопределенному состоянию? Возможно, взвешенное среднее от исходов - это то, что вы ищете.
• Тезис Чёрча-Тьюринга
  
  Тезис о моделях вычислений

Не переведено:

• Solomonoff induction: Intro Dialogue (Math 2)
  
  An introduction to Solomonoff induction for the unfamiliar reader who isn't bad at math
• 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 4⁄5 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.
• 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 5⁄32 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?
• 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?
• Ability to read algebra
  
  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?
• Arithmetical hierarchy
  
  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
  
• Ability to 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?
• Math 0
  
  Are you not actively bad at math, nor traumatized about math?
• Math 1
  
  Is math sometimes fun for you, and are you not anxious if you see a math puzzle you don’t know how to solve?
• Math 2
  
  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!
• Math 3
  
  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!
• Ability to read calculus
  
  Can you take integral signs and differentiations in stride?
• Uncountability
  
  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.
• Gödel encoding and self-reference
  
  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.
• Math playpen
  
  Playpen page for Math domain
• Order theory
  
  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.
• Group theory
  
  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.
• Closure
  
• Abstract algebra
  
  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
  
• Associative operation
  
• Associativity: Intuition
  
• Generalized associative law
  
• Associativity: Examples
  
• Associativity vs commutativity
  
• Commutative operation
  
• Commutativity: Intuition
  
• Commutativity: Examples
  
• Associativity vs commutativity
  
• String (of text)
  
• Function
  
• 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”.
• Set
  
  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
  
• 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.
• Relation
  
• 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
• Information theory
  
• 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”.
• Type theory
  
  Modern foundations for formal mathematics.
• Programming in Dependent Type Theory
  
  Working with simple types in Lean
• Linear algebra
  
• 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
  
• Real analysis
  
  The study of real numbers and real-valued functions.
• Colon-to notation
  
  Find out what the notation “f : X → Y” means that everyone keeps using.
• Decit
  
  Decimal digit
• Trit
  
  Trinary digit
• Bit
  
• 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
  
• Bit (abstract)
  
• Digit wheel
  
• Natural number
  
  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…
• Uncomputability
  
  The diagonal function and the halting problem
• Iff
  
  If and only if…
• Derivative
  
  How things change
• Integer
  
• Integers: Intro (Math 0)
  
  The integers are the whole numbers extended into the negatives.
• Pi
  
• Pi is irrational
  
  The number pi is famously not rational, in spite of joking attempts at legislation to fix its value at 3 or 22⁄7.
• Complexity theory
  
  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.
• Real number
  
• 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.
• P vs NP
  
  Is creativity purely mechanical?
• P vs NP: Arguments against P=NP
  
  Why we believe P and NP are different
• Conjugacy class
  
  In a group, the elements can be partitioned naturally into certain classes.
• 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?
• Category theory
  
  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.
• Morphism
  
• Isomorphism
  
  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”.
• Computer Programming Familiarity
  
  Want to see programming analogies and applications in your math explanations? Mark this as known.
• n-digit
  
• Emulating digits
  
• Decimal notation
  
  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.
• Quotient group
  
• Proportion
  
  A representation of a value as a fraction or multiple of another value.
• Rational number
  
  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.
• Currying
  
  Transforms a function of many arguments into a function into a function of a single argument
• The set of rational numbers is countable
  
  Although there are “lots and lots” of rational numbers, there are still only countably many of them.
• Elementary Algebra
  
• Modal logic
  
  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
• Intro to Number Sets
  
  An introduction to number sets for people who have no idea what a number set is.
• Order of operations
  
  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.
• Irrational number
  
  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 22⁄7.
• The square root of 2 is irrational
  
  The number whose square is 2 can’t be written is a quotient of natural numbers
• Logistic function
  
  A monotonic function from the real numbers to the open unit interval.
• Löb's theorem
  
  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
  
• The n-th root of m is either an integer or irrational
  
  In other words, no power of a rational number that is not an integer is ever an integer.
• Binary notation
  
  A way to write down numbers using powers of two.
• Boolean
  
  A value in logic that evaluates to either “true” or “false”.
• Diagonal lemma
  
  Constructing self-referential sentences
• Quine
  
  A computer program that prints (or does other computations to) its own source code, using indirect self-reference.
• Gödel's first incompleteness theorem
  
  The theorem that destroyed Hilbert’s program
• Proof of Gödel's first incompleteness theorem
  
• Multiplication of rational numbers (Math 0)
  
  “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”.
• Factorial
  
  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
  
• Provability predicate
  
• Freely reduced word
  
  “Freely reduced” captures the idea of “no cancellation” in a free group.
• Exponential notation for function spaces
  
  Why Y^X is good notation for the space of maps from X to Y
• Consistency
  
• Euclid's Lemma on prime numbers
  
  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.
• Greatest common divisor
  
  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.
• Metric
  
  A metric is a function that defines a distance between elements in a set and follows some basic rules.
• Modular arithmetic
  
  Addition as traveling around a circle, instead of along a line.
• Turing machine
  
  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
  
• Ordering of rational numbers (Math 0)
  
  How do we know if one lot of apples is “more apples” than another lot?
• Fundamental Theorem of Arithmetic
  
  The FTA tells us that natural numbers can be decomposed uniquely into prime factors; it is the basis of almost all number theory.
• Well-defined
  
  A mathematical object is “well-defined” if we have given it a completely unambiguous definition.
• Ordered field
  
  An ordered ring with division.
• LaTeX
  
• 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?
• Mathematical object
  
• 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.
• Element
  
• Identity element
  
  An element in a set with a binary operation that leaves every element unchanged when used as the other operand.
• Proof technique
  
• Proof by contradiction
  
  Discover what ‘reductio ad absurdum’ means!
• Mathematical induction
  
  Proving a statement about all positive integers by knocking them down like dominoes.
• Generalized element
  
  A category-theoretic generalization of the notion of element of a set.
• Examination through isomorphism
  
• Least common multiple
  
• An introductory guide to modern logic
  
  Logic, provability, Löb, Gödel and more!
• Axiom
  
• 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.
• Countability
  
  Some infinities are bigger than others. Countable infinities are the smallest infinities.
• Featured math content
  
  Some Arbital pages we think are great!
• Primer on Infinite Series
  
  What does it mean to add things together forever?
• Lambda calculus
  
  A minimal, inefficient, and hard-to-read, but still interesting and useful, programming language.
• Square root
  
  What is the opposite of multiplying a number by itself?