Foundations of mathematics

79 345 subscribers already with us

Foundations of mathematics Topics

Sort by:

A proof by contradiction establishes the truth of a given proposition by the supposition that it is false and the subsequent drawing of a conclusion that is contradictory to something that is proven to be true. That is, the supposition that is false followed necessarily by the conclusion from not-, where is false, which implies that is true.For example, the second of Euclid's theorems starts with the assumption that there is a finite number of primes. Cusik gives some other nice examples.

Uniqueness theorem

A theorem, also called a unicity theorem, stating the uniqueness of a mathematical object, which usually means that there is only one object fulfilling given properties, or that all objects of a given class are equivalent (i.e., they can be represented by the same model). This is often expressed by saying that the object is uniquely determined by a certain set of data. The word unique is sometimes replaced by essentially unique, whenever one wants to stress that the uniqueness is only referred to the underlying structure, whereas the form may vary in all ways that do not affect the mathematical content.The object of many uniqueness theorems is the solution to a problem or an equation; in such cases, a uniqueness theorem is normally combined with an existence theorem.

Existence theorem

A theorem stating the existence of an object, such as the solution to a problem or equation. Strictly speaking, it need not tell how many such objects there are, nor give hints on how to find them. Some existence theorems give explicit formulas for solutions (e.g., Cramer's rule), others describe in their proofs iteration processes for approaching them (e.g., Bolzano-Weierstrass theorem), while others are settled by nonconstructive proofs which simply deduce the necessity of solutions without indicating any method for determining them (e.g., the Brouwer fixed point theorem, which is proved by reductio ad absurdum, showing that the nonexistence would lead to a contradiction).

Transfinite induction

Transfinite induction, like regular induction, is used to show a property holds for all numbers . The essential difference is that regular induction is restricted to the natural numbers , which are precisely the finite ordinal numbers. The normal inductive step of deriving from can fail due to limit ordinals.Let be a well ordered set and let be a proposition with domain . A proof by transfinite induction uses the following steps (Gleason 1991, Hajnal 1999): 1. Demonstrate is true. 2. Assume is true for all . 3. Prove , using the assumption in (2). 4. Then is true for all . To prove various results in point-set topology, Cantor developed the first transfinite induction methods in the 1880s. Zermelo (1904) extended Cantor's method with a "proof that every set can be well-ordered," which became the axiom of choice or Zorn's Lemma (Johnstone 1987). Transfinite induction and Zorn's lemma are often used interchangeably (Reid 1995), or are strongly..

Principle of mathematical induction

The truth of an infinite sequence of propositions for , ..., is established if (1) is true, and (2) implies for all . This principle is sometimes also known as the method of induction.

Pattern of two loci

According to G. Pólya, the method of finding geometric objects by intersection. 1. For example, the centers of all circles tangent to a straight line at a given point lie on a line that passes through and is perpendicular to . 2. In addition, the circle centered at with radius is the locus of the centers of all circles of radius passing through . The intersection of and consists of two points and which are the centers of two circles of radius tangent to at .Many constructions with straightedge and compass are based on this method, as, for example, the construction of the center of a given circle by means of the perpendicular bisector theorem.

Modus tollens

Modus tollens is a valid argument form in propositional calculus in which and are propositions. If implies , and is false, then is false. Also known as an indirect proof or a proof by contrapositive.For example, if being the king implies having a crown, not having a crown implies not being the king.

Characterization

A description of an object by properties that are different from those mentioned in its definition, but are equivalent to them. The following list gives a number of examples.1. A rational number is defined as the quotient of two integers, but it can be characterized as a number admitting a finite or repeating decimal expansion. 2. An equilateral triangle is defined as a triangle having three equal sides, but it can be characterized as a triangle having two angles of . 3. A real square matrix is nonsingular, by definition, if it admits a matrix inverse, but it can be characterized by the condition that its determinant be nonzero. Of course, a characterization should not merely be a rephrasing of the definition, but should give an entirely new description, which is useful because it contains a simpler formulation, can be verified more easily, is interesting because it places the object in another context, or unveils unexpected links between different..

Empty set

The set containing no elements, commonly denoted or , the former of which is used in this work. These correspond to Wolfram Language and TeX characters summarized in the table below.symbolTeXWolfram Language\varnothing\[Diameter]\emptyset\[EmptySet]Unfortunately, some authors use the notation 0 instead of for the empty set (Mendelson 1997). The empty set is generally designated using (i.e., the empty list) in the Wolfram Language.A set that is not the empty set is called a nonemptyset. The empty set is sometimes also known as the null set (Mendelson 1997).The complement of the empty set is the universal set.Strangely, the empty set is both open and closed for any set and topology.A groupoid, semigroup, quasigroup, ringoid, and semiring can be empty. Monoids, groups, and rings must have at least one element, while division algebras and fields must have at least two elements...

Element

If is a member of a set , then is said to be an element of , written . If is not an element of , this is written .The term element also refers to a particular member of a group, or entry in a matrix or unevaluated determinant .

Disjoint sets

Two sets and are disjoint if their intersection , where is the empty set. sets , , ..., are disjoint if for . For example, and are disjoint, but and are not. Disjoint sets are also said to be mutually exclusive or independent.

Superset

A set containing all elements of a smaller set. If is a subset of , then is a superset of , written . If is a proper superset of , this is written .

Directed set

A set together with a relation which is both transitive and reflexive such that for any two elements , there exists another element with and . In this case, the relation is said to "direct" the set.

Subset

A subset is a portion of a set. is a subset of (written ) iff every member of is a member of . If is a proper subset of (i.e., a subset other than the set itself), this is written . If is not a subset of , this is written . (The notation is generally not used, since automatically means that and cannot be the same.)The subsets (i.e., power set) of a given set can befound using Subsets[list].An efficient algorithm for obtaining the next higher number having the same number of 1 bits as a given number (which corresponds to computing the next subset) is given by Gosper (1972) in PDP-10 assembler.The set of subsets of a set is called the power set of , and a set of elements has subsets (including both the set itself and the empty set). This follows from the fact that the total number of distinct k-subsets on a set of elements is given by the binomial sumFor sets of , 2, ... elements, the numbers of subsets are therefore 2, 4, 8, 16, 32, 64, ... (OEIS A000079). For example, the set..

Russell's antinomy

Let be the set of all sets which are not members of themselves. Then is neither a member of itself nor not a member of itself. Symbolically, let . Then iff .Bertrand Russell discovered this paradox and sent it in a letter to G. Frege just as Frege was completing Grundlagen der Arithmetik. This invalidated much of the rigor of the work, and Frege was forced to add a note at the end stating, "A scientist can hardly meet with anything more undesirable than to have the foundation give way just as the work is finished. I was put in this position by a letter from Mr. Bertrand Russell when the work was nearly through the press."

A fact noticed by physicist G. Gamow when he had an office on the second floor and physicist M. Stern had an office on the sixth floor of a seven-story building (Gamow and Stern 1958, Gardner 1986). Gamow noticed that about 5/6 of the time, the first elevator to stop on his floor was going down, whereas about the same fraction of time, the first elevator to stop on the sixth floor was going up. This actually makes perfect sense, since 5 of the 6 floors 1, 3, 4, 5, 6, 7 are above the second, and 5 of the 6 floors 1, 2, 3, 4, 5, 7 are below the sixth. However, the situation takes some unexpected turns if more than one elevator is involved, as discussed by Gardner (1986). Furthermore, even worse, the analysis by Gamow and Stern (1958) turns out to be incorrect (Knuth 1969)!Main character Charles Eppes discusses the elevator paradox in the Season 4 episode "Chinese Box" of the television crime drama NUMB3RS...

A paradox mentioned in the Greek work Mechanica, dubiously attributed to Aristotle. Consider the above diagram depicting a wheel consisting of two concentric circles of different diameters (a wheel within a wheel). There is a 1:1 correspondence of points on the large circle with points on the small circle, so the wheel should travel the same distance regardless of whether it is rolled from left to right on the top straight line or on the bottom one. this seems to imply that the two circumferences of different sized circles are equal, which is impossible.The fallacy lies in the assumption that a one-to-one correspondence of points means that two curves must have the same length. In fact, the cardinalities of points in a line segment of any length (or even an infinite line, a plane, a three-dimensional space, or an infinite dimensional Euclidean space) are all the same: (the cardinality of the continuum), so the points of any of these can be put in a one-to-one..

Consider the length of the diagonal of a unit square as approximated by piecewise linear steps that may only be taken in the right and up directions. Obviously, the length so obtained is equal to half the perimeter, or 2. As the number of steps becomes large, the path visually appears to approach a diagonal line. However, no matter how small the steps, if they are constrained to be only to the right and up, their total length is always 2, despite the fact that the length of the diagonal is .This apparent paradox arises in physics in the computation of Feynman diagrams, where it has implications for the types of paths that must be included in order to obtain a good approximation to physical quantities.

In identical experiments, an Allais paradox occurs when the addition of an independent event influences choice behavior. Consider the choices in the following table (Kahneman and Tversky 1979).lottery1 to 333435 to 100preference018%82%0083%017%In Experiment 1, a choice of and was given, and most participants picked . In Experiment 2, a choice of and was given, and most participants picked .This observed pattern violates the independence axiom, since in both experiments, the payoff is identical if a ball is picked, while if the event is disregarded, the two experiments are identical.To see it another way, consider the event to be a black box that is always received if the random ball value is . Knowing or not knowing the contents of the black box should not influence behavior.

Destructive dilemma

A formal argument in logic in which it is stated that 1. and (where means "implies"), and 2. Either not- or not- is true, from which two statements it follows that either not- or not- is true.

Ultraproduct

Let be a language of first-order predicate logic, let be an indexing set, and for each , let be a structure of the language . Let be an ultrafilter in the power set Boolean algebra . Then the ultraproduct of the family is the structure that is given by the following: 1. For each fundamental constant of the language , the value of is the equivalence class of the tuple , modulo the ultrafilter . 2. For each -ary fundamental relation of the language , the value of is given as follows: The tuple is in if and only if the set is a member of the ultrafilter . 3. For each -ary fundamental operation of the language , and for each -tuple , the value of is . The ultraproduct of the family is typically denoted .

Transfer principle

In nonstandard analysis, the transfer principle is the technical form of the following intuitive idea: "Anything provable about a given superstructure by passing to a nonstandard enlargement of is also provable without doing so, and vice versa." It is a result of Łoś' theorem and the completeness theorem for first-order predicate logicThe transfer principle is stated as follows. Let be a superstructure, let be an enlargement of , let be any sentence in the language for , and let denote the -transform of . Then if and only if .

Superstructure

In nonstandard analysis, the limitation to first-order analysis can be avoided by using a construction known as a superstructure. Superstructures are constructed in the following manner. Let be an arbitrary set whose elements are not sets, and call the elements of "individuals." Define inductively a sequence of sets with and, for each natural number ,and letThen is called the superstructure over . An element of is an entity of .Using the definition of ordered pair provided by Kuratowski, namely , it follows that for any . Therefore, , and for any function from into , we have . Now assume that the set is (in one-to-one correspondence with) the set of real numbers , and then the relation which describes continuity of a function at a point is a member of . Careful consideration shows that, in fact, all the objects studied in classical analysis over are entities of this superstructure. Thus, first-order formulas about are sufficient to study..

Satisfaction

Let be a relational system, and let be a language which is appropriate for . Let be a well-formed formula of , and let be a valuation in . Then is written provided that one of the following holds: 1. is of the form , for some variables and of , and maps and to the same element of the structure . 2. is of the form , for some -ary predicate symbol of the language , and some variables of , and is a member of . 3. is of the form , for some formulas and of such that and . 4. is of the form , and there is an element of such that . In this case, is said to satisfy with the valuation .

Nonstandard analysis

Nonstandard analysis is a branch of mathematical logic which introduces hyperreal numbers to allow for the existence of "genuine infinitesimals," which are numbers that are less than 1/2, 1/3, 1/4, 1/5, ..., but greater than 0. Abraham Robinson developed nonstandard analysis in the 1960s. The theory has since been investigated for its own sake and has been applied in areas such as Banach spaces, differential equations, probability theory, mathematical economics, and mathematical physics.The axioms used in nonstandard analysis are first-order set theoretical axioms, but many of the topics studied in classical analysis that are axiomatized with higher-order axioms can be reformulated in set theoretical terms in a first-order axiomatization. As an example, consider the notion of a measure on a set. In classical analysis, one studies measure spaces. A measure space consists of a set , together with a measure , which is a function..

&321;o&347;' theorem

Let be a set, and let be an ultrafilter on , let be a formula of a given language , and let be any collection of structures which is indexed by the set . Denote by the equivalence class of under , for any element of the product . Then the ultraproduct satisfies via a valuation in ,

Hyperreal number

Hyperreal numbers are an extension of the real numbers to include certain classes of infinite and infinitesimal numbers. A hyperreal number is said to be finite iff for some integer . is said to be infinitesimal iff for all integers .

Hyperfinite set

One of the most useful tools in nonstandard analysis is the concept of a hyperfinite set. To understand a hyperfinite set, begin with an arbitrary infinite set whose members are not sets, and form the superstructure over . Assume that includes the natural numbers as elements, let denote the set of natural numbers as elements of , and let be an enlargement of . By the transfer principle, the ordering on extends to a strict linear ordering on , which can be denoted with the symbol "." Since is an enlargement of , it satisfies the concurrency principle, so that there is an element of such that if , then . This follows because the relation is a concurrent relation on the set of natural numbers.Any member that is not also an element of is called an infinite nonstandard natural number, and for any set , if is in one-to-one correspondence with any element of , then is called a hyperfinite set in . Because there are infinite nonstandard natural numbers in any..

Cup

The symbol , used for the union of sets, and, sometimes, also for the logical connective OR instead of the symbol (vee). In fact, for any two sets and and this equivalence demonstrates the connection between the set-theoretical and the logical meaning.

Connective

A function, or the symbol representing a function, which corresponds to English conjunctions such as "and," "or," "not," etc. that takes one or more truth values as input and returns a single truth value as output. The terms "logical connective" and "propositional connective" (Mendelson 1997, p. 13) are also used. The following table summarizes some common connectives and their notations.connectivesymbolAND, , , , , equivalent, , implies, , NAND, , nonequivalent, , NOR, , NOT, , , OR, , , XNOR XNOR XOR,

Xnor

The connective in logic corresponding to the exclusive nor operation. XNOR is equivalent to , where denotes AND, denotes OR, and denotes NOT. The circuit diagram symbol for an XNOR gate is illustrated above, and the XNOR truth table is given below for two arguments. For two arguments, " XNOR " is identical to " iff " and " is equivalent to " (). XNOR TTTTFFFTFFFT

Biconditional

The connective in (also denoted ) that returns a true result iff and are either both true or both false. The biconditional is also called an equivalence.

Nonequivalent

If and (i.e., , where denotes NOT, denotes implies, and denotes AND), then and are said to be inequivalent, a relationship which is written symbolically as , , or . Nonequivalence is implemented in the Wolfram Language as Unequal[A, B, ...]. Binary nonequivalence has the same truth table as XOR (i.e., exclusive disjunction), reproduced below.TTFTFTFTTFFF

Negation

The operation of interchanging true and false in a logical statement. The negation of is often called "NOT-," and can be denoted , or with the negation sign , so not- is written .Note that in computer languages such as C, perl, and the Wolfram Language, not- is denoted . In FORTRAN, not- is written .not.A, where is a variable of logical type.

Alternative denial

The term used in propositional calculus for the NAND connective. The notation is used for this connective, a most unfortunate choice in light of modern usage of or to denote OR.

Venn diagram

A schematic diagram used in logic theory to depict collectionsof sets and represent their relationships.The Venn diagrams on two and three sets are illustrated above. The order-two diagram (left) consists of two intersecting circles, producing a total of four regions, , , , and (the empty set, represented by none of the regions occupied). Here, denotes the intersection of sets and .The order-three diagram (right) consists of three symmetrically placed mutually intersecting circles comprising a total of eight regions. The regions labeled , , and consist of members which are only in one set and no others, the three regions labelled , , and consist of members which are in two sets but not the third, the region consists of members which are simultaneously in all three, and no regions occupied represents .In general, an order- Venn diagram is a collection of simple closed curves in the plane such that 1. The curves partition the plane into connected..

Formal language

In mathematics, a formal language is normally defined by an alphabet and formation rules. The alphabet of a formal language is a set of symbols on which this language is built. Some of the symbols in an alphabet may have a special meaning. The formation rules specify which strings of symbols count as well-formed. The well-formed strings of symbols are also called words, expressions, formulas, or terms. The formation rules are usually recursive. Some rules postulate that such and such expressions belong to the language in question. Some other rules establish how to build well-formed expressions from other expressions belonging to the language. It is assumed that nothing else is a well-formed expression.For example, the language of propositional calculus could be defined as follows. The alphabet of this language is comprised of English letters with optional indexes and the following special symbols: (NOT), (AND), (OR), (implies), and (grouping)...

Propositional calculus

Propositional calculus is the formal basis of logic dealing with the notion and usage of words such as "NOT," "OR," "AND," and "implies." Many systems of propositional calculus have been devised which attempt to achieve consistency, completeness, and independence of axioms. The term "sentential calculus" is sometimes used as a synonym for propositional calculus.Axioms (or their schemata) and rules of inference define a proof theory, and various equivalent proof theories of propositional calculus can be devised. The following list of axiom schemata of propositional calculus is from Kleene (2002). (1)(2)(3)(4)(5)(6)(7)(8)(9)(10)In each schema, , , can be replaced by any sentential formula. The following rule called Modus Ponens is the sole rule of inference:(11)This rule states that if each of and is either an axiom or a theorem formally deduced from axioms by application of..

Reflexive

A relation on a set is reflexive provided that for every in .

Canonical map

A function mapping a set ( modulo ), where is an equivalence relation in , is called a canonical map.

Transitive

A relation on a set is transitive provided that for all , and in such that and , we also have .

Irreflexive

A relation on a set is irreflexive provided that no element is related to itself; in other words, for no in .

Symmetric relation

A relation on a set is symmetric provided that for every and in we have iff . The symmetric relations on nodes are isomorphic with the rooted graphs on nodes.

Equivalence relation

An equivalence relation on a set is a subset of , i.e., a collection of ordered pairs of elements of , satisfying certain properties. Write "" to mean is an element of , and we say " is related to ," then the properties are 1. Reflexive: for all , 2. Symmetric: implies for all 3. Transitive: and imply for all , where these three properties are completely independent. Other notations are often used to indicate a relation, e.g., or .

Antisymmetric relation

A relation on a set is antisymmetric provided that distinct elements are never both related to one another. In other words and together imply that .

Relation

A relation is any subset of a Cartesian product. For instance, a subset of , called a "binary relation from to ," is a collection of ordered pairs with first components from and second components from , and, in particular, a subset of is called a "relation on ." For a binary relation , one often writes to mean that is in .

Equivalence class

An equivalence class is defined as a subset of the form , where is an element of and the notation "" is used to mean that there is an equivalence relation between and . It can be shown that any two equivalence classes are either equal or disjoint, hence the collection of equivalence classes forms a partition of . For all , we have iff and belong to the same equivalence class.A set of class representatives is a subset of which contains exactly one element from each equivalence class.For a positive integer, and integers, consider the congruence , then the equivalence classes are the sets , etc. The standard class representatives are taken to be 0, 1, 2, ..., .

Initial segment

Let be a well ordered set. Then the set for some is called an initial segment of (Rubin 1967, p. 161; Dauben 1990, pp. 196-197; Moore 1982, pp. 90-91). This term was first used by Cantor, who also proved that if and are well ordered sets that are not order isomorphic, then exactly one of the following statements is true: 1. is order isomorphic to an initial segment of , or 2. is order isomorphic to an initial segment of (Dauben 1990, p. 198).

Fence poset

A partial order defined by (, ), (, ) for odd .

Duality law

A metatheorem stating that every theorem on partially ordered sets remains true if all inequalities are reversed. In this operation, supremum must be replaced by infimum, maximum with minimum, and conversely. In a lattice, this means that meet and join must be interchanged, and in a Boolean algebra, 1 and 0 must be switched.Each of de Morgan's two laws can be derived from the other by duality.

Totally ordered set

A total order (or "totally ordered set," or "linearly ordered set") is a set plus a relation on the set (called a total order) that satisfies the conditions for a partial order plus an additional condition known as the comparability condition. A relation is a total order on a set (" totally orders ") if the following properties hold. 1. Reflexivity: for all . 2. Antisymmetry: and implies . 3. Transitivity: and implies . 4. Comparability (trichotomy law): For any , either or . The first three are the axioms of a partial order, while addition of the trichotomy law defines a total order.Every finite totally ordered set is well ordered. Any two totally ordered sets with elements (for a nonnegative integer) are order isomorphic, and therefore have the same order type (which is also an ordinal number)...

Dominance

The dominance relation on a set of points in Euclidean -space is the intersection of the coordinate-wise orderings. A point dominates a point provided that every coordinate of is at least as large as the corresponding coordinate of .A partition dominates a partition if, for all , the sum of the largest parts of is the sum of the largest parts of . For example, for , dominates all other partitions, while is dominated by all others. In contrast, and do not dominate each other (Skiena 1990, p. 52).The dominance orders in are precisely the partially ordered sets of dimension at most .

Dilworth's lemma

The partial order width of a set is equal to the minimum number of chains needed to cover . Equivalently, if a set of elements is partially ordered, then contains a chain of size or an antichain of size . Letting be the cardinal number of , the partial order width, and the partial order length, this last statement says . Dilworth's lemma is a generalization of the Erdős-Szekeres theorem. Ramsey's theorem generalizes Dilworth's lemma.

Tarski's fixed point theorem

Let be any complete lattice. Suppose is monotone increasing (or isotone), i.e., for all , implies . Then the set of all fixed points of is a complete lattice with respect to (Tarski 1955)Consequently, has a greatest fixed point and a least fixed point . Moreover, for all , implies , whereas implies .Consider three examples: 1. Let satisfy , where is the usual order of real numbers. Since the closed interval is a complete lattice, every monotone increasing map has a greatest fixed point and a least fixed point. Note that need not be continuous here. 2. For declare to mean that , , (coordinatewise order). Let satisfy . Then the set(1)(2)is a complete lattice (with respect to the coordinatewise order). Hence every monotone increasing map has a greatest fixed point and a least fixed point. 3. Let and be injections. Then there is a bijection (Schröder-Bernstein theorem), which can be constructed as follows. The power set of ordered by set inclusion,..

Order isomorphic

Two totally ordered sets and are order isomorphic iff there is a bijection from to such that for all ,(Ciesielski 1997, p. 38). In other words, and are equipollent ("the same size") and there is an order preserving mapping between the two.Dauben (1990) and Suppes (1972) call this property "similar." The definitionworks equally well on partially ordered sets.

Cover relation

The transitive reflexive reduction of a partial order. An element of a partially ordered set covers another element provided that there exists no third element in the poset for which . In this case, is called an "upper cover" of and a "lower cover" of .

Strictly between

Let be a partially ordered set, and let . If , then is said to be between and . If is between and and , then is strictly between and .

Maximal element

Let be a partially ordered set. Then an element is said to be maximal if, for all , . Alternatively, an element is maximal such that if for any , then .Note that the definition for a maximal element above is true for any two elements of a partially ordered set that are comparable. However, it may be the case that two elements of a given partial ordering are not comparable.

Complete lattice

A partially ordered set (or ordered set or poset for short) is called a complete lattice if every subset of has a least upper bound (supremum, ) and a greatest lower bound (infimum, ) in .Taking shows that every complete lattice has a greatest element (maximum, ) and a least element (minimum, ).Of course, every complete lattice is a lattice. Moreover, every lattice with a finite set is a complete lattice.

Realizer

A set of linear extensions of a partially ordered set is a realizer of (and is said to realize ) provided that for all , iff is below in every member of .

Linear extension

A linear extension of a partially ordered set is a permutation of the elements , , ... of such that implies . For example, the linear extensions of the partially ordered set are 1234, 1324, 1342, 3124, 3142, and 3412, all of which have 1 before 2 and 3 before 4.

Comparable elements

Suppose is a partial ordering on a nonempty set . Then the elements are said to be comparable provided or .Because two elements in a partially ordered set need not be comparable, it is possible for a partially ordered set to have more than one maximal element. For example, suppose we have a nonempty partially ordered set in which every element is incomparable to every other element, i.e., is totally unordered. It follows that every element of is maximal.

Preorder

A relation "" is called a preorder (or quasiorder) on a set if it satisfies: 1. Reflexivity: for all . 2. Transitivity: and implies . A preorder that also has antisymmetry is a partial order.

Chain

Let be a finite partially ordered set. A chain in is a set of pairwise comparable elements (i.e., a totally ordered subset). The partial order length of is the maximum cardinal number of a chain in . For a partial order, the size of the longest chain is called the partial order length.

Poset dimension

The dimension of a partially ordered set is the size of the smallest realizer of . Equivalently, it is the smallest integer such that is isomorphic to a dominance order in .

Isomorphic posets

Two partially ordered sets are said to be isomorphic if their "structures" are entirely analogous. Formally, partially ordered sets and are isomorphic if there is a bijection from to such that precisely when .

Partially ordered set

A partially ordered set (or poset) is a set taken together with a partial order on it. Formally, a partially ordered set is defined as an ordered pair , where is called the ground set of and is the partial order of .An element in a partially ordered set is said to be an upper bound for a subset of if for every , we have . Similarly, a lower bound for a subset is an element such that for every , . If there is an upper bound and a lower bound for , then the poset is said to be bounded.

Interval order

A partially ordered set is an interval order if it is isomorphic to some set of intervals on the real line ordered by left-to-right precedence. Formally, is an interval order provided that one can assign to each an interval such that in the real numbers iff in .

Ordinal number

In common usage, an ordinal number is an adjective which describes the numerical position of an object, e.g., first, second, third, etc.In formal set theory, an ordinal number (sometimes simply called an "ordinal" for short) is one of the numbers in Georg Cantor's extension of the whole numbers. An ordinal number is defined as the order type of a well ordered set (Dauben 1990, p. 199; Moore 1982, p. 52; Suppes 1972, p. 129). Finite ordinal numbers are commonly denoted using arabic numerals, while transfinite ordinals are denoted using lower case Greek letters.It is easy to see that every finite totally ordered set is well ordered. Any two totally ordered sets with elements (for a nonnegative integer) are order isomorphic, and therefore have the same order type (which is also an ordinal number). The ordinals for finite sets are denoted 0, 1, 2, 3, ..., i.e., the integers one less than the corresponding nonnegative..

Ordinal comparison

Let and be well ordered sets with ordinal numbers and . Then iff is order isomorphic to an initial segment of (Dauben 1990, p. 199). From this, it can easily be shown that the ordinal numbers are totally ordered by the relation. In fact, they are well ordered by the relation.

Order type

Every totally ordered set is associated with a so-called order type. Two sets and are said to have the same order type iff they are order isomorphic (Ciesielski 1997, p. 38; Dauben 1990, pp. 184 and 199; Moore 1982, p. 52; Suppes 1972, pp. 127-129). Thus, an order type categorizes totally ordered sets in the same way that a cardinal number categorizes sets. The term is due to Georg Cantor, and the definition works equally well on partially ordered sets.The order type of the negative integers is called (Moore 1982, p. 62), although Suppes (1972, p. 128) calls it . The order type of the rationals is called (Dauben 1990, p. 152; Moore 1982, p. 115; Suppes 1972, p. 128). Some sources call the order type of the reals (Dauben 1990, p. 152), while others call it (Suppes 1972, p. 128).In general, if is any order type, then is the same type ordered backwards (Dauben 1990, p. 153)...

Limit ordinal

An ordinal number is called a limit ordinal iff it has no immediate predecessor, i.e., if there is no ordinal number such that (Ciesielski 1997, p. 46; Moore 1982, p. 60; Rubin 1967, p. 182; Suppes 1972, p. 196). The first limit ordinal is .

Model theory

Model theory is a general theory of interpretations of axiomatic set theory. It is the branch of logic studying mathematical structures by considering first-order sentences which are true of those structures and the sets which are definable in those structures by first-order formulas (Marker 1996).Mathematical structures obeying axioms in a system are called "models" of the system. The usual axioms of analysis are second order and are known to have the real numbers as their unique model. Weakening the axioms to include only the first-order ones leads to a new type of model in what is called nonstandard analysis.

Uniquely complemented lattice

A uniquely complemented lattice is a complemented lattice that satisfiesThe class of uniquely complemented lattices is not a subvariety of the class of complemented lattices. On the other hand, there is a well-known class of uniquely complemented lattices that is a subvariety of the variety of complemented lattices, namely the class of Boolean algebras. They form a variety because they are the distributive complemented lattices, and one can prove that any distributive complemented lattice is uniquely complemented.

Locally bounded lattice

A lattice is locally bounded if and only if each of its finitely generated sublattices is bounded.Every locally bounded lattice is locally subbounded, and every locally bounded lattice has a bounded hyperfinite extension in any nonstandard enlargement . This latter nonstandard property characterizes locally subbounded lattices.A locally bounded lattice is locally tight if and only if each of its hyperfinitely generated extensions is internally tight. One can also prove the following result, using nonstandard characterizations of these notions: Let be a locally finite lattice with at least one strictly increasing meet endomorphism and at least one strictly decreasing join endomorphism. If is locally tight, then it is bounded.

Local polarity

Let be a lattice, and let . Then the pair is a local polarity if and only if for each finite set , there is a finitely generated sublattice of that contains and on which the restriction is a lattice polarity.Using nonstandard methods, one may show that the following result holds: Let be a locally finite lattice. Then the set of local polarities of is a relation which is a one-to-one correspondence between its domain and range.

Solved problems

There are many unsolved problems in mathematics. Severalfamous problems which have recently been solved include: 1. The Pólya conjecture (disproven byHaselgrove 1958, smallest counterexample found by Tanaka 1980). 2. The four-color theorem (Appel and Haken1977ab and Appel et al. 1977 using a computer-assisted proof). 3. The Bieberbach conjecture (L. deBranges 1985). 4. Tait's flyping conjecture (Menasco and Thistlethwaite in 1991) and the other two of Tait's knot conjectures (by various authors 1987). 5. Fermat's last theorem (Wiles 1995, Taylorand Wiles 1995). 6. The Kepler conjecture (Hales 2002). 7. The Taniyama-Shimura conjecture(Breuil et al. in 1999). 8. The honeycomb conjecture (Hales 1999).9. The Poincaré conjecture. 10. Catalan's conjecture. 11. The strong perfect graph theorem...

Fallacy

A fallacy is an incorrect result arrived at by apparently correct, though actually specious reasoning. The great Greek geometer Euclid wrote an entire book on geometric fallacies which, unfortunately, has not survived (Gardner 1984, p. ix).The most common example of a mathematical fallacy is the "proof" that as follows. Let , then (1)(2)(3)(4)(5)(6)The incorrect step is (4), in which division by zero () is performed, which is not an allowed algebraic operation. Similarly flawed reasoning can be used to show that , or any number equals any other number.Ball and Coxeter (1987) give other such examples in the areas of both arithmetic and geometry.

Sentence

A sentence is a logic formula in which every variable is quantified. The concept of a sentence is important because formulas with variables that are not quantified are ambiguous.The concept of the sentence can be illustrated as follows (Enderton 1977). The formula , in which each variable is quantified, can be translated into English as the complete sentence "There exists a set which has every set as an element." However, the formula , in which is not quantified, can only be translated as the sentence fragment "Every set is an element of ___," where "___" is unspecified because is not quantified.Because a "quantified variable" (or "quantifier") is just a more descriptive name for a bound variable, a sentence can also be defined as a logic formula with no free variables (Enderton 1977). A sentence can also be defined as a closed sentential formula (Carnap 1958, pp. 24 and 85), although..

Horn clause

A clause (i.e., a disjunction of literals) is called a Horn clause if it contains at most one positive literal. Horn clauses are usually written asorwhere and is the only positive literal.A definite clause is a Horn clause that has exactly one positive literal. A Horn clause without a positive literal is called a goal.Horn clauses express a subset of statements of first-order logic. Programming language Prolog is built on top of Horn clauses. Prolog programs are comprised of definite clauses and any question in Prolog is a goal.

Herbrand universe

Consider a first-order logic formula in Skolemized formThen the Herbrand universe of is defined by the following rules. 1. All constants from belong to . If there are no constants in , then contains an arbitrary constant . 2. If , and an -place function occurs in , then . The clauses (disjunctions of literals) obtained from those of by replacing all variables by elements of the Herbrand universe are called ground clauses, with similar definitions for a ground literal and ground atom. The set of all ground atoms that can be formed from predicate symbols from and terms from is called the Herbrand base.Consecutive generation of elements of the Herbrand universe and verification of unsatisfiability of generated elements can be straightforwardly implemented in a computer program. Given the completeness of first-order logic, this program is basically a tool for automated theorem proving. Of course, this exhaustive search is too slow for practical..

Herbrand base

The set of all ground atoms that can be formed from predicate symbols from a clause in Skolemized form and terms from the Herbrand universe of .

Ground literal

Consider a clause (disjunction of literals) obtained from those of a first-order logic formula in Skolemized formThen a literal obtained from those of by replacing all variables by elements of the Herbrand universe of is called a ground literal.

Ground clause

Consider a clause (disjunction of literals) obtained from those of a first-order logic sentential formula in Skolemized formthen a clause obtained from those of by replacing all variables by elements of the Herbrand universe of is called a ground clause.

Resolution principle

The resolution principle, due to Robinson (1965), is a method of theorem proving that proceeds by constructing refutation proofs, i.e., proofs by contradiction. This method has been exploited in many automatic theorem provers. The resolution principle applies to first-order logic formulas in Skolemized form. These formulas are basically sets of clauses each of which is a disjunction of literals. Unification is a key technique in proofs by resolution.If two or more positive literals (or two or more negative literals) in clause are unifiable and is their most general unifier, then is called a factor of . For example, is factored to . In such a factorization, duplicates are removed.Let and be two clauses with no variables in common, let contain a positive literal , contain a negative literal , and let be the most general unifier of and . Thenis called a binary resolvent of and . For example, if and , then is their binary resolvent.A resolvent of two..

Ground atom

Consider a clause (disjunction of literals) obtained from those of a first-order logic formula in Skolemized formThen an atomic statement obtained from those of by replacing all variables by elements of the Herbrand universe of is called a ground atom. The set of all ground atoms that can be formed from predicate symbols from and terms from is called the Herbrand base.

Grammar

A grammar defining formal language is a quadruple , where is a finite set of nonterminals, is a finite set of terminal symbols, is a finite set of productions, and is an element of .The set of terminal symbols is 's alphabet. Nonterminals are symbols representing language constructs. The sets and should not intersect. is called the start symbol. Productions are rules of the form: , where both and are strings of terminals and nonterminals, contains at least one nonterminal.Sentential forms for grammar are defined by the following rules: is a sentential form and if is a sentential form and production belongs to , then is a sentential form as well. is the set of all strings which are sentential forms consisting entirely of terminal symbols. For a language defined by a grammar, recognition whether a given string (expression) belongs to that language is, in general, a non-trivial task. All languages defined by grammars are recursively enumerable sets.1...

Regular expression

Regular expressions define formal languages as sets of strings over a finite alphabet. Let denote a selected alphabet. Then is a regular expression that denotes the empty set and is a regular expression that denotes the set containing the empty string as its only element.If , then is a regular expression that denotes the set whose only element is string . If and are regular expressions denoting sets and , then 1. is a regular expression denoting the set , where denotes the union. 2. is a regular expression denoting the set of all concatenations of and , where and . 3. is a regular expression denoting closure of , that is, the set of zero or more concatenations of strings from The sets defined by regular expressions are called regular sets, and a set is regulariff it is defined by a right linear grammar...

Reduction system

A system in which words (expressions) of a formal language can be transformed according to a finite set of rewrite rules is called a reduction system. While reduction systems are also known as string rewriting systems or term rewriting systems, the term "reduction system" is more general.Lambda calculus is an example of a reduction system with lambda conversion rules constituting its rewrite rules.If none of the rewrite rules of a reduction system apply to expression , then is said to be in normal form for a reduction system.A pair of expressions is called joinable if both and can be reduced to the same expression in zero or more reduction steps (i.e., applications of rewrite rules).If is reduced to in one step, this is indicated . If is reduced to in zero or more steps, this is indicated . The notation is used if there is a sequence such that , , and for every pair , either or ...

Reduction order

A strict order on the set of terms of a term rewriting system is called a reduction order if 1. The set of terms is well ordered with respect to , that is, all its nonempty subsets contain their least elements, 2. This order is compatible with functions (operations) of the system, i.e.,and 3. For any substitution (cf. unification), . If holds for every rewriting rule , then this term rewriting system is finitely terminating.

Game of logic

The Game of Logic, described by Lewis Carroll--author of Alice in Wonderland--in 1887 (Carroll 1972) consists of discussing the meaning of propositions like "Some fresh cakes are sweet," and is an instructive introduction to the concepts of logic.The game takes place in a world divided into four quadrants. In the northwest quadrant, the cakes are fresh and sweet, in the northeast, they are fresh and not-sweet, in the southwest, they are not-fresh and sweet, and in the southeast, they are not-fresh and not-sweet. The game is played with four red coins and five gray coins. A red coin is used to indicate the presence of some (one or more) cakes in a sector, while a gray coin indicates that the sector is empty.A red coin in the northwest sector is a representation of the proposition "Some fresh cakes are sweet." By using more coins it is possible to represent more complex propositions. For example, one red coin in the northwest sector..

Independent vertex set

An independent vertex set of a graph is a subset of the vertices such that no two vertices in the subset represent an edge of . The figure above shows independent sets consisting of two subsets for a number of graphs (the wheel graph , utility graph , Petersen graph, and Frucht graph).The polynomial whose coefficients give the number of independent vertex sets of each cardinality in a graph is known as its independence polynomial.A set of vertices is an independent vertex set iff its complement forms a vertex cover (Skiena 1990, p. 218). The counts of vertex covers and independent vertex sets in a graph are therefore the same.The empty set is trivially an independent vertex setsince it contains no vertices, and therefore no edge endpoints.A maximum independent vertex set is an independent vertex set of a graph containing the largest possible number of vertices for the given graph, and the cardinality of this set is called the independence number..

Semialgebraic set

A semialgebraic set is a subset of which is a finite Boolean combination of sets of the form and , where and are polynomials in , ..., over the reals.By Tarski's theorem, the solution set of a quantified system of real algebraic equations and inequalities is a semialgebraic set (Strzebonski 2000).

Antichain

Let be a finite partially ordered set, then an antichain in is a set of pairwise incomparable elements. Antichains are also called Sperner systems in older literature (Comtet 1974).For example, consider to be a family of subsets together with the subset relation (i.e., if is a subset of ). The following table gives the antichains on the set of subsets (i.e., the power set) of the -set for small .antichains123The number of antichains on the -set for , 1, 2, ..., are 1, 2, 5, 19, 167, ... (OEIS A014466). If the empty set is not considered a valid antichain, then these reduce to 0, 1, 4, 18, 166, ... (OEIS A007153; Comtet 1974, p. 273). The numbers obtained by adding one to OEIS A014466, 2, 3, 6, 20, 168, 7581, 7828354, ... (OEIS A000372), are also frequently encountered (Speciner 1972).The number of antichains on the -set are equal to the number of monotonic increasing Boolean functions of variables, and also the number of free distributive lattices..

Cardinal exponentiation

Let and be any sets, and let be the cardinal number of a set . Then cardinal exponentiation is defined by(Ciesielski 1997, p. 68; Dauben 1990, p. 174; Moore 1982, p. 37; Rubin 1967, p. 275, Suppes 1972, p. 116).It is easy to show that the cardinal number of the power set of is , since and there is a natural bijection between the subsets of and the functions from into .

Infinite set

A set of elements is said to be infinite if the elements of a proper subset can be put into one-to-one correspondence with the elements of . An infinite set whose elements can be put into a one-to-one correspondence with the set of integers is said to be countably infinite; otherwise, it is called uncountably infinite.

Cardinal comparison

For any sets and , their cardinal numbers satisfy iff there is a one-to-one function from into (Rubin 1967, p. 266; Suppes 1972, pp. 94 and 116). It is easy to show this satisfies the reflexive and transitive axioms of a partial order. However, it is difficult to show the antisymmetry property, whose proof is known as the Schröder-Bernstein theorem. To show the trichotomy property, one must use the axiom of choice.Although an order type can be defined similarly, it does not seem usual to do so.

Let and be any sets with empty intersection, and let denote the cardinal number of a set . Then(Ciesielski 1997, p. 68; Dauben 1990, p. 173; Rubin 1967, p. 274; Suppes 1972, pp. 112-113).It is an interesting exercise to show that cardinal addition is well-defined. The main steps are to show that for any cardinal numbers and , there exist disjoint sets and with cardinal numbers and , and to show that if and are disjoint and and disjoint with and then . The second of these is easy. The first is a little tricky and requires an appeal to the axioms of set theory. Also, one needs to restrict the definition of cardinal to guarantee if is a cardinal, then there is a set satisfying .

Unsolved problems

There are many unsolved problems in mathematics. Some prominent outstanding unsolved problems (as well as some which are not necessarily so well known) include 1. The Goldbach conjecture. 2. The Riemann hypothesis. 3. The conjecture that there exists a Hadamard matrixfor every positive multiple of 4. 4. The twin prime conjecture (i.e., the conjecture that there are an infinite number of twin primes). 5. Determination of whether NP-problems are actuallyP-problems. 6. The Collatz problem. 7. Proof that the 196-algorithm does not terminatewhen applied to the number 196. 8. Proof that 10 is a solitary number. 9. Finding a formula for the probability that two elements chosen at random generate the symmetric group . 10. Solving the happy end problem for arbitrary . 11. Finding an Euler brick whose space diagonal isalso an integer. 12. Proving which numbers can be represented as a sum of three or four (positiveor negative) cubic numbers. 13. Lehmer's..

Set partition

A set partition of a set is a collection of disjoint subsets of whose union is . The number of partitions of the set is called a Bell number.

Disjunction

The term in logic used to describe the operation commonly known as OR. A literal is considered a (degenerate) disjunction (Mendelson 1997, p. 30).The Wolfram Language command Disjunction[expr, a1, a2, ...] gives the disjunction of expr over all choices of the Boolean variables .

Fibered category morphism

Let and be fibered categories over a topological space . A morphism of fibered categories consists of: 1. a functor for each open subset and 2. a natural isomorphism for each inclusion . It is required that these structures satisfy a compatibility condition with respect to the 's, namely, that for the inclusions , , the above diagram should commute.

Fibered category

A fibered category over a topological space consists of 1. a category for each open subset , 2. a functor for each inclusion , and 3. a natural isomorphismfor each pair of inclusions , . In addition, for any three composable inclusions , , and , there exists a natural commuting as shown above.Sometimes, the pair is used to denote a fibered category with more precision while the shorthand is sometimes used for , , .

Faithful functor

A functor is said to be faithful if it is injective on maps. This does not necessarily imply injectivity on objects. For example, the forgetful functor from the category of groups to the category of sets is faithful, but it identifies non-isomorphic groups having the same underlying set. Conversely, a functor injective on objects need not be injective on maps. For example, a counterexample is the functor on the category of vector spaces which leaves every vector space unchanged and sends every map to the zero map.A functor which is injective both on objects and maps is sometimes called an embedding.

Abelian category

An Abelian category is a category for which the constructions and techniques of homological algebra are available. The basic examples of such categories are the category of Abelian groups and, more generally, the category of modules over a ring. Abelian categories are widely used in algebra, algebraic geometry, and topology.Many of the same constructions that are found in categories of modules, such as kernels, exact sequences, and commutative diagrams are available in Abelian categories. A disadvantage that must be overcome is the fact that the objects in a category do not necessarily have elements that can be manipulated directly, so the traditional definitions do not work. As a result, methods must be developed that allow definition and manipulation of objects without the use of elements.As an example, consider the definition of the kernel of a morphism, which states that given , the kernel of is defined to be a morphism such that all morphisms..

Hilbert's axioms

The 21 assumptions which underlie the geometry published in Hilbert's classic text Grundlagen der Geometrie. The eight incidence axioms concern collinearity and intersection and include the first of Euclid's postulates. The four ordering axioms concern the arrangement of points, the five congruence axioms concern geometric equivalence, and the three continuity axioms concern continuity. There is also a single parallel axiom equivalent to Euclid's parallel postulate.

Axiom of the unordered pair

The axiom of Zermelo-Fraenkel set theory which asserts the existence for any sets and of a set having and as its only elements. is called the unordered pair of and , denoted . The axiom may be stated symbolically as

Axiom of the sum set

The axiom of Zermelo-Fraenkel set theory which asserts the existence for any set of the sum (union) of all sets that are elements of . The axiom may be stated symbolically as

Axiom of the power set

One of the Zermelo-Fraenkel axioms which asserts the existence for any set of the power set consisting of all the subsets of . The axiom may be stated symbolically as(Enderton 1977). Note that the version given by Itô (1986, p. 147),is confusing, and possibly incorrect.

Presburger arithmetic

Presburger arithmetic is the first-order theory of the natural numbers containing addition but no multiplication. It is therefore not as powerful as Peano arithmetic. However, it is interesting because unlike the case of Peano arithmetic, there exists an algorithm that can decide if any given statement in Presburger arithmetic is true (Presburger 1929). No such algorithm exists for general arithmetic as a consequence of Robinson and Tarski's negative answer to the decision problem. Presburger (1929) also proved that his arithmetic is consistent (does not contain contradictions) and complete (every statement can either be proven or disproven), which is false for Peano arithmetic as a consequence of Gödel's first incompleteness theorem.Fischer and Rabin (1974) proved that every algorithm which decides the truth of Presburger statements has a running time of at least for some constant , where is the length of the Presburger statement...

Excision axiom

One of the Eilenberg-Steenrod axioms which states that, if is a space with subspaces and such that the set closure of is contained in the interior of , then the inclusion map induces an isomorphism .

Euclid's postulates

1. A straight line segment can be drawn joining anytwo points. 2. Any straight line segment can be extended indefinitelyin a straight line. 3. Given any straight line segment, a circle can be drawn having the segment as radius and one endpoint as center. 4. All right angles are congruent.5. If two lines are drawn which intersect a third in such a way that the sum of the inner angles on one side is less than two right angles, then the two lines inevitably must intersect each other on that side if extended far enough. This postulate is equivalent to what is known as the parallel postulate. Euclid's fifth postulate cannot be proven as a theorem, although this was attempted by many people. Euclid himself used only the first four postulates ("absolute geometry") for the first 28 propositions of the Elements, but was forced to invoke the parallel postulate on the 29th. In 1823, Janos Bolyai and Nicolai Lobachevsky independently realized that entirely..

Axiom of subsets

The axiom of Zermelo-Fraenkel set theory which asserts the existence for any set and a formula of a set consisting of all elements of satisfying ,where denotes exists, means for all, denotes "is an element of," means equivalent, and denotes logical AND.This axiom is called the subset axiom by Enderton (1977), while Kunen (1980) calls it the comprehension axiom. Itô (1986) terms it the axiom of separation, but this name appears to not be used widely in the literature and to have the additional drawback that it is potentially confusing with the separation axioms of Hausdorff arising in topology.This axiom was introduced by Zermelo.

Axiom of replacement

One of the Zermelo-Fraenkel axioms which asserts the existence for any set of a set such that, for any of , if there exists a satisfying , then such exists in ,This axiom was introduced by Fraenkel.

Peano's axioms

1. Zero is a number. 2. If is a number, the successor of is a number. 3. zero is not the successor of a number. 4. Two numbers of which the successors are equal are themselves equal. 5. (induction axiom.) If a set of numbers contains zero and also the successor of every number in , then every number is in . Peano's axioms are the basis for the version of numbertheory known as Peano arithmetic.

Axiom of infinity

The axiom of Zermelo-Fraenkel set theorywhich asserts the existence of a set containing all the natural numbers,where denotes exists, is the empty set, is logical AND, means for all, and denotes "is an element of" (Enderton 1977). Following von Neumann, , , , , ....

De morgan's laws

Let represent "or", represent "and", and represent "not." Then, for two logical units and ,These laws also apply in the more general context of Boolean algebra and, in particular, in the Boolean algebra of set theory, in which case would denote union, intersection, and complementation with respect to any superset of and .

Axiom of foundation

One of the Zermelo-Fraenkel axioms, also known as the axiom of regularity (Rubin 1967, Suppes 1972). In the formal language of set theory, it states thatwhere means implies, means exists, means AND, denotes intersection, and is the empty set (Mendelson 1997, p. 288). More descriptively, "every nonempty set is disjoint from one of its elements."The axiom of foundation can also be stated as "A set contains no infinitely descending (membership) sequence," or "A set contains a (membership) minimal element," i.e., there is an element of the set that shares no member with the set (Ciesielski 1997, p. 37; Moore 1982, p. 269; Rubin 1967, p. 81; Suppes 1972, p. 53).Mendelson (1958) proved that the equivalence of these two statements necessarily relies on the axiom of choice. The dual expression is called -induction, and is equivalent to the axiom itself (Itô 1986, p. 147)...

Parallel postulate

Given any straight line and a point not on it, there "exists one and only one straight line which passes" through that point and never intersects the first line, no matter how far they are extended. This statement is equivalent to the fifth of Euclid's postulates, which Euclid himself avoided using until proposition 29 in the Elements. For centuries, many mathematicians believed that this statement was not a true postulate, but rather a theorem which could be derived from the first four of Euclid's postulates. (That part of geometry which could be derived using only postulates 1-4 came to be known as absolute geometry.)Over the years, many purported proofs of the parallel postulate were published. However, none were correct, including the 28 "proofs" G. S. Klügel analyzed in his dissertation of 1763 (Hofstadter 1989). The main motivation for all of this effort was that Euclid's parallel postulate did..

Continuity axioms

"The" continuity axiom is an additional Axiom which must be added to those of Euclid's Elements in order to guarantee that two equal circles of radius intersect each other if the separation of their centers is less than (Dunham 1990). The continuity axioms are the three of Hilbert's axioms which concern geometric equivalence.Archimedes' Axiom is sometimes also known as"the continuity axiom."

Axiom of extensionality

The axiom of Zermelo-Fraenkel set theorywhich asserts that sets formed by the same elements are equal,Note that some texts (e.g., Devlin 1993), use a bidirectional equivalent preceding "," while others (e.g., Enderton 1977, Itô 1986), use the one-way implies . However, one-way implication suffices.Using the notation ( is a subset of ) for , the axiom can be written concisely aswhere denotes logical AND.

Axiom of choice

An important and fundamental axiom in set theory sometimes called Zermelo's axiom of choice. It was formulated by Zermelo in 1904 and states that, given any set of mutually disjoint nonempty sets, there exists at least one set that contains exactly one element in common with each of the nonempty sets. The axiom of choice is related to the first of Hilbert's problems.In Zermelo-Fraenkel set theory (in the form omitting the axiom of choice), Zorn's lemma, the trichotomy law, and the well ordering principle are equivalent to the axiom of choice (Mendelson 1997, p. 275). In contexts sensitive to the axiom of choice, the notation "ZF" is often used to denote Zermelo-Fraenkel without the axiom of choice, while "ZFC" is used if the axiom of choice is included.In 1940, Gödel proved that the axiom of choice is consistent with the axioms of von Neumann-Bernays-Gödel set theory (a conservative extension of Zermelo-Fraenkel..

Long exact sequence of a pair axiom

One of the Eilenberg-Steenrod axioms. It states that, for every pair , there is a natural long exact sequencewhere the map is induced by the inclusion map and is induced by the inclusion map . The map is called the boundary map.

Categorical axiomatic system

An axiomatic system is said to be categorical if there is only one essentially distinct representation for it. In particular, the names and types of objects within the system may vary while still being considered "the same," e.g., geometries and their plane duals.An example of an axiomatic system which isn't categorical is a geometrydescribed by the following four axioms (Smart): 1. There exist five points. 2. Each line is a subset of thosefive points. 3. There exist two lines. 4. Each line contains at least two points.One way to see that this is a non-categorical axiomatic system is to note that one can form a compatible system from two fundamentally different models, e.g., 1. Two disjoint lines each containing two points plus a separate point not on either line. 2. Two lines containing three pointseach which intersect in one of the points. The presence of an intersection in one model andnot the other implies that the models are fundamentally..

Axioms of subsets

For any set theoretic formula ,In other words, for any formula and set there is a subset of consisting exactly of those elements which satisfy the formula.

Absorption law

The law appearing in the definition of Boolean algebrasand lattice which states thatfor binary operators and (which most commonly are logical OR and logical AND). The two parts of the absorption law are sometimes called the "absorption identities" (Grätzer 1971, p. 5).

Axiom schema

Propositional calculus, first-order logic, and other theories in mathematical logic are defined by their axioms (or axiom schemata, plural: axiom schemata) and inference rules. An axiom schema is a sentential formula representing infinitely many axioms. These axioms are obtained by replacing variables in the schema by any formula. For example, the axiom schema(1)in propositional calculus represents theaxioms (2)(3)and so on.It is typical to define a theory by axiom schemata rather than axioms. If axioms but not their schemata are utilized, then substitution for variables should be incorporated into inference rules.

Surreal number

Surreal numbers are the most natural collection of numbers which includes both the real numbers and the infinite ordinal numbers of Georg Cantor. They were invented by John H. Conway in 1969. Every real number is surrounded by surreals, which are closer to it than any real number. Knuth (1974) describes the surreal numbers in a work of fiction.The surreal numbers are written using the notation , where , is the simplest number greater than 0, is the simplest number greater than 1, etc. Similarly, is the simplest number less than 0, etc. However, 2 can also be represented by , , , etc.Some simple games have abbreviated names that can be expressed in terms of surreal numbers. For example, , , for an integer , , , and . Most surreal numbers can be represented as hackenbush positions.

Join

In a lattice, any two elements and have a least upper bound. This least upper bound is often called the join of and , and is denoted by .One can also speak of the join operation in a general partially ordered set. If and are two elements in some partially ordered set , and if there is a smallest element (with respect to the given order) with the property that and , then is said to be the join of and .

Distributive lattice

A lattice which satisfies the identitiesis said to be distributive.

Complemented lattice

A complemented lattice is an algebraic structure such that is a bounded lattice and for each element , the element is a complement of , meaning that it satisfies 1. 2. . A related notion is that of a lattice with complements. Such a structure is a bounded lattice such that for each , there is such that and .One difference between these notions is that the class of complemented lattices forms a variety, whilst the class of lattices with complements does not. (The class of lattices with complements is a subclass of the variety of lattices, but it is not a subvariety of the class of lattices.) Every lattice with complements is a reduct of a complemented lattice, by the axiom of choice. To see this, let be a lattice with complements. For each , let denote the set of complements of . Because is a lattice with complements, for each , is nonempty, so by the axiom of choice, we may choose from each collection a distinguished complement for . This defines a function which..

Lattice homomorphism

Let and be lattices, and let . Then is a lattice homomorphism if and only if for any , and . Thus a lattice homomorphism is a specific kind of structure homomorphism. In other words, the mapping is a lattice homomorphism if it is both a join-homomorphism and a meet-homomorphism.If is a one-to-one lattice homomorphism, then it is a lattice embedding, and if a lattice embedding is onto, then it is a lattice isomorphism.An example of an important lattice isomorphism in universal algebra is the isomorphism that is guaranteed by the correspondence theorem, which states that if is an algebra and is a congruence on , then the mapping that is defined by the formulais a lattice isomorphism.

Meet

In a lattice, any two elements and have a greatest lower bound. This greatest lower bound is often called the meet of and , and is denoted by .One can also speak of the meet operation in a general partially ordered set. If and are two elements in some partially ordered set , and if there is a greatest element (with respect to the given order) with the property that and , then is said to be the meet of and .

Ordinal multiplication

Let and be totally ordered sets. Let be the Cartesian product and define order as follows. For any and , 1. If , then , 2. If , then and compare the same way as (i.e., lexicographical order) (Ciesielski 1997, p. 48; Rubin 1967; Suppes 1972). However, Dauben (1990, p. 104) and Moore (1982, p. 40) define multiplication in the reverse order.Like addition, multiplication is not commutative, but it is associative,(1)An inductive definition for ordinal multiplication states that for any ordinal number ,(2)(3)If is a limit ordinal, then is the least ordinal greater than any ordinal in the set (Suppes 1972, p. 212).

Math Topics
Check the price