Transcript An algebra without a finite basis of equations

Nonfinite basicity of one
number system with
constant
Almaz Kungozhin
Kazakh National University
PhD-student
ACCT 2012, June 15-21
Outline
•
•
•
•
•
History
Definitions
Known results
New definitions
Main result
History
• L. Zadeh, Fuzzy sets, Inform. and Control
8 (1965), 338-353.
• P. Hádjek, L. Godo, F. Esteva, A complete
many-valued logic with productconjunction. Arch. Math. Logic 35 (1996)
191-208.
• A.Kungozhin, Nonfinite basicity for a
certain number system, Algebra and
Logic, v.51, No 1, 2012, 56-65
t-norms
• Łukasiewicz (Ł) t-norm
x ∗ y = max(0, x + y − 1)
• Gödel (G) t-norm
x ∗ y = min(x, y)
• Product t-norm
x∗y=x·y
Negations
• ”Classical” fuzzy negation
¬x = 1 - x
• Godel’s negation
¬0 = 1, ¬x = 0 for x > 0
A = [0;1], ¬, , =
A1 = [0;1], ¬, , 1, =
where
[0, 1] is the segment of real numbers
¬(x) = 1 – x (negation)
x · y (ordinary product)
= – symbol of equality
1 – distinguished constant
Terms
0-complexity terms: x, y, .., x1, x2,...(,1)
If t, t1 are terms of complexity n, and
complexity of t2 is not bigger than n,
then
¬(t), (t1) ∗ (t2) and (t2) ∗ (t1)
are terms of complexity n + 1
Identity
Terms t1(x1, x2, …, xn) and t2(x1, x2, …, xn)
are identical in algebra
t1(x1, x2, …, xn) = t2(x1, x2, …, xn)
iff equation is satisfied in algebra for every
values of variables.
Remark 1. Terms are identical iff so are
their corresponding polynomials
Examples of identities
x = (x)
xy=yx
(x  y)  z = x  (y  z)
x  y = y  (x)
(x  y)  z = (y  z)  x
Basis of identities
A basis in a set of identities is its subset such
that every identity turns out to be logical
consequence of the basis.
(Birghoff’s completeness theorem 1935)
{bi(x1, x2, …, xni)= i(x1, x2, …, xni): iI}- basis
iff for any t =  it is possible to build a chain
t  t0 = t1 = ... = tk  
each following term is obtained from previous by
changing a subterm bi(1, 2, …, ni) to the
subterm i(1, 2, …, ni) (and vice versa)
Nurtazin conjecture (1997)
The basis of identities of the number
system A = [0;1], ¬, , = is
x = (x)
xy=yx
(x  y)  z = x  (y  z)
Contrary instance
(x  (y  x  y)) = (x  y)  (x  y)
since
1 – x(1 – yx(1 – y)) = 1 – x + yx2 – y 2x2
(1 – xy)  (1 – x(1 – y)) = (1 – xy)  (1 – x+ xy)
= 1 – x+ xy – xy + yx2 – y 2x2 =
= 1 – x + yx2 – y 2x2
Theorem
A system of identities in the
number system A does not have a
finite basis.
1-trivially identical terms
Two terms are 1-trivially identical (t 1) if they
can be derived from each other by substitutions
using equations (t) = t, t1  t2 = t2  t1, t1  (t2  t3)
= (t1  t2)  t3, t1  1 = t1, t1  1 = 1
Examples
x  y 1 y  (x), (x  y)  z 1 (y  z)  x
(x  (y  x  y)) = (x  y)  (x  y), but
(x  (y  x  y)) 1 (x  y)  (x  y)
1-trivial terms
A term t called A1-trivial iff any term
identical to it is A1-trivially identical to it.
Examples
Terms x, (x), (x  y) are trivial.
Terms (x  (y  x  y)), (x  y)  (x  y) are
not trivial.
Simplifying S(t)
Any A1-term can be simplified by applying
the rules (t) = t, t1  1 = t1, 1  t1 = t1, t1  1 =
1, 1  t1 = 1 for any subterm in any order
The minimal term is S(t)
Remark 1. t1  t2 = t2  t1, t1  (t2  t3) = (t1  t2)  t3 are
not used
Remark 2. S(t)  1, or S(t)  ¬1, or doesn’t contain
1’s.
Remark 3. S(t) defined correctly
Properties of S(t)
•
•
•
•
t = S(t)
t 1 if and only if S(t)  S() (1  1, ¬1 ¬1)
t is A1-trivial if and only if S(t) is trivial
If S(t) is nested (then it is trivial) then t is A1trivial
Theorem
A system of identities in the algebra
A1 = [0;1], ¬, , 1, =
does not have a finite basis.
Proof (by contradiction)
Let there is a finite basis then we add to it trivial
axioms: double negation, commutative,
associative lows and (if they are absent):
• x1=x
• x  ¬1 = ¬1
Using simplification we can 1-trivially and
equivalently reduce this basis to a basis of
identities without 1’s, and the equations x  1 = x,
x  ¬1 = ¬1, 1 = 1, ¬1 = ¬1. (Let maximal number
of variables is lesser than n).
Series of nontrivial equations
For every even positive number n
¬(x1¬(x2… ¬(xn-1¬(xnx1¬(x2…¬(xn-1¬(xn))…) =
¬(x1x2… xn-1xn)¬(x1¬(x2…¬(xn-1¬(xn))…)
is valid in the algebra A1.
Thank You for Your Attention!