polynomials in algebraic systems


Polynomials in an Algebraic System

Let (A,O) be an algebraic system. Given any non-negative integer n, let S be a set of functions from An to A, satisfying the following criteria:

  1. 1.

    the projection πi:AnA is an element of S for each i between 1 and n.

  2. 2.

    for every 0-ary operator symbol cO, the corresponding element cAA is an element of S.

  3. 3.

    for any m-ary operator ωA on A, and any p1,,pmS, the function ωA(p1,,pm):AnA, given by

    ωA(p1,,pm)(a1,,an):=ωA(p1(a1,,an),,pm(a1,,an))

    is an element of S.

Take the intersectionMathworldPlanetmath of all such sets and call it 𝐏n(A). Then 𝐏n(A) is the smallest set satisfying the above two conditions. We call an element of 𝐏n(A) an n-ary polynomialMathworldPlanetmathPlanetmathPlanetmath of the algebraMathworldPlanetmathPlanetmathPlanetmath A. A polynomial of A is some n-ary polynomial of A. Two polynomials p,q are said to be equivalentMathworldPlanetmathPlanetmathPlanetmathPlanetmath if they have the same arity n, and for any 𝐚An, p(𝐚)=q(𝐚).

Examples.

  • Let G be a group. Then f(x)=x is a unary polynomial. In general, a unary polynomial of G has the form xn, n1. For a binary polynomial, first note that f(x,y)=x and g(x,y)=y are both binary. For this, a binary polynomial of G looks like

    xn1ym1xnkymk,

    where n1,mk0 and the rest are positive integers. If G is abelian, a binary polynomial has the simplified form xnym, and more generally, an n-ary polynomial of an abelian group has the form

    x1n1xknk.
  • Let R be a ring. f(x)=x is a unary polynomial, so are g(x)=nx and h(x)=xm where n,m are non-negative integers. In general, a unary polynomial of R looks like

    nmxm+nm-1xm-1++n1x+n0,

    where ni are non-negative integers with nm>0, and m is any positive integer. This is the form of a polynomial that is familiar to most people.

  • Continuing from the example above, note that, however,

    amxm+am-1xm-1++a1x+a0

    where aiR is in general not a polynomial under this definition. This is an example of an algebraic functionMathworldPlanetmath in an algebraic system.

Remarks.

  • 𝐏0(A) is non-empty iff O contains constant symbols (nullary function symbols).

  • By virtue of the definition, 𝐏n(A) is an algebraic system for each non-negative integer n.

Polynomial Symbols

If we have two algebras A,B of the same type, then, by the definition above, a polynomial of A may be considered as a polynomial of B, and vice versa. Putting this formally, we introduce polynomial symbols for a class K of algebras of the same type O. Let X={x1,x2,} be a countably infiniteMathworldPlanetmath set of variables, or symbols. For any non-negative integer n, consider a set S consisting of the following elements:

  1. 1.

    x1,,xn,

  2. 2.

    every nullary operator symbol,

  3. 3.

    if ωO is m-ary and p1,,pmS, then ω(p1,,pm)S.

Take the intersection of all such sets and we end up with a set satisfying the two conditions again, call it 𝐏n(O). Any element of 𝐏n(O) is called an n-ary polynomial symbol of K. A polynomial symbol of K is just some n-ary polynomial symbol. In model theoryMathworldPlanetmath, a polynomial symbol is nothing more than a term (http://planetmath.org/Term) over X in the O-languagePlanetmathPlanetmath.

Now, suppose AK. For a given non-negative integer n, consider the function fA:𝐏n(O)𝐏n(A), defined recursively by

  1. 1.

    fA(xi):=πi,

  2. 2.

    fA(c):=cA,

  3. 3.

    fA(ω(p1,,pn)):=ωA(fA(p1),,fA(pn)).

Then by the constructions of 𝐏n(O) and 𝐏n(A), fA is a surjection. Any polynomial p of A is said to be induced by a polynomial symbol q of K if fA(q)=p. We usually write p=qA to denote that the polynomial p (of A) is induced by the polynomial symbol q (of K). It is not hard to see that, between two algebras of the same type, there is a one-to-one correspondence between their respective polynomials the same arities. However, equivalence of polynomials in one algebra does not translate to equivalence in another.

Example. x(yz) and (xy)(xz) are both polynomials symbols in the class of lattices. In the subclass of distributive lattices, the induced polynomials are equivalent. However, in the subclass of modular lattices, the equivalence no longer holds.

Remark. Like 𝐏n(A), 𝐏n(O) is also an algebraic system, called the n-ary polynomial algebra, or absolutely free algebra, of O. Furthermore, the function fA above is an algebra homomorphism.

References

  • 1 G. Grätzer: Universal AlgebraMathworldPlanetmath, 2nd Edition, Springer, New York (1978).
  • 2 S. Burris, H.P. Sankappanavar: A Course in Universal Algebra, Springer, New York (1981).
Title polynomials in algebraic systems
Canonical name PolynomialsInAlgebraicSystems
Date of creation 2013-03-22 16:47:31
Last modified on 2013-03-22 16:47:31
Owner CWoo (3771)
Last modified by CWoo (3771)
Numerical id 16
Author CWoo (3771)
Entry type Definition
Classification msc 08A40
Synonym absolutely free algebra
Related topic TermAlgebra
Related topic AlgebraicFunction
Defines polynomial
Defines equivalent polynomials
Defines polynomial symbol
Defines induced polynomial
Defines polynomial algebra