let F be Field; :: thesis:
let E be FieldExtension of F; :: thesis:
let a be Element of E; :: thesis:
let n be Element of NAT ; :: thesis:
let M be Subset of (VecSp (E,F)); :: thesis:
assume AS1: ( M = { (a |^ i) where i is Element of NAT : i <= n } & ( for i, j being Element of NAT st i < j & j <= n holds
a |^ i <> a |^ j ) ) ; :: thesis:
let l be Linear_Combination of M; :: thesis:
let p be Polynomial of F; :: thesis:
assume AS2: ( deg p <= n & ( for i being Element of NAT st i <= n holds
p . i = l . (a |^ i) ) ) ; :: thesis:
set V = VecSp (E,F);
defpred S₁[ Nat] means for l being Linear_Combination of M st card (Carrier l) = $1 holds
for p being Polynomial of F st deg p <= n & ( for i being Element of NAT st i <= n holds
p . i = l . (a |^ i) ) holds
Sum l = Ext_eval (p,a);
IA: S₁[ 0 ]

let l be Linear_Combination of M; :: thesis:
assume card (Carrier l) = 0 ; :: thesis:
then Carrier l = {} ;
then A2: l = ZeroLC (VecSp (E,F)) by VECTSP_6:def 3;
let p be Polynomial of F; :: thesis:
assume A4: ( deg p <= n & ( for i being Element of NAT st i <= n holds
p . i = l . (a |^ i) ) ) ; :: thesis:

let i be Element of NAT ; :: thesis:

per cases ;

suppose i > n ; :: thesis:

then A5: i > deg p by A4, XXREAL_0:2;
deg p = (len p) - 1 by HURWITZ:def 2;
then i + 1 > ((len p) - 1) + 1 by A5, XREAL_1:6;
hence p . i = (0_. F) . i by NAT_1:13, ALGSEQ_1:8; :: thesis:

end;

suppose A5: i <= n ; :: thesis:

then a |^ i in M by AS1;
then reconsider v = a |^ i as Element of (VecSp (E,F)) ;
thus p . i = l . v by A4, A5
.= (0_. F) . i by A2, VECTSP_6:3 ; :: thesis:

end;

then p = 0_. F ;
hence Ext_eval (p,a) = 0. E by ALGNUM_1:13
.= 0. (VecSp (E,F)) by FIELD_4:def 6
.= Sum l by A2, VECTSP_6:15 ;
:: thesis:

end;

IS: now :: thesis:

let k be Nat; :: thesis:
assume B0: S₁[k] ; :: thesis:

now :: thesis:

let l be Linear_Combination of M; :: thesis:
assume B1: card (Carrier l) = k + 1 ; :: thesis:
let pp be Polynomial of F; :: thesis:
assume B2: ( deg pp <= n & ( for i being Element of NAT st i <= n holds
pp . i = l . (a |^ i) ) ) ; :: thesis:

now :: thesis:

assume C0: pp = 0_. F ; :: thesis:

now :: thesis:

let o be object ; :: thesis:
assume C1: o in Carrier l ; :: thesis:
Carrier l c= M by VECTSP_6:def 4;
then o in M by C1;
then consider i being Element of NAT such that
C2: ( o = a |^ i & i <= n ) by AS1;
l . (a |^ i) = pp . i by B2, C2
.= 0. F by C0 ;
hence contradiction by C1, C2, VECTSP_6:2; :: thesis:

end;

then Carrier l = {} by XBOOLE_0:def 1;
hence contradiction by B1; :: thesis:

end;

then reconsider p = pp as non zero Polynomial of F by UPROOTS:def 5;
defpred S₂[ object , object ] means ( ( $1 = a |^ (deg p) & $2 = LC p ) or ( $1 <> a |^ (deg p) & $2 = 0. F ) );
A: for x being object st x in the carrier of (VecSp (E,F)) holds
ex y being object st
( y in the carrier of F & S₂[x,y] )

proof

let x be object ; :: thesis:
assume x in the carrier of (VecSp (E,F)) ; :: thesis:

per cases ;

suppose x = a |^ (deg p) ; :: thesis:

hence ex y being object st
( y in the carrier of F & S₂[x,y] ) ; :: thesis:

end;

suppose x <> a |^ (deg p) ; :: thesis:

hence ex y being object st
( y in the carrier of F & S₂[x,y] ) ; :: thesis:

end;

consider lp being Function of the carrier of (VecSp (E,F)), the carrier of F such that
L: for x being object st x in the carrier of (VecSp (E,F)) holds
S₂[x,lp . x] from FUNCT_2:sch 1(A);
reconsider lp = lp as Element of Funcs ( the carrier of (VecSp (E,F)), the carrier of F) by FUNCT_2:8;
U: M is finite

proof

deffunc H₁( Nat) -> Element of the carrier of E = a |^ $1;
defpred S₃[ Nat] means $1 <= n;
D: { H₁(i) where i is Nat : ( i <= n & S₃[i] ) } is finite from FINSEQ_1:sch 6();

E: now :: thesis:

let o be object ; :: thesis:
assume o in { H₁(i) where i is Nat : ( i <= n & S₃[i] ) } ; :: thesis:
then consider i being Nat such that
E1: ( o = a |^ i & i <= n & i <= n ) ;
i is Element of NAT by ORDINAL1:def 12;
hence o in M by E1, AS1; :: thesis:

end;

now :: thesis:

let o be object ; :: thesis:
assume o in M ; :: thesis:
then consider i being Element of NAT such that
E1: ( o = a |^ i & i <= n ) by AS1;
thus o in { H₁(i) where i is Nat : ( i <= n & S₃[i] ) } by E1; :: thesis:

end;

hence M is finite by D, E, TARSKI:2; :: thesis:

end;

for v being Element of (VecSp (E,F)) st not v in M holds
lp . v = 0. F

proof

let v be Element of (VecSp (E,F)); :: thesis:
assume not v in M ; :: thesis:
then v <> a |^ (deg p) by B2, AS1;
hence lp . v = 0. F by L; :: thesis:

end;

then reconsider lp = lp as Linear_Combination of VecSp (E,F) by U, VECTSP_6:def 1;

now :: thesis:

let o be object ; :: thesis:
assume o in Carrier lp ; :: thesis:
then consider v being Element of (VecSp (E,F)) such that
A1: ( o = v & lp . v <> 0. F ) by VECTSP_6:1;
( v = a |^ (deg p) & lp . v = LC p ) by L, A1;
hence o in M by A1, B2, AS1; :: thesis:

end;

then Carrier lp c= M ;
then reconsider lp = lp as Linear_Combination of M by VECTSP_6:def 4;
X1: {a} is Subset of (FAdj (F,{a})) by FAt;
a in {a} by TARSKI:def 1;
then reconsider a1 = a as Element of the carrier of (FAdj (F,{a})) by X1;
X: a |^ (deg p) is Element of (VecSp (E,F)) by FIELD_4:def 6;
C0: Carrier lp = {(a |^ (deg p))}

proof

C2: now :: thesis:

let o be object ; :: thesis:
assume o in {(a |^ (deg p))} ; :: thesis:
then C3: o = a |^ (deg p) by TARSKI:def 1;
then lp . o <> 0. F by X, L;
hence o in Carrier lp by X, C3, VECTSP_6:2; :: thesis:

end;

now :: thesis:

let o be object ; :: thesis:
assume C3: o in Carrier lp ; :: thesis:
Carrier lp = { v where v is Element of (VecSp (E,F)) : lp . v <> 0. F } by VECTSP_6:def 2;
then consider v being Element of (VecSp (E,F)) such that
C4: ( o = v & lp . v <> 0. F ) by C3;
o = a |^ (deg p) by C4, L;
hence o in {(a |^ (deg p))} by TARSKI:def 1; :: thesis:

end;

hence Carrier lp = {(a |^ (deg p))} by C2, TARSKI:2; :: thesis:

end;

lp . (a |^ (deg p)) = LC p by X, L;
then C: Ext_eval ((LM p),a) = Sum lp by C0, lembasx1a;
set q = p - (LM p);
reconsider lk = l - lp as Linear_Combination of M by VECTSP_6:42;
C2: l = lk + lp

proof

thus lk + lp = (l + (- lp)) + lp by VECTSP_6:def 11
.= l + ((- lp) + lp) by VECTSP_6:26
.= l + (lp + (- lp)) by VECTSP_6:25
.= l + (lp - lp) by VECTSP_6:def 11
.= l + (ZeroLC (VecSp (E,F))) by VECTSP_6:43
.= l by VECTSP_6:27 ; :: thesis:

end;

C3: Carrier lk = (Carrier l) \ (Carrier lp)

proof

C4: now :: thesis:

let o be object ; :: thesis:
assume o in Carrier lk ; :: thesis:
then consider v being Element of (VecSp (E,F)) such that
C5: ( o = v & lk . v <> 0. F ) by VECTSP_6:1;

C6: now :: thesis:

assume C7: v = a |^ (deg p) ; :: thesis:
then C9: l . v = p . (deg p) by B2
.= LC p by thLC ;
lk . v = (l . v) - (lp . v) by VECTSP_6:40
.= (LC p) - (LC p) by L, C7, C9 ;
hence contradiction by C5, RLVECT_1:15; :: thesis:

end;

then C7: not v in Carrier lp by C0, TARSKI:def 1;
lk . v = (l . v) - (lp . v) by VECTSP_6:40
.= (l . v) - (0. F) by C6, L ;
then v in Carrier l by C5, VECTSP_6:2;
hence o in (Carrier l) \ (Carrier lp) by C7, C5, XBOOLE_0:def 5; :: thesis:

end;

now :: thesis:

let o be object ; :: thesis:
assume o in (Carrier l) \ (Carrier lp) ; :: thesis:
then C5: ( o in Carrier l & not o in Carrier lp ) by XBOOLE_0:def 5;
then consider v being Element of (VecSp (E,F)) such that
C6: ( o = v & l . v <> 0. F ) by VECTSP_6:1;
C7: o <> a |^ (deg p) by C0, C5, TARSKI:def 1;
lk . v = (l . v) - (lp . v) by VECTSP_6:40
.= (l . v) - (0. F) by C6, C7, L ;
hence o in Carrier lk by C6, VECTSP_6:1; :: thesis:

end;

hence Carrier lk = (Carrier l) \ (Carrier lp) by C4, TARSKI:2; :: thesis:

end;

now :: thesis:

let o be object ; :: thesis:
assume C5: o in Carrier lp ; :: thesis:
then C4: o = a |^ (deg p) by C0, TARSKI:def 1;
reconsider v = o as Element of (VecSp (E,F)) by C5;
lp . v = LC p by L, C4
.= pp . (deg p) by thLC
.= l . v by C4, B2 ;
then l . v <> 0. F by C5, VECTSP_6:2;
hence o in Carrier l by VECTSP_6:2; :: thesis:

end;

then Carrier lp c= Carrier l ;
then A: card ((Carrier l) \ (Carrier lp)) = (card (Carrier l)) - (card (Carrier lp)) by CARD_2:44
.= (k + 1) - 1 by B1, C0, CARD_2:42 ;
B: deg (p - (LM p)) < n by thdLM, B2, XXREAL_0:2;
for i being Element of NAT st i <= n holds
(p - (LM p)) . i = lk . (a |^ i)

proof

let i be Element of NAT ; :: thesis:
assume B1: i <= n ; :: thesis:
reconsider v = a |^ i as Element of (VecSp (E,F)) by FIELD_4:def 6;

per cases ;

suppose B3: i = deg p ; :: thesis:

hence (p - (LM p)) . i = (p . (deg p)) - ((LM p) . (deg p)) by POLYNOM3:27
.= (p . (deg p)) - ((LM p) . (deg (LM p))) by thdegLM
.= (l . v) - ((LM p) . (deg (LM p))) by B3, B2
.= (l . v) - (LC (LM p)) by thLC
.= (l . v) - (LC p) by thdegLC
.= (l . v) - (lp . v) by B3, L
.= lk . (a |^ i) by VECTSP_6:40 ;
:: thesis:

end;

suppose D2: i <> deg p ; :: thesis:

D3: a |^ i <> a |^ (deg p)

proof

per cases by D2, XXREAL_0:1;

suppose i < deg p ; :: thesis:

hence a |^ i <> a |^ (deg p) by B2, AS1; :: thesis:

end;

suppose i > deg p ; :: thesis:

hence a |^ i <> a |^ (deg p) by B1, AS1; :: thesis:

end;

p <> 0_. F ;
then len p <> 0 by POLYNOM4:5;
then (len p) + 1 > 0 + 1 by XREAL_1:6;
then len p >= 1 by NAT_1:13;
then D5: (len p) -' 1 = (len p) - 1 by XREAL_0:def 2;
D4: i <> (len p) -' 1 by D5, D2, HURWITZ:def 2;
thus (p - (LM p)) . i = (p . i) - ((LM p) . i) by POLYNOM3:27
.= (p . i) - (0. F) by D4, POLYNOM4:def 1
.= (l . v) - (0. F) by B2, B1
.= (l . v) - (lp . v) by D3, L
.= lk . (a |^ i) by VECTSP_6:40 ; :: thesis:

end;

then D: Ext_eval ((p - (LM p)),a) = Sum lk by A, C3, B, B0;
thus Sum l = (Sum lk) + (Sum lp) by C2, VECTSP_6:44
.= the addF of E . ((Sum lk),(Sum lp)) by FIELD_4:def 6
.= ((Ext_eval (p,a)) - (Ext_eval ((LM p),a))) + (Ext_eval ((LM p),a)) by C, D, exevalminus2
.= (Ext_eval (p,a)) + ((- (Ext_eval ((LM p),a))) + (Ext_eval ((LM p),a))) by RLVECT_1:def 3
.= (Ext_eval (p,a)) + (0. E) by RLVECT_1:5
.= Ext_eval (pp,a) ; :: thesis:

end;

hence S₁[k + 1] ; :: thesis:

end;

I: for k being Nat holds S₁[k] from NAT_1:sch 2(IA, IS);
consider n being Nat such that
H: card (Carrier l) = n ;
thus Ext_eval (p,a) = Sum l by AS2, I, H; :: thesis: