请输入您要查询的字词:

 

单词 CongruenceLattice
释义

congruence lattice


Theorem 1.

The set Con(A) of all congruencesPlanetmathPlanetmathPlanetmathPlanetmathPlanetmath on an algebraic system A is a complete latticeMathworldPlanetmath that is a sublattice (called the congruence lattice of A) of the lattice of equivalence relations on A.

Proof.

It is not hard to see that Con(A) is a topped intersection structure. As a result, Con(A) is a complete lattice. Since it is also a subset of the lattice E(A) of equivalence relationsMathworldPlanetmath on A, the only remaining item to show is that it is a sublattice of E(A). In other words, we need to show that if 𝒞 is a family of congruence relations on A, so is Θ:=𝒞.

For convenience, let us introduce some notational devices:

  • 𝐧:={1,,n};

  • for any ak,bkA and ΘkCon(A), where k𝐧, we mean

    (a1,,an)(b1,,bn)(mod(Θ1,,Θn))

    by akbk(modΘk), for each k𝐧;

  • (a1,,an)(b1,,bn)(modΘ) means akbk(modΘ), for each k𝐧;

  • Finally, when ckck+1(modΘk), where k𝐧-𝟏, we write

    c1Θ1c2Θ2Θn-1cn.

    Let us call this an (of n).

Back to the proof. Let ω be an n-ary operator on A and (a1,,an)(b1,,bn)(modΘ). We want to show that ω(a1,,an)ω(b1,,bn)(modΘ).

The proof now breaks up into two main steps:

Step 1.

For each in, aibi(modΘ) means we have a finite

ai=c1F1c2F2Fp-1cp=bi,

where each Fi is a congruence in C, and each ciA. Now the lengths of the sequencesPlanetmathPlanetmath may vary by i. The idea is to show that we can in fact pick the sequences so that they all have the same length.

To see this, take the first two pairs of congruent elements a1b1(modΘ) and a2b2(modΘ), and expand them into two finite

  1. 1.

    a1=c1F1c2F2Fp-1cp=b1, and

  2. 2.

    a2=d1G1d2G2Gq-1dq=b2,

where ci,djA and Fi,Gj𝒞. If q<p, we may lengthen the second chain so it has the same length as the first one:

a2=d1G1d2Gq-1dqGqdq+1Gq+1Gp-1dp,

where Gq-1=Gq==Gp-1 and dq==dp=b.

The above argument and an inductionMathworldPlanetmath step on n show that we can indeed make all the “expanded” the same length. As a result, without loss of generality, we assume that all the expanded chains have the same length, say r+1.

Step 2.

CompletePlanetmathPlanetmathPlanetmathPlanetmathPlanetmath the proof.

Instead of writing all n chains, let us use our notational device, and we have the following single (again, we may write it in this fashion because all chains are now assumed to have the same finite length of r+1):

\\xymatrix(c11,,c1n)\\ar@3-[rr]-(F11,,F1n)&&(c21,,c2n)\\ar@3-[rr]-(F21,,F2n)&&\\ar@3-[rr]-(Fr1,,Frn)&&(cr+1,1,,cr+1,n)

where each cijA, each Fij𝒞, with (i,j)(𝐫+𝟏)×𝐧, and that (a1,,an)=(c11,,c1n) and (cr+1,1,,cr+1,n)=(b1,,bn).

Look at the first congruence pair \\xymatrix(c11,,c1n)\\ar@3-[rr]-(F11,,F1n)&&(c21,,c2n). This can be expanded into an of length n as follows:

\\xymatrix(c11,c12,,c1n)\\ar@3-[r]-F11&(c21,c12,,c1n)\\ar@3-[r]-F12&\\ar@3-[r]-F1n&(c21,c22,,c2n)

The idea is to replace the coordinatesMathworldPlanetmathPlanetmath one at a time, in sequence, from the first to the last, until all n coordinates are completely replaced from (c11,,c1n) to (c21,,c2n).

Now, since each F1j is a congruence, apply ω to each n-tuple to get a new

\\xymatrixω(c11,c12,,c1n)\\ar@3-[r]-F11&ω(c21,c12,,c1n)\\ar@3-[r]-F12&\\ar@3-[r]-F1n&ω(c21,c22,,c2n).

But this chain implies that ω(a1,,an)=ω(c11,,cin)ω(c21,,c2n)(modΘ). So what we have shown is that the images of the first congruence pair are congruent modulo Θ. But this process can be easily applied to subsequent congruence pairs, so that we end up with

\\xymatrixω(a1,,a2)\\ar@3-[r]-Θ&ω(c21,,c2n)\\ar@3-[r]-Θ&\\ar@3-[r]-Θ&ω(b1,,bn).

As Θ is an equivalence relation, ω(a1,,a2)ω(b1,,bn)(modΘ), completing the proof.∎

Remarks.

  • Furthermore, it can be shown that Con(A) is an algebraic lattice. The compact elements of Con(A) are finite joins of so-called principal congruences.

  • Conversely, it can be shown (by Grätzer) that every algebraic lattice is isomorphicPlanetmathPlanetmathPlanetmath to the congruence lattice of some algebraic system.

  • If A is a lattice, then Con(A) is distributivePlanetmathPlanetmath. The converse statement, that every distributive algebraic lattice is isomorphic to a congruence lattice, has recently been proven to be false by F. Wehrung.

References

  • 1 G. Grätzer: Universal AlgebraMathworldPlanetmath, 2nd Edition, Springer, New York (1978).
  • 2 F. Wehrung: http://hal.archives-ouvertes.fr/docs/00/11/93/14/PDF/CLP.pdfA Solution to Dilworth’s Congruence Lattice Problem, (2005).

随便看

 

数学辞典收录了18232条数学词条,基本涵盖了常用数学知识及数学英语单词词组的翻译及用法,是数学学习的有利工具。

 

Copyright © 2000-2023 Newdu.com.com All Rights Reserved
更新时间:2025/5/5 2:36:57