Diagram (mathematical logic)

Concept in model theory

In model theory, a branch of mathematical logic, the diagram of a structure is a simple but powerful concept for proving useful properties of a theory, for example the amalgamation property and the joint embedding property, among others.

## Definition

[edit]

Let  L {\displaystyle {\mathcal {L}}} be a first-order language and  T {\displaystyle T} be a theory over  L . {\displaystyle {\mathcal {L}}.} For a model A {\displaystyle {\mathfrak {A}}} of  T {\displaystyle T} one expands  L {\displaystyle {\mathcal {L}}} to a new language

L A := L ∪ { c a : a ∈ A } {\displaystyle {\mathcal {L}}_{A}:={\mathcal {L}}\cup \\{c_{a}:a\in A\\}}

by adding a new constant symbol  c a {\displaystyle c_{a}} for each element  a {\displaystyle a} in  A , {\displaystyle A,} where  A {\displaystyle A} is a subset of the domain of  A . {\displaystyle {\mathfrak {A}}.} Now one may expand  A {\displaystyle {\mathfrak {A}}} to the model

A A := ( A , a ) a ∈ A . {\displaystyle {\mathfrak {A}}_{A}:=({\mathfrak {A}},a)_{a\in A}.}

The positive diagram of  A {\displaystyle {\mathfrak {A}}} , sometimes denoted  D + ( A ) {\displaystyle D^{+}({\mathfrak {A}})} , is the set of all those atomic sentences which hold in  A {\displaystyle {\mathfrak {A}}} while the negative diagram, denoted  D − ( A ) , {\displaystyle D^{-}({\mathfrak {A}}),} thereof is the set of all those atomic sentences which do not hold in  A {\displaystyle {\mathfrak {A}}} .

The diagram D ( A ) {\displaystyle D({\mathfrak {A}})} of  A {\displaystyle {\mathfrak {A}}} is the set of all atomic sentences and negations of atomic sentences of  L A {\displaystyle {\mathcal {L}}_{A}} that hold in  A A . {\displaystyle {\mathfrak {A}}_{A}.} [1][2] Symbolically,  D ( A ) = D + ( A ) ∪ ¬ D − ( A ) {\displaystyle D({\mathfrak {A}})=D^{+}({\mathfrak {A}})\cup \neg D^{-}({\mathfrak {A}})} .

## See also

[edit]

* Elementary diagram

## References

[edit]

1. ^ Hodges, Wilfrid (1993). Model theory. Cambridge University Press. ISBN 9780521304429.
2. ^ Chang, C. C.; Keisler, H. Jerome (2012). Model Theory (Third ed.). Dover Publications. pp. 672 pages.

* v
* t
* e

Mathematical logic

General|

* Axiom
* list
* Cardinality
* First-order logic
* Formal proof
* Formal semantics
* Foundations of mathematics
* Information theory
* Lemma
* Logical consequence
* Model
* Theorem
* Theory
* Type theory

Theorems (list)
and paradoxes|

* Gödel's completeness and incompleteness theorems
* Tarski's undefinability
* Banach–Tarski paradox
* Cantor's theorem, paradox and diagonal argument
* Compactness
* Halting problem
* Lindström's
* Löwenheim–Skolem
* Russell's paradox

Logics|

| Traditional|

* Classical logic
* Logical truth
* Tautology
* Proposition
* Inference
* Logical equivalence
* Consistency
* Equiconsistency
* Argument
* Soundness
* Validity
* Syllogism
* Square of opposition
* Venn diagram

|

Propositional|

* Boolean algebra
* Boolean functions
* Logical connectives
* Propositional calculus
* Propositional formula
* Truth tables
* Many-valued logic
* 3
* finite
* ∞

Predicate|

* First-order
* list
* Second-order
* Monadic
* Higher-order
* Fixed-point
* Free
* Quantifiers
* Predicate
* Monadic predicate calculus

Set theory|

* Set
* hereditary
* Class
* (Ur-)Element
* Ordinal number
* Extensionality
* Forcing
* Relation
* equivalence
* partition
* Set operations:
* intersection
* union
* complement
* Cartesian product
* power set
* identities

Types of sets|

* Countable
* Uncountable
* Empty
* Inhabited
* Singleton
* Finite
* Infinite
* Transitive
* Ultrafilter
* Recursive
* Fuzzy
* Universal
* Universe
* constructible
* Grothendieck
* Von Neumann

Maps and cardinality|

* Function/Map
* domain
* codomain
* image
* In/Sur/Bi-jection
* Schröder–Bernstein theorem
* Isomorphism
* Gödel numbering
* Enumeration
* Large cardinal
* inaccessible
* Aleph number
* Operation
* binary

Set theories|

* Zermelo–Fraenkel
* axiom of choice
* continuum hypothesis
* General
* Kripke–Platek
* Morse–Kelley
* Naive
* New Foundations
* Tarski–Grothendieck
* Von Neumann–Bernays–Gödel
* Ackermann
* Constructive

Formal systems (list),
language and syntax|

* Alphabet
* Arity
* Automata
* Axiom schema
* Expression
* ground
* Extension
* by definition
* conservative
* Relation
* Formation rule
* Grammar
* Formula
* atomic
* closed
* ground
* open
* Free/bound variable
* Language
* Metalanguage
* Logical connective
* ¬
* ∨
* ∧
* →
* ↔
* =
* Predicate
* functional
* variable
* propositional variable
* Proof
* Quantifier
* ∃
* !
* ∀
* rank
* Sentence
* atomic
* spectrum
* Signature
* String
* Substitution
* Symbol
* function
* logical/constant
* non-logical
* variable
* Term
* Theory
* list

Example axiomatic
systems (list)|

* of arithmetic:
* Peano
* second-order
* elementary function
* primitive recursive
* Robinson
* Skolem
* of the real numbers
* Tarski's axiomatization
* of Boolean algebras
* canonical
* minimal axioms
* of geometry:
* Euclidean:
* Elements
* Hilbert's
* Tarski's
* non-Euclidean

* Principia Mathematica

Proof theory|

* Formal proof
* Natural deduction
* Logical consequence
* Rule of inference
* Sequent calculus
* Theorem
* Systems
* axiomatic
* deductive
* Hilbert
* list
* Complete theory
* Independence (from ZFC)
* Proof of impossibility
* Ordinal analysis
* Reverse mathematics
* Self-verifying theories

Model theory|

* Interpretation
* function
* of models
* Model
* equivalence
* finite
* saturated
* spectrum
* submodel
* Non-standard model
* of arithmetic
* Diagram
* elementary
* Categorical theory
* Model complete theory
* Satisfiability
* Semantics of logic
* Strength
* Theories of truth
* semantic
* Tarski's
* Kripke's
* T-schema
* Transfer principle
* Truth predicate
* Truth value
* Type
* Ultraproduct
* Validity

Computability theory|

* Church encoding
* Church–Turing thesis
* Computably enumerable
* Computable function
* Computable set
* Decision problem
* decidable
* undecidable
* P
* NP
* P versus NP problem
* Kolmogorov complexity
* Lambda calculus
* Primitive recursive function
* Recursion
* Recursive set
* Turing machine
* Type theory

Related|

* Abstract logic
* Algebraic logic
* Automated theorem proving
* Category theory
* Concrete/Abstract category
* Category of sets
* History of logic
* History of mathematical logic
* timeline
* Logicism
* Mathematical object
* Philosophy of mathematics
* Supertask

Mathematics portal

This mathematical logic-related article is a stub. You can help Wikipedia by expanding it.

|

* v
* t
* e

*[v]: View this template
*[t]: Discuss this template
*[e]: Edit this template