Editing Kleene algebra (section)

== Properties ==

Zero is the smallest element: 0 ≤ ''a'' for all ''a'' in ''A''.

The sum ''a'' + ''b'' is the [[least upper bound]] of ''a'' and ''b'': we have ''a'' ≤ ''a'' + ''b'' and ''b'' ≤ ''a'' + ''b'' and if ''x'' is an element of ''A'' with ''a'' ≤ ''x'' and ''b'' ≤ ''x'', then ''a'' + ''b'' ≤ ''x''. Similarly, ''a''<sub>1</sub> + ... + ''a''<sub>''n''</sub> is the least upper bound of the elements ''a''<sub>1</sub>, ..., ''a''<sub>''n''</sub>.

Multiplication and addition are monotonic: if ''a'' ≤ ''b'', then 
* ''a'' + ''x'' ≤ ''b'' + ''x'', 
* ''ax'' ≤ ''bx'', and 
* ''xa'' ≤ ''xb'' 
for all ''x'' in ''A''.

Regarding the star operation, we have 
* 0<sup>*</sup> = 1 and 1<sup>*</sup> = 1, 
* ''a'' ≤ ''b'' implies ''a''<sup>*</sup> ≤ ''b''<sup>*</sup> (monotonicity),
* ''a''<sup>''n''</sup> ≤ ''a''<sup>*</sup> for every [[natural number]] ''n'', where ''a''<sup>''n''</sup> is defined as ''n''-fold multiplication of ''a'',
* (''a''<sup>*</sup>)(''a''<sup>*</sup>) = ''a''<sup>*</sup>,
* (''a''<sup>*</sup>)<sup>*</sup> = ''a''<sup>*</sup>, 
* 1 + ''a''(''a''<sup>*</sup>) = ''a''<sup>*</sup> = 1 + (''a''<sup>*</sup>)''a'', 
* ''ax'' = ''xb'' implies (''a''<sup>*</sup>)''x'' = ''x''(''b''<sup>*</sup>),
* ((''ab'')<sup>*</sup>)''a'' = ''a''((''ba'')<sup>*</sup>),
* (''a''+''b'')<sup>*</sup> = ''a''<sup>*</sup>(''b''(''a''<sup>*</sup>))<sup>*</sup>, and
* ''pq'' = 1 = ''qp'' implies ''q''(''a''<sup>*</sup>)''p'' = (''qap'')<sup>*</sup>.<ref>Kozen (1990), sect.2.1.2, p.5</ref>

If ''A'' is a Kleene algebra and ''n'' is a natural number, then one can consider the set M<sub>''n''</sub>(''A'') consisting of all ''n''-by-''n'' [[matrix (mathematics)|matrices]] with entries in ''A''.
Using the ordinary notions of matrix addition and multiplication, one can define a unique <sup>*</sup>-operation so that M<sub>''n''</sub>(''A'') becomes a Kleene algebra.