Relational Structure

Definition

A relational structure is a fundamental mathematical construct consisting of:

• A domain $D$ (a non-empty set)
• A family of relations $\mathbf{R}=\{R_1,R_2,\dots ,R_n\}$ on $D$

Formally, a relational structure is an ordered tuple:

$\mathcal{A}=⟨D,R_1,R_2,\dots ,R_n⟩$

where each $R_i$ is a relation on $D$ (i.e., $R_i\subseteq D^{k_i}$ for some arity $k_i$).

Key Characteristics

• Domain: Non-empty set of objects/elements
• Relations: Subsets of Cartesian products of the domain
• Signature: Specifies number and arities of relations
• Foundation for models: Provides semantic structures for logic
• Extensional: Defined by actual elements and tuples
• Homomorphisms: Structure-preserving mappings between relational structures
• Isomorphism: Captures structural equivalence

Components

1. Domain (Universe):

   • Set $D$ of elements
   • Can be finite or infinite
   • Elements are the “objects” of discourse

2. Relations:

   • $n$-ary relations: $R_i\subseteq D^n$
   • Binary relations ($n=2$): Most common in applications
   • Unary relations ($n=1$): Properties or predicates
   • Functions can be represented as functional relations

3. Signature (Type):

   • Specifies structure: $\sigma =(k_1,k_2,\dots ,k_n)$
   • $k_i$ is arity of $R_i$
   • Two structures have same type if same signature

Examples

1. Graph as Relational Structure:

   • Domain $D=$ set of vertices
   • Binary relation $E\subseteq D\times D$ (edge relation)
   • Structure: $G=⟨V,E⟩$

2. Ordered Set:

   • Domain $D=$ set of elements
   • Binary relation $\le \subseteq D\times D$ (ordering relation)
   • Structure: $⟨D,\le ⟩$

3. Group:

   • Domain $D=$ set of elements
   • Ternary relation $M\subseteq D\times D\times D$ (multiplication)
   • Nullary relation $\{e\}$ (identity element)
   • Binary relation $I\subseteq D\times D$ (inverse)
   • Structure: $⟨D,M,e,I⟩$

4. Database Schema:

   • Domain $D=$ set of data values
   • Relations $R_i=$ tables (relations in database sense)
   • Structure: $⟨D,R_1,R_2,\dots ,R_n⟩$

5. Kinship Structure:

   • Domain $D=$ set of persons
   • Relations: parent-of, sibling-of, spouse-of
   • Structure: $⟨\text{Persons},\text{Parent},\text{Sibling},\text{Spouse}⟩$

Morphisms Between Structures

For structures $\mathcal{A}=⟨D_A,{\mathbf{R}}_A⟩$ and $\mathcal{B}=⟨D_B,{\mathbf{R}}_B⟩$:

1. Homomorphism: Function $h:D_A\to D_B$ preserving relations

   • If $(a_1,\dots ,a_n)\in R_A$ then $(h(a_1),\dots ,h(a_n))\in R_B$

2. Isomorphism: Bijective homomorphism with inverse also homomorphism

   • Structures are essentially the same

3. Embedding: Injective homomorphism

   • A can be seen as substructure of B

4. Automorphism: Isomorphism from structure to itself

   • Reveals symmetries

Applications

1. Model Theory:

   • Relational structures are models of logical theories
   • Satisfaction of formulas in structures

2. Database Theory:

   • Relational databases are relational structures
   • Queries as structure-preserving operations

3. Graph Theory:

   • Graphs are relational structures
   • Graph properties as relational properties

4. Formal Ontology:

   • Extensional relational structures for ontologies
   • Models of conceptualizations

5. Systems Theory:

   • Systems as relational structures
   • System behavior and composition

Properties of Relations

Relations in a structure may satisfy various properties:

1. Reflexivity: ∀x: (x,x) ∈ R
2. Symmetry: ∀x,y: (x,y) ∈ R → (y,x) ∈ R
3. Transitivity: ∀x,y,z: (x,y) ∈ R ∧ (y,z) ∈ R → (x,z) ∈ R
4. Anti-symmetry: ∀x,y: (x,y) ∈ R ∧ (y,x) ∈ R → x = y
5. Functionality: Each element has unique image

Relationship to Other Concepts

• Set Theory: Domain is a set, relations are sets of tuples
• Logic: Structures provide semantics for logical languages
• Algebra: Algebraic structures are special relational structures
• Category Theory: Structures and homomorphisms form categories

Key References

Model Theory

Wilfrid Hodges (1993)

Comprehensive treatment of relational structures in model theory, including morphisms, homomorphisms, and the role of structures in providing semantics for logical languages.

Relational structures provide the semantic foundation for both mathematical logic and many areas of computer science, extensively studied by Tarski, Robinson, Chang, and Keisler.

Related Concepts

• set-theoretic-system - Set-theoretic foundation
• extensional-relational-structure - Application in ontology
• intensional-relational-structure - Conceptual counterpart
• system - Systems as relational structures
• valued-relation - Generalization with value sets

Bibliography Keys

• chang1990model
• hodges1993model
• enderton2001mathematical
• tarski1954contributions
• robinson1963introduction