User:Hans Adler/Model theory and universal algebra

DRAFT ARTICLE ON BOOLEAN LOGIC

Boolean logic is the algebra of the two numbers 1 and 0, interpreted as the truth values TRUE and FALSE. It is a variant of elementary algebra. Instead of addition, multiplication and ordinary negation, Boolean logic has conjunction (AND), disjunction (OR) and logical negation (NOT). George Boole described the laws of Boolean logic as "universal laws of thought which are the basis of all reasoning". Nowadays Boolean logic is the basis of digital electronics, and hence of modern computers. On a higher level it is represented in most computer programming languages, typically by Boolean variables. Boolean logic is also essentially the same as propositional logic and corresponds to the most basic operations of set operations intersection, union and complement.

Basic operations

operation	concrete values		alternative notations
AND:	0 • 0 = 0	1 • 0 = 0	a × b	ab
a • b	0 • 1 = 0	1 • 1 = 1	a & b	a ∧ b
OR:	0 + 0 = 0	1 + 0 = 1	a ∨ b
a + b	0 + 1 = 1	1 + 1 = 1
NOT:	0 = 1	1 = 0	¬a	~a
a			a'	1 – a

Given two variables a and b that hold numbers 0 or 1, the conjunction a AND b is often written like a product a × b = a • b = ab, and the disjunction a OR b like a sum a + b. This notation goes back to George Boole. In Boolean logic, 1 + 1 = 1; otherwise the two operations give exactly the same results as normal addition and multiplication. In practice this is unlikely to lead to confusion since 2 does not represent a truth value. However, disjunction and addition must be clearly distinguished when it is not clear whether a formula should be read in ordinary or Boolean algebra.

Boole wrote negation in the form 1 – a, but this is no longer customary. The standard notation in digital electronics is a. When negating an expression that already involves negations, one can avoid typesetting complications by using the alternative notation ¬x = x. For example when negating the expression a + b, one may write ¬(a + b) or ¬(¬a + ¬b) or ¬a + ¬b instead of (ā + ƃ).

Properties of conjunction and disjunction

The fact that conjunction and disjunction are written like multiplication and addition suggests that they have similar properties. The laws listed in the following table show that this is true for both operations individually, except that both do not have an inverse operation.

operation	notation	commutative	associative	identity element	inverse operation
conjunction	a × b or a • b or ab	a • b = b • a	(a • b) • c = a • (b • c)	1, which preserves numbers: a • 1 = a	none
disjunction	a + b	a + b = b + a	(a + b) + c = a + (b + c)	0, which preserves numbers: a + 0 = a	none

Distributive laws

• distributes over +	+ distributes over •
(a + b) • c = (a • c) + (b • c)	(a • b) + c = (a + c) • (b + c)

Moreover, it is well known that in ordinary algebra multiplication distributes over addition, i.e. the distributive law (a + b) • c = (a • c) + (b • c) holds. While this is also true in Boolean logic, i.e. conjunction distributes over disjunction, the dual law is also true, i.e. disjunction distributes over conjunction. Another law whose dual is true in Boolean logic but not in ordinary algebra is 0a = 0: The equation 1 + a = 1 always holds in Boolean logic, since disjunction with TRUE always results in TRUE.

Order of operations

When conjunction is notated multiplicatively, then in the absence of parentheses it binds stronger than disjunction. For example ab + c = a • b + c = (a • b) + c, not a • (b + c). When other notations are used for conjunction and disjunction, there is often no specified order of operations, so that parentheses are always required in mixed expressions.

When negation is indicated by a horizontal line, then as for a square root symbol the extent of the line defines its scope, and so there is no need for precedence rules. When it is notated as ¬, then it binds even stronger than multiplication. In this respect logical negation is more similar to an exponent such as in x² than to arithmetic negation. This is also true for other notations such as ~: they all bind stronger than AND and OR.

References

• Burris, Stanley (2000), The Laws of Boole's Thought (PDF).
• Boole, George (1948) [1847], The Mathematical Analysis of Logic, being an essay towards a calculus of deductive reasoning, New York: Philosophical Library.
• Boole, George (2005) [1854], [[The Laws of Thought|An Investigation of the Laws of Thought]], Project Gutenberg {{citation}}: URL–wikilink conflict (help).
• Hailperin, Theodore (1986), Boole's Logic and Probability: A critical exposition from the standpoint of contemporary algebra, logic and probability theory (2nd ed.), Amsterdam: North-Holland.
• Levitz; Levitz; Logic and Boolean Algebra.
• Maini, Anil Kumar (2007), "Boolean Algebra and Simplification Techniques", Digital electronics: principles, devices and applications, New York: John Wiley & Sons, pp. 189–231, ISBN 978-0-470-03214-5
• Mendelson, Elliott (1970), Boolean Algebra and Switching Circuits, Schaum's Outline Series in Mathematics, McGraw–Hill, ISBN 978-0-07-041460-0

DRAFT ARTICLE ON MODEL THEORY

Note: The greater part of the draft is now part of the article model theory.

The role of model theory

In a similar way as proof theory, model theory is situated in an area of interdisciplinarity between mathematics, philosophy, and computer science. [Insert picture here: Venn diagram depicting maths, logic and computer science, with model theory in the intersection.] The most important professional organization in the field of model theory is the Association for Symbolic Logic.

...

Finite model theory

...

[Picture showing how a relational database is a relational structure]

[Example of a non-trivial Datalog query and its translation into a normal first-order formula?]

ω-categoricity

• reducts

• back-and-forth [picture?]
• Fraïssé's theorem
• ω-categoricity

Classification theory

• elementary embeddings
• complete theories
• Morley's theorem
• indiscernibles
• strong minimality
• prime models
• Baldwin-Lachlan theorem
• stability and the spectrum of a theory
• simplicity
• independence property

[picture of stability, simplicity, NIP, superstability, strongly dependent, strong minimality, o-minimality]

Geometric stability theory

• forking
• heirs and coheirs
• imaginaries
• regular types
• Zilber's conjecture
• Hrushovski's amalgamation construction
• group configuration [picture!]
• modularity and triviality
• Robinson theories / compact abstract theories
• thorn-forking

Topological model theory

[Lots of pictures possible]

• o-minimality
• weak o-minimality
• C-minimality and similar generalizations
• classical results
• topological structures
• cell decomposition
• o-minimal homology

Other areas of model theory

• Computable model theory
• Inner model theory
• Institutional model theory
• Model checking
• Non-standard analysis
• Kripke semantics
• Abstract model theory

FRAGMENTS FOR LATER USE ELSEWHERE

Morphisms between structures

For every signature σ there is a category which has the σ-structures as objects. In fact, three such categories are in wide use and determine the flavours of different areas of model theory. Homomorphisms are the most general notion. They are the standard notion in finite model theory and universal algebra, and they specialize correctly in the case of many algebraic and other structures. Embeddings are used in algebraic model theory, and elementary embeddings are the most natural notion for abstract model theory.

Homomorphisms

Given two structures ${\mathcal {A}},{\mathcal {B}}$ of the same signature σ, a σ-homomorphism $h:{\mathcal {A}}\rightarrow {\mathcal {B}}$ is

• a map $h:|{\mathcal {A}}|\rightarrow |{\mathcal {B}}|$ which
• commutes with all (n-ary) functions f of σ:

$h(f^{\mathcal {A}}(a_{1},a_{2},\dots ,a_{n}))=f^{\mathcal {B}}(h(a_{1}),h(a_{2}),\dots ,h(a_{n}))$

for all $a_{1},a_{2},\dots ,a_{n}\in |{\mathcal {A}}|$, and

• preserves all (n-ary) relations R of σ:

${\mathcal {A}}\models R(a_{1},a_{2},\dots ,a_{n})\;\implies \;{\mathcal {B}}\models R(h(a_{1}),h(a_{2}),\dots ,h(a_{n}))$

for all $a_{1},a_{2},\dots ,a_{n}\in |{\mathcal {A}}|$.

The notion of σ-homomorphism directly generalizes the usual notions of homomorphism for algebraic structures such as groups, rings, modules and lattice (mathematics)s, but also for relational structures such as graphs and partial orders, and for mixed structures such as linearly ordered groups. It is also the standard notion of morphism in universal algebra and in finite model theory.

The σ-structures and σ-homomorphisms form a category σ-Hom. The epimorphisms in this category are the surjective σ-homomorphisms, and the monomorphisms are the injective σ-homomorphisms. The isomorphisms in this category are bijective σ-homomorphisms, but the converse is true iff there are no function symbols in σ.

Quantifier-free embeddings

Given two structures ${\mathcal {A}},{\mathcal {B}}$ of the same signature σ, a σ-embedding $h:{\mathcal {A}}\rightarrow {\mathcal {B}}$ is

• an injective map $h:|{\mathcal {A}}|\rightarrow |{\mathcal {B}}|$ which
• commutes with all (n-ary) functions f of σ:

$h(f^{\mathcal {A}}(a_{1},a_{2},\dots ,a_{n}))=f^{\mathcal {B}}(h(a_{1}),h(a_{2}),\dots ,h(a_{n}))$

for all $a_{1},a_{2},\dots ,a_{n}\in |{\mathcal {A}}|$, and

• does not affect any (n-ary) relations R of σ:

${\mathcal {A}}\models R(a_{1},a_{2},\dots ,a_{n})\;\implies \;{\mathcal {B}}\models R(h(a_{1}),h(a_{2}),\dots ,h(a_{n}))$

for all $a_{1},a_{2},\dots ,a_{n}\in |{\mathcal {A}}|$.

In other words, a σ-embedding is a σ-homomorphism is a σ-isomorphism with an induced substructure. The σ-structures and σ-embeddings form a subcategory σ-Emb of σ-Hom. These are the standard notions for a style of model theory that is often connected with Abraham Robinson and his school on the east coast of the United States. Hodges disputes this.

Elementary embeddings

Given two structures ${\mathcal {A}},{\mathcal {B}}$ of the same signature σ, an elementary σ-embedding $h:{\mathcal {A}}\rightarrow {\mathcal {B}}$ is

• an map $h:|{\mathcal {A}}|\rightarrow |{\mathcal {B}}|$ which
• commutes with all first-order σ-formulas φ(x_1,x_2, ... ,x_n):

${\mathcal {A}}\models \varphi (a_{1},a_{2},\dots ,a_{n})\iff {\mathcal {B}}\models \varphi (h(a_{1}),h(a_{2}),\dots ,h(a_{n}))$

for all $a_{1},a_{2},\dots ,a_{n}\in |{\mathcal {A}}|$.

The σ-structures and elementary σ-embeddings form a subcategory σ-Elem of σ-Hom. There is a tradition, questioned by Hodges, that connects the style of model theory which works with elementary embeddings to Alfred Tarski and his school on the west coast of the United States.

Biographies related to model theory

• Peter Cameron
• Andrzej Ehrenfeucht
• Roland Fraïssé
• Kurt Gödel
• Rami Grossberg
• Wilfrid Hodges
• Ehud Hrushovski
• Howard Jerome Keisler
• Leopold Löwenheim
• Dugald Macpherson
• Michael D. Morley
• Abraham Robinson
• Saharon Shelah
• Thoralf Skolem
• Alfred Tarski
• Robert Vaught

Resources

• Stanford Encyclopedia of Philosophy: Model Theory [1]
• Stanford Encyclopedia of Philosophy: First-order Model Theory [2]
• MathWorld: Model Theory [3]
• MathWorld: Universal Algebra [4]
• Springer Encyclopaedia of Mathematics: Universal Algebra [5]
• Springer Encyclopaedia of Mathematics: Algebraic System [6]

• Anand Pillay: Lecture Notes - Model Theory [7]
• Anand Pillay: Model Theory [8]

• Jouko Väänänen: A Short Course in Finite Model Theory [9]

• Burris & Sankappanavar: A Course in Universal Algebra [10]
• Basic Notation of Universal Algebra [11]
• Terms over Many Sorted Universal Algebra [12]
• Many Sorted Algebras [13]
• Minimal Signature for Partial Algebra [14]
• George M. Bergman: An Invitation to General Algebra [15]
• Peter Burmeister: A Model Theoretic Oriented Approach to Partial Algebras [16]
• Peter Burmeister: Lecture Notes on Universal Algebra – Many Sorted Partial Algebras [17]
• [18]

LIST OF THINGS TO DO

Organisational things

• Keep categorisations clean.
• Keep Project Math templates and article classifications in good shape.
• Keep List of mathematical logic topics#Model_theory up to date.

Existing articles

• Extend age (model theory) and rename to Fraïssé limit.
• Merge elementary class and pseudoelementary class.
• Herbrand universe needs work. What is the exact definition? Can it be merged with Term algebra? If not, explain the difference.
• Ax-Kochen theorem uses undefined terms like "exceptional prime".
• Compactness theorem. Explain the topological space of all complete first-order σ-theories. The compactness theorem is equivalent to saying that it is compact. It is in fact a Stone space.
• Interpretable structure add modern meaning
• What to do about reduced product and direct product?
• Problematic relation between algebraic structure and structure (mathematical logic).
• separoid

Wishlist for new articles

• Glossary of model theory (see Lists of mathematics topics for many other glossaries).
• Homogeneous structure, with a redirect from homogeneous model
• theory (mathematical logic) has the potential to swallow conservative extension and complete theory
• oriented matroid

Strange things

• assignment (mathematical logic)
• conservative extension
• atomic sentence – this is philosophical logic

Non-first-order model theory

• Boolean-valued model. Should this be in Category:Inner model theory?
• institutional model theory, institution (computer science) (is this finite model theory? -- No. --Tillmo 22:06, 30 November 2007 (UTC))
• Kripke semantics, general frame
• Lindström quantifier

PAGE VIEW STATISTICS

• Gödel's incompleteness theorems 24502
• First-order logic 20452
• Model theory 6773
• Embedding 5755
• Soundness 4049
• Peano axioms 3859
• Gödel's completeness theorem 2503 / Original proof of Gödel's completeness theorem 682
• Undecidable problem 1998
• Kripke semantics 1923
• Interpretation (logic) 1636
• Presburger arithmetic 1431
• Structure (mathematical logic) 1353
• Theory (mathematical logic) 1221
• Compactness theorem 1203
• Atomic model (mathematical logic) 970 (before renaming)
• Skolem normal form 947
• Substructure 820
• Skolem's paradox 774
• Signature (logic) 749
• Functional predicate 733
• Ultraproduct 701
• List of first-order theories 699
• Saturated model 633
• Quantifier elimination 585
• Complete theory 510
• Interpretation (model theory) 493
• Reduct 465
• Non-standard arithmetic 463
• Löwenheim–Skolem theorem 454
• Type (model theory) 356
• Conservative extension 355
• Valuation (logic) 335
• Stable theory 335
• Exponential field 334
• Definable set 333
• Non-standard model 315
• Institutional model theory 310
• Institution (computer science) 306
• Elementary equivalence ca. 300
• Spectrum of a theory 294
• Elementary class 280
• Morley's categoricity theorem 278
• Prime model 261
• Boolean-valued model 259
• Age (model theory) 254 / Amalgamation property 250 / Joint embedding property 1
• O-minimal theory 243
• Back-and-forth method 236
• Differentially closed field 217
• Ehrenfeucht–Fraïssé game 193
• Indiscernibles 191
• Potential isomorphism 189
• Hrushovski construction 183
• Computable model theory 180
• General frame 167
• Ax–Kochen theorem 164
• Vaught conjecture 164
• Tarski's_exponential_function_problem 154
• Tennenbaum's theorem 153
• Morley rank 151
• Tame group 145
• C-minimal theory 136
• Pregeometry (model theory) 128
• Stable group 116
• Pseudoelementary class 99
• Model complete theory 91
• Zariski geometry 88
• Strongly minimal theory 88
• Weakly o-minimal structure 87
• Descriptive complexity theory 94
• Decidable sublanguages of set theory 87
• Forking extension 75
• Stability spectrum 72
• Imaginary element 69
• Existentially closed model 67
• Ax–Grothendieck theorem 39
• Wilkie's theorem 0

DRAFT ARTICLE ON TOPOLOGICAL MODEL THEORY

First-order topological structures and theories

Given a signature σ, a first-order topological σ-structure is a σ-structure M, equipped with a first-order σ-formula (without parameters) Ω(x;y₁…y_n) such that the realisation sets of the instances Ω(x;b₁…b_n) form the basis of a topology. In other words, Ω is required to satisfy the axiom $\forall x\forall {\bar {y}}\forall {\bar {z}}\exists {\bar {w}}[\Omega (x;{\bar {w}})\wedge \forall x'(\Omega (x;{\bar {w}})\to \Omega (x;{\bar {y}})\Omega (x;{\bar {z}}))]$. A first-order topological σ-theory is a first-order σ-theory T equipped with a first-order σ-formula Ω(x;y₁…y_n) such that all models of T are first-order topological σ-structures in the obvious way.

t-minimal structures and theories. (Follow Pillay or Schoutens?)