Syntax (logic)

Encyclopedia

In logic

,

s or formal system

s without regard to any interpretation

or meaning

given to them. Syntax is concerned with the rules used for constructing, or transforming the symbols and words of a language, as contrasted with the semantics of a language which is concerned with its meaning.

The symbols

, formulas

, system

s, theorem

s, proofs

, and interpretations

expressed in formal languages are syntactic entities whose properties may be studied without regard to any meaning they may be given, and, in fact, need not be given any.

Syntax is usually associated with the rules (or grammar) governing the composition of texts in a formal language that constitute the well-formed formula

s of a formal system.

In computer science

, the term syntax

refers to the rules governing the composition of meaningful texts in a formal language, such as a programming language

, that is, those texts for which it makes sense to define the semantics

or meaning, or otherwise provide an interpretation.

, abstraction

or concept

, tokens

of which may be marks or a configuration of marks which form a particular pattern. Symbols of a formal language need not be symbols of anything. For instance there are logical constants which do not refer to any idea, but rather serve as a form of punctuation in the language (e.g. parentheses). A symbol or string of symbols may comprise a well-formed formula if the formulation is consistent with the formation rules of the language. Symbols of a formal language must be capable of being specified without any reference to any interpretation of them.

of symbol

s which are its words (usually called its well-formed formula

s). Which strings of symbols are words is determined by fiat by the creator of the language, usually by specifying a set of formation rule

s. Such a language can be defined without reference

to any meaning

s of any of its expressions; it can exist before any interpretation

is assigned to it – that is, before it has any meaning.

of symbol

s are the well-formed formulaIn mathematical logic, a well-formed formula, shortly wff, often simply formula, is a word which is part of a formal language...

s of a formal language. It is synonymous with the set of strings

over the alphabet

of the formal language which constitute well formed formulas. However, it does not describe their semantics

(i.e. what they mean).

expressing something true

or false

. A proposition is identified ontologically

as an idea

, concept

or abstraction

whose token instances

are patterns of symbolsFor other uses see Symbol In logic, symbols build literal utility to illustrate ideas. A symbol is an abstraction, tokens of which may be marks or a configuration of marks which form a particular pattern...

, marks, sounds, or stringsIn formal languages, which are used in mathematical logic and theoretical computer science, a string is a finite sequence of symbols that are chosen from a set or alphabet....

of words. Propositions are considered to be syntactic entities and also truthbearer

s.

s in a formal language

.

s, or have both. A formal system is used to derive

one expression from one or more other expressions. Formal systems, like other syntactic entities may be defined without any interpretationAn interpretation is an assignment of meaning to the symbols of a formal language. Many formal languages used in mathematics, logic, and theoretical computer science are defined in solely syntactic terms, and as such do not have any meaning until they are given some interpretation...

given to it (as being, for instance, a system of arithmetic).

in formal system

of A from the set Г.

Syntactic consequence does not depend on any interpretationAn interpretation is an assignment of meaning to the symbols of a formal language. Many formal languages used in mathematics, logic, and theoretical computer science are defined in solely syntactic terms, and as such do not have any meaning until they are given some interpretation...

of the formal system.

. Truth-functional propositional logic and first-order predicate logic

are semantically complete, but not syntactically complete (for example the propositional logic statement consisting of a single variable "a" is not a theorem, and neither is its negation, but these are not tautologies

). Gödel's incompleteness theorem shows that no recursive system that is sufficiently powerful, such as the Peano axioms

, can be both consistent and complete.

, which may itself be a formal language, and as such itself is a syntactic entity.

Logic

In philosophy, Logic is the formal systematic study of the principles of valid inference and correct reasoning. Logic is used in most intellectual activities, but is studied primarily in the disciplines of philosophy, mathematics, semantics, and computer science...

,

**syntax**is anything having to do with formal languageFormal language

A formal language is a set of words—that is, finite strings of letters, symbols, or tokens that are defined in the language. The set from which these letters are taken is the alphabet over which the language is defined. A formal language is often defined by means of a formal grammar...

s or formal system

Formal system

In formal logic, a formal system consists of a formal language and a set of inference rules, used to derive an expression from one or more other premises that are antecedently supposed or derived . The axioms and rules may be called a deductive apparatus...

s without regard to any interpretation

Interpretation (logic)

An interpretation is an assignment of meaning to the symbols of a formal language. Many formal languages used in mathematics, logic, and theoretical computer science are defined in solely syntactic terms, and as such do not have any meaning until they are given some interpretation...

or meaning

Meaning (linguistics)

In linguistics, meaning is what is expressed by the writer or speaker, and what is conveyed to the reader or listener, provided that they talk about the same thing . In other words if the object and the name of the object and the concepts in their head are the same...

given to them. Syntax is concerned with the rules used for constructing, or transforming the symbols and words of a language, as contrasted with the semantics of a language which is concerned with its meaning.

The symbols

Symbol (formal)

For other uses see Symbol In logic, symbols build literal utility to illustrate ideas. A symbol is an abstraction, tokens of which may be marks or a configuration of marks which form a particular pattern...

, formulas

Well-formed formula

In mathematical logic, a well-formed formula, shortly wff, often simply formula, is a word which is part of a formal language...

, system

Formal system

In formal logic, a formal system consists of a formal language and a set of inference rules, used to derive an expression from one or more other premises that are antecedently supposed or derived . The axioms and rules may be called a deductive apparatus...

s, theorem

Theorem

In mathematics, a theorem is a statement that has been proven on the basis of previously established statements, such as other theorems, and previously accepted statements, such as axioms...

s, proofs

Formal proof

A formal proof or derivation is a finite sequence of sentences each of which is an axiom or follows from the preceding sentences in the sequence by a rule of inference. The last sentence in the sequence is a theorem of a formal system...

, and interpretations

Interpretation (logic)

An interpretation is an assignment of meaning to the symbols of a formal language. Many formal languages used in mathematics, logic, and theoretical computer science are defined in solely syntactic terms, and as such do not have any meaning until they are given some interpretation...

expressed in formal languages are syntactic entities whose properties may be studied without regard to any meaning they may be given, and, in fact, need not be given any.

Syntax is usually associated with the rules (or grammar) governing the composition of texts in a formal language that constitute the well-formed formula

Well-formed formula

In mathematical logic, a well-formed formula, shortly wff, often simply formula, is a word which is part of a formal language...

s of a formal system.

In computer science

Computer science

Computer science or computing science is the study of the theoretical foundations of information and computation and of practical techniques for their implementation and application in computer systems...

, the term syntax

Syntax of programming languages

In computer science, the syntax of a programming language is the set of rules that define the combinations of symbols that are considered to be correctly structured programs in that language. The syntax of a language defines its surface form...

refers to the rules governing the composition of meaningful texts in a formal language, such as a programming language

Programming language

A programming language is an artificial language designed to communicate instructions to a machine, particularly a computer. Programming languages can be used to create programs that control the behavior of a machine and/or to express algorithms precisely....

, that is, those texts for which it makes sense to define the semantics

Semantics

Semantics is the study of meaning. It focuses on the relation between signifiers, such as words, phrases, signs and symbols, and what they stand for, their denotata....

or meaning, or otherwise provide an interpretation.

### Symbols

A symbol is an ideaIdea

In the most narrow sense, an idea is just whatever is before the mind when one thinks. Very often, ideas are construed as representational images; i.e. images of some object. In other contexts, ideas are taken to be concepts, although abstract concepts do not necessarily appear as images...

, abstraction

Abstraction

Abstraction is a process by which higher concepts are derived from the usage and classification of literal concepts, first principles, or other methods....

or concept

Concept

The word concept is used in ordinary language as well as in almost all academic disciplines. Particularly in philosophy, psychology and cognitive sciences the term is much used and much discussed. WordNet defines concept: "conception, construct ". However, the meaning of the term concept is much...

, tokens

Type-token distinction

In disciplines such as philosophy and knowledge representation, the type-token distinction is a distinction that separates an abstract concept from the objects which are particular instances of the concept...

of which may be marks or a configuration of marks which form a particular pattern. Symbols of a formal language need not be symbols of anything. For instance there are logical constants which do not refer to any idea, but rather serve as a form of punctuation in the language (e.g. parentheses). A symbol or string of symbols may comprise a well-formed formula if the formulation is consistent with the formation rules of the language. Symbols of a formal language must be capable of being specified without any reference to any interpretation of them.

### Formal language

A*formal language*is a syntactic entity which consists of a set of finite stringsString (computer science)

In formal languages, which are used in mathematical logic and theoretical computer science, a string is a finite sequence of symbols that are chosen from a set or alphabet....

of symbol

Symbol (formal)

For other uses see Symbol In logic, symbols build literal utility to illustrate ideas. A symbol is an abstraction, tokens of which may be marks or a configuration of marks which form a particular pattern...

s which are its words (usually called its well-formed formula

Well-formed formula

In mathematical logic, a well-formed formula, shortly wff, often simply formula, is a word which is part of a formal language...

s). Which strings of symbols are words is determined by fiat by the creator of the language, usually by specifying a set of formation rule

Formation rule

In mathematical logic, formation rules are rules for describing which strings of symbols formed from the alphabet of a formal language are syntactically valid within the language. These rules only address the location and manipulation of the strings of the language. It does not describe anything...

s. Such a language can be defined without reference

Reference

Reference is derived from Middle English referren, from Middle French rèférer, from Latin referre, "to carry back", formed from the prefix re- and ferre, "to bear"...

to any meaning

Meaning (linguistics)

In linguistics, meaning is what is expressed by the writer or speaker, and what is conveyed to the reader or listener, provided that they talk about the same thing . In other words if the object and the name of the object and the concepts in their head are the same...

s of any of its expressions; it can exist before any interpretation

Interpretation (logic)

An interpretation is an assignment of meaning to the symbols of a formal language. Many formal languages used in mathematics, logic, and theoretical computer science are defined in solely syntactic terms, and as such do not have any meaning until they are given some interpretation...

is assigned to it – that is, before it has any meaning.

### Formation rules

*Formation rules*are a precise description of which stringsString (computer science)

In formal languages, which are used in mathematical logic and theoretical computer science, a string is a finite sequence of symbols that are chosen from a set or alphabet....

of symbol

Symbol (formal)

For other uses see Symbol In logic, symbols build literal utility to illustrate ideas. A symbol is an abstraction, tokens of which may be marks or a configuration of marks which form a particular pattern...

s are the well-formed formula

Well-formed formula

s of a formal language. It is synonymous with the set of strings

String (computer science)

In formal languages, which are used in mathematical logic and theoretical computer science, a string is a finite sequence of symbols that are chosen from a set or alphabet....

over the alphabet

Alphabet

An alphabet is a standard set of letters—basic written symbols or graphemes—each of which represents a phoneme in a spoken language, either as it exists now or as it was in the past. There are other systems, such as logographies, in which each character represents a word, morpheme, or semantic...

of the formal language which constitute well formed formulas. However, it does not describe their semantics

Semantics

Semantics is the study of meaning. It focuses on the relation between signifiers, such as words, phrases, signs and symbols, and what they stand for, their denotata....

(i.e. what they mean).

### Propositions

A**proposition**is a sentenceSentence (linguistics)

In the field of linguistics, a sentence is an expression in natural language, and often defined to indicate a grammatical unit consisting of one or more words that generally bear minimal syntactic relation to the words that precede or follow it...

expressing something true

Truth

Truth has a variety of meanings, such as the state of being in accord with fact or reality. It can also mean having fidelity to an original or to a standard or ideal. In a common usage, it also means constancy or sincerity in action or character...

or false

Falsity

Falsity or falsehood is a perversion of truth originating in the deceitfulness of one party, and culminating in the damage of another party...

. A proposition is identified ontologically

Ontology

Ontology is the philosophical study of the nature of being, existence or reality as such, as well as the basic categories of being and their relations...

as an idea

Idea

In the most narrow sense, an idea is just whatever is before the mind when one thinks. Very often, ideas are construed as representational images; i.e. images of some object. In other contexts, ideas are taken to be concepts, although abstract concepts do not necessarily appear as images...

, concept

Concept

The word concept is used in ordinary language as well as in almost all academic disciplines. Particularly in philosophy, psychology and cognitive sciences the term is much used and much discussed. WordNet defines concept: "conception, construct ". However, the meaning of the term concept is much...

or abstraction

Abstraction

Abstraction is a process by which higher concepts are derived from the usage and classification of literal concepts, first principles, or other methods....

whose token instances

Type-token distinction

In disciplines such as philosophy and knowledge representation, the type-token distinction is a distinction that separates an abstract concept from the objects which are particular instances of the concept...

are patterns of symbols

Symbol (formal)

, marks, sounds, or strings

String (computer science)

of words. Propositions are considered to be syntactic entities and also truthbearer

Truthbearer

Truth-bearer is a term used to designate entities that are either true or false and nothing else. The thesis that some things are true while others are false raises the question of the nature of these things. Since there is divergence of opinion on the matter, the term truthbearer is used to be...

s.

### Formal theories

A**formal theory**is a set of sentenceSentence (mathematical logic)

In mathematical logic, a sentence of a predicate logic is a boolean-valued well formed formula with no free variables. A sentence can be viewed as expressing a proposition, something that may be true or false...

s in a formal language

Formal language

A formal language is a set of words—that is, finite strings of letters, symbols, or tokens that are defined in the language. The set from which these letters are taken is the alphabet over which the language is defined. A formal language is often defined by means of a formal grammar...

.

### Formal systems

A*formal system*(also called a*logical calculus*, or a*logical system*) consists of a formal language together with a deductive apparatus (also called a*deductive system*). The deductive apparatus may consist of a set of transformation rules (also called*inference rules*) or a set of axiomAxiom

In traditional logic, an axiom or postulate is a proposition that is not proven or demonstrated but considered either to be self-evident or to define and delimit the realm of analysis. In other words, an axiom is a logical statement that is assumed to be true...

s, or have both. A formal system is used to derive

Proof theory

Proof theory is a branch of mathematical logic that represents proofs as formal mathematical objects, facilitating their analysis by mathematical techniques. Proofs are typically presented as inductively-defined data structures such as plain lists, boxed lists, or trees, which are constructed...

one expression from one or more other expressions. Formal systems, like other syntactic entities may be defined without any interpretation

Interpretation (logic)

given to it (as being, for instance, a system of arithmetic).

#### Syntactic consequence within a formal system

A formula A is a**syntactic consequence**within some formal system of a set Г of formulas if there is a formal proofDerivation

Derivation may refer to:* Derivation , a function on an algebra which generalizes certain features of the derivative operator* Derivation * Derivation in differential algebra, a unary function satisfying the Leibniz product law...

in formal system

Formal system

In formal logic, a formal system consists of a formal language and a set of inference rules, used to derive an expression from one or more other premises that are antecedently supposed or derived . The axioms and rules may be called a deductive apparatus...

of A from the set Г.

Syntactic consequence does not depend on any interpretation

Interpretation (logic)

of the formal system.

#### Syntactic completeness of a formal system

A formal system is*syntactically complete*(also*deductively complete*,*maximally complete*,*negation complete*or simply*complete*) iff for each formula A of the language of the system either A or ¬A is a theorem of . In another sense, a formal system is syntactically complete iff no unprovable axiom can be added to it as an axiom without introducing an inconsistencyConsistency

Consistency can refer to:* Consistency , the psychological need to be consistent with prior acts and statements* "Consistency", an 1887 speech by Mark Twain...

. Truth-functional propositional logic and first-order predicate logic

Predicate logic

In mathematical logic, predicate logic is the generic term for symbolic formal systems like first-order logic, second-order logic, many-sorted logic or infinitary logic. This formal system is distinguished from other systems in that its formulae contain variables which can be quantified...

are semantically complete, but not syntactically complete (for example the propositional logic statement consisting of a single variable "a" is not a theorem, and neither is its negation, but these are not tautologies

Tautology (logic)

In logic, a tautology is a formula which is true in every possible interpretation. Philosopher Ludwig Wittgenstein first applied the term to redundancies of propositional logic in 1921; it had been used earlier to refer to rhetorical tautologies, and continues to be used in that alternate sense...

). Gödel's incompleteness theorem shows that no recursive system that is sufficiently powerful, such as the Peano axioms

Peano axioms

In mathematical logic, the Peano axioms, also known as the Dedekind–Peano axioms or the Peano postulates, are a set of axioms for the natural numbers presented by the 19th century Italian mathematician Giuseppe Peano...

, can be both consistent and complete.

### Interpretations

An*interpretation*of a formal system is the assignment of meanings to the symbols, and truth values to the sentences of a formal system. The study of interpretations is called formal semantics.*Giving an interpretation*is synonymous with*constructing a model*

. An interpretation is expressed in a metalanguageStructure (mathematical logic)

In universal algebra and in model theory, a structure consists of a set along with a collection of finitary operations and relations which are defined on it....

Metalanguage

Broadly, any metalanguage is language or symbols used when language itself is being discussed or examined. In logic and linguistics, a metalanguage is a language used to make statements about statements in another language...

, which may itself be a formal language, and as such itself is a syntactic entity.

## See also

- Symbol (formal)Symbol (formal)
- Formation ruleFormation ruleIn mathematical logic, formation rules are rules for describing which strings of symbols formed from the alphabet of a formal language are syntactically valid within the language. These rules only address the location and manipulation of the strings of the language. It does not describe anything...
- Formal grammarFormal grammarA formal grammar is a set of formation rules for strings in a formal language. The rules describe how to form strings from the language's alphabet that are valid according to the language's syntax...
- Syntax (linguistics)SyntaxIn linguistics, syntax is the study of the principles and rules for constructing phrases and sentences in natural languages....
- Syntax (programming languages)
- Mathematical logicMathematical logicMathematical logic is a subfield of mathematics with close connections to foundations of mathematics, theoretical computer science and philosophical logic. The field includes both the mathematical study of logic and the applications of formal logic to other areas of mathematics...
- Well-formed formulaWell-formed formula