Диссертация (1104034), страница 5
Текст из файла (страница 5)
Î÷åâèäíî, ÷òî ýòî äàåò íàì ôóíêöèþ Cmpl−1 , êîòîðàÿ óäîâëåòâîðÿåò âñåì òðåáóåìûì óñëîâèÿì.Òåïåðü ìû ðàññìàòðèâàåì ñëó÷àé n ≥ 0. Ïóñòü ìû ïîëó÷èëè íàâõîä (α, c) è c = hm, A, di. Ìû âîçâðàùàåì ðåçóëüòàò Cmpln (α, c) =hm, A, ei, ãäå e êîíå÷íàÿ ïîñëåäîâàòåëüíîñòü (e0 , . . . , em−1 ), è äëÿâñåõ i<m èìååì ei=Cmpln−1 (`(Ai ), di ). Ýòî äàåò íàì âû-÷èñëèìóþ ôóíêöèþ Cmpln . Î÷åâèäíî, ocnα (Cmpln (α, c)) = ocnα (c) èwαn (Cmpln (α, c)) = wαn (d).
Ïîêàæåì, ÷òî evnα (Cmpln (α, c)) = Uαn \ evnα (c).Ðàññìîòðèì ìèð (β0 , β1 , . . . , βn ) ∈ Uαn . Ìû íàõîäèì åäèíñòâåííîå ÷èñëî i òàêîå, ÷òî β0 ∈ Ai . Ìû èìååì β1 < `(Ai ) è, ñëåäîâàòåëü-íî, (β1 , . . . , βn ) ∈ U`(n−1Ai ) . Èç ïðåäïîëîæåíèÿ èíäóêöèè ìû çíàåì, ÷òî(β1 , . . . , βn ) ∈ evn`(−1Ai ) (Cmpln (`(Ai ), di )) åñëè è òîëüêî åñëè (β1 , . .
. , βn ) ∈n−1nU`(n−1Ai ) \ ev`(Ai ) (di ). Òàêèì îáðàçîì, (β0 , . . . , βn ) ∈ evα (Cmpln (α, c)) â òîìè òîëüêî òîì ñëó÷àå, åñëè (β0 , . . . , βn ) ∈ Uαn \ evnα (c). Ñëåäîâàòåëüíî,evnα (Cmpln (α, c)) = Uαn \ evnα (c). Èç ïðåäïîëîæåíèÿ èíäóêöèè è ëåììû281.9 ìû ïîëó÷àåì, ÷òî äëÿ Cmpln âûïîëíÿåòñÿ âåðõíÿÿ îöåíêà íà âðåìÿðàáîòû 4.Î÷åâèäíî, èìåþò ìåñòî ñëåäóþùèå ëåììû:Ëåììà 1.13.Ñóùåñòâóåò âû÷èñëèìàÿ ôóíêöèÿ EmpSn (α) òàêàÿ, ÷òîíà îðäèíàëå α > 0 îíà çà âðåìÿ O(c(α)) âîçâðàùàåò êîä c ∈ Cnα òàêîé,÷òî evnα (c) = ∅, ocnα (c) = n è wαn (c) = 1.Ëåììà 1.14.Åñëè n ≥ 0, òî èìååòñÿ âû÷èñëèìàÿ ôóíêöèÿ Infn (α, c)òàêàÿ, ÷òî íà àðãóìåíòàõ 0 < α < ε0 è c ∈ Cnα , evnα (c) 6= ∅:1. Infn (α, c) ÿâëÿåòñÿ îðäèíàëîì;2.
Infn (α, c) = inf{γ0 | ∃γ1 , . . . , γn ((γ0 , . . . , γn ) ∈ evnα (c))};3. c(Infn (α, c)) ≤ oc(c);4. Infn íà âõîäå (α, c) èìååò âðåìÿ ðàáîòû îöåíèâàåìîå ñâåðõó, êàêO(max(ocnα (c), c(α)) · (wαn (c))n ).Äîêàçàòåëüñòâî. Èäåÿ ïîñòðîåíèÿ ôóíêöèè Infn (α, hm, A, di), ãäå n >0, ñîñòîèò â íàõîæäåíèè ïåðâîãî Ai ñ íåïóñòûì evn`(−1Ai ) (di ) è çàòåì âû÷èñëåíèèinf{γ0 | ∃γ1 , . . . , γn ((γ0 , . .
. , γn ) ∈ evnα (hm, A, di))},èñïîëüçóÿ Infn−1 (`(Ai ), di ).Ìû äîêàçûâàåì ëåììó èíäóêöèåé ïî n. Ïóñòü ìû ïîëó÷èëè íàâõîä (α, c), ãäå c = hm, A, di ∈ Cnα , è äëÿ âñåõ i < m ìû èìååì Ai =[βi , γi ). Ìû íàõîäèì ìèíèìàëüíîå ÷èñëî k òàêîå, ÷òî IsEmpn (dk ) = 0(íàïîìíèì, ÷òî îòñþäà ñëåäóåò, ÷òî evnα (dk ) 6= ∅); òàêîå k ñóùåñòâóåòòàê êàê evnα (c) 6= ∅. ñëó÷àå n = 0 ìû âîçâðàùàåì βk â êà÷åñòâå ðåçóëüòàòà Infn (α, c).Èç ëåììû 1.9 ñëåäóåò, ÷òî c(Infn (α, c)) ≤ ocnα (c).
Íåñëîæíî âèäåòü, ÷òîòðåáóåìàÿ âåðõíÿÿ îöåíêà íà âðåìÿ ðàáîòû èìååò ìåñòî.Òåïåðü ìû ðàññìàòðèâàåì ñëó÷àé n≥1. Ïîëîæèì δ=Infn−1 (`(Ak ), dk ). Åñëè δ = 0, òî ìû âîçâðàùàåì çíà÷åíèå Infn (α, c) =29βk . Èíà÷å ìû âîçâðàùàåì Infn (α, c) = βk + ω δ . Äîêàæåì, ÷òî òàêàÿInfn óäîâëåòâîðÿåò ñâîéñòâó 2. Î÷åâèäíî, Infn (α, c) ìèíèìàëüíûéîðäèíàë èç ìíîæåñòâà Ak òàêîé, ÷òî `(Infn (α, c)) ≥ δ . Òåì ñàìûì, äëÿâñÿêîãî ζ0 ∈ Ak , ζ0 < Infn (α, c) è íåêîòîðûõ îðäèíàëîâ ζ1 , . . . , ζn òàêèõ,÷òî (ζ0 , .
. . , ζn ) ∈ Uαn ìû èìååì `(ζ1 ) < δ . Ïîýòîìó, èç ïðåäïîëîæåíèÿèíäóêöèè 2. ñëåäóåò, ÷òîInfn (α, c) ≥ inf{γ0 | ∃γ1 , . . . , γn ((γ0 , . . . , γn ) ∈ evnα (c))}.Òàêæå èç ñâîéñòâà 2. äëÿ Infn−1 ñëåäóåò, ÷òî ñóùåñòâóåò ïîñëåäîâàòåëüíîñòü (δ, γ2 , . . . , γn ) ∈ evn`(−1Ak ) (dk ), à òåì ñàìûì(Infn (α, c), δ, γ2 , . .
. , γn ) ∈ evnα (c),è ñâîéñòâî 2. èìååò ìåñòî. Èç òîãî, ÷òî ñâîéñòâî 4. èìååò ìåñòî äëÿInfn−1 ñëåäóåò, ÷òî 4. âûïîëíÿåòñÿ è äëÿ Infn . Ïî ïðåäïîëîæåíèþ èíäóêöèè,c(Infn (α, c)) = c(βk ) + c(Infn−1 (`(Ak ), dk )) ≤ c(βk ) + oc(dk )≤ max c(βi ) + max oc(di ) = oc(c)i<mËåììà 1.15.i <mÄëÿ ÷èñåë 0 ≤ k ≤ n ñóùåñòâóåò âû÷èñëèìàÿ ôóíêöèÿRk -Invn (α, c) òàêàÿ, ÷òî íà âñÿêèõ âõîäàõ 0 < α < ε0 è c ∈ Cnα ìûèìååì:1. Rk -Invn (α, c) ýëåìåíò Cnα ;2. evnα (Rk -Invn (α, c)) = {w ∈ Uαn | ∃w0 ∈ evnα (c)(w Rk w0 )};3.
ocnα (Rk -Invn (α, c)) ≤ ocnα (c) + n è wαn (Rk -Invn (α, c)) ≤ wαn (c) + 1;4. âðåìÿ ðàáîòû Rk -Invn (α, c) îöåíèâàåòñÿ êàêO(max(ocnα (c), c(α)) · (wαn (c))n ).Äîêàçàòåëüñòâî. Ôóíêöèÿ R0 -Invn ìîæåò áûòü ëåãêî çàäàíà ñ èñïîëüçîâàíèåì Infn . Èäåÿ ðàáîòû ôóíêöèè Rk -Invn äëÿ k > 0 ñîñòîèò â30ïðèìåíåíèè R0 -Invn−k êî âñåì Cnβ−k -êîäàì, íàñëåäñòâåííî ëåæàùèì âäàííîì êîäå.Ìû äîêàçûâàåì ëåììó èíäóêöèåé ïî k.Ðàññìîòðèì ñëó÷àé k = 0.
Ïóñòü äàíû îðäèíàë α è êîä c ∈ Cnα .Åñëè IsEmp(α, c) = 1, ÷òî ýêâèâàëåíòíî òîìó, ÷òî evnα (c) ïóñòî, òî ìûïîëàãàåìRk -Invn (α, c) = EmpSn (α).Èíà÷å, ìû ïîëàãàåìRk -Invn (α, c) = h2, (B0 , B1 ), (e0 , e1 )i,ãäå B0 = [0, Infn (α, c) + 1), B1 = [Infn (α, c) + 1, α), e0 = EmpSn−1 (`(B0 ))è e1 = Cmpln (`(B1 ), EmpSn−1 (`(B1 ))). Ñâîéñòâî 1. î÷åâèäíî âûïîëíåíî. 2.è 3. ñëåäóþò èç ëåììû 1.14. Íåïîñðåäñòâåííîé ïðîâåðêîé ìû óñòàíàâëèâàåì âåðõíþþ îöåíêó íà âðåìÿ ðàáîòû, ò.å. ñâîéñòâî 4.Òåïåðü ìû ðàññìàòðèâàåì ñëó÷àé k > 0.
Ïóñòü äàíû îðäèíàë α > 0 è êîä c = hm, A, di ∈ Cnα . Äëÿ i < m ìû ïîëàãàåìei = Rk−1 -Invn−1 (`(Ai ), di ). Ìû âîçâðàùàåì çíà÷åíèå Rk -Invn (α, c) =hm, A, ei. Ñâîéñòâà 1. è 4. äëÿ Rk -Invn ñëåäóþò èç ñâîéñòâ Rk−1 -Invn−1ñ òåìè æå íîìåðàìè, èìåþùèìèñÿ â ñèëó ïðåäïîëîæåíèÿ èíäóêöèè. Ìûâûâîäèì ñâîéñòâî 3.
èç ëåììû 1.5 è ñâîéñòâà 3. äëÿ Rk−1 -Invn−1 .Ëåììà 1.16.Èìååòñÿ âû÷èñëèìàÿ ôóíêöèÿ Rstrn (α, β, c) òàêàÿ, ÷òîíà àðãóìåíòàõ âèäà 0 < β ≤ α < ε0 è c ∈ Cnα îíà îáëàäàåò ñëåäóþùèìèñâîéñòâàìè:1. Rstrn (α, β, c) ∈ Cnβ ;2. evnβ (Rstrn (α, β, c)) = evnα (c) ∩ Uβn ;3. ocnβ (Rstrn (α, β, c)) ≤ ocnα (c), wβn (Rstrn (α, β, c)) ≤ wαn (c);4. RstrnóäîâëåòâîðÿåòâåðõíåéîöåíêåíàâðåìÿðàáîòûO(max(ocnα (c), c(α), c(β)) · (wαn (c))n ).Äîêàçàòåëüñòâî.
Ìû äîêàçûâàåì ëåììó èíäóêöèåé ïî n. Ñëó÷àé n =31−1 òðèâèàëåí:Rstr−1 : (α, β, c) 7−→ c.Ïóñòü n ≥ 0. Ðàññìîòðèì âõîä (α, β, c), ãäå c = hm, A, di ∈ Cnα . Ìûâûáèðàåì ìàêñèìàëüíîå k < m òàêîå, ÷òî Ak ìåíüøå, ÷åì β ; î÷åâèäíî,÷òî ïî êðàéíåé ìåðå îäíî òàêîå k ñóùåñòâóåò. Ïóñòü Ak = [γ, δ). Ñåé÷àñìû îïðåäåëèì êîíå÷íûå ïîñëåäîâàòåëüíîñòè B è e, ýëåìåíòàìè êîòîðûõÿâëÿþòñÿ B0 , . . . , Bk è e0 , . .
. , ek ñîîòâåòñòâåííî. Ìû ïîëàãàåì Bi = Ai èei = di äëÿ i < k. Ïîëîæèì Bk = [γ, β) è ek = Rstrn (`(Ak ), `([γ, β)), c).Ìû âîçâðàùàåì çíà÷åíèå Rstrn (α, β, c) = hk + 1, B, ei. Èç ïðåäïîëîæåíèÿ èíäóêöèè ìû íåïîñðåäñòâåííî âûâîäèì ñâîéñòâà 1., 3. è 4. Äëÿóñòàíîâëåíèÿ ñâîéñòâà 2. ìû ðàññìàòðèâàåì ìèð (ζ0 , . .
. , ζn ) ∈ Uβn è äîêàçûâàåì, ÷òî(ζ0 , . . . , ζn ) ∈ evnβ (Rstrn (α, β, c)) ⇐⇒ (ζ0 , . . . , ζn ) ∈ evnα (c).Ñëó÷àé ζ0 6∈ Ak òðèâèàëåí, à ñëó÷àé ζ0 ∈ Ak ñëåäóåò èç ïóíêòà 2. ïðåäïîëîæåíèÿ èíäóêöèè è ëåììû 1.5.Ëåììà 1.17.Ñóùåñòâóåò âû÷èñëèìàÿ ôóíêöèÿ Intrn (α, c1 , c2 ) òà-êàÿ, ÷òî íà àðãóìåíòàõ 0 < α < ε0 è c1 , c2 ∈ Cnα îíà îáëàäàåò ñëåäóþùèìè ñâîéñòâàìè:1. Intrn (α, c1 , c2 ) ∈ Cnα ;2. evnα (Intrn (α, c1 , c2 )) = evnα (c1 ) ∩ evnα (c2 );3.
ocnα (Intrn (α, c1 , c2 )) ≤ ocnα (c1 ) + ocnα (c2 );4. wαn (Intrn (α, c1 , c2 )) ≤ wαn (c1 ) + wαn (c2 );5. âðåìÿ ðàáîòû Intrn (α, c1 , c2 ) óäîâëåòâîðÿåò âåðõíåé îöåíêåO(max(ocnα (c1 ), ocnα (c2 ), c(α)) · (max(wαn (c1 ), wαn (c2 )))n+1 ).Äîêàçàòåëüñòâî. Èäåÿ âû÷èñëåíèÿ Intrn (α, c1 , c2 ) òàêîâà:1. íàéòè êîäû c01 è c02 òàêèå, ÷òî èõ evnα -çíà÷åíèÿ ñîâïàäàþò ñî çíà÷åíèÿìè c1 è c2 ñîîòâåòñòâåííî è èìåþò âèä c01 = hk, B, e(1) i èc02 = hk, B, e(2) i;322. ïîëó÷èòü òðåáóåìûé êîä, èñïîëüçóÿ çíà÷åíèÿ Intrn−1 íà âñåõ âõîäàõ(1)(2)âèäà (`(Bi ), ei , ei ).Ìû äîêàçûâàåì ýòó ëåììó èíäóêöèåé ïî n. Ñëó÷àé n = −1òðèâèàëåí. Òåïåðü ïðåäïîëîæèì, ÷òî n ≥ 0.
Íèæå ìû îïèøåì àëãîðèòì ðàáîòû Intrn . Ïóñòü íàì äàíà íà âõîä òðîéêà (α, c1 , c2 ), ãäå êîäc1 = hm1 , A(1) , d(1) i ∈ Cnα è êîä c2 = hm2 , A(2) , d(2) i ∈ Cnα . Ìû ðàññìàò(1)(2)ðèâàåì âñå ïîïàðíûå ïåðåñå÷åíèÿ Ai ∩ Aj , ãäå i < m1 è j < m2 ; âñåïåðåñå÷åíèÿ ýòîãî âèäà ëèáî ïóñòû, ëèáî ðàâíû [β, γ) äëÿ íåêîòîðûõîðäèíàëîâ β è γ òàêèõ, ÷òî β < γ .Ìû ðàññìàòðèâàåì âñå íåïóñòûå ïåðåñå÷åíèÿ ýòîãî âèäà (âñå èçêîòîðûõ ÿâëÿþòñÿ ïîëóèíòåðâàëàìè) è óïîðÿäî÷èâàåì èõ â ïîðÿäêåâîçðàñòàíèÿ ëåâûõ êîíöîâ; ýòà ïðîöåäóðà äàåò íàì ïîñëåäîâàòåëüíîñòüB0 , B1 , . . . , Bk−1 .
Ìû ïîëó÷àåì êîíå÷íóþ ïîñëåäîâàòåëüíîñòü B äëèíû k.SÎ÷åâèäíî, ÷òîBi = [0, α) è äëÿ âñåõ i < k − 1 ïðàâûé êîíåö Bi ðàâåíi<këåâîìó êîíöó Bi+1 . Ëåãêî âèäåòü, ÷òî k ≤ m1 + m2 .Îïðåäåëèì êîíå÷íûå ïîñëåäîâàòåëüíîñòè e(1) , e(2) è e(3) äëèíû k. Äëÿ âñåõ i < k ìû íàõîäèì åäèíñòâåííîå j < m1 òàêîå, ÷òî(1)Bi ⊂ Aj(1)è ïîëàãàåì ei(1)(1)= Rstrn−1 (`(Aj ), `(Bi ), dj ).
Àíàëîãè÷íî,(2)äëÿ âñåõ i < k ìû íàõîäèì åäèíñòâåííîå j < m2 òàêîå, ÷òî Bi ⊂ Aj(2)(2)(2)è çàòåì ïîëàãàåì ei = Rstrn−1 (`(Aj ), `(Bi ), dj ). Äëÿ âñåõ i < k(3)ìû ïîëàãàåì ei= Intrn−1 (`(Bi ), e(1) , e(2) ). Ìû âîçâðàùàåì çíà÷åíèåIntrn (α, c1 , c2 ) = hk, B, e(3) i.Èç ïðåäïîëîæåíèÿ èíäóêöèè ìû çàêëþ÷àåì, ÷òî ñâîéñòâà 1., 3. è4 âûïîëíÿþòñÿ. Òàê êàê ìû ìîæåì óïîðÿäî÷èòü ïîëóèíòåðâàëû çà êâàäðàòè÷íîå ÷èñëî ñðàâíåíèé îðäèíàëîâ, ìû ïîëó÷àåì òðåáóåìóþ îöåíêó5., ïðèìåíÿÿ ïðåäïîëîæåíèå èíäóêöèè.
Äëÿ ïðîâåðêè óñëîâèÿ 4. ìûðàññìàòðèâàåì ìèð (ζ0 , . . . , ζn ) ∈ Uβn è äîêàçûâàåì, ÷òî(ζ0 , . . . , ζn ) ∈ evnα (Intrn (α, c1 , c2 )) ⇐⇒ (ζ0 , . . . , ζn ) ∈ evnα (c1 ) ∩ evnα (c2 );(1)(2)(1)(2)ìû íàõîäèì ïàðû ïîëóèíòåðâàëîâ Ai , Aj òàêèõ, ÷òî ζ0 ∈ Ai ∩ Aj ,à çàòåì èñïîëüçóåì èìåþùååñÿ ïî ïðåäïîëîæåíèþ èíäóêöèè ñâîéñòâî 433(1)(2)(1)(1)(2)(1)äëÿ n −1, îðäèíàëà `(Ai ∩ Aj ) è êîäîâ Rstrn (`(Ai ), `(Ai ∩ Aj ), di ),(2)(1)(2)(2)Rstrn (`(Aj ), `(Ai ∩ Aj ), dj ).Äëÿ âñåõ ïîëèìîäàëüíûõ ôîðìóë ϕ ìû îáîçíà÷àåì ÷åðåç |ϕ| êîëè÷åñòâî ñâÿçîê â ϕ:1. |>| = |⊥| = |x| = 1;2. |ϕ ∧ ψ| = |ϕ ∨ ψ| = |ϕ → ψ| = |ϕ| + |ψ| + 1;3. |hniϕ| = |ϕ| + 1.Ñåé÷àñ ìû äîêàæåì òåîðåìó 2.Äîêàçàòåëüñòâî. Ðàññìîòðèì çàìêíóòóþ GLPn -ôîðìóëó ϕ.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
