First-order predicate calculus or first-order logic is a theory in Symbolic logic that formalizes quantified statements such as "there exists an object with the property that..." or "for all objects, the following is true...". First-order logic is distinguished from higher-order logic in that it does not allow statements such as "for every property, the following is true..." or "there exists a set of objects such that...". Nevertheless, first-order logic is strong enough to formalize all of Set theory and thereby virtually all of Mathematics. It is the classical logical theory underlying mathematics.
Like any logical theory, first-order calculus consists of
There are two types of axioms: the logical axioms which embody the general truths about proper reasoning involving quantified statements, and the axioms describing the subject matter at hand, for instance axioms describing sets in set theory or axioms describing numbers in arithmetic.
While the set of inference rules in first-order calculus is finite, the set of axioms may very well be and often is infinite. However we require that there is a general Algorithm which can decide for a given well-formed formula whether it is an axiom or not. Furthermore, there should be an algorithm which can decide whether a given application of an inference rule is correct or not.
The well-formed formulas contain
The object, predicate and function constants will typically depend on the particular domain we are talking about.
Instead of giving the lengthy definition of well-formed formulas, we will simply look at some examples from arithmetic together with their ordinary interpretation. Our domain here is the set of natural numbers:
For every number x there exists a bigger number y. That's true.
There exists a number y which is bigger than every number x. That's not true.
If a number x is divisible by 6, then it is also divisible by 3. True.
There exists a number x such that there doesn't exist a smaller number y. True (take x=0).
Now one would have to write down 15 logical axioms and 2 inference rules to completely specify the first-order calculus. How can one be sure that those axioms and rules are enough? This is the subject of Gödel's completeness theorem: if you start out with some subject matter axioms and you look at a certain statement, then it is possible to prove that statement using only the subject matter axioms, the 15 logical axioms and the two inference rules if and only if the statement is true in every domain in which the subject matter axioms are true.
The Peano axioms for the natural numbers are sometimes formulated as second-order statements (the induction axiom talks about all "properties" or all "sets of numbers"), but this is not necessary if one is willing to allow infinitely many first-order axioms. A first-order version of the Peano axioms follows.
We are using the object constants 0 and 1, the function constants + and *, and the predicate constant =. Here are the axioms:
Axioms 1, 2 and 7 are the traditional Peano axioms while axioms 3-6 serve to define addition and multiplication. If one omits the function constant * and axioms 5 and 6 and allows in scheme 7 only formulas without *, then one gets the very interesting Presburger arithmetic
A logical calculus is a formal, axiomatic system for recursively generating well-formed formulas (wffs). Essentially, it's a definition of a vocabulary, rules for the formation of well-formed formulas (wffs), and rules of inference permitting the generation of all valid argument forms expressible in the calculus.
The propositional calculus is the foundation of Symbolic logic; more complex logical calculi are usually defined by adding new operators and rules of transformation to it. It is generally defined as follows:
The vocabulary is composed of:
The rules for the formation of wffs:
Repeated applications of these three rules permit the generation of complex wffs. For example:
The propositional calculus has ten inference rules. The first eight are non-hypothetical, meaning that they do not involve hypothetical reasoning: specifically, the introduction of hypothetical premises is not used; the last two rules are hypothetical. These rules are introduction and elimination rules for each logical operator, used for deriving argument forms.
Negative elimination is basically the rule of double negatives: "it's not the case that it's not raining" means that it's raining. Likewise, it's logically consistent to claim that "it's raining" means that "it's not not raining".
Formally:
¬ ¬ A ∴ A also
¬ ¬ ¬ A ∴ ¬ A
Conjunction introduction is the inference that, if A is true, and B is true, then the conjunction A and B is true.
For example, if it's true that it's raining, and it's true that I'm inside, then it's true that it's raining, and I'm inside.
Formally:
A B ∴ ( A ∧ B )
Conjunction elimination is the inference that, if the conjunction A and B is true, then A is true, and B is true.
For instance, if it's true that it's raining, and I'm inside, then one may assert either term of the conjunction alone: it's raining, or I'm inside.
Formally:
( A ∧ B ) ∴ A or
( A ∧ B ) ∴ B
Disjunction introduction is the principle that, if A is true, then it's true that either A or B is true.
For example, if it's true that it's raining outside, it's trivially true that either it's raining outside, or my car is freshly waxed. Since a disjunction is true if at least one of the terms is true, and we know that one of the terms is true, the second term is irrelevant for determining the truth value of the disjunction.
Formally:
A ∴ ( A ∨ B )
Disjunction elimination is the inference that, if A or B is true, and both A and B entail C, then we may justifiably infer C.
For example, it's true that either I'm inside or I'm outside. It's also true that if I'm inside, I have my wallet on me. It's also true that if I'm outside, I have my wallet on me. Given these three premises, it follows that I have my wallet on me.
Formally:
( A ∨ B ) ( A → C ) ( B → C ) ∴ C
Biconditional introduction is the inference that, if B follows from A, and A follows from B, then A if and only if B.
For example: if I'm breathing, then I'm alive; also, if I'm alive, then I'm breathing. Therefore, I'm breathing if and only if I'm alive.
Formally:
( A → B ) ( B → A ) ∴ ( A ↔ B )
Biconditional elimination allows one to infer a conditional from a biconditional: if ( A ↔ B ) is true, then one may infer one direction of the biconditional, either ( A → B ) or ( B → A ).
For example, if it's true that I'm breathing if and only if I'm alive, then it's true that if I'm breathing, I'm alive; likewise, it's true that if I'm alive, I'm breathing.
Formally:
( A ↔ B ) ∴ ( A → B ) also
( A ↔ B ) ∴ ( B → A )
Modus ponens (Latin: mode that affirms) is a valid, simple Argument form:
or in symbols:
P → Q
P
∴ Q
The argument form has two premises. The first premise is the "if-then" or
conditional claim, namely that P implies Q. The second premise is that P,
the antecedent of the conditional claim, is true. From these two
premises it can be logically concluded that Q, the consequent of the
conditional claim, must be true as well.
Here is an example of an argument that fits the form modus ponens:
For an amusing dialog that problematizes modus ponens, see Lewis Carroll's "What the Tortoise Said to Achilles".
Conditional proof takes the form of asserting a conditional, and proving that the premise or antecedent of the conditional necessarily leads to the conclusion. Proving this requires assuming the premise and deriving, from that assumption, the consequent of the conditional. By proving the connection between the antecedent and the consequent, the assumption of the antecedent is justified post hoc.
For example, I claim that "if you don't leave now, you'll be late for work". I prove it with the following argument:
∴ If you don't leave now, you'll be late for work.
Note that I haven't proved that you'll be late for work: I've only proven the conditional, that the consequent follows necessarily from the antecedent.
Introducing an hypothesis means adding a wff to a derivation not originally present as a premise; discharging the hypothesis means eliminating the wff justifiably--any wffs correctly derived from the hypothesis justify the introduction of the hypothesis after the fact.
With wffs and rules of inference, it's possible to derive wffs; the
derivation is a valid argument form, while the derived wff is known as a
Lemma.
Reductio ad absurdum (from Latin Reduced to an absurdity) is a tool of logic, also known as "proof by contradiction".
Say we wish to prove hypothesis A. The procedure is to show that assuming "not A" (i.e. that A is false) leads to a logical contradiction. Thus A cannot be false, and must therefore be true. For examples, see Irrational number and Cantor's diagonal argument.
It is important to note that to form a valid proof, it must be demonstrated that "not A" implies a property that is actually false or actually incompatible with "not A". The danger here is the logical fallacy of argument from lack of imagination, where it is proven that "not A" implies a property "B", which looks false, but is not really proven to be false. Historical examples of this fallacy include false proofs of the fifth postulate a.k.a. parallel postulate of Euclid (see Non-Euclidean geometry).
Symbolic logic, or formal or deductive logic, is an attempt to codify and formalize the processes of reasoning, or logic. Logical statements are expressed as symbolic strings, in a precise, compact and unambiguous notation (sometimes described as a logical calculus), similar to notations used in mathematics. Axioms, statements which are accepted without proof, are identified, and the valid rules of argumentation (transformation rules) are defined.
There are many different systems of symbolic logic. A system of symbolic logic has a number of components: the set of acceptable sentences, called well-formed formulas (or wffs); transformation rules for deriving new formulas from one or more initial formulas; the set of axioms, which is a subset of the set of wffs. The sets of wffs and axioms can be finite or infinite, so long as they are recursive; i.e. so long as there exists a procedure for determining whether any given sentence is a wff or axiom, which could be carried out in a finite number of steps by a device such as a Turing machine (sometimes, it is enough to require that these sets be recursively enumerable).
The theorems of the system are the axioms and all the wffs that can be derived from the axioms by a finite number of applications of the transformation rules. In systems of natural deduction the set of axioms is empty and the transformation rules correspond to patterns of reasoning such as modus ponens whose validity, or truth-preserving nature, is easily recognized.
For a symbolic logic system to be useful it helps to have two additional properties; soundness and completeness. These properties relate the system of symbolic logic to some underlying model. The property of soundness states that if a theorem can be proven in the symbolic system then it is also true in the model. The property of completeness states that if the theorem is true in a model, then there is some proof for it in the associated symbolic logic. A symbolic logic is said to be determined by a model if it is both sound and complete. Logics of this kind are useful for systems of mechanical theorem proving.
Metalogic is the study of different systems of symbolic logic, and their properties. We can not only prove statements in a logical system; we can also prove statements about logical systems. The most important result along these lines are Gödel's incompleteness theorems which essentially show that every sufficiently powerful logical system does contain sentences which can be neither proved nor refuted from within the system.
There are three main types of logical systems which are used: propositional calculus, predicate calculus, and modal logic.
Propositional logic deals with the logic of individual sentences. The primary system here is the classical system, which is the system most commonly used. Various alternatives to the classical system have been studied, including:
Predicate logic extends propositional calculus to deal with predication and quantification. Again we have a classical system, and various deviations from this system. Most of the different systems of propositional calculus can be extended in this manner to produce systems of predicate calculus. There are two main varieties of systems of predicate calculus: first-order predicate calculus, which allows quantification over objects and is the standard logic used in mathematics (see set theory); and higher-order predicate calculus, which permits in addition quantification over predicates and predication of predicates.
There exist proofs for the soundness and completeness of both predicate and first order logic (see Goedels completeness theorem). Second and higher order logics are not complete however; in other words in all second and higher order logics there are theorems which are true in any model but are not provable within the symbolic system.
The term modal logic has two meanings. In a restricted sense, it means the logic of necessity and possibility. But more broadly, it also includes other logics with a similar structure: deontic logics (which deal with ideas of permission and obligation), temporal logics (which deal with the relationships of past, present and future between events), and doxastic logic (which deals with belief). What all these systems have in common is that they involve the application of unary operators (called modal operators) to statements of either propositional or predicate calculus. It is in this broader sense that the term is used here.
The various systems of modal logic include K, M, S4, S5 and B. The systems differ in having different axioms.
In epistemology, an axiom is a self-evident truth upon which other knowledge must rest, from which other knowledge is built up. To say the least, not all epistemologists agree that axioms, understood in that sense, exist.
As the word "axiom" is understood in mathematics, an axiom is not a proposition that is self-evident. Rather, it simply means a starting point in a logical system. For example, in some rings, the operation of multiplication is commutative, and in some it is not; those rings in which it is are said to satisfy the "axiom of commutativity of multiplication." Another name for an axiom is postulate. An axiom is an elementary basis for a formal logic system that together with the rules of inference define a logic.
For instance, (misquoting Peano) simple arithmetic including addition can be defined and many theorems proven by assuming
Using these axioms, and defining the customary short names 1, 2, 3, and so on for inc(0), inc(inc(0)), inc(inc(inc(0))) respectively, we can show that:
and
1 + 2 = 1 + inc(1) Expansion of abbreviation (2 = inc(1))
1 + 2 = inc(1) + 1 Axiom 4
1 + 2 = 2 + 1 Abbreviation (2 = inc(1))
1 + 2 = 2 + inc(0) Expansion of abbreviation (1 = inc(0))
1 + 2 = inc(2) + 0 Axiom 4
1 + 2 = 3 Axiom 3
Any fact that we can derive from the axioms need not be an axiom. Anything that we cannot derive from the axioms and for which we also cannot derive the negation might reasonably added as an axiom.
Probably the most famous very early set of axiom are the 4+1 postulates of Euclid. These turn out to be fairly incomplete, actually, and many more postulates are necessary to completely characterize his geometry (Hilbert used 23).
I say 4+1 since the 5th postulate (through a point outside a line there is exactly one parallel) was suspected to be derivable from the first 4 for nearly two millennia. Ultimately, the fifth postulate was found to be independent of the first four. Indeed, one can assume that no parallels through a point outside a line exist, that exactly one exists, or that infinitely many exist. These choices give us alternative forms of geometry in which the interior angles of a triangle add up to less than, exactly or more than a straight line respectively and are known as elliptic, Euclidean and hyperbolic geometries. The general theory of relativity is essentially a claim that mass gives space hyperbolic geometry.
The fact that alternative forms of geometry might exist was very troubling to mathematicians of the 19th century and in similar developments, say Boolean Algebra, there were generally elaborate efforts taken to derive the system from normal arithmetic systems. Galois showed just before his untimely death that these efforts were largely wasted but that the grand parallels between axiomatic systems could be put to good use as he algebraicly solved many classical geometrical problems. Ultimately, the abstract parallels between algebraic systems were seen to be more important than the details and modern algebra was born.
In the twentieth century, Gödel's Incompleteness Theorem showed that no explicit list of axioms sufficiently large for ordinary mathematics could be both (1) complete (i.e. every statement can be either proved or disproved) and (2) consistent (i.e. no statement can be both proved and disproved).
Giuseppe Peano proposed the following 5 axioms for the natural numbers; they have come to be known as the Peano axioms or Peano postulates.
These axioms are sometimes paraphrased differently, starting at 1 instead of 0. These axioms are given here in a second-order predicate calculus form. See first-order predicate calculus for a way to rephrase these axioms to be first-order.
Although natural numbers satisfy these axioms, there are other, nonstandard models of arbitrary large cardinality - by Compactness theorem the existence of infinite natural numbers cannot be excluded in any axiomatization.
When the axioms were first proposed, people such as Bertrand Russell agreed these axioms implicitly defined what we mean by a "natural number". Henri Poincaré was more cautious, saying they only defined natural numbers if they were consistent. If a proof can exist that starts from just these axioms, and derives a contradiction such as P AND NOT P, then the axioms are inconsistent, and don't really define anything. David Hilbert posed a problem of proving consistency using only finite logic as one of the problems on his famous list. The motivation was to eliminate infinity, by justifying it with this proof, and show that it brings nothing new.
But in 1931, Kurt Goedel in his celebrated Second Incompleteness Theorem showed such a proof cannot exist. It is even impossible to prove consistency of Peano arithmetic while assuming the axioms themselves. Furthermore, we can never prove that any axiom system is consistent within the system itself, if it is at least as strong as Peano's axioms.
In 1936, Gerhard Gentzen proved the consistency of Peano's axioms, using transfinite induction. This was a proof using logic alone, but of course infinite. It gives an algorithm for simplifying a possible proof of contradiction by a series of simple transformations, until it becomes very short. To see that it becomes very short we need transfinite induction. Gentzen's proof has been humorously called "assuming the dubious to prove the obvious".
All mathematicians assume that Peano arithmetic is consistent, although this relies on intuition only. However, early forms of naive set theory also intuitively looked consistent, before the inconsistencies were discovered. This has been a source of confusion for a number of people, especially nonmathematicians.
The point is that we do have to rely on our intuition, and that it brings something new. Roger Penrose has argued that this intuition is what differs men from machines, but his arguments are dubious. The modern set theory often consideres axioms postulating existence of large cardinals - none of them can be proved within set theory, nor is it possible to prove consistency of these axioms. But mathematicians generally do not exclude possibility that some of these axiom systems are inconsistent. The intuition here is much less clear than in the case of natural numbers. Some people argue that even Peano arithmetic could be inconsistent - since intuition is not really a reliable source of truth. This argument can be extended and make us doubt even finite logic itself - these questions go back to Kant and his famous Critique of Pure Reason.
A theorem is a statement which can be proven true within some logical framework. Proving theorems is a central activity of mathematics. Note that 'theorem' is distinct from, but related to, 'theory'.
A mathematical statement which is believed to be true but has not been proven is known as a conjecture. See mathematics for a list of famous theorems and conjectures.
In mathematics, a logical system consists of a basic set of axioms, as well as a process of inference, which allows to derive new theorems from axioms and other theorems that have been derived earlier.
While in propositional logic, any proven statement is called a theorem, in general mathematics a statement must be interesting or important in some way to be called a theorem. Less important statements are called:
Recursion is a way of specifying a process by means of itself. More precisely (and to dispel the appearance of circularity in the definition), "complicated" instances of the process are defined in terms of "simpler" instances, and the "simplest" instances are given explicitly.
Examples of mathematical objects often defined recursively are functions and sets.
The canonical example of a recursively defined function is the following definition of the factorial function f(n):
Given this definition, also called a recurrence relation, we work out f(3) as follows:
f(3) = 3 · f(3-1)
= 3 · f(2)
= 3 · 2 · f(2-1)
= 3 · 2 · f(1)
= 3 · 2 · 1 · f(1-1)
= 3 · 2 · 1 · f(0)
= 3 · 2 · 1 · 1
= 6
Another example is the definition of Fibonacci numbers.
Here is another, perhaps simpler way to understand recursive processes:
A common method of simplification is to divide the problem into subproblems. Such a programming technique is called divide-et-impera or divide and conquer and is a fundamental part of dynamic programming.
Virtually all programming languages in use today allow the direct specification of recursive functions and procedures. When such a function is called, the computer keeps track of the various instances of the function by using a stack. Conversely, every recursive function can be transformed into an iterative function by using a stack.
Any function that can be evaluated by a computer can be expressed in terms of
recursive functions, without use of
iteration. Indeed, some languages designed for
logic programming and
functional programming provide recursion as the only means of repetition
directly available to the programmer. Such languages generally make
tail recursion as efficient as iteration, letting programmers express other
repetition structures (such as
Scheme's map and for) in terms of recursion.
Recursion is deeply embedded in the theory of computation, with the theoretical equivalence of recursive functions and Turing machines at the foundation of ideas about the universality of the modern computer.
In set theory there is a theorem guaranteeing that recursively defined functions exist:
The recursion theorem. Given a set X, an element a of X and a function f : X -> X, there is a unique function F : N -> X (where N denotes the set of natural numbers) such that
[A proof of the recursion theorem from set theory is needed]
The canonical example of a recursively defined set is the natural numbers:
The natural numbers can be defined as the smallest set satisfying these two properties.
Another interesting example is the set of all true propositions in an axiomatic system.
[It needs to be pointed out that determining whether a certain object is in a recursively defined set is not an algorithmic task]
Logic is regarded as a branch both of philosophy and of mathematics. A system of logic (or simply "a logic") is a set of rules for reasoning about a given domain. Many different systems of logic have been devised. Such artificial systems of reasoning now find many practical applications in computing.
It was pioneered by Aristotle. Although it is possible that Aristotle himself had been taught by someone else, the earliest study of reasoning can be attributed to Aristotle. Aristotle and his followers held that two of the most important principles of logic are the law of non-contradiction and the law of excluded middle. This kind of logic is now given various names to distinguish it from more recent systems of logic, e.g., Aristotelian logic or classical two-valued logic.
Today, some other axioms or inference rules would be held to be at least as important. The ultimate goal of logic, if it can be said to have a goal, is valid argumentation and to avoid logical fallacy.
Logic as a science defines the structure of statement and argument and defines formulae by which these are codified. Implicit in a study of logic is the understanding of what makes a good argument and what arguments are fallacious. Students of traditional logic--which studied standards of definition as well as of argument--were often made to memorize certain argument forms so that they could more easily create better arguments and disprove weaker ones thrown against them. The Jesuits emphasized this so highly, that their students were required to take part in a structured argument session with their peers.
Georg Hegel, who considered himself the modern Aristotle, created a dialectical logic (see The Science of Logic), arguing that all concepts necessarily overcome themselves by cancellation, preservation, and supersession--a process commonly called sublation. Contemporary logicians have naught but scorn for Hegel's logic, which they consider metaphysically spurious.
Mathematical logic or symbolic logic has changed this somewhat by axiomatizing logic and presenting all argument in the form of symbolic strings with very highly constrained forms that represent different statements. The rules of argumentation then are codified as legal transformations on these strings and the allowable starting points (the so-called axioms). Kurt Gödel in the 1930's proved his celebrated incompleteness theorem and thus derailed the idea (put forward by Hilbert and others) that all of reasoned thought could be axiomatized. This sea-change had been foreshadowed by the work of Bertrand Russell and Alfred North Whitehead in mathematics. At roughly the same time, Alonzo Church, Andrei Andreevich Markov, Alan Turing and others were realizing that all sufficiently powerful formal models of computation were equivalent. This led to the computational equivalent of the incompleteness theorem, the Halting Problem.
Propositional Logic can be illustrated either by truth tables or Johnston Diagrams.
In the early 20th century Jan Lukasiewicz investigated the extension of the traditional true/false values to include a third value. Logics have been devised with an infinite number of "degrees of truth", e.g., represented by a real number between 0 and 1. Bayesian probability can be interpreted as a system of logic where probability is the subjective truth value. Fuzzy logic is another such system.
In a logical calculus, logical operators or logical connectors serve to connect statements into more complicated compound statements. For example, considering the assertions "It's raining", and "I'm inside", we can form the compound assertions "it's raining, and I'm inside" or "it's not raining" or "if it's raining, then I'm inside."
The basic operators are "not" (¬), "and" (∧), "or" (∨), "conditional" (→), and "biconditional" (↔). "Not" is a unary operator--it takes a single term ( ¬ P ). The rest are binary operators, taking two terms to make a compound statement ( P ∧ Q, P ∨ Q, P → Q, P ↔ Q ).
Note the similarity between the symbols for "and" ( ∧ ) and "set theoretic intersection" ( ∩ ); likewise for "or" ( ∨ ) and "union ( ∪ ). This is not a coincidence: the definition of the intersection uses "and" and the definition of union uses "or".
Truth tables for these connectives:
| P | Q | ¬P | P ∧ Q | P ∨ Q | P → Q | P ↔ Q |
|---|---|---|---|---|---|---|
| T | T | F | T | T | T | T |
| T | F | F | F | T | F | F |
| F | T | T | F | T | T | F |
| F | F | T | F | F | T | T |
In order to reduce the number of necessary parentheses, one introduces precendence rules: ¬ has higher precedence than ∧, ∧ higher than ∨, and ∨ higher than →. So for example, P ∨ Q ∧ ¬ R → S is short for (P ∨ (Q ∧ (¬ R)) → S.
Note that the logical equivalence of certain compound statements entails that not all of these operators are necessary for a full-blooded logical calculus. For example, ¬ P ∨ Q is logically equivalent to P → Q; since logical equivalence means that equivalent terms may be subsituted for each other in an expression, it's not necessary to have a conditional operator. The five operators listed above are the basic set for the sake of convenience (and brevity).
One can also consider other connectives, such as NAND, XOR and NOR. It can be shown that all connectives can be expressed with NAND alone, and they can also all be expressed with NOR alone.
In boolean algebra, logical negation is a unary logical operator that reverses the truth value of its operand. The negation of the statement p is written in various ways:
It is read as "not p". For instance, if p denotes the statement "today is Saturday", then its negation ~p is the statement "today is not Saturday".
In classical logic, double negation means affirmation, i.e. the statements p and ~(~p) are logically equivalent.
(Redirected from Logical and)
Conjunction, or and, is a logical operator in logical calculi. The symbol "∧" is typically used, and "P ∧ Q" is read "P and Q". In boolean logic, logical conjunction returns TRUE if, and only if, all its inputs are TRUE.
| Input1 | Input2 | Output |
|---|---|---|
| FALSE | FALSE | FALSE |
| FALSE | TRUE | FALSE |
| TRUE | FALSE | FALSE |
| TRUE | TRUE | TRUE |
Intuitively, the logical operator works the same as the common English word "and". The sentence "it's raining, and I'm inside" asserts that two things are simultaneously true: that it's raining outside, and that I'm inside. Logically, this would be denoted by saying that A stands for "it's raining", B stands for "I'm inside", together A ∧ B.
"And" is a binary operator, meaning that it takes two terms and asserts that both are simultaneously true. However, it's common usage to chain conjunctions, such as A ∧ B ∧ C. Properly written, using parenthesis for proper grouping, this would be written as ( ( A ∧ B ) ∧ C ), but the intent is easily understood: the statement is true if A and B and C are simultaneously true. Notice that since "And" is both associative and commutative that the parenthesis are not strictly necessary.
The term "conjunction" can also be applied to a logical statement or formula that contains only literals separated by ANDs. For example, all of the following are considered conjunctions:
A ∧ B ¬A ∧ B A ∧ ¬B ∧ ¬C &and D &and ¬E ¬B
A minor issue of logic and language is the role of the word "but". Logically, the sentence "it's raining, but the sun is shining" is equivalent to "it's raining, and the sun is shining", so logically, "but" is equivalent to "and". However, as demonstrated by the preceding sentences, "but" and "and" are semantically distinct. The former sentences suggests that the latter sentence is usually a contradiction.
One way to resolve this problem of correspondence between symbolic logic and natural language is to observe that the first sentence (using "but"), implies the existence of a hidden but mistaken assumption, namely that the sun doesn't shine when it rains. That implication captures the semantic difference of "and" and "but" without disturbing their logical equivalence.
(Redirected from Logical or)
In logic and mathematics, a disjunction is an "or statement". For example "John skis or Sally swims" is a disjunction.
Note that while in everyday language, use of the word "or" can sometimes mean "either, but not both" (eg "would you like tea or coffee?"), when used formally, "or" allows for both parts of the or statement (its disjuncts) to be true.
The statement "P or Q" is often written as
Such a disjunction is false if both P and Q are false. In all other cases it is true.
More generally a disjunction is a logical formula that can have one or more literals separated only by ORs. A single literal is often considered to be a degenerate disjunction.
For example, all the following are disjunctions:
A ∨ B ¬A ∨ B A ∨ ¬B ∨ ¬C ∨ D ∨ ¬E ¬B
The equivalent notion in set theory is the set theoretic union.
A conditional statement, or simply a conditional for short, is an "if-then" statement, written in the form: 'if P, then Q'. Here, 'P' is the antecedent (the "if" part of the statement) and 'Q' is the consequent (the "then" part). For example, in "If you give me ten dollars, then I will be your best friend," the claim "you give me ten dollars" is the antecedent of the conditional, and "I will be your best friend" is the consequent.
In classical two-valued logic, an argument is said to have validity or to be valid if, and only if, it is the case that, if the premises of the argument are true, then the conclusion must be true. In other words, a valid argument is one where the premises make the conclusion true. There are many other ways to formulate this basic definition: the premises entail the conclusion; it cannot be the case both that the premises are true and the conclusion false; the falsehood of the conclusion entails the falsehood of at least one premise; etc.
A close examination of the definition of 'valid' should make a few things clear about validity. The definition says neither that the premises have to be true nor that that the conclusion has to be true. Validity is a conditional notion: what it says is that if the premises happen to be true, then the conclusion has to be true. As far as validity is concerned the premises might be completely and obviously false. Consider an example of a valid argument:
Bear in mind that 'valid' is a technical term in logic: this is a perfectly valid argument. What does that mean, in this example? Something like this: suppose it were true that all dogs had eight legs; and suppose, just suppose, that the President really were a dog; well, in that absurd imaginary world, the President would have to have eight legs. The conclusion has to be true, if the premises are true. So the argument is valid, even though it has false premises, not to mention a false conclusion.
Validity is not to be confused with soundness; a sound argument is not only valid, its premises are true as well. Not all valid arguments are valid in the loose and popular sense of this word, meaning 'good': not all valid arguments (valid, as this term is used in logic) are good, or successful, as the above example should show.
Argument form is what makes an argument valid. But a valid argument is one where, if the premises are true, then the conclusion must be true (and here is a way to put it more briefly: the premises make the conclusion necessary). Now put these two propositions together and draw a conclusion:
One can see whether the premises make the conclusion necessary just by looking at the form of the argument. That is why argument form is so important. Look, for example, at the following argument form. In fact, any argument that follows this form is valid. You can see that just by reading it:
Now examine the following argument. It fits that form and is (therefore) valid:
A lemma is the proof of a minor claim to be made in the proof of a major result. Of course, the distinction between theorems and lemmas is rather arbitrary, since one mathematician's major result is another's minor claim. Gauss's Lemma and Zorn's Lemma, for example, are interesting enough per se for some authors to stop at the nominal lemma without going on to use that result in any "major" theorem.
The test form of an argument is what results from replacing different words, or sentences, that make up the argument with letters; the letters are called variables.
Some examples of valid arguments forms are modus ponens, modus tollens, and disjunctive syllogism. One invalid argument form is affirming the consequent.
Just as variables can stand for various numbers in mathematics, variables can stand for various words, or sentences, in logic. Argument forms are very important in the study of logic. The parts of argument forms--sentence forms (see below)--are equally important. In a logic course one would learn how to determine what the forms of various sentences and arguments are.
The basic notion of argument form can be introduced with an example. Here is an example of an argument:
A All humans are mortal. Socrates is human. Therefore, Socrates is mortal.
We can rewrite argument A by putting each sentence on its own line:
B
To demonstrate the important notion of the form of an argument, substitute letters for similar items throughout B:
C
All we have done in C is to put 'S' for 'human' and 'humans', 'P' for 'mortal', and 'a' for 'Socrates'; what results, C, is the form of the original argument in A. So argument form C is the form of argument A. Moreover, each individual sentence of C is the sentence form of its respective sentence in A.
There is a good reason why attention to argument and sentence forms is important. The reason is this: form is what makes an argument valid or cogent.
In epistemology, a proposition that cannot be understood without knowing that it is true, is called a self-evident proposition. A self-evident proposition is one that can be known to be true without proof (but only if one understands what it says). Some epistemologists deny that any proposition can be self-evident.
My belief that I am conscious is considered by many to be self-evident; your belief that I am conscious is not.
In informal or colloquial speech, "self-evident" often merely means "obvious."
Certain forms of argument from self-evidence are considered fallacious or abusive in debate. An example is the assertion that since an opponent disagrees with a (claimed self-evident) proposition, that he must have misunderstood it.
Compare with: the concepts of primitive notion and axiom in mathematics
In mathematics, a set of symbols is frequently used in mathematical expressions. As mathematicians are familiar with these symbols, they are not explained each time they are used. So, for mathematical novices, the following table lists many common symbols together with their name, pronunciation and related field of mathematics. Additionally, the second line contains an informal definition, and the third line gives a short example.
Note: If some of the symbols don't display properly for you, then your browser does not completely implement the HTML 4 character entities. Mozilla does, although you may still need to install additional fonts to see everything.
| Symbol | Name | reads as | Category |
|---|---|---|---|
| ⇒ → |
material implication | implies; if .. then | propositional logic |
| A ⇒ B means: if A is true then
B is also true; if A is false then nothing is said about
B. → may mean the same as ⇒, or it may have the meaning for functions mentioned further down |
|||
| x = 2 ⇒ x2 = 4 is true, but x2 = 4 ⇒ x = 2 is in general false (since x could be −2) | |||
| ⇔ ↔ |
material equivalence | if and only if; iff | propositional logic |
| A ⇔ B means: A is true if B is true and A is false if B is false | |||
| x + 5 = y + 2 ⇔ x + 3 = y | |||
| ∧ | logical conjunction | and | propositional logic |
| the statement A ∧ B is true if A and B are both true; else it is false | |||
| n < 4 ∧ n > 2 ⇔ n = 3 when n is a natural number | |||
| ∨ | logical disjunction | or | propositional logic |
| the statement A ∨ B is true if A or B (or both) are true; if both are false, the statement is false | |||
| n ≥ 4 ∨ n ≤ 2 ⇔ n ≠ 3 when n is a natural number | |||
| ¬ / |
logical negation | not | propositional logic |
| the statement ¬A is true if and only if A
is false a slash placed through another operator is the same as "¬" placed in front |
|||
| ¬(A ∧ B) ⇔ (¬A) ∨ (¬B); x ∉ S ⇔ ¬(x ∈ S) | |||
| ∀ | universal quantification | for all; for any; for each | predicate logic |
| ∀ x: P(x) means: P(x) is true for all x | |||
| ∀ n ∈ N: n2 ≥ n | |||
| ∃ | existential quantification | there exists | predicate logic |
| ∃ x: P(x) means: there is at least one x such that P(x) is true | |||
| ∃ n ∈ N: n + 5 = 2n | |||
| = | equality | equals | everywhere |
| x = y means: x and y are different names for precisely the same thing | |||
| 1 + 2 = 6 − 3 | |||
| := :⇔ |
definition | is defined as | everywhere |
| x := y means: x is defined
to be another name for y P :⇔ Q means: P is defined to be logically equivalent to Q |
|||
| cosh x := (1/2)(exp x + exp (−x)); A XOR B :⇔ (A ∨ B) ∧ ¬(A ∧ B) | |||
| { , } | set brackets | the set of ... | set theory |
| {a,b,c} means: the set consisting of a, b, and c | |||
| N = {0,1,2,...} | |||
| { : } { | } |
set builder notation | the set of ... such that ... | set theory |
| {x : P(x)} means: the set of all x for which P(x) is true. {x | P(x)} is the same as {x : P(x)}. | |||
| {n ∈ N : n2 < 20} = {0,1,2,3,4} | |||
| ∅ {} |
empty set | empty set | set theory |
| {} means: the set with no elements; ∅ is the same thing | |||
| {n ∈ N : 1 < n2 < 4} = {} | |||
| ∈ ∉ |
set membership | in; is in; is an element of; is a member of; belongs to | set theory |
| a ∈ S means: a is an element of the set S; a ∉ S means: a is not an element of S | |||
| (1/2)−1 ∈ N; 2−1 ∉ N | |||
| ⊆ ⊂ |
subset | is a subset of | set theory |
| A ⊆ B means: every element of A
is also element of B A ⊂ B means: A ⊆ B but A ≠ B |
|||
| A ∩ B ⊆ A; Q ⊂ R | |||
| ∪ | set theoretic union | the union of ... and ...; union | set theory |
| A ∪ B means: the set that contains all the elements from A and also all those from B, but no others | |||
| A ⊆ B ⇔ A ∪ B = B | |||
| ∩ | set theoretic intersection | intersected with; intersect | set theory |
| A ∩ B means: the set that contains all those elements that A and B have in common | |||
| {x ∈ R : x2 = 1} ∩ N = {1} | |||
| \ | set theoretic complement | minus; without | set theory |
| A \ B means: the set that contains all those elements of A that are not in B | |||
| {1,2,3,4} \ {3,4,5,6} = {1,2} | |||
| ( ) [ ] { } |
function application; grouping | of | set theory |
| for function application: f(x) means:
the value of the function f at the element x for grouping: perform the operations inside the parentheses first |
|||
| If f(x) := x2, then f(3) = 32 = 9; (8/4)/2 = 2/2 = 1, but 8/(4/2) = 8/2 = 4 | |||
| : → | mapping arrow | from ... to | functions |
| f: X → Y means: the function f maps the set X into the set Y | |||
| If f(x) = x2, then we might take f: Z → N | |||
| N | natural numbers | N | numbers |
| N means: {0,1,2,3,...} | |||
| {|a| : a ∈ Z} = N | |||
| Z | integers | Z | numbers |
| Z means: {...,−3,−2,−1,0,1,2,3,...} | |||
| {a : |a| ∈ N} = Z | |||
| Q | rational numbers | Q | numbers |
| Q means: {p/q : p,q ∈ Z, q ≠ 0} | |||
| 3.14 ∈ Q; π ∉ Q | |||
| R | real numbers | R | numbers |
| R means: {limn→∞ an : ∀ n ∈ N: an ∈ Q, the limit exists} | |||
| π ∈ R; √(−1) ∉ R | |||
| C | complex numbers | C | numbers |
| C means: {a + bi : a,b ∈ R} | |||
| i = √(−1) ∈ C | |||
| < > |
comparison | is less than, is greater than | partial orders |
| x < y means: x is less than y; x > y means: x is greater than y | |||
| x < y ⇔ y > x | |||
| ≤ ≥ |
comparison | is less than or equal to, is greater than or equal to | partial orders |
| x ≤ y means: x is less than or equal to y; x ≥ y means: x is greater than or equal to y | |||
| x ≥ 1 ⇒ x2 ≥ x | |||
| √ | square root | the principal square root of; square root | real numbers |
| √x means: the positive number whose square is x | |||
| √(x2) = |x| | |||
| ∞ | infinity | infinity | numbers |
| ∞ means: an extended number that is greater than all real numbers; it often occurs in limits | |||
| limx→0 1/|x| = ∞ | |||
| π | pi | pi | Euclidean geometry |
| π means: the ratio of a circle's circumference to its diameter | |||
| A = πr˛ is the area of a circle with radius r | |||
| | | | absolute value | absolute value of | numbers |
| |x| means: the distance in the real line (or the complex plane) between x and zero | |||
| |a + bi| = √(a2 + b2) | |||
| ∑ | addition | sum over ... from ... to ... of | arithmetic |
| ∑k=1n ak means: a1 + a2 + ... + an | |||
| ∑k=14 k2 = 12 + 22 + 32 + 42 = 1 + 4 + 9 + 16 = 30 | |||
| ∏ | multiplication | product over ... from ... to ... of | arithmetic |
| ∏k=1n ak means: a1a2···an | |||
| ∏k=14 (k + 2) = (1 + 2)(2 + 2)(3 + 2)(4 + 2) = 3 × 4 × 5 × 6 = 360 | |||
| ∫ | integration | integral from ... to ... of ... with respect to | calculus |
| ∫ab f(x) dx means: the signed area between the x-axis and the graph of the function f between x = a and x = b | |||
| ∫0b x2 dx = b3/3; ∫x2 dx = x3/3 | |||
|
gradient | del, nabla, gradient of | calculus |
| ∇f (x1, …, xn) is the vector of partial derivatives (df / dx1, …, df / dxn) | |||
| If f (x,y,z) = 3xy + z˛ then ∇f = (3y, 3x, 2z) | |||
| insert more | |||
An argument by lack of imagination is the logical fallacy that states because something is currently inexplicable, that it did not happen, or that because one cannot conceive of something, it cannot exist. It is used often to attempt to invalidate a scientific theory by pointing out a phenomenon which the theory does not readily explain. This is rather simple to do because there are a lot of phenomena that are currently unexplained. However, the mistake is to assert that because a phenomenon is unexplained, it is unexplainable.
This logical fallacy should be distinguised from the logically valid method of reductio ad absurdum. In reductio ad absurdum it is necessary to show that A implies not A, not merely that A implies something which the speaker considers absurd.
Another example of this argument is Ayn Rand's defense of patent and copyright law. She argued that such laws were "obviously necessary" for authors and inventors to earn a living (or in other words, that she could not imagine any ways for them to earn a living without them, so such methods can't exist), so they should be supported. Rand's conclusion is falsified by, for example, the fact that a wealthy patron could commission a work, or that an author could control the work through trade secret law rather than through a copyright.
Richard Dawkins has called this fallacy "the argument from personal incredulity"; he uses it specifically in the context of arguments about creationism versus evolution, where it is often phrased in terms such as: "A mechanism that works so perfectly (for instance, the eye) could not have evolved by chance". In a more colorful example he counters a Bishop's implicit assumption that since polar bears are camouflaged even though they have no natural predators, their camouflage serves no evolutionary purpose--the polar bear benefits from the camouflage when hunting of course.
A decidable or recursive language is a formal language for which there exists an algorithm to solve the following decision problem: Given string w, does w belong to the language? The algorithm is not allowed to run into an infinite loop and has to produce a YES/NO answer for any input string after a finite amount of time. To formalize the rather vague term "algorithm", one usually employs Turing machines, but several other equivalent approaches are possible.
All regular, context-free and context-sensitive languages are recursive, but there exist recursively enumerable languages which are not recursive; one example is given by the halting problem.
The Turing machine is an abstract model of computer execution and storage introduced in 1936 by Alan Turing to give a mathematically precise definition of algorithm or 'mechanical procedure'. As such it is still widely used in theoretical computer science, especially in complexity theory and the theory of computation. The thesis that states that Turing machines indeed capture the informal notion of effective or mechanical method in logic and mathematics is known as the Church-Turing thesis.
Turing machines shouldn't be confused with the Turing test, Turing's attempt to capture the notion of artificial intelligence.
A Turing machine that is is able to simulate any other Turing machine is called a universal Turing machine.
A Turing machine consists of:
Note that every part of the machine is finite, but it is the potentially unlimited amount of tape that gives it an unbounded amount of storage space.
The following Turing machine has an alphabet {'0', '1'}, with 0 being the blank symbol. It expects a series of 1's on the tape, with the head initially on the leftmost 1, and doubles the 1's with a 0 in between, i.e., "111" becomes "1110111". The set of states is {s1, s2, s3, s4, s5} and the start state is s1. The action table is as follows.
Old Read Wr. New Old Read Wr. New St. Sym. Sym. Mv. St. St. Sym. Sym. Mv. St. - - - - - - - - - - - - - - - - - - - - - - - - s1 1 -> 0 R s2 s4 1 -> 1 L s4 s2 1 -> 1 R s2 s4 0 -> 0 L s5 s2 0 -> 0 R s3 s5 1 -> 1 L s5 s3 0 -> 1 L s4 s5 0 -> 1 R s1 s3 1 -> 1 R s3
A computation of this Turing machine might for example be: (the position of the head is indicated by displaying the cell in bold face)
Step State Tape Step State Tape
- - - - - - - - - - - - - - - - -
1 s1 11 9 s2 1001
2 s2 01 10 s3 1001
3 s2 010 11 s3 10010
4 s3 0100 12 s4 10011
5 s4 0101 13 s4 10011
6 s5 0101 14 s5 10011
7 s5 0101 15 s1 11011
8 s1 1101 -- halt --
The behavior of this machine can be described as a loop: it starts out in s1, replaces the first 1 with a 0, then uses s2 to move to the right, skipping over 1's and the first 0 encountered. S3 then skips over the next sequence of 1's (initially there are none) and replaces the first 0 it finds with a 1. S4 moves back to the left, skipping over 1's until it finds a 0 and switches to s5. s5 then moves to the left, skipping over 1's until it finds the 0 that was originally written by s1. It replaces that 0 with a 1, moves one position to the right and enters s1 again for another round of the loop. This continues until s1 finds a 0 (this is the 0 right in the middle between the two strings of 1's) at which time the machine halts.
Every Turing machine computes a certain fixed partial function over the strings over its alphabet. In that sense it behaves like a computer with a fixed program. However, as Alan Turing already described, we can encode the action table of every Turing machine in a string. Thus we might try to construct a Turing machine that expects on its tape a string describing an action table followed by a string describing the input tape, and then computes the tape that the encoded Turing machine would have computed. As Turing showed, such a Turing machine is indeed possible and since it is able to simulate any other Turing machine it is called a universal Turing machine.
With this encoding of action tables as strings, it becomes in principle possible for Turing machines to answer questions about the behavior of other Turing machines. Most of these questions however are undecidable, see for instance the Halting problem, which was already shown to be undecidable in Turing's original paper, and Rice's theorem.
If we broaden the definition to include any Turing machine that simulates some Turing-complete computational model, not just Turing machines that directly simulate other Turing machines, a universal Turing machine can be fairly simple, using just a few states and a few symbols. For example, only 2 states are needed, since a 2×18 (meaning 2 states, 18 symbols) universal Turing machine is known. A complete list of the smallest known universal Turing machines is: 2×18, 3×10, 4×6, 5×5, 7×4, 10×3, 22×2. These simulate a computational model called tag-systems.
A universal Turing machine is Turing complete. It can calculate any recursive function, decide any recursive language, and accept any recursively enumerable language. According to the Church-Turing thesis, the problems solvable by a universal Turing machine are exactly those problems solvable by an algorithm or an effective method of computation, for any reasonable definition of those terms.
It is not difficult to simulate a Turing Machine on a modern computer (except for the limited memory of actually existing computers).
It is also possible to build a Turing Machine on a purely mechanical basis. The mathematician Karl Scherer has indeed built such a machine in 1986 using metal and plastic construction sets, and some wood. The 1.5 meter high machine uses the pulling of strings to read, move and write the data (which is represented using ball bearing balls).
The machine is now exhibited in the entrance of the Department of Computer Science of the University in Heidelberg, Germany.
A partially decidable or recursively enumerable language is a formal language for which there is an algorithm for the following decision problem:
There are three potential outcomes: YES, NO, and LOOP. If the string is in the language, then the algorithm must output "YES", and halt. If the string is not in the language, then the algorithm may either output "NO" and halt, or it may run forever in an infinite loop that never outputs anything. To formalize the rather vague term "algorithm", one usually employs Turing machines, but several other equivalent approaches are possible.
Some partially decidable languages have an algorithm that always answers YES or NO correctly, and never has an infinite loop. Those languages are called decidable languages or recursive languages. Some problems are recursively enumerable but not recursive. One example is the halting problem, which is the problem:
All recursive, regular, context-free and context-sensitive languages are recursively enumerable. Some problems are so difficult that they aren't even recursively enumerable. One example is this problem:
The section on symbolic logic mentions axiomatic treatments of the subject. Here we say a bit about systems of natural deduction.
The name is suggestive. One of the popular ways of cashing out natural deduction is that it is an application of the laws (rules, whatever) of logic to our "natural modes" of inference.
For instance, if I say that
The general move is this. One begins a proof by assuming 'all x are such that, if x is A then x is M'. Next assume that something (call it 's') is not M, ie. assume 'it is not the case that s is M'. Now, a system of natural deduction will license the use of these assumptions. Moreover, the rules of the system will license the move from the first assumption 'all x, A(x) then M(x)' to 'A(s) then M(s)'[it would be called 'universal instantiation' or something]. We have 'not M(s)', and it readily follows that not 'A(s)'[the rule is called 'modus tollens', for those systems that countenance it - it need not be countenanced if there are other "simpler rules" capable of handling the inference. If such simpler rules are present, the abscence of modus tollens notwithstanding, the inference just takes more steps.].
Now, an axiomatic system COULD handle such an inference (since it's valid, and all such deductions are captured by non-wimpy axiomatic systems), but this would require a proof adhering to very restrictive syntactical (typographical, if one likes) rules. The advantage of a natural deduction system is that it has an apparatus for dealing with the sort of assumptions we just made. That is, one can assume whatever s/he likes, and proceed to deduce whatever can be deduced given the rules of the system. The method is thought to be more like argument, and more akin to the practice of mathematicians. Open your favorite math book. It's very unlikely that there are axiomatic proofs in that book (in any strict syntactical sense). Rather, the mathematician assumes something (which may be tentative, or an established fact- usually a fact) and then uses a bit of logic to show what must also be the case given the assumption (granted, s/he will almost always use certain "obvious" arithemtical properties in the proof-or other properties). In short, natural deduction systems are easier to work within. They are more natural.
An argument is sound if, and only if, (1) the argument is valid and (2) all of its premises are true.
So suppose we have a sound argument:
In this case we have an argument where, first, if the premises are all true, then the conclusion must be true (i.e., the argument is valid); and, second, it so happens that the premises are all true. It follows that the conclusion must be true. That is the nice thing about soundness: if you know an argument is sound, then you know that its conclusion is true. By definition, all sound arguments have true conclusions. So soundness is a very good quality for an argument to have.
In mathematical analysis, a metric space (M, d) is said to be complete if every Cauchy sequence of points in M has a limit in M.
Intuitively, a space is complete if it "doesn't have any holes", if there aren't any "points missing". For instance, the rational numbers are not complete, because √ 2 is "missing". It is always possible to "fill all the holes", leading to the completion of a given space. This will be explained below.
The rational numbers Q, with the standard metric given by the absolute value, are not complete. Consider for instance the sequence defined by x1 = 1 and xn+1 = (xn + 2/xn) / 2. This is a Cauchy sequence of rational numbers, but it does not converge towards any rational limit; in fact, it converges towards the irrational number √2 (see square root).
The open interval (0,1), again with the absolute value metric, is not complete either: The sequence 1/2, 1/3, 1/4, 1/5, ... is Cauchy, but does not have a limit in the space.
The real numbers and the complex numbers with the metric given by the absolute value are complete, so is Euclidean space Rn and, more generally, all Banach spaces.
The p-adic numbers are complete for any prime number p.
If S is an arbitrary set, then the set SN of all sequences in S becomes a complete metric space if we define the distance between the sequences (xn) and (yn) to be 1/N where N is the smallest index for which xN ≠ yN; if there is no such index, then the two sequences are the same and we define their distance to be 0. This space is homeomorphic to the product of a countable number of copies of the discrete space S. If S is finite, SN is therefore compact.
Every compact metric space is complete. In fact, a metric space is compact if and only if it is complete and totally bounded.
A subspace of a complete space is complete if and only if it is closed.
If X is some set, and M is a complete metric space, then the set B(X, M) consisting of all bounded function f : X -> M, with the metric d(f, g) = supx in Xd(f(x), g(x)), is a complete metric space.
If X is a topological space and M is a complete metric space, then the set Cb(X, M) consisting of all continuous bounded functions f : X -> M is a closed subspace of B(X, M) and hence also complete.
The Baire category theorem applies to complete spaces: the interior of a union of countably many nowhere dense subsets of a complete space is empty.
For any metric space (M, d), one can construct a complete metric space (M', d') which contains M as a dense subset and such that d(x, y) = d'(x, y) for all x and y in M. It has the following universal property: if N is any complete metric space and f : M -> N is any uniformly continuous map, then there exists a unique uniformly continuous map g : M' -> N which extends f. The space M' is essentially uniquely determined by this property, and is called the completion of M.
The completion of M can be constructed as a set of equivalence classes of Cauchy sequences in M. For any two Cauchy sequences (xn) and (yn) in M, we may define their distance as
(This limit exists because the real numbers are complete.) This is not yet a metric, since two different Cauchy sequences may have the distance 0. But "having distance 0" is an equivalence relation on the set of all Cauchy sequences, and the set of equivalence classes turns into an metric space, the completion of M.
The standard construction of the real numbers is a special case of this (if one disregards the circularity inherent in the fact that the definition of metric spaces involves real numbers): the real numbers are the completion of the rational numbers using the ordinary absolute value to measure distances. By using different notions of distance on the rationals, one obtains different incomplete metric spaces, and their completions turn out to be the p-adic numbers.
If this completion procedure is applied to a normed vector space, one obtains a Banach space containing the original space as a dense subspace, and if it is applied to an inner product space, one obtains a Hilbert space containing the original space as a dense subspace.
Note that completeness is a property of the metric and not of the topology, meaning that a complete metric space can be homeomorphic to a non-complete one. An example is given by the real numbers, which are complete and homeomorphic to the open interval (0,1), which is not complete. Another example are the irrational numbers: they are not complete as a subspace of the real numbers with the usual metric (take any sequence of irrational numbers converging to a rational number). However, the irrational numbers are homeomorphic to the countable power of the natural numbers, which is a complete metric space as explained above in the examples section.
In topology one considers completely metrizable spaces, spaces for which there exists at least one complete metric inducing the given topology. Completely metrizable spaces can be characterized as those spaces which can be written as an intersection of countably many open subsets of some complete metric space Cech completeness, absolute G_delta spaces. The Baire category theorem applies to these spaces as well.
It is also possible to define the concept of completeness for uniform spaces using a generalization of sequences. A net (xα) in a uniform space X is a Cauchy net if for every entourage V there exists an α0 such that for all α, β > α0 we have (xα, xβ) in V. If every Cauchy net has a limit in X, then X is called complete. One can construct a completion for an arbitrary uniform space similar to the completion of metric spaces.
In complexity theory, a problem P is said to be complete for a complexity class C, under a given type of reduction, if P is in C, and every problem in C reduces to P using that reduction. For example, each problem in the class NP-Complete is complete for the class NP, under polynomial-time, many-one reduction.
In logic, a system of axioms is said to be complete if, for any statement P, a proof exists for P or for not P. A system is consistent if a proof never exists for both P and not P. Goedel's incompleteness theorem proved that no system as powerful as Peano's axioms can be both consistent and complete.
In graph theory, a complete graph is one where every pair of vertices have an edge connecting them.
For the notion of completeness of lattices, see lattice.
For the notion of completeness of measures, see complete measure.
The word model is used in various contexts meaning something (abstract or physical) that represents 'the real thing'. It is often a simplified version, but it can also mean an especially good example; a physical model of something large is usually smaller, and of something very small is larger.
A physical model of something that can move, like a vehicle or machine, may be completely static, or have parts that can be moved manually, or be powered. A physical model may show inner parts that are normally not visible.
The purpose of a physical model on a smaller scale may be to have a better overview, for testing purposes, as hobby or toy.
The purpose of a physical model on a larger scale may be to see the structure of things that are normally to small to see properly or to see at all, for example a model of an insect or of a molecule.
A physical model of an animal shows how it is built without it walking or flying away, and without danger, and if the real animal is not available.
The word model has applications throughout science with variations according to the subject matter under discussion. In general, it indicates an object which we study, not for its intrinsic interest, but because it is a formalized or simplified representation of a class of phenomena which can be studied easily. See also Model theory.
Gödel's completeness theorem is a fundamental theorem in Mathematical logic proved by Kurt Gödel in 1929. It states, in its most familiar form, that in first-order predicate calculus every universally valid formula can be proved.
A logical formula is called universally valid if it is true in every possible domain and with every possible interpretation, inside that domain, of non-constant symbols used in the formula. To say that it can be proved means that there exists a formal proof of that formula which uses only the logical axioms and rules of inference adopted in some particular formalisation of first-order predicate calculus.
The theorem can be seen as a justification of the logical axioms and inference rules of first-order logic. The rules are "complete" in the sense that they are strong enough to prove every universally valid statement. It was already known earlier that only universally valid statements can be proven in first-order logic.
To cleanly state Gödel's completeness theorem, one has to refer to an underlying set theory in order to clarify what the word "domain" in the definition of "universally valid" means.
The branch of mathematical logic that deals with what is true in different domains and under different interpretations is Model theory; the branch that deals with what can be formally proved is Proof theory. The completeness theorem, therefore, establishes a fundamental connection between what can be proved and what is (universally) true; between model theory and proof theory; between semantics and syntax in mathematical logic. It should not, however, be misinterpreted as obliterating the difference between these two concepts; in fact, another celebrated result by the same author, Goedels Incompleteness Theorem, shows that there are inherent limitations in what can be achieved with formal proofs in mathematics.
For an explanation of Gödel's original proof of the theorem, see original proof.
In mathematical logic, Gödel's incompleteness theorems are two celebrated theorems proven by Kurt Gödel in 1930. Somewhat simplified, the first theorem states that in any axiomatic system sufficiently strong to allow one to do basic arithmetic, one can construct a statement that
- EITHER -
- OR -
In the first case, we call the axiomatic system incomplete, in the second case we call it inconsistent. A short version of the first incompleteness theorem is therefore: "Any sufficiently strong consistent axiomatic system is incomplete."
Gödel's second incompleteness theorem, which is proved by formalizing part of the proof of the first within the system itself, states that a sufficiently strong consistent system cannot prove its own consistency.
The subsequent combined work of Gödel and Paul Cohen has given concrete examples of undecidable statements (statements which can be neither proven nor disproven): both the axiom of choice and the continuum hypothesis are undecidable in the standard axiomatization of set theory. These results do not require the incompleteness theorem. Following this work, many more statements in set theory have been proven to be undecidable.
In 1977, Kirby, Paris and Harrington proved that a statement in combinatorics, a version of the Ramsey theorem, is undecidable in the axiomatization of arithmetic given by the Peano axioms but can be proven to be true in the larger system of set theory. Kruskal's tree theorem, which has applications in computer science, is also undecidable from the Peano axioms but provable in set theory. Goodstein's theorem is a relatively simple statement about natural numbers that is undecidable in the Peano arithmetic.
Gregory Chaitin produced undecidable statements in algorithmic information theory and in fact proved his own incompleteness theorem in that setting.
The incompleteness results affect the philosophy of mathematics, particularly viewpoints like formalism, which uses formal logic to define its principles. One can paraphrase the first theorem as saying that "we can never find an all encompassing axiomatic system which is able to prove all mathematical truths, but no falsehoods." The following rephrasing of the second theorem is even more unsettling to the foundations of mathematics:
Therefore, in order to establish the consistency of a system S, one needs to utilize some other system T, but a proof in T is not completely convincing unless T's consistency has already been established without using S. The consistency of the Peano axioms for natural numbers for example can be proven in set theory, but not in the theory of natural numbers alone. This provides a negative answer to problem number 2 on David Hilbert's famous list of important open questions in mathematics.
In principle, Gödel's theorems still leave some hope: it might be possible to produce a general algorithm which for a given statement determines whether it is undecidable or not, thus allowing mathematicians to bypass the undecidable statements altogether. However, the negative answer to the Entscheidungsproblem shows that no such algorithm exists.
Note that Gödel's theorems only apply to sufficiently strong axiomatic systems. This means that the axiomatic system should be strong enough to formulate the properties of natural numbers; this is true for example for all systems which are at least as powerful as Peano's axioms. There are weak axiomatic systems which are provably consistent and complete, for instance Presburger arithmetic.
The axiomatic system may consist of infinitely many axioms (as first-order Peano arithmetic does), but for Gödel's theorem to apply, there has to be an effective algorithm which enumerates all the axioms. Otherwise, one could use the "axiomatic system" having all true arithmetical statements as axioms, and would have constructed a counterexample to Gödel's first theorem. Here, the word "true" has been used naively, assuming that every statement about natural numbers is either true or false in an absolute sense, independent of our feeble axiomatization attempts. While Gödel would have agreed, modern logicians do not use this notion of "truth" since it is notoriously hard to define. A more modern counter example to Gödel's first theorem could be constructed as follows: order all possible statements about natural numbers first by length and then lexicographically, start with an axiomatic system initially equal to the Peano axioms, go through your list of statements one by one, and, if the current statement cannot be proven nor disproven from the current axiom system, add it to that system. This creates an "axiom system" which is complete, consistent, and sufficiently powerful, but not recursively enumerable.
Gödel himself only proved a technically slightly weaker version of the above theorems; the first proof for the versions stated above was given by Rosser in 1936.
In essence, the proof of the first theorem consists of constructing the statement
within a formal axiomatic system. As such, it can be seen as a modern variant of the Liar paradox.
Note that, if the axiomatic system is consistent, Gödel's proof shows that p (and its negation) cannot be proven in the system. Therefore it can be argued that p is "true" in some sense: after all, p claims not to be provable, and it isn't. Gödel himself adopted this interpretation: he believed the Peano axioms to be consistent and for him, p was a true statement about natural numbers that could not be proven from those axioms. Nowadays, mathematical logicians often prefer to avoid speaking about truth altogether.
Roger Penrose claims that this (alleged) difference between "truth that can be mechanically proven" and "truth that can be understood by humans" shows that human intelligence is not mechanical in nature. This view is not widely accepted, because as stated by Marvin Minsky, human intelligence is capable of error and of understanding statements which are in fact inconsistent or false.
The position that the theorem shows humans to have an ability that transcends formal logic can also be criticized as follows: We do not know whether the sentence p is true or not, because we do not (and can not) know whether the system is consistent. So in fact we do not know any truth outside of the system. All we know is the following statement:
This statement is easily proved within the system. In fact, such a proof will now be given.
The main problem in fleshing out the above mentioned proof idea is the following: in order to construct a statement p that is equivalent to "p cannot be proven", p would have to somehow contain a reference to p, which could easily end in an infinite regress. Gödel's ingenious trick, which was later used by Alan Turing to solve the Entscheidungsproblem, will be described below.
First of all, every formula or statement that can be formulated in our system gets a unique number, called its Gödel number. This is done in such a way that it is easy to mechanically convert back and forth between formulas and Gödel numbers. Because our system is strong enough to reason about numbers, it is now also possible to reason about formulas.
A formula F(x) that contains exactly one free variable x is called a statement form. As soon as x is replaced by a specific number, the statement form turns into a bona fide statement, and it then is either provable in the system, or not. Statement forms themselves are not statements and therefore cannot be proven or disproven. But every statement form F(x) has a Gödel number which we will denote by G(F).
By carefully analyzing the axioms and rules of the system, one can then write down a statement form P(x) which embodies the idea that x is the Gödel number of a statement which can be proven in our system. Formally: P(x) can be proven if and only if x is the Gödel number of a statement that can be proven. (While this is good enough for this proof sketch, it is technically not completely accurate. See Gödel's paper for the problem and Rosser's paper for the resolution. The key word is "omega-consistency".)
Now comes the trick: a statement form F(x) is called self-unprovable if F(G(F)), i.e. the form F applied to its own Gödel number, is not provable. This concept can be defined formally, and therefore we can construct a statement form SU(x) which embodies the concept: SU(x) is provable if and only if x is the Gödel number of a self-unprovable statement form. Then define the statement p = SU(G(SU)). This is the statement p that was mentioned above.
Intuitively, we are now asking the question: "Is the property of being self-unprovable itself self-unprovable?" This is very reminiscent of the Barber paradox: the barber who shaves precisely those people who don't shave themselves, does he shave himself?
If p were provable, then SU(G(SU)) would be true, and by definition of SU, that would make x = G(SU) the Gödel number of a self-unprovable statement form, hence SU would be self-unprovable, which by definition of self-unprovable means that SU(G(SU)) is not provable, but this was our p: p is not provable. This contradiction shows that p cannot be provable.
If the negation of p were provable, then, assuming our system to be consistent, p cannot also be provable, i.e. SU(G(SU)) is not provable, and by definition of SU this means that x = G(SU) is not the Gödel number of a self-unprovable form, which implies that SU is not self-unprovable. By definition of self-unprovable, we conclude that SU(G(SU)) is provable, hence p is provable. Again a contradiction. This one shows that the negation of p cannot be provable either.
Let p stand for the undecidable sentence constructed above, and let's assume that the consistency of the system can be proven from within the system itself. We have seen above that if the system is consistent, then p is not provable. The proof of this implication can be formalized in the system itself, and therefore the statement "p is not provable", or "not P(p)" can be proven in the system.
But this last statement is equivalent to p itself (and this equivalence can be proven in the system), so p can be proven in the system. This contradiction shows that the system must be inconsistent.
Truth tables are a tool developed by Charles Pierce in the 1880s and used in logic to determine whether an expression is necessarily true, contingently true, or necessarily false, or whether an argument is valid or not. For example, the truth-value of an expression such as '(P ∨ Q) → R' (read as follows: "If either P or Q is true, then R is true") depends on the truth-values of the variables 'P', 'Q', and 'R'. The truth table exhaustively lists, in separate rows, the possible combinations of truth-values of all the variables in the expression, and then outputs the truth-value of the complete expression for each row of the table. If an expression is true in every row of the table, it is necessarily true; if false in every row, it is necessarily false; if it is true in some and false in others, it is neither necessarily true nor necessarily false, but logically contingent.
Truth tables describe the boolean outputs of an expression, circuit, or other computational entity for each possible value of its inputs. The input variables and output expressions are listed as column headings. The rows of the table are filled by listing each possible combination of inputs, one combination per row, and filling in the outputs that result from each combination of inputs.
Example of a truth table in logic:
P | Q | P & Q | P ∨ Q | P xor Q | P → Q | P <-> Q
T | T | T | T | F | T | T
T | F | F | T | T | F | F
F | T | F | T | T | T | F
F | F | F | F | F | T | T
Key:
Contents of old truth tables page--to integrate with the above:
A truth table is the explicit depiction of the relationship of logical operators such as not, and, or, conditional, and biconditional. Generally limited to bivalent logic systems (where only two truth values are possible, true or false), the possible values of the terms involved are enumerated, as well as the result of performing the logical operation on the terms.
For example, take two terms, A and B, and the logical operator "and" (∧), signifying the conjunction "A and B". In common English, if A is true and B is true, then the conjunction "A and B" is true; under all other possible assignments of truth values to A and B, the conjunction is false. This relationship is depicted in a truth table as follows:
A B A ∧ B T T T T F F F T F F F F
In a bivalent logic system, all the operators can be explicitly defined this way. For example, the not (~) relationship is defined as follows:
A ~A T F F T
The or (∨) relationship is defined as follows:
A B A ∨ B T T T T F T F T T F F F
Compound expressions can be constructed, using parenthesis to denote precedence. The negation of conjunction [ ~( A ∧ B ) ], is depicted as follows:
A B A ∧ B ~( A ∧ B ) T T T F T F F T F T F T F F F T
Truth tables can also, then, be used to prove logical equivalence. The truth table for the disjunction of not-A and not-B is:
A B ~A ~B ~A ∨ ~B T T F F F T F F T T F T T F T F F T T T
Because the enumeration of possible truth-values for A and B yeilds the same truth-value under both ~; ( A ∧ B ) and ~A ∨ ~B, the two are logically equivalent, and may be substituted for each other (this particular equivalence is one of DeMorgan's Laws).
A paraconsistent logic is a non-trivial logic which allows inconsitencies. More specifically, it allows both a statement and its negation to be asserted, without absurdity following. In standard logics, anything can be derived from an inconsistency; this is known as ex contradictione quodlibet (ECQ). A paraconsistent logic is then a logical system in which ECQ does not hold.
Paraconsistent logic can be used in modelling belief systems which are inconsistent, and yet from which not anything can be inferred. In standard logics, care has to be taken to not allow such statements as the liar paradox to be formed; paraconsistent logics can be much simplified in that they do not have to excise such statements (though they still have to excise Curry's paradox). Additionally, a paraconsistent logic can potentially overcome the limitation of arithmetic that Goedels incompleteness theorem implies, and be complete.
Approaches to paraconsistent logic include:
The words set theory can be used to mean two subtly different things:
Mathematics (from Greek mathema: science, knowledge, learning; mathematikos: fond of learning) is the study of patterns of quantity, structure, change and space. In the modern view, it is the investigation of axiomatically defined abstract structures using formal logic as the common framework. The specific structures investigated often have their origin in the natural sciences, most commonly in physics, but mathematicians also define and investigate structures for reasons purely internal to mathematics, for instance because they realize that the structure provides a unifying generalization for several subfields or a helpful tool in common calculations. Finally, many mathematicians study in the areas that they do for aesthetic reasons - simply because they find the structures they investigate beautiful in and of themselves.
Historically, the major disciplines within mathematics arose out of the need to do calculations in commerce, to measure land and to predict astronomical events. These three needs can be roughly related to the broad subdivision of mathematics into the study of structure, space and change.
The study of structure starts with numbers, initially the familiar natural numbers and integers. The rules governing arithmetical operations are recorded in elementary algebra, and the deeper properties of whole numbers are studied in number theory. The investigation of methods to solve equations leads to the field of abstract algebra, which, among other things, studies rings and fields, structures that generalize the properties possessed by the familiar numbers. The physically important concept of vector, generalized to vector spaces and studied in linear algebra, belongs to the two branches of structure and space.
The study of space originates with geometry, first the Euclidean geometry and trigonometry of familiar three-dimensional space, but later also generalized to non-Euclidean geometries which play a central role in general relativity. Several long standing questions about ruler and compass constructions were finally settled by Galois theory. The modern fields of differential geometry and algebraic geometry generalize geometry in different directions: differential geometry emphasizes the concepts of coordinate system, smoothness and direction, while in algebraic geometry geometrical objects are described as solution sets of polynomial equations. Group theory investigates the concept of symmetry abstractly and provides a link between the studies of space and structure. Topology connects the study of space and the study of change by focusing on the concept of continuity.
Understanding and describing the change in measurable quantities is the common theme of the natural sciences, and calculus was developed as a most useful tool for doing just that. The central concept used to describe a changing variable is that of a function. Many problems lead quite naturally to relations between a quantity and its rate of change, and the methods to solve these are studied in the field of differential equations. The numbers used to represent continuous quantities are the real numbers, and the detailed study of their properties and the properties of real-valued functions is known as real analysis. For several reasons, it is convenient to generalise to the complex numbers which are studied in complex analysis. Functional analysis focuses attention on (typically infinite-dimensional) spaces of functions, laying the groundwork for quantum mechanics among many other things.
In order to clarify and investigate the foundations of mathematics, the fields of set theory, mathematical logic and model theory were developed.
When computers were first conceived, several surrounding theoretical questions were tackled by mathematicians, leading to the fields of computability theory, computational complexity theory, information theory and algorithmic information theory. Many of these questions are now investigated in theoretical computer science.
Computers also aided the new field of chaos theory, which deals with the fact that many dynamical systems in nature obey laws that cause their behaviour to become unpredictable in practice, though deterministic in theory. Chaos theory is closely related to the geometry of fractals such as the Mandelbrot set.
An important field in applied mathematics is probability and statistics, which allows the description, analysis and prediction of random phenomena and is used in all sciences. Numerical analysis investigates the methods of efficiently solving various mathematical problems numerically on computers and takes rounding errors into account. Discrete mathematics is the common name for those fields of mathematics useful in computer science.
An alphabetical list of mathematical topics is available; together with the "Watch links" feature, this list is useful to track changes in mathematics articles. The following list of subfields and topics reflects one organizational view of mathematics.
A natural number is any of the numbers 0, 1, 2, 3... that can be used to measure the size of finite sets.
Some mathematicians (especially number theorists) prefer not to regard zero as a natural number, while some others (especially set theorists, logicians and computer scientists) take the opposite stance. In this encyclopedia, zero is considered to be a natural number.
Though even a small child will understand what we mean by natural numbers, their definition has not been easy. The Peano postulates essentially uniquely describe the set of natural numbers, which is denoted by N (or more properly, an N in blackboard bold).
The last postulate ensures that the proof technique of mathematical induction is valid.
A standard construction in set theory is to define each natural number as the set of natural numbers less than it, so that 0 = {}, 1 = {0}, 2 = {0,1}, 3 = {0,1,2}... when you see a natural number used as a set this is typically what is meant.
One can inductively define an addition on the natural numbers by requiring a + (b + 1) = (a + b) + 1. This turns the natural numbers (N, +) into a commutative monoid with neutral element 0, the so-called free monoid with one generator. This monoid satisfies the cancellation property and can therefore be embedded in a group. The smallest group containing the natural numbers is the integers.
Analogously, a multiplication * can be defined via a * (b + 1) = ab + a. This turns (N, *) into a commutative monoid; addition and multiplication are compatible which is expressed in the distribution law: a * (b + c) = ab + ac.
Furthermore, one defines a total order on the natural numbers by writing a <= b if and only if there exists another natural number c with a + c = b. This order is compatible with the arithmetical operations in the following sense: if a, b and c are natural numbers and a <= b, then a + c <= b + c and ac <= bc. An important property of the natural numbers is that they are well-ordered: every set of natural numbers has a smallest element.
While it is in general not possible to divide one natural number by another and get a natural number as result, the procedure of division with remainder is available as a substitute: For any two natural numbers a and b with b <> 0 we can find natural numbers q and r such that
The number q is called the quotient and r is called the remainder of division of a by b. The numbers q and r are uniquely determined by a and b.
The deeper properties of the natural numbers, such as the distribution of prime numbers for example, are studied in number theory.
Natural numbers can be used for two purposes: to describe the position of an element in an ordered sequence, which is generalized by the concept of ordinal number, and to specify the size of a finite set, which is generalized by the concept of cardinal number. In the finite world, these two concepts coincide: the finite ordinals are equal to N as are the finite cardinals. When moving beyond the finite, however, the two concepts diverge.
The real numbers are those numbers that are used to represent a continuous quantity (including 0 and negatives). One may think of a real number as a possibly infinite decimal fraction, such as 324.823211247...; the real numbers also stand in a one-to-one correspondence with the points on a line. Measurements in the physical sciences are almost always expressed as real numbers. The real numbers are the central object of study in the mathematical field of real analysis.
The real numbers contain the integers and the rational numbers as well as irrational numbers such as the square root of 2 and transcendental numbers such as pi (π).
Computers can only approximate most real numbers with rational numbers; these approximations are known as floating point numbers or fixed point numbers. (See real data type.) Computer algebra systems are able to treat some real numbers exactly by storing their algebraic description (such as sqrt(2)) rather than their decimal approximation.
The term "real number" is a retronym coined in response to "imaginary number".
Mathematicians use the symbol R (or alternatively, ℝ, an R in blackboard bold) to represent the set of all real numbers.
What follows is a rigorous mathematical description of the concept.
Let R denote the set of all real numbers. Then:
The latter property is what differentiates the reals from the rationals. For example, the set of rationals with square less than 2 has a rational upper bound (e.g., 1.5) but no rational least upper bound, because the square root of 2 is not rational.
The real numbers are uniquely specified by the above properties. More precisely, given any two Dedekind complete ordered fields R1 and R2, there exists a unique field isomorphism from R1 to R2, allowing us to think of them as essentially the same mathematical object.
The main reason for introducing the reals is that the reals contain all limits. More technically, the reals are complete (in the sense of metric spaces or uniform spaces, which is a different sense than the Dedekind completeness of the order in the previous section). This means the following:
A sequence (xn) of real numbers is called a Cauchy sequence if for any ε > 0 there exists an integer N (possibly depending on ε) such that the distance |xn - xm| is less than ε provided that n and m are both greater than N. In other words, a sequence is a Cauchy sequence if its elements xn eventually come and remain arbitrarily close to each other.
A sequence (xn) converges to the limit x if for any ε > 0 there exists an integer N (possibly depending on ε) such that the distance |xn - x| is less than ε provided that n is greater than N. In other words, a sequence has limit x if its elements eventually come and remain arbitrarily close to x.
It is easy to see that every convergent sequence is a Cauchy sequence. Now the important fact about the real numbers is that the converse is true:
That is, the reals are complete.
Note that the rationals are not complete. For example, the sequence (1,1.4,1.41,1.414,1.4142,1.41421,...) is Cauchy but it does not converge to a rational number. (In the real numbers, in contrast, it converges to the square root of 2.)
The existence of limits of Cauchy sequences is what makes calculus work and is of great practical use. The standard numerical test to determine if a sequence has a limit is to test if it is a Cauchy sequence, as the limit is typically not known in advance.
For example the standard series of the exponential function
converges to a real number because for every x the sums
can be made arbitrarily small by choosing N sufficiently large. This proves that the sequence is Cauchy, so we know that the sequence converges even if we don't know ahead of time what the limit is.
If we have a space where Cauchy sequences are meaningful (such as a metric space, i.e., a space where distance is defined, or more generally a uniform space), a standard procedure to force all Cauchy sequences to converge is adding new points to the space (a process called completion). By starting with rational numbers and the metric d(x,y) = |x - y|, we can construct the real numbers, as will be detailed below. (If we started with a different metric on the rationals, we'd end up with the p-adic numbers instead.)
Let R be the set of Cauchy sequences of rational numbers. Cauchy sequences (xn) and (yn) can be added, multiplied and compared as follows:
Two Cauchy sequences are called equivalent if the sequence (xn - yn) has limit 0. This does indeed define an equivalence relation, it is compatible with the operations defined above, and the set R of all equivalence classes can be shown to satisfy all the axioms of the real numbers given above. We can embed the rational numbers into the reals by identifying the rational number r with the sequence (r,r,r,...).
A practical and concrete representative for an equivalence class representing a real number is provided by the representation to base b -- in practice, b is usually 2 (binary), 8 (octal), 10 (decimal) or 16 (hexadecimal). For example, the number π = 3.14159... corresponds to the Cauchy sequence (3,3.1,3.14,3.141,3.1415,...). Notice that the sequence (0,0.9,0.99,0.999,0.9999,...) is equivalent to the sequence (1,1.0,1.00,1.000,1.0000,...); this shows that 0.9999... = 1.
The real numbers are often described as "the complete ordered field", a phrase that can be interpreted in several ways.
First, an order can be lattice complete. It's easy to see that no ordered field can be lattice complete, because it can have no largest element (given any element z, z + 1 is larger). So this is not the sense that is meant.
Additionally, an order can be Dedekind complete, as defined in the section Axioms. The uniqueness result at the end of that section justifies using the word "the" in the phrase "complete ordered field" when this is the sense of "complete" that is meant. This sense of completeness is most closely related to the construction of the reals from Dedekind cuts, since that construction starts from an ordered field (the rationals) and then forms the Dedekind completion of it in a standard way.
These two notions of completeness ignore the field structure. However, an ordered group (and a field is a group under the operations of addition and subtraction) defines a uniform structure, and uniform structures have a notion of completeness; the description in the section Completeness above is a special case. (We refer to the notion of completeness in uniform spaces rather than the related and better known notion for metric spaces, since the definition of metric space relies on already having a characterisation of the real numbers.) It is not true that R is the only uniformly complete ordered field, but it is the only uniformly complete Archimedean field, and indeed one often hears the phrase "complete Archimedean field" instead of "complete ordered field". Since it can be proved that any uniformly complete Archimedean field must also be Dedekind complete (and vice versa, of course), this justifies using "the" in the phrase "the complete Archimedean field". This sense of completeness is most closely related to the construction of the reals from Cauchy sequences (the construction carried out in full in this article), since it starts with an Archimedean field (the rationals) and forms the uniform completion of it in a standard way.
But the original use of the phrase "complete Archimedean field" was by David Hilbert, who meant still something else by it. He meant that the real numbers form the largest Archimedean field in the sense that every other Archimedean field is a subfield of R. Thus R is "complete" in the sense that nothing further can be added to it without making it no longer an Archimedean field. This sense of completeness is most closely related to the construction of the reals from surreal numbers, since that construction starts with a proper class that contains every ordered field (the surreals) and then selects from it the largest Archimedean subfield.
The reals are uncountable, that is, there are strictly more real numbers than natural numbers (even though both sets are infinite). This is proved with Cantor's diagonal argument. In fact, the cardinality of the reals is 2ω (see cardinal numbers), i.e., the cardinality of the set of subsets of the natural numbers. Since only a countable set of real numbers can be algebraic, almost all real numbers are transcendental. The nonexistence of a subset of the reals with cardinality strictly in between that of the integers and the reals is known as the continuum hypothesis. This can neither be proved nor be disproved, but is independent from the axioms of set theory.
The real numbers form a metric space: the distance between x and y is defined to be the absolute value |x - y|. By virtue of being a totally ordered set, they also carry an order topology; the topology arising from the metric and the one arising from the order are identical. The reals are a contractible (hence connected and simply connected), locally compact separable metric space, of dimension 1, and are everywhere dense. The real numbers are not compact. There are various properties that uniquely specify them; for instance, all unbounded, continuous, and separable order topologies are necessarily homeomorphic to the reals.
Every nonnegative real number has a square root, and no negative number does. This shows that the order on R is determined by its algebraic structure. Also, every polynomial of odd degree admits at least one root: these two properties make R the premier example of a real closed field. Proving this is the first half of one proof of the fundamental theorem of algebra.
The reals carry a canonical measure, the Lebesgue measure, which is the Haar measure on their structure as a topological group normalised such that the unit interval [0,1] has measure 1.
The supremum axiom of the reals refers to subsets of the reals and is therefore a second-order logical statement. It is not possible to characterize the reals with first-order logic alone: the Lowenheim-Skolem theorem implies that there exists a countable dense subset of the real numbers satisfying exactly the same sentences in first order logic as the real numbers themselves. The set of hyperreal numbers is much bigger than R but also satisfies the same first order sentences as R. Ordered fields that satisfy the same first-order sentences as R are called nonstandard models of R. This is what makes nonstandard analysis work; by proving a first-order statement in some nonstandard model (which may be easier than proving it in R), we know that the same statement must also be true of R.
The real numbers can be generalized and extended in several different directions. Perhaps the most natural extension are the complex numbers which contain solutions to all polynomial equations. However, the complex numbers are not an ordered field. Ordered fields extending the reals are the hyperreal numbers and the surreal numbers; both of them contain infinitesimal and infinitely large numbers and thus are not Archimedean. Occasionally, formal elements +∞ and -∞ are added to the reals to form the extended real number line, a compact space which is not a field anymore but retains many of the properties of the real numbers. Self-adjoint operators on a Hilbert space (for example, self-adjoint square complex matrices) generalize the reals in many respects: they can be ordered (though not totally ordered), they are complete, all their eigenvalues are real and they form a real associative algebra. Positive-definite operators correspond to the positive reals and normal operators correspond to the complex numbers.
Fractions had been used by the Egyptians around 1000 BC; the Greek mathematicians around 500 BC realized the need for irrational numbers. Negative numbers began to be generally accepted in the 1600s. The development of the calculus in the 1700s used the entire set of real numbers without having defined them cleanly. The first rigorous definition was given by Georg Cantor in 1871, which is essentially the same construction used in this article.
A rational number is a number that can be expressed as the ratio between two integers, usually written as a fraction a / b, where the denominator (here b) is not equal to zero. Rational numbers are commonly called "fractions"; they are precisely those numbers whose decimal digit expansion is either finite or periodic. The set of all rational numbers is denoted by Q, usually in blackboard bold.
A number that is not rational is called an irrational number.
Mathematically we may define them as an ordered pair of integers (a, b), with b not equal to zero. We can define addition and multiplication upon these pairs with the following rules:
To conform to our expectation that 2/4 = 1/2, we define an equivalence relation ~ upon these pairs with the following rule:
This equivalence relation is compatible with the addition and multiplication defined above, and we may define Q to be the quotient set of ~, i.e. we identify two pairs (a, b) and (c, d) if they are equivalent in the above sense.
We can also define a total order on Q by writing
The set of all rational numbers is countable.
The set Q, together with the addition and multiplication operations shown above, forms a field, the quotient field of the integers Z. In fact, the rationals are an ordered field, and therefore have characteristic 0. Furthermore, the rationals are the smallest field with characteristic 0: every other field of characteristic 0 contains a copy of Q.
The rationals are a densely ordered set: between any two rationals there sits another one, in fact infinitely many other ones.
By virtue of their order, the rationals carry an order topology. The rational numbers are a (dense) subset of the real numbers, and as such they also carry a subspace topology. The rational numbers form a metric space by using the metric d(x,y) = |x - y|, and this yields a third topology on Q. Fortunately, all three topologies coincide and turn the rationals into a topological field. The rational numbers are an important example of a space which is not locally compact. The space is also totally disconnected. The rational numbers are not complete; the real numbers are the completion of Q. Real numbers which are not rational are called irrational.
Any positive rational number can be expressed as a sum of distinct reciprocals of positive integers. For instance, 5/7 = 1/2 + 1/6 + 1/21. For any positive rational number, there are infinitely many different such representations. These representations are called Egyptian fractions, because the ancient Egyptians used them. The hieroglyph used for this is the letter that looks like a mouth, which is transliterated R, so the above fraction would be written as R2R6R21. The Egyptians also had a different notation for dyadic fractions.
In addition to the absolute value metric mentioned above, there are other metrics which turn Q into a topological field: let p be a prime number and for any non-zero integer a let |a|p = p-n, where pn is the highest power of p dividing a; in addition write |0|p = 0. For any rational number a/b, we set |a/b|p = |a|p / |b|p. Then dp(x, y) = |x - y|p defines a metric on Q. The metric space (Q, dp) is not complete, and its completion is given by the p-adic numbers.
An irrational number is any real number that is not a rational number, i.e., that cannot be written as a fraction a / b with a and b integers and b not zero.
There are two types of irrational numbers, the algebraic ones such as 21/2 (the square root of 2) and 31/3 (the cube root of 3), and the transcendental numbers such as π and e.
Perhaps the numbers most easily proved to be irrational are logarithms like log23. The argument by reductio ad absurdum is as follows:
The discovery of irrational number is usually attributed attributed to Pythagoras or one of his followers, who produced a (most likely geometrical) proof of the irrationality of the square root of 2.
One proof of this irrationality is the following reductio ad absurdum.
This proof can be generalized to show that any root of any natural number is either a natural number or irrational.
Another reductio ad absurdum showing that √2 is irrational is less well-known and has sufficient charm that it is worth including here. It proceeds by observing that if √2=m/n then √2=(2n-m)/(m-n), so that a fraction in lowest terms is reduced to yet lower terms. That is a contradiction if n and m are positive integers, so the assumption that √2 is rational must be false. It is possible to construct from an isosceles right triangle whose leg and hypotenuse have respective lengths n and m, by a classic straightedge-and-compass construction, a smaller isosceles right triangle whose leg and hypotenuse have respective lengths m-n and 2n-m. That construction proves the irrationality of √2 by the kind of method the was employed by ancient Greek geometers.
All transcendental numbers are irrational, and the article on transcendental numbers lists several examples. er is irrational if r ≠ 0 is rational; πn is irrational for positive integers n.
Another way to construct irrational numbers is as zeros of polynomials: start with a polynomial equation
where the coefficients ai are integers. Suppose you know that there exists some real number x with p(x) = 0 (for instance because of the intermediate value theorem). The only possible rational roots of this polynomial equation are of the form r/s where r is a divisor of a0 and s is a divisor of an; there are only finitely many such candidates which you an all check by hand. If neither of them is a root of p, then x must be irrational. For example, this technique can be used to show that x = (21/2 + 1)1/3 is irrational: we have (x3 - 1)2 = 2 and hence x6 - 2x3 -1 = 0, and this latter polynomial doesn't have any rational roots (the only candidates to check are ±1).
It is not known whether 2e, πe, π√2 or the Euler-Mascheroni gamma constant γ are irrational.
The set of all irrational numbers is uncountable (since the rationals are countable and the reals are uncountable). Using the absolute value to measure distances, the irrational numbers become a metric space which is not complete. However, this metric space is homeomorphic to the complete metric space of all sequences of positive integers; the homeomorphism is given by the infinite continued fraction expansion. This shows that the Baire category theorem applies to the space of irrational numbers.
The integers, or whole numbers, consist of the natural numbers (0, 1, 2, ...) and the negative whole numbers (-1, -2, -3, ...). The set of all integers is usually denoted by Z (more properly, a Z in blackboard bold), which stands for Zahlen (German for "number").
Integers can be added and subtracted, multiplied, and compared. The main reason for introducing the negative numbers is that it becomes possible to solve all equations of the form
for the unknown x; over the natural numbers, only some of those equations are solvable.
Mathematicians express the fact that all the usual laws of arithmetic are valid in the integers by saying that (Z, +, *) is a commutative ring.
The ordering on Z is given by ... < -2 < -1 < 0 < 1 < 2 < ... and it turns Z into a totally ordered set without upper or lower bound. We call an integer positive if it is greater than zero; zero itself is not considered to be positive. The order is compatible with the algebraic operations in the following way:
Like the natural numbers, the integers form a countably infinite set.
The integers do not form a field since for instance there is no integer x such that 2x = 1. The unique smallest field containing the integers is given by the rational numbers.
An important property of the integers is division with remainder: given two integers a and b with b≠0, we can always find integers q and r such that
and such that 0 <= r < |b| (see absolute value). q is called the quotient and r is called the remainder resulting from division of a by b. The numbers q and r are uniquely determined by a and b. This division makes possible the Euclidean algorithm for computing greatest common divisors, which also shows that the greatest common divisor of two integers can always be written as a sum of multiples of the two numbers.
All of this can be abbreviated by saying that Z is a Euclidean domain. It implies that Z is a principal ideal domain and that whole numbers can be written as products of primes in an essentially unique way. This is the fundamental theorem of arithmetic.
The branch of mathematics which studies the integers is called number theory.
From Wikipedia, the free encyclopedia.
A transcendental number is any real or complex number that is not an algebraic number, i.e., it is not the solution of any polynomial equation of the form
where n ≥ 1 and the coefficients ai are integers (or, equivalently, rationals), not all 0.
The set of algebraic numbers is countable while the set of all real numbers is uncountable; this implies that the set of all transcendental numbers is also uncountable, so in a very real sense there are many more transcendental numbers than algebraic ones. However, only few classes of transcendental numbers are known and proving that a given number is transcendental can be extremely difficult.
The existence of transcendental numbers was first proved in 1844 by Joseph Liouville, who exhibited examples, including the Liouville constant
in which the nth digit after the decimal point is 1 if n is a factorial (i.e., 1, 2, 6, 24, 120, 720, ...., etc.) and 0 otherwise. The first number to be proved transcendental without having been specifically constructed to achieve this was e, by Charles Hermite in 1873. In 1882, Carl Louis Ferdinand von Lindemann published a proof that the number pi is transcendental. In 1874, Georg Cantor found the argument described above establishing the ubiquity of transcendental numbers.
Here is a list of numbers known to be transcendental:
The discovery of transcendental numbers allowed the proof of the impossibility of several ancient geometric problems involving ruler and compass construction; the most famous one, squaring the circle, is impossible because π is transcendental.
The complex numbers are a natural extension of the real numbers: the real number line can be viewed as a subset of the complex number plane. Every complex number can be visualized as a point in the plane; using the definitions below, it becomes possible to add, subtract, multiply and divide such points.
Formally we may define complex numbers as ordered pairs of real numbers (a, b) together with the operations:
So defined, the complex numbers form a field, the complex number field, denoted by C (properly, a C in blackboard bold). If we identify the real number a with the complex number (a, 0), then the field of real numbers R becomes a subfield of C. Furthermore, C forms a two-dimensional real vector space. Unlike the reals, complex numbers cannot be ordered in any way that is compatible with its arithmetic operations: C cannot be turned into an ordered field.
The complex number i = (0, 1) is called the imaginary unit. It is an imaginary number and it satisfies i2 = -1 (remember that we don't distinguish between (-1, 0) and -1). Every complex number z can then be written as z = a + i b, where a and b are real numbers uniquely determined by z. The number a is called the real part of z and b is the imaginary part of z.
Geometrically, the algebraic operations on complex numbers can be understood as follows: to add two complex numbers z1 = a1 + ib1 and z2 = a2 + ib2, we think of them as vectors in the x-y plane pointing from the origin to the point (a1, b1) and (a2, b2), respectively. Then we translate (move) the second vector, without changing its direction, so that its base point coincides with the first vector's tip; the second vector's tip will then correspond to the complex number z1 + z2. In order to multiply the two numbers z1 and z2, we first measure their respective counter clockwise angles with the positive x-axis and add these angles up: the resulting angle corresponds to the product vector z1 · z2. The length of this product vector is given by the product of the lengths of the two original vectors. Multiplication with a fixed complex number can
therefore be seen as a simultaneous rotation and stretching. Multiplication with i corresponds to a counter clockwise rotation by 90 degrees. Even the fact (-1) · (-1) = +1 from arithmetic can be understood geometrically as the combination of two 180 degree turns.
Sometimes, the representation of complex numbers in the form z = a + i b ("rectangular coordinates") is not as convenient as using polar coordinates: every non-zero complex number z can be written as z = r eiφ where r is a positive real number and the angle φ is a real number (see Euler's formula). Every pair (r, φ) of "polar coordinates" defines a unique non-zero complex number z in this fashion. The angle φ however is not uniquely defined by z since Euler's formula implies z = r ei(φ + 2πk) for any integer k. Because of this, one generally restricts φ to the interval (-π, π] and calls it the principal argument of z and writes φ = arg(z). With this convention, the polar coordinates are uniquely defined by z.
The multiplication of complex numbers is especially easy if the numbers are represented in polar coordinates: r eiφ · s eiψ = (rs) ei(φ + ψ). Division of complex numbers as well as exponentiation are also easy in polar coordinates. Addition however is cumbersome in this representation.
The absolute value or magnitude of a complex number z is its euclidean distance from the origin, if we think of z as a point in the plane. We denote it by |z|; it is always a non-negative real number. Algebraically, if z = a + ib, we can define |z| = sqrt(a2 + b2 ). If the complex number z is written in polar coordinates z = r eiφ, then |z| = r.
One can check readily that the absolute value has three important properties:
for all complex numbers z and w. By defining the distance function d(z, w) = |z - w| we turn the complex numbers into a metric space and we can therefore talk about limits and continuity. The addition, subtraction, multiplication and division of complex numbers are then continuous operations. Unless anything else is said, this is always the metric being used on the complex numbers.
The complex conjugate of the complex number z = a + ib is defined to be z* = a - ib. The following can be checked:
The latter formula is the method of choice to compute the inverse of a complex number if it is given in rectangular coordinates.
A root of the polynomial p is a complex number z such that p(z) = 0. A most striking result is that all polynomials of degree n with real or complex coefficients have exactly n complex roots (counting multiple roots according to their multiplicity). This is known as the Fundamental Theorem of Algebra, and shows that the complex numbers are an algebraically closed field. Because of this, mathematicians sometimes consider the complex numbers to be more "natural" than the real numbers: all polynomial equations have solutions among the complex numbers, which is not true for the real numbers.
The study of functions of a complex variable is known as complex analysis and has enormous practical use in applied mathematics as well as in other branches of mathematics. Often, the most natural proofs for statements in real analysis or even number theory employ techniques from complex analysis (see prime number theorem for an example). Unlike real functions which are commonly represented as two dimensional graphs, complex functions have four dimensional graphs and may usefully be illustrated by color coding a three dimensional graph to suggest four dimensions, or by animating the complex function's dynamic transformation of the complex plane.
While usually not useful, alternative representations of complex field can give some insight into their nature. One particularly elegant representation interprets every complex number as 2x2 matrix with real entries which stretches and rotates the points of the plane. Every such matrix has the form
/ a -b \ \ b a /
with real numbers a and b. The sum and product of two such matrices is again of this form. Every non-zero such matrix is invertible, and its inverse is again of this form. Therefore, the matrices of this form are a field. In fact, this is exactly the field of complex numbers. Every such matrix can be written as
/ a -b \ = a / 1 0 \ + b / 0 -1 \ \ b a / \ 0 1 / \ 1 0 /
which suggests that we should identify the real number one with the matrix
/ 1 0 \ \ 0 1 /
and the imaginary unit with
/ 0 -1 \ \ 1 0 /
a rotation by 90 degrees. Note that the square of this latter matrix is indeed equal to -1.
The absolute value of a complex number expressed as a matrix is equal to the square root of the determinant of that matrix. If the matrix is viewed as a transformation of a plane, then the transformation rotates points through an angle equal to the argument of the complex number and scales by a factor equal to the complex number's absolute value. The conjugate of the complex number z corresponds to the transformation which rotates through the same angle as z but in the opposite direction, and scales in the same manner as z; this can be described by the transpose of the matrix corresponding to z.
Complex numbers are used in electrical engineering and other fields as a convenient description for periodically varying signals (see Fourier analysis). In an expression z = r eiφ one may think of r as the amplitude and φ as the phase of a sine wave of given frequency. Furthermore, when representing a sinusoidal current or voltage as the real part of a complex valued function of the form
where ω represents the angular frequency and the complex number z encodes the phase and amplitude, the treatment of resistors, capacitors and inductors can be unified by introducing imaginary resistances for the latter two (see electrical network). Electrical engineers and some physicists use the letter j for the imaginary unit since i is typically reserved for varying currents.
The complex number field is also of utmost importance in quantum mechanics since the underlying theory is built on (infinite dimensional) Hilbert spaces over C.
In Special and general relativity, some formulas for the metric on spacetime become simpler if one takes the time variable to be imaginary.
In differential equations, it is common to first find all complex roots r of the characteristic equation of a linear differential equation and then attempt to solve the system in terms of base functions of the form f(t) = ert.
In algebra, a polynomial function, or polynomial for short, is a function of the form
where x is a scalar-valued variable, and a0,...,an are fixed scalars, called the coefficients of the polynomial f. The highest occurring power of x (n if the coefficient an is not zero) is called the degree of f; its coefficient is called the leading coefficient. a0 is called the constant coefficient of f. Each summand of the polynomial of the form ak xk is called a term.
In calculus, the scalars are almost always real or complex numbers.
The polynomial can be written in sigma notation as: ''
'' Polynomials of
The function f(x) = -7 x3 + 2/3 x2 - 5 x + 3 is an example of a cubic function with leading coefficient -7 and constant coefficient 3.
Polynomials are important because they are the simplest functions: their definition involves only addition and multiplication (since the powers are just shorthands for repeated multiplications). They are also simple in a different sense: the polynomials of degree ≤ n are precisely those functions whose (n+1)st derivative is identically zero. One important aspect of calculus is the project of analyzing complicated functions by means of approximating them with polynomials. The culmination of these efforts is Taylor's theorem, which roughly states that every differentiable function locally looks like a polynomial, and the Weierstrass approximation theorem, which states that every continuous function defined on a compact interval of the real axis can be approximated on the whole interval as closely as desired by a polynomial.
Quotients of polynomials are called rational functions. These are the only functions that can be evaluated directly on a computer, since typically only the operations of addition, multiplication and division are implemented in hardware. All the other functions that computers need to evaluate, such as trigonometric functions, logarithms and exponential functions, must then be approximated in software by suitable rational functions.
In order to determine function values of polynomials for given values of the variable x, one does not apply the polynomial as a formula directly, but uses the much more efficient Horner scheme instead. If the evaluation of a polynomial at many equidistant points is required, Newton's difference method reduces the amount of work dramatically. The Difference Engine of Charles Babbage was designed to create large tables of values of logarithms and trigonometric functions automatically by evaluating approximating polynomials at many points using Newton's difference method.
A root or zero of the polynomial f(x) is a number r such that f(r) = 0. Determining the roots of polynomials, or "solving algebraic equations", is among the oldest problems in mathematics. Some polynomials, such as f(x) = x2 + 1, do not have any roots among the real numbers. If however the set of allowed candidates is expanded to the complex numbers, every (non-constant) polynomial has a root (see Fundamental Theorem of Algebra).
Approximations for the real roots of a given polynomial can be found using Newton's method, or more efficiently using Laguerre's method which employs complex arithmetic and can locate all complex roots. These algorithms are studies in numerical analysis.
There is a difference between approximating roots and finding concrete closed formulas for them. Formulas for the roots of polynomials of degree up to 4 have been known since the sixteenth century (see quadratic formula, Cardano, Tartaglia). But formulas for degree 5 eluded researchers for a long time. In 1824, Abel proved the striking result that there can be no general formula (involving only the arithmetical operations and radicals) for the roots of a polynomial of degree ≥ 5 in terms of its coefficients (see Abel-Ruffini theorem). This result marked the start of Galois theory which engages in a detailed study of relations among roots of polynomials.
In multivariate calculus, ''polynomials in several variables'' play an important role. These are the simplest multivariate functions and can be defined using addition and multiplication alone. An example of a polynomial in the variables x, y, and z is
The total degree of such a multivariate polynomial can be gotten by adding the exponents of the variables in every term, and taking the maximum. The above polynomial f(x,y,z) has total degree 6.
In abstract algebra, one has to carefully distinguish between polynomials and polynomial functions. A polynomial f is defined to be a formal expression of the form
where the coefficients a0, ... , an are elements of some ring R and X is considered to be a formal symbol. Two polynomials are considered to be equal if and only if the sequences of their coefficients are equal. Polynomials with coefficients in R can be added by simply adding corresponding coefficients and multiplied using the distributive law and the rules
One can then check that the set of all polynomials with coefficients in the ring R forms itself a ring, the ring of polynomials over R, which is denoted by R[X]. If R is commutative, then R[X] is an algebra over R.
One can think of the ring R[X] as arising from R by adding one new element X to R and only requiring that X commute with all elements of R. In order for R[X] to form a ring, all sums of powers of X have to be included as well. Formation of the polynomial ring, together with forming factor rings by factoring out ideals, are important tools for constructing new rings out of known ones. For instance, the clean construction of finite fields involves the use of those operations, starting out with the field of integers modulo some prime number as the coefficient ring R (see modular arithmetic).
To every polynomial f in R[X], one can associate a polynomial function with domain and range equal to R. One obtains the value of this function for a given argument r by everywhere replacing the symbol X in f's expression by r. The reason that algebraists have to distinguish between polynomials and polynomial functions is that over some rings R (for instance over finite fields), two different polynomials may give rise to the same polynomial function. This is not the case over the real or complex numbers and therefore analysts don't separate the two concepts.
In commutative algebra, one major focus of study is divisibility among polynomials. If R is an integral domain and f and g are polynomials in R[X], we say that f divides g if there exists a polynomial q in R[X] such that f q = g. One can then show that "every zero gives rise to a linear factor", or more formally: if f is a polynomial in R[X] and r is an element of R such that f(r) = 0, then the polynomial (X - r) divides f. The converse is also true. The quotient can be computed using the Horner scheme.
If F is a field and f and g are polynomials in F[X] with g ≠ 0, then there exist polynomials q and r in F[X] with
and such that that the degree of r is smaller than the degree of g. The polynomials q and r are uniquely determined by f and g. This is called "division with remainder" or "long division" and shows that the ring F[X] is a euclidean domain.
One also speaks of polynomials in several variables, obtained by taking the ring of polynomials of a ring of polynomials: R[X,Y] = (R[X])[Y] = (R[Y])[X]. These are of fundamental importance in algebraic geometry which studies the simultaneous zero sets of several such multivariate polynomials.
Polynomials are frequently used to encode information about some other object. The characteristic polynomial of a matrix or linear operator contains information about the operator's eigenvalues. The minimal polynomial of an algebraic element records the simplest algebraic relation satisfied by that element.
Other related objects studied in abstract algebra are formal power series, which are like polynomials but may have infinite degree, and the rational functions, which are ratios of polynomials.
Presburger arithmetic is the first-order theory of the natural numbers with addition. It is not as powerful as the Peano axioms because multiplication is omitted. In fact, Presburger proved in 1929 that there is an algorithm which decides for any given statement in Presburger arithmetic whether it is true or not. No such algorithm exists for general arithmetic as a consequence of the negative answer to the Entscheidungsproblem. Furthermore, Presburger proved that his arithmetic is consistent (does not contain contradictions) and complete (every statement can either be proven or disproven). Again, this is false for general arithmetic; this is the content of Gödel's incompleteness theorem.
Presburger arithmetic is an interesting example in computational complexity theory and computation because Fischer and Rabin proved in 1974 that every algorithm which decides the truth of Presburger statements has a runtime of at least 2^(2^(cn)) for some constant c. Here, n is the length of the Presburger statement. Hence, the problem is one of the few that provably need more than polynomial run time.
In the formal description of the theory, we use the object constants 0 and 1, the function constant +, and the predicate constant =. The axioms are:
Concepts such as divisibility or prime number cannot be formalized in Presburger arithmetic. Here is a typical theorem that can be proven from the above axioms:
It says that if x ≤ y + 1, then y + 2 > x.
In mathematics, a ring is an algebraic structure in which addition and multiplication are defined and have similar properties to those familiar from the integers.
A ring is an abelian group (R, +), together with a second binary operation * such that for all a, b and c in R,
and such that there exists a multiplicative identity, or unity, that is, an element 1 so that for all a in R,
Some authors omit the requirement for a multiplicative identity, and call those rings which do have multiplicative identities unitary rings. In this encyclopedia, the existence of a multiplicative identity is taken to be part of the definition.
The symbol * is usually omitted from the notation, so that a * b is just written ab.
From the axioms, one can immediately deduce that
for all elements a and b in R. Here, 0 is the neutral element with respect to addition +, and -x stands for the additive inverse of the element x in R.
An element a in a ring is called invertible if there is an element b such that
If that is the case, b is uniquely determined by a and we write a-1 = b. The set of all invertible elements in a ring is closed under multiplication * and therefore forms a group, the group of units of the ring. If both a and b are invertible, then we have
Rings that sit inside other rings are called subrings. Maps between rings which respect the ring operations are called ring homomorphisms. Rings, together with ring homomorphisms, form a category. Closely related is the notion of ideals, certain subsets of rings which arise as kernels of homomorphisms and can serve to define factor rings. Basic facts about ideals, homomorphisms and factor rings are recorded in the isomorphism theorems and in the Chinese remainder theorem.
A ring is called commutative if its multiplication is commutative. The theory of commutative rings resembles the theory of numbers in several respects, and various definitions for commutative rings are designed to recover properties known from the integers. Commutative rings are also important in algebraic geometry. In commutative ring theory, numbers are often replaced by ideals, and the definition of prime ideal tries to capture the essence of prime numbers. Integral domains, non-trivial commutative rings where no two non-zero elements multiply to give zero, generalize another property of the integers and serve as the proper realm to study divisibility. Principal ideal domains are integral domains in which every ideal can be generated by a single element, another property shared by the integers. Euclidean domains are integral domains in which the Euclidean algorithm can be carried out. Important examples of commutative rings can be constructed as rings of polynomials and their factor rings.
Non-commutative rings resemble rings of matrices in many respects. Following the model of algebraic geometry, attempts have been made recently at defining non-commutative geometry based on non-commutative rings. Non-commutative rings and associative algebras (rings that are also vector spaces) are often studied via their categories of modules. A module over a ring is an abelian group that the ring acts on as a ring of endomorphisms, very much akin to the way fields (integral domains in which every non-zero element is invertible) act on vector spaces. Examples of non-commutative rings are given by rings of square matrices or more generally by rings of endomorphisms of abelian groups or modules, and by monoid rings.
Any ring can be seen as a preadditive category with a single object. It is therefore natural to consider arbitrary preadditive categories to be generalizations of rings. And indeed, many definitions and theorems originally given for rings can be translated to this more general context. Additive functors between preadditive categories generalize the concept of ring homomorphism, and ideals in additive categories can be defined as sets of morphisms closed under addition and under composition with arbitrary morphisms.
In mathematics and computer science, Boolean algebras are algebraic structures which capture the essence of the logical operations AND (represented by ∧, or ^ for browsers that don't support the character), OR (represented by ∨, or v) and NOT (represented by ¬, or ~) as well as the set theoretic operations union, intersection and complement. Today, Boolean algebras find many applications in electronic chip design. They were first defined by George Boole in the middle of the 19th century.
A Boolean algebra is a lattice (A, ^ , v) with the following four additional properties:
From these axioms, one can directly show that the smallest element 0 and the largest element 1 are unique, that every element has only one complement, that
and that deMorgan's laws
are valid. The dual version of the distributive law,
also holds true. In general, any law valid about Boolean algebras can be transformed into another valid, "dual" law by replacing 0 by 1 and ^ by v.
Like any lattice, a Boolean algebra can be seen as a partially ordered set by defining
(which is also equivalent to b = a v b).
The most important Boolean algebra has only two elements, 0 and 1, and is defined by the rules
v 0 1 ^ 0 1
---- ----
0 | 0 1 0 | 0 0
1 | 1 1 1 | 0 1
It has applications in logic, where 0 is interpreted as "false", 1 is "true", ^ is "and", v is "or", and ~ is "not". Expressions involving variables and the Boolean operations represent statement forms, and two such expressions can be shown to be equal using the above axioms if and only if the corresponding statement forms are logically equivalent.
The two-element Boolean algebra is also used for circuit design in electrical engineering; here 0 and 1 represent the two different states of digital circuits, typically high and low voltage. Circuits are described by expressions containing variables, and two such expressions are equal for all values of the variables if and only if the corresponding circuits have the same input - output behavior. Furthermore, every possible input - output behavior can be modeled by a suitable Boolean expression.
The two-element Boolean algebra is also important in the general theory of Boolean algebras, because an equation involving several variables is generally true in all Boolean algebras if and only if it is true in the two-element Boolean algebra (which can always be checked by a trivial brute force algorithm). This can for example be used to show that the following laws (Consensus theorems) are generally valid in all Boolean algebras:
The power set of any given set S forms a Boolean algebra with the two operations v = union and ^ = intersection. The smallest element 0 is the empty set and the largest element 1 is the set S itself.
For any natural number n, the set of all positive divisors of n forms a lattice if we write a <= b for a divides b. This lattice is a Boolean algebra if and only if n is squarefree. The smallest element 0 of this Boolean algebra is the natural number 1; the largest element 1 of this Boolean algebra is the natural number n.
Other examples of Boolean algebras arise from topological spaces: if X is a topological space, then the collection of all subsets of X which are both open and closed forms a Boolean algebra with the operations v = union and ^ = intersection.
If R is an arbitrary ring and we define the set of central idempotents by
then the set A becomes a Boolean algebra with the operations e v f = e + f + ef and e ^ f = ef.
A homomorphism between the Boolean algebras A and B is a function f : A -> B such that for all a, b in A:
It then follows that f(~a) = ~f(a) for all a in A as well. The class of all Boolean algebras, together with this notion of morphism, forms a category. An isomorphism from A to B is a homomorphism from A to B which is bijective. The inverse of an isomorphism is also an isomorphism, and we call the two Boolean algebras A and B isomorphic. From the standpoint of Boolean algebra theory, they cannot be distinguished; they only differ in the notation of their elements.
Every Boolean algebra (A, ^, v) gives rise to a ring (A, +, *) by defining a + b = (a ^ ~b) v (b ^ ~a) (this operation is called "symmetric difference" in the case of sets and XOR in the case of logic) and a * b = a ^ b. The zero element of this ring coincides with the 0 of the Boolean algebra; the multiplicative identity element of the ring is the 1 of the Boolean algebra. This ring has the property that a * a = a for all a in A; rings with this property are called Boolean rings.
Conversely, if a Boolean ring A is given, we can turn it into a Boolean algebra by defining x v y = x + y + xy and x ^ y = xy. Since these two operations are inverses of each other, we can say that every Boolean ring arises from a Boolean algebra, and vice versa. Furthermore, a map f : A -> B is a homomorphism of Boolean algebras if and only if it is a homomorphism of Boolean rings. The categories of Boolean rings and Boolean algebras are equivalent.
An ideal of the Boolean algebra A is a subset I such that for all x, y in I we have x v y in I and for all a in A we have a ^ x in I. This notion of ideal coincides with the notion of ring ideal in the Boolean ring A. An ideal I of A is called prime if I ≠ A and if a ^ b in I always implies a in I or b in I. An ideal I of A is called maximal if I ≠ A and if the only ideal containing I is A itself. These notions coincide with ring theoretic ones of prime ideal and maximal ideal in the Boolean ring A.
It can be shown that every finite Boolean algebra is isomorphic to the Boolean algebra of all subsets of a finite set; in particular, the number of elements of every finite Boolean algebra is a power of two.
The celebrated Stone representation theorem states that every Boolean algebra A is isomorphic to the Boolean algebra of all closed-open sets in some (compact totally disconnected T1) topological space. This space can be defined as the space of all maximal ideals in A, with the sets {M : M is a maximal ideal that doesn't contain a} for a in A as base of the topology.
Abstract algebra is the field of mathematics concerned with the study of algebraic structures such as groups, rings and fields. The term "abstract algebra" is used to distinguish the field from "elementary algebra" or "high school algebra" which teaches the correct rules for manipulating formulas and algebraic expressions involving real and complex numbers.
Historically, algebraic structures usually arose first in some other field of mathematics, were specified axiomatically, and were then studied in their own right in abstract algebra. Because of this, abstract algebra has numerous fruitful connections to all other branches of mathematics.
Examples of algebraic structures with a single binary operation are:
More complicated examples include:
In universal algebra, all those definitions and facts are collected that apply to all algebraic structures alike. All the above classes of objects, together with the proper notion of homomorphism, form categories, and category theory frequently provides the formalism for translating between and comparing different algebraic structures.
Cantor's diagonal argument is a logical argument devised by Georg Cantor to demonstrate that the real numbers are not countably infinite. (It is also called the diagonalization argument or the diagonal slash argument.) It does this by showing that the interval (0,1), that is, the real numbers larger than 0 and smaller than 1, is not countably infinite. It proceeds as follows:
r1 = 0 . 0 1 0 5 1 1 0 ...
r2 = 0 . 4 1 3 2 0 4 3 ...
r3 = 0 . 8 2 4 5 0 2 6 ...
r4 = 0 . 2 3 3 0 1 2 6 ...
r5 = 0 . 4 1 0 7 2 4 6 ...
r6 = 0 . 9 9 3 7 8 3 8 ...
r7 = 0 . 0 1 0 5 1 3 0 ...
...
x = 0 . 1 0 0 1 0 0 1 ...
Note: Strictly speaking, this argument only shows that the number of decimal expansions of real numbers between 0 and 1 is not countably infinite. But since there are expansions such as 0.01999... and 0.02000... that represent the same real number, this does not immediately imply that the corresponding set of real numbers is also not countably infinite. This can be remedied by disallowing the decimal expansions that end with an infinite series of 9's. In that case it can be shown that for every real number there is a unique corresponding decimal expansion. It is easy to see that the proof then still works because the number x contains only 1's and 0's in its decimal expansion.
The diagonal argument is an example of reductio ad absurdum because it proves a certain proposition (the interval (0,1) is not countably infinite) by showing that the assumption of its negation leads to a contradiction.
A generalized form of the diagonal argument was used by Cantor to show that for every set S the power set of S, i.e., the set of all subsets of S (here written as P(S)), is larger than S itself. This proof proceeds as follows:
Note the similarity between the construction of T and the set in Russell's paradox. Its result can be used to show that the notion of the set of all sets is an inconsistent notion in normal set theory; if S would be the set of all sets then P(S) would at the same time be bigger than S and a subset of S.
The diagonal argument shows that the set of real numbers is "bigger" than the set of integers. Therefore, we can ask if there is a set whose cardinality is "between" that of the integers and that of the reals. This question leads to the famous Continuum hypothesis. Similarly, the question of whether there exists a set whose cardinality is between s and P(s) for some s, leads to the Generalized continuum hypothesis.
Generally, an algorithm is a list of instructions for accomplishing some task, and the task can be anything that has a recognizable end-point (or result). Often some of the specific steps in the procedure are to be repeated until the task is done. Normally, there are different algorithms for the same task, some betther than others. A cooking recipe is one kind of algorithm. Some recipes for making potato salad, for example, have "peel the potato" before "boil the potato", while some have the "boil" step before the "peel" step, but they all call for those steps to be repeated for however many potatoes there are, and they all end when the potato salad is ready to eat.
Algorithms are essential to the way computers process information, because a computer program is essentially an algorithm that tells the computer what specific steps to perform, in what specific order, to perform a specific task, such as calculating the employees' paychecks or printing the students' report cards. In that context, an algorithm is a well-defined method or procedure for solving a problem, usually a problem in mathematics or otherwise relating to the manipulation of information. Some people restrict the definition of algorithm to procedures that eventually finish, while others also include procedures that run forever without stopping.
Algorithms are often implemented as computer programs but can also be implemented as electric circuits or even performed directly by humans.
As an example of an algorithm, here is a simple one. Imagine you have a random, unsorted list of numbers. Our goal is to find the highest number in this list. First upon thinking about the solution, you will realize that you must look at every number in the list. Upon further thinking, you will realize that you need tp look at each number only once. Taking this into account, here is a simple algorithm to accomplish this:
Most of the time, algorithms are written in computer code. Here is a more formal notation in a pseudocode that is similar to most programming languages:
Given: a list List of length Length
counter = 0
largest = List[counter]
while counter < Length:
if List[counter] > largest:
largest = List[counter]
counter = counter + 1
print largest
As it happens, most people that implement algorithms want to know how much of a particular resource (such as time or storage) a given algorithm requires. Methods have been developed for the analysis of algorithms to obtain such quantitative answers, and after reading that section, you will determine that this algorithm has a time requirement of O(n), where the big O notation was used and n stands for the length of the list.
The word algorithm is a corruption of the word algorism which came from the name of Abu Ja'far Mohammed ibn Musa al-Khwarizmi (ca. 780 - ca. 845). He was the author of the book Kitab al-jabr w'al-muqabala (Rules of Restoration and Reduction) which introduced algebra to people in the West. The word algebra itself originates from al-Jabr from the book title. The word algorism originally referred only to the rules of performing arithmetic using Arabic numerals but evolved into algorithm by the 18th century. The word has now evolved to include all definite procedures for solving problems or performing tasks.
The lack of mathematical rigor in the "well-defined procedure" definition of algorithm posed some difficulties for mathematicians and logicians of the 19th and early 20th centuries. This problem was largely solved with the description of the Turing machine, an abstract model of a computer described by Alan Turing, and the demonstration that every method yet found for describing "well-defined procedures" advanced by other mathematicians could be emulated on a Turing machine (a statement known as the Church-Turing thesis). Nowadays, a formal criterion for an algorithm is that it is a procedure implementable on a completely-specified Turing machine or one of the equivalent formalisms.
Algorithms come in different flavours. A greedy algorithm works by making a series of simple decisions that are never reconsidered. A divide-and-conquer algorithm recursively reduces an instance of a problem to one or more smaller instances of the same problem, until the instances are small enough. A dynamic programming algorithm works bottom-up by building progressively larger solutions to subproblems arising from the original problem, and then uses those solutions to obtain the final result. Many problems (such as playing chess) can be modeled as problems on graphs. A graph exploration algorithm specifies rules for moving around a graph and is useful for such problems. Probabilistic algorithms are those that make some choices randomly. Parallel algorithms take advantage of computer architectures where several processors can work on a problem at the same time. Genetic algorithms attempt to find solutions to problems by mimicking biological evolutionary processes, with a cycle of random mutations, reproduction and "survival of the fittest". In genetic programming, this approach is extended to evolve the algorithms themselves.
Related topics:
The branch of philosophy that deals with the nature of knowledge.
Epistemology is the study of the origin, nature, and limits of human knowledge. There are various ways people approach this task.
(1) Rationalists (see rationalism) believe there are innate ideas that are not found in experience. These ideas exist independently of any experience we may have. They may in some way derive from the structure of the human mind, or they may exist independently of the mind. If they exist independently, they may be understood by a human mind once it reaches a necessary degree of sophistication
(2) Empiricists (see: empiricism, scientific method, philosophy of science) deny that there exist any concepts that exist prior to experience. For them, all knowledge is a product of human learning, based on human perception. Perception, however, is a cause of concern since illusions, misunderstandings and hallucinations prove that perception does not always depict the world as it really is.
A problem for empiricists is the existence of mathematical theorems; their truths certainly do not depend on experience, and they can be known prior to experience. Empiricists rebut that all mathematical theorems are empty of cognitive content, as they only express the relationship of concepts to one another. Rationalists would hold that such relationships are indeed a form of cognitive content.
(3) The German philosopher Immanuel Kant is widely understood as having worked out a synthesis between these views. In Kant's view people certainly do have knowledge that is prior to experience, which is not devoid of cognitive significance. For example, the principle of causality. He held that there are a priori synthetic concepts.
People in all schools of thought agree that we have the capacity to think of questions that no possible appeal to experience could answer. For instance: Is there an end to time? Is there a God? Is the God of the philosophers the same as the Biblical God? Is there a reality beyond that which we can sense? Such questions are termed transcendental, as they seem to go beyond the limits of rational inquiry. In the 20th century logical positivists have declared such questions to be totally devoid of cognitive significance. Others disagree, and hold that only some metaphysical claims are devoid of cognitive significance howevers may not be.
There is no consensus as to which epistemology will be the most productive in allowing human beings to have the most accurate understanding of the world. While not widely appreciated, all people use an epistemology, even if unconsciously. Thinking beings cannot understand and analyze ideas without first having a system to accept and analyze information in the first place, which we all do. All people - even children - possess rudimentary and undeveloped epistemologies. However, only those who who study some philosophy and logic can begin to recognize how their own epistemologies work; only they can choose to change their epistemology, if they so wish.
Our analysis then will be dependent on the system we used to begin with. One might wonder: What do I have to do, to be sure that I do have the truth? How can I be sure that my beliefs are true? Is there some sort of guarantee available to me -- some sort of criterion I might use, in order to decide, as rationally and as carefully as I possibly could, that indeed what I believe is true?
Suppose you thought your belief had been arrived at rationally. You used logic, you based your belief on observation and experiment, you conscientiously answered objections, and so forth. So you conclude that your belief is rational. Well if so, then your belief has at least some claim to be true. Rationality is a indicator of truth: if your belief is rational, then it is at least probably true. At the very least, the rationality of a belief is reason to think the belief is true.
Now, there are a number of features of beliefs, such as rationality, justification, and probability, that are indicators of truth. So let's define a general term:
A feature of belief is an epistemic feature if it is at least some indication that the belief is true.
Many of our beliefs do have lots of positive epistemic features; many of our beliefs are quite rational, quite justified, very probably true, highly warranted, and so on. But most of us, at least in some moments, don't want to rest content with just being rational. We don't want to have a rational belief that is, unfortunately, false. Because that's possible, right? I can be very conscious, careful, and logical in forming a belief, and so be rational in holding the belief; but it still might be false. So rationality isn't our ultimate ambition that we have for our beliefs.
Our ultimate ambition for our beliefs is knowledge. Because if I do know something, then not only am I justified, or rational, in a belief; because I have knowledge, I have the truth. So naturally, when we are thinking about the epistemic features of our beliefs, the big question is this: When do I have knowledge? When can I say that I have it? As I'm sure you are aware, there are some people who claim that we can't have knowledge; such people are called skeptics. More on that, of course, later.
Now I can describe to you the field of epistemology, which is also called the theory of knowledge. Here is a definition:
Epistemology includes the study of (1) what the epistemic features of belief, such as justification and rationality, each are (e.g., what justified belief is); (2) the origin or sources of such features (and thus the sources of knowledge); (3) what knowledge is, i.e., what epistemic features would make a true belief knowledge; (4) whether it is possible to have knowledge.
So, first, epistemologists spend a great deal of time concerning themselves with various epistemic features of belief, such as justification and rationality. And they write long articles and books trying to say just when beliefs are justified, or rational.
A second, related concern is where such epistemic features ultimately come from. If I say, for example, that my belief that Paris is the capital of France is justified, I can ask: Where did the justification for my belief come from? Probably at some point some reliable source told me that Paris is the capital of France; and that was enough to make me justified in adopting the belief. OK, then one, but only one, source of justification would be testimony, which is just a fancy word for what other people tell me. Another source of justification would be sense-perception. So epistemology asks: What are the ultimate sources of justification, rationality, or other epistemic features of belief? And that allows to answer a further question: What are the ultimate sources of knowledge?
Which brings us to the third topic studied by epistemologists, namely, what knowledge is. The question here isn't what we can know, or even what we do know. The question is: What would knowledge be, if we had it? A belief has to pass some sort of muster if it's to count as knowledge. So what features would a belief have to have, in order to be an actual piece of knowledge -- not just something that pretends to be knowledge, but which is actually knowledge?
Then, fourth, there is one of the more difficult topics of philosophy -- trying to answer, or otherwise deal with, the challenge that we cannot have knowledge. A number of philosophers -- not too many, but some -- have said that we cannot have knowledge. A lot of philosophers have said that it's very difficult to obtain knowledge; but they don't deny that we have it, or that we can have it. Not so many philosophers, however, have gone so far as to say that we have no knowledge at all, or (to say something even stronger) that it is impossible to have knowledge.