Tuesday, November 17, 2020
Subalgebra-related congruences
The algebraic structures studied in classical abstract algebra: groups, rings, fields, vector spaces, modules, etc allow theorists to brush aside congruences and focus on subalgebras instead. Most abstract algebra textbooks describe how normal subgroups, ideals, submodules, etc produce the congruence relations. This can be formalized with a mapping between the two universal algebra lattices $Sub(A)$ and $Con(A)$.
\[ f: (K \subseteq Sub(A)) \to Con(A) \]
I call this the congruencization mapping, which is a term which probably hasn't been used before. The idea is that congruences are comparatively more complicated, so if we can construct them from simpler objects that can save us a bit of work. Indeed, this is the case with groups and related structures where $Con(A)$ is fully determined by the sublattice of normal subgroups. In semigroups, separate mappings to $Con(A)$ need to be considered. The obvious one that comes to mind is that in a Rees congruence semigroup there is a mapping from ideals to congruences.
\[ f: (Ideals(S) \subseteq Sub(S)) \to Con(A) \]
Once we have formally defined these mappings to $Con(A)$ we can separately consider their properties. It is clear that in both cases, the larger the subalgebra the bigger the congruence, so the mapping is monotone. In particular, the larger the ideal, the larger the Rees congruence associated with it.
Saturday, November 14, 2020
Inclusion-exclusion principle for set partitions
Set theory is essentially an additive logic, while on the other hand partition theory is a multiplicative logic. Sets can be added together with respect to cardinality, and the difference from the sum can be determined by the intersection. This naturally leads one to wonder if a similar construct be introduced for set partitions to measure how far they are from being multiplicative. To deal with this, I introduced the idea of the sparsity of two set partitions.
Definition. Let $P$ and $Q$ be two set partitions, and let $P \times Q$ be their cartesian product. Then the sparsity of $P$ and $Q$ is the number of non-intersecting sets in $P \times Q$ defined by $|\{ (p,q) \in P \times Q : |p \cap q| = 0 \}|$
This naturally leads to a generalization of the inclusion-exclusion principle to set partitions. Instead of intersection measuring how far two sets are from being additive, the sparsity measures how far two set partitions are from being multiplicative.
Theorem. Let $P$ and $Q$ be two equivalence relations with a finite number of equivalence classes $|P|$ and $|Q|$ in each of them. Then the number of equivalence classes in their meet in the lattice of equivalence relations is the product of the number of equivalence classes in each of them minus the sparsity. In other words, \[ |P \wedge Q| = |P|*|Q| - sparsity(p,q) \] Proof. Let $P \times Q$ be the cartesian product of the sets of equivalence classes of $P$ and $Q$. Then we can partition $P \times Q$ into two classes $Z$ consisting of all pairs of equivalence classes with zero intersection and $N$ consisting of all pairs of equivalence classes without zero intersection. Since these two classes are non-intersecting, by the inclusion-exclusion principle for set partitions: \[ |P \times Q| = |N| + |Z| \] The cartesian product of two finite sets $A \times B$ can be partitioned into $|A|$ different equivalence classes all containing $|B|$ elements. By the inclusion-exclusion principle and the fact that each of these sets is disjoint, this can be expressed as a sum which by the definition of multiplication is equal to $|A| * |B|$. \[ |A \times B| = \sum_{n=1}^{|A|} |B| = |A|*|B| \] Using this formula, we can substitute $|P|*|Q|$ into the formula for the cardinality of $|P \times Q|$ where $P$ and $Q$ are the specifically sets of equivalence classes. This produces the new formula below. \[ |P|*|Q| = |N| + |Z| \] We are almost done with the proof now, except that we need to relate this decomposition of the product to the lattice operation $P \wedge Q$. In order to do that, we must construct $P \wedge Q$. If we express $P$ and $Q$ as equivalence relations, this is $P \cap Q$ and so $P \cap Q \subseteq P,Q$. If we take $P \cap Q$ and them break it down into equivalence classes, each equivalence classes $C$ of $P \cap Q$ is a subset of exactly one equivalence class in $P$ and $Q$ since $P$ and $Q$ are partitions, which produces a single member of $P \times Q$ consisting of two equivalence classes that contain $C$. These two equivalence classes that contain $C$ are members of $N$ which produce non-empty intersections and each equivalence class is distinct so they all define different members of $N$. Therefore, this defines a one to one mapping $f: P \wedge Q \to N$ which means that $|P \wedge Q|$ equals $|N|$ since one to one mappings preserve cardinality. Additionally, $|Z| = sparsity(p,q)$ by definition. \[ |N| = |P \wedge Q| \] \[ |Z| = sparsity(p,q) \] Finally, these two equivalent definitions can be substituted into the previous formula for $|P|*|Q|$ and $sparsity(p,q)$ can be subtracted from both sides to get the intended formula. \[ |P \wedge Q| = |P|*|Q| - sparsity(p,q) \] The two formulas compared:
We can now compare the two formulas used in additive logic and multiplicative logic side by side to get the analogy between the intersection of sets and the sparsity of partitions. \[ |A \cup B| = |A| + |B| - |A \cap B| \] \[ |A \wedge B| = |A| * |B| - sparsity(a,b) \] These are the fundamental formulas that relate logic and arithmetic. Partition logic can most accurately be defined as a higher form of set theory. While set lattices have $2^n$ members, the lattice of partitions has $2^{n-1}-1$ difference atoms. That is the atoms in partition logic are sort of like sets, in that they are bits of information. Bits of information then can be used to construct all pieces of information in the partition lattice. As this is the fundamental logic of information, its fair to say that partition logic is the natural logic of multiplication.
Direct products:
As we have seen how partitions multiply together, we can now consider special cases of multiplicative partitions. One such special case is that of a direct product.
Definition. two set partitions $P$ and $Q$ are direct products of one another if they are multiplicative and the intersection of equivalence classes taken from $P$ and $Q$ all have cardinality one.
This can be used to describe a cartesian product used in set theory. In a cartesian product, the first and second equivalence relations are direct products of one another in the lattice of equivalence relations. On the same note, the direct product of two algebraic structures is defined by congruences that are direct products of one another.
References:
https://arxiv.org/abs/0902.1950
Definition. Let $P$ and $Q$ be two set partitions, and let $P \times Q$ be their cartesian product. Then the sparsity of $P$ and $Q$ is the number of non-intersecting sets in $P \times Q$ defined by $|\{ (p,q) \in P \times Q : |p \cap q| = 0 \}|$
This naturally leads to a generalization of the inclusion-exclusion principle to set partitions. Instead of intersection measuring how far two sets are from being additive, the sparsity measures how far two set partitions are from being multiplicative.
Theorem. Let $P$ and $Q$ be two equivalence relations with a finite number of equivalence classes $|P|$ and $|Q|$ in each of them. Then the number of equivalence classes in their meet in the lattice of equivalence relations is the product of the number of equivalence classes in each of them minus the sparsity. In other words, \[ |P \wedge Q| = |P|*|Q| - sparsity(p,q) \] Proof. Let $P \times Q$ be the cartesian product of the sets of equivalence classes of $P$ and $Q$. Then we can partition $P \times Q$ into two classes $Z$ consisting of all pairs of equivalence classes with zero intersection and $N$ consisting of all pairs of equivalence classes without zero intersection. Since these two classes are non-intersecting, by the inclusion-exclusion principle for set partitions: \[ |P \times Q| = |N| + |Z| \] The cartesian product of two finite sets $A \times B$ can be partitioned into $|A|$ different equivalence classes all containing $|B|$ elements. By the inclusion-exclusion principle and the fact that each of these sets is disjoint, this can be expressed as a sum which by the definition of multiplication is equal to $|A| * |B|$. \[ |A \times B| = \sum_{n=1}^{|A|} |B| = |A|*|B| \] Using this formula, we can substitute $|P|*|Q|$ into the formula for the cardinality of $|P \times Q|$ where $P$ and $Q$ are the specifically sets of equivalence classes. This produces the new formula below. \[ |P|*|Q| = |N| + |Z| \] We are almost done with the proof now, except that we need to relate this decomposition of the product to the lattice operation $P \wedge Q$. In order to do that, we must construct $P \wedge Q$. If we express $P$ and $Q$ as equivalence relations, this is $P \cap Q$ and so $P \cap Q \subseteq P,Q$. If we take $P \cap Q$ and them break it down into equivalence classes, each equivalence classes $C$ of $P \cap Q$ is a subset of exactly one equivalence class in $P$ and $Q$ since $P$ and $Q$ are partitions, which produces a single member of $P \times Q$ consisting of two equivalence classes that contain $C$. These two equivalence classes that contain $C$ are members of $N$ which produce non-empty intersections and each equivalence class is distinct so they all define different members of $N$. Therefore, this defines a one to one mapping $f: P \wedge Q \to N$ which means that $|P \wedge Q|$ equals $|N|$ since one to one mappings preserve cardinality. Additionally, $|Z| = sparsity(p,q)$ by definition. \[ |N| = |P \wedge Q| \] \[ |Z| = sparsity(p,q) \] Finally, these two equivalent definitions can be substituted into the previous formula for $|P|*|Q|$ and $sparsity(p,q)$ can be subtracted from both sides to get the intended formula. \[ |P \wedge Q| = |P|*|Q| - sparsity(p,q) \] The two formulas compared:
We can now compare the two formulas used in additive logic and multiplicative logic side by side to get the analogy between the intersection of sets and the sparsity of partitions. \[ |A \cup B| = |A| + |B| - |A \cap B| \] \[ |A \wedge B| = |A| * |B| - sparsity(a,b) \] These are the fundamental formulas that relate logic and arithmetic. Partition logic can most accurately be defined as a higher form of set theory. While set lattices have $2^n$ members, the lattice of partitions has $2^{n-1}-1$ difference atoms. That is the atoms in partition logic are sort of like sets, in that they are bits of information. Bits of information then can be used to construct all pieces of information in the partition lattice. As this is the fundamental logic of information, its fair to say that partition logic is the natural logic of multiplication.
- Addition -> set theory
- Multiplication -> partition logic
Direct products:
As we have seen how partitions multiply together, we can now consider special cases of multiplicative partitions. One such special case is that of a direct product.
Definition. two set partitions $P$ and $Q$ are direct products of one another if they are multiplicative and the intersection of equivalence classes taken from $P$ and $Q$ all have cardinality one.
This can be used to describe a cartesian product used in set theory. In a cartesian product, the first and second equivalence relations are direct products of one another in the lattice of equivalence relations. On the same note, the direct product of two algebraic structures is defined by congruences that are direct products of one another.
References:
https://arxiv.org/abs/0902.1950
Friday, November 13, 2020
Difference join of input/output relations
Given a function $f: A \to B$ we have seen how we can establish a logical input/output relationship using the lattice of set partitions, which establishes that for certain ordered pair of partitions $I$ and $O$ a mapping can be defined between the equivalence classes of $I$ and the equivalence classes of $O$. We will now see that the natural way of combining these input/output relations is defined by the meet operation in the lattice of equivalence relations.
Lemma. let $A$ and $B$ be sets and let $P_1 \times Q_1$ and $P_2 \times Q_2$ be set partitions of $A \times B$. Then $P_1 \times Q_1 \wedge P_2 \times Q_2 = P_1 \wedge P_2 \times Q_1 \wedge Q_2$.
Proof. define projection mappings to $P_1$ and $P_2$ on the first index and $Q_1$ and $Q_2$ on the second index. Then we can define a mapping to the ordered pair $(P_1, P_2)$ and this has $P_1 \wedge P_2$ as a kernel and a mapping to the ordered pair $(Q_1, Q_2)$ with $Q_1 \wedge Q_2$ as a kernel. Then mapping to both ordered pairs $((P_1,P_2),(Q_1,Q_2))$ produces a kernel of $P_1 \wedge P_2 \times Q_1 \wedge Q_2$. By swapping the inner elements of this function we can get $((P_1,Q_1),(P_2,Q_2))$ which is the ordered pair expression of $P_1 \times Q_1 \wedge P_2 \times Q_2 = P_1$. Since these two projection mappings have one-to-one mappings between one another they have isomorphic set partitions.
Corollary. $P^2 \wedge Q^2 = (P \wedge Q)^2$.
Proof. this can be immediately achieved by a simple change of variables.
Proving the main theorem:
Theorem. let $f: A \to B$ be a function and let $I_1 \to O_1$ and $I_2 \to O_2$, then $I_1 \wedge I_2 \to O_1 \wedge O_2$.
Proof. let $a =_{I_1 \wedge I_2} b$, then by the definition of intersection $a =_{I_1} b$ and $a =_{I_2} b$. Since $I_1 \to O_1$ by assumption, $f(a) =_{O_1} f(b)$ and likewise by $I_2 \to O_2$ we can infer $f(a) =_{O_2} f(b)$. Finally, by the definition of intersection of equivalence relations $f(a) =_{O_1 \wedge O_2} f(b)$.
Remarks. it makes perfect sense that given a collection of inputs you can get a collection of all their outputs. The interesting thing is that we can formally model this using the meet operation of the lattice of equivalence relations, which is the mathematical means of handling collections of information.
Constructing the congruence lattice:
Corollary. let $f : A^2 \to B$ and let $P,Q$ be congruence relations. Then their equality meet $P \wedge Q$ is a congruence.
Proof. congruence relations define mappings between equivalence classes from $P^2 \to P$ and from $Q^2 \to Q$. By the difference join of equivalence relations we can now get a mapping between equivalence classes $P^2 \wedge Q^2 \to P \wedge Q$. By the meet of cartesian products of partitions this is equal to $(P \wedge Q)^2 \to (P \wedge Q)$ which means that $P \wedge Q$ is a congruence.
Corollary. the set of congruences of an algebraic structure $A$ forms a lattice
Definition. the lattice of congruences of an algebraic structure $A$ will be denoted $Con(A)$.
Remarks. the lattice of congruences $Con(A)$ has more structure then the lattice of subalgebras $Sub(A)$ because it is a set of set systems rather then simply a set system. Therefore, it makes sense to consider $Sub(A)$ before moving on to $Con(A)$ which is potentially more complicated. Even then, $Con(A)$ has an intuitive basis in the idea of combining inputs and outputs as we have seen here.
Properties of lattices of congruences:
By the theorems that we have proven here we can immediately infer that the lattice of congruences $Con(A)$ is a lattice-ordered bounds-maintining meet subsemilattice of the lattice of equivalence relations on the ground set of an algebraic structure. As equivalence relations are intersection closed, this means that $Con(A)$ forms a Moore family as a set system just like $Sub(A)$.
Lemma. let $A$ and $B$ be sets and let $P_1 \times Q_1$ and $P_2 \times Q_2$ be set partitions of $A \times B$. Then $P_1 \times Q_1 \wedge P_2 \times Q_2 = P_1 \wedge P_2 \times Q_1 \wedge Q_2$.
Proof. define projection mappings to $P_1$ and $P_2$ on the first index and $Q_1$ and $Q_2$ on the second index. Then we can define a mapping to the ordered pair $(P_1, P_2)$ and this has $P_1 \wedge P_2$ as a kernel and a mapping to the ordered pair $(Q_1, Q_2)$ with $Q_1 \wedge Q_2$ as a kernel. Then mapping to both ordered pairs $((P_1,P_2),(Q_1,Q_2))$ produces a kernel of $P_1 \wedge P_2 \times Q_1 \wedge Q_2$. By swapping the inner elements of this function we can get $((P_1,Q_1),(P_2,Q_2))$ which is the ordered pair expression of $P_1 \times Q_1 \wedge P_2 \times Q_2 = P_1$. Since these two projection mappings have one-to-one mappings between one another they have isomorphic set partitions.
Corollary. $P^2 \wedge Q^2 = (P \wedge Q)^2$.
Proof. this can be immediately achieved by a simple change of variables.
Proving the main theorem:
Theorem. let $f: A \to B$ be a function and let $I_1 \to O_1$ and $I_2 \to O_2$, then $I_1 \wedge I_2 \to O_1 \wedge O_2$.
Proof. let $a =_{I_1 \wedge I_2} b$, then by the definition of intersection $a =_{I_1} b$ and $a =_{I_2} b$. Since $I_1 \to O_1$ by assumption, $f(a) =_{O_1} f(b)$ and likewise by $I_2 \to O_2$ we can infer $f(a) =_{O_2} f(b)$. Finally, by the definition of intersection of equivalence relations $f(a) =_{O_1 \wedge O_2} f(b)$.
Remarks. it makes perfect sense that given a collection of inputs you can get a collection of all their outputs. The interesting thing is that we can formally model this using the meet operation of the lattice of equivalence relations, which is the mathematical means of handling collections of information.
Constructing the congruence lattice:
Corollary. let $f : A^2 \to B$ and let $P,Q$ be congruence relations. Then their equality meet $P \wedge Q$ is a congruence.
Proof. congruence relations define mappings between equivalence classes from $P^2 \to P$ and from $Q^2 \to Q$. By the difference join of equivalence relations we can now get a mapping between equivalence classes $P^2 \wedge Q^2 \to P \wedge Q$. By the meet of cartesian products of partitions this is equal to $(P \wedge Q)^2 \to (P \wedge Q)$ which means that $P \wedge Q$ is a congruence.
Corollary. the set of congruences of an algebraic structure $A$ forms a lattice
Definition. the lattice of congruences of an algebraic structure $A$ will be denoted $Con(A)$.
Remarks. the lattice of congruences $Con(A)$ has more structure then the lattice of subalgebras $Sub(A)$ because it is a set of set systems rather then simply a set system. Therefore, it makes sense to consider $Sub(A)$ before moving on to $Con(A)$ which is potentially more complicated. Even then, $Con(A)$ has an intuitive basis in the idea of combining inputs and outputs as we have seen here.
Properties of lattices of congruences:
By the theorems that we have proven here we can immediately infer that the lattice of congruences $Con(A)$ is a lattice-ordered bounds-maintining meet subsemilattice of the lattice of equivalence relations on the ground set of an algebraic structure. As equivalence relations are intersection closed, this means that $Con(A)$ forms a Moore family as a set system just like $Sub(A)$.
Monday, November 9, 2020
Congruences of binary operations clarified
The definition of congruences of binary operations is well known, and they are widely used in semigroup theory and related branches of abstract algebra. We can make the definition of a congruence into an input/output relation, and thereby make it more intuitive / easier to understand and put it in the larger context of input/output relations. In order to do this, we must first introduce the idea of the cartesian product of two set partitions.
Cartesian product of set partitions:
Let $A$ and $B$ be sets, and let $P,Q$ be set partitions of $A$ and $B$ respectively. Then $P \times Q$ is the set partition on the cartesian product $A \times B$ defined by equality of $P$ in the first index and equality by $Q$ in the second index. \[ (a,b) =_{P \times Q} (c,d) \iff (a =_P c) \land (b =_Q d) \] It is not hard to see that a given set partition can have a product defined over itself by making both set partitions equal. This will determine the input set partition on the congruences of binary operation. \[ (a,b) =_{P^2} (c,d) \iff (a =_P c) \land (b =_P d) \] This sort of construction can even be generalized to any equality of n-tuple for use in universal algebra. In this way, all congruences can be defined as input/output relations where some piece of information determines another piece of information within a function.
Congruences as input/output relations:
It is not hard to see then that congruences of a binary operation $f$ are defined by input/output relationships of the form $P^2 \to P$. In other words, \[ (a,b) =_{P^2} (c,d) \implies f(a,b) =_P f(c,d) \] As is the case with all input/output relations this produces a quotient operation $P^2 \to P$ which describes how the $P^2$ input information completely determines the $P$ output information.
Cartesian product of set partitions:
Let $A$ and $B$ be sets, and let $P,Q$ be set partitions of $A$ and $B$ respectively. Then $P \times Q$ is the set partition on the cartesian product $A \times B$ defined by equality of $P$ in the first index and equality by $Q$ in the second index. \[ (a,b) =_{P \times Q} (c,d) \iff (a =_P c) \land (b =_Q d) \] It is not hard to see that a given set partition can have a product defined over itself by making both set partitions equal. This will determine the input set partition on the congruences of binary operation. \[ (a,b) =_{P^2} (c,d) \iff (a =_P c) \land (b =_P d) \] This sort of construction can even be generalized to any equality of n-tuple for use in universal algebra. In this way, all congruences can be defined as input/output relations where some piece of information determines another piece of information within a function.
Congruences as input/output relations:
It is not hard to see then that congruences of a binary operation $f$ are defined by input/output relationships of the form $P^2 \to P$. In other words, \[ (a,b) =_{P^2} (c,d) \implies f(a,b) =_P f(c,d) \] As is the case with all input/output relations this produces a quotient operation $P^2 \to P$ which describes how the $P^2$ input information completely determines the $P$ output information.
Sunday, November 8, 2020
Congruences of unary operations
Input/output relations can be defined on any function from a partition of the input set and a partition of the output set. Suppose that we have a function $f : A \to A$, then a single set partition can be used on both the input set and the output set. This leads to the notion of a congruence of unary operation.
Definition. let $f : A \to A$ be a unary operation, and let $C$ be a set partition of $A$. Then $P$ forms a congruence of $f$ provided that it satisfies the input/output relationship $P \to P$. In other words, \begin{equation} x =_P y \implies f(x) =_P f(y) \end{equation} Example one. let $\mathbb{C}$ be the set of complex numbers and consider the complex conjugation map $f : \mathbb{C} \to \mathbb{C}$ defined by $f(a+b) = f(a-bi)$. Then the set partitions for the real part R and the imaginary part I both form congruences. The quotient function f/R which is the effect of the complex conjugation on the real part is the identity, and the quotient function f/I is negation. In other words, f/I maps equivalence classes by imaginary number value to their corresponding negative equivalence class.
Example two. let sgn(x) be the sign function, then it produces three equivalence classes. The sign function is a congruence on the negation function of the real numbers $f : \mathbb{R} \to \mathbb{R}$. The quotient is a permutation on three elements which maps zero to itself, one to negative one, and negative one back to one.
Example three. let $f : \mathbb{R}^3 \to \mathbb{R}^3$ be the function defined by $f(x,y,z) = (1/x,-y,z^2)$. Then first, second, and third all produce congruences with corresponding quotients of negation, reciprocal, and square. All the functions operate on their inputs/outputs independently, and they have no effect on one another. In situations like these, we can get a commutative factorization as all functions can be applied independently without effecting their inputs or outputs.
Example four. let $P$ and $Q$ be two set partitions in which each pair of equivalence classes between intersects exactly once and let $T$ be the transformation semigroup on their common input set. Then the functions which are congruences of $P$ with identity quotients and which are congruences of $Q$ form the subsemigroup of transformations of $Q$. The effect on $Q$ of any transformation is its quotient. $P$ and $Q$ can be anything from indices or fields to any piece of information as long as they have all singular intersections. In this way, unary congruences make getters and setters both axiomatic and comprehensible.
Definition. let $f : A \to A$ be a unary operation, and let $C$ be a set partition of $A$. Then $P$ forms a congruence of $f$ provided that it satisfies the input/output relationship $P \to P$. In other words, \begin{equation} x =_P y \implies f(x) =_P f(y) \end{equation} Example one. let $\mathbb{C}$ be the set of complex numbers and consider the complex conjugation map $f : \mathbb{C} \to \mathbb{C}$ defined by $f(a+b) = f(a-bi)$. Then the set partitions for the real part R and the imaginary part I both form congruences. The quotient function f/R which is the effect of the complex conjugation on the real part is the identity, and the quotient function f/I is negation. In other words, f/I maps equivalence classes by imaginary number value to their corresponding negative equivalence class.
Example two. let sgn(x) be the sign function, then it produces three equivalence classes. The sign function is a congruence on the negation function of the real numbers $f : \mathbb{R} \to \mathbb{R}$. The quotient is a permutation on three elements which maps zero to itself, one to negative one, and negative one back to one.
Example three. let $f : \mathbb{R}^3 \to \mathbb{R}^3$ be the function defined by $f(x,y,z) = (1/x,-y,z^2)$. Then first, second, and third all produce congruences with corresponding quotients of negation, reciprocal, and square. All the functions operate on their inputs/outputs independently, and they have no effect on one another. In situations like these, we can get a commutative factorization as all functions can be applied independently without effecting their inputs or outputs.
Example four. let $P$ and $Q$ be two set partitions in which each pair of equivalence classes between intersects exactly once and let $T$ be the transformation semigroup on their common input set. Then the functions which are congruences of $P$ with identity quotients and which are congruences of $Q$ form the subsemigroup of transformations of $Q$. The effect on $Q$ of any transformation is its quotient. $P$ and $Q$ can be anything from indices or fields to any piece of information as long as they have all singular intersections. In this way, unary congruences make getters and setters both axiomatic and comprehensible.
Saturday, November 7, 2020
Input/output relations
The lattice of set partitions is one of the most important constructions in mathematics, because of its key role in the theory of functions. As functions are relations between input and output, all aspects of the relationship between set partitions and functions can be described by input/output relationships. First, I will briefly discuss set partitions.
Lattice of set partitions:
Set partitions play two different roles: they represent equivalences and they represent differences. Therefore, they can be ordered in two different ways: the equivalence ordering and the differences ordering. The equivalence ordering is useful for example because there is a monotone mapping between subalgebras of the symmetric group (permutation groups) and the lattice of equivalence relations defined by orbits. The differences ordering is useful because it determines the information ordering of functions on a given input. A function has more information then another if preserves more differences then it. In order to avoid confusion between these dual lattices, the semilattices can be labeled individually:
Input/output relations:
Suppose that we have a function $f : A \to B$ with an input set $A$ and an an output set $B$. This essentially means that the function defines an input/output relationship between the inputs and the outputs. Given any input a single output is defined. We can relate this to set partitions by defining a set partition of the input set $I$ and a set partition of the output set $O$. Using these set partitions, we can define a criterion for a functional input/output relationship between these set partitions: \[ x =_I y \implies f(x) =_O f(y) \] Intuitively this means that given the information in the input, then we can determine the information in the output. Partitions can be defined from anything from indices of sequences, fields, or any other piece of information which makes this possible. So this general construction lets us determine when any piece of information determines another. Congruences defined in abstract algebra are also defined in this way.
Functions as composite objects:
Given an input/output relationship on a function, then we can always get a quotient function which defines how given an element of I we can determine which element of O is produced. That is the quotient function defines how we can get the output information from the input information. In this way, we see how functions are partially ordered: that is they have parts. As functions are input/output relationships the most natural way to define their parts is not through subsets but rather through set partitions that determine input/output relationships that can produce new quotient functions. These are new input/output relationships which are parts of functions.
Lattice of set partitions:
Set partitions play two different roles: they represent equivalences and they represent differences. Therefore, they can be ordered in two different ways: the equivalence ordering and the differences ordering. The equivalence ordering is useful for example because there is a monotone mapping between subalgebras of the symmetric group (permutation groups) and the lattice of equivalence relations defined by orbits. The differences ordering is useful because it determines the information ordering of functions on a given input. A function has more information then another if preserves more differences then it. In order to avoid confusion between these dual lattices, the semilattices can be labeled individually:
- Differences join: the join in the differences ordering
- Equality join: the join in the equvialence ordering
Input/output relations:
Suppose that we have a function $f : A \to B$ with an input set $A$ and an an output set $B$. This essentially means that the function defines an input/output relationship between the inputs and the outputs. Given any input a single output is defined. We can relate this to set partitions by defining a set partition of the input set $I$ and a set partition of the output set $O$. Using these set partitions, we can define a criterion for a functional input/output relationship between these set partitions: \[ x =_I y \implies f(x) =_O f(y) \] Intuitively this means that given the information in the input, then we can determine the information in the output. Partitions can be defined from anything from indices of sequences, fields, or any other piece of information which makes this possible. So this general construction lets us determine when any piece of information determines another. Congruences defined in abstract algebra are also defined in this way.
Functions as composite objects:
Given an input/output relationship on a function, then we can always get a quotient function which defines how given an element of I we can determine which element of O is produced. That is the quotient function defines how we can get the output information from the input information. In this way, we see how functions are partially ordered: that is they have parts. As functions are input/output relationships the most natural way to define their parts is not through subsets but rather through set partitions that determine input/output relationships that can produce new quotient functions. These are new input/output relationships which are parts of functions.
Saturday, October 31, 2020
Ring subsets
Let $R$ be a ring. Then the subsets of $R$ can be classified by which operations and relations they are closed under. This produces an ontology of Moore families.
Every single one of these Moore families produces a type of lattice: lattices of additive subgroups, lattices of subrings,lattices of ideals, etc. Subfamilies in the inclusion ordering form lattice-ordered suborders of one another as lattices. These may or may not be sublattices depending upon the families in consideration.
Lattice of ideals:
Theorem. the lattice of ideals forms a sublattice of the lattice of additive subgroups
Proof.
Meet closure:
Ideals and additive subgroups are both Moore families, so they both preserve intersection as their meet operation. Therefore, the lattice of ideals is a meet subsemilattice of the lattice of additive subgroups.
Join closure:
Let $R$ be a ring, then the additive group of the ring $(R,+)$ is an commutative group. The join of two groups is equal to the set of all sums of sequences formed by elements of the two groups, but with commutativity this reduces to all sums of two elements with one chosen from each group. Let $A,B$ be subgroups of $(R,+)$ then $A \vee B$ is equal to the set {a+b} of sums of elements from each group.This forms a subgroup, so the only thing to remain is to show that this set {a+b} is also an ideal.
Let $x$ be an element of the ring $R$. Then let $a+b$ be an element of $A \vee B$. The product of $x$ and $a+b$ is equal to $x(a+b)$. By the distributive law, this is equal to $xa+xb$. The set $A$ is an ideal so there exists some element of $A$ denoted $a_0$ which is equal to the product $xa$ and since $B$ is an ideal there is some element $b_0$ equal to the product $xb$. By substitution $xa+xb = a_0+b_0$, but now $a_0+b_0 \in {a+b} = A \vee B$ and therefore the product is in the original set. Ideals therefore form a join subsemilattice of the lattice of additive subgroups.
Remarks. the join of two ideals in the lattice of ideals is typically referred to as $A+B$ rather then $A \vee B$. The fact that ideals are a sublattice of additive subgroups puts this in context. Therefore, from one now one the join of ideals can be referred to as $A+B$.
Corollary. the lattice of ideals is a sublattice of $Sub(R)$.
Proof. Additive subgroups, subrings, and ideals form a chain of lattices. Ideals are a sublattice of additive subgroups, and therefore they must be a sublattice of the intermediate lattice of subrings. To see this, consider the join of two ideals $A,B$ in the lattice of subrings. This is the smallest set that is both an additive subgroup and multiplicatively closed which contains both of them, but the smallest additively closed set is also multiplicatively closed. Therefore, the subring join of ideals is the additive subgroup join which is an ideal. Therefore, the join of ideals is an ideal. The meet of ideals is an ideal because both subrings and ideals are Moore families.
Overview. ideals form a union-free modular Moore family
Lattice of radical ideals
Another lattice of ring subsets is the lattice of radical ideals. This does not necessarily form a sublattice of the lattice of ideals. The closure operation associated with this family is the radical of an ideal $\sqrt{I}$. Prime ideals are the intersection-irreducible members of this family, therefore by considering the lattice of radical ideals we can give the prime ideals a lattice-theoretic perspective.
Lattice of ideals:
Theorem. the lattice of ideals forms a sublattice of the lattice of additive subgroups
Proof.
Meet closure:
Ideals and additive subgroups are both Moore families, so they both preserve intersection as their meet operation. Therefore, the lattice of ideals is a meet subsemilattice of the lattice of additive subgroups.
Join closure:
Let $R$ be a ring, then the additive group of the ring $(R,+)$ is an commutative group. The join of two groups is equal to the set of all sums of sequences formed by elements of the two groups, but with commutativity this reduces to all sums of two elements with one chosen from each group. Let $A,B$ be subgroups of $(R,+)$ then $A \vee B$ is equal to the set {a+b} of sums of elements from each group.This forms a subgroup, so the only thing to remain is to show that this set {a+b} is also an ideal.
Let $x$ be an element of the ring $R$. Then let $a+b$ be an element of $A \vee B$. The product of $x$ and $a+b$ is equal to $x(a+b)$. By the distributive law, this is equal to $xa+xb$. The set $A$ is an ideal so there exists some element of $A$ denoted $a_0$ which is equal to the product $xa$ and since $B$ is an ideal there is some element $b_0$ equal to the product $xb$. By substitution $xa+xb = a_0+b_0$, but now $a_0+b_0 \in {a+b} = A \vee B$ and therefore the product is in the original set. Ideals therefore form a join subsemilattice of the lattice of additive subgroups.
Remarks. the join of two ideals in the lattice of ideals is typically referred to as $A+B$ rather then $A \vee B$. The fact that ideals are a sublattice of additive subgroups puts this in context. Therefore, from one now one the join of ideals can be referred to as $A+B$.
Corollary. the lattice of ideals is a sublattice of $Sub(R)$.
Proof. Additive subgroups, subrings, and ideals form a chain of lattices. Ideals are a sublattice of additive subgroups, and therefore they must be a sublattice of the intermediate lattice of subrings. To see this, consider the join of two ideals $A,B$ in the lattice of subrings. This is the smallest set that is both an additive subgroup and multiplicatively closed which contains both of them, but the smallest additively closed set is also multiplicatively closed. Therefore, the subring join of ideals is the additive subgroup join which is an ideal. Therefore, the join of ideals is an ideal. The meet of ideals is an ideal because both subrings and ideals are Moore families.
Overview. ideals form a union-free modular Moore family
Lattice of radical ideals
Another lattice of ring subsets is the lattice of radical ideals. This does not necessarily form a sublattice of the lattice of ideals. The closure operation associated with this family is the radical of an ideal $\sqrt{I}$. Prime ideals are the intersection-irreducible members of this family, therefore by considering the lattice of radical ideals we can give the prime ideals a lattice-theoretic perspective.
Subscribe to:
Posts (Atom)