Book: A Transition to Advanced Mathematics#
Contents#
Abstract Algebra#
Structure |
Properties |
|---|---|
Magma |
Non-empty set, binary operation, closed |
Semi Group |
Non-empty set, binary operation, closed, associative |
Monoid |
Non-empty set, binary operation, closed, associative, identity element |
Group |
Non-empty set, binary operation, closed, associative, identity element, inverse elements |
Rng |
Non-empty set, binary operation, closed, associative, identity element, inverse elements, commutative (abelian group) |
. |
Non-empty set, binary operation, closed, associative (semi group) |
. |
Distributivity of multiplication over addition |
Ring |
Non-empty set, binary operation, closed, associative, identity element, inverse elements, commutative (abelian group) |
. |
Non-empty set, binary operation, closed, associative, identity element (monoid) |
. |
Distributivity of multiplication over addition |
Division Ring |
Non-empty set, binary operation, closed, associative, identity element, inverse elements, commutative (abelian group) |
. |
Non-empty set, binary operation, closed, associative, identity element, inverse elements (group) |
. |
Distributivity of multiplication over addition |
Field |
Non-empty set, binary operation, closed, associative, identity element, inverse elements, commutative (abelian group) |
. |
Non-empty set, binary operation, closed, associative, identity element, inverse elements, commutative (abelian group) |
. |
Distributivity of multiplication over addition |
Algebraic Structures#
DEFINITION
An algebraic structure is a non-empty set \(A\) with a collection of one or more operations on \(A\) and a possibly empty collection of relations on \(A\).
Note:
Algebraic structures may also be called models, structures, algebraic systems, or algebras.
DEFINITION
The order of an algebraic structure is the order of its set.
Properties of algebraic structures#
Closure#
A collection of objects is closed under some operation if applying that operation to members of the collection returns an object in the collection.
DEFINITION
Let \((A, *)\) be a structure and let \(B\) be a subset of \(A\). \(B\) is closed under \(*\) iff for all \(x, y \in B, x * y \in B\).
\(A\) is closed under \(*\) since \(*\) is a function that maps to \(A\).
For any proper subset \(B\) of \(A\) that is closed under \(*\), the same operation \(*\) is used to denote the restriction of the operation to \(B \times B\).
The following statements are equivalent:
\(B\) is closed under \(*\)
\(*\) is an operation on \(B\)
\((B, *)\) is a structure
Associativity#
DEFINITION
Let \((A, *)\) be a structure. \(*\) is associative on \(A\) iff for all \(x, y, z \in A, (x * y) * z = x * (y * z)\).
What are the implications of associativity?
So long as factors are written in the same order, parentheses can be discarded: \((ab)c = a(bc) = abc\). This can be extended inductively: \(((ab)c)d = (a(bc))d = (abc)d = abcd\).
Since \((xx)x = x(xx) = xxx\), we can define powers such as \(x^3\). If \((xx)x \ne x(xx)\), then \(x^3\) doesn’t work.
Commutativity#
DEFINITION
Let \((A, *)\) be a structure. \(*\) is commutative on \(A\) iff for all \(x, y \in A, x * y = y * x\).
Identity Element#
DEFINITION
Let \((A, *)\) be a structure. An element \(e\) of \(A\) is an identity element for \(*\) iff for all \(x \in A, x * e = e = e * x\).
Inverse Element#
DEFINITION
Let \((A, *)\) be a structure. If \(A\) has an identity element \(e\), and \(a\) and \(b\) are in \(A\), then \(b\) is an inverse of \(a\) iff \(a * b = b * a = e\). In this case, \(a\) would also be an inverse of \(b\).
Distributivity#
Let \(S\) be a set and let \(*\) and \(+\) be two binary operations on \(S\).
Let \(x, y, z \in S\).
The operation \(*\) is left-distributive over \(+\) if \(x * (y + z) = (x * y) + (x * z)\).
The operation \(*\) is right-distributive over \(+\) if \((y + z) * x = (y * x) + (z * x)\).
The operation \(*\) is distributive over \(+\) if it is left- and right-distributive.
When \(*\) is commutative the three conditions above are logically equivalent.
Uniqueness of the Identity Element and the Inverse Elements#
\(Theorem\)
Let \((A, *)\) be a structure.
\((A, *)\) has at most one identity element.Let \(*\) be associative on \(A\) with identity \(e\).
If \(a \in A\) has an inverse, then \(a\) has only one inverse.
\(Proof\)
(Show that if \(e\) and \(f\) are both identities for \(*\), then \(e = f\).)
Assumption: Let \(e\) and \(f\) both be identities for \(*\).
Since \(e\) is an identity for \(*\), \(ef = f = fe\) (by the definition of an identity element).
Since \(f\) is an identity for \(*\), \(ef = e = fe\) (by the definition of an identity element).
Therefore, \(e = f\).
\(\blacksquare\)
\(Proof\)
(Show that if \(x\) and \(y\) are both inverses of \(a\) for \(*\), then \(x = y\).)
Assumption: Let \(x\) and \(y\) both be inverses of \(a\) for \(*\).
Since \(x\) is an inverse of \(a\) for \(*\), \(ax = xa = e\) (by the definition of an inverse element).
Since \(y\) is an inverse of \(a\) for \(*\), \(ay = ya = e\) (by the definition of an inverse element).
Therefore, \(x = y\).
\(\blacksquare\)
Operation Tables#
DEFINITION
An operation table for a structure \((A, *)\) of order \(n\) is an \(n \times n\) array of products such that the product \(x * y\) appears in row \(x\) and column \(y\).
\(*\) is commutative on \(A\) if the operation table for \((A, *)\) is symmetric about its main diagonal.
There is no easy way to check that \(*\) is associative on \(A\) just by visually inspecting the operation table for \((A, *)\).
For a structure of order \(n\), associativity requires the equivalence all \(n^3\) products of three elements \(x * y * z\) grouped two ways \((x * y) * z\) and \(x * (y * z)\).
Example
\((\{1, 2, 3\}, *)\)
Properties
closed under \(*\)
not commutative
\(1 * 1 = 3\)
\(1 * 2 = 2\) but \(2 * 1 = 3\)
\(1 * 3 = 1\) but \(3 * 1 = 2\)
\(2 * 2 = 1\)
\(2 * 3 = 3\) and \(3 * 2 = 3\)
\(3 * 3 = 3\)
not associative
\((1 * 1) * 1 = 2\) but \(1 * (1 * 1) = 1\)
\((1 * 1) * 2 = 3\) but \(1 * (1 * 2) = 2\)
\((1 * 1) * 3 = 3\) and \(1 * (1 * 3) = 3\)
\((1 * 2) * 1 = 3\) but \(1 * (2 * 1) = 1\)
\((1 * 2) * 2 = 1\) but \(1 * (2 * 2) = 3\)
\((1 * 2) * 3 = 3\) but \(1 * (2 * 3) = 1\)
\((1 * 3) * 1 = 3\) but \(1 * (3 * 1) = 2\)
\((1 * 3) * 2 = 2\) but \(1 * (3 * 2) = 1\)
\((1 * 3) * 3 = 1\) and \(1 * (3 * 3) = 1\)
…
no identity element
Example
\((\{1, 2, 3\}, \circ)\)
Properties
closed under \(\circ\)
not commutative
\(1 \circ 1 = 1\)
\(1 \circ 2 = 2\) but \(2 \circ 1 = 1\)
…
associative
\((1 \circ 1) \circ 1 = 1\) and \(1 \circ (1 \circ 1) = 1\)
\((1 \circ 1) \circ 2 = 2\) and \(1 \circ (1 \circ 2) = 2\)
\((1 \circ 1) \circ 3 = 3\) and \(1 \circ (1 \circ 3) = 3\)
\((1 \circ 2) \circ 1 = 1\) and \(1 \circ (2 \circ 1) = 1\)
\((1 \circ 2) \circ 2 = 2\) and \(1 \circ (2 \circ 2) = 2\)
\((1 \circ 2) \circ 3 = 3\) and \(1 \circ (2 \circ 3) = 3\)
\((1 \circ 3) \circ 1 = 1\) and \(1 \circ (3 \circ 1) = 1\)
\((1 \circ 3) \circ 2 = 2\) and \(1 \circ (3 \circ 2) = 2\)
\((1 \circ 3) \circ 3\) and \(1 \circ (3 \circ 3)\)
\((2 \circ 1) \circ 1\) and \(2 \circ (1 \circ 1)\)
\((2 \circ 1) \circ 2\) and \(2 \circ (1 \circ 2)\)
\((2 \circ 1) \circ 3\) and \(2 \circ (1 \circ 3)\)
\((2 \circ 2) \circ 1\) and \(2 \circ (2 \circ 1)\)
\((2 \circ 2) \circ 2\) and \(2 \circ (2 \circ 2)\)
\((2 \circ 2) \circ 3\) and \(2 \circ (2 \circ 3)\)
\((2 \circ 3) \circ 1\) and \(2 \circ (3 \circ 1)\)
\((2 \circ 3) \circ 2\) and \(2 \circ (3 \circ 2)\)
\((2 \circ 3) \circ 3\) and \(2 \circ (3 \circ 3)\)
\((3 \circ 1) \circ 1\) and \(3 \circ (1 \circ 1)\)
\((3 \circ 1) \circ 2\) and \(3 \circ (1 \circ 2)\)
\((3 \circ 1) \circ 3\) and \(3 \circ (1 \circ 3)\)
\((3 \circ 2) \circ 1\) and \(3 \circ (2 \circ 1)\)
\((3 \circ 2) \circ 2\) and \(3 \circ (2 \circ 2)\)
\((3 \circ 2) \circ 3\) and \(3 \circ (2 \circ 3)\)
\((3 \circ 3) \circ 1\) and \(3 \circ (3 \circ 1)\)
\((3 \circ 3) \circ 2\) and \(3 \circ (3 \circ 2)\)
\((3 \circ 3) \circ 3\) and \(3 \circ (3 \circ 3)\)
no identity element
Example
\((\{1, 2, 3\}, \cdot)\)
Properties
closed under \(\cdot\)
commutative
\(1 \cdot 1 = 3\)
\(1 \cdot 2 = 1\) and \(2 \cdot 1 = 1\)
\(1 \cdot 3 = 2\) and \(3 \cdot 1 = 2\)
\(2 \cdot 2 = 2\)
\(2 \cdot 3 = 3\) and \(3 \cdot 2 = 3\)
\(3 \cdot 3 = 1\)
associative
\((1 \cdot 1) \cdot 1\) and \(1 \cdot (1 \cdot 1)\)
\((1 \cdot 1) \cdot 2\) and \(1 \cdot (1 \cdot 2)\)
\((1 \cdot 1) \cdot 3\) and \(1 \cdot (1 \cdot 3)\)
\((1 \cdot 2) \cdot 1\) and \(1 \cdot (2 \cdot 1)\)
\((1 \cdot 2) \cdot 2\) and \(1 \cdot (2 \cdot 2)\)
\((1 \cdot 2) \cdot 3\) and \(1 \cdot (2 \cdot 3)\)
\((1 \cdot 3) \cdot 1\) and \(1 \cdot (3 \cdot 1)\)
\((1 \cdot 3) \cdot 2\) and \(1 \cdot (3 \cdot 2)\)
\((1 \cdot 3) \cdot 3\) and \(1 \cdot (3 \cdot 3)\)
\((2 \cdot 1) \cdot 1\) and \(2 \cdot (1 \cdot 1)\)
\((2 \cdot 1) \cdot 2\) and \(2 \cdot (1 \cdot 2)\)
\((2 \cdot 1) \cdot 3\) and \(2 \cdot (1 \cdot 3)\)
\((2 \cdot 2) \cdot 1\) and \(2 \cdot (2 \cdot 1)\)
\((2 \cdot 2) \cdot 2\) and \(2 \cdot (2 \cdot 2)\)
\((2 \cdot 2) \cdot 3\) and \(2 \cdot (2 \cdot 3)\)
\((2 \cdot 3) \cdot 1\) and \(2 \cdot (3 \cdot 1)\)
\((2 \cdot 3) \cdot 2\) and \(2 \cdot (3 \cdot 2)\)
\((2 \cdot 3) \cdot 3\) and \(2 \cdot (3 \cdot 3)\)
\((3 \cdot 1) \cdot 1\) and \(3 \cdot (1 \cdot 1)\)
\((3 \cdot 1) \cdot 2\) and \(3 \cdot (1 \cdot 2)\)
\((3 \cdot 1) \cdot 3\) and \(3 \cdot (1 \cdot 3)\)
\((3 \cdot 2) \cdot 1\) and \(3 \cdot (2 \cdot 1)\)
\((3 \cdot 2) \cdot 2\) and \(3 \cdot (2 \cdot 2)\)
\((3 \cdot 2) \cdot 3\) and \(3 \cdot (2 \cdot 3)\)
\((3 \cdot 3) \cdot 1\) and \(3 \cdot (3 \cdot 1)\)
\((3 \cdot 3) \cdot 2\) and \(3 \cdot (3 \cdot 2)\)
\((3 \cdot 3) \cdot 3\) and \(3 \cdot (3 \cdot 3)\)
identity element 2
\(1 \cdot 2 = 1 = 2 \cdot 1\)
\(2 \cdot 2 = 2\)
\(3 \cdot 2 = 3 = 2 \cdot 3\)
inverse elements
\(1\) and \(3\) are inverses of each other
\(2\) is its own inverse
Example
\((\{1, 2, 3\}, +)\)
Properties
closed under \(+\)
not commutative
\(1 + 1 = 3\)
\(1 + 2 = 3\) but \(2 + 1 = 1\)
\(1 + 3 = 1\) and \(3 + 1 = 1\)
\(2 + 2 = 1\)
\(2 + 3 = 2\) and \(3 + 2 = 2\)
\(3 + 3 = 3\)
not associative
\((1 + 1) + 1 = 1\) and \(1 + (1 + 1) = 1\)
\((1 + 1) + 2 = 2\) but \(1 + (1 + 2) = 1\)
…
identity element 3
\(1 + 3 = 1 = 3 + 1\)
\(2 + 3 = 2 = 3 + 2\)
\(3 + 3 = 3\)
inverse elements
\(1\) and \(3\) are their own inverses
\(2\) does not have an inverse
Groups and Semi Groups#
DEFINITION
A group \((G, *)\) is a set \(G\) equipped with a binary operation \(* : G \times G \to G\) with the following properties.
\( \begin{aligned} \forall a, b \in G &\quad a * b \in G &\quad& \text{the group operation is closed} \\ \forall a, b, c \in G &\quad (a * b) * c = a * (b * c) &\quad& \text{the group operation is associative} \\ \exists \varepsilon \in G \,\, \forall a \in G &\quad a * \varepsilon = a &\quad& \text{there is an identity element} \\ \forall a \in G \,\, \exists b \in G &\quad a * b = \varepsilon &\quad& \text{each element has an inverse} \\ \end {aligned} \)
An abelian group (commutative group) has the additional property that the group operation is commutative.
\( \begin{aligned} \forall a, b \in G &\quad a * b = b * a &\quad& \text{the group operation is commutative} \\ \end {aligned} \)
Example
The set of arrows (or vectors) with a common origin in two-dimensional space is an additive abelian group. Given arrows \(h, g\) the arrow \(h + g\) is formed by drawing \(g\) with its tail at the head of \(h\) and then taking the arrow from the tail of \(h\) to the head of \(g\). The identity element is the arrow with length zero. An arrow’s inverse is an arrow of the same length drawn in the opposite direction.
DEFINITION
A semi group \((S, *)\) is a set \(S\) equipped with a binary operation \(* : S \times S \to S\) with the following properties.
\( \begin{aligned} \forall a, b \in S &\quad a * b \in S &\quad& \text{the semi group operation is closed} \\ \forall a, b, c \in S &\quad (a * b) * c = a * (b * c) &\quad& \text{the semi group operation is associative} \\ \end {aligned} \)
Let \((A, *)\) be a structure. \((A, *)\) is a semigroup iff \(*\) is associative over \(A\).
DEFINITION
A monoid \((M, *)\) is a set \(M\) equipped with a binary operation \(* : M \times M \to M\) with the following properties.
\( \begin{aligned} \forall a, b \in M &\quad a * b \in M &\quad& \text{the monoid operation is closed} \\ \forall a, b, c \in M &\quad (a * b) * c = a * (b * c) &\quad& \text{the monoid operation is associative} \\ \exists \varepsilon \in M \,\, \forall a \in M &\quad a * \varepsilon = a &\quad& \text{there is an identity element} \\ \end {aligned} \)
To review
\(\alpha^m = \alpha...\alpha\) \(\}m\) times, where \(\alpha \in \mathbb{F}\) and \(m\) a positive integer, denotes the group operation applied to \(\alpha\) \(m\) times
\((\alpha^m)^n = a^{mn}\)
\((\alpha\beta)^m = \alpha^m\beta^m\)
\(\forall \alpha, \beta \in \mathbb{F}\) and all positive integers \(m, n\)
Rings#
DEFINITION
A rng (ring without identity) \((R, +, \times)\) is a set \(R\) equipped with two binary operations called addition \(+ : R \times R \to R\) and multiplication \(\times : R \times R \to R\) s.t.
\((R, +)\) is an abelian group
\((R, \times)\) is a semi group
Multiplication distributes over addition
DEFINITION
A ring (ring with identity) has the additional property that there is a multiplicative identity element.
This makes \((R, \times)\) not a semi group but a monoid.
DEFINITION
A division ring has the additional property that there are multiplicative inverses for nonzero elements.
This makes \((R, \times)\) not a monoid but a group.
The set of polynomials \(F[x]\) in x with coefficients belonging to a field F is a ring.
Fields#
a.k.a. commutative division ring
Informally, a field is two abelian groups.
Formally, a field is a triple \((F, +, \times)\) s.t. \((F, +)\) is an additive abelian group; \((F \setminus \{0\}, \times)\) is an abelian group; and multiplication distributes over addition.
A field is a commutative ring where \(0 \ne 1\) (i.e., the additive identity element is not the multiplicative identity element) and every non-zero element is invertible.
Fields can be thought of as systems of numbers.
Examples of fields
\(\mathbb{R}\) the field of real numbers
\(\mathbb{C}\) the field of complex numbers
\(GF(2)\) the Galois field of order \(2\)
A field is a tuple \((F, +, \cdot)\) that consists of a set and two operations called addition and multiplication satisfying the following properties:
Additive Closure \(a, b \in F \rightarrow a + b \in F\)
Additive Commutativity \(a + b = b + a\)
Additive Associativity \(a + (b + c) = (a + b) + c\)
Existence of the Additive Identity Element \(\exists 0 \in F, \forall a \in F, a + 0 = a\)
Existence of Additive Inverse Elements \(\forall a \in F, \exists -a \in F, a + (-a) = 0\)
Multiplicative Closure \(a, b \in F \rightarrow a \cdot b \in F\)
Multiplicative Commutativity \(a \cdot b = b \cdot a\)
Multiplicative Associativity \(a \cdot (b \cdot c) = (a \cdot b) \cdot c\)
Existence of the Multiplicative Identity Element \(\exists 1 \in F, \forall a \in F, a \cdot 1 = a\)
Existence of Multiplicative Inverse Elements \(\forall a \ne 0 \in F, \exists a^{-1} \in F, a \cdot a^{-1} = 1\)
Distributivity \(a \cdot (b + c) = a \cdot b + a \cdot c\)
In other words, a field
is an abelian group under addition
the nonzero elements are an abelian group under multiplication
the distributive law holds
Subtraction
\(a - b \equiv a + (-b)\)
Division
\(a \div b \equiv a \cdot b^{-1}\)
Additional properties of fields:
\(a0 = 0 \,\,\,\forall a \in F\)
\((ab = 0) \rightarrow (a = 0 \lor b = 0)\) (if the product ab is zero, then at least one of a or b is zero)
\((a \ne 0 \land b \ne 0) \rightarrow (ab \ne 0)\) (the product of two nonzero elements is nonzero)
Infinite Fields
\(\mathbb{R}\) the set of real numbers
\(\mathbb{C}\) the set of complex numbers
Vector Spaces#
DEFINITION
A vector space (linear space) is an additive abelian group with a field action.
A vector space over a field \(\mathbf{F}\) is also called an \(\mathbf{F}\) vector space.
A vector space over a field \(\mathbf{F}\) is a set \(V\) with two binary operations called (vector) addition \(+ : V \times V \to V\) and scalar multiplication \(\mathbf{F} \times V \to V\)
A vector space (linear space) is a set whose elements (called vectors) may be added and multiplied (“scaled”) by numbers called scalars. Scalars may be real numbers, complex numbers, or any field elements. The operations of vector addition and scalar multiplication must satisfy the vector axioms. The terms “real vector space” and “complex vector space” specify the nature of the scalars: real coordinate space or complex coordinate space.
Example
The set of arrows (or vectors) with a common origin in two-dimensional space is an additive abelian group. The set of real numbers \(\mathbb{R}\) act on these arrows by scaling them. If \(g\) is an arrow then \(2g\) doubles its length; \(0g\) takes its length to zero; and \(-1g\) reverses its direction and halves its length.
Some well-known algebraic structures#
\( \begin{aligned} (\mathbb{Z}, +) && \infty &\quad \text{abelian group} &\quad \text{} \\ (\mathbb{Z}, \times) && \infty &\quad \text{commutative monoid} &\quad \text{} \\ (\mathbb{Z}, +, \times) && \infty &\quad \text{commutative ring with identity} &\quad \text{} \\ (\{ 0 \}, +) && 1 &\quad \\ (\{ 0 \}, \times) && 1 &\quad \\ (\{ 0, 1 \}, +) && 2 &\quad \\ (\{ 0, 1 \}, \times) && 2 &\quad \\ (\mathbb{N}, +) && \infty &\quad \text{commutative monoid} &\quad \text{} \\ (\mathbb{N}, +, \lt) && \infty &\quad \\ (\mathbb{N}, \times) && \infty &\quad \text{commutative monoid} &\quad \text{} \\ (\mathbb{P}, +) && \infty &\quad \text{commutative semi-group} &\quad \text{} \\ (\mathbb{P}, \times) && \infty &\quad \text{commutative semi-group} &\quad \text{} \\ (\mathbb{E}, +) && \infty &\quad \text{} &\quad \text{} \\ (\mathbb{E}, \times) && \infty &\quad \text{} &\quad \text{} \\ (\mathbb{O}, +) && \infty &\quad \text{} &\quad \text{} \\ (\mathbb{O}, \times) && \infty &\quad \text{} &\quad \text{} \\ (\mathbb{Z}^-, +) && \infty &\quad \text{} &\quad \text{} \\ (\mathbb{Z}^-, \times) && \infty &\quad \text{} &\quad \text{} \\ (\mathbb{Z}_m, +) && \infty &\quad \text{} &\quad \text{} \\ (\mathbb{Z}_m, \times) && \infty &\quad \text{} &\quad \text{} \\ (\mathbb{Q}, +) && \infty &\quad \text{abelian group} &\quad \text{} \\ (\mathbb{Q}, \times) && \infty &\quad \text{commutative monoid} &\quad \text{} \\ (\mathbb{Q} \setminus \{0\}, \times) && \infty &\quad \text{abelian group} &\quad \text{} \\ (\mathbb{Q}, +, \times) && \infty &\quad \text{commutative ring with identity} &\quad \text{} \\ ((0, 1), +) && \infty &\quad \\ ((0, 1), \times) && \infty &\quad \\ (\mathbb{R}, +) && \infty &\quad \text{} &\quad \text{} \\ (\mathbb{R}, \times) && \infty &\quad \text{} &\quad \text{} \\ (\mathbb{R}, +, \times) && \infty &\quad \text{commutative ring with identity} &\quad \text{} \\ (\mathbb{R}, +, \times, \lt) && \infty &\quad \\ (\mathbb{C}, +) && \infty &\quad \text{} &\quad \text{} \\ (\mathbb{C}, \times) && \infty &\quad \text{} &\quad \text{} \\ (\mathbb{C}, +, \times) && \infty &\quad \text{commutative ring with identity} &\quad \text{} \\ ( \Sigma^*, *) && \infty &\quad \text{monoid} &\quad \text{all strings over an alphabet under string concatenation} \\ \end {aligned} \)
\((\{ 0 \}, +)\)
closed
\((\{ 0 \}, \times)\)
closed
\((\{ 0, 1 \}, +)\)
not closed
\((\{ 0, 1 \}, \times)\)
closed
\(((0, 1), +)\) the open interval
not closed
\(((0, 1), \times)\) the open interval
closed
Integers#
Algebraic properties of integer arithmetic.
\(\mathbb{Z} = \{ \dots, -2, -1, 0, 1, 2, \dots \}\)
The set of integers under addition \((\mathbb{Z}, +)\) is an abelian group.
\( \begin{aligned} \forall a, b \in \mathbb{Z} &\quad a + b \in \mathbb{Z} &\quad& \text{additive closure} \\ \forall a, b, c \in \mathbb{Z} &\quad (a + b) + c = a + (b + c) &\quad& \text{additive associativity} \\ \exists 0 \in \mathbb{Z} \,\, \forall a \in \mathbb{Z} &\quad a + 0 = a &\quad& \text{existence of the identity element} \\ \forall a \in \mathbb{Z} \,\, \exists (-a) \in \mathbb{Z} &\quad a + (-a) = 0 &\quad& \text{inverse elements} \\ \forall a, b \in \mathbb{Z} &\quad a + b = b + a &\quad& \text{additive commutativity} \\ \end {aligned} \)
The set of integers under multiplication \((\mathbb{Z}, \times)\) is not a group but a commutative monoid.
\( \begin{aligned} \forall a, b \in \mathbb{Z} &\quad ab \in \mathbb{Z} &\quad& \text{multiplicative closure} \\ \forall a, b, c \in \mathbb{Z} &\quad (ab)c = a(bc) &\quad& \text{multiplicative associativity} \\ \exists 1 \in \mathbb{Z} \,\, \forall a \in \mathbb{Z} &\quad a \times 1 = a &\quad& \text{existence of the identity element} \\ \forall a, b \in \mathbb{Z} &\quad ab = ba &\quad& \text{multiplicative commutativity} \\ \end {aligned} \)
Only \(1\) and \(-1\) have integer multiplicative inverses.
The set of integers under addition and multiplication \((\mathbb{Z}, +, \times)\) is a commutative ring with unity.
Distributivity of Multiplication over Addition
\(\forall a, b, c \in \mathbb{Z} \,\, [\,\, a \cdot (b + c) = a \cdot b + a \cdot c \,\,]\)
\(2 + (3 \times 4) = 14 \ne 30 = 2 + 3 \times 2 + 4\)
Nonnegative Integers#
Algebraic properties of nonnegative-integer arithmetic.
\(\mathbb{N} = \{ 0, 1, 2, 3, \dots \}\)
The set of nonnegative integers under addition \((\mathbb{N}, +)\) is a commutative monoid.
\( \begin{aligned} \forall a, b \in \mathbb{N} &\quad a + b \in \mathbb{N} &\quad& \text{additive closure} \\ \forall a, b, c \in \mathbb{N} &\quad (a + b) + c = a + (b + c) &\quad& \text{additive associativity} \\ \exists 0 \in \mathbb{N} \,\, \forall a \in \mathbb{N} &\quad a + 0 = a &\quad& \text{existence of the identity element} \\ \forall a, b \in \mathbb{N} &\quad a + b = b + a &\quad& \text{additive commutativity} \\ \end {aligned} \)
The set of nonnegative integers under multiplication \((\mathbb{N}, \times)\) is a commutative monoid.
\( \begin{aligned} \forall a, b \in \mathbb{N} &\quad ab \in \mathbb{N} &\quad& \text{multiplicative closure} \\ \forall a, b, c \in \mathbb{N} &\quad (ab)c = a(bc) &\quad& \text{multiplicative associativity} \\ \exists 1 \in \mathbb{N} \,\, \forall a \in \mathbb{N} &\quad a \times 1 = a &\quad& \text{existence of the identity element} \\ \forall a, b \in \mathbb{N} &\quad ab = ba &\quad& \text{multiplicative commutativity} \\ \end {aligned} \)
The nonnegative integers are not closed under subtraction.
\(1, 2 \in \mathbb{N} \quad 1 - 2 \not\in \mathbb{N}\)
The nonnegative integers are not closed under division.
\(1, 2 \in \mathbb{N} \quad 1 / 2 \not\in \mathbb{N}\)
Positive Integers#
Algebraic properties of positive-integer arithmetic.
\(\mathbb{P} = \mathbb{Z}^+ = \{ 1, 2, 3, \dots \}\)
The set of positive integers under addition \((\mathbb{P}, +)\) is a commutative semigroup.
\( \begin{aligned} \forall a, b \in \mathbb{P} &\quad a + b \in \mathbb{P} &\quad& \text{additive closure} \\ \forall a, b, c \in \mathbb{P} &\quad (a + b) + c = a + (b + c) &\quad& \text{additive associativity} \\ \forall a, b \in \mathbb{P} &\quad a + b = b + a &\quad& \text{additive commutativity} \\ \end {aligned} \)
The set of positive integers under multiplication \((\mathbb{P}, \times)\) is a commutative semigroup.
\( \begin{aligned} \forall a, b \in \mathbb{P} &\quad ab \in \mathbb{P} &\quad& \text{multiplicative closure} \\ \forall a, b, c \in \mathbb{P} &\quad (ab)c = a(bc) &\quad& \text{multiplicative associativity} \\ \forall a, b \in \mathbb{P} &\quad ab = ba &\quad& \text{multiplicative commutativity} \\ \end {aligned} \)
The positive integers are not closed under subtraction.
\(1, 2 \in \mathbb{P} \quad 1 - 2 \not\in \mathbb{P}\)
The positive integers are not closed under division.
\(1, 2 \in \mathbb{P} \quad 1 / 2 \not\in \mathbb{P}\)
Even Integers#
Algebraic properties of even-integer arithmetic.
\(\mathbb{E} = \{ \dots, -4, -2, 0, 2, 4, \dots \}\)
Odd Integers#
Algebraic properties of odd-integer arithmetic.
\(\mathbb{O} = \{ \dots, -3, -1, 1, 3, \dots \}\)
Negative Integers#
Algebraic properties of negative-integer arithmetic.
\(\mathbb{Z}^- = \{ -1, -2, -3, \dots \}\)
Modular Integers#
Algebraic properties of modular-integer arithmetic.
\( \begin{aligned} \mathbb{Z}_m = \,\, & \{ [0]_m, [1]_m, [2]_m, \dots, [m - 1]_m \} \\ & \{ \bar{0}, \bar{1}, \bar{2}, \dots, \overline{m - 1} \} \\ & \{ 0, 1, 2, \dots, m - 1 \} \\ \end {aligned} \)
Rationals#
Algebraic properties of rational arithmetic.
\(\mathbb{Q} = \left\{ \frac{p}{q} : p, q \in \mathbb{Z}, q \ne 0 \right\}\)
The set of rationals under addition \((\mathbb{Q}, +)\) is an abelian group.
\( \begin{aligned} \forall a, b \in \mathbb{Q} &\quad a + b \in \mathbb{Q} &\quad& \text{additive closure} \\ \forall a, b, c \in \mathbb{Q} &\quad (a + b) + c = a + (b + c) &\quad& \text{additive associativity} \\ \exists 0 \in \mathbb{Q} \,\, \forall a \in \mathbb{Q} &\quad a + 0 = a &\quad& \text{existence of the identity element} \\ \forall a \in \mathbb{Q} \,\, \exists (-a) \in \mathbb{Q} &\quad a + (-a) = 0 &\quad& \text{inverse elements} \\ \forall a, b \in \mathbb{Q} &\quad a + b = b + a &\quad& \text{additive commutativity} \\ \end {aligned} \)
The set of rationals under multiplication \((\mathbb{Q}, \times)\) is a commutative monoid.
The set of rationals sans \(0\) under multiplication \((\mathbb{Q} \setminus \{0\}, \times)\) is an abelian group.
\( \begin{aligned} \forall a, b \in \mathbb{Q} &\quad a \times b \in \mathbb{Q} &\quad& \text{multiplicative closure} \\ \forall a, b, c \in \mathbb{Q} &\quad (a \times b) \times c = a \times (b \times c) &\quad& \text{multiplicative associativity} \\ \exists 1 \in \mathbb{Q} \,\, \forall a \in \mathbb{Q} &\quad a \times 1 = a &\quad& \text{existence of the identity element} \\ \forall a \in \mathbb{Q} \setminus \{0\} \,\, \exists a^{-1} \in \mathbb{Q} \setminus \{0\} &\quad a \times a^{-1} = 1 &\quad& \text{inverse elements} \\ \forall a, b \in \mathbb{Q} &\quad a \times b = b \times a &\quad& \text{multiplicative commutativity} \\ \end {aligned} \)
The set of rational numbers under addition and multiplication \((\mathbb{Q}, +, \times)\) is a commutative ring with identity and satisfies the requirements of a field.
Distributivity of Multiplication over Addition
\(\forall a, b, c \in \mathbb{Q} \,\, [\,\, a \cdot (b + c) = a \cdot b + a \cdot c \,\,]\)
Proofs#
Closure under addition.
Let \(\frac{a}{b}, \frac{c}{d} \in \mathbb{Q}\).
\(a, b, c, d \in \mathbb{Z}; b, d \ne 0\)
\( \frac{a}{b} + \frac{c}{d} = \frac{a}{b} \frac{d}{d} + \frac{c}{d} \frac{b}{b} = \frac{ad + bc}{bd} \)
\(ad + bc, bd \in \mathbb{Z}; bd \ne 0\)
\(\therefore \frac{ad + bc}{bd} \in \mathbb{Q}\)
\(\blacksquare\)
Additive associativity.
\( \begin{aligned} & \left( \frac{a}{b} + \frac{c}{d} \right) + \frac{e}{f} \\ = & \frac{ad + bc}{bd} + \frac{e}{f} \\ = & \frac{ad + bc}{bd} \frac{f}{f} + \frac{e}{f} \frac{bd}{bd} \\ = & \frac{adf + bcf + bde}{bdf} \\ = & \frac{a}{b} \frac{df}{df} + \frac{cf + de}{df} \frac{b}{b} \\ = & \frac{a}{b} + \frac{cf + de}{df} \\ = & \frac{a}{b} + \left( \frac{c}{d} + \frac{e}{f} \right) \\ \end {aligned} \)
\(\blacksquare\)
Additive identity element.
Let \(\frac{a}{b}\) be a rational number.
\(a, b \in \mathbb{Z}; b \ne 0\)
\(\frac{a}{b} + \frac{0}{b} = \frac{a}{b}\)
\(\blacksquare\)
Additive inverse elements.
Let \(\frac{a}{b}\) be a rational number.
\(a, b \in \mathbb{Z}; b \ne 0\)
\(\frac{a}{b} + \frac{-a}{b} = 0\)
\(\blacksquare\)
Additive commutativity.
\( \begin{aligned} & \frac{a}{b} + \frac{c}{d} \\ = & \frac{ad + bc}{bd} \\ = & \frac{bc + ad}{bd} \\ = & \frac{bc}{bd} + \frac{ad}{bd} \\ = & \frac{c}{d} + \frac{a}{b} \\ \end {aligned} \)
\(\blacksquare\)
Closure under multiplication.
Let \(\frac{a}{b}, \frac{c}{d} \in \mathbb{Q}\).
\(a, b, c, d \in \mathbb{Z}; b, d \ne 0\)
\( \frac{a}{b} \frac{c}{d} = \frac{ac}{bd} \)
\(ac, bd \in \mathbb{Z}; bd \ne 0\)
\(\therefore \frac{ac}{bd} \in \mathbb{Q}\)
\(\blacksquare\)
Reals#
Algebraic properties of real arithmetic.
\(\mathbb{R}\)
The set of real numbers under addition and multiplication \((\mathbb{R}, +, \times)\) is a commutative ring with identity and satisfies the requirements of a field.
Complex Numbers#
Algebraic properties of complex arithmetic.
\(\mathbb{C} = \left\{ a + bi : a, b \in \mathbb{Z} \right\}\)
The set of complex numbers under addition and multiplication \((\mathbb{C}, +, \times)\) is a commutative ring with identity and satisfies the requirements of a field.
Strings#
Algebraic properties of string operations.
The set of all strings including the empty string \(\varepsilon\) over an alphabet \(\Sigma\) under string concatenation \((\Sigma^*, *)\) is a monoid.
\( \begin{aligned} \forall w_1, w_2 \in \Sigma^* &\quad w_1w_2 \in \Sigma^* &\quad& \text{closure under string concatenation} \\ \forall w_1, w_2, w_3 \in \Sigma^* &\quad (w_1w_2)w_3 = w_1(w_2w_3) &\quad& \text{associativity of string concatenation} \\ \exists \varepsilon \in \Sigma^* \,\, \forall w \in \Sigma^* &\quad \varepsilon w = w &\quad& \text{existence of the identity element} \end {aligned} \)