Draft:Proposition (mathematical logic)

In modern logic, the term "proposition" is often used for sentences of a formal language. In this usage, propositions are formal syntactic objects which can be studied independently of the meaning they would receive from a semantics. Propositions are also called sentences, statements, statement forms, formulas, and well-formed formulas, though these terms are usually not synonymous within a single text.

A formal language begins with different types of symbols. These types can include variables, operators, function symbols, predicate (or relation) symbols, quantifiers, and propositional constants.(Grouping symbols such as delimiters are often added for convenience in using the language, but do not play a logical role.) Symbols are concatenated together according to recursive rules, in order to construct strings to which truth-values will be assigned. The rules specify how the operators, function and predicate symbols, and quantifiers are to be concatenated with other strings. A proposition is then a string with a specific form. The form that a proposition takes depends on the type of logic.

The type of logic called propositional, sentential, or statement logic includes only operators and propositional constants as symbols in its language. The propositions in this language are propositional constants, which are considered atomic propositions, and composite (or compound) propositions, which are composed by recursively applying operators to propositions. Application here is simply a short way of saying that the corresponding concatenation rule has been applied.

The types of logics called predicate, quantificational, or n-order logic include variables, operators, predicate and function symbols, and quantifiers as symbols in their languages. The propositions in these logics are more complex. First, one typically starts by defining a term as follows:

1. A variable, or

1. A function symbol applied to the number of terms required by the function symbol's arity.

For example, if is a binary function symbol and x, y, and z are variables, then x (y z) is a term, which might be written with the symbols in various orders. Once a term is defined, a proposition can then be defined as follows:

1. A predicate symbol applied to the number of terms required by its arity, or

1. An operator applied to the number of propositions required by its arity, or

1. A quantifier applied to a proposition.

For example, if = is a binary predicate symbol and ∀ is a quantifier, then ∀x,y,z [(x = y) → (x z = y z)] is a proposition. This more complex structure of propositions allows these logics to make finer distinctions between inferences, i.e., to have greater expressive power.