PlanetMath (more info)
 Math for the people, by the people.
Encyclopedia | Requests | Forums | Docs | Wiki | Random | RSS  
Login
create new user
name:
pass:
forget your password?
Main Menu
sections
Encyclopædia
Papers
Books
Expositions

meta
Requests (198)
Orphanage
Unclass'd
Unproven (490)
Corrections (7)
Classification

talkback
Polls
Forums
Feedback
Bug Reports

downloads
Snapshots
PM Book

information
News
Docs
Wiki
ChangeLog
TODO List
Legalese
About
Owner confidence rating: Very high Entry average rating: No information on entry rating
first-order theory (Definition)

In what follows, references to sentences and sets of sentences are all relative to some fixed first-order language $ L$.

Definition. A theory $ T$ is a deductively closed set of sentences in $ L$; that is, a set $ T$ such that for each sentence $ \varphi$, $ T \vdash \varphi$ only if $ \varphi \in T$.

Remark. Some authors do not require that a theory be deductively closed. Therefore, a theory is simply a set of sentences. This is not a cause for alarm, since every theory $ T$ under this definition can be “extended” to a deductively closed theory $ T^{\vdash}:=\lbrace \varphi \in L\mid T\vdash \varphi\rbrace$. Furthermore, $ T^{\vdash}$ is unique (it is the smallest deductively closed theory including $ T$), and any structure $ M$ is a model of $ T$ iff it is a model of $ T^{\vdash}$.

Definition. A theory $ T$ is consistent if and only if for some sentence $ \varphi$, $ T \not \vdash \varphi$. Otherwise, $ T$ is inconsistent. A sentence $ \varphi$ is consistent with $ T$ if and only if the theory $ T \cup \lbrace \varphi \rbrace$ is consistent.

Definition. A theory $ T$ is complete if and only if $ T$ is consistent and for each sentence $ \varphi$, either $ \varphi \in T$ or $ \neg \varphi \in T$.

Lemma. A consistent theory $ T$ is complete if and only if $ T$ is maximally consistent. That is, $ T$ is complete if and only if for each sentence $ \varphi$, $ \varphi \not \in T$ only if $ T \cup \lbrace \varphi \rbrace$ is inconsistent.

Theorem. (Tarski) Every consistent theory $ T$ is included in a complete theory.

Proof : Use Zorn's lemma on the set of consistent theories that include $ T$.

Remark. A theory $ T$ is axiomatizable if and only if $ T$ includes a decidable subset $ \Delta$ such that $ \Delta \vdash T$ (every sentence of $ T$ is a logical consequence of $ \Delta$), and finitely axiomatizable if $ \Delta$ can be made finite. Every complete axiomatizable theory $ T$ is decidable; that is, there is an algorithm that given a sentence $ \varphi$ as input yields 0 if $ \varphi \in T$, and $ 1$ otherwise.



Anyone with an account can edit this entry. Please help improve it!

"first-order theory" is owned by CWoo. [ full author list (3) | owner history (2) ]
(view preamble)

View style:

Other names:  first order theory
Also defines:  theory, complete theory, axiomatizable theory, deductively closed, finitely axiomatizable theory
Log in to rate this entry.
(view current ratings)

Cross-references: algorithm, finite, finitely axiomatizable, consequence, subset, Zorn's lemma, complete, inconsistent, consistent, iff, structure, first-order language, fixed, sentences
There are 254 references to this entry.

This is version 15 of first-order theory, born on 2002-06-03, modified 2007-10-25.
Object id is 3012, canonical name is FirstOrderTheories.
Accessed 19150 times total.

Classification:
AMS MSC: 03B10 (Mathematical logic and foundations :: General logic :: Classical first-order logic)
 03C07 (Mathematical logic and foundations :: Model theory :: Basic properties of first-order languages and structures)
Pending Errata and Addenda
None.
[ View all 1 ]
Discussion
Style: Expand: Order:
forum policy

No messages.

Interact
post | correct | update request | add derivation | add example | add (any)