:: Evaluation of Multivariate Polynomials
:: by Christoph Schwarzweller and Andrzej Trybulec
::
:: Received April 14, 2000
:: Copyright (c) 2000 Association of Mizar Users

begin

scheme :: POLYNOM2:sch 1
SeqExD{ F₁() -> non empty set , F₂() -> Element of NAT , P₁[ set , set ] } :

ex p being FinSequence of F₁() st
( dom p = Seg F₂() & ( for k being Element of NAT st k in Seg F₂() holds
P₁[k,p /. k] ) )

provided

A1: for k being Element of NAT st k in Seg F₂() holds
ex x being Element of F₁() st P₁[k,x]

proof end;

scheme :: POLYNOM2:sch 2
FinRecExD2{ F₁() -> non empty set , F₂() -> Element of F₁(), F₃() -> Element of NAT , P₁[ set , set , set ] } :

ex p being FinSequence of F₁() st
( len p = F₃() & ( p /. 1 = F₂() or F₃() = 0 ) & ( for n being Element of NAT st 1 <= n & n <= F₃() - 1 holds
P₁[n,p /. n,p /. (n + 1)] ) )

provided

A1: for n being Element of NAT st 1 <= n & n <= F₃() - 1 holds
for x being Element of F₁() ex y being Element of F₁() st P₁[n,x,y]

proof end;

scheme :: POLYNOM2:sch 3
FinRecUnD2{ F₁() -> set , F₂() -> Element of F₁(), F₃() -> Element of NAT , F₄() -> FinSequence of F₁(), F₅() -> FinSequence of F₁(), P₁[ set , set , set ] } :

F₄() = F₅()

provided

A1: for n being Element of NAT st 1 <= n & n <= F₃() - 1 holds
for x, y1, y2 being Element of F₁() st P₁[n,x,y1] & P₁[n,x,y2] holds
y1 = y2 and
A2: ( len F₄() = F₃() & ( F₄() /. 1 = F₂() or F₃() = 0 ) & ( for n being Element of NAT st 1 <= n & n <= F₃() - 1 holds
P₁[n,F₄() /. n,F₄() /. (n + 1)] ) ) and
A3: ( len F₅() = F₃() & ( F₅() /. 1 = F₂() or F₃() = 0 ) & ( for n being Element of NAT st 1 <= n & n <= F₃() - 1 holds
P₁[n,F₅() /. n,F₅() /. (n + 1)] ) )

proof end;

scheme :: POLYNOM2:sch 4
FinInd{ F₁() -> Element of NAT , F₂() -> Element of NAT , P₁[ Nat] } :

for i being Element of NAT st F₁() <= i & i <= F₂() holds
P₁[i]

provided

A1: P₁[F₁()] and
A2: for j being Element of NAT st F₁() <= j & j < F₂() & P₁[j] holds
P₁[j + 1]

proof end;

scheme :: POLYNOM2:sch 5
FinInd2{ F₁() -> Element of NAT , F₂() -> Element of NAT , P₁[ Nat] } :

for i being Element of NAT st F₁() <= i & i <= F₂() holds
P₁[i]

provided

A1: P₁[F₁()] and
A2: for j being Element of NAT st F₁() <= j & j < F₂() & ( for j' being Element of NAT st F₁() <= j' & j' <= j holds
P₁[j'] ) holds
P₁[j + 1]

proof end;

Lm1: for X being set
for A being Subset of X
for O being Order of X holds
( O is_reflexive_in A & O is_antisymmetric_in A & O is_transitive_in A )

proof end;

Lm2: for X being set
for A being Subset of X
for O being Order of X st O is_connected_in X holds
O is_connected_in A

proof end;

Lm3: for X being set
for S being Subset of X
for R being Order of X st R is being_linear-order holds
R linearly_orders S

proof end;

theorem :: POLYNOM2:1

canceled;

theorem Th2: :: POLYNOM2:2

for L being non empty unital associative multMagma
for a being Element of L
for n, m being Element of NAT holds (power L) . a,(n + m) = ((power L) . a,n) * ((power L) . a,m)

proof end;

registration

cluster non empty non trivial right_complementable associative commutative Abelian add-associative right_zeroed well-unital distributive doubleLoopStr ;
existence
ex b₁ being non empty doubleLoopStr st
( b₁ is Abelian & b₁ is right_zeroed & b₁ is add-associative & b₁ is right_complementable & b₁ is well-unital & b₁ is distributive & b₁ is commutative & b₁ is associative & not b₁ is trivial )

proof end;

end;

begin

theorem :: POLYNOM2:3

canceled;

theorem Th4: :: POLYNOM2:4

for p being FinSequence
for k being Element of NAT st k in dom p holds
for i being Element of NAT st 1 <= i & i <= k holds
i in dom p

proof end;

Lm4: for X being set
for A being finite Subset of X
for a being Element of X
for R being Order of X st R linearly_orders {a} \/ A holds
R linearly_orders A

proof end;

theorem Th5: :: POLYNOM2:5

for L being non empty right_zeroed left_zeroed addLoopStr
for p being FinSequence of the carrier of L
for i being Element of NAT st i in dom p & ( for i' being Element of NAT st i' in dom p & i' <> i holds
p /. i' = 0. L ) holds
Sum p = p /. i

proof end;

theorem :: POLYNOM2:6

for L being non empty right_complementable add-associative right_zeroed well-unital distributive doubleLoopStr
for p being FinSequence of the carrier of L st ex i being Element of NAT st
( i in dom p & p /. i = 0. L ) holds
Product p = 0. L

proof end;

theorem Th7: :: POLYNOM2:7

for L being non empty Abelian add-associative addLoopStr
for a being Element of L
for p, q being FinSequence of the carrier of L st len p = len q & ex i being Element of NAT st
( i in dom p & q /. i = a + (p /. i) & ( for i' being Element of NAT st i' in dom p & i' <> i holds
q /. i' = p /. i' ) ) holds
Sum q = a + (Sum p)

proof end;

theorem Th8: :: POLYNOM2:8

for L being non empty associative commutative doubleLoopStr
for a being Element of L
for p, q being FinSequence of the carrier of L st len p = len q & ex i being Element of NAT st
( i in dom p & q /. i = a * (p /. i) & ( for i' being Element of NAT st i' in dom p & i' <> i holds
q /. i' = p /. i' ) ) holds
Product q = a * (Product p)

proof end;

theorem Th9: :: POLYNOM2:9

for X being set
for A being empty Subset of X
for R being Order of X st R linearly_orders A holds
SgmX R,A = {}

proof end;

theorem Th10: :: POLYNOM2:10

for X being set
for A being finite Subset of X
for R being Order of X st R linearly_orders A holds
for i, j being Element of NAT st i in dom (SgmX R,A) & j in dom (SgmX R,A) & (SgmX R,A) /. i = (SgmX R,A) /. j holds
i = j

proof end;

Lm5: for D being set
for p being FinSequence of D st dom p <> {} holds
1 in dom p

proof end;

theorem Th11: :: POLYNOM2:11

for X being set
for A being finite Subset of X
for a being Element of X st not a in A holds
for B being finite Subset of X st B = {a} \/ A holds
for R being Order of X st R linearly_orders B holds
for k being Element of NAT st k in dom (SgmX R,B) & (SgmX R,B) /. k = a holds
for i being Element of NAT st 1 <= i & i <= k - 1 holds
(SgmX R,B) /. i = (SgmX R,A) /. i

proof end;

theorem Th12: :: POLYNOM2:12

for X being set
for A being finite Subset of X
for a being Element of X st not a in A holds
for B being finite Subset of X st B = {a} \/ A holds
for R being Order of X st R linearly_orders B holds
for k being Element of NAT st k in dom (SgmX R,B) & (SgmX R,B) /. k = a holds
for i being Element of NAT st k <= i & i <= len (SgmX R,A) holds
(SgmX R,B) /. (i + 1) = (SgmX R,A) /. i

proof end;

theorem Th13: :: POLYNOM2:13

for X being non empty set
for A being finite Subset of X
for a being Element of X st not a in A holds
for B being finite Subset of X st B = {a} \/ A holds
for R being Order of X st R linearly_orders B holds
for k being Element of NAT st k + 1 in dom (SgmX R,B) & (SgmX R,B) /. (k + 1) = a holds
SgmX R,B = Ins (SgmX R,A),k,a

proof end;

begin

theorem Th14: :: POLYNOM2:14

for X being set
for b being bag of X st support b = {} holds
b = EmptyBag X

proof end;

Lm6: for X being set
for b being bag of X holds b is PartFunc of X,NAT

proof end;

definition

let X be set ;
let b be bag of X;
attr b is empty means :Def1: :: POLYNOM2:def 1
b = EmptyBag X;

end;

:: deftheorem Def1 defines empty POLYNOM2:def 1 :

for X being set
for b being bag of X holds
( b is empty iff b = EmptyBag X );

registration

let X be non empty set ;
cluster non empty set ;
existence
not for b₁ being bag of X holds b₁ is empty

proof end;

end;

definition

let X be set ;
let b be bag of X;
:: original: support
redefine func support b -> finite Subset of X;
coherence
support b is finite Subset of X

proof end;

end;

theorem Th15: :: POLYNOM2:15

for n being Ordinal
for b being bag of n holds RelIncl n linearly_orders support b

proof end;

definition

let X be set ;
let x be FinSequence of X;
let b be bag of X;
:: original: *
redefine func b * x -> PartFunc of NAT ,NAT ;
coherence
x * b is PartFunc of NAT ,NAT

proof end;

end;

definition

let n be Ordinal;
let b be bag of n;
let L be non empty non trivial well-unital doubleLoopStr ;
let x be Function of n,L;
func eval b,x -> Element of L means :Def2: :: POLYNOM2:def 2
ex y being FinSequence of the carrier of L st
( len y = len (SgmX (RelIncl n),(support b)) & it = Product y & ( for i being Element of NAT st 1 <= i & i <= len y holds
y /. i = (power L) . ((x * (SgmX (RelIncl n),(support b))) /. i),((b * (SgmX (RelIncl n),(support b))) /. i) ) );
existence
ex b₁ being Element of L ex y being FinSequence of the carrier of L st
( len y = len (SgmX (RelIncl n),(support b)) & b₁ = Product y & ( for i being Element of NAT st 1 <= i & i <= len y holds
y /. i = (power L) . ((x * (SgmX (RelIncl n),(support b))) /. i),((b * (SgmX (RelIncl n),(support b))) /. i) ) )

proof end;

uniqueness
for b₁, b₂ being Element of L st ex y being FinSequence of the carrier of L st
( len y = len (SgmX (RelIncl n),(support b)) & b₁ = Product y & ( for i being Element of NAT st 1 <= i & i <= len y holds
y /. i = (power L) . ((x * (SgmX (RelIncl n),(support b))) /. i),((b * (SgmX (RelIncl n),(support b))) /. i) ) ) & ex y being FinSequence of the carrier of L st
( len y = len (SgmX (RelIncl n),(support b)) & b₂ = Product y & ( for i being Element of NAT st 1 <= i & i <= len y holds
y /. i = (power L) . ((x * (SgmX (RelIncl n),(support b))) /. i),((b * (SgmX (RelIncl n),(support b))) /. i) ) ) holds
b₁ = b₂

proof end;

end;

:: deftheorem Def2 defines eval POLYNOM2:def 2 :

for n being Ordinal
for b being bag of n
for L being non empty non trivial well-unital doubleLoopStr
for x being Function of n,L
for b₅ being Element of L holds
( b₅ = eval b,x iff ex y being FinSequence of the carrier of L st
( len y = len (SgmX (RelIncl n),(support b)) & b₅ = Product y & ( for i being Element of NAT st 1 <= i & i <= len y holds
y /. i = (power L) . ((x * (SgmX (RelIncl n),(support b))) /. i),((b * (SgmX (RelIncl n),(support b))) /. i) ) ) );

Lm7: for X being set holds support (EmptyBag X) = {}

proof end;

theorem Th16: :: POLYNOM2:16

for n being Ordinal
for L being non empty non trivial well-unital doubleLoopStr
for x being Function of n,L holds eval (EmptyBag n),x = 1. L

proof end;

theorem Th17: :: POLYNOM2:17

for n being Ordinal
for L being non empty non trivial well-unital doubleLoopStr
for u being set
for b being bag of n st support b = {u} holds
for x being Function of n,L holds eval b,x = (power L) . (x . u),(b . u)

proof end;

Lm8: for n being Ordinal
for L being non empty non trivial right_complementable associative commutative add-associative right_zeroed well-unital distributive doubleLoopStr
for b1, b2 being bag of n
for u being set st not u in support b1 & support b2 = (support b1) \/ {u} & ( for u' being set st u' <> u holds
b2 . u' = b1 . u' ) holds
for x being Function of n,L
for a being Element of L st a = (power L) . (x . u),(b2 . u) holds
eval b2,x = a * (eval b1,x)

proof end;

Lm9: for n being Ordinal
for L being non empty non trivial right_complementable associative commutative Abelian add-associative right_zeroed well-unital distributive doubleLoopStr
for b1 being bag of n st ex u being set st support b1 = {u} holds
for b2 being bag of n
for x being Function of n,L holds eval (b1 + b2),x = (eval b1,x) * (eval b2,x)

proof end;

theorem Th18: :: POLYNOM2:18

for n being Ordinal
for L being non empty non trivial right_complementable associative commutative Abelian add-associative right_zeroed well-unital distributive doubleLoopStr
for b1, b2 being bag of n
for x being Function of n,L holds eval (b1 + b2),x = (eval b1,x) * (eval b2,x)

proof end;

begin

registration

let n be Ordinal;
let L be non empty right_complementable add-associative right_zeroed addLoopStr ;
let p, q be Polynomial of n,L;
cluster p - q -> finite-Support ;
coherence
p - q is finite-Support

proof end;

end;

theorem Th19: :: POLYNOM2:19

for L being non empty non trivial right_complementable add-associative right_zeroed well-unital distributive doubleLoopStr
for n being Ordinal
for p being Polynomial of n,L st Support p = {} holds
p = 0_ n,L

proof end;

registration

let n be Ordinal;
let L be non empty non trivial right_complementable add-associative right_zeroed well-unital distributive doubleLoopStr ;
let p be Polynomial of n,L;
cluster Support p -> finite ;
coherence
Support p is finite by POLYNOM1:def 10;

end;

theorem Th20: :: POLYNOM2:20

for n being Ordinal
for L being non empty non trivial right_complementable add-associative right_zeroed well-unital distributive doubleLoopStr
for p being Polynomial of n,L holds BagOrder n linearly_orders Support p

proof end;

definition

let n be Ordinal;
let b be Element of Bags n;
func b @ -> bag of n equals :: POLYNOM2:def 3
b;
correctness
coherence
b is bag of n;
;

end;

:: deftheorem defines @ POLYNOM2:def 3 :

for n being Ordinal
for b being Element of Bags n holds b @ = b;

definition

let n be Ordinal;
let L be non empty non trivial right_complementable add-associative right_zeroed well-unital distributive doubleLoopStr ;
let p be Polynomial of n,L;
let x be Function of n,L;
func eval p,x -> Element of L means :Def4: :: POLYNOM2:def 4
ex y being FinSequence of the carrier of L st
( len y = len (SgmX (BagOrder n),(Support p)) & it = Sum y & ( for i being Element of NAT st 1 <= i & i <= len y holds
y /. i = ((p * (SgmX (BagOrder n),(Support p))) /. i) * (eval (((SgmX (BagOrder n),(Support p)) /. i) @ ),x) ) );
existence
ex b₁ being Element of L ex y being FinSequence of the carrier of L st
( len y = len (SgmX (BagOrder n),(Support p)) & b₁ = Sum y & ( for i being Element of NAT st 1 <= i & i <= len y holds
y /. i = ((p * (SgmX (BagOrder n),(Support p))) /. i) * (eval (((SgmX (BagOrder n),(Support p)) /. i) @ ),x) ) )

proof end;

uniqueness
for b₁, b₂ being Element of L st ex y being FinSequence of the carrier of L st
( len y = len (SgmX (BagOrder n),(Support p)) & b₁ = Sum y & ( for i being Element of NAT st 1 <= i & i <= len y holds
y /. i = ((p * (SgmX (BagOrder n),(Support p))) /. i) * (eval (((SgmX (BagOrder n),(Support p)) /. i) @ ),x) ) ) & ex y being FinSequence of the carrier of L st
( len y = len (SgmX (BagOrder n),(Support p)) & b₂ = Sum y & ( for i being Element of NAT st 1 <= i & i <= len y holds
y /. i = ((p * (SgmX (BagOrder n),(Support p))) /. i) * (eval (((SgmX (BagOrder n),(Support p)) /. i) @ ),x) ) ) holds
b₁ = b₂

proof end;

end;

:: deftheorem Def4 defines eval POLYNOM2:def 4 :

for n being Ordinal
for L being non empty non trivial right_complementable add-associative right_zeroed well-unital distributive doubleLoopStr
for p being Polynomial of n,L
for x being Function of n,L
for b₅ being Element of L holds
( b₅ = eval p,x iff ex y being FinSequence of the carrier of L st
( len y = len (SgmX (BagOrder n),(Support p)) & b₅ = Sum y & ( for i being Element of NAT st 1 <= i & i <= len y holds
y /. i = ((p * (SgmX (BagOrder n),(Support p))) /. i) * (eval (((SgmX (BagOrder n),(Support p)) /. i) @ ),x) ) ) );

theorem Th21: :: POLYNOM2:21

for n being Ordinal
for L being non empty non trivial right_complementable add-associative right_zeroed well-unital distributive doubleLoopStr
for p being Polynomial of n,L
for b being bag of n st Support p = {b} holds
for x being Function of n,L holds eval p,x = (p . b) * (eval b,x)

proof end;

theorem Th22: :: POLYNOM2:22

for n being Ordinal
for L being non empty non trivial right_complementable add-associative right_zeroed well-unital distributive doubleLoopStr
for x being Function of n,L holds eval (0_ n,L),x = 0. L

proof end;

theorem Th23: :: POLYNOM2:23

for n being Ordinal
for L being non empty non trivial right_complementable add-associative right_zeroed well-unital distributive doubleLoopStr
for x being Function of n,L holds eval (1_ n,L),x = 1. L

proof end;

theorem Th24: :: POLYNOM2:24

for n being Ordinal
for L being non empty non trivial right_complementable add-associative right_zeroed well-unital distributive doubleLoopStr
for p being Polynomial of n,L
for x being Function of n,L holds eval (- p),x = - (eval p,x)

proof end;

Lm10: for n being Ordinal
for L being non empty non trivial right_complementable Abelian add-associative right_zeroed well-unital distributive doubleLoopStr
for p, q being Polynomial of n,L
for x being Function of n,L
for b being bag of n st not b in Support p & Support q = (Support p) \/ {b} & ( for b' being bag of n st b' <> b holds
q . b' = p . b' ) holds
eval q,x = (eval p,x) + ((q . b) * (eval b,x))

proof end;

Lm11: for n being Ordinal
for L being non empty non trivial right_complementable Abelian add-associative right_zeroed well-unital distributive doubleLoopStr
for p being Polynomial of n,L st ex b being bag of n st Support p = {b} holds
for q being Polynomial of n,L
for x being Function of n,L holds eval (p + q),x = (eval p,x) + (eval q,x)

proof end;

theorem Th25: :: POLYNOM2:25

for n being Ordinal
for L being non empty non trivial right_complementable Abelian add-associative right_zeroed well-unital distributive doubleLoopStr
for p, q being Polynomial of n,L
for x being Function of n,L holds eval (p + q),x = (eval p,x) + (eval q,x)

proof end;

theorem :: POLYNOM2:26

for n being Ordinal
for L being non empty non trivial right_complementable Abelian add-associative right_zeroed well-unital distributive doubleLoopStr
for p, q being Polynomial of n,L
for x being Function of n,L holds eval (p - q),x = (eval p,x) - (eval q,x)

proof end;

Lm12: for n being Ordinal
for L being non empty non trivial right_complementable associative commutative Abelian add-associative right_zeroed well-unital distributive doubleLoopStr
for p, q being Polynomial of n,L
for b1, b2 being bag of n st Support p = {b1} & Support q = {b2} holds
for x being Function of n,L holds eval (p *' q),x = (eval p,x) * (eval q,x)

proof end;

Lm13: for n being Ordinal
for L being non empty non trivial right_complementable associative commutative Abelian add-associative right_zeroed well-unital distributive doubleLoopStr
for q being Polynomial of n,L st ex b being bag of n st Support q = {b} holds
for p being Polynomial of n,L
for x being Function of n,L holds eval (p *' q),x = (eval p,x) * (eval q,x)

proof end;

theorem Th27: :: POLYNOM2:27

for n being Ordinal
for L being non empty non trivial right_complementable associative commutative Abelian add-associative right_zeroed well-unital distributive doubleLoopStr
for p, q being Polynomial of n,L
for x being Function of n,L holds eval (p *' q),x = (eval p,x) * (eval q,x)

proof end;

begin

definition

let n be Ordinal;
let L be non empty non trivial right_complementable add-associative right_zeroed well-unital distributive doubleLoopStr ;
let x be Function of n,L;
func Polynom-Evaluation n,L,x -> Function of (Polynom-Ring n,L),L means :Def5: :: POLYNOM2:def 5
for p being Polynomial of n,L holds it . p = eval p,x;
existence
ex b₁ being Function of (Polynom-Ring n,L),L st
for p being Polynomial of n,L holds b₁ . p = eval p,x

proof end;

uniqueness
for b₁, b₂ being Function of (Polynom-Ring n,L),L st ( for p being Polynomial of n,L holds b₁ . p = eval p,x ) & ( for p being Polynomial of n,L holds b₂ . p = eval p,x ) holds
b₁ = b₂

proof end;

end;

:: deftheorem Def5 defines Polynom-Evaluation POLYNOM2:def 5 :

for n being Ordinal
for L being non empty non trivial right_complementable add-associative right_zeroed well-unital distributive doubleLoopStr
for x being Function of n,L
for b₄ being Function of (Polynom-Ring n,L),L holds
( b₄ = Polynom-Evaluation n,L,x iff for p being Polynomial of n,L holds b₄ . p = eval p,x );

registration

let n be Ordinal;
let L be non empty non trivial right_complementable associative Abelian add-associative right_zeroed well-unital distributive doubleLoopStr ;
cluster Polynom-Ring n,L -> well-unital ;
coherence
Polynom-Ring n,L is well-unital ;

end;

registration

let n be Ordinal;
let L be non empty non trivial right_complementable associative Abelian add-associative right_zeroed well-unital distributive doubleLoopStr ;
let x be Function of n,L;
cluster Polynom-Evaluation n,L,x -> unity-preserving ;
coherence
Polynom-Evaluation n,L,x is unity-preserving

proof end;

end;

registration

let n be Ordinal;
let L be non empty non trivial right_complementable Abelian add-associative right_zeroed well-unital distributive doubleLoopStr ;
let x be Function of n,L;
cluster Polynom-Evaluation n,L,x -> additive ;
coherence
Polynom-Evaluation n,L,x is additive

proof end;

end;

registration

let n be Ordinal;
let L be non empty non trivial right_complementable associative commutative Abelian add-associative right_zeroed well-unital distributive doubleLoopStr ;
let x be Function of n,L;
cluster Polynom-Evaluation n,L,x -> multiplicative ;
coherence
Polynom-Evaluation n,L,x is multiplicative

proof end;

end;

registration

let n be Ordinal;
let L be non empty non trivial right_complementable associative commutative Abelian add-associative right_zeroed well-unital distributive doubleLoopStr ;
let x be Function of n,L;
cluster Polynom-Evaluation n,L,x -> RingHomomorphism ;
coherence
Polynom-Evaluation n,L,x is RingHomomorphism

proof end;

end;