Axiom of choice

In mathematics, the axiom of choice is a special rule used in set theory. It says that if you have many groups that are not empty, you can choose one item from each group to make a new group. This works even if there are endless groups. The idea was first written down in 1904 by Ernst Zermelo to help prove another important math idea called the well-ordering theorem.

Sometimes you don’t need this special rule. For example, if you have groups of whole numbers, you can always choose the smallest number from each group. But for some collections, like all the non-empty groups of real numbers, there is no simple way to choose one item from each group. In these cases, the axiom of choice is needed.

At first, some mathematicians were not sure about this rule. But now, most use it without question because many useful math results, like Tychonoff's theorem, need it to be proven. Some areas of math study rules that don’t work with the axiom of choice, but many still use it in their work.

Statement

A choice function is a rule that picks one item from each set in a group of sets that are not empty. It makes sure that for any set in the group, one item can be chosen.

This idea helps us understand the axiom of choice. The axiom says that no matter how many sets we have, even if there are infinitely many, we can always pick one item from each set. This is important in math because it lets us build new sets from existing ones.

The axiom can also be described in different ways that all mean the same thing. One way looks at groups of sets and makes sure we can pick one item from each group. Another way looks at special collections of sets called power sets. All these ideas help mathematicians work with big collections of sets.

Main article: Zermelo–Fraenkel set theory

Usage

Before the late 1800s, mathematicians used an idea without explaining it clearly. For example, if they knew a group of sets all had at least one item, they might say, "pick one item from each set to make a new rule." It turns out that proving this new rule exists is hard without the axiom of choice, but people didn’t realize this until Zermelo came along.

Examples

Cases where the axiom of choice is not needed

For a small group of non-empty sets, we can choose one item from each set without needing a special rule. This works because we can only make a limited number of choices at once.

When there is a clear way to pick one item, like always choosing the smallest number from a group of numbers, we also don’t need this special rule.

Real numbers

We need this special rule when dealing with groups of real numbers. For example, some groups of numbers don’t have a smallest number, so we can’t use the “pick the smallest” method. In these cases, the rule helps us choose one number from each group.

Constructing a non-measurable set

Main article: Non-measurable set § Examples

Imagine a circle and many ways to turn it. By using this special rule, we can pick one point from each turned version of the circle. This creates a special group of points that can’t be measured in certain ways. This idea also helps show surprising results in geometry.

Criticism and acceptance

Some people worry that using the axiom of choice in math can lead to results that are hard to understand. For example, it can show that certain special arrangements of numbers exist, but it doesn’t tell us how to build them. This can be a problem when we want clear ways to solve things.

One famous example is the Banach–Tarski paradox, which shows that, using the axiom of choice, a solid ball can be split into pieces and then put back together to make two balls of the same size. Even though these results sound strange, most mathematicians still use the axiom of choice because it helps them prove many important ideas in math.

In constructive mathematics

In normal math, the axiom of choice helps prove that something exists without showing how to find it. But in a special kind of math called constructive mathematics, this rule does not work because it uses different logic.

In another type of math called type theory, the axiom of choice can be used or proven true, unlike in constructive set theory. Some smaller versions of the choice rule, like the axiom of countable choice, are used in constructive math without causing problems.

Independence

The axiom of choice is a rule in math that helps us pick one item from each group in a collection, even if the collection is very large. We can show that this rule is not part of the basic rules of set theory.

Mathematicians have found ways to build different versions of math where the axiom of choice is true and where it is false. This shows that we can choose whether to use this rule based on what we need for our proofs. Using the axiom of choice can make some proofs easier and help us understand big collections of objects better.

Stronger axioms

Some ideas in math are even stronger than the axiom of choice. For example, the axiom of constructibility and the generalized continuum hypothesis both include the axiom of choice but go further.

In some larger math systems, there is an idea called the axiom of global choice. This is stronger because it works not just with collections of sets, but with bigger groups called classes. This idea comes from another concept called the axiom of limitation of size. There is also Tarski's axiom, used in another math system, which is also stronger than the axiom of choice.

Equivalents

There are important ideas in math that are connected to the axiom of choice. When we study sets using Zermelo-Fraenkel (ZF) rules but don't include the axiom of choice, these ideas either all work the same way or all don't work the same way as the axiom of choice.

Two of the most well-known connected ideas are Zorn's lemma and the well-ordering theorem. Zermelo first introduced the axiom of choice to help prove the well-ordering theorem.

• Set theory
  • Trichotomy: The sizes of any two groups of things can be compared.
  • Tarski's theorem about choice: For any large group of things, the group and the group combined with itself have the same size.
  • Every matching rule between two groups has a matching partner.
  • For any group of non-empty sets, we can pick one thing from each set.
  • If there is a rule that connects things in group X to things in group Y, where every thing in X has at least one match in Y, then we can make a new rule that matches each thing in X to one thing in Y.
  • The all-at-once group of any list of non-empty sets is not empty.
  • In any group of non-empty sets, we can find a smaller group of sets that still touches on everything in the big group.
  • For any group of things, there is a biggest possible group of groups that have no things in common.
  • Well-ordering theorem: Every group of things can be arranged in a special order where we can always find the first thing in any smaller group.
  • For any step number, the group of all possible groups of that step has a special order.
  • Hausdorff maximal principle: Every group of things arranged in steps has a biggest step group.
  • Antichain principle: Every group of things arranged in steps has a biggest group of things that don't share steps.
  • Zorn's lemma
  • Krull's theorem: Every meaningful math system with a main thing has a biggest important group.
  • For any non-empty group, there is a way to combine things so that the group follows group rules.
  • Every free group that adds and subtracts things is free to change.
  • Baer's criterion: Every group that can be split and put back together can be used in any way.
  • Every group is a free to change thing in the group of all groups.
• Functional analysis
  • The solid ball around zero in the study of math shapes over real numbers has a point that can't be split.
• Point-set topology
  • Tychonoff's theorem: The all-at-once group of any list of groups that can't be split apart is can't be split apart.
  • The covering of the all-at-once group of any list of groups in a space is the same as the covering of the groups themselves.
• Mathematical logic
  • If a group of statements in first-order logic has a part that doesn't argue with itself, then that part can be made as big as possible without arguing with itself.
  • Löwenheim–Skolem theorem: If a group of statements in first-order logic has a very large model, then it has models of every size bigger than the size of the statement language.
• Graph theory
  • Every connected network of points has a tree that touches every point; also, every part of the network that connects everything can be made into a tree that touches everything, and every part that connects everything includes a tree that touches everything.

Category theory

Many results in the study of groups and rules need the axiom of choice to prove them.

Examples of statements in this study that need choice include:

• Every small group of rules has a basic example.
• If two small groups of rules are almost the same, then they are really the same.
• Every smooth rule between small-complete groups that meets the right condition has a matching rule on the left.

Weaker forms

There are simpler ideas in math that are not the full Axiom of Choice but still need some choice. One example is the Axiom of Dependent Choice. Another is the Axiom of Countable Choice, which says that for any list of non-empty sets, we can pick one item from each set. These ideas help with many basic proofs in math.

When we add more rules, like using bigger numbers to describe sets, these simpler forms get closer to the full Axiom of Choice. Other smaller choice rules include the Boolean Prime Ideal Theorem and the Axiom of Uniformization. The Boolean Prime Ideal Theorem is linked to another rule called the Ultrafilter Lemma.

Results requiring AC (or weaker forms) but weaker than it

The Axiom of Choice is used in many parts of math. Here are some ideas that need some form of choice but not the full Axiom of Choice:

• Set theory

  • Axiom of Countable Choice: The combined items from a list of non-empty sets can always be made.
  • Axiom of Dependent Choice: If we can always move to the next item in a set using a rule, we can build an endless list following that rule.
  • Axiom of Choice for finite sets: The combined items from any list of non-empty small sets can always be made.
  • Ultrafilter Lemma: Every small group of rules can be part of a bigger, complete group of rules.
  • The combined items from a list of countable sets that can also be listed is countable.
  • Every very large set has a part that can be listed.
  • Eight ways to define a small set all work the same.
  • Every very large game with special rules has a winner.
  • For very large numbers, doubling the number gives the same number.

• Measure theory

  • There are special sets that cannot be measured the usual way.
  • Some sets that can be measured are not made from simple building blocks.

• Abstract algebra

  • Every field of numbers has a complete set of solutions.
  • Every expansion of a field has a base for building new numbers.
  • Very large spaces of numbers always contain a large independent group.
  • Special rules for building with groups of numbers need a weaker form of choice.
  • Every part of a free group is also free.
  • The number systems for real and complex numbers work the same way.

• Metric spaces

  • In spaces where distance matters, the old and new ways to find nearby points agree. This, along with two other ideas, needs only countable choice, not the full Axiom of Choice.
  • For functions between spaces where distance matters, the old and new ideas about smoothness agree.
  • For spaces where distance matters, the old and new ideas about being compact agree.

• Functional analysis

  • A rule for extending straight-line rules in complex spaces can be made.
  • Every space with inner products has a full set of basic directions.
  • Special spaces of rules have special compact properties.
  • Full spaces where distance matters have many important rules about closeness and open sets.
  • In very large spaces, there are rules that are not smooth.

• General topology

  • A special space is small and close if and only if it is complete and not too spread out.
  • Every special space has a bigger space that completes it.
  • For two separate groups in a normal space and a special number line, there is a smooth rule that separates the groups.
  • For a closed part of a normal space and a smooth rule on that part, there is a smooth rule on the whole space that matches the old one.
  • For a special type of space and any cover of that space by open pieces, there is a way to smoothly combine those pieces.

• Mathematical logic

  • Every set of logical rules that does not break can be made complete.
  • If every small part of a set of logical rules has a model, then the whole set has a model.

Stronger forms of the negation of AC

If we do not accept the axiom of choice, there are some ideas that are stronger than just saying it is not true. One of these ideas is called BP. BP says that every group of real numbers has a special property. This idea is stronger than just saying there is no way to pick one item from each group of nonempty groups.

We can mix some rules together and still have everything work out. For example, some rules work well together if we also add BP. There is also a special idea called the axiom of determinacy. This idea says that every group of real numbers can be measured in certain ways. This idea works well with some other rules, but it needs a very strong extra rule to be fully consistent.

In a different system of rules created by Quine called New Foundations, the axiom of choice cannot be proven true.

Statements implying the negation of AC

There are special ways to understand math where a rule called the axiom of choice does not work. When this rule does not work, some unusual things can happen.

For example, there can be a group of numbers that can be split into more parts than the number of items in the group. Also, there can be a math rule that behaves differently when looking at sequences of numbers close together.

Some math ideas, like certain types of spaces or groups, might not behave as usual without the axiom of choice. This helps show how important this rule is in math.

Axiom of choice in type theory

In type theory, there is a version of the axiom of choice. It starts with two types, σ and τ, and a connection R between objects of these types. The axiom says that if for every object x of type σ, there is some object y of type τ that connects with x through R, then we can create a special rule or function f. This function will connect every x of type σ to a matching y of type τ using R.

Unlike in set theory, this version of the axiom of choice is usually shown as an axiom scheme. Here, R can change to fit many different rules or forms.