# Logic

## Logic Topics

Sort by:

### Russell's antinomy

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

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

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

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

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

### Destructive dilemma

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

### Ultraproduct

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

### Transfer principle

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

### Superstructure

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

### Satisfaction

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

### Nonstandard analysis

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

### &321;o&347;' theorem

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

### Hyperreal number

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

### Hyperfinite set

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

### Cup

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

### Connective

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

### Xnor

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

### Biconditional

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

### Nonequivalent

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

### Negation

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

### Alternative denial

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

### Venn diagram

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

### Formal language

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

### Propositional calculus

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

### For all

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.

### Prenex normal form

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.

### Finitely terminating

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.

### Existential sentence

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.

### Open sentential formula

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).

### Equipollent

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.

### Equational logic

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...

### Unification

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,..

### Modus ponens

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.

### Disjunctive syllogism

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.

### Model

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).

### Disjunctive normal form

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...

### True

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.

### Theory

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.

### Cut elimination theorem

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 system

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 .

### Critical pair

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...

### Tautology

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.

### Law of the excluded middle

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.

### Structure homomorphism

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..

### Structure

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 , .

### Constructive dilemma

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.

### Strict order

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

### Skolemized form

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.

### Karnaugh map

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..

### Intuitionistic logic

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..

### Combinatory logic

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).

### Skolem function

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.

### Interpretation

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...

### Combinator

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.

### Sequent calculus

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..

### Closed sentential formula

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).

### Independence axiom

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 .

### Rice's theorem

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.

### Kleene's recursion theorem

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.

### Recursively undecidable

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..

### G&ouml;del number

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..

### Recursively enumerable set

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..

### Recursive set

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.

### Productive 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.

### Creative set

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.

### Logic

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..

### Fallacy

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

### Sentence

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

### Horn clause

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

### Herbrand universe

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

### Herbrand base

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

### Ground literal

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

### Ground clause

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

### Resolution principle

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

### Ground atom

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

### Grammar

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

### Regular expression

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

### Reduction system

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

### Reduction order

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

### Game of logic

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

### Disjunction

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

### Presburger arithmetic

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

A paradox also known as the surprise examination paradoxor prediction paradox.A prisoner is told that he will be hanged on some day between Monday and Friday, but that he will not know on which day the hanging will occur before it happens. He cannot be hanged on Friday, because if he were still alive on Thursday, he would know that the hanging will occur on Friday, but he has been told he will not know the day of his hanging in advance. He cannot be hanged Thursday for the same reason, and the same argument shows that he cannot be hanged on any other day. Nevertheless, the executioner unexpectedly arrives on some day other than Friday, surprising the prisoner.This paradox is similar to that in Robert Louis Stevenson's "bottle imp paradox," in which you are offered the opportunity to buy, for whatever price you wish, a bottle containing a genie who will fulfill your every desire. The only catch is that the bottle must thereafter be resold for a price..

The paradox of a man who states "I am lying." If he is lying, then he is telling the truth, and vice versa. Another version of this paradox is the Epimenides paradox. Such paradoxes are often analyzed by creating so-called "metalanguages" to separate statements into different levels on which truth and falsity can be assessed independently. For example, Bertrand Russell noted that, "The man who says, 'I am telling a lie of order ' is telling a lie, but a lie of order " (Gardner 1984, p. 222).

A lamp is turned on for 1/2 minute, off for 1/4 minute, on for 1/8 minute, etc. At the end of one minute, the lamp switch will have been moved times, where is aleph-0. Will the lamp be on or off? This paradox is actually nonsensical, since it is equivalent to asking if the "last" integer is even or odd.

### Tarski's theorem

Tarski's theorem says that the first-order theory of reals with , , , and allows quantifier elimination. Algorithmic quantifier elimination implies decidability assuming that the truth values of sentences involving only constants can be computed. However, the converse is not true. For example, the first-order theory of reals with , , and is decidable, but does not allow quantifier elimination.Tarski's theorem means that the solution set of a quantified system of real algebraic equations and inequations is a semialgebraic set (Tarski 1951, Strzebonski 2000).Although Tarski proved that quantifier elimination was possible, his method was totally impractical (Davenport and Heintz 1988). A much more efficient procedure for implementing quantifier elimination is called cylindrical algebraic decomposition. It was developed by Collins (1975) and is implemented as CylindricalDecomposition[ineqs, vars]...

### G&ouml;del's first incompleteness theorem

Gödel's first incompleteness theorem states that all consistent axiomatic formulations of number theory which include Peano arithmetic include undecidable propositions (Hofstadter 1989). This answers in the negative Hilbert's problem asking whether mathematics is "complete" (in the sense that every statement in the language of number theory can be either proved or disproved).The inclusion of Peano arithmetic is needed, since for example Presburger arithmetic is a consistent axiomatic formulation of number theory, but it is decidable.However, Gödel's first incompleteness theorem also holds for Robinson arithmetic (though Robinson's result came much later and was proved by Robinson).Gerhard Gentzen showed that the consistency and completeness of arithmetic can be proved if transfinite induction is used. However, this approach does not allow proof of the consistency of all mathematics...

### G&ouml;del's completeness theorem

If is a set of axioms in a first-order language, and a statement holds for any structure satisfying , then can be formally deduced from in some appropriately defined fashion.

### Richardson's theorem

Let be the class of expressions generated by 1. The rational numbers and the two real numbers and , 2. The variable , 3. The operations of addition, multiplication,and composition, and 4. The sine, exponential,and absolute value functions. Then if , the predicate "" is recursively undecidable.

### Lambda calculus

A formal logic developed by Alonzo Church and Stephen Kleene to address the computable number problem. In the lambda calculus, is defined as the abstraction operator. Three theorems of lambda calculus are -conversion, -conversion, and -conversion. Lambda-reduction (also called lambda conversion) refers to all three.

### Quantifier elimination

Quantifier elimination is the removal of all quantifiers (the universal quantifier and existential quantifier ) from a quantified system. A first-order theory allows quantifier elimination if, for each quantified formula, there exists an equivalent quantifier-free formula. Examples of such theories include the real numbers with , , , and , and the theory of complex numbers with , , and . Quantifier elimination is implemented in as Resolve[expr].Unfortunately, the worst-case time-complexity for real quantifier elimination is doubly exponential in the number of quantifier blocks (Weispfenning 1988, Davenport and Heintz 1988, Heintz et al. 1989, Caviness and Johnson 1998).

### Goodstein's theorem

For all , there exists a such that the th term of the Goodstein sequence . In other words, every Goodstein sequence converges to 0.The secret underlying Goodstein's theorem is that the hereditary representation of in base mimics an ordinal notation for ordinals less than some number. For such ordinals, the base bumping operation leaves the ordinal fixed whereas the subtraction of one decreases the ordinal. But these ordinals are well ordered, and this allows us to conclude that a Goodstein sequence eventually converges to zero.Amazingly, Paris and Kirby showed in 1982 that Goodstein's theorem is not provable in ordinary Peano arithmetic (Borwein and Bailey 2003, p. 35).

### Cap

The symbol , used for the intersection of sets, and sometimes also for the logical connective AND instead of the symbol (wedge). In fact, for any two sets and and this equivalence demonstrates the connection between the set-theoretical and the logical meaning.The term "cap" is also used to refer to the topological object produced by puncturing a surface a single time, attaching two zips around the puncture in opposite directions, distorting the hole so that the zips line up, and then zipping up. The cap is topologically trivial in the sense that a surface with a cap is topologically equivalent to a surface without one.

Zeno's paradoxes are a set of four paradoxes dealingwith counterintuitive aspects of continuous space and time. 1. Dichotomy paradox: Before an object can travel a given distance , it must travel a distance . In order to travel , it must travel , etc. Since this sequence goes on forever, it therefore appears that the distance cannot be traveled. The resolution of the paradox awaited calculus and the proof that infinite geometric series such as can converge, so that the infinite number of "half-steps" needed is balanced by the increasingly short amount of time needed to traverse the distances. 2. Achilles and the tortoise paradox: A fleet-of-foot Achilles is unable to catch a plodding tortoise which has been given a head start, since during the time it takes Achilles to catch up to a given position, the tortoise has moved forward some distance. But this is obviously fallacious since Achilles will clearly pass the tortoise! The resolution..

### Strange loop

A strange loop is a phenomenon in which, whenever movement is made upwards or downwards through the levels of some hierarchical system, the system unexpectedly arrives back where it started. Hofstadter (1989) uses the strange loop as a paradigm in which to interpret paradoxes in logic (such as Grelling's paradox, the liar's paradox, and Russell's antinomy) and calls a system in which a strange loop appears a tangled hierarchy.Canon 5 from Bach's Musical Offering (sometimes known as Bach's endlessly rising canon) is a musical piece that continues to rise in key, modulating through the entire chromatic scale until it ends in the same key in which it began. This is the first example cited by Hofstadter (1989) as a strange loop.Other examples include the endlessly rising stairs in M. C. Escher 1960 lithograph Ascending and Descending, the endlessly falling waterfall in his 1961 lithograph Waterfall, and the pair of hands drawing each..

### Truth table

A truth table is a two-dimensional array with columns. The first columns correspond to the possible values of inputs, and the last column to the operation being performed. The rows list all possible combinations of inputs together with the corresponding outputs. For example, the following truth table shows the result of the binary AND operator acting on two inputs and , each of which may be true or false.FFFFTFTFFTTTThe following Wolfram Language code can be used to generate a truth table for n levels of operator op. TruthTable[op_, n_] := Module[ { l = Flatten[Outer[List, Sequence @@ Table[{True, False}, {n}]], n - 1], a = Array[A, n] }, DisplayForm[ GridBox[Prepend[Append[, op @@ ]& /@ l, Append[a, op @@ a]], RowLines -> True, ColumnLines -> True] ] ]

### Conjunctive normal form

A statement is in conjunctive normal form if it is a conjunction (sequence of ANDs) consisting of one or more conjuncts, each of which is a disjunction (OR) of one or more literals (i.e., statement letters and negations of statement letters; Mendelson 1997, p. 30). Examples of conjunctive normal forms include (1)(2)(3)(4)where denotes OR, denotes AND, and denotes NOT (Mendelson 1997, p. 30).Every statement in logic consisting of a combination of multiple , , and s can be written in conjunctive normal form.An expression can be put in conjunctive normal form using the WolframLanguage using the following code: ConjunctiveNormalForm[f_] := Not[LogicalExpand[Not[f]]] //. { Not[a_Or] :> And @@ (Not /@ List @@ a), Not[a_And] :> Or @@ (Not /@ List @@ a) }

### Robbins axiom

The logical axiomwhere denotes NOT and denotes OR, that, when taken together with associativity and commutativity, is equivalent to the axioms of Boolean algebra.The Robbins operator can be defined in the WolframLanguage by Robbins := Function[{x, y}, ! (! (! y \[Or] x) \[Or] ! (x \[Or] y))]That the Robbins axiom is a true statement in Booleanalgebra can be verified by examining its truth table.TTTTFTFTFFFF

Determining the length of a country's coastline is not as simple as it first appears, as first considered by L. F. Richardson (1881-1953) and sometimes known as the Richardson effect (Mandelbrot 1983, p. 28). In fact, the answer depends on the length of the ruler you use for the measurements. A shorter ruler measures more of the sinuosity of bays and inlets than a larger one, so the estimated length continues to increase as the ruler length decreases.In fact, a coastline is an example of a fractal, and plotting the length of the ruler versus the measured length of the coastline on a log-log plot gives a straight line, the slope of which is the fractal dimension of the coastline (and will be a number between 1 and 2).

### Quantified system

A quantified system of real algebraic equations and inequalities in variables is an expressionwhere is a quantifier ( or ) and is a system of real algebraic equations and inequalities in . By Tarski's theorem, the solution set of a quantified system of real algebraic equations and inequalities is a semialgebraic set.