with . . ince ( i )     ( ), all subgoals of  ( i ) appear in   before subgoals of ( i). Therefore, is binder consistent with , and since is minimal, i is min consistent and not contradicting a contradiction.

(b) The sets of the second t  pe do not contain       contradicting pro ections, but in N some block of some pro ection is violated, or ma blocks from di erent pro ections are not ordered b . In such a case, N is . contradicting, b  orollar   and  emma  .

(c) The sets of the third t  pe do not contain      contradicting pro ections, and ma  blocks of the pro ections are not violated in  N and are sorted b ver  pro ection  ; either belongs to                 (  ;), or not. If   ;
( i ).

then there exists an
( i ) such that i is blockwise e uivalent to i (because the conti) is strongly valid by the inductive hypothesis, and is not     contradicting). If the contr
( i), we can set . .

NO 1 O 2 T 'k This substitution is well defined, since each - i
N O 1 O 2 O k et . N .

has the same number of ma blocks as j, and ma blocks of the pro ections are not violated in N. et be a minimal ordering of 0, binder consistent with      ince    is minimal, blocks of is blockwise e uivalent to 1, the ordering 1 - 1 - 1 or o' is well defined and minimal. In 1 the positions of the subgoals from  (  ) did not change thus, 2 is min consistent with 1, and blockwise e uivalence of 2 and 102 entails minimalit  of the ordering   2 01 02 o' o'          '  is  minimal.

other is, and finall obtainthat were 0 1  0 2 ON (note that we introduced blockwise e uivalence definition of Nietz and and strong validit onl to be able to perform this transition). is minimal, therefore   N is blockwise e uivalent to  N   N 
( ), since all its pro ections are candidates of the child nodes. Thereupon, N is blockwise e uivalent to a member of
( ) is strongl valid. To prove that prove ( ) is strongl valid, o, it su ces to show that all the members of 
( ) b b blgorithm , are either contradicting or blockwise e uivalent to members of 
( ). uch orderings can be of three t  pes
(a) rderings that violate blocks of the children pro ections. The are contradicting b   orollar
(b) rderings that do not violate blocks, but where ma blocks of children pro ections are not ordered b . The  are      contradicting b   emma
(c) rderings that do not violate blocks and have them sorted b    .  oreach combination of pro ections, one consistent ordering of is retained in the candidate set, and all the other are re ected.       orollar   , the re ected orderings are blockwise e uivalent to the retained candidate.

onse uently .

( ) is strongl  valid.