FACTOID # 22: South Dakota has the highest employment ratio in America, but the lowest median earnings of full-time male employees.
 
 Home   Encyclopedia   Statistics   States A-Z   Flags   Maps   FAQ   About 
   
 
WHAT'S NEW
 

SEARCH ALL

FACTS & STATISTICS    Advanced view

Search encyclopedia, statistics and forums:

 

 

(* = Graphable)

 

 


Encyclopedia > Axiom of Choice

In mathematics, the axiom of choice, or AC, is an axiom of set theory. Intuitively speaking, AC says that given a collection of bins each containing at least one object, exactly one object from each bin can be picked and gathered in another bin—even if there are infinitely many bins and there is no "rule" for which object to pick from each. AC is not required if the number of bins is finite or if such a selection "rule" is available. Euclid, Greek mathematician, 3rd century BC, as imagined by by Raphael in this detail from The School of Athens. ... An axiom is a sentence or proposition that is not proved or demonstrated and is considered as obvious or as an initial necessary consensus for a theory building or acceptation. ... Set theory is the mathematical theory of sets, which represent collections of abstract objects. ... In set theory, an infinite set is a set that is not a finite set. ...


It was formulated in 1904 by Ernst Zermelo.[1] While it was originally controversial, it is now used without reservation by most mathematicians. However, there are schools of mathematical thought, primarily within set theory, that either reject the axiom of choice or investigate consequences of axioms inconsistent with AC. Ernst Friedrich Ferdinand Zermelo (July 27, 1871, Berlin, German Empire – May 21, 1953, Freiburg im Breisgau, West Germany) was a German mathematician, whose work has major implications for the foundations of mathematics and hence on philosophy. ...

Contents

Statement

The axiom of choice states:

Let X be a set of non-empty sets. Then we can choose a single member from each set in X.

A choice function is a function f on a collection X of sets such that for every set s in X, f(s) is an element of s. With this concept, the axiom can be stated: In mathematics, a set can be thought of as any collection of distinct objects considered as a whole. ... In set theory, a set is called non-empty (or nonempty) if it contains at least one element, and is therefore not the empty set. ... A choice function is a mathematical function whose domain is a collection of nonempty sets such that for every in , is in . ...

For any set of non-empty sets, X, there exists a choice function f defined on X.

Or alternatively:

An arbitrary Cartesian product of non-empty sets is non-empty.

Or most compactly: In mathematics, the Cartesian product is a direct product of sets. ...

Every set of nonempty sets has a choice function.

This immediately permits a compact formulation of the negation of the axiom of choice:

There exists a set of nonempty sets which has no choice function.

Variants

A second version of the axiom of choice states:

Given any set of pairwise disjoint non-empty sets, there exists at least one set that contains exactly one element in common with each of the non-empty sets.

Some authors use a third version which effectively says: In mathematics, two sets are said to be disjoint if they have no element in common. ...

For any set A, the powerset of A (minus the empty set) has a choice function.

Authors who use this formulation often speak of the choice function on A, but be advised that this is a slightly different notion of choice function. Its domain is the powerset of A (minus the empty set), and so makes sense for any set A, whereas with the definition used elsewhere in this article, the domain of a choice function on a collection of sets is that collection, and so only makes sense for sets of sets. With this alternate notion of choice function, the axiom of choice can be compactly stated as In mathematics, given a set S, the power set of S, written P(S) or 2S, is the set of all subsets of S. In formal language, the existence of power set of any set is presupposed by the axiom of power set. ...

Every set has a choice function.[2]

which is equivalent to

For any set A there is a function f such that for any non-empty subset B of A, f(B)in B

and the negation of the axiom of choice is expressed thus:

There is a set A such that for all functions f (on the set of non-empty subsets of A), there is a B such that f(B) notin B.

Usage

Until the late 19th century, the axiom of choice was often used implicitly, although it had not yet been formally stated. For example, after having established that the set X contains only non-empty sets, a mathematician might have said "let F(s) be one of the members of s for all s in X." In general, it is impossible to prove that F exists without the axiom of choice, but this seems to have gone unnoticed until Zermelo.


Not every situation requires the axiom of choice. For finite sets X, the axiom of choice follows from the other axioms of set theory. In that case it is equivalent to saying that if we have several (a finite number of) boxes, each containing at least one item, then we can choose exactly one item from each box. Clearly we can do this: We start at the first box, choose an item; go to the second box, choose an item; and so on. There are only finitely many boxes, so eventually our choice procedure comes to an end. The result is an explicit choice function: a function that takes the first box to the first element we chose, the second box to the second element we chose, and so on. (A formal proof for all finite sets would use the principle of mathematical induction.) Mathematical induction is a method of mathematical proof typically used to establish that a given statement is true of all natural numbers. ...


For certain infinite sets X, it is also possible to avoid the axiom of choice. For example, suppose that the elements of X are sets of natural numbers. Every nonempty set of natural numbers has a smallest element, so to specify our choice function we can simply say that it takes each set to the least element of that set. This gives us a definite choice of an element from each set and we can write down an explicit expression that tells us what value our choice function takes. Any time it is possible to specify such an explicit choice, the axiom of choice is unnecessary. In set theory, an infinite set is a set that is not a finite set. ...


The difficulty appears when there is no natural choice of elements from each set. If we cannot make explicit choices, how do we know that our set exists? For example, suppose that X is the set of all non-empty subsets of the real numbers. First we might try to proceed as if X were finite. If we try to choose an element from each set, then, because X is infinite, our choice procedure will never come to an end, and consequently, we will never be able to produce a choice function for all of X. So that won't work. Next we might try the trick of specifying the least element from each set. But some subsets of the real numbers don't have least elements. For example, the open interval (0,1) does not have a least element: If x is in (0,1), then so is x/2, and x/2 is always strictly smaller than x. So taking least elements doesn't work, either. In mathematics, the real numbers may be described informally as numbers that can be given by an infinite decimal representation, such as 2. ...


The reason that we are able to choose least elements from subsets of the natural numbers is the fact that the natural numbers come pre-equipped with a well-ordering: Every subset of the natural numbers has a unique least element under the natural ordering. Perhaps if we were clever we might say, "Even though the usual ordering of the real numbers does not work, it may be possible to find a different ordering of the real numbers which is a well-ordering. Then our choice function can choose the least element of every set under our unusual ordering." The problem then becomes that of constructing a well-ordering, which turns out to require the axiom of choice for its existence; every set can be well-ordered if and only if the axiom of choice is true. In mathematics, a well-order (or well-ordering) on a set S is a total order on S with the property that every non-empty subset of S has a least element in this ordering. ...


A proof requiring the axiom of choice is always nonconstructive: even if the proof produces an object then it is impossible to say exactly what that object is. Consequently, while the axiom of choice asserts that there is a well-ordering of the real numbers, it does not give us an example of one. Yet the reason why we chose above to well-order the real numbers was so that for each set in X we could explicitly choose an element of that set. If we cannot write down the well-ordering we are using, then our choice is not very explicit. This is one of the reasons why some mathematicians dislike the axiom of choice. For example, constructivists posit that all existence proofs should be totally explicit; it should be possible to construct anything that exists. They reject the axiom of choice because it asserts the existence of an object without telling what it is. On the other hand, the mere fact that one has used the axiom of choice to prove the existence of a set does not mean that it cannot be constructed by another method. In mathematics, a nonconstructive proof, is a mathematical proof that purports to demonstrate the existence of something, but which does not say how to construct it. ... In the philosophy of mathematics, constructivism asserts that it is necessary to find (or construct) a mathematical object to prove that it exists. ...


Independence

By work of Kurt Gödel and Paul Cohen, the axiom of choice is logically independent of the other axioms of Zermelo–Fraenkel set theory (ZF). This means that neither it nor its negation can be proven to be true in ZF, if ZF is consistent. Consequently, if ZF is consistent, then ZFC is consistent and ZF¬C is also consistent. [...]I dont believe in natural science. ... Paul Joseph Cohen (April 2, 1934 – March 23, 2007[1]) was an American mathematician. ... In mathematical logic, a sentence σ is called independent of a given first-order theory T if T neither proves nor refutes σ; that is, it is impossible to prove σ from T, and it is also impossible to prove from T that σ is false. ... Zermelo–Fraenkel set theory, with the axiom of choice, commonly abbreviated ZFC, is the most common form of axiomatic set theory, and as such is the most common foundation of mathematics. ...


So the decision whether or not it is appropriate to make use of the axiom of choice in a proof cannot be made by appeal to other axioms of set theory. The decision must be made on other grounds.


One argument given in favor of using the axiom of choice is that it is convenient to use it: using it cannot hurt (cannot result in contradiction) and makes it possible to prove some propositions that otherwise could not be proved.


The axiom of choice is not the only significant statement which is independent of ZF. For example, the generalized continuum hypothesis (GCH) is not only independent of ZF, but also independent of ZF plus the axiom of choice (ZFC). However, ZF plus GCH implies AC, making GCH a strictly stronger claim than AC, even though they are both independent of ZF. In mathematics, the continuum hypothesis is a hypothesis about the possible sizes of infinite sets. ...


One reason that some mathematicians dislike the axiom of choice is that it implies the existence of some bizarre counter-intuitive objects. An example of this is the Banach–Tarski paradox which says in effect that it is possible to "carve up" the 3-dimensional solid unit ball into finitely many pieces and, using only rotation and translation, reassemble the pieces into two balls each with the same volume as the original. Note that the proof, like all proofs involving the axiom of choice, is an existence proof only: it does not tell us how to carve up the unit sphere to make this happen, it simply tells us that it can be done. The Banach–Tarski paradox: A ball can be decomposed and reassembled into two balls the same size as the original. ...


On the other hand, the negation of the axiom of choice is also bizarre. For example, the statement "For any two sets S and T, the cardinality of S is less than or equal to the cardinality of T or the cardinality of T is less than or equal to the cardinality of S" is equivalent to the axiom of choice. Put differently, if the axiom of choice is false, then there are sets S and T of incomparable size: neither can be mapped in a one-to-one fashion onto a subset of the other. Negation (i. ... In mathematics, the cardinality of a set is a measure of the number of elements of the set. There are two approaches to cardinality – one which compares sets directly using bijections and injections, and another which uses cardinal numbers. ...


A third possibility is to prove theorems using neither the axiom of choice nor its negation, a tactic preferred in constructive mathematics. Such statements will be true in any model of Zermelo–Fraenkel set theory, regardless of the truth or falsity of the axiom of choice in that particular model. This renders any claim that relies on either the axiom of choice or its negation undecidable. For example, under such an assumption, the Banach–Tarski paradox is neither true nor false: It is impossible to construct a decomposition of the unit ball which can be reassembled into two unit balls, and it is also impossible to prove that it can't be done. However, the Banach–Tarski paradox can be rephrased as a statement about models of ZF by saying, "In any model of ZF in which AC is true, the Banach–Tarski paradox is true." Similarly, all the statements listed below which require choice or some weaker version thereof for their proof are undecidable in ZF, but since each is provable in any model of ZFC, there are models of ZF in which each statement is true. In mathematics, model theory is the study of the representation of mathematical concepts in terms of set theory, or the study of the structures that underlie mathematical systems. ...


Stronger axioms

The axiom of constructibility and the generalized continuum hypothesis both imply the axiom of choice, but are strictly stronger than it. The axiom of constructibility is a possible axiom for set theory in mathematics. ... In mathematics, the continuum hypothesis is a hypothesis about the possible sizes of infinite sets. ...


In class theories such as Von Neumann–Bernays–Gödel set theory and Morse–Kelley set theory, there is a possible axiom called the axiom of global choice which is stronger than the axiom of choice for sets because it also applies to proper classes. And the axiom of global choice follows from the axiom of limitation of size. In foundations of mathematics, von Neumann–Bernays–Gödel set theory (NBG) is an axiom system for set theory designed to yield the same results as Zermelo-Fraenkel set theory, together with the axiom of choice (ZFC), but with only a finite number of axioms, that is without axiom schemas. ... Morse–Kelley set theory or Kelley–Morse set theory (MK or KM) is a set theory with proper classes properly extending the usual set theory ZF. It is a first order theory (though it can be confused with second-order ZF). ... In class theories, the axiom of global choice is a stronger variant of the axiom of choice which applies to proper classes as well as sets. ... In class theories, the axiom of limitation of size says that for any class C, C is a set (a class which can be an element of other classes) if and only if V (the class of all sets) cannot be mapped one-to-one into C. This axiom is...


Equivalents

There are a remarkable number of important statements that, assuming the axioms of ZF but neither AC nor ¬AC, are equivalent to the axiom of choice. The most important among them are Zorn's lemma and the well-ordering theorem. In fact, Zermelo initially introduced the axiom of choice in order to formalize his proof of the well-ordering principle. Zermelo-Fraenkel set theory, commonly abbreviated ZFC, is the most common form of axiomatic set theory, and as such is the most common foundation of mathematics. ... Zorns lemma, also known as the Kuratowski-Zorn lemma, is a proposition of set theory that states: Every non-empty partially ordered set in which every chain (i. ... The well-ordering theorem (not to be confused with the well-ordering axiom) states that every set can be well-ordered. ...

  • Set theory
    • Well-ordering theorem: Every set can be well-ordered. Consequently, every cardinal has an initial ordinal.
    • If the set A is infinite, then A and A×A have the same cardinality.
    • Trichotomy: If two sets are given, then either they have the same cardinality, or one has a smaller cardinality than the other.
    • The Cartesian product of any nonempty family of nonempty sets is nonempty.
    • König's theorem: Colloquially, the sum of a sequence of cardinals is strictly less than the product of a sequence of larger cardinals. (The reason for the term "colloquially", is that the sum or product of a "sequence" of cardinals cannot be defined without some aspect of the axiom of choice.)
    • Every surjective function has a right inverse.
  • Order theory
    • Zorn's lemma: Every non-empty partially ordered set in which every chain (i.e. totally ordered subset) has an upper bound contains at least one maximal element.
    • Hausdorff maximal principle: In any partially ordered set, every totally ordered subset is contained in a maximal totally ordered subset.
    • Restricted Hausdorff maximal principle: In any partially ordered set there exists a maximal totally ordered subset.

Set theory is the mathematical theory of sets, which represent collections of abstract objects. ... The well-ordering theorem (not to be confused with the well-ordering axiom) states that every set can be well-ordered. ... The von Neumann cardinal assignment is a cardinal assignment which uses ordinal numbers. ... In mathematics, the cardinality of a set is a measure of the number of elements of the set. There are two approaches to cardinality – one which compares sets directly using bijections and injections, and another which uses cardinal numbers. ... A trichotomy is a splitting into three parts, and, apart from its normal literal meaning, can refer to: trichotomy (mathematics), in the mathematical field of order theory trichotomy (philosophy), for the idea that man has a threefold nature In taxonomy, a trichotomy is speciation of three groups from a common... In mathematics, the Cartesian product is a direct product of sets. ... In set theory, Königs theorem (named after the Hungarian mathematician Julius König) colloquially states that if the axiom of choice holds and if I is a set and mi and ni are cardinal numbers for every i in I, and then The sum here is the cardinality... A surjective function. ... In mathematics, the idea of inverse element generalises the concepts of negation, in relation to addition, and reciprocal, in relation to multiplication. ... Order theory is a branch of mathematics that studies various kinds of binary relations that capture the intuitive notion of a mathematical ordering. ... Zorns lemma, also known as the Kuratowski-Zorn lemma, is a proposition of set theory that states: Every non-empty partially ordered set in which every chain (i. ... The Hausdorff maximal principle, (also called the Hausdorff maximality theorem) formulated and proved by Felix Hausdorff in 1914, is an alternate and earlier formulation of Zorns lemma and therefore also equivalent to the axiom of choice. ... The Hausdorff maximal principle, (also called the Hausdorff maximality theorem) formulated and proved by Felix Hausdorff in 1914, is an alternate and earlier formulation of Zorns lemma and therefore also equivalent to the axiom of choice. ... Algebra is a branch of mathematics concerning the study of structure, relation and quantity. ... In mathematics, a vector space (or linear space) is a collection of objects (called vectors) that, informally speaking, may be scaled and added. ... In linear algebra, a basis is a set of vectors that, in a linear combination, can represent every vector in a given vector space, and such that no element of the set can be represented as a linear combination of the others. ... In mathematics, a ring is an algebraic structure in which addition and multiplication are defined and have properties listed below. ... In mathematics, more specifically in ring theory a maximal ideal is an ideal which is maximal (with respect to set inclusion) amongst all proper ideals, i. ... In mathematics, general topology or point set topology is that branch of topology which studies elementary properties of topological spaces and structures defined on them. ... In mathematics, Tychonoffs theorem states that the product of any collection of compact topological spaces is compact. ... In mathematics, a subset of Euclidean space Rn is called compact if it is closed and bounded. ... Topological spaces are structures that allow one to formalize concepts such as convergence, connectedness and continuity. ... In mathematics, the closure of a set S consists of all points which are intuitively close to S. A point which is in the closure of S is a point of closure of S. The notion of closure is in many ways dual to the notion of interior. ... In mathematical analysis, a metric space M is said to be complete (or Cauchy) if every Cauchy sequence of points in M has a limit that is also in M. Intuitively, a space is complete if it doesnt have any holes, if there arent any points missing. For... In the mathematical field of topology, a uniform space is a set with a uniform structure. ...

Category theory

There are several results in category theory which invoke the axiom of choice for their proof. These results might be weaker than, equivalent to, or stronger than the axiom of choice, depending on the strength of the technical foundations. For example, if one defines categories in terms of sets, that is, as sets of objects and morphisms (usually called a small category), or even locally small categories, whose hom-objects are sets, then there are sets which are not contained in the category of sets, and so it is difficult for a category-theoretic formulation to apply to all sets. On the other hand, other foundational descriptions of category theory are considerably stronger, and an identical category-theoretic statement of choice may be stronger than the standard formulation, à la class theory, mentioned above. In mathematics, category theory deals in an abstract way with mathematical structures and relationships between them. ... Category theory is a mathematical theory that deals in an abstract way with mathematical structures and relationships between them. ... In mathematics, the category of sets is the category whose objects are all sets and whose morphisms are all functions. ...


Examples of category-theoretic statements which require choice include:

  • Every small category has a skeleton.
  • If two small categories are weakly equivalent, then they are equivalent.
  • Every continuous functor on a small-complete category which satisfies the appropriate solution set condition has a left-adjoint (the Freyd adjoint functor theorem).

In mathematics, categories allow one to formalize notions involving abstract structure and processes that preserve structure. ... In mathematics, a skeleton of a category is a subcategory which, roughly speaking, does not contain any extraneous isomorphisms. ... In category theory, an abstract branch of mathematics, an equivalence of categories is a relation between two categories that establishes that these categories are essentially the same. There are numerous examples of categorical equivalences from many areas of mathematics. ... In mathematics, adjoint functors are pairs of functors which stand in a particular relationship with one another. ...

Weaker forms

There are several weaker statements which are not equivalent to the axiom of choice, but which are closely related. A simple one is the axiom of countable choice (ACω or CC), which states that a choice function exists for any countable set X. This usually suffices when trying to make statements about the real numbers, for example, because the rational numbers, which are countable, form a dense subset of the reals. See also the Boolean prime ideal theorem, the axiom of dependent choice (DC), and the axiom of uniformization. The axiom of countable choice or axiom of denumerable choice is an axiom of set theory similar to the axiom of choice. ... In topology and related areas of mathematics, a subset A of a topological space X is called dense (in X) if, intuitively, any point in X can be well-approximated by points in A. Formally, A is dense in X if for any point x in X, any neighborhood of... In mathematics, a number of prime ideal theorems for guaranteeing the existence of certain subsets of an abstract algebra can be stated. ... In mathematics, the axiom of dependent choice is a weak form of the axiom of choice which is still sufficient to develop most of real analysis. ... In set theory, the axiom of uniformization, a weak form of the axiom of choice, states that if is a subset of , where and are Polish spaces, then there is a subset of that is a partial function from to , and whose domain equals Such a function is called a...


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

One of the most interesting aspects of the axiom of choice is the large number of places in mathematics that it shows up. Here are some statements that require the axiom of choice in the sense that they are not provable from ZF but are provable from ZFC (ZF plus AC). Equivalently, these statements are true in all models of ZFC but false in some models of ZF.

  • General topology
    • A uniform space is compact if and only if it is complete and totally bounded.
    • Every Tychonoff space has a Stone–Čech compactification.

Set theory is the mathematical theory of sets, which represent collections of abstract objects. ... In set theory and other branches of mathematics, the union of a collection of sets is the set that contains everything that belongs to any of the sets, but nothing else. ... In mathematics the term countable set is used to describe the size of a set, e. ... Infinity is a word carrying a number of different meanings in mathematics, philosophy, theology and everyday life. ... An injective function. ... In mathematics, a natural number can mean either an element of the set {1, 2, 3, ...} (i. ... In set theory a set S is Dedekind-infinite if there is a bijective function from S to some proper subset of S, or equivalently if there is an injective function from the natural numbers into S. In the absence of choice, Dedekind-infinite is a stronger condition than merely... In set theory, determinacy is the study of under what circumstances one or the other player of a game must have a winning strategy, and the consequences of the existence of such strategies. ... In mathematics, the Borel algebra (or Borel σ-algebra) on a topological space is either of two σ-algebras on a topological space X: The minimal σ-algebra containing the open sets. ... In mathematics, the Baire space is the set of all infinite sequences of natural numbers. ... In set theory, determinacy is the study of under what circumstances one or the other player of a game must have a winning strategy, and the consequences of the existence of such strategies. ... In mathematics, a measure is a function that assigns a number, e. ... In mathematics, the Vitali set is an elementary example of a set of real numbers that is not Lebesgue measurable. ... In mathematics, a non-measurable set is a set whose structure is so complicated it sheds light on the very notion of length, area or volume. ... Please refer to Real vs. ... In mathematics, the Lebesgue measure is the standard way of assigning a volume to subsets of Euclidean space. ... In mathematics, the Hausdorff paradox, named after Felix Hausdorff, states that if you remove a certain countable subset of the sphere S², the remainder can be divided into three subsets A, B and C such that A, B, C and B ∪ C are all congruent. ... The Banach–Tarski paradox: A ball can be decomposed and reassembled into two balls the same size as the original. ... In mathematics, the Lebesgue measure is the standard way of assigning a length, area or volume to subsets of Euclidean space. ... In set theory, a disjoint union (or discriminated union) is a union of a collection of sets whose members are pairwise disjoint. ... Algebra is a branch of mathematics concerning the study of structure, relation and quantity. ... In abstract algebra, a field is an algebraic structure in which the operations of addition, subtraction, multiplication and division (except division by zero) may be performed, and the same rules hold which are familiar from the arithmetic of ordinary numbers. ... In mathematics, particularly abstract algebra, an algebraic closure of a field K is an algebraic extension of K that is algebraically closed. ... In mathematics, more specifically in abstract algebra, field extensions are the main object of study in field theory. ... In abstract algebra, the transcendence degree of a field extension L/K is a certain rather coarse measure of the size of the extension. ... In mathematics, Stones representation theorem for Boolean algebras, named in honor of Marshall H. Stone, is the duality between the category of Boolean algebras and the category of Stone spaces, i. ... In mathematics, a number of prime ideal theorems for guaranteeing the existence of certain subsets of an abstract algebra can be stated. ... The Cayley graph of the free group on two generators a and b In mathematics, a group G is called free if there is a subset S of G such that any element of G can be written in one and only one way as a product of finitely many... An additive group is a group, and any group can be written as an additive group, so the adjective additive does not describe a class of groups, but rather the notation used to write the group operation. ... Please refer to Real vs. ... The complex numbers are an extension of the real numbers, in which all non-constant polynomials have roots. ... Functional analysis is the branch of mathematics, and specifically of analysis, concerned with the study of spaces of functions. ... In mathematics, the Hahn-Banach theorem is a central tool in functional analysis. ... Functional analysis is the branch of mathematics, and specifically of analysis, concerned with the study of spaces of functions. ... In mathematics, a linear transformation (also called linear operator or linear map) is a function between two vector spaces that respects the arithmetical operations addition and scalar multiplication defined on vector spaces, or, in other words, it preserves linear combinations. Definition and first consequences Formally, if V and W are... The mathematical concept of a Hilbert space (named after the German mathematician David Hilbert) generalizes the notion of Euclidean space in a way that extends methods of vector algebra from the plane and three-dimensional space to spaces of functions. ... The Banach-Alaoglu theorem (also known as Alaoglus theorem) states that the closed unit ball of the dual space of a normed vector space is compact in the weak* topology. ... The compactness theorem is a basic fact in symbolic logic and model theory and asserts that a set (possibly infinite) of first-order sentences is satisfiable, i. ... The Baire category theorem is an important tool in general topology and functional analysis. ... In mathematical analysis, a metric space M is said to be complete (or Cauchy) if every Cauchy sequence of points in M has a limit that is also in M. Intuitively, a space is complete if it doesnt have any holes, if there arent any points missing. For... In mathematics, a metric space is a set where a notion of distance between elements of the set is defined. ... In mathematics, there are two theorems with the name open mapping theorem. In functional analysis, the open mapping theorem, also known as the Banach-Schauder theorem, is a fundamental result which states: if A : X → Y is a surjective continuous linear operator between Banach spaces X and Y, then A... In mathematics, the closed graph theorem is a basic result in functional analysis which characterizes continuous linear operators between Banach spaces in terms of the operator graph. ... In mathematics, linear maps form an important class of simple functions which preserve the algebraic structure of linear spaces and are often used as approximations to more general functions (see linear approximation). ... In mathematics, general topology or point set topology is that branch of topology which studies elementary properties of topological spaces and structures defined on them. ... In topology and related branches of mathematics, Tychonoff spaces and completely regular spaces are particularly nice kinds of topological spaces. ... In mathematics, the Stone–Čech compactification of a Tychonoff topological space is the largest Hausdorff compactification of , in the sense that any Hausdorff compactification of is a quotient of in a way that preserves the embeddings of . ...

Stronger forms of ¬AC

Now, consider stronger forms of the negation of AC. For example, if we abbreviate by BP the claim that every set of real numbers has the property of Baire, then BP is stronger than ¬AC, which asserts the nonexistence of any choice function on perhaps only a single set of nonempty sets. Note that strengthened negations may be compatible with weakened forms of AC. For example, ZF + DC + BP is consistent, if ZF is. A subset of a topological space has the property of Baire (Baire property) if it differs from an open set by a meager set; that is, if there is an open such that is meager. ...


It is also consistent with ZF + DC that every set of reals is Lebesgue measurable; however, this consistency result, due to Robert M. Solovay, cannot be proved in ZFC itself, but requires a mild large cardinal assumption (the existence of an inaccessible cardinal). The much stronger axiom of determinacy, or AD, implies that every set of reals is Lebesgue measurable, has the property of Baire, and has the perfect set property (all three of these results are refuted by AC itself). ZF + DC + AD is consistent provided that a sufficiently strong large cardinal axiom is consistent (the existence of infinitely many Woodin cardinals). In mathematics, the Lebesgue measure is the standard way of assigning a volume to subsets of Euclidean space. ... Robert M. Solovay is a set theorist who spent many years as a professor at UC Berkeley. ... In mathematics, a cardinal is called a large cardinal if it belongs to a class of cardinals, the existence of which provably cannot be proved within the standard axiomatic set theory ZFC, if one assumes ZFC itself is consistent. ... In set theory, a cardinal number is called weakly inaccessible if it is an uncountable regular weak limit cardinal and strongly inaccessible, or just inaccessible, if it is an uncountable regular strong limit cardinal. ... In mathematics, the axiom of determinacy (abbreviated as AD) is an axiom in set theory. ... In descriptive set theory, a subset of a Polish space has the perfect set property if it is either countable or has a nonempty perfect subset. ... In mathematical logic, a Woodin cardinal is a cardinal number &#954; such that for all f : &#954; &#8594; &#954; there exists &#945; < &#954; with f[&#945;] &#8838; &#945; and an elementary embedding j : V &#8594; M from V into a transitive inner model M with critical point &#945; and Vj...


Results requiring ¬AC

There are models of Zermelo-Fraenkel set theory in which the axiom of choice is false. We will abbreviate "Zermelo-Fraenkel set theory plus the negation of the axiom of choice" by ZF¬C. For certain models of ZF¬C, it is possible to prove the negation of some standard facts. Note that any model of ZF¬C is also a model of ZF, so for each of the following statements, there exists a model of ZF in which that statement is true.

  • There exists a model of ZF¬C in which there is a function f from the real numbers to the real numbers such that f is not continuous at a, but for any sequence {xn} converging to a, limn f(xn)=f(a).
  • There exists a model of ZF¬C in which real numbers are a countable union of countable sets.
  • There exists a model of ZF¬C in which there is a field with no algebraic closure.
  • In all models of ZF¬C there is a vector space with no basis.
  • There exists a model of ZF¬C in which there is a vector space with two bases of different cardinalities.

For proofs, see Thomas Jech, The Axiom of Choice, American Elsevier Pub. Co., New York, 1973. Thomas J. Jech (Tomáš Jech) is a is a set theorist who was at Penn State, but is now at the Mathematical Institute of the Academy of Sciences of the Czech Republic. ...

  • There exists a model of ZF¬C in which every set in Rn is measurable. Thus it is possible to exclude counterintuitive results like the Banach–Tarski paradox which are provable in ZFC. Furthermore, this is possible whilst assuming the Axiom of dependent choice, which is weaker than AC but sufficient to develop most of real analysis.
  • In all models of ZF¬C, the generalized continuum hypothesis does not hold.

In mathematics, a measure is a function that assigns a number, e. ... The Banach–Tarski paradox: A ball can be decomposed and reassembled into two balls the same size as the original. ... In mathematics, the axiom of dependent choice is a weak form of the axiom of choice which is still sufficient to develop most of real analysis. ... Real analysis is a branch of mathematical analysis dealing with the set of real numbers and functions of real numbers. ... In mathematics, the continuum hypothesis is a hypothesis about the possible sizes of infinite sets. ...

Law of the excluded middle

The assumption of the axiom of choice is also sufficient to derive the law of the excluded middle in some constructive systems (where the law is not assumed). For any proposition P,, we can build the sets The law of excluded middle (tertium non datur in Latin) states that for any proposition P, it is true that (P or ~P). ... In the philosophy of mathematics, constructivism asserts that it is necessary to find (or construct) a mathematical object to prove that it exists. ... In set theory and its applications to logic, mathematics, and computer science, set-builder notation is a mathematical notation for describing a set by indicating the properties that its members must satisfy. ...


U = {x in {0, 1} : (x = 0) vee P}, V = {x in {0, 1} : (x = 1) vee P}.


These are sets, using the axiom of separation. In classical set theory this would be equivalent to In axiomatic set theory and the branches of logic, mathematics, and computer science that use it, the axiom schema of specification, or axiom schema of separation, or axiom schema of restricted comprehension, is a schema of axioms in Zermelo-Fraenkel set theory. ...


U = begin{cases} {0,1}, & mbox{if } P  {0}, & mbox{if } neg Pend{cases}


and similarly for V,. However, without the law of the excluded middle, these equivalences can't be proven; in fact the two sets aren't even provably finite (in the usual sense of being in bijection with a natural number, though they would be in the Dedekind sense). In mathematics, a set is called finite if there is a bijection between the set and some set of the form {1, 2, ..., n} where is a natural number. ... A bijective function. ... In mathematics, a natural number can mean either an element of the set {1, 2, 3, ...} (i. ... In set theory a set S is Dedekind-infinite if there is a bijective function from S to some proper subset of S, or equivalently if there is an injective function from the natural numbers into S. In the absence of choice, Dedekind-infinite is a stronger condition than merely...


By the axiom of choice, there will exist a choice function f, for the set {U, V},; that is, a function f, such that


f(U) in U wedge f(V) in V,.


By the definition of the two sets, this means that


[(f(U) = 0) vee P] wedge [(f(V) = 1) vee P],,


which implies f(U) neq f(V) vee P.


But since P to (U = V), (by the axiom of extensionality), In axiomatic set theory and the branches of logic, mathematics, and computer science that use it, the axiom of extensionality, or axiom of extension, is one of the axioms of Zermelo-Fraenkel set theory. ...


therefore P to (f(U) = f(V)),,


so (f(U) neq f(V)) to neg P.


Thus neg P vee P.


As this could be done for any proposition, this completes the proof that the axiom of choice implies the law of the excluded middle. Forms of the axiom of separation are available in many constructive set theories. In the intuitionistic type theory of Per Martin-Löf, on the other hand, subsets of a type have different treatments. A form of the axiom of choice is a theorem, yet excluded middle is not. Intuitionistic Type Theory, or Constructive Type Theory, or Martin-Löf Type Theory or just Type Theory (with capital letters) is at the same time a functional programming language, a logic and a set theory based on the principles of mathematical constructivism. ... Per Martin-Löf 2004 Per Martin-Löf is a Swedish logician, philosopher, and mathematician born in 1942. ...


Quotes

"The Axiom of Choice is obviously true, the well-ordering principle obviously false, and who can tell about Zorn's lemma?" — Jerry Bona
This is a joke: although the three are all mathematically equivalent, most mathematicians find the axiom of choice to be intuitive, the well-ordering principle to be counterintuitive, and Zorn's lemma to be too complex for any intuition.
"The Axiom of Choice is necessary to select a set from an infinite number of socks, but not an infinite number of shoes." — Bertrand Russell
The observation here is that one can define a function to select from an infinite number of pairs of shoes by stating for example, to choose the left shoe. Without the axiom of choice, one cannot assert that such a function exists for pairs of socks, because left and right socks are (presumably) indistinguishable from each other.
"The axiom gets its name not because mathematicians prefer it to other axioms." — A. K. Dewdney
This quote comes from the famous April Fools' Day article in the computer recreations column of the Scientific American, April 1989.

The well-ordering theorem (not to be confused with the well-ordering axiom) states that every set can be well-ordered. ... Zorns lemma, also known as the Kuratowski-Zorn lemma, is a proposition of set theory that states: Every non-empty partially ordered set in which every chain (i. ... Bertrand Arthur William Russell, 3rd Earl Russell, OM, FRS, (18 May 1872 – 2 February 1970), was a British philosopher, logician, mathematician and advocate for social reform. ... Alexander Keewatin Dewdney (* August 5, 1941 in London, Ontario) is a Canadian mathematician, computer scientist, and philosopher who has written a number of books on the future and implications of modern computing. ... April Fools Day or All Fools Day, though not a holiday in its own right, is a notable day celebrated in many countries on April 1. ... Scientific American is a popular-science magazine, published (first weekly and later monthly) since August 28, 1845, making it the oldest continuously published magazine in the United States. ...

References

  1. ^ Zermelo, Ernst (1904). "Beweis, dass jede Menge wohlgeordnet werden kann". Mathematische Annalen 59: 514-16. 
  2. ^ Patrick Suppes, "Axiomatic Set Theory", Dover, 1972 (1960), ISBN 0-486-61630-4, p. 240
  • Ernst Zermelo, "Untersuchungen über die Grundlagen der Mengenlehre I," Mathematische Annalen 65: (1908) pp. 261-81. PDF download via digizeitschriften.de
Translated in: Jean van Heijenoort, 2002. From Frege to Godel: A Source Book in Mathematical Logic, 1879-1931. New edition. Harvard Univ. Press. ISBN 0-674-32449-8
  • 1904. "Proof that every set can be well-ordered," 139-41.
  • 1908. "Investigations in the foundations of set theory I," 199-215.
  • Gregory H Moore, "Zermelo's axiom of choice, Its origins, development and influence", Springer; 1982. ISBN 0-387-90670-3
  • Paul Howard and Jean Rubin, "Consequences of the Axiom of Choice". Mathematical Surveys and Monographs 59; American Mathematical Society; 1998.
  • Herrlich, Horst, Axiom of Choice, Springer Lecture Notes in Mathematics 1876, Springer Verlag Berlin Heidelberg (2006). ISBN 3-540-30989-6.

Patrick Colonel Suppes (b. ... Jean van Heijenoort (prounounced highenort) (July 23, 1912, Creil France - March 29, 1986, Mexico City) was a pioneer historian of mathematical logic. ...

External links


  Results from FactBites:
 
PlanetMath: axiom of choice (838 words)
objects that are proved to exist using the axiom of choice cannot generally be described by any kind of systematic rule, for if they could it would not be necessary to their construction.
Some mathematicians have suggested an axiom that would result in all subsets of the real numbers being measurable; this would of course imply the negation of the axiom of choice.
This is version 24 of axiom of choice, born on 2001-10-18, modified 2006-12-18.
Axiom of choice - Wikipedia, the free encyclopedia (3385 words)
A proof requiring the axiom of choice is always nonconstructive: even if the proof produces an object then it is impossible to say exactly what that object is. Consequently, while the axiom of choice asserts that there is a well-ordering of the real numbers, it does not give us an example of one.
Stronger than AC The axiom of constructibility and the generalized continuum hypothesis both imply the axiom of choice, but are strictly stronger than it.
The assumption of the axiom of choice is also sufficient to derive the law of the excluded middle in some constructive systems (where the law is not assumed).
  More results at FactBites »

 
 

COMMENTARY     


Share your thoughts, questions and commentary here
Your name
Your comments

Want to know more?
Search encyclopedia, statistics and forums:

 


Press Releases |  Feeds | Contact
The Wikipedia article included on this page is licensed under the GFDL.
Images may be subject to relevant owners' copyright.
All other elements are (c) copyright NationMaster.com 2003-5. All Rights Reserved.
Usage implies agreement with terms, 1022, m