💻 computer science

Three-Dimensional Affine Spatial Logics

This paper investigates three-dimensional affine spatial logics, demonstrating that logics across different dimensions possess distinct theories and establishing that the three-dimensional case is sufficiently expressive to define coordinate frames and characterize regions up to affine equivalence.

Original authors: Adam Trybus

Published 2026-03-18

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Adam Trybus

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are an architect trying to describe the shape of a room, but you are forbidden from using numbers, rulers, or coordinates like "3 meters wide" or "5 meters high." You can only use words like "inside," "outside," "touching," and "flat." This is the world of Spatial Logic.

This paper, written by Adam Trybus, is about taking that idea and stepping it up from a flat 2D floor plan into a full 3D room. Specifically, it explores Affine Geometry—a way of looking at space that cares about straight lines and parallelism, but ignores exact distances and angles.

Here is a breakdown of the paper's journey, using simple analogies.

1. The Setup: The "Shape-Only" Universe

Most people think of geometry as measuring things (Euclidean geometry). But imagine a world where you can stretch, squash, or tilt an object, and as long as it stays "straight" and "parallel," it's considered the same shape. This is Affine Geometry.

The Analogy: Think of a rubber sheet. If you draw a square on it and stretch it into a diamond shape, it's no longer a square in the strict sense, but in affine geometry, it's still a "good" shape because the lines are still straight and parallel lines stay parallel.
The Goal: The author wants to build a language (a logic) that can describe these shapes using only regions (blobs of space) and two simple rules:
1. Inclusion: Is this blob inside that one?
2. Convexity: Is this blob "bulging out" everywhere (like a ball) or does it have a dent (like a Pac-Man)?

2. The Problem: 2D vs. 3D

The author had previously studied this in 2D (flat paper). In 2D, you can draw a "coordinate frame" (like an X and Y axis) using just three lines that cross each other. Once you have that frame, you can describe any shape on that paper perfectly.

But what happens when you go 3D?

The Analogy: Imagine you are in a room. In 2D, you can define a corner with two walls meeting. In 3D, you need three walls meeting to define a corner.
The Discovery: The author proves that the "rules" (theories) for 2D space and 3D space are fundamentally different. You can't just copy-paste the 2D rules into 3D; the 3D world has new, more complex behaviors (like how three planes intersect).

3. The Big Breakthrough: Building a 3D "GPS"

The core of the paper is showing that in this 3D world, we can build a Coordinate Frame using only the logic of "blobs" and "convexity."

How they did it:
1. They found a way to identify a Half-Space (one side of a flat wall).
2. They figured out how to tell if two walls are Parallel or if they Cross to form a line.
3. They identified three specific shapes of intersections:
  - The Fan: Three walls meeting at a single line (like the pages of an open book).
  - The Prism: A weird, stretched shape.
  - The Corner: Three walls meeting at a single point (like the corner of a room).
4. By forcing the logic to describe a "Corner," they successfully built a 3D coordinate system (X, Y, and Z axes) without ever using numbers.

4. Doing Math with Shapes

Once they had the 3D "axes," they did something magical: they defined Addition and Multiplication using only shapes.

The Analogy: Imagine you have a stick of length 1. To add another stick, you don't measure it; you use a geometric trick (drawing parallel lines) to slide the second stick next to the first. The result is a new stick representing the sum.
The author showed that you can define the number 1, the number 2, and even fractions like 1/2 just by arranging these geometric shapes in specific patterns. You can essentially "count" using only the arrangement of walls and corners.

5. The Final Result: The "Perfect Description"

The paper concludes with a powerful theorem: Every single shape in this 3D world has a unique "fingerprint" formula.

The Analogy: Imagine you have a clay sculpture. The author proved that you can write a single sentence in this special language that describes that sculpture so perfectly that only that sculpture (or a version of it that has been stretched/squashed) can satisfy the sentence.
If two shapes satisfy the same "fingerprint" sentence, they are Affine Equivalent. This means they are the same shape, just viewed from a different angle or stretched differently.

Why Does This Matter?

This isn't just abstract math. It connects to Qualitative Spatial Reasoning (QSR), which is used in Artificial Intelligence.

Real World Application: If you are building a robot that needs to navigate a room, it doesn't need to know the room is "5.4 meters wide." It just needs to know, "The wall is to my left, and the door is a convex opening in front of me."
This paper proves that we can build a very powerful, precise language for robots (or AI) to understand 3D space using only these simple, non-numerical concepts. It bridges the gap between human intuition ("that looks like a corner") and rigorous mathematical logic.

In short: The author took a logic system designed for flat paper, proved it behaves differently in 3D, and then showed that in 3D, you can build a complete mathematical universe (including numbers and coordinates) using nothing but the concepts of "inside," "outside," and "straight lines."

1. Problem Statement

The paper addresses a gap in the field of Qualitative Spatial Reasoning (QSR) and Spatial Logic. While significant research exists regarding topological spatial logics and point-based affine logics, there is a scarcity of work on region-based affine spatial logics, particularly in dimensions higher than two.

Context: Most existing research focuses on the real plane ( $\mathbb{R}^2$ ) or topological systems.
The Gap: The author aims to analyze a family of affine logics where the primitives are inclusion ( $\leq$ ) and convexity ($conv$), interpreted over real spaces of increasing dimensionality ( $\mathbb{R}^n$ ).
Specific Challenge: The paper seeks to determine if the logical theories of these models differ across dimensions and, specifically, to explore the expressiveness of the logic in three dimensions ( $\mathbb{R}^3$ ). The ultimate goal is to prove that the logic is powerful enough to define coordinate frames and characterize regions up to affine equivalence.

2. Methodology

The author employs a model-theoretic approach within the framework of first-order logic.

Underlying Structures:
- Domain: The logic is interpreted over the set of Regular Open Rational Polytopes in $\mathbb{R}^n$ , denoted as $ROQ(\mathbb{R}^n)$ . These are Boolean combinations of half-spaces bounded by hyperplanes with rational coefficients.
- Language ( $L_{conv, \leq}$ ): A first-order language with two primitive symbols:
  - $\leq$ : Binary inclusion relation ( $a \subseteq b$ ).
  - $conv$: Unary predicate indicating convexity.
- Models ( $M_n$ ): The structure $M_n = \langle ROQ(\mathbb{R}^n), conv, \leq \rangle$ .
Analytical Approach:
1. Comparative Analysis: The author first establishes that models of different dimensions ( $M_n$ vs. $M_{n+1}$ ) have distinct theories.
2. Expressiveness Construction: In the 3D case, the author constructs complex formulas to define geometric entities (planes, lines, points) and operations (addition, multiplication) indirectly through the properties of regions (half-spaces).
3. Coordinate Frame Definition: The core methodology involves defining a "coordinate frame" in 3D using specific configurations of half-spaces (corners, prisms, fans) to establish axes and units of measurement.
4. Arithmetic Simulation: Using the defined coordinate frame, the author demonstrates how to simulate arithmetic operations (addition and multiplication) on line segments within the logic, allowing for the definition of rational numbers.

3. Key Contributions

A. Distinctness of Theories Across Dimensions

The paper proves that the logical theory of the $n$ -dimensional rational model is distinct from the $(n+1)$ -dimensional model.

Mechanism: The author utilizes Helly's Theorem. Helly's Theorem states that for a finite collection of convex sets in $\mathbb{R}^n$ , if every $n+1$ of them intersect, then all of them intersect.
Result: The author constructs a sentence $\phi_N$ that expresses Helly's Theorem for $N \geq n+1$ . This sentence is valid in $M_n$ but invalid in $M_{n+1}$ (where a counterexample exists). Thus, $Th(M_n) \neq Th(M_{n+1})$ .

B. Expressiveness in Three Dimensions ( $M_3$ )

The paper provides a detailed construction showing that $M_3$ is highly expressive, capable of defining:

Geometric Primitives:
- Half-spaces: Defined as regions where both the region and its complement are convex.
- Planes: The unique boundary of a half-space.
- Lines: The intersection of two non-parallel, non-coincident planes.
- Points: The intersection of three non-parallel lines in a plane.
Configurations: The author defines formulas for specific 3D configurations of three planes:
- Fan: Three planes meeting in a single line.
- Prism: Two planes meeting a third in parallel lines.
- Corner: Three planes meeting pairwise in three distinct lines (forming a tetrahedron-like structure).
Coordinate Frames: A "Corner" configuration is used to define three axes. A fourth half-space is used to define "units of measurement" (points $I, J, K$ ) on these axes, effectively creating a 3D affine coordinate system.

C. Definability of Arithmetic

Building on the coordinate frame, the author proves that addition and multiplication of line segments (and by extension, rational numbers) are definable in $M_3$ .

Method: The author adapts geometric constructions (similar to those by Bennett [1995]) using parallelism and intersection properties of lines within the defined planes.
Implication: Since the logic can define rational numbers and arithmetic operations, the theory of $M_3$ is undecidable.

D. Affine Completeness (The Main Theorem)

The paper culminates in a theorem analogous to Pratt's [1999] result for 2D, extended to 3D.

Theorem 5.6: Every region $r \in ROQ(\mathbb{R}^3)$ satisfies an affine-complete formula.
Meaning: There exists a formula $\phi$ such that if any two regions $r$ and $r'$ satisfy $\phi$ , then $r$ and $r'$ are affine-equivalent (i.e., there exists an affine transformation mapping $r$ to $r'$ ).
Proof Strategy:
1. Any rational polytope is a Boolean combination of half-spaces.
2. The logic can "fix" a coordinate frame.
3. The logic can "fix" the bounding half-spaces of a specific region relative to that frame.
4. Since the coordinate frame and the bounding half-spaces are fixed, the entire region is uniquely determined up to affine transformation.

4. Results

Dimensional Separation: Theories of affine spatial logics are strictly different for each dimension $n$ due to the varying constraints of Helly's Theorem.
3D Expressiveness: The logic $L_{conv, \leq}$ $L_{co n v, \leq}$ over $M_3$ $M_{3}$ is sufficient to define:
- Planes, lines, and points.
- Parallelism and coincidence.
- Coordinate frames and rational units.
- Arithmetic operations on coordinates.
Affine Characterization: Every rational polytope in 3D can be uniquely characterized (up to affine equivalence) by a single first-order formula in this logic.

5. Significance

Philosophical & Theoretical: The work supports the philosophical view (championed by Russell and Pasch) that affine geometry is a fundamental, non-numerical (qualitative) framework for space, distinct from but intermediate between projective and Euclidean geometries. It validates the use of qualitative reasoning for complex spatial structures.
Computational & AI: By demonstrating that affine equivalence can be captured logically, the paper provides a foundation for Qualitative Spatial Reasoning (QSR) systems that need to handle 3D environments without relying on precise numerical coordinates.
Future Directions: The paper sets the stage for axiomatizing the theory of $M_3$ . While the 2D case has a known sound and complete axiom system, the 3D case is more complex. The results suggest that these findings can likely be extended to any dimension $n > 2$ , opening a path for a general theory of $n$ -dimensional affine spatial logics.

In summary, Trybus successfully extends the expressiveness results of 2D affine spatial logics to 3D, proving that the logic is powerful enough to reconstruct affine geometry, define arithmetic, and uniquely identify regions up to affine transformation, while simultaneously proving that the logical theories of these models are distinct across dimensions.