Index: > A B C D E F G H I J K L M N O P Q R S T U V W X Y Z

Home > First-order predicate calculus

First Prev [ 1 2 3 ] Next Last

First-order predicate calculus or first-order logic (FOL) is a theory in symbolic logic that permits the formulation of quantified statements such as "there is at least one X such that..." or "for any X, it is the case that...", where X is an element of a set called the domain of discourse. A first-order theory is a theory that can be axiomatised as an extension of first-order logic by adding a recursive set of first-order sentences as axioms.

First-order logic is distinguished from higher-order logic in that it does not allow statements such as "for every property, it is the case that..." 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. Its restriction to quantification over individuals makes it difficult to use for the purposes of topology, but it is the classical logical theory underlying mathematics. It is a stronger theory than sentential logic, but a weaker theory than arithmetic, set theory, or Second-order logic.

1 Defining first-order logic

Like any logical theory, the calculus of first-order logic consists of

a specification of how to construct syntactically correct statements (the well-formed formulas)
a set of axioms, each axiom being a well-formed formula itself
a set of inference rules which allow one to prove theorems from axioms or earlier proven theorems.

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.

2 Well-formed formulas of first-order logic

The well-formed formulas contain:

variables such as x, y, ... which are place holders for objects of the domain under consideration (these can be called "variable terms")
object constants such as 0, 1 or the empty set ø which stand for fixed individual objects in our domain (these can be called "constant terms"; it is also possible to use lower case letters such as a, b, c, ... , w to represent such constants, as long as they are different from the letters used for the variable terms)
predicate constants such as (lessThan), (isIn), (equals) which stand for fixed relations between or properties of our objects. These are also called first-order predicates to distinguish them from predicates that talk about predicates.
function constants such as , which stand for fixed functions taking objects as arguments and returning objects as values
logical connectives such as (and), (or), (conditional), (biconditional) (not), (thereExists or existential quantifier) and (forAll or universal quantifier). All of these except for the last two are also used in propositional logicA propositional calculus is a formal, deduction system, or proof theory for reasoning with propositional formulas as symbolic logic. It is also extensional. Compare, by contrast, predicate logic and modal logic, which also have their own calculi. A calcul.

Note that only , , and are needed for a complete set of logical connectives.

The object, predicate and function constants will typically depend on the particular domain we are talking about.

3 Examples of well-formed formulas

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 numberNatural number can mean either a positive integer ( 1, 2, 3, 4,. or a non-negative integer ( 0, 1, 2, 3, 4,. Natural numbers have two main purposes: they can be used for counting ("there are 3 apples on the table"), or they can be used for ordering ("thiss:

(i.e.: forAll x, thereExists y suchThat y isGreaterThan x )

For every number x there exists a bigger number y. That's true.

(i.e.: thereExists y suchThat forAll x, y isGreaterThan x )

There exists a number y which is bigger than every number x. That's not true.

(i.e.: forAll x, ( thereExists y suchThat 6*y=x) implies (thereExists y suchThat 3*y=x) )

If a number x is divisible by 6, then it is also divisible by 3. True.

(i.e.: thereExists x suchThat (not ThereExists y suchThat y < x ) )

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 theoremModel theory Godel's completeness theorem is a fundamental theorem in mathematical logic proved by Kurt Godel in 1929. It states, in its most familiar form, that in first-order predicate calculus every universally valid formula can be proved. The word "pr: 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. (See also Leon HenkinLeon Henkin is a logician, currently Emeritus Professor at Berkeley. He is principally known for the "Henkin Completeness Proof": his version of the proof of the semantic completeness of standard systems of first-order logic. Henkin's result was not novel)

Politics	Business	Finance

Topics: First-order Predicate Calculus Axioms I.e Forall Logic Set...

First NationalThe First National Exhibitors' Circuit was founded 1917 by the merger of 26 of the biggest First Run cinema chains in the United States of America, controlling more than 600 cinemas, more than 200 of them were First Run cinemas. The foundation, an initiat	First handFirst hand is where one experiences something personally, in effect, within reach of ones hands, also known as first person. Other points of view include second hand and third person. See also Hand Right Hand Qualia External links First Hand is also a phi	First Lady of the United StatesFirst Lady of the United States is the unofficial title of the hostess of the White House. The position is traditionally filled by the wife of the President of the United States, and the title is sometimes taken to apply only to the wife of a sitting pres
First Past the Post electoral systemThe first-past-the-post electoral system is a voting system for single-member districts, variously called first-past-the-post (FPTP or FPP winner-take-all plurality voting or relative majority . In political science, it is known as Single-Member District	First-order predicate calculusModel theory Logic First-order predicate calculus or first-order logic FOL is a theory in symbolic logic that permits the formulation of quantified statements such as "there is at least one X such that. or "for any X, it is the case that. where X is an el	First-class cricketFirst-class cricket is a term for cricket matches of at least three days length, either involving international teams, or the highest division of domestic competition. Conduct of a game of first-class cricket The game is conducted similarly to Test cricke
First Council of Nicaea	First aid	First-order predicate
First Epistle to the Corinthians	First Epistle to Timothy	First Epistle of Peter
First Epistle of John	First Vatican Council	First Council of the Lateran

Non User