Structure (mathematical logic)

Math uses sets of things. We can use rules for them. These rules show how things work.

A structure is a group of things. It has a list of rules. These rules tell us how to use the things.

Rules can be ways to group things. They can also be ways to sort things. We use these rules to study math.

Some rules use symbols. These symbols tell us what to do. One rule might be adding numbers. Another rule might be sorting shapes.

We can use structures to study many things. They help us understand numbers and graphs. Math is full of these patterns.

In math, a structure is a way to organize ideas. It is made of three main parts. First, there is a domain. This is a set of things, like a group of numbers. Second, there is a signature. This is a list of symbols. These symbols act like a set of instructions. Third, there is an interpretation function. This tells us what the symbols actually do to our set.

For example, we can use a structure to talk about numbers. We might use symbols for adding or multiplying. The domain could be all the rational numbers. The symbols tell us how to combine them. You can also use structures to study graphs. In a graph, the domain is a set of points. The symbols show if those points are connected by lines.

Sometimes, one structure is part of another. We call this an induced substructure. For instance, the rational numbers are a substructure of the real numbers. We can also use maps called homomorphisms to compare two structures. These maps show how one structure can relate to another while keeping the rules the same.

In the world of math, a structure is a way to organize sets of things. It is not just a pile of numbers or shapes. Instead, it is a system that uses rules to connect them. Think of it like a game board. You need the pieces, the rules, and a way to know what the moves mean. In math, these pieces are called a domain. The rules are found in a signature. Finally, the interpretation function tells you how the rules work on your pieces.

To build a structure, you need three specific parts. First, you choose a domain, which is a set of objects. This set cannot be empty in most standard logic. Second, you pick a signature. This is a list of symbols that represent functions or relations. Each symbol has an arity, which is a number that says how many objects it uses at once. For example, a binary function uses two objects. Third, you use an interpretation function. This part assigns real actions to your symbols. It turns a symbol into a real way to combine or compare your objects.

People have studied these ideas for a long time. In the 19th century, mathematicians used structures to prove if sets of rules were consistent. A famous philosopher named Willard Van Orman Quine used the term "model" in 1940. He was talking about the work of Richard Dedekind. Dedekind was a pioneer who helped develop set theory between 1831 and 1916. Later, in 1954, Alfred Tarski coined the term "theory of models." Tarski was a member of the Lwów–Warsaw school.

We see structures in many places in math. You can use them to look at the rational numbers. In that structure, the domain is the set of rational numbers. The signature includes symbols for adding and multiplying. The interpretation function tells you how to actually add or multiply those numbers. You can also use them for graphs. In a graph structure, the domain is a set of points called vertices. A relation symbol tells you if two vertices are connected by an edge.

Sometimes, one structure lives inside another. We call this an induced substructure. For example, the rational numbers are a substructure of the real numbers. The real numbers are also a substructure of the complex numbers. You can also compare two structures using a map called a homomorphism. A homomorphism is a way to move from one structure to another. It must preserve the functions and relations. This means the rules stay the same even when you move the objects.

In mathematical logic, a structure is a formal way to organize a set of objects using specific rules. It is not just a collection of things; it is a system that defines how those things interact. Mathematicians use structures to study algebra and model theory. Universal algebra looks at structures that generalize ideas like groups, rings, and vector spaces. Model theory uses structures to define the meaning of first-order logic. In this field, a structure is often called a model if it satisfies all the sentences in a given theory.

To build a structure, you must define three specific components: a domain, a signature, and an interpretation function. The domain is an arbitrary set of objects, sometimes called the universe or the underlying set. In classical first-order logic, the domain cannot be empty. The signature is a list of symbols that represent functions and relations. Each symbol has an arity, which is a natural number representing how many elements the symbol acts upon. Finally, the interpretation function connects the symbols to the domain. It assigns an n-ary function to each function symbol and an n-ary relation to each relation symbol.

Functions and relations within a structure work in very specific ways. A function symbol of arity $n$ becomes a real operation that takes $n$ elements from the domain and produces a result. If a function symbol has an arity of zero, it is called a constant symbol. This constant identifies a specific, fixed element within the domain. Relation symbols work differently by describing how elements relate to one another. For example, a binary relation symbol might describe a connection between two elements. These rules allow us to turn abstract symbols into concrete mathematical actions.

The history of these ideas involves several important thinkers. Since the 19th century, mathematicians have used models to prove if a set of axioms is consistent. In 1940, the philosopher Willard Van Orman Quine used the term "model" while referencing the work of Richard Dedekind. Dedekind was a pioneer in set theory from 1831 to 1916. Later, in 1954, Alfred Tarski, a member of the Lwów–Warsaw school, coined the term "theory of models." These developments helped move logic from abstract reasoning toward a more formal, structural science.

We can see structures in many familiar mathematical systems. For instance, the rational numbers can be viewed as a structure with a specific signature. This signature includes two binary function symbols for addition and multiplication, a unary function for negation, and two constant symbols for zero and one. The real numbers and complex numbers follow this same pattern. Interestingly, the ring of integers is also a structure using this same signature, even though it is not a field. This shows that a structure does not have to satisfy every rule of a specific system to be valid.

Sometimes, one structure is contained within another, which we call an induced substructure. For a structure to be an induced substructure, it must share the same signature and its domain must be a subset of the larger domain. Furthermore, all functions and relations must work the same way in both. A subset of a domain is called "closed" if applying any function to its elements always results in another element within that same subset. The rational numbers are an induced substructure of the real numbers. Similarly, the real numbers are an induced substructure of the complex numbers.

Mathematicians also use homomorphisms to compare different structures. A homomorphism is a map from one structure to another that preserves all functions and relations. If you move an element from one system to another using a homomorphism, the mathematical rules must still hold true. A special type of homomorphism is called an embedding. An embedding is a homomorphism that is also injective, meaning it maps distinct elements to distinct targets. These concepts are vital in computer science. For example, the "homomorphism problem" is used to study the complexity of constraint satisfaction problems and database queries.