abstractmath.org 2.0
help with abstract math

Produced by Charles Wells   Revised 2015-12-16
Introduction to this website   website TOC   website index
blog   Back to Understanding Math Chapter head


# MATHEMATICAL STRUCTURES

## Basic idea

A mathematical structure is a set (or sometimes several sets) with various associated mathematical objects such as subsets, sets of subsets, operations and relations, all of which must satisfy various requirements (axioms). The collection of associated mathematical objects is called the structure and the set is called the underlying set.

### Warning

This definition of mathematical structure is not a mathematical definition. The word "structure" is usually used in the definition or discussion of a particular kind of mathematical structure, without any general definition of the phrase "mathematical structure" being given.

In recent times it has become common to define a mathematical structure using either category theory or type theory. When done that way, the structure may not necessarily have a set as underlying structure.

## Examples of mathematical structures

In this article, I give some simple examples in detail. Although they are simple, they all have uses in one or another branch of math. After those examples, some mathematical structures of major importance are listed that an undergraduate math student may meet.

$\mathbb{N}$ is the set of all positive integers, $\mathbb{Z}$ is the set of all integers and $\mathbb{R}$ is the set of all real numbers.

### Pointed sets

A pointed set is a set together with a particular element of the set.

##### Examples
• The set $\{1,2,3\}$ together with $2$ is a pointed set. It would normally be written as $(\{1,2,3\},2)$.
• $(\mathbb{R},\pi)$ is a pointed set.
• $(\mathbb{Z},\pi)$ is not a pointed set because $\pi\notin\mathbb{Z}$.

### Relations

A relation is a set $S$ together with a set of ordered pairs of elements of the set.

I will sometimes denote the set of ordered pairs by a Greek letter, for example $\alpha$ (pronounced "alfa"), so that $\alpha$ must be a subset of $S\times S$. Then, if $(s,s')$ is an ordered pair in the set $\alpha$, you could write "$s\,\alpha\, s'$", pronounced "$s$ is related by $\alpha$ to $s'$".

##### Small examples
• The set $\alpha:=\{(1,2),(2,3),(1,3)\}$ is a relation on the set $S=\{1,2,3\}$. It is in fact the familiar relation "$\lt$" on $S$, because if $m,n$ are in $S$, then $m\lt n$ if and only if $(m,n)$ is one of the pairs $(1,2)$, $(2,3)$, or $(1,3)$. The concept that "$\lt$" is a set of ordered pairs takes a bit of getting used to.
• The set $S:=\{1,2,3\}$ together with the set of ordered pairs $\{(1,1),(1,2),(2,3),(3,1)\}$ is a relation. It is not a familiar relation. It is an arbitrary relation. (Click on "arbitrary". You might learn something.) If you called it "$\beta$" (pronounced "bay-ta" in the USA), then "$1\,\beta\,2$" is true but "$1\,\beta\,3$" is false.
• $\mathbb{Z}$ together with the set $\{(m,m)\,|\,m=m\}$ (see setbuilder notation) is the equals relation on the set of all integers.

There are more examples of relations in the section on Maps between math structures.

#### Congruence relations

Congruence relations are defined by requiring that two integers be related if they have the same remainder when divided by a particular integer. A congruence relation is an example of an equivalence relation.

For example, every integer $n$ leaves one of these remainders when divided by $3$: $0$, $1$ or $2$. I will use the notation "$\underset{3}\sim$" for this relation and similarly for integers other than $3$. (The standard notation is described in the Wikipedia article.) So $5\underset{3}\sim17$ is true because both $5$ and $17$ leave a remainder of $2$ when divided by $3$, but $5\underset{3}\sim10$ is false.

Notice that for integers $m$ and $n$, $m\underset{2}\sim n$ is true if and only if $m$ and $n$ are both even or both odd.

### Partitions

A partition is a set together with a set of subsets
(called "blocks") with the property that
every element of the set is in exactly one block.

##### Small examples
• The set $\{1,2,3\}$ together with the set of subsets $\{\{1,2\},\{3\}\}$ is a partition. Note that $1\in\{1,2\}$ and not in $\{3\}$, similarly for $2$, and $3\in\{3\}$ and not in $\{1,2\}$, so this structure fits the definition of "partition".
• The set $\{1,2,3,4,5,6,7\}$ together with the set of subsets $\{\{1,4,7\},\{2,5\},\{3,6\}\}$ is a partition. Notice that it groups numbers together that have the same remainder when divided by $3$. It can be visualized like this:
• The set $\{1,2,3\}$ together with the set of subsets $\{\{1,2\},\{1,3\}\}$ is not a partition because $1$ is in two different blocks.
• The set $\{1,2,3\}$ together with the set of subsets $\{\{1,2\},\{1\}\}$ is not a partition because $3$ is not in any block.

Can you list all the partitions of $\{1,2,3\}$?

#### Partition induced by a congruence relation

We can group the set $\mathbb{N}$ of positive integers into three blocks depending on what their remainder when divided by $3$ is. This produces three infinite blocks: $\{1,4,7,10,13,\ldots\}$, $\{2,5,8,11,14,\ldots\}$ and $\{3,6,9,12,15,\ldots\}$.

If you do this for $2$ instead of $3$ you get two blocks: the set of even positive integers and the set of odd positive integers.

### Binary operations

If $S$ is a set, then the notation "$S\times S$" denotes the set of all ordered pairs of elements of $S$. For example, if $S=\{2,5,7\}$, then $S\times S=\{(2,2),(2,5),(2,7),(5,2),(5,5),( 5,7),(7,2),(7,5),(7,7)\}$

A binary operation on a set $S$ is a function $b:S\times S\to S$.

##### Examples
• The operation of adding two real numbers is a binary operation $+:\mathbb{R}\to\mathbb{R}$. Like many common binary operations, it is written between the two numbers; you write "$2+5$" instead of "$+(2,5)$". See infix notation. Other familiar binary operations on the real numbers are multiplication and subtraction.
• Many more examples of binary operations are given in the chapter on Examples of Functions.

## Some mathematical structures of major importance in math

A math major in a college in the USA is likely to meet with all three of these examples.

### Group

A group is an abstraction of symmetry in all of its meanings. The definition of a group says it is a binary operation with certain properties, but the importance of groups comes from their association with symmetry. Most math majors in the USA learn about groups from some course or other.

The Wikipedia articles on groups, symmetries, symmetry groups and group actions include many examples and theorems concerning groups of symmetries.

### Vector space

A vector space is a set, whose elements are called vectors, with an operation of addition on the vectors and an operation called scalar multiplication allowing a vector to be multiplied by a number (or more generally by an element of a particular field).

When you first meet with vectors as a student, typically (in the USA) in second or third semester calculus, they are drawn as arrows; the idea is that a vector is determined by a direction and a length. In that guise they have a basic role to play in physics. In fact, there are vector spaces whose elements are functions; then they are called function spaces and are a major tool in analysis.

The Wikipedia article on vector spaces describes the definition and uses of vector spaces in considerable detail. It is one of the better written math articles in Wikipedia.

### Metric space

A metric space is a set $S$ together with a function $d:S\times S\to\mathbb{R}$ that satisfies a list of axioms that are all true for the distance function on the real line. So a metric space is an abstraction of the behavior of the distance function on the reals. In particular, in a metric space you can define convergence to a limit.

A metric space is an example of a topological space, although topological spaces are a more general concept.

The Wikipedia article on metric spaces defines metric spaces and gives many examples of them.

## Maps between math structures

Structures of a given type may have maps between them that preserve the structure. Such maps are often called morphisms, but particular types of structures may have their own names for structure-preserving functions. I give some examples here. Maps between structures are also discussed in the article Functions: Images and Metaphors.

### Morphisms of pointed sets

If $(S,s)$ and $(T,t)$ are pointed sets, then a function $m:S\to T$ is a morphism of pointed sets if and only if $m(s)=t$.

##### Examples
• $(\mathbb{Z},42)$ and $(\mathbb{R},\pi)$ are pointed sets. The function $f$ defined by $f(n):=(n-41)\pi$ is a morphism of pointed sets, because $f(42)=\pi$.
• The constant function that takes every integer in $\mathbb{Z}$ to $\pi$ is also a morphism of pointed sets.
• The inclusion function $\text{inc}:\mathbb{Z}\to\mathbb{R}$ defined by $\text{inc}(n)=n$ is not a morphism because $\text{inc}(42)\neq\pi$.

### Morphisms of relations

Suppose $\alpha$ is a relation on $S$ and $\beta$ is a relation on $T$. Then a morphism of relations from $\alpha$ to $\beta$ is a function $f:S\to T$ satisfying the following requirement

If $s\,\alpha\, s'$ then $t\,\beta\,t'$.

#### Increasing function

Earlier I mentioned the relation $\alpha:=\{(1,2),(2,3),(1,3)\}$ on the set $S=\{1,2,3\}$, which is the "less-than" relation "$\lt$" on $S$. Now let $T:=\{1,2,3,4\}$. Then "$\lt$" is also a relation on $T$, namely the relation $\beta:=\{(1,2),(1,3),(1,4),(2,3),(2,4),(3,4)\}$ Then the function $f:S\to T$ defined by $f(1)=1$, $f(2)=2$ and $f(3)=4$ is a morphism of relations from $(S,\alpha)$ to $(T,\beta)$. The easiest way to check this is by drawing a picture:

In this picture, the less-than relation in each of the sets is simply "above", and you can see that if one number is above another number on the left, then the numbers that the arrows take them two have the same relationship.

A function that preserves the "less-than" relation is called a strictly increasing function. The function that takes $1\to 1$, $2\to 4$, $3\to 4$ does not preserve "$\lt$" since $2\lt3$ but $4$ is not less than $4$. However, that function does preserve the "$\leq$" relation, since $4\leq4$. As you might guess, such a function is called an increasing function but not a strictly increasing function.

#### Maps between congruence relations

Let's look at the doubling function $d:\mathbb{N}\to\mathbb{N}$ defined by $d(n)=2n$.

The function $d$ is a morphism of relations from $\underset{3}\sim$ to $\underset{2}\sim$. To prove this requires showing that if $m\underset{3}\sim n$, then $2m\underset{2}\sim 2n$. Now, by definition, for any integers $r$ and $s$, $r\underset{2}\sim s$ means that $r$ and $s$ are both even or both odd. But for any integer $r$, $2r$ is always even! So the statement "If $m\underset{3}\sim n$, then $2m\underset{2}\sim 2n$" is true because "$2m\underset{2}\sim 2n$" is always true!

If you are not sure you understand this, read about the truth table for conditional assertions: If $Q$ is true, then "If $P$ then $Q$" is always true.

On the other hand, $d$ is not a morphism of relations from $\underset{2}\sim$ to $\underset{3}\sim$. This is false by counterexample: $4\underset{2}\sim 8$ because they are both even, but $8\underset{3}\sim 16$ is false, because when $8$ is divided by $3$ the remainder is $2$, but when $16$ is divided by $3$ the remainder is $1$.

### Morphisms of partitions

Let $S$ and $T$ be sets and $P_S$ be a partition of $S$ and $P_T$ a partition of $T$. A function $f:S\to T$ is a morphism of partitions if $f$ takes every element of a block of $P_S$ into one particular block of $P_T$.

#### Example

We looked previously at these two partitions:

• The partition $\{\{1,2\},\{3\}\}$ of the set $\{1,2,3\}$.
• The partition $\{\{1,4,7\},\{2,5\},\{3,6\}\}$ of the set $\{1,2,3,4,5,6,7\}$.
##### Examples

Any constant function is a morphism of partitions, for example this one:

These are also morphisms of partitions:

The inclusion function is not a morphism of partitions (in this case!).

This function is also not a morphism:

### Morphisms of binary operations

Suppose $*$ is a binary operation on a set $S$ and $\#$ is a binary operation on a set $T$. Then a function $f:S\to T$ is a morphism of binary operations if for all $s,s'\in S$, $f(s* s')=f(s)\# f(s')$. The customary way of saying this is: "$f:(S,*)\to(T,\#)$ is a homomorphism from $(S,*)$ to $(T,\#)$".

Many examples of morphisms of binary operations are described in the abstractmath.org article Functions: Images and Metaphors. I will give one example here.

#### Exponentiation

Both addition and multiplication are binary operations on the set $\mathbb{R}$ of real numbers. Let $E:\mathbb{R}\to\mathbb{R}$ be the function defined by $E(r):=2^r$. Then $E:(\mathbb{R},+)\to(\mathbb{R},\times)$ is a homomorphism.

This follows from the law of exponents: $E(r+s)=2^{r+s}=2^r\times 2^s=E(r)\times E(s)$

## How to think about mathematical structures

### Many structures on one set

The same set can have many different structures on it. For example, a two-element set has two different partition structures on it and eight different binary operations on it.

### Canonical structures

Widely-used mathematical objects generally have "canonical structures" of various types on them. For example, the set of integers can be ordered in many ways, but it has a particular ordering (the familiar one) that is referred to as "the ordering of the integers". In the same way, the set of real numbers has a canonical topology.

### Minimality

Presenting a complex mathematical idea as a mathematical structure involves finding a minimal or nearly minimal set of associated objects (a structure) and a minimal or nearly minimal set of conditions on those objects from which the theorems about the structure follow. The ingredients of the structure are kept (nearly) non-redundant so that it is easier to verify that some object is an example of that kind of structure. This is essentially the main use of the axiomatic method

This small set of objects and conditions may not be the most important aspects of the structure for applications or for one's mental representation of the structure.

All this is discussed in more detail in the article on Definition.

### Different definitions for the same structure

The same kind of structure can often be defined by two or more very different kinds of minimal ingredients. A mathematical structure of a given type has lots of structure implied by the minimal definition, and when you think of a structure it is best to think of it as containing all that information, not just the stuff in the definition.

##### Example

"Equivalence relation" and "partition" are two different ways of defining exactly the same structure on a set. This is explained in the Wikipedia article on The Fundamental Theorem of Equivalence Relations.