:: wikimiki.org ::

BiJection

BiJection

In mathematics, injections, surjections and bijections are classes of functions distinguished by the manner in which arguments (input expressions from the domain) and images (output expressions from the codomain) are related or mapped to each other.
- A function

f: \; A \to B

is injective (one-to-one) if

f(x)=f(y) \; \to \; x=y

or, equivalently, if

x \ne y \; \to \; f(x) \ne f(y)

. One could also say that every element of the codomain (sometimes called range) is mapped to by at most one element (argument) of the domain; not every element of the codomain, however, need have an argument mapped to it. An injective function is an injection.
- A function is surjective (onto) if every element of the codomain is mapped to by some element (argument) of the domain; some images may be mapped to by more than one argument. (Equivalently, a function where the range is equal to the codomain.) A surjective function is a surjection.
- A function is bijective (one-to-one and onto) if and only if (iff) it is both injective and surjective. (Equivalently, every element of the codomain is mapped to by exactly one element of the domain.) A bijective function is a bijection (one-to-one correspondence). (Note: a one-to-one function is injective, but may fail to be surjective, while a one-to-one correspondence is both injective and surjective.) An injective function need not be surjective (not all elements of the codomain may be associated with arguments), and a surjective function need not be injective (some images may be associated with more than one argument). The four possible combinations of injective and surjective features are illustrated in the following diagrams.

Injection

if and only if A function is injective (one-to-one) if every possible element of the codomain is mapped to by at most one argument. Equivalently, a function is injective if it maps distinct arguments to distinct images. An injective function is an injection. The formal definition is the following. :The function

f: A \to B

is injective iff for all

a,b \in A

, we have

f(a) = f(b) \Rarr a = b.

- A function f : A → B is injective if and only if A is empty or f is left-invertible, that is, there is a function g: B → A such that g o f = identity function on A.
- Since every function is surjective when its codomain is restricted to its range, every injection induces a bijection onto its range. More precisely, every injection f : A → B can be factored as a bijection followed by an inclusion as follows. Let f_R : A → f(A) be f with codomain restricted to its image, and let i : f(A) → B be the inclusion map from f(A) into B. Then f = i o f_R. A dual factorisation is given for surjections below.
- The composition of two injections is again an injection, but if g o f is injective, then it can only be concluded that f is injective. See the figure at right.
- Every embedding is injective.

Surjection

embedding A function is surjective (onto) if every possible image is mapped to by at least one argument. In other words, every element in the codomain has non-empty preimage. Equivalently, a function is surjective if its range is equal to its codomain. A surjective function is a surjection. The formal definition is the following. :The function

f: A \to B

is surjective iff for all

b \in B

, there is

a \in A

such that

f(a) = b.

- A function f : A → B is surjective if and only if it is right-invertible, that is, if and only if there is a function g: B → A such that f o g = identity function on B. (This statement is equivalent to the axiom of choice.)
- By collapsing all arguments mapping to a given fixed image, every surjection induces a bijection defined on a quotient of its domain. More precisely, every surjection f : A → B can be factored as a projection followed by a bijection as follows. Let A/~ be the equivalence classes of A under the following equivalence relation: x ~ y if and only if f(x) = f(y). Equivalently, A/~ is the set of all preimages under f. Let P(~) : A → A/~ be the projection map which sends each x in A to its equivalence class [x]_~, and let f_P : A/~ → B be the well-defined function given by f_P([x]_~) = f(x). Then f = f_P o P(~). A dual factorisation is given for injections above.
- The composition of two surjections is again a surjection, but if g o f is surjective, then it can only be concluded that g is surjective. See the figure at right
- .

Bijection

axiom of choice A function is bijective if it is both injective and surjective. A bijective function is a bijection (one-to-one correspondence). A function is bijective if and only if every possible image is mapped to by exactly one argument. This equivalent condition is formally expressed as follows. :The function

f: A \to B

is bijective iff for all

b \in B

, there is a unique

a \in A

such that

f(a) = b.

- A function f : A → B is bijective if and only if it is invertible, that is, there is a function g: B → A such that g o f = identity function on A and f o g = identity function on B. This function maps each image to its unique preimage.
- The composition of two bijections is again a bijection, but if g o f is a bijection, then it can only be concluded that f is injective and g is surjective. (See the figure at right and the remarks above regarding injections and surjections.)
- The bijections from a set to itself form a group under composition, called the symmetric group.

Cardinality

Suppose you want to define what it means for two sets to "have the same number of elements". One way to do this is to say that two sets "have the same number of elements" if and only if all the elements of one set can be paired with the elements of the other, in such a way that each element is paired with exactly one element. Accordingly, we can define two sets to "have the same number of elements" if there is a bijection between them. We say that the two sets have the same cardinality.

Examples

It is important to specify the domain and codomain of each function since by changing these, functions which we think of as the same may have different jectivity.

Injective and surjective (bijective)

- For every set A the identity function id_A and thus specifically

\mathbf \to \mathbf : x \mapsto x

.
-

\mathbf^+ \to \mathbf^+ : x \mapsto x^2

and thus also its inverse

\mathbf^+ \to \mathbf^+ : x \mapsto \sqrt

.
- The exponential function

\exp : \mathbf \to \mathbf^+ : x \mapsto \mathrm^x

and thus also its inverse the natural logarithm

\ln : \mathbf^+ \to \mathbf : x \mapsto \ln

Injective and non-surjective

- The exponential function

\exp : \mathbf \to \mathbf : x \mapsto \mathrm^x

Non-injective and surjective

\mathbf \to \mathbf : x \mapsto (x-1)x(x+1) = x^3 - x

- The sine function f(x) = sin x

Non-injective and non-surjective

\mathbf \to \mathbf : x \mapsto x^2

Properties

- For every function f, subset A of the domain and subset B of the codomain we have A ⊂ f⁻¹(fA) and f(f⁻¹B) ⊂ B. If f is injective we have A = f⁻¹(fA) and if f is surjective we have f(f⁻¹B) = B.
- For every function h : A → C we can define a surjection H : A → h(A) : a → h(a) and an injection I : h(A) → C : a → a. It follows that h = I o H. This decomposition is unique up to isomorphism.

Category theory

In the category of sets, injections, surjections, and bijections correspond precisely to monomorphisms, epimorphisms, and isomorphisms, respectively.

History

This terminology was originally coined by the Bourbaki group.

Mathematics

Mathematics is often defined as the study of topics such as quantity, structure, space, and change. Another view, held by many mathematicians, is that mathematics is the body of knowledge justified by deductive reasoning, starting from axioms and definitions. Practical mathematics, in nearly every society, is used for such purposes as accounting, measuring land, or predicting astronomical events. Mathematical discovery or research often involves discovering and cataloging patterns, without regard for application. The remarkable fact that the "purest" mathematics often turns out to have practical applications is what Eugene Wigner has called "the unreasonable effectiveness of mathematics." Today, the natural sciences, engineering, economics, and medicine depend heavily on new mathematical discoveries. The word "mathematics" comes from the Greek μάθημα (máthema) meaning "science, knowledge, or learning" and μαθηματικός (mathematikós) meaning "fond of learning". It is often abbreviated maths in Commonwealth English and math in North American English.

History

:Main article: History of mathematics The evolution of mathematics might be seen to be an ever-increasing series of abstractions, or alternatively an expansion of subject matter. The first abstraction was probably that of numbers. The realization that two apples and two oranges do have something in common, namely that they fill the hands of exactly one person, was a breakthrough in human thought. In addition to recognizing how to count concrete objects, prehistoric peoples also recognized how to count abstract quantities, like time -- days, seasons, years. Arithmetic (e.g. addition, subtraction, multiplication and division), naturally followed. Monolithic monuments testify to a knowledge of geometry. Further steps need writing or some other system for recording numbers such as tallies or the knotted strings called khipu used by the Inca empire to store numerical data. Numeral systems have been many and diverse. Historically, the major disciplines within mathematics arose, from the start of recorded history, out of the need to do calculations on taxation and commerce, to understand the relationships among numbers, to measure land, and to predict astronomical events. These needs can be roughly related to the broad subdivision of mathematics, into the studies of quantity, structure, space, and change. Mathematics since has been much extended, and there has been a fruitful interaction between mathematics and science, to the benefit of both. Mathematical discoveries have been made throughout history and continue to be made today.

Inspiration, pure and applied mathematics, and aesthetics

Mathematics arises wherever there are difficult problems that involve quantity, structure, space, or change. At first these were found in commerce, land measurement and later astronomy; nowadays, all sciences suggest problems studied by mathematicians, and many problems arise within mathematics itself. Newton invented infinitesimal calculus and Feynman his Feynman path integral using a combination of reasoning and physical insight, and today's string theory also inspires new mathematics. Some mathematics is only relevant in the area that inspired it, and is applied to solve further problems in that area. But often mathematics inspired by one area proves useful in many areas, and joins the general stock of mathematical concepts. As in most areas of study, the explosion of knowledge in the scientific age has led to specialization in mathematics. One major distinction is between pure mathematics and applied mathematics. Within applied mathematics, two major areas have split off and become disciplines in their own right, statistics and computer science. Many mathematicians talk about the elegance of mathematics, its intrinsic aesthetics and inner beauty. Simplicity and generality are valued. There is beauty also in a clever proof, such as Euclid's proof that there are infinitely many prime numbers, and in a numerical method that speeds calculation, such as the fast Fourier transform. G. H. Hardy in "A Mathematicians Apology" expressed the belief that these esthetic considerations are, in themselves, sufficient to justify the study of pure mathematics. Main article: Mathematical beauty.

Notation, language, and rigor

Mathematical writing is not easily accessible to the layperson. A Brief History of Time, Stephen Hawking's 1988 bestseller, contained a single mathematical equation. This was the author's compromise with the publisher's advice, that each equation would halve the sales. The reasons for the inaccessibility even of carefully-expressed mathematics can be partially explained. Contemporary mathematicians strive to be as clear as possible in the things they say and especially in the things they write (this they have in common with lawyers). They refer to rigor. To accomplish rigor, mathematicians have extended natural language. There is precisely-defined vocabulary for referring to mathematical objects, and stating certain common relations. There is an accompanying mathematical notation which, like musical notation, has a definite content and also has a strict grammar (under the influence of computer science, more often now called syntax). Some of the terms used in mathematics are also common outside mathematics, such as ring, group and category; but are not such that one can infer the meanings. Some are specific to mathematics, such as homotopy and Hilbert space. It was said that Henri Poincaré was only elected to the Académie Française so that he could tell them how to define automorphe in their dictionary. Rigor is fundamentally a matter of mathematical proof. Mathematicians want their theorems to follow mechanically from axioms by means of formal axiomatic reasoning. This is to avoid mistaken 'theorems', based on fallible intuitions; of which plenty of examples have occurred in the history of the subject (for example, in mathematical analysis). Axioms in traditional thought were 'self-evident truths', but that conception turns out not to be workable in pushing the mathematical boundaries. At a formal level, an axiom is just a string of symbols, which has an intrinsic meaning only in the context of all derivable formulas of an axiomatic system. It was the goal of Hilbert's program to put all of mathematics on a firm axiomatic basis, but according to Gödel's incompleteness theorem every (strong enough) axiom system has undecidable formulas; and so a final axiomatization of mathematics is unavailable. Nonetheless mathematics is often imagined to be (as far as its formal content) nothing but set theory in some axiomatization, in the sense that every mathematical statement or proof could be cast into formulas within set theory.

Is mathematics a science?

Carl Friedrich Gauss referred to mathematics as the Queen of the Sciences. The mathematician-physicist Leon M. Lederman has quipped: "The physicists defer only to mathematicians, and the mathematicians defer only to God (though you may be hard pressed to find a mathematician that modest)." If one considers science to be strictly about the physical world, then mathematics, or at least pure mathematics, is not a science. An alternative view is that certain scientific fields (such as theoretical physics) are mathematics with axioms that are intended to correspond to reality. In fact, the theoretical physicist, J. M. Ziman, proposed that science is public knowledge and thus includes mathematics. [http://info.med.yale.edu/therarad/summers/ziman.htm] In any case, mathematics shares much in common with many fields in the physical sciences, notably the exploration of the logical consequences of assumptions. Intuition and experimentation also play a role in the formulation of conjectures in both mathematics and the (other) sciences.

Overview of fields of mathematics

As noted above, the major disciplines within mathematics first arose out of the need to do calculations in commerce, to understand the relationships between numbers, to measure land, and to predict astronomical events. These four needs can be roughly related to the broad subdivision of mathematics into the study of quantity, structure, space, and change (i.e. arithmetic, algebra, geometry and analysis). In addition to these main concerns, there are also subdivisions dedicated to exploring links from the heart of mathematics to other fields: to logic, to set theory (foundations) and to the empirical mathematics of the various sciences (applied mathematics). The study of quantity starts with numbers, first the familiar natural numbers and integers and their arithmetical operations, which are characterized in arithmetic. The deeper properties of whole numbers are studied in number theory. The study of structure began with investigations of Pythagorean triples. Neolithic monuments on the British Isles are constructed using Pythagorean triples. Eventually, this led to the invention of more abstract numbers, such as the square root of two. The deeper structural properties of numbers are studied in abstract algebra and the investigation of groups, rings, fields and other abstract number systems. Included is the important concept of vectors, generalized to vector spaces and studied in linear algebra. The study of vectors combines three of the fundamental areas of mathematics, quantity, structure, and space. The study of space originates with geometry, beginning with Euclidean geometry. Trigonometry combines space and number. The modern study of space generalizes these ideas to include higher-dimensional geometry, non-Euclidean geometries (which play a central role in general relativity) and topology. Quantity and space both play a role in analytic geometry, differential geometry, and algebraic geometry. Within differential geometry are the concepts of fiber bundles, calculus on manifolds. Within algebraic geometry is the description of geometric objects as solution sets of polynomal equations, combining the concepts of quantity and space, and also the study of topological groups, which combine structure and space. Lie groups are used to study space, structure, and change. Topology in all its many ramifications may be the greatest growth area in 20th century mathematics. Understanding and describing change is a common theme in the natural sciences, and calculus was developed as a most useful tool. The central concept used to describe a changing quantity is that of a function. Many problems lead quite naturally to relations between a quantity and its rate of change, and the methods of differential equations. The numbers used to represent continuous quantities are the real numbers, and the detailed study of their properties and the properties of real-valued functions is known as real analysis. These have been generalized, with the inclusion of the square root of negative one, to the complex numbers, which are studied in complex analysis. Functional analysis focuses attention on (typically infinite-dimensional) spaces of functions. One of many applications of functional analysis is quantum mechanics. Many phenomena in nature can be described by dynamical systems; chaos theory makes precise the ways in which many of these systems exhibit unpredictable yet still deterministic behavior. Beyond quantity, structure, space, and change are areas of pure mathematics that can be approached only by deductive reasoning. In order to clarify the foundations of mathematics, the fields of mathematical logic and set theory were developed. Mathematical logic, which divides into recursion theory, model theory, and proof theory, is now closely linked to computer science. When electronic computers were first conceived, several essential theoretical concepts in computer science were shaped by mathematicians, leading to the fields of computability theory, computational complexity theory, and information theory. Many of those topics are now investigated in theoretical computer science. Discrete mathematics is the common name for the fields of mathematics most generally useful in computer science. An important field in applied mathematics is statistics, which uses probability theory as a tool and allows the description, analysis, and prediction of phenomena where chance plays a part. It is used in all the sciences. Numerical analysis investigates methods for using computers to efficiently solve a broad range of mathematical problems that are typically beyond human capacity, and taking rounding errors or other sources of error into account to obtain credible answers.

Major themes in mathematics

An alphabetical and subclassified list of mathematical topics is available. The following list of themes and links gives just one possible view. For a fuller treatment, see Areas of mathematics or the list of lists of mathematical topics.

Change

:Ways to express and handle change in mathematical functions, and changes between numbers. : :Arithmetic – Calculus – Vector calculus – Analysis – Differential equations – Dynamical systems – Chaos theory – List of functions

Foundations and methods

:Approaches to understanding the nature of mathematics. :philosophy of mathematics – mathematical intuitionism – mathematical constructivism – foundations of mathematics – set theory – symbolic logic – model theory – category theory – Logic – reverse mathematics – table of mathematical symbols

Discrete mathematics

:Discrete mathematics involves techniques that apply to objects that can only take on specific, separated values. : :Combinatorics – Naive set theory – Theory of computation– Cryptography – Graph theory

Applied mathematics

:Applied mathematics uses the full knowledge of mathematics to solve real-world problems. :Mathematical physics – Mechanics – Fluid mechanics – Numerical analysis – Optimization – Probability – Statistics – Mathematical economics – Financial mathematics – Game theory – Mathematical biology – Cryptography – Information theory

Important theorems

:These theorems have interested mathematicians and non-mathematicians alike. :See list of theorems for more :Pythagorean theorem – Fermat's last theorem – Gödel's incompleteness theorems – Fundamental theorem of arithmetic – Fundamental theorem of algebra – Fundamental theorem of calculus – Cantor's diagonal argument – Four color theorem – Zorn's lemma – Euler's identity – classification theorems of surfaces – Gauss-Bonnet theorem – Quadratic reciprocity – Riemann-Roch theorem.

Important conjectures

See list of conjectures for more :These are some of the major unsolved problems in mathematics. :Goldbach's conjecture – Twin Prime Conjecture – Riemann hypothesis – Poincaré conjecture – Collatz conjecture – P=NP? – open Hilbert problems.

History and the world of mathematicians

Mathematics and other fields

:Mathematics and architecture – Mathematics and education – Mathematics of musical scales

Common misconceptions

Mathematics is not a closed intellectual system, in which everything has already been worked out. There is no shortage of open problems. Pseudomathematics is a form of mathematics-like activity undertaken outside academia, and occasionally by mathematicians themselves. It often consists of determined attacks on famous questions, consisting of proof-attempts made in an isolated way (that is, long papers not supported by previously published theory). The relationship to generally-accepted mathematics is similar to that between pseudoscience and real science. The misconceptions involved are normally based on:
- misunderstanding of the implications of mathematical rigour;
- attempts to circumvent the usual criteria for publication of mathematical papers in a learned journal after peer review, with assumptions of bias;
- lack of familiarity with, and therefore underestimation of, the existing literature. The case of Kurt Heegner's work shows that the mathematical establishment is neither infallible, nor unwilling to admit error in assessing 'amateur' work. And like astronomy, mathematics owes much to amateur contributors such as Fermat and Mersenne. Mathematics is not accountancy. Although arithmetic computation is crucial to accountants, their main concern is to verify that computations are correct through a system of doublechecks. Advances in abstract mathematics are mostly irrelevant to the efficiency of concrete bookkeeping, but the use of computers clearly does matter. Mathematics is not numerology. Numerology uses modular arithmetic to reduce names and dates down to numbers, but assigns emotions or traits to these numbers intuitively or on the basis of traditions. Mathematical concepts and theorems need not correspond to anything in the physical world. In the case of geometry, for example, it is not relevant to mathematics to know whether points and lines exist in any physical sense, as geometry starts from axioms and postulates about abstract entities called "points" and "lines" that we feed into the system. While these axioms are derived from our perceptions and experience, they are not dependent on them. And yet, mathematics is extremely useful for solving real-world problems. It is this fact that led Eugene Wigner to write an essay on The Unreasonable Effectiveness of Mathematics in the Natural Sciences. Mathematics is not about unrestricted theorem proving, any more than literature is about the construction of grammatically correct sentences. However, theorems are elements of formal theories, and in some cases computers can generate proofs of these theorems more or less automatically, by means of automated theorem provers. These techniques have proven useful in formal verification of programs and hardware designs. However, they are unlikely to generate (in the near term, at least) mathematics with any widely recognized aesthetic value.

Bibliography

- Benson, Donald C., The Moment Of Proof: Mathematical Epiphanies (1999).
- Courant, R. and H. Robbins, What Is Mathematics? (1941);
- Davis, Philip J. and Hersh, Reuben, The Mathematical Experience. Birkhäuser, Boston, Mass., 1980. A gentle introduction to the world of mathematics.
- Boyer, Carl B., History of Mathematics, Wiley, 2nd edition 1998 available, 1st edition 1968 . A concise history of mathematics from the Concept of Number to contemporary Mathematics.
- Gullberg, Jan, Mathematics--From the Birth of Numbers. W.W. Norton, 1996. An encyclopedic overview of mathematics presented in clear, simple language.
- Hazewinkel, Michiel (ed.), Encyclopaedia of Mathematics. Kluwer Academic Publishers 2000. A translated and expanded version of a Soviet math encyclopedia, in ten (expensive) volumes, the most complete and authoritative work available. Also in paperback and on CD-ROM.
- Kline, M., Mathematical Thought from Ancient to Modern Times (1973).
- Pappas, Theoni, The Joy Of Mathematics (1989).

External links

- [http://www.cut-the-knot.org/ Interactive Mathematics Miscellany and Puzzles] — A collection of articles on various math topics, with interactive Java illustrations at cut-the-knot
- Rusin, Dave: [http://www.math-atlas.org/ The Mathematical Atlas]. A guided tour through the various branches of modern mathematics.
- Stefanov, Alexandre: [http://us.geocities.com/alex_stef/mylist.html Textbooks in Mathematics]. A list of free online textbooks and lecture notes in mathematics.
- Weisstein, Eric et al.: [http://www.mathworld.com/ MathWorld: World of Mathematics]. An online encyclopedia of mathematics.
- Polyanin, Andrei: [http://eqworld.ipmnet.ru/ EqWorld: The World of Mathematical Equations]. An online resource focusing on algebraic, ordinary differential, partial differential (mathematical physics), integral, and other mathematical equations.
- A mathematical thesaurus maintained by the [http://nrich.maths.org/ NRICH] project at the University of Cambridge (UK), [http://thesaurus.maths.org/ Connecting Mathematics]
- [http://planetmath.org/ Planet Math]. An online math encyclopedia under construction, focusing on modern mathematics. Uses the GFDL, allowing article exchange with Wikipedia. Uses TeX markup.
- [http://www.mathforge.net/ Mathforge]. A news-blog with topics ranging from popular mathematics to popular physics to computer science and education.
- [http://www.youngmath.net/concerns Young Mathematicians Network (YMN)]. A math-blog "Serving the Community of Young Mathematicians". Topics include: Math News, Grad and Undergrad Life, Job Search, Career, Work & Family, Teaching, Research, Misc...
- [http://metamath.org/ Metamath]. A site and a language, that formalize math from its foundations.
- [http://world.std.com/~reinhold/dir/mathmovies.html Math in the Movies]. A guide to major motion pictures with scenes of real mathematics
- [http://math.cofc.edu/faculty/kasman/MATHFICT/default.html Mathematics in fiction]. Links to works of fiction that refer to mathematics or mathematicians.
- [http://www.mathhelpforum.com/math-help Math Help Forum]. A forum, for math help, math discussion and debate.
- [http://www.sosmath.com/CBB S.O.S. Mathematics Cyberboard] a math help forum which incorporates a LaTeX extension, making it easier for members to write and display math formulae.
- [http://www-history.mcs.st-and.ac.uk/~history/ Mathematician Bibliography]. Extensive history and quotes from all famous mathematicians.
- [http://www.physicsmathforums.com/ Physics Math Forums]
- Category:School subjects fiu-vro:Matõmaatiga zh-min-nan:Sò·-ha̍k ko:수학 ms:Matematik ja:数学 simple:Mathematics th:คณิตศาสตร์

Function (mathematics)

In mathematics, a function is a relation, such that each element of a set (the domain) is associated with a unique element of another (possibly the same) set (the codomain, not to be confused with the range). The concept of a function is fundamental to virtually every branch of mathematics and every quantitative science. The terms function, mapping, map and transformation are usually used synonymously. The term operation is frequently used for binary functions; functions whose domain is a set of functions, or a vector space, are often called operators (see also operator (programming)).

Intuitive introduction

Essentially, a function is a "rule" or procedure that assigns an "output" value to each given "input" value. The following are examples of functions:
- In a group of people, each person has a favorite colour—from the set of red, orange, yellow, green, cyan, blue, indigo, or violet. Here, the input is the person, and the output is one of the 8 colours. The favorite colour is a function of the person. For example, John has favorite colour red, while Kim has favorite colour violet. Note that more than one person may be associated with a given colour (e.g., John and Kim may both like red), but one person cannot have more or less than one favorite color.
- A stone is dropped from different stories of a tall building. The dropped stone may take 2 seconds to fall from the second story, and 4 seconds to fall from the 8th story. Here, the input is the story, and the output is the number of seconds. The relevant function describes the relationship between the time it takes the stone to reach the ground and the story. (See acceleration) The "rule" defining a function can be specified by a formula, a relationship, or simply a table listing the outputs against inputs. The most important feature of a function is that it is consistent, or deterministic, always producing the same output from a given input. In this way, a function may be thought of as a mechanism or "machine" (a "black box") consistently converting a given valid input into its unique associated output. In certain technical contexts, the input is often called the argument of the function, and the output the value of the function. A very common type of function occurs when the argument (input) and the value (output) are both numbers, the functional relationship is expressed by a formula, and the value (output) of the function is obtained by direct substitution of the argument into the formula. Consider for example :

f(x)=x^

which for any number x, assigns to x the associated value the square of x. A straightforward generalization is to allow functions depending on several arguments. For instance, :

g(x,y) = xy

is a function which takes the input, two expressions x and y, and assigns to it its product (output), xy. It might seem that this is not really a function as we described above, because this "rule" depends on two inputs. However, if we think of the two inputs together as a single pair (x, y), then we can interpret g as a function -- the argument (unified single input) is the ordered pair (x, y), and the function value (output) is xy. Such functions whose input consists of ordered pairs are called "binary" or "2-ary". In the sciences, we often encounter functions that are not given by (known) formulas. Consider for instance the temperature distribution on earth over time: this is a function which takes location and time as arguments and gives as output value the temperature at the indicated location at the indicated moment in time. We have seen that the intuitive notion of function is not limited to computations using single numbers and not even limited to computations; the mathematical notion of function is still more general and is not limited to situations involving numbers. Rather, a function links a "domain" (set of inputs) to a "codomain" (set of possible outputs) in such a way that every element of the domain is associated to precisely one element of the codomain. Functions are abstractly defined as certain relations, as will be seen below. Because of this generality, the function concept is fundamental to virtually every branch of mathematics and the quantitative sciences.

History

As a mathematical term, "function" was coined by Leibniz in 1694, to describe a quantity related to a curve, such as a curve's slope or a specific point of a curve. The functions Leibniz considered are today called differentiable functions, and they are the type of function most frequently encountered by nonmathematicians. For this type of function, one can talk about limits and derivatives; both are measurements of the change of output values associated to a change of input values, and these measurements are the basis of calculus. The word function was later used by Euler during the mid-18th century to describe an expression or formula involving various arguments, e.g. f(x) = sin(x) + x³. During the 19th century, mathematicians started to formalize all the different branches of mathematics. Weierstrass advocated building calculus on arithmetic rather than on geometry, which favoured Euler's definition over Leibniz's (see arithmetization of analysis). By broadening the definition of functions, mathematicians were then able to study "strange" mathematical objects such as continuous functions that are nowhere differentiable. These functions were first thought to be only theoretical curiosities, and they were collectively called "monsters" as late as the turn of the 20th century. However, powerful techniques from functional analysis have shown that these functions are in some sense "more common" than differentiable functions. Such functions have since been applied to the modeling of physical phenomena such as Brownian motion. Towards the end of the 19th century, mathematicians started trying to formalize all of mathematics using set theory, and they sought to define every mathematical object as a set. Dirichlet and Lobachevsky independently and almost simultaneously gave the modern "formal" definition of function (see formal definition below). In this definition, a function is a special case of a relation. In most cases of practical interest, however, the differences between the modern definition and Euler's definition are negligible. The notion of function as a rule for computing, rather than a special kind of relation, has been formalized in mathematical logic and theoretical computer science by means of several systems, including the lambda calculus, the theory of recursive functions and the Turing machine.

Formal definition

Formally a function f from a set X to a set Y, written f : X → Y, is an ordered triple (X, Y, G(f)), where G(f) is a subset of the cartesian product X × Y, such that for each x in X, there is a unique y in Y such that the ordered pair (x, y) is in G(f). X is called the domain of f, Y is called the codomain of F, and G(f) is called the graph of f. For each "input value" x in the domain, the corresponding unique "output value" y in the codomain is denoted by f(x). Equivalently a function f can be defined as a relation between X and Y which satisfies: # f is total, or entire: for all x in X, there exists a y in Y such that x f y (x is f-related to y), i.e. for each input value, there is at least one output value in Y. # f is many-to-one, or functional: if x f y and x f z, then y = z. i.e., many input values can be related to one output value, but one input value cannot be related to many output values. A relation between X and Y that satisfies condition (1) is a multivalued function. Every function is a multivalued function, but not every multivalued function is a function. A relation between X and Y that satisfies condition (2) is a partial function. Every function is a partial function, but not every partial function is a function. In this encyclopedia, the term "function" will mean a relation satisfying both conditions (1) and (2), unless otherwise stated. Consider the following three examples:

image:notMap1.png

This relation is total but not many-to-one; the element 3 in X is related to two elements b and c in Y. Therefore, this is a multivalued function, but not a function.

image:notMap2.png

This relation is many-to-one but not total; the element 1 in X is not related to any element of Y. Therefore, this is a partial function, but not a function.

image:mathmap2.png

This relation is both total and many-to-one, and so it is a function from X to Y. Note that the emphasis is on "-to-one" as "many" may actually mean "one". The function can be given explicitly by specifying its graph G(f) = or as :

f(x)=\left\

Parameter

:For usage in computer science and programming, see parameter (computer science). A parameter is a measurement or value on which something else depends. For example, a parametric equaliser is an audio filter that allows the frequency of maximum cut or boost to be set by one control, and the size of the cut or boost by another. These settings, the frequency level of the peak or trough, are two of the parameters of a frequency response curve, and in a two-control equaliser they completely describe the curve. More elaborate parametric equalisers may allow other parameters to be varied, such as skew. These parameters each describe some aspect of the response curve seen as a whole, over all frequencies. A graphic equaliser provides individual level controls for various frequency bands, each of which acts only on that particular frequency band.

Types of parameter

Mathematical

In mathematics, the difference in meaning between a parameter and an argument of a function is that the parameters are the symbols that are part of the function's definition, while arguments are the symbols that are supplied to the function when it is used. The value or objects assigned to the parameters by the corresponding arguments of a function or system are not reassigned during the function's evaluation. So, parameters are effectively constants during the evaluation or processing of that function or system. The value of arguments can change outside of the function and between function usages. This distinction, the parameter's constancy, is a key part of the meaning of a parameter in any situation, often in usage beyond just mathematics. In some informal situations people regard it as a matter of convention (and therefore a historical accident) whether some or all the arguments of a function are called parameters.

Computer science

When the terms formal parameter and actual parameter are used, they generally correspond with the definitions used in computer science. In the definition of a function such as :f(x) = x + 2, x is a formal parameter. When the function is used as in :y = f(3) + 5, 3 is the actual parameter value that is used to solve the equation. These concepts are discussed in a more precise way in functional programming and its foundational disciplines, lambda calculus and combinatory logic. In computing, the parameters passed to a function subroutine are more normally called arguments.

Logic

In logic, the parameters passed to (or operated on by) an open predicate are called parameters by some authors (e.g., Prawitz, "Natural Deduction"; Paulson, "Designing a theorem prover"). Parameters locally defined within the predicate are called variables. This extra distinction pays off when defining substitution (without this distinction special provision has to be made to avoid variable capture). Others (maybe most) just call parameters passed to (or operated on by) an open predicate variables, and when defining substitution have to distinguish between free variables and bound variables.

Analytic geometry

In analytic geometry, curves are often given as the image of some function. The argument of the function is invariably called "the parameter". A circle of radius 1 centered at the origin can be specified in more than one form: - implicit form :

x^2+y^2=1

- parametric form :

(x,y)=(\cos t,\sin t)

:where t is the parameter. A somewhat more detailed description can be found at parametric equation.

Mathematical analysis

In mathematical analysis, one often considers "integrals dependent on a parameter". These are of the form :

F(t)=\int_^f(x;t)\,dx.

In this formula, t is the argument of the function F on the left-hand side, and the parameter that the integral depends on, on the right-hand side. The quantity x is a dummy variable or variable (or parameter) of integration. Now, if we performed the substitution x=g(y), it would be called a change of variable.

Probability theory

In probability theory, one may describe the distribution of a random variable as belonging to a family of probability distributions, distinguished from each other by the values of a finite number of parameters. For example, one talks about "a Poisson distribution with mean value λ", or "a normal distribution with mean μ and variance σ²". The latter formulation and notation leaves some ambiguity whether σ or σ² is the second parameter; the distinction is not always relevant. It is possible to use the sequence of moments (mean, mean square, ...) or cumulants (mean, variance, ...) as parameters for a probability distribution.

Statistics

In statistics, the probability framework above still holds, but attention shifts to estimating the parameters of a distribution based on observed data, or testing hypotheses about them. In classical estimation these parameters are considered "fixed but unknown", but in Bayesian estimation they are random variables with distributions of their own. It is possible to make statistical inferences without assuming a particular parametric family of probability distributions. In that case, one speaks of non-parametric statistics as opposed to the parametric statistics described in the previous paragraph. For example, Spearman is a non-parametric test as it is computed from the order of the data regardless of the actual values, whereas Pearson is a parametric test as it is computed directly from the data and can be used to derive a mathematical relationship. Statistics are mathematical characteristics of samples which are used as estimates of parameters, mathematical characteristics of the populations from which the samples are drawn. For example, the sample mean (

\overline X

) is an estimate of the mean parameter (μ) of the population from which the sample was drawn.

Expression (mathematics)

An expression combines numbers, operators, and/or free variables and bound variables: bound variables are defined in the expression (they are for internal use), free variables are taken from the context. For a given combination of values for the free variables, an expression may be evaluated to a value, and is said to have that value, although for some combinations of values of the free variables, the expression may be undefined. Thus an expression represents a function of the values for the free variables. The evaluation of an expression is dependent on the definition of the mathematical operators and system of values that forms the context of an expression. Two expressions are said to be equivalent if, for each combination of values for the free variables, they have the same value, i.e., they represent the same function. Example: The expression :

\sum_^ 2xy

has free variable x, bound variable y, constants 1, 2, and 3, two occurrences of an implicit multiplication operator, and a summation operator. The expression is equivalent with the simpler expression 12x. The value for x=3 is 36. Expressions and their evaluation were formalised by Alonzo Church and Stephen Kleene in the 1930s in their lambda calculus. The lambda calculus has been a major influence in the development of modern mathematics and computer programming languages. One of the more interesting results of the lambda calculus is that the equivalence of two expressions in the lambda calculus is in some cases undecidable. This is also true of any expression in any system that has power equivalent to the lambda calculus.

External links

- [http://www.mathematics21.org/theory-of-formulas-index.html Axiomatic Theory of Formulas] - theory of expressions on high abstraction level.
- [http://www.algebra.com/services/rendering/ Plot mathematical expressions] this system plots math equations, graphs, diagrams, and even animated cartoons of transformation of math expressions and arithmetic operations. Knowledge of TeX not required. Category:Abstract algebra Category:Algebra ja:数式

Image (mathematics)

In mathematics, the image of an element x in a set X under the function f : X → Y, denoted by f(x), is the unique y in Y that is associated with x. The image of a subset A ⊆ X under f is the subset of Y defined by :f[A] = Notice that the range of f is the image f[X] of its domain X. An alternative notation for f[A], favored by set theorists, is f ^"A. When there is no risk of confusion, f[A] is sometimes denoted simply f(A). With this definition, the image of f becomes a function whose domain is the set of all subsets of X (also known as the power set of X) and whose codomain is the power set of Y. Note that the same notation is used for the original function f and its image. This is a common convention; the intended usage must be inferred from context. The preimage or inverse image of a set B ⊆ Y under f is the subset of X defined by :f⁻¹[B] = The inverse image of a singleton, f⁻¹[], is called a fiber or fibre, or level set. Again, in a context where there is no risk of confusion, we may denote f⁻¹[B] by f⁻¹(B), and think of f⁻¹ as a function from the power set of Y to the power set of X. Note that f⁻¹ should not be confused with the inverse function. The two only coincide if f is bijective. Looking at it the other way,

f

can be seen as a family of sets indexed by

Y

. An obvious extension of this idea is that of a fibred category.

Examples

1. f: → defined by

f(x)=\left\

Codomain

A codomain in mathematics is the set of "output" values associated with (or mapped to) the domain of "input" arguments in a function. For any given function

f\colon A\rightarrow B

, the set A, on which f is defined (the arguments), is called the domain, and B (the set of possible values) is called the codomain of f. The set of all actual values

\lbrace f(x) | x \in A \rbrace

or f(A) is called the range of f. Beware that sometimes the codomain is incorrectly called the range because of a failure to distinguish between possible and actual values. The codomain is not to be confused with the range, which is in general only a subset of B; in lower-level mathematics education, however, range is often taught as being equivalent to codomain.

Example

Let the function f be a function on the real numbers: :

f\colon \mathbb\rightarrow\mathbb

defined by :

f\colon\,x\mapsto x^2.

The codomain of f is R, but clearly f(x) never takes negative values, and thus the range is in fact the set R₀⁺—non-negative reals, i.e. the interval [0,∞): :

0\leq f(x)<\infty.

One could have defined the function g thus: :

g\colon\mathbb\rightarrow\mathbb^+_0

g\colon\,x\mapsto x^2.

While f and g have the same effect on a given number, they are not, in the modern view, the same function since they have different codomains. The codomain can affect whether or not the function is a surjection; in our example, g is a surjection while f is not. The codomain does not affect whether or not the function is an injection.

Codomain

A codomain in mathematics is the set of "output" values associated with (or mapped to) the domain of "input" arguments in a function. For any given function

f\colon A\rightarrow B

, the set A, on which f is defined (the arguments), is called the domain, and B (the set of possible values) is called the codomain of f. The set of all actual values

\lbrace f(x) | x \in A \rbrace

Example

Let the function f be a function on the real numbers: :

f\colon \mathbb\rightarrow\mathbb

defined by :

f\colon\,x\mapsto x^2.

The codomain of f is R, but clearly f(x) never takes negative values, and thus the range is in fact the set R₀⁺—non-negative reals, i.e. the interval [0,∞): :

0\leq f(x)<\infty.

One could have defined the function g thus: :

g\colon\mathbb\rightarrow\mathbb^+_0

g\colon\,x\mapsto x^2.

If and only if

↔
⇔
≡

logical symbols
representing iff.

In mathematics, philosophy, logic and technical fields that depend on them, "if and only if" is a connective between statements which means that the truth of either one of the statements requires the truth of the other. Thus, either both statements are true, or both are false. In writing, common alternative phrases to "if and only if" include iff, "Q is necessary and sufficient for P", "P is equivalent to Q", "P precisely if Q", and "P precisely when Q". (Many authors regard "iff" as unsuitable in formal writing; others use it freely.) In logical formulae, logical symbols are used instead of these phrases; see the discussion of notation.

Usage

Notation

The corresponding logical symbols are "↔" and "⇔" and "≡", and sometimes "iff". These are usually treated as equivalent. However, some texts of mathematical logic (particularly those on first-order logic, rather than propositional logic) make a distinction between these, in which the first, ↔, is used as a symbol in logic formulas, while ⇔ is used in reasoning about those formulas (e.g., in metalogic). Another term for the logical connective is exclusive nor.

Proofs

In most logical systems, one proves a statement of the form "P iff Q", through the more roundabout route of separately proving both of the statements "if P, then Q" and "if Q, then P". (or its contrapositive, "If not P, then not Q"). Proving this pair of statements sometimes leads to a more natural proof, since there are not obvious conditions in which one would infer a biconditional directly. An alternative is to prove the disjunction "(P and Q) or (not-P and not-Q)", which itself can be inferred directly from either of its disjuncts--that is, because "iff" is truth-functional, "P iff Q" follows if P and Q have both been shown true, or both false.

Origin of the abbreviation

Usage of the abbreviation iff first appeared in print in John Kelley's 1955 book General Topology. Its invention is often credited to the mathematician Paul Halmos, but in his autobiography he states that he borrowed it from puzzlers.

The difference between "if" and "iff"

Put simply, the difference between if and iff can be explained with the following two sentences: # Madison will eat pudding if the pudding is a custard. (equivalently: If the pudding is a custard, then Madison will eat it) #: # Madison will eat pudding if and only if (iff) the pudding is a custard. Sentence (1) states only that Madison will eat custard pudding. It does not however preclude the possibility that Madison might also have occasion to eat bread pudding. Maybe she will, maybe she will not. The sentence does not tell us. All we know for certain is that she will eat custard pudding. Sentence (2) however makes it quite clear that Madison will eat custard pudding and custard pudding only. She will not eat any other type of pudding. A further difference is that "if" is used in definitions (except in formal logic); see more below.

Advanced considerations

Philosophical interpretation

A sentence that is composed of two other sentences joined by "iff" is called a biconditional. Iff joins two sentences to form a new sentence. It should not be confused with logical equivalence which is a description of a relation between two sentences. The biconditional "A iff B" uses the sentences A and B, describing a relation between the states of affairs A and B describe. By contrast "A is logically equivalent to B" mentions the two sentences: it describes a relation between those two sentences, and not between whatever matters they describe. The distinction is a very confusing one, and has led many a philosopher astray. Certainly it is the case that when A is logically equivalent to B, "A iff B" is true. But the converse does not hold. Let's reconsider the sentence: :Madison will eat pudding today if and only if it's custard. There is clearly no logical equivalence between the two halves of this particular biconditional. For more on the distinction, see W. V. Quine's Mathematical Logic, Section 5.

Definitions

In philosophy and logic, "iff" is used to indicate definitions, since definitions are supposed to be universally quantified biconditionals. In mathematics and elsewhere, however, the word "if" is normally used in definitions, rather than "iff". This is due to the observation that "if" in the English language has a definitional meaning, separate from its meaning as a propositional conjunction. This separate meaning can be explained by noting that a definition (for instance: A group is "abelian" if it satisfies the commutative law; or: A grape is a "raisin" if it is well dried) is not an equivalence to be proved, but a rule for interpreting the term defined. (Some authors, nevertheless, explicitly indicate that the "if" of a definition means "iff"!)

Examples

Here are some examples of true statements that use "iff" - true biconditionals (the first is an example of a definition, so it should normally have been written with "if"):
- A person is a bachelor iff that person is an unmarried but marriageable man.
- "Snow is white" (in English) is true iff "Schnee ist weiß" (in German) is true.
- For any p, q, and r: (p & q) & r iff p & (q & r). (Since this is written using variables and "&", the statement would usually be written using "↔", or one of the other symbols used to write biconditionals, in place of "iff").

Analogs

Other words are also sometimes emphasized in the same way by repeating the last letter; for example orr for "Or and only Or" (the exclusive disjunction).

More general usage

Iff is used outside the field of logic, wherever logic is applied, especially in mathematical discussions. It has the same meaning as above: it is an abbreviation for if and only if, indicating that one statement is both necessary and sufficient for the other. This is an example of mathematical jargon. (However, as noted above, if, rather than iff, is generally used in statements of definition.) Category:Logic Category:Mathematical terminology ja:同値

IFF

IFF, Iff or iff can stand for:
- Interchange File Format - a computer file format introduced by Electronic Arts
- Identification friend or foe - a battlefield identification system
- iff - the mathematics concept if and only if
- International Film Festival
- TIFF - Toronto International Film Festival
- Montreal International Film Festival
- International Floorball Federation - the international federation regulating the sport of floorball
- International Flavors and Fragrances

Codomain

A codomain in mathematics is the set of "output" values associated with (or mapped to) the domain of "input" arguments in a function. For any given function

f\colon A\rightarrow B

, the set A, on which f is defined (the arguments), is called the domain, and B (the set of possible values) is called the codomain of f. The set of all actual values

\lbrace f(x) | x \in A \rbrace

Example

Let the function f be a function on the real numbers: :

f\colon \mathbb\rightarrow\mathbb

defined by :

f\colon\,x\mapsto x^2.

The codomain of f is R, but clearly f(x) never takes negative values, and thus the range is in fact the set R₀⁺—non-negative reals, i.e. the interval [0,∞): :

0\leq f(x)<\infty.

One could have defined the function g thus: :

g\colon\mathbb\rightarrow\mathbb^+_0

g\colon\,x\mapsto x^2.

Embedding

:For other uses of this term, see embedded (disambiguation). In mathematics, an embedding (or imbedding) is one instance of some mathematical object contained within another instance, such as a group that is a subgroup.

Topology/Geometry

General topology

In general topology, an embedding is a homeomorphism onto its image. More explicitly, a map f : X → Y between topological spaces X and Y is an embedding if f yields a homeomorphism between X and f(X) (where f(X) carries the subspace topology inherited from Y). Intuitively then, the embedding f : X → Y lets us treat X as a subspace of Y. Every embedding is injective and continuous. Every map that is injective, continuous and either open or closed is an embedding; however there are also embeddings which are neither open nor closed. The latter happens if the image f(X) is neither an open set nor a closed set in Y.

Differential geometry

In differential geometry: Let M and N be smooth manifolds and

f:M\to N

be a smooth map, it is called an immersion if for any point

x\in M

the differential

d_xf:T_x(M)\to T_(N)

is injective (here

T_x(M)

denotes tangent space of

M

x

). Then an embedding, or a smooth embedding, is defined to be an immersion which is an embedding in the above sense (i.e. homeomorphism onto its image). When the manifold is compact, the notion of a smooth embedding is equivalent to that of an injective immersion. In other words, an embedding is diffeomorphic to its image, and in particular the image of an embedding must be a submanifold. An immersion is a local embedding (i.e. for any point

x\in M

there is a neighborhood

x\in U\subset M

such that

f:U\to N

is an embedding.) An important case is N=Rⁿ. The interest here is in how large n must be, in terms of the dimension m of M. The Whitney embedding theorem states that n = 2m is enough. For example the real projective plane of dimension 2 requires n = 4 for an embedding. The less restrictive condition of immersion applies to the Boy's surface—which has self-intersections.

Riemannian geometry

In Riemannian geometry: Let (M,g) and (N,h) be Riemannian manifolds. An isometric embedding is a smooth embedding f : M → N which preserves the metric in the sense that g is equal to the pullback of h by f, i.e. g = f
- h. Explicitly, for any two tangent vectors :

v,w\in T_x(M)

we have :

g(v,w)=h(df(v),df(w))

. Analogously, isometric immersion is an immersion between Riemannian manifolds which preserves the Riemannian metrics. Equivalently, an isometric embedding (immersion) is a smooth embedding (immersion) which preserves length of curves (cf. Nash embedding theorem).

Algebra

Field theory

In field theory, an embedding of a field E in a field F is a ring homomorphism σ : E → F. The kernel of σ is an ideal of E which cannot be the whole field E, because of the condition σ(1)=1. Therefore the kernel is 0 and thus any embedding of fields is a monomorphism. Moreover, E is isomorphic to the subfield σ(E) of F. This justifies the name embedding for an arbitrary homomorphism of fields.

Domain theory

In domain theory, an embedding of partial orders is

F

in the function space [X →Y] such that #

\forall x_1,x_2\in X: x_1\leq x_2\Leftrightarrow F(x_1)\leq F(x_2)

and #

\forall y\in Y:\

is directed. Based on an article from FOLDOC, used by permission.

Preimage

f

can be seen as a family of sets indexed by

Y

. An obvious extension of this idea is that of a fibred category.

Examples

1. f: → defined by

f(x)=\left\

Axiom of choice

In mathematics, the axiom of choice, or AC, is an axiom of set theory. It was formulated in 1904 by Ernst Zermelo. While it was originally controversial, it is now used without embarrassment by most mathematicians. However, there are still schools of mathematical thought, primarily within set theory, that either reject the axiom of choice, or even investigate consequences of axioms inconsistent with AC. Intuitively speaking, AC says that given a collection of bins, each containing at least one object, then 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.

Statement

The axiom of choice states: Stated more formally: Another formulation of the axiom of choice states:

Usage

Until the late 19th century, the axiom of choice was often used implicitly. 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.) 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 least 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. 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, . So that won't work, either. The reason that we are able to choose least elements from subsets of the natural numbers is the fact that the natural numbers are well-ordered: Every subset of the natural numbers has a unique least element. 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 constructing such an ordering, and it turns out that every set can be well-ordered if and only if the axiom of choice is true. 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.

Independence of AC

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. Consequently, assuming the axiom of choice, or its negation, will never lead to a contradiction that could not be obtained without that assumption. 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. 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. On the other hand, the negation of the axiom of choice is also bizarre. For example, the statement that 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. 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 under Results requiring AC 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.

Weaker forms of AC

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, 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, and the axiom of uniformization.

Results requiring AC (or weaker forms)

One of the most interesting aspects of the axiom of choice is the large number of places in mathematics that it shows up. There are also 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: every set can be well-ordered. In fact, Zermelo initially introduced the axiom of choice in order to formalize his proof of the well-ordering principle. 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. The statements printed in bold have the property that they are equivalent to AC (over ZF). - Set theory - Any union of countably many countable sets is itself countable. - If the set A is infinite, then there exists an injection from the natural numbers N to A. - If the set A is infinite, then A and A×A have the same cardinality. - Trichotomy: If two sets are given, then they either have the same cardinality, or one has a smaller cardinality than the other. - The product of any nonempty family of nonempty sets is nonempty. - Every infinite game

G(T,X)

where

X

is either open or closed is determined.
- Measure theory
- The Vitali theorem on the existence of non-measurable sets.
- The Hausdorff paradox.
- The Banach-Tarski paradox.
- Algebra
- Every vector space has a basis.
- Every unital ring other than the trivial ring contains a maximal ideal.
- Every field has an algebraic closure.
- Every field extension has a transcendence basis.
- Every

BiJection

Injection

Surjection

Bijection

Cardinality

Examples

Injective and surjective (bijective)

Injective and non-surjective

Non-injective and surjective

Non-injective and non-surjective

Properties

Category theory

History

See also

Mathematics

History

Inspiration, pure and applied mathematics, and aesthetics

Notation, language, and rigor

Is mathematics a science?

Overview of fields of mathematics

Major themes in mathematics

Quantity

Structure

Space

Change

Foundations and methods

Discrete mathematics

Applied mathematics

Important theorems

Important conjectures

History and the world of mathematicians

Mathematics and other fields

Common misconceptions

See also

Bibliography

External links

Function (mathematics)

Intuitive introduction

History

Formal definition

Parameter

Types of parameter

Mathematical

Computer science

Logic

Analytic geometry

Mathematical analysis

Probability theory

Statistics

See also

Expression (mathematics)

See also

External links

Image (mathematics)

Examples

Codomain

Example

See also

Codomain

Example

See also

If and only if

Usage

Notation

Proofs

Origin of the abbreviation

The difference between "if" and "iff"

Advanced considerations

Philosophical interpretation

Definitions

Examples

Analogs

More general usage

IFF

Codomain

Example

See also

Embedding

Topology/Geometry

General topology