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.
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.
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, 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..
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.
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 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.
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..
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...
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 .
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.
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 .
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.
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..
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.
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.
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 .
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 .
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..
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 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..
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 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 .
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..
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.
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,
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
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.
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
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.
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.
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..
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 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..
If a proposition is true for all , this is written . is one of the two so-called quantifiers, and translates the universal quantifier .The Wolfram Language command Experimental`ForAllRealQ[ineqs, vars] can be used to determine if the system of real equations and inequalities ineqs is satisfied for all real values of the variables vars.
A formula of first-order logic is in prenexnormal form if it is of the form(1)where each is a quantifier ("for all") or ("exists") and is quantifier-free.For example, the formula(2)is in prenex normal form, whereas formula(3)is not, where denotes OR.Every formula of first-order logic can be convertedto an equivalent formula in prenex normal form.
A reduction system is called finitely terminating (or Noetherian) if there are no infinite rewriting sequences. This property guarantees that any rewriting algorithm will terminate on any input.Ordering expressions may help to find out that a reduction system is finitely terminating. Orders used for this purpose are based on some measure of expression complexity. Existence of a reduction order compliant with rules of a term rewriting system guarantees that the system is finitely terminating.The problem of determining whether a given reduction system is finitely terminatingis recursively undecidable.
The theorem in set theory and logic that for all sets and ,(1)where denotes complement set of and is the empty set. The set is depicted in the above Venn diagram and clearly coincides with iff is empty.The corresponding theorem in a Boolean algebra states that for all elements of ,(2)The version of Poretsky's Law for logic can be derived from (2) using the rules of propositional calculus, namely for all propositions and ,(3)where "is equivalent to" means having the same truth table. In fact, in the following table, the values in the second and in the third column coincide if and only if the value in the first column is 0.( and not ) or (not and )000011101110
A statement claiming the existence of an object with given properties. In the language of set theory it can be formulated as follows,where is the universal set and is a given set contained in it. In other words, it states that set is nonempty.
A sentential formula that contains at least one free variable (Carnap 1958, p. 24). A sentential variable containing no free variables (i.e., all variables are bound) is called a closed sentential formula. Examples of open sentential formulas includewhich means that is even (over the domain of integers), andwhich means that and is not the product of two numbers (both greater than one), i.e., is prime.Closed sentential formulas are known as sentences, although it sometimes also happens that open sentential formulas are admitted as sentences (Carnap 1958, p. 25).
Two statements in logic are said to be equipollent if theyare deducible from each other.Two sets and are said to be equipollent iff there is a one-to-one correspondence (i.e., a bijection) from onto (Moore 1982, p. 10; Rubin 1967, p. 67; Suppes 1972, p. 91).The term equipotent is sometimes used instead of equipollent.
The terms of equational logic are built up from variables and constants using function symbols (or operations). Identities (equalities) of the form(1)where and are terms, constitute the formal language of equational logic. The syllogisms of equational logic are summarized below.1. Reflexivity:(2)2. Symmetry:(3)3. Transitivity:(4)4. For a function symbol and ,(5)5. For a substitution (cf. unification),(6)The above rules state that if the formula above the line is a theorem formally deducted from axioms by application of the syllogisms, then the formula below the line is also a formal theorem. Usually, some finite set of identities is given as axiom schemata.Equational logic can be combined with first-order logic. In this case, the fourth rule is extended onto predicate symbols as well, and the fifth rule is omitted. These syllogisms can be turned into axiom schemata having the form of implications to which Modus Ponens can be applied...
Consider expressions built up from variables and constants using function symbols. If , ..., are variables and , ..., are expressions, then a set of mappings between variables and expressions is called a substitution.If and is an expression, then is called an instance of if it is received from by simultaneously replacing all occurrences of (for ) by the respective .If and are two substitutions, then the composition of and (denoted ) is obtained from by removing all elements such that and all elements such that is one of , ..., .A substitution is called a unifier for the set of expressions if . A unifier for the set of expressions is called the most general unifier if, for any other unifier for the same set of expressions , there is yet another unifier such that .A unification algorithm takes a set of expressions as its input. If this set is not unifiable, the algorithm terminates and yields a negative result. If there exists a unifier for the input set of expressions,..
The rulewhere means "implies," which is the sole rule of inference in propositional calculus. This rule states that if each of and is either an axiom or a theorem formally deduced from axioms by application of inference rules, then is also a formal theorem.
A disjunctive syllogism is a valid argument form in propositional calculus, where and are propositions:For example, if someone is going to study law or medicine, and does not study law, they will therefore study medicine.
A well-formed formula is said to be true for the interpretation (written ) iff every sequence in (the set of all denumerable sequences of elements of the domain of ), satisfies . is said to be false for iff no sequence in satisfies .Then an interpretation is said to be a model for a set of well-formed formulas iff every well-formed formula in is true for (Mendelson 1997, pp. 59-60).
A statement is in disjunctive normal form if it is a disjunction (sequence of ORs) consisting of one or more disjuncts, each of which is a conjunction (AND) of one or more literals (i.e., statement letters and negations of statement letters; Mendelson 1997, p. 30). Disjunctive normal form is not unique.The Wolfram Language command LogicalExpand[expr] gives disjunctive normal form (with some contractions, i.e., LogicalExpand attempts to shorten output with heuristic simplification).Examples of disjunctive normal forms include (1)(2)(3)(4)(5)where denotes OR, denotes AND, and denotes NOT (Mendelson 1997, p. 30). Some authors also exclude statements containing both statement letters and their negations, which would exclude the third example above.Every statement in logic consisting of a combination of multiple , , and s can be written in disjunctive normal form...
A metatheorem in mathematical logic also known under the name "conditional proof." It states that if the sentential formula can be derived from the set of sentential formulas , then the sentential formula can be derived from .In a less formal setting, this means that if a thesis can be proven under the hypotheses , then one can prove that implies under hypothesis .
A statement which is rigorously known to be correct. A statement which is not true is called false, although certain statements can be proved to be rigorously undecidable within the confines of a given set of assumptions and definitions. Regular two-valued logic allows statements to be only true or false, but fuzzy logic treats "truth" as a continuum which can have any value between 0 and 1. The symbol is sometimes used to denote "true," although "T" is more commonly used in truth tables.
A theory is a set of sentences which is closed under logical implication. That is, given any subset of sentences in the theory, if sentence is a logical consequence of , then must also be in the theory.
The cut elimination theorem, also called the "Hauptsatz" (Gentzen 1969), states that every sequent calculus derivation can be transformed into another derivation with the same endsequent (bottom sequent) and in which the cut rule does not occur.All derivations without cuts posses the sub-formula property that all formulas occurring in a derivation are sub-formulas of the formulas from the endsequent.A sharpened form of theorem applies to the classical variant of sequent calculus. This form states that any derivation can be transformed to another derivation with the same endsequent and having the following properties. 1. It has no cuts. 2. It contains a so-called midsequent whose derivation contains no and , and the only inference rules occurring in the derivation below the midsequent are the and rules and structural rules. ..
Term rewriting systems are reduction systems in which rewrite rules apply to terms. Terms are built up from variables and constants using function symbols (or operations). Rules of term rewriting systems have the form , where both and are terms, is not a variable, and every variable from occurs in as well.A reduction step for term is defined as follows. If is a unifier for and , then is reduced to . If is a unifier for and where is a subterm of , then is reduced to a term obtained from by replacing with .
Let and be two rules of a term rewriting system, and suppose these rules have no variables in common. If they do, rename the variables. If is a subterm of (or the term itself) such that it is not a variable, and the pair is unifiable with the most general unifier , then and the result of replacing in by are called a critical pair.The fact that all critical pairs of a term rewriting system are joinable, i.e., can be reduced to the same expression, implies that the system is locally confluent.For instance, if and , then and would form a critical pair because they can both be derived from .Note that it is possible for a critical pair to be produced by one rule, used in two different ways. For instance, in the string rewrite "AA" -> "B", the critical pair ("BA", "AB") results from applying the one rule to "AAA" in two different ways...
A tautology is a logical statement in which the conclusion is equivalent to the premise. More colloquially, it is formula in propositional calculus which is always true (Simpson 1992, p. 2015; D'Angelo and West 2000, p. 33; Bronshtein and Semendyayev 2004, p. 288).If is a tautology, it is written . A sentence whose truth table contains only 'T' is called a tautology. The following sentences are examples of tautologies: (1)(2)(3)(Mendelson 1997, p. 26), where denotes AND, denotes "is equivalent to," denotes NOT, denotes OR, and denotes implies.
A law in (2-valued) logic which states there is no third alternative to truth or falsehood. In other words, for any statement , either or not- must be true and the other must be false. This law no longer holds in three-valued logic or fuzzy logic.
In logic, the term "homomorphism" is used in a manner similar to but a bit different from its usage in abstract algebra. The usage in logic is a special case of a "morphism" from category theory.Let , and be structures for a common language , and let . Then is a homomorphism from to provided that it satisfies the following: 1. For each constant , . 2. For each predicate symbol , if the arity of is , then3. For each function symbol (or operation) , if the arity of is , then for any ,For example, let and be (directed) graphs (the set is the set of vertices of , and is the set of vertices of , while is the relational representation of the edges of the graph , etc.). A homomorphism from to is a function such that for any vertices and of , and are connected by a directed edge (from to if and only if the vertices and are connected by a directed edge from to .Another example is available in the theory of ordered groups. Let and be ordered groups. (We are using the..
Let be a language of the first-order logic. Assume that the language has the following sets of nonlogical symbols: 1. is the set of constant symbols of . (These are nullary function symbols.) 2. is the set of predicate symbols of , and for each , is the arity of . The symbols in are also called relation symbols of the language . 3. is the set of function symbols of , and for each , is the arity of . The symbols in are also called operation symbols of the language . 4. is the universal quantifier symbol of . A structure for is a tuple , , where is a set (called the underlying set of ), and the following hold: 1. For each , , 2. For each , , 3. For each , .
A formal argument in logic in which it is stated that (1) and (where means "implies"), and (2) either or is true, from which two statements it follows that either or is true.
A relation is a strict order on a set if it is 1. Irreflexive: does not hold for any . 2. Asymmetric: if , then does not hold. 3. Transitive: and implies . Note that transitivity and irreflexivity combined imply that if holds, then does not.A strict order is total if, for any , either , , or .Every partial order induces a strict orderSimilarly, every strict order induces a partial order
A formula of first-order logic is said to be in Skolemized form (sometimes also called Skolem standard form or universal form) if it is of the formwhere is a quantifier-free formula in conjunctive normal form known as the matrix of the formula in question. Since is a conjunction of clauses each of which is a disjunction of literals, is often viewed as a set of the clauses. The process of placing a formula in Skolemized form is known as Skolemization.
In combinatorial logic minimization, a device known as a Karnaugh map is frequently used. It is similar to a truth table, but the various variables are represented along two axes and are arranged in such a way that only one input bit changes in going from one square to an adjacent square. It is also known as a Veitch diagram, K-map, or KV-map.The Karnaugh map may be used to quickly eliminate redundant operations in a Boolean function. The easiest to read Karnaugh maps are those drawn for a function in the form of a complete product or "sum of products," where the latter name also implies the use of and for the AND and OR operators. In a typical truth table for such a function, the inputs are enumerated using 0 for false and 1 for true, and ordered as a counting sequence when read as positive binary integers. A truth table for a function of four variables is illustrated below.00000000100010100111010000101001101011111000110010101001011011001110111110011110For..
The proof theories of propositional calculus and first-order logic are often referred to as classical logic.Intuitionistic propositional logic can be described as classical propositional calculusin which the axiom schema(1)is replaced by(2)Similarly, intuitionistic predicate logic is intuitionistic propositional logic combined with classical first-order predicate calculus.Intuitionistic logic is a part of classical logic, that is, all formulas provable in intuitionistic logic are also provable in classical logic. Although, even some basic theorems of classical logic do not hold in intuitionistic logic. Of course, the law of the excluded middle(3)does not hold in intuitionistic propositional logic.Here are some examples of propositional formulas that are not provable in intuitionistic propositional logic:(4)(5)Here are some examples of first-order formulas that are not provable in intuitionistic predicate logic:(6)(7)Truth..
A fundamental system of logic based on the concept of a generalized function whose argument is also a function (Schönfinkel 1924). This mathematical discipline was subsequently termed combinatory logic by Curry and "-conversion" or "lambda calculus" by Church. The system of combinatory logic is extremely fundamental, in that there are a relatively small finite numbers of atoms, axioms, and elementary rules. Despite the fact that the system contains no formal variables, it can be used for doing anything that can be done with variables in more usual systems (Curry 1977, p. 119).
Consider a formula in prenex normal form,If is the existential quantifier () and , ..., are all the universal quantifier variables such that , , then introduce the new function symbol and term . (If , then is a constant.) This function is called Skolem function (or Herbrand function).Now replace all occurrences of by this term and remove . When all existential quantifiers are removed, convert into conjunctive normal form. This process, which usually termed skolemization, results in a formula in Skolemized form. The resulting formula is unsatisfiable iff the source formula is unsatisfiable. Note that if the source formula is satisfiable, it is not necessarily equivalent to the resulting formula.
An interpretation of first-order logic consists of a non-empty domain and mappings for function and predicate symbols. Every -place function symbol is mapped to a function from to , and every -place predicate symbol is mapped to a function from to the set comprised of two values true and false.The domain is the range of all variables in formulas of first-order logic, and is called the domain of the interpretation.For a given interpretation, the truth table of anyformula is defined by the following rules. 1. The truth tables for propositional connectives apply to evaluate the value of ( AND ), ( OR ), ( implies ), and (NOT ). 2. ("for all , ") is true if is true for any element of as value of at free occurrences of in . Otherwise, is false. 3. ("there exists an such that ") is true if is true for at least one element of as value of at free occurrences of in . Otherwise, is false. Truth tables for infinite domains of interpretation are infinite...
In December 1920, M. Schönfinkel presented in a report to the Mathematical Society in Göttingen a new type of formal logic based on the concept of a generalized function whose argument is also a function (Schönfinkel 1924). This mathematical discipline was subsequently termed combinatory logic by Curry and "-conversion" or "-calculus" by Church. Combinators can be used in the study of algebra, topology, and category theory, and have found application in the study of programs in algorithmic languages.
A sequent is an expression , where and are (possibly empty) sequences of formulas. Here, is called the antecedent and is called the consequent. The informal understanding of sequents is that the sequent corresponds to . The initial sequent of all derivations is(1)The rules of inference for sequent calculus are divided in two categories: structural and logical. There are at least two logical rules for every propositional connective and every quantifier; one of them applies to the antecedent, whereas the other applies to the consequent. The structural rules are thinning,(2)contraction,(3)exchange,(4)and cut,(5)The logical rules are given by conjunction,(6)disjunction,(7)negation,(8)implication,(9)universal quantifier,(10)and existential quantifier(11)Here, the variable is free in and is obtained from by replacing all free occurrences of by . The variable occurring in the -succedent rule and the -antecedent rule is called..
A closed sentential formula is a sentential formula in which none of the variables are free (i.e., all variables are bound). Examples of closed sentential formulas are given bywhich expresses the commutativity of addition,andwhich expresses the infinitude of the primes.A closed sentential formula is called a sentence (Carnap 1958, pp. 24-25 and 85). However, in some language systems, open sentential formulas are also admitted as sentences (Carnap 1958, p. 25).
Assume , , and are lotteries. Denote " is preferred to " as , and indifference between them by . One version of the probability axioms are then given by the following, the last of which is the independence axiom: 1. Completeness: either or . 2. Transitivity: . 3. Continuity: a unique such that . 4. Independence: if , then for all and .
If is a class of recursively enumerable sets, then the set of Gödel numbers of functions whose domains belong to is called its index set. If the index set of is a recursive set, then either is empty or contains all recursively enumerable sets.Rice's theorem is an important result for computer science because it sets up boundaries for research in that area. It basically states that only trivial properties of programs are algorithmically decidable.
Let denote the recursive function of variables with Gödel number , where (1) is normally omitted. Then if is a partial recursive function, there exists an integer such thatwhere is Church's lambda notation. This is the variant most commonly known as Kleene's recursion theorem.Another variant generalizes the first variant by parameterization, and is the strongest form of the recursion theorem. This form states that for each , there exists a recursive function of variables such that is a injection and if is a total function, then for all , ..., , and ,Yet another and weaker variant of the recursion theorem guarantees the existence of a recursive function that is a fixed point for a recursive functional.
Determination of whether predicate is true or false for any given values of , ..., is called its decision problem. The decision problem for predicate is called recursively decidable if there is a total recursive function such that(1)Given the equivalence of computability and recursiveness, this definition may be restated with reference to computable functions instead of recursive functions.The halting problem was one of the first to be shown recursively undecidable. The formulation of recursive undecidability of the halting problem and many other recursively undecidable problems is based on Gödel numbers. For instance, the problem of deciding for any given whether the Turing machine whose Gödel number is is total is recursively undecidable. Hilbert's tenth problem is perhaps the most famous recursively undecidable problem.Most proofs of recursive undecidability use reduction. They show that recursive decidability..
Turing machines are defined by sets of rules that operate on four parameters: (state, tape cell color, operation, state). Let the states and tape cell colors be numbered and represented by quadruples of ordinal numbers. Then there exist algorithmic procedures that sequentially list all consistent sets of Turing machine rules. A set of rules is called consistent if any two quadruples differ in the first or second element out of the four. Any such procedure gives both an algorithm for going from any integer to its corresponding Turing machine and an algorithm for getting the index of any consistent set of Turing machine rules.Assume that one such procedure is selected. If Turing machine is defined by the set of quadruples whose index is , then is called the Gödel number of . The result of application of Turing machine with Godel number to is usually denoted .Given the equivalence of computability and recursiveness, it is common to use Gödel..
A set of integers is said to be recursively enumerable if it constitutes the range of a recursive function, i.e., if there exists a recursive function that can eventually generate any element in (Wolfram 2002, p. 1138). Any recursive set is also recursively enumerable.The union and intersection of two recursively enumerable sets are also recursively enumerable.Recursively undecidable problems give examples of recursively enumerable sets that are not recursive. For example, convergence of is known to be recursively undecidable, where denotes the Turing machine with Gödel number . Hence the set of all for which is convergent is not recursive. However, this set is recursively enumerable because it is the range of defined as follows:(1)A set is recursive iff both and its complement are recursively enumerable. This provides an approach to constructing additional sets that are not recursively enumerable. In particular, the..
A set of integers is said to be recursive if there is a total recursive function such that for and for . Any recursive set is also recursively enumerable.Finite sets, sets with finite complements, the odd numbers, and the prime numbers are all examples of recursive sets. The union and intersection of two recursive sets are themselves recursive, as is the complement of a recursive set.
A set of integers is productive if there exists a partial recursive function such that, for any , the following holds: If the domain of is a subset of , then is convergent, belongs to , and does not belong to the domain of , where denotes a recursive function whose Gödel number is .Productive sets are not recursively enumerable.
A recursively enumerable set is creative if its complement is productive. Creative sets are not recursive. The property of creativeness coincides with completeness. Namely, set is creative iff if it is many-one complete.Elementary arithmetic formulas are built up from 0, 1, 2, ..., , , , variables, connectives, and quantifiers. The set of all true arithmetic formulas is productive. Informally speaking, this means that no axiomatization of arithmetic can capture all true formulas and nothing else. For example, consider Peano arithmetic. Under the assumption that no false arithmetic formulas are provable in this theory, provable Peano arithmetic formulas form a creative set.
The complete products of a Boolean algebra of subsets generated by a set of cardinal number are the Boolean functions(1)where each may equal or its complement . For example, the complete products of are(2)Each Boolean function has a unique representation(up to order) as a union of complete products. For example,(3)(4)(5)(Comtet 1974, p. 186).
The formal mathematical study of the methods, structure, and validity of mathematical deduction and proof.In Hilbert's day, formal logic sought to devise a complete, consistent formulation of mathematics such that propositions could be formally stated and proved using a small number of symbols with well-defined meanings. The difficulty of formal logic was demonstrated in the monumental Principia Mathematica (1925) of Whitehead and Russell's, in which hundreds of pages of symbols were required before the statement could be deduced.The foundations of this program were obliterated in the mid 1930s when Gödel unexpectedly proved a result now known as Gödel's second incompleteness theorem. This theorem not only showed Hilbert's goal to be impossible, but also proved to be only the first in a series of deep and counterintuitive statements about rigor and provability in mathematics.A very simple form of logic is the study of "truth..
Roughly speaking, a matroid is a finite set together with a generalization of a concept from linear algebra that satisfies a natural set of properties for that concept. For example, the finite set could be the rows of a matrix, and the generalizing concept could be linear dependence and independence of any subset of rows of the matrix.Formally, a matroid consists of a finite set of elements together with a family of nonempty subsets of , called circuits, which satisfy the axioms 1. No proper subset of a circuit is a circuit, 2. If and , then contains a circuit. (Harary 1994, p. 40).An equivalent definition considers a matroid as a finite set of elements together with a family of subsets of , called independent sets, such that 1. The empty set is independent, 2. Every subset of an independent set is independent,3. For every subset of , all maximum independent sets contained in have the same number of elements. (Harary 1994, pp. 40-41).The number..
A class is a generalized set invented to get around Russell's antinomy while retaining the arbitrary criteria for membership which leads to difficulty for sets. The members of classes are sets, but it is possible to have the class of "all sets which are not members of themselves" without producing a paradox (since is a proper class (and not a set), it is not a candidate for membership in ).The distinction between classes and sets is a concept from vonNeumann-Bernays-Gödel set theory.
A set-theoretic term having a number of different meanings. Fraenkel (1953, p. 37) used the term as a synonym for "finite set." However, according to Russell's definition (Russell 1963, pp. 21-22), an inductive set is a nonempty partially ordered set in which every element has a successor. An example is the set of natural numbers , where 0 is the first element, and the others are produced by adding 1 successively.Roitman (1990, p. 40) considers the same construction in a more abstract form: the elements are sets, 0 is replaced by the empty set , and the successor of every element is the set . In particular, every inductive set contains a sequence of the formFor many other authors (e.g., Bourbaki 1970, pp. 20-21; Pinter 1971, p. 119), an inductive set is a partially ordered set in which every totally ordered subset has an upper bound, i.e., it is a set fulfilling the assumption of Zorn's lemma.The versions..
A set is a finite or infinite collection of objects in which order has no significance, and multiplicity is generally also ignored (unlike a list or multiset). Members of a set are often referred to as elements and the notation is used to denote that is an element of a set . The study of sets and their properties is the object of set theory.Older words for set include aggregate and set class. Russell also uses the unfortunate term manifold to refer to a set.Historically, a single horizontal overbar was used to denote a set stripped of any structure besides order, and hence to represent the order type of the set. A double overbar indicated stripping the order from the set and hence represented the cardinal number of the set. This practice was begun by set theory founder Georg Cantor.Symbols used to operate on sets include (which means "and" or intersection), and (which means "or" or union). The symbol is used to denote the set containing..
A proper subset of a set , denoted , is a subset that is strictly contained in and so necessarily excludes at least one member of . The empty set is therefore a proper subset of any nonempty set.For example, consider a set . Then and are proper subsets, while and are not.
A set whose elements can be numbered through from 1 to , for some positive integer . The number is called the cardinal number of the set, and is often denoted or . In other words, is equipollent to the set . We simply say that has elements. The empty set is also considered as a finite set, and its cardinal number is 0.A finite set can also be characterized as a set which is not infinite, i.e., as a set which is not equipollent to any of its proper subsets. In fact, if , and , a certain number of elements of do not belong to , so that .For all , the number of subsets having exactly elements (the so-called k-subsets, or combinations of elements out of ) is equal to the binomial coefficient(1)(2)Hence the number of subsets of (i.e., the cardinal number of its power set) is(3)(4)(5)by virtue of the binomial theorem.Assigning to each k-subset of its complement set defines a one-to-one correspondence between the set of k-subsets and the set of -subsets of . This proves the..
The word "rank" refers to several related concepts in mathematics involving graphs, groups, matrices, quadratic forms, sequences, set theory, statistics, and tensors.In graph theory, the graph rank of a graph is defined as , where is the number of vertices on and is the number of connected components (Biggs 1993, p. 25).In set theory, rank is a (class) function from sets to ordinal numbers. The rank of a set is the least ordinal number greater than the rank of any member of the set (Mirimanoff 1917; Moore 1982, pp. 261-262; Rubin 1967, p. 214). The proof that rank is well-defined uses the axiom of foundation.For example, the empty set has rank 0 (since it has no members and 0 is the least ordinal number), has rank 1 (since , its only member, has rank 0), has rank 2, and has rank . Every ordinal number has itself as its rank.Mirimanoff (1917) showed that, assuming the class of urelements is a set, for any ordinal number , the class..
A set is said to be nowhere dense if the interior of the set closure of is the empty set. For example, the Cantor set is nowhere dense.There exist nowhere dense sets of positive measure. For example, enumerating the rationals in as and choosing an open interval of length containing for each , then the union of these intervals has measure at most 1/2. Hence, the set of points in but not in any of has measure at least 1/2, despite being nowhere dense.
Given a set with a subset , the complement (denoted or ) of with respect to is defined as(1)Using set difference notation, the complement isdefined by(2)If , then(3)where is the empty set. The complement is implemented in the Wolfram Language as Complement[l, l1, ...].Given a single set, the second probabilityaxiom gives(4)Using the fact that ,(5)(6)This demonstrates that(7)Given two sets,(8)(9)
The disjoint union of two sets and is a binary operator that combines all distinct elements of a pair of given sets, while retaining the original set membership as a distinguishing characteristic of the union set. The disjoint union is denoted(1)where is a Cartesian product. For example, the disjoint union of sets and can be computed by finding(2)(3)so(4)(5)
The set difference is defined byHere, the backslash symbol is defined as Unicode U+2216.The set difference is therefore equivalent to the complement set, and is implemented in the Wolfram Language as Complement[A, B].The symbol is sometimes also used to denote a set difference (Smith et al. 1997, p. 68).
Let and be sets, and let be a relation on . Then is a concurrent relation if and only if for any finite subset of , there exists a single element of such that if , then . Examples of concurrent relations include the following: 1. The relation on either the natural numbers, the integers, the rational numbers, or the real numbers. 2. The relation between elements of an extension of a field , defined by3. The containment relation between open neighborhoods of a given point of a topological space .
The reflexive reduction of a binary relation on a set is the minimum relation on with the same reflexive closure as . Thus for any elements and of , provided that and are distinct and .
The transitive reduction of a binary relation on a set is the minimum relation on with the same transitive closure as . Thus for any elements and of , provided that and there exists no element of such that and .The transitive reduction of a graph is the smallest graph such that , where is the transitive closure of (Skiena 1990, p. 203).
The reflexive closure of a binary relation on a set is the minimal reflexive relation on that contains . Thus for every element of and for distinct elements and , provided that .
The transitive closure of a binary relation on a set is the minimal transitive relation on that contains . Thus for any elements and of provided that there exist , , ..., with , , and for all .The transitive closure of a graph is a graph which contains an edge whenever there is a directed path from to (Skiena 1990, p. 203). The transitive closure of a graph can be computed using TransitiveClosure[g] in the Wolfram Language package Combinatorica` .
A relation on a set is reflexive provided that for every in .
A function mapping a set ( modulo ), where is an equivalence relation in , is called a canonical map.
A relation on a set is transitive provided that for all , and in such that and , we also have .
A relation on a set is irreflexive provided that no element is related to itself; in other words, for no in .
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.
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 .
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 .
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 .
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, ..., .
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).
A Hasse diagram is a graphical rendering of a partially ordered set displayed via the cover relation of the partially ordered set with an implied upward orientation. A point is drawn for each element of the poset, and line segments are drawn between these points according to the following two rules: 1. If in the poset, then the point corresponding to appears lower in the drawing than the point corresponding to . 2. The line segment between the points corresponding to any two elements and of the poset is included in the drawing iff covers or covers . Hasse diagrams are also called upward drawings. Hasse diagrams for a graph are implemented as HasseDiagram[g] in the Wolfram Language package Combinatorica` , where is a directed acyclic Combinatorica graph object.The above figures show the Hasse diagrams for Boolean algebras of orders , 3, 4, and 5. In particular, these figures illustrate the partition between left and right halves of the lattice, each..
An ideal of a partial order is a subset of the elements of which satisfy the property that if and , then . For disjoint chains in which the th chain contains elements, there are ideals. The number of ideals of a -element fence poset is the Fibonacci number .
A partially ordered set is defined as an ordered pair . Here, is called the ground set of and is the partial order of .
A totally ordered set is said to be well ordered (or have a well-founded order) iff every nonempty subset of has a least element (Ciesielski 1997, p. 38; Moore 1982, p. 2; Rubin 1967, p. 159; Suppes 1972, p. 75). Every finite totally ordered set is well ordered. The set of integers , which has no least element, is an example of a set that is not well ordered.An ordinal number is the ordertype of a well ordered set.
A relation "" is a partial order on a set if it has: 1. Reflexivity: for all . 2. Antisymmetry: and implies . 3. Transitivity: and implies .For a partial order, the size of the longest chain (antichain) is called the partial order length (partial order width). A partially ordered set is also called a poset.A largest set of unrelated vertices in a partial order can be found using MaximumAntichain[g] in the Wolfram Language package Combinatorica` . MinimumChainPartition[g] in the Wolfram Language package Combinatorica` partitions a partial order into a minimum number of chains.
A partial order defined by (, ), (, ) for odd .
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.
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)...
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 .
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.
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,..
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.
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 .
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 .
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.
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.
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 .
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.
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.
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.
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.
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 .
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 .
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.
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 .
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..
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.
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)...
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 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.
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.
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.
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.
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...
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.
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..
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.
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..
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 .
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.
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.
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..
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.
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 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...
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 ...
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.
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..
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..
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).
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..
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 .
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.
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 .
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..
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.
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 .
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.
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 , , .
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.
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..
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.
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
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
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 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...
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 .
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..
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.
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.
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.
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, , , , , ....
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 .
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)...
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..
"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."
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.
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..
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.
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..
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.
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).
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 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.
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 .
A lattice which satisfies the identitiesis said to be distributive.
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..
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.
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 .
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).