Home About us Products Services Contact us Bookmark
:: wikimiki.org ::
Mathematical Structure

Mathematical structure

In mathematics, a structure on a set, or more generally a type, consists of additional mathematical objects that in some manner attach to the set, making it easier to visualize or work with, or endowing the collection with meaning or significance. A partial list of possible structures are measures, algebraic structures (groups, fields, etc.), topologies, metric structures (geometries), orders, and equivalence relations. Sometimes, a set is endowed with more than one structure simultaneously; this enables mathematicians to study it more richly. For example, an order induces a topology. As another example, if a set both has a topology and is a group, and the two structures are related in a certain way, the set becomes a topological group.

Example: the real numbers

The set of real numbers has several standard structures:
- an order: each number is either less or more than every other number.
- algebraic structure: there are operations of multiplication and addition that make it into a field.
- a measure: intervals along the real line have a certain length.
- a geometry: it is equipped with a metric and is flat.
- a topology: numbers are close to or far from one another. There are interfaces among these:
- Its order and, independently, its metric structure induce its topology.
- Its order and algebraic structure make it into an ordered field.
- Its algebraic structure and topology make it into a Lie group, a type of topological group.

References


- (provides a categorical definition.) Structure ja:数学的構造

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.

Quantity

This starts from explicit measurements of sizes of numbers or sets, or ways to find such measurements. : :Number – Natural number – Integers – Rational numbers – Real numbers – Complex numbers – Hypercomplex numbers – Quaternions – Octonions – Sedenions – Hyperreal numbers – Surreal numbers – Ordinal numbers – Cardinal numbers – p-adic numbers – Integer sequences – Mathematical constants – Number names – Infinity – Base

Structure

:Pinning down ideas of size, symmetry, and mathematical structure. : :Abstract algebra – Number theory – Algebraic geometry – Group theory – Monoids – Analysis – Topology – Linear algebra – Graph theory – Universal algebra – Category theory – Order theory – Measure theory

Space

:A more visual approach to mathematics. : :Topology – Geometry – Trigonometry – Algebraic geometry – Differential geometry – Differential topology – Algebraic topology – Linear algebra – Fractal geometry

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

See also list of mathematics history topics :History of mathematics – Timeline of mathematics – Mathematicians – Fields medal – Abel Prize – Millennium Prize Problems (Clay Math Prize) – International Mathematical Union – Mathematics competitions – Lateral thinking – Mathematical abilities and gender issues

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.

See also


- Mathematical game
- Mathematical problem
- Mathematical puzzle
- Puzzle

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:คณิตศาสตร์

Type theory

At the broadest level, type theory is the branch of mathematics and logic that concerns itself with classifying entities into collections called types. In this sense, it is related to the metaphysical notion of 'type'. Modern type theory was invented partly in response to Russell's paradox, and features prominently in Russell and Whitehead's Principia Mathematica. With the rise of powerful programmable computers, and the development of programming languages for the same, type theory has found practical application in the development of programming language type systems. Definitions of "type system" in the context of programming languages vary, but the following definition due to Benjamin C. Pierce roughly corresponds to the current consensus in the type theory community: :[A type system is a] tractable syntactic method for proving the absence of certain program behaviors by classifying phrases according to the kinds of values they compute.
(Types and Programming Languages, MIT Press, 2002) In other words, a type system divides program values into sets called types (this is called a "type assignment"), and makes certain program behaviors illegal on the basis of the types that are thus assigned. For example, a type system may classify the value "hello" as a string and the value 5 as a number, and prohibit the programmer from adding "hello" to 5 based on that type assignment. In this type system, the program "hello" + 5 would be illegal. Hence, any program permitted by the type system would be provably free from the erroneous behavior of adding strings and numbers. The design and implementation of type systems is a topic nearly as broad as the topic of programming languages itself. In fact, type theory proponents commonly proclaim that the design of type systems is the very essence of programming language design: "Design the type system correctly, and the language will design itself." Note that type theory, as described herein, refers to static typing disciplines. Programming systems and languages that employ dynamic typing do not prove a priori that a program uses values correctly; instead they raise an error at runtime, when the program attempts to perform some behavior that uses values incorrectly. Some claim that "dynamic typing" is a misnomer for this reason. However, in many dynamically typed, object-oriented languages, a type is more of an interface and as long as classes share common interfaces, one does not care of what class the object is. In any case, the two should not be confused.

Further reading


- Benjamin Pierce, Types and Programming Languages, MIT Press, 2002. (ISBN 0-262-16209-1)
- Glynn Winskel: The Formal Semantics of Programming Languages, An Introduction, The MIT Press 1993 (ISBN 0-262-23169-7)
- Luca Cardelli, "Type Systems," The Computer Science and Engineering Handbook, Allen B. Tucker (Ed.), chapter 103, pp. 2208-2236, CRC Press, Boca Raton, FL, 1997. [http://citeseer.ist.psu.edu/cardelli97type.html (online)]

See also


- Intuitionistic type theory
- Duck typing

External links


- [http://www.nist.gov/dads/HTML/abstractDataType.html Abstract data type]
- [http://www.cs.ucsd.edu/users/goguen/ps/beatcs-adj.ps.gz A summary paper on the formal basis of ADTs, relationship to category theory, and list of good references]. Pages 3-4 appear relevant. Reference number [6] looks good, but it may not be available online.
- [http://www.nuprl.org/documents/Constable/NaiveTypeTheoryPreface.html Naïve Computational Type Theory] by Robert L. Constable Category:Mathematical logic Category:Logic in computer science
-

Measure theory

In mathematics, a measure is a function that assigns a number, e.g., a "size", "volume", or "probability", to subsets of a given set. The concept has developed in connection with a desire to carry out integration over arbitrary sets rather than on an interval as traditionally done, and is important in mathematical analysis and probability theory. Measure theory is that branch of real analysis which investigates σ-algebras, measures, measurable functions and integrals. It is of importance in probability and statistics. See also Lebesgue integration, Lebesgue measure.

Formal definitions

Formally, a countably additive measure μ is a function defined on a σ-algebra Σ over a set X with values in the extended interval [0, ∞] such that the following properties are satisfied:
- The empty set has measure zero: :: \mu(\varnothing) = 0;
- Countable additivity or σ-additivity: if E1, E2, E3, ... is a countable sequence of pairwise disjoint sets in Σ, ::\mu\left(\bigcup_^\infty E_i\right) = \sum_^\infty \mu(E_i). The members of Σ are called measurable sets and the triple (X,Σ,μ) is called a measure space. The following properties can be derived from the definition above:
- Monotonicity: If E1 and E2 are measurable sets :: E_1 \subseteq E_2 \mbox \mu(E_1) \leq \mu(E_2);\,\!
- If E1, E2, E3, ... is a countable sequence of sets in Σ, then ::\mu\left( \bigcup_^\infty E_i\right) \le \sum_^\infty \mu(E_i);
- If E1, E2, E3, ... are measurable sets and En is a subset of En+1 for all n, then the union of the sets En is measurable, and :: \mu\left(\bigcup_^\infty E_i\right) = \lim_ \mu(E_i);
- If E1, E2, E3, ... are measurable sets and En+1 is a subset of En for all n, then the intersection of the sets En is measurable; furthermore, if at least one of the En has finite measure, then :: \mu\left(\bigcap_^\infty E_i\right) = \lim_ \mu(E_i). Note that the preceding property is false without the assumption that at least one of the En has finite measure. For instance, for each n ∈ N, let :: E_n = [n, \infty) \subseteq \mathbb which all have infinite measure, but the intersection is empty.

Sigma-finite measures

A measure space (X,Σ,μ) is called finite if μ(X) is a finite real number (rather than ∞). It is called σ-finite if X is the countable union of measurable sets of finite measure. A set in a measure space has σ-finite measure if it is a union of sets with finite measure. For example, the real numbers with the standard Lebesgue measure are σ-finite but not finite. Consider the closed intervals [k,k+1] for all integers k; there are countably many such intervals, each has measure 1, and their union is the entire real line. Alternatively, consider the real numbers with the counting measure, which assigns to each finite set of reals the number of points in the set. This measure space is not σ-finite, because every set with finite measure contains only finitely many points, and it would take uncountably many such sets to cover the entire real line. The σ-finite measure spaces have some very convenient properties; σ-finiteness can be compared in this respect to separability of topological spaces.

Completeness

A measurable set X is called a null-set if μ(X) = 0. The measure μ is called complete if every subset of a null-set is measurable (and then automatically itself a null-set). A measure can be extended to a complete one by considering the σ-algebra of subsets Y which differ by a subset of a null set from a measurable set X, that is such that the symmetric difference of X and Y is contained in a null-set. One defines μ(Y) to equal μ (X).

Examples

Some important measures are listed here.
- The counting measure is defined by μ(X) = number of elements in X.
- The Lebesgue measure is the unique complete translation-invariant measure on a σ-algebra containing the intervals in R such that μ([0,1]) = 1.
- Circular angle measure is invariant under rotation.
- The Haar measure for a locally compact topological group is a generalization of the Lebesgue measure and has a similar uniqueness property.
- The zero measure is defined by μ(X) = 0 for all X.
- Every probability space gives rise to a measure which takes the value 1 on the whole space (and therefore takes all its values in the unit interval [0,1]). Such a measure is called a probability measure. See probability axioms. Other measures include: Borel measure, Ergodic measure, Euler measure, Gauss measure, Jordan measure.

Generalizations

For certain purposes, it is useful to have a "measure" whose values are not restricted to the non-negative reals or infinity. For instance, a countably additive set function with values in the (signed) real numbers is called a signed measure, while such a function with values in the complex numbers is called a complex measure. A measure that takes values in a Banach space is called a spectral measure; these are used mainly in functional analysis for the spectral theorem. To distinguish the usual positive-valued measure from generalizations, we speak of "positive measures". Another generalization is the finitely additive measure. This is the same as a measure except that instead of requiring countable additivity we require only finite additivity. Historically, this definition was used first, but proved to be not so useful. It turns out that in general, finitely additive measures are connected with notions such as Banach limits, the dual of L∞ and the Stone-Čech compactification. All these are linked in one way or another to the axiom of choice. The remarkable result in integral geometry known as Hadwiger's theorem states that the space of translation-invariant, finitely additive, not-necessarily-nonnegative set functions defined on finite unions of compact convex sets in Rn consists (up to scalar multiples) of one "measure" that is "homogeneous of degree k" for each k=0,1,2,...,n, and linear combinations of those "measures". "Homogeneous of degree k" means that rescaling any set by any factor c>0 multiplies the set's "measure" by ck. The one that is homogeneous of degree n is the ordinary n-dimensional volume. The one that is homogeneous of degree n-1 is the "surface volume". The one that is homogeneous of degree 1 is a mysterious function called the "mean width", a misnomer. The one that is homogenous of degree 0 is the Euler characteristic.

See also


- Outer measure
- Hausdorff measure
- product measure
- almost everywhere

References


- P. Halmos, Measure theory, D. van Nostrand and Co., 1950
- M. E. Munroe, Introduction to Measure and Integration, Addison Wesley, 1953
- R. M. Dudley, Real Analysis and Probability, Cambridge University Press, 2002
- D. H. Fremlin, Measure Theory, Torres Fremlin, 2000. Available online at http://www.essex.ac.uk/maths/staff/fremlin/mt.htm
- ja:測度論



Geometry

Geometry (Greek γεωμετρία; geo = earth, metria = measure) arose as the field of knowledge dealing with spatial relationships. It was one of the two fields of pre-modern mathematics, the other being the study of numbers. In modern times, geometric concepts have been generalized to a high level of abstraction and complexity, and have been subjected to the methods of calculus and abstract algebra, so that many modern branches of the field are barely recognizable as the descendants of early geometry. (See areas of mathematics and algebraic geometry.)

The earliest geometry

The earliest recorded beginnings of geometry may be traced to Ancient Egypt (see geometry in Egypt) and Ancient Babylon (see Babylonian mathematics) around 3000 B.C. Early geometry was a collection of empirically discovered principles concerning lengths, angles, areas, and volumes, which were developed to meet some practical need in surveying, construction, astronomy, and various crafts. Among these were some surprisingly sophisticated principles, and a modern mathematician might be hard put to derive some of them without the use of calculus. For example, both the Egyptians and the Babylonians were aware of versions of the Pythagorean theorem about 1500 years before Pythagoras; the Egyptians had a correct formula for the volume of a frustum of a square pyramid; the Babylonians had a trigonometry table. Chinese culture at this same time period was equally advanced, so it is likely that they had an equally advanced mathematics, but no artifacts have survived from which we could learn about it. This may be partly due to their early use of paper, rather than clay tablets or stone, to record their achievements.

The Greek period (c. 600 B.C. – 600 A.D.)

The Greek Period must be considered in detail, since geometry, for most of its history, was what the Greeks made it. For the Ancient Greeks, geometry was the crown jewel of their sciences, reaching a completeness and perfection of methodology that no other branch of their knowledge had attained. They expanded the range of geometry to many new kinds of figures, curves, surfaces, and solids; they changed its methodology from trial-and-error to logical deduction; they recognized that geometry studies “eternal forms”, or abstractions, of which physical objects are only approximations; and they developed the idea of an “axiomatic theory”, which, for more than 2000 years, was regarded to be the ideal paradigm for all scientific theories.

Thales and Pythagoras

Thales (635-543 B.C.) of Ionia (now southwestern Turkey), was the first to whom deduction in mathematics is attributed. There are five geometric propositions for which he wrote deductive proofs, though his proofs have not survived. Pythagoras (582-496 B.C.) of Ionia, and later, Italy, then colonized by Greeks, may have been a student of Thales, and probably traveled to Babylon and Egypt. The theorem that bears his name was not his discovery, but he was the first to give a deductive proof of it. He gathered a group of students around him to study mathematics, music, and philosophy, and together they discovered most of what high school students learn today in their geometry courses. In addition, they made the profound discovery of incommensurable lengths and irrational numbers.

Plato

Plato (427-347 B.C.), the philosopher most esteemed by the Greeks, had inscribed above the entrance to his famous school, “Let none enter here who are ignorant of geometry.” Though he was not a mathematician himself, his views on mathematics had great influence. Mathematicians thus accepted his belief that geometry should use no tools but a compass and straight edge – never measuring instruments such as a marked ruler or a protractor, because these were a workman’s tools, not worthy of a scholar. This dictum led to a deep study of the possible ruler and compass constructions, and three classic ruler-and-compass problems: how to use these tools to trisect an angle, to construct a cube twice the volume of a given cube, and to construct a square equal in area to a given circle. The proofs of the impossibility of these constructions, finally achieved in the 19th century, led to important principles regarding the deep structure of the real number system. Aristotle (384-322 B.C.), Plato’s greatest pupil, wrote a treatise on methods of reasoning used in deductive proofs (see Logic) which was not substantially improved upon until the 19th century.

Euclid

Euclid (365?-275? B.C.), probably a student of one of Plato’s students, wrote a treatise in 13 books (chapters), titled The Elements of Geometry, in which he presented geometry in the ideal axiomatic form. The treatise is not a compendium of all that the Greeks knew at the time about geometry; Euclid himself wrote eight more advanced books on geometry. We know from other references that Euclid’s was not the first elementary geometry textbook, but it was so much superior that the others fell into disuse and were lost. He was brought to the university at Alexandria by Ptolemy I, King of Egypt. The Elements began with definitions of terms, fundamental geometric principles (called axioms or postulates), and general quantitative principles (called common notions) from which all the rest of geometry could be logically deduced. Following are his five axioms, somewhat paraphrased to make the English easier to read. # Any two points can be joined by a straight line. # Any finite straight line can be extended in a straight line. # A circle can be drawn with any center and any radius. # All right angles are equal to each other. # If two straight lines in a plane are crossed by another straight line (called the transversal), and the interior angles between the two lines and the transversal lying on one side of the transversal add up to less than two right angles, then on that side of the transversal, the two lines extended will intersect (also called the parallel postulate). It was soon observed, and no doubt Euclid himself knew, that his fifth axiom could be replaced by the shorter statement “Given a line and a point not on the line, there is only one line through the given point and in the same plane with the given line that does not intersect the given line.” This is called Playfair’s Axiom, after the British teacher who proposed to make the replacement in all the school textbooks. The axioms, according to Plato, should be simple and self-evident principles, so clearly true that they need no proof. Euclid’s first four axioms meet this criterion, but the fifth, even if replaced by Playfair’s Axiom, is not simple, and most would say not self-evident like the first four. The fifth resembled more the theorems that Euclid proved from the axioms. Furthermore, Euclid developed a substantial part of his theory of triangles without using the Fifth Axiom. The speculation arose, probably during Euclid’s lifetime, that the Fifth Axiom can and should be proved as a theorem from the first four, and thus is unnecessary as an axiom. Thus began many centuries of attempts to prove the Fifth Axiom, and the question was not settled until the 19th century.

Archimedes

Archimedes (287-212 B.C.), of Syracuse, Sicily, when it was a Greek city-state, was the greatest of the Greek mathematicians, and often named as one of the three greatest of all time (along with Isaac Newton and Carl Friedrich Gauss). Had he not been a mathematician, he would still be remembered as a great physicist, engineer, and inventor. In his mathematics, he developed methods very similar to the coordinate systems of analytic geometry, and the limiting process of integral calculus. The only element lacking for the creation of these fields was an efficient algebraic notation in which to express his concepts.

After Archimedes

After Archimedes, Greek mathematics began to decline. There were a few minor stars yet to come, but the golden age of geometry was over. Proclus (410-485), author of Commentary on the First Book of Euclid, was one of the last important players in Greek geometry. He was a competent geometer, but more importantly, he was a superb commentator on the works that preceded him. Much of that work did not survive to modern times, and is known to us only through his commentary. The Roman Republic and Empire that succeeded and absorbed the Greek city-states produced excellent engineers, but no mathematicians of note.

The Middle Ages, Renaissance, and Reformation

The great library of Alexandria was burned. There is a growing consensus among historians that the Library of Alexandria likely suffered from several destructive events, but that the destruction of Alexandria's pagan temples in the late 4th century was probably the most severe and final one. The evidence for that destruction is the most definitive and secure. Caesar's invasion may well have led to the loss of some 40,000-70,000 scrolls in a warehouse adjacent to the port (as Luciano Canfora argues, they were likely copies produced by the Library intended for export), but it is unlikely to have affected the Library or Museum, given that there is ample evidence that both existed later. Civil wars, decreasing investments in maintenance and acquisition of new scrolls and generally declining interest in non-religious pursuits likely contributed to a reduction in the body of material available in the Library, especially in the fourth century. The Serapeum was certainly destroyed by Theophilus in 391, and the Museum and Library may have fallen victim to the same campaign. The Islamic ascendency in the Middle East, north Africa, and Spain began about 640 A.D. Original Arab mathematics during this period was primarily algebraic rather than geometric, though there were important commentaries on geometry. Omar Khayyám, for example, was a geometer as well as a poet. Scholarship in Europe declined until even the great works of antiquity were lost to them, and survived only in the Islamic centers of learning. When Europe started to emerge from the intellectual darkness of the Middle Ages, the writers of Ancient Greece and Rome were rediscovered in Islamic libraries and translated from Arabic into Latin. Euclid’s Elements of Geometry was recovered, and the rigorous deductive methods of geometry were relearned. Development of geometry in the style of Euclid resumed, resulting in an abundance of new theorems and concepts, many of them very profound and elegant.

The 17th and early 18th centuries

In the early 17th century, there were two important developments in geometry. The first and most important was the creation of analytic geometry, or geometry with coordinates and equations, by Rene Descartes (1596-1650) and Pierre de Fermat (1601-1665). This was a necessary precursor to the development of calculus and a precise quantitative science of physics. The second geometric development of this period was the systematic study of projective geometry by Girard Desargues (1591-1661). Projective geometry is the study of geometry without measurement, just the study of how points align with each other. There had been some early work in this area by Greek geometers, notably Pappus (c. 340). The greatest flowering of the field occurred with Jean-Victor Poncelet (1788-1867). In the late 17th century, calculus was developed independently and almost simultaneously by Isaac Newton (1642-1727) and Gottfried Wilhelm von Leibniz (1646-1716). This was the beginning of a new field of mathematics now called analysis. Though not itself a branch of geometry, it is applicable to geometry, and it solved two families of problems that had long been almost intractable: finding tangent lines to odd curves, and finding areas enclosed by those curves. The methods of calculus reduced these problems mostly to straightforward matters of computation.

The late 18th and 19th centuries

Non-Euclidean geometry

The old problem of proving Euclid’s Fifth Postulate, the "Parallel Postulate", from his first four postulates had never been forgotten. Beginning not long after Euclid, many attempted demonstrations were given, but all were later found to be faulty, through allowing into the reasoning some principle which itself had not been proved from the first four postulates. By 1700 a great deal had been discovered about what can be proved from the first four, and what the pitfalls were in attempting to prove the fifth. Saccheri, Lambert, and Legendre each did excellent work on the problem in the 18th century, but still fell short of success. In the early 19th century, Gauss, Johann Bolyai, and Lobatchewsky, each independently, took a different approach. Beginning to suspect that it was impossible to prove the Parallel Postulate, they set out to develop a self-consistent geometry in which that postulate was false. In this they were successful, thus creating the first non-Euclidean geometry. By 1854, Bernhard Riemann, a student of Gauss, had applied methods of calculus in a ground-breaking study of the intrinsic (self-contained) geometry of all smooth surfaces, and thereby found a different non-Euclidean geometry. This work of Riemann later became fundamental for Einstein's theory of relativity. It remained to prove mathematically that the non-Euclidean geometry was just as self-consistent as Euclidean geometry, and this was first accomplished by Beltrami in 1868. With this, non-Euclidean geometry was established on an equal mathematical footing with Euclidean geometry. While it was now known that different geometric theories were mathematically possible, the question remained, "Which one of these theories is correct for our physical space?" The mathematical work revealed that this question must be answered by physical experimentation, not mathematical reasoning, and uncovered the reason why the experimentation must involve immense (interstellar, not earth-bound) distances. With the development of relativity theory in physics, this question became vastly more complicated.

Introduction of mathematical rigor

All the work related to the Parallel Postulate revealed that it was quite difficult for a geometer to separate his logical reasoning from his intuitive understanding of physical space, and, moreover, revealed the critical importance of doing so. Careful examination had uncovered some logical inadequacies in Euclid's reasoning, and some unstated geometric principles to which Euclid sometimes appealed. This critique paralleled the crisis occurring in calculus and analysis regarding the meaning of infinite processes such as convergence and continuity. In geometry, there was a clear need for a new set of axioms, which would be complete, and which in no way relied on pictures we draw or on our intuition of space. Such axioms were given by David Hilbert in 1894 in his dissertation Grundlagen der Geometrie (Foundations of Geometry). Some other complete sets of axioms had been given a few years earlier, but did not match Hilbert's in economy, elegance, and similarity to Euclid's axioms.

Analysis situs, or topology

In the mid-18th century, it became apparent that certain progressions of mathematical reasoning recurred when similar ideas were studied on the number line, in two dimensions, and in three dimensions. Thus the general concept of a metric space was created so that the reasoning could be done in more generality, and then applied to special cases. This method of studying calculus- and analysis-related concepts came to be known as analysis situs, and later as topology. The important topics in this field were properties of more general figures, such as connectedness and boundaries, rather than properties like straightness, and precise equality of length and angle measurements, which had been the focus of Euclidean and non-Euclidean geometry. Topology soon became a separate field of major importance, rather than a sub-field of geometry or analysis.

The 20th century

See also


- List of geometry topics
- Important publications in geometry.

External links


- [http://www.cut-the-knot.org/WhatIs/WhatIsGeometry.shtml What Is Geometry?] at cut-the-knot
- [http://www.elvenkids.com/tools/geometria/Geometria.php Geometria] An online tool to compute lines, surfaces and volumes of the main plane and solid figures, through direct and indirect formulas.
- [http://www.geogebra.at/ Geogebra] A free dynamic geometry tool, useful for exploring geometry.
- [http://agutie.homestead.com Geometry Step by Step from the Land of the Incas] by Antonio Gutierrez.
- [http://www.cut-the-knot.org/geometry.shtml Geometry] at cut-the-knot
- [http://www.islamicarchitecture.org/art/islamic-geometry-and-floral-patterns.html Islamic Geometry]
- Stanford Encyclopedia of Philosophy:
  - [http://plato.stanford.edu/entries/geometry-finitism/ Finitism in Geometry]
  - [http://plato.stanford.edu/entries/geometry-19th/ Geometry in the 19th Century]
- [http://www.egwald.com/geometry/index.php Online Interactive Geometric Objects] by Elmer G. Wiens Category:Geometry ko:기하학 ja:幾何学 simple:Geometry zh-min-nan:Kí-hô-ha̍k

Order theory

Order theory is a branch of mathematics that studies various kinds of binary relations that capture the intuitive notion of a mathematical ordering. This article gives a detailed introduction to the field and includes some of the most basic definitions. For a quick lookup of order theoretic terms, there is also an order theory glossary. A list of order topics collects the various articles that exist in the vicinity of order theory.

Background and motivation

Orders appear everywhere - at least as far as mathematics and related areas, such as computer science, are concerned. The first order that one typically meets in primary school mathematical education is the order ≤ of natural numbers. This intuitive concept is easily extended to orderings of other sets of numbers, such as the integers and the reals. Indeed the idea of being greater or smaller than another number is one of the basic intuitions of number systems in general (although one usually is also interested in the actual difference of two numbers, which is not given by the order). Another familiar example of an ordering is the lexicographic order of words in a dictionary. The above types of orders have a special property: each element can be compared to any other element, i.e. it is either greater, smaller, or equal. However, this is not always a desired requirement. A well-known example is the subset ordering of sets. If a set A contains all the elements of a set B, then B is said to be smaller than or equal to A. Yet there are sets that cannot be compared in this fashion since each of them contains some elements that are not present in the other. Hence, subset-inclusion is a partial order, as opposed to the total orders given before. Order theory captures the intuition of orders that arises from such examples in a general setting. This is achieved by specifying properties that a relation ≤ must have to be a mathematical order. This more abstract approach makes much sense, because one can derive numerous theorems in the general setting, without focusing on the details of any particular order. These insights can then be readily transferred to many concrete applications. Driven by the wide practical usage of orders, numerous special kinds of ordered sets have been defined, some of which have grown to mathematical fields of their own. In addition, order theory does not restrict to the various classes of ordering relations, but also considers appropriate functions between them. A simple example of an order theoretic property for functions comes from analysis where monotone functions are found frequently.

Introduction to the basic definitions

This section aims at giving a first guide to the realm of ordered sets. It addresses readers who have basic knowledge of set theory and arithmetics and who know what a binary relation is, but who are not familiar with order theoretic considerations so far.

Partially ordered sets

As already hinted at above, orders are special binary relations. Hence consider some set P and a relation ≤ on P. Then ≤ is a partial order if it is reflexive, antisymmetric, and transitive, i.e., for all a, b and c in P, we have that: :a ≤ a (reflexivity) : if a ≤ b and b ≤ a then a = b (antisymmetry) : if a ≤ b and b ≤ c then a ≤ c (transitivity) A set with a partial order on it is called a partially ordered set, poset, or just an ordered set if the intended meaning is clear. By checking these properties, one immediately sees that the well-known orders on natural numbers, integers, rational numbers and reals are all orders in the above sense. However, they have the additional property of being total, i.e., for all distinct a and b in P, we have that: :a ≤ b or b ≤ a (totality) These orders can also be called linear orders or chains. While many classical orders are linear, the subset order on sets provides an example where this is not the case. In fact, many advanced properties of posets are mainly interesting for non-linear orders.

Visualizing orders

Before proceeding to further examples and definitions, it will be helpful to display orders in a convenient graphical way, in order to provide "pictures" that one can have in mind (or on paper) when trying to understand the more abstract concepts. For this purpose, so-called Hasse diagrams have been introduced. These are graphs where the vertices are the elements of the poset and the ordering relation is indicated by both the edges and the relative positioning of the vertices. Orders are drawn bottom-up: if an element x is smaller than y then there exists a path from x to y that is directed upwards. It is often needed that connections between points intersect each other, but points must never be located at the direct connection between two other points. Even infinite sets can sometimes be illustrated by similar diagrams, using an ellipsis (...) after drawing a sufficiently instructive finite sub-order. This works well for the natural numbers, but it fails for the reals, where there is no immediate successor above 0. However, quite often one can obtain an intuition related to diagrams of a similar kind. The above orders are all very common in mathematics. However, there are also examples that one does often not consider as orders. For instance, the identity relation = on any set is a partial order. Within this order, every two elements are incomparable. It is also the only relation that is both a partial order and an equivalence relation. The Hasse diagram of such a discrete order is just a collection of labeled points, without any edges between them. Another example is given by the divisibility relation "|". For two natural numbers n and m, we write n|m if n divides m without rest. One easily sees that this really yields a partial order. An instructive exercise is to draw the Hasse diagram for the set of natural numbers that are smaller than or equal to 13, ordered by |.

Special elements within an order

In a partially ordered set there are some elements that play a special role. The most basic example is given by the least element of a poset. For example, 1 is the least element of the positive integers and the empty set is the least set under the subset order. Formally, an element m is a least element if: : m ≤ a, for all elements a of the order. The notation 0 is frequently found for the least element, even when no numbers are concerned. However, in orders on sets of numbers, this notation might be inappropriate or ambiguous, since the number 0 is not always least. An example is given by the above divisibility order |, where 1 is the least element since it divides all other numbers. On the other hand, 0 is the number that is divided by all other numbers. Hence it is the greatest element of the order! Other frequent terms for the least and greatest elements is bottom and top or zero and unit. Least and greatest elements may fail to exist, as the example of the real numbers shows. On the other hand, if they exist, least and greatest elements are always unique. In contrast, consider the divisibility relation | on the set . Although this set has neither top nor bottom, the elements 2, 3, and 5 do not have any elements below them, while 4, 5, and 6 have no other number above. Such elements are called minimal and maximal, respectively. Formally, an element m is minimal if: : a ≤ m implies a = m, for all elements a of the order. Exchanging ≤ with ≥ yields the definition of maximality. As the example shows, there can be many maximal elements and some elements may be both maximal and minimal (e.g. 5 above). However, if there is a least element, then it is the only minimal element of the order. Again, in infinite posets maximal elements do not always exist - the set of all finite subsets of a given infinite set, ordered by subset inclusion, provides one out of many counterexamples. An important tool to ensure the existence of maximal elements under certain conditions is Zorn's Lemma. Subsets of partially ordered sets inherit the order. We already applied this by considering the subset of the natural numbers with the induced divisibility ordering. Now there are also elements of a poset that are special with respect to some subset of the order. This leads to the definition of upper bounds. Given a subset S of some poset P, an upper bound of S is an element b of P that is above all elements of S. Formally, this means that : s ≤ b, for all s in S. Lower bounds again are defined by inverting the order. For example, -5 is a lower bound of the natural numbers as a subset of the integers. Given a set of sets, an upper bound for these sets under the subset ordering is given by their union. In fact, this upper bound is quite special: it is the smallest set that contains all of the sets. Hence, we have found the least upper bound of a set of sets. This concept is also called supremum or join, and for a set S one writes sup(S) or vS for its least upper bound. Conversely, the greatest lower bound is known as infimum or meet and denoted inf(S) or ^S. These concepts play an important role in many applications of order theory. For two elements x and y, one also writes x v y and x ^ y for sup() and inf(), respectively. (Using Wikipedia's TeX markup, one can also write \vee and \wedge, as well as the larger symbols \bigvee and \bigwedge. Note however, that all of these symbols may fail to match the font size of the standard text and should therefore preferably be used in extra lines. The rendering of ∨ for v and ∧ for ^ is not supported by many of today's web browsers across all platforms and therefore avoided here.) For another example, consider again the relation | on natural numbers. The least upper bound of two numbers is the smallest number that is divided by both of them, i.e. the least common multiple of the numbers. Greatest lower bounds in turn are given by the greatest common divisor.

Duality

In the previous definitions, we often noted that a concept can be defined by just inverting the ordering in a former definition. This is the case for "least" and "greatest", for "minimal" and "maximal", for "upper bound" and "lower bound", and so on. This is a general situation in order theory: A given order can be inverted by just exchanging its direction, pictorially flipping the Hasse diagram top-down. This yields the so-called dual, inverse, or opposite order. Every order theoretic definition has its dual: it is the notion one obtains by applying the definition to the inverse order. Since the symmetry of all concepts, this operation preserves the theorems of partial orders. For a given mathematical result, one can just invert the order and replace all definitions by their duals and one obtains another valid theorem. This is important and useful, since one obtains two theorems for the price of one. Some more details and examples can be found in the article on duality in order theory.

Constructing new orders

There are multiple ways to construct orders, or to combine given orders to a new one. The dual order is a first example. Another major construction is the cartesian product of two partially ordered sets, together with the product order on pairs of elements. This is defined from the original orders by setting (a, x) ≤ (b, y) if a ≤ b and x ≤ y. The disjoint union of two posets is a further typical construction, where the order is just the union of the original orders. As in the case of the common order of numbers, every partial order ≤ gives rise to a strict order <, by defining a < b if a ≤ b and not b ≤ a. This transformation can be inverted by setting a ≤ b if a < b or a = b.

Functions between orders

It is reasonable to consider functions between partially ordered sets having certain additional properties, that are related to the ordering relations of the two sets. The most fundamental condition that occurs in this context is monotonicity. A function f from a poset P to a poset Q is monotone, or order-preserving, if a ≤ b in P implies f(a) ≤ f(b) in Q (Noting that, strictly, the two relations here are different since they apply to different sets.). The converse of this implication leads to functions that are order-reflecting, i.e. functions f as above for which f(a) ≤ f(b) implies a ≤ b. On the other hand, a function may also be order-reversing or antitone, if a ≤ b implies f(a) ≥ f(b). An order-embedding is a function f between orders that is both order-preserving and order-reflecting. Examples for these definitions are found easily. For instance, the function that maps a natural number to its successor is clearly monotone with respect to the natural order. Any function from a discrete order, i.e. from a set ordered by the identity order "=", is also monotone. Mapping each natural number to the corresponding real number gives an example for an order embedding. The set complement on a powerset is an example of an antitone function. An important question is when two orders are "essentially equal", i.e. when they are the same up to renaming of elements. Order isomorphisms are functions that define such a renaming. An order-isomorphism is a monotone bijective function that has a monotone inverse. This is equivalent to being a surjective order-embedding. Hence, the image f(P) of an order-embedding is always isomorphic to P, which justifies the term "embedding". A more elaborate type of functions is given by so-called Galois connections. Monotone Galois connections can be viewed as a generalization of order-isomorphisms, since they constitute of a pair of two functions in converse directions, which are "not quite" inverse to each other, but that still have close relationships. Another special type of self-maps on a poset are closure operators, which are not only monotonic, but also idempotent, i.e. f(x) = f(f(x)), and extensive (or inflationary), i.e. x ≤ f(x). These have many applications in all kinds of "closures" that appear in mathematics. Besides being compatible with the mere order relations, functions between posets may also behave well with respect to special elements and constructions. For example, when talking about posets with least element, it may seem reasonable to consider only monotonic functions that preserve this element, i.e. which map least elements to least elements. If binary infima ^ exist, then a reasonable property might be to require that f(x^y) = f(x)^f(y), for all x and y. All of these properties, and indeed many more, may be compiled under the label of limit-preserving functions. Finally, one can invert the view, switching from functions of orders to orders of functions. Indeed, the functions between two posets P and Q can be ordered via the pointwise order. For two functions f and g, we have f ≤ g if f(x) ≤ g(x) for all elements x of P. This occurs for example in domain theory, where function spaces play an important role.

Special types of orders

Many of the structures that are studied in order theory employ order relations with further properties. In fact, even some relations that are not partial orders are of special interest. Mainly the concept of a preorder has to be mentioned. A preorder is a relation that is reflexive and transitive, but not necessarily antisymmetric. Each preorder induces an equivalence relation between elements, where a is equivalent to b, if a ≤ b and a ≥ b. Preorders can be turned into orders by identifying all elements that are equivalent with respect to this relation. Basic types of special orders have already been given in form of total orders. An additional simple but useful property leads to so-called well-orders, within which all non-empty subsets have a least element, or equivalently in which there is no infinite descending sequence of distinct elements. For partial orders, a similar definition leads to well partial orders, where in addition to having no infinite descending chains there are no infinite antichains. Many other types of orders arise when the existence of infima and suprema of certain sets is guaranteed. Focusing on this aspect, usually referred to as completeness of orders, one obtains:
- Bounded posets, i.e. posets with a least and greatest element (which are just the supremum and infimum of the empty subset),
- Lattices, in which every non-empty finite set has a supremum and infimum,
- Complete lattices, where every set has a supremum and infimum, and
- Directed complete partial orders (dcpos), that guarantee the existence of suprema of all directed subsets and that are studied in domain theory. However, one can go even further: if all finite non-empty infima exist, then ^ can be viewed as a total binary operation in the sense of universal algebra. Hence, in a lattice, two operations ^ and v are available, and one can define new properties by giving identities, such as : x ^ (y v z)  =  (x ^ y) v (x ^ z), for all x, y, and z. This condition is called distributivity and gives rise to distributive lattices. There are some other important distributivity laws which are discussed in the article on distributivity in order theory. Some additional order structures that are often specified via algebraic operations and defining identities are
- Heyting algebras and
- Boolean algebras, which both introduce a new operation ~ called negation. Both structures play a role in mathematical logic and especially Boolean algebras have major applications in computer science. Finally, various structures in mathematics combine orders with even more algebraic operations, as in the case of quantales, that allow for the definition of an addition operation. Many other important properties of posets exist. For example, a poset is locally finite if every closed interval [a, b] in it is finite. Locally finite posets give rise to incidence algebras which in turn can be used to define the Euler characteristic of finite bounded posets.

Subsets of ordered sets

In an ordered set, one can define many types of special subsets based on the given order. A simple example are upper sets; i.e. sets that contain all elements that are above them in the order. Formally, the upper closure of a set S in a poset P is given by the set . A set that is equal to its upper closure is called an upper set. Lower sets are defined dually. More complicated lower subsets are ideals, which have the additional property that each two of their elements have an upper bound within the ideal. Their duals are given by filters. A related concept is that of a directed subset, which like an ideal contains upper bounds of finite subsets, but does not have to be a lower set. Furthermore it is often generalized to preordered sets. A subset which is - as a sub-poset - linearly ordered, is called a chain. The opposite notion, the antichain, is a subset that contains no two comparable elements; i.e. that is a discrete order.

Related mathematical areas

Although most mathematical areas use orders in one or the other way, there are also a few theories that have relationships which go far beyond mere application. Together with their major touching points with order theory, some of these are to be presented below.

Universal algebra

As already mentioned, the methods and formalisms of universal algebra are an important tool for many order theoretic considerations. Beside formalizing orders in terms of algebraic structures that satisfy certain identities, one can also establish other connections to algebra. An example is given by the correspondence between Boolean algebras and Boolean rings. Other issues are concerned with the existence of free constructions, such as free lattices based on a given set of generators. Furthermore, closure operators are important in the study of universal algebra.

Topology

In topology orders play a very prominent role. In fact, the set of open sets provides a classical example of a complete lattice, more precisely a complete Heyting algebra (or "frame" or "locale"). Filters and nets are notions closely related to order theory and the closure operator of sets can be used to define topology. Beyond these relations, topology can be looked at solely in terms of the open set lattices, which leads to the study of pointless topology. Furthermore, a natural preorder of elements of the underlying set of a topology is given by the so-called specialization order, that is actually a partial order if the topology is T0. Conversely, in order theory, one often makes use of topological results. There are various ways to define subsets of an order which can be considered as open sets of a topology. Especially, it is interesting to consider topologies on a poset (X, ≤) that in turn induce ≤ as their specialization order. The finest such topology is the Alexandrov topology, given by taking all upper sets as opens. Conversely, the coarsest topology that induces the specialization order is the upper topology, having the complements of principal ideals (i.e. sets of the form for some x) as a subbase. Additionally, a topology with specialization order ≤ may be order consistent, meaning that their open sets are "inaccessible by directed suprema" (with respect to ≤). The finest order consistent topology is the Scott topology, which is coarser than the Alexandrov topology. A third important topology in this spirit is the Lawson topology. There are close connections between these topologies and the concepts of order theory. For example, a function preserves directed suprema iff it is continuous with respect to the Scott topology (for this reason this order theoretic property is also called Scott-continuity).

Category theory

The visualization of orders with Hasse diagrams has a straightforward generalization: instead of displaying lesser elements below greater ones, the direction of the order can also be depicted by giving directions to the edges of a graph. In this way, each order is seen to be equivalent to a directed acyclic graph, where the nodes are the elements of the poset and there is a directed path from a to b if and only if a ≤ b. Dropping the requirement of being acyclic, one can also obtain all preorders. When equipped with all transitive edges, these graphs in turn are just special categories, where elements are objects and each set of morphisms between two elements is at most singleton. Functions between orders become functors between categories. Interestingly, many ideas of order theory are just concepts of category theory in small. For example, an infimum is just a categorical product. More generally, one can capture suprema and infima under the abstract notion of a categorical limit (or colimit, respectively). Another place where categorical ideas occur is the concept of a (monotone) Galois connection, which is just the same as a pair of adjoint functors. But category theory also has its impact on order theory on a larger scale. Classes of posets with appropriate functions as discussed above form interesting categories. Often one can also state constructions of orders, like the product order, in terms of categories. Further insights result when categories of orders are found categorically equivalent to other categories, for example of topological spaces. This line of research leads to various representation theorems, often collected under the label of Stone duality.

History

As explained before, orders are ubiquitous in mathematics. However, earliest explicit mentionings of partial orders are probably to be found not before the 19th century. In this context the works of George Boole are of great importance. Moreover, works of Charles S. Peirce, Richard Dedekind, and Ernst Schröder also consider concepts of order theory. Certainly, there are others to be named in this context and surely there exists more detailed material on the history of order theory. Please contribute if any further knowledge is available to you. The term poset as an abbreviation for partially ordered set was coined by Garrett Birkhoff, a fact that, according to [http://members.aol.com/jeff570/mathword.html Earliest Known Uses of Some of the Words of Mathematics], is stated on page 1 of the second edition of his influential book Lattice Theory (Amer. Math. Soc. Coll. Publ., vol. 25, New York, 1948).

See also

List of order topics, Incidence algebra, Möbius function, total order, total preorder, partial order, cyclic order and Important publications in order theory.

Literature


- B. A. Davey and H. A. Priestley, Introduction to Lattices and Order, 2nd edition, Cambridge University Press, 2002. ISBN 0521784514 : Probably the most popular textbook introduction to the whole area. Suitable for undergraduate students.
- G. Gierz, K. H. Hofmann, K. Keimel, J. D. Lawson, M. Mislove, and D. S. Scott, Continuous Lattices and Domains, In Encyclopedia of Mathematics and its Applications, Vol. 93, Cambridge University Press, 2003. ISBN 0521803381 : The comprehensive new version of the famous "Compendium" (of continuous lattices). Some advanced mathematical background is assumed.
- S. N. Burris and H. P. Sankappanavar, [http://www.thoralf.uwaterloo.ca/htdocs/ualg.html A Course in Universal Algebra] :A free online textbook covering various topics, chiefly among them lattices.
-

Equivalence relation

In mathematics, an equivalence relation on a set X is a binary relation on X that is reflexive, symmetric and transitive, i.e., if the relation is written as ~ it holds for all a, b and c in X that # (Reflexivity) a ~ a # (Symmetry) if a ~ b then b ~ a # (Transitivity) if a ~ b and b ~ c then a ~ c A set together with an equivalence relation is called a setoid. Equivalence relations are often used to group together objects that are similar in some sense.

Examples of equivalence relations


- The equality ("=") relation between real numbers or sets.
- The relation "is congruent to (modulo 5)" between integers.
- The relation "is similar to" on the set of all triangles.
- The relation "has the same birthday as" on the set of all human beings.
- The relation of logical equivalence on statements in first-order logic.
- The relation "is isomorphic to" on models of a set of sentences.
- The relation "is in thermal equilibrium with".
- The relation "has the same image under a function" on the elements of the domain of the function.
- Green's relations are five equivalence relations on the elements of a semigroup.

Examples of relations that are not equivalences


- The relation "≥" between real numbers is not an equivalence relation, because although it is reflexive and transitive, it is not symmetric. E.g. 7 ≥ 5 does not imply that 5 ≥ 7. It is, however, a partial order relation.
- The relation "has a common factor greater than 1 with" between natural numbers greater than 1, is not an equivalence relation, because although it is reflexive and symmetric, it is not transitive (2 and 6 have a common factor greater than 1, and 6 and 3 have a common factor greater than 1, but 2 and 3 do not have a common factor greater than 1).
- The empty relation R on a non-empty set X (i.e. a R b is never true) is not an equivalence relation, because although it is vacuously symmetric and transitive, it is not reflexive (except when X is also empty).
- The relation "is approximately equal" between real numbers or other things, even if more precisely defined, is not an equivalence relation, because although it is reflexive and symmetric, it is not transitive (it may seem so at first sight, but many small changes can add up to a big change).
- The relation "is the mother of" on the set of all human beings is not an equivalence relation, because it not reflexive (A is not the mother of A), symmetric (If A is the mother of B, then B is not the mother of A), and is not transitive (if A is the mother of B, and B is the mother of C, it does not necessarily mean A is the mother of C)

Partitioning into equivalence classes

Every equivalence relation on X defines a partition of X into subsets called equivalence classes: all elements equivalent to each other are put into one class. Conversely, if the set X can be partitioned into subsets, then we can define an equivalence relation ~ on X by the rule "a ~ b if and only if a and b lie in the same subset". For example, if G is a group and H is a subgroup of G, then we can define an equivalence relation ~ on G by writing a ~ b if and only if ab-1 lies in H. The equivalence classes of this relation are the right cosets of H in G. Since every equivalence relation can be identified with a partition and vice versa, the number of equivalence relations on a set X of n elements is given by the nth Bell number, Bn. If an equivalence relation ~ on X is given, then the set of all its equivalence classes is the quotient set of X by ~ and is denoted by X/~.

Generating equivalence relations

If two equivalence relations over the set X are given, then their intersection (viewed as subsets of X×X) is also an equivalence relation. This allows for a convenient way of defining equivalence relations: given any binary relation R on X, the equivalence relation generated by R is the smallest equivalence relation containing R. Concretely, the equivalence relation ~ generated by R can be described as follows: a ~ b