tag

#first order logic

7 pages tagged

Maths › 03. Logic and Foundations ›

6.1 Definable Sets

Definability is one of the central ideas of model theory. Once a first order language and a structure have been fixed, formulas can be used to describe subsets of the domain, relations on the domain, and functions between definable sets. In this way, syntax gives rise to geometry inside a structure: a formula becomes a description of a set of points satisfying a condition. In this section, we work with...
logic model theory definability first order logic May 2, 2026
Maths › 03. Logic and Foundations ›

5.1 Compactness

The compactness theorem is one of the central structural results of first order logic, and it expresses a precise relationship between finite and infinite behavior of theories, showing that global satisfiability is completely controlled by finite fragments. Definition 5.1 (Structures and Satisfaction) Let $\mathcal{L}$ be a first order language, and let $\mathcal{M}$ be an $\mathcal{L}$-structure. For a sentence $A$ in $\mathcal{L}$, we write: $$ \mathcal{M} \models A $$ to mean...
logic model theory compactness first order logic May 2, 2026
Maths › 03. Logic and Foundations ›

2.4 Satisfaction

Satisfaction is the formal relation that connects syntax with semantics in first order logic, and it tells us when a formula is true in a structure under a given assignment of objects to its free variables. Satisfaction Let $\mathcal{M}$ be a structure with domain $M$, and let $s$ be an assignment: $$ s : \mathrm{Var} \to M $$ The notation: $$ \mathcal{M}, s \models A $$ means that the formula...
logic first order logic satisfaction models theories May 2, 2026
Maths › 03. Logic and Foundations ›

2.5 Validity and Entailment

Validity and entailment are semantic notions that compare formulas across all structures, rather than inside one fixed structure. Satisfaction tells us whether a formula is true in a particular structure under a particular assignment, while validity and entailment ask whether truth is forced in every possible interpretation of the language. Validity A sentence is valid if it is true in every structure for its language. Definition 2.41 (Validity) Let $A$...
logic first order logic validity entailment models May 2, 2026
Maths › 03. Logic and Foundations ›

2.3 Structures

In first order logic, formulas do not have meaning by themselves, and meaning is provided by specifying a structure in which the symbols of the language are interpreted as actual objects, functions, and relations. Structures A structure consists of a domain together with interpretations of all symbols in the signature, and it serves as the semantic environment in which formulas are evaluated. Definition 2.19 (Structure) A structure $\mathcal{M}$ for a...
logic first order logic structures interpretations models May 2, 2026
Maths › 03. Logic and Foundations ›

2.1 Terms, Predicates

First order logic extends propositional logic by introducing internal structure inside statements, so that instead of treating statements as atomic objects, we can describe objects, properties of objects, and relations between objects in a precise formal language. Symbols and Signatures To define the language, we begin with a collection of symbols that describe the kinds of objects and operations that are allowed, and this collection is called a signature. A...
logic first order logic syntax terms predicates May 2, 2026
Maths › 03. Logic and Foundations ›

2.2 Quantifiers

Quantifiers are the symbols that allow first order logic to express statements about many objects at once, and they are the main feature that separates first order logic from propositional logic. Universal and Existential Quantifiers There are two basic quantifiers: $$ \forall $$ and: $$ \exists $$ The universal quantifier $\forall$ is read as "for all", and it is used to state that a formula holds for every object in...
logic first order logic quantifiers scope variables May 2, 2026