PlanetMath: polynomials in algebraic systems

(more info)

Math for the people, by the people.

Main Menu

sections Encyclopædia
Papers
Books
Expositions

meta Requests (191)
Orphanage
Unclass'd (1)
Unproven (496)
Corrections (7)
Classification

talkback Polls
Forums
Feedback
Bug Reports

downloads Snapshots
PM Book

information News
Docs
Wiki
ChangeLog
TODO List
Legalese
About

Entry average rating: No information on entry rating

polynomials in algebraic systems

(Definition)

Polynomials in an Algebraic System

Let

be an algebraic system. Given any non-negative integer

, let

be a set of functions from

, satisfying the following criteria:

the projection $\pi_i:A^n\to A$ is an element of for each between and .
for every 0-ary operator symbol $c\in O$ , the corresponding element $c_A\in A$ is an element of .
for any -ary operator $\omega_A$ on , and any $p_1,\ldots,p_m\in S$ , the function $\omega_A(p_1,\ldots,p_m):A^n\to A$ , given by
$\displaystyle \omega_A(p_1,\ldots,p_m)(a_1,\ldots,a_n):=\omega_A(p_1(a_1,\ldots,a_n),\ldots, p_m(a_1,\ldots,a_n))$
is an element of .

Take the intersection of all such sets and call it $% latex2html id marker 520 $ \textbf{P}_n(A)$$ . Then $% latex2html id marker 522 $ \textbf{P}_n(A)$$ is the smallest set satisfying the above two conditions. We call an element of $% latex2html id marker 524 $ \textbf{P}_n(A)$$ an

-ary polynomial of the algebra

. A polynomial of

is some

-ary polynomial of

. Two polynomials

are said to be equivalent if they have the same arity

, and for any $% latex2html id marker 540 $ \textbf{a}\in A^n$$ , $% latex2html id marker 542 $ p(\textbf{a})=q(\textbf{a})$$ .

Examples.

Let be a group. Then is a unary polynomial. In general, a unary polynomial of has the form , $n\ge 1$ . For a binary polynomial, first note that and are both binary. For this, a binary polynomial of looks like
$\displaystyle x^{n_1}y^{m_1}\cdots x^{n_k}y^{m_k},$
where $n_1,m_k\ge 0$ and the rest are positive integers. If is abelian, a binary polynomial has the simplified form , and more generally, an -ary polynomial of an abelian group has the form
$\displaystyle x_1^{n_1}\cdots x_k^{n_k}.$
Let be a ring. is a unary polynomial, so are and where are non-negative integers. In general, a unary polynomial of looks like
$\displaystyle n_mx^{m}+n_{m-1}x^{m-1}+\cdots + n_1x+n_0,$
where are non-negative integers with , and 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,
$\displaystyle a_mx^{m}+a_{m-1}x^{m-1}+\cdots + a_1x+a_0$
where $a_i\in R$ is in general not a polynomial under this definition. This is an example of an algebraic function in an algebraic system.

Remarks.

$% latex2html id marker 596 $ \textbf{P}_0(A)$$ is non-empty iff contains constant symbols (nullary function symbols).
By virtue of the definition, $% latex2html id marker 600 $ \textbf{P}_n(A)$$ is an algebraic system for each non-negative integer .

Polynomial Symbols

If we have two algebras

of the same type, then, by the definition above, a polynomial of

may be considered as a polynomial of

, and vice versa. Putting this formally, we introduce polynomial symbols for a class

of algebras of the same type

. Let $X=\lbrace x_1,x_2,\ldots\rbrace$ be a countably infinite set of variables, or symbols. For any non-negative integer

, consider a set

consisting of the following elements:

$x_1,\ldots,x_n$ ,
every nullary operator symbol,
if $\omega\in O$ is -ary and $p_1,\ldots,p_m\in S$ , then $\omega(p_1, \ldots, p_m)\in S$ .

Take the intersection of all such sets and we end up with a set satisfying the two conditions again, call it $% latex2html id marker 631 $ \textbf{P}_n(O)$$ . Any element of $% latex2html id marker 633 $ \textbf{P}_n(O)$$ is called an

-ary polynomial symbol of

. A polynomial symbol of

is just some

-ary polynomial symbol. In model theory, a polynomial symbol is nothing more than a term over

in the

-language.

Now, suppose $A\in K$ . For a given non-negative integer , consider the function $% latex2html id marker 651 $ f_A:\textbf{P}_n(O)\to \textbf{P}_n(A)$$ , defined recursively by

$f_A(x_i):=\pi_i$ ,
,
$f_A(\omega(p_1,\ldots,p_n)):=\omega_A(f_A(p_1),\ldots,f_A(p_n))$ .

Then by the constructions of $% latex2html id marker 659 $ \textbf{P}_n(O)$$ and $% latex2html id marker 661 $ \textbf{P}_n(A)$$ ,

is a surjection. Any polynomial

is said to be induced by a polynomial symbol

. We usually write

to denote that the polynomial

(of

) is induced by the polynomial symbol

(of

). 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\vee(y\wedge z)$ and $(x\vee y)\wedge (x\vee z)$ 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 $% latex2html id marker 689 $ \textbf{P}_n(A)$$ , $% latex2html id marker 691 $ \textbf{P}_n(O)$$ is also an algebraic system, called the -ary polynomial algebra, or absolutely free algebra, of . Furthermore, the function above is an algebra homomorphism.

"polynomials in algebraic systems" is owned by CWoo.

(view preamble)