(Predicate Logic and Mathematical Theories)

Reflexivity

A property in a signature where a binary predicate R is reflexive if ∀𝑥 𝑅 𝑥 holds true for all structures.

Symmetry

In a signature with a binary predicate =, symmetry is satisfied if ∀𝑥 ∀𝑦 (𝑅 (𝑥, 𝑦 )→ 𝑅 (𝑦, 𝑥)) for all x and y.

Transitivity

For a binary predicate = in a signature, transitivity is met when ∀𝑥 ∀𝑦 ∀𝑧 𝑅 𝑥, 𝑦 ∧ 𝑅 𝑦, 𝑧 → 𝑅 𝑥, 𝑧 holds true.

Anti-symmetry

In a signature with a binary predicate =, anti-symmetry is achieved if ∀𝑥 ∀𝑦 ( 𝑅 (𝑥, 𝑦) ∧ 𝑅 (𝑦, 𝑥) → 𝑥 = 𝑦) for all x and y.

One-to-one (injective) functions

Functions in a signature with a unary function 𝑓 and a binary predicate = are one-to-one if ∀𝑥 ∀𝑦 (𝑓 (𝑥) = 𝑓( 𝑦) → 𝑥 = 𝑦).

Onto (surjective) functions

In a signature with a unary function 𝑓, functions are onto if ∀𝑥 ∃𝑦 (𝑓 (𝑦) = x) holds true for all x.

Reachability

The concept that cannot be expressed in Predicate Logic, involving the ability to determine if one element is reachable from another.

Closure Under an Operator

A set 𝐴 is closed under an operator 𝑓 if 𝑓 maps elements of 𝐴 to elements in the same set 𝐴, ∀𝑎 ∈ 𝐴, 𝑓 𝑎 ∈ A.

Theory

A set of sentences closed under logical entailment, where any entailed sentence is also part of the theory.

Theory structure

The set of all sentences that a structure satisfies, denoted by 𝑇ℎ(𝒮), for a given structure 𝒮.