text: 22 SHAHRAM MOHSENIPOUR ⊂ − (53) Y (cid:48) F 1(β (cid:48) ) e +i e +i ≤ (cid:8) (cid:9) for 1 i < θ where | | ≤ (54) sup Y (cid:48) ; 1 i < θ = θ e +i and (cid:2) (cid:3) (cid:2) (cid:3) (cid:2) (cid:91) (cid:3) (cid:48) × · · · × × | ⊂ (cid:48) r r r,f (55) Y Y (cid:48) F ( Y (cid:48) ) S , 1 e e +i ≤ 1 i<θ − (cid:48) (cid:48) ≥ where s e = f 0. As in the previous subcases it is time to enter the Erd¨os and Rado’s polarized partition relation into the scene. By Corollary 2.3 we have −→ (56) (κ , . . . , κ , . . . , κ (cid:48)) (µ , . . . , µ , . . . , µ (cid:48))r . 1 d d+d p+1 e e 2χ R We shall introduce a partition relation on the set × · · · × × × · · · × ∈ [Xp∪+1{]r} [Xp+∈d]r [X×e+·δ·1·]×r [Xe+δd(cid:48) ]r as follows: For any α M∗ (cid:8)(cid:63) and(cid:89)any a [X(cid:89)]r [X ]r, let (cid:9) 1 p (cid:48) ∈ d × d (cid:8) P = x [X ]r [X ]r; τleft(a, x) = α (cid:9) α,a p+i e+δi i=1 i=1 ∈ where τleft(a, x) = (cid:63) is an abbreviation for τleft(a, x) > M∗. for any a as above, the set P ; α ∪ { } α,a M∗ (cid:63) forms a partition for the se(cid:89)t (cid:89) (cid:48) d × d [X ]r [X ]r p+i e+δi i=1 i=1 R R which we denote by . L(cid:89)et be a par(cid:89)tition relation such that (cid:89) a (cid:48) ∀ ∈ d × d R ∀ ∈ p R x , x [X ]r [X ]r : x x iﬀ a [X ]rx x . 1 2 p+i e+δi 1 2 i 1 a 2 i=1 i=1 i=1 ⊂ ≤ ≤ The number of partition classes is at most 2χ. Hence by (59) there are subsets Z X for 1 i d | | ⊂ ≤ ≤ (cid:48) | i | p+i such that Z = µ and also subset Z X for 1 i d such that Z = µ and the set i p+i ×d+·i· · × e+δi × · · · × d+i e+i [Z ]r [Z ]r [Z (cid:48)]r 1 d d+d ≤ ≤ ∗ ≤ ≤ (cid:48) ∗ lies in one partition class. Now for 1 i p put Y = X and for 1 i d + d put Y = Z . Also ≤ ≤ i (cid:48) i ∗ p•+•i i let Ye(cid:48)+i = Xe+δ (cid:48)+i for 1 i < θ. Finally for 1 (cid:89)i < e let Yi be any member of (Yi ) in the sense d of Fact 3.2. Now we can deduce that p ∀ ∈ ∗ a [Y ]r i (cid:89) i=1 either (cid:48) ∀ ∈ d+d ∗ x [Y ]r τleft(a, x) > M∗, p+i ∈ i=1 or there exists α M∗ such that ##LTLine## ##LTLine##

text: SHAHRAM

text: MOHSENIPOUR

text: Y

text: F

text: e

text: +i

text: e

text: +i

text: for

text: i

text: θ

text: where

text: sup

text: Y

text: i

text: θ

text: θ

text: e

text: +i

text: and

text: r

text: r

text: r,f

text: Y

text: Y

text: F

text: Y

text: S

text: e

text: e

text: +i

text: i<θ

text: where

text: s

text: e

text: f

text: As

text: in

text: the

text: previous

text: subcases

text: it

text: is

text: time

text: to

text: enter

text: the

text: Erd¨os

text: and

text: Rado’s

text: polarized

text: partition

text: relation

text: into

text: the

text: scene.

text: By

text: Corollary

text: we

text: have

text: (κ

text: κ

text: κ

text: (µ

text: µ

text: µ

text: d

text: d+d

text: e

text: e

text: 2χ

text: R

text: We

text: shall

text: introduce

text: a

text: partition

text: relation

text: on

text: the

text: set

text: [Xp+∈d]r

text: ]r

text: as

text: follows:

text: For

text: any

text: α

text: M∗

text: a

text: [X

text: ]r,

text: let

text: p

text: d

text: d

text: P

text: x

text: [X

text: ]r

text: [X

text: ]r;

text: τleft(a,

text: x)

text: α

text: α,a

text: p+i

text: e+δi

text: where

text: τleft(a,

text: x)

text: is

text: an

text: abbreviation

text: for

text: τleft(a,

text: x)

text: M∗.

text: for

text: any

text: a

text: as

text: above,

text: the

text: set

text: P

text: α

text: α,a

text: M∗

text: forms

text: a

text: partition

text: for

text: the

text: d

text: d

text: [X

text: ]r

text: [X

text: ]r

text: p+i

text: e+δi

text: R

text: R

text: which

text: we

text: denote

text: by

text: be

text: a

text: relation

text: such

text: that

text: a

text: d

text: d

text: R

text: p

text: R

text: x

text: x

text: [X

text: ]r

text: [X

text: ]r

text: x

text: x

text: iﬀ

text: a

text: [X

text: ]rx

text: x

text: p+i

text: e+δi

text: i

text: a

text: The

text: number

text: of

text: partition

text: classes

text: is

text: at

text: most

text: Hence

text: by

text: there

text: are

text: subsets

text: Z

text: X

text: for

text: i

text: d

text: i

text: p+i

text: such

text: that

text: Z

text: µ

text: and

text: also

text: subset

text: Z

text: X

text: for

text: i

text: d

text: such

text: that

text: Z

text: µ

text: and

text: the

text: set

text: i

text: p+i

text: ×d+·i·

text: e+δi

text: d+i

text: e+i

text: [Z

text: ]r

text: [Z

text: ]r

text: [Z

text: d

text: d+d

text: lies

text: in

text: one

text: partition

text: class.

text: Now

text: for

text: i

text: p

text: put

text: Y

text: X

text: and

text: for

text: i

text: d

text: d

text: put

text: Y

text: Z

text: Also

text: i

text: i

text: p•+•i

text: i

text: let

text: Xe+δ

text: for

text: i

text: θ.

text: Finally

text: for

text: e

text: let

text: Yi

text: be

text: any

text: member

text: of

text: (Yi

text: in

text: the

text: sense

text: d

text: of

text: Fact

text: Now

text: we

text: can

text: deduce

text: that

text: p

text: a

text: [Y

text: ]r

text: i

text: either

text: d+d

text: x

text: [Y

text: ]r

text: τleft(a,

text: x)

text: M∗,

text: p+i

text: or

text: there

text: exists

text: α

text: M∗

text: such

text: that

text: ##LTLine##

text: ##LTLine##


text: ON KEISLER SINGULAR-LIKE MODELS II 25 So if we assume ≤ ≤ γ = γ (µ , . . . , µ ) for 1 i e, i i 1 i ≤ γ = γ (µ , . . . , µ ) for 1 i < θ, e+i e+i 1 e then there are sets: ∈ − ∈ − X [F 1(γ )]µ1, . . . , X [F 1(γ )]µe, 1 1 e e ⊂ − X(cid:8) F 1(γ (cid:9) ) e+i e+i with | | (cid:89)(cid:2) s(cid:3)up (cid:2)Xe+i (cid:91); i < θ =(cid:3)θ such that e × | ⊂ r r,f X F ( X ) S i e+i ≤ i=1 1 i<θ − where s e = f. Now set ≤ ≤ β (µ , . . . , µ ) = γ (µ , . . . , µ ) for 1 i e. i 1 i i 1 i ≤ ≤ ⊂ − | | ≥ For 1 i d, let δ be the least ordinal < θ such that there is X F 1(γ ) with X µ . i · · · e+δi e+δi e+δi e+i We additionally may suppose that δ < δ < < δ . Also set 1 2 d ≤ ≤ β (µ , . . . , µ , . . . , µ ) = γ (µ , . . . , µ ) for 1 i d. e+i 1 e e+i e+δi 1 e We need to set up the situation before deﬁning the rest of β . This will be done by employing the i Erd¨os-Rado polarized partition theorem. Assume that M∗ = M and (cid:63) is a symbol diﬀerent from e+δ≤d ≤ (cid:48) all elements of M. let χ denotes the cardinality of M∗. Now for 1 i d deﬁne the cardinals κ , λ (cid:105) i i as follows: If i = 1, then λ = max(µ , 2χ), − (λ ) < κ < θ. If i > 1, then λ = max(µ , κ − ), (cid:105) 1 p+1 r 1 1 1 i p+i i 1 − (λ ) < κ < θ. By Corollary 2.3 we have r 1 i i −→ (65) (κ , . . . , κ (cid:48)) (µ , . . . , µ (cid:48))r 1 d p+1 e 2χ ≤ ≤ (cid:48) Now for 1 i d , let δ be the least ordinal < θ such that δ > δ − and there is ⊂ − |d+i | ≥ d+i d+i 1 X F 1(γ ) with X κ . Set e+δd+i e+δd+i e+δd+i i ≤ ≤ (cid:48) β (µ , . . . , µ ) = γ (µ , . . . , µ ) for 1 i d . p+i 1 p+i e+δd+i 1 e Also set ≤ βe(cid:48)+i(µ1, . . . , µp+i) = γe+δ (cid:48)+i(µ1, . . . , µe) for 1 i < θ. d+d We claim that the strategy β deﬁned above constitutes a winning strategy for the player II in the (cid:48) (cid:48) i game G(S , e ). Clearly it gives a strictly increasing sequence of moves for the player II. We shall prove that there are sets ∈ − ∈ − (66) Y1 [F 1(β1)]µ1, . . . , Ye(cid:48) [F 1(βe(cid:48))]µe(cid:48) ⊂ − ≤ (67) Y (cid:48) F 1(β (cid:48) ) for 1 i < θ e +i e +i such that (cid:8) (cid:9) | | (68) sup Y (cid:48) ; i < θ = θ e +i and

text: ON

label: paragraph

text: KEISLER

text: SINGULAR-LIKE

text: MODELS

text: II

text: So

text: if

text: we

text: assume

text: γ

text: γ

text: (µ

text: µ

text: for

text: i

text: e,

text: i

text: i

text: i

text: γ

text: γ

text: (µ

text: µ

text: for

text: i

text: θ,

text: e+i

text: e+i

text: e

text: then

text: there

text: are

text: sets:

text: X

text: [F

text: X

text: [F

text: )]µe,

text: e

text: e

text: F

text: e+i

text: e+i

text: with

text: i

text: θ

text: such

text: that

text: e

text: r

text: r,f

text: X

text: F

text: X

text: S

text: i

text: e+i

text: i<θ

text: where

text: s

text: e

text: f.

text: Now

text: set

text: β

text: (µ

text: µ

text: γ

text: (µ

text: µ

text: for

text: i

text: e.

text: i

text: i

text: i

text: i

text: For

text: i

text: d,

text: let

text: δ

text: be

text: the

text: least

text: ordinal

text: θ

text: such

text: that

text: there

text: is

text: X

text: F

text: with

text: X

text: µ

text: i

text: e+δi

text: e+δi

text: e+δi

text: e+i

text: We

text: additionally

text: may

text: suppose

text: that

text: δ

text: δ

text: δ

text: Also

text: set

text: d

text: β

text: (µ

text: µ

text: µ

text: γ

text: (µ

text: µ

text: for

text: i

text: d.

text: e+i

text: e

text: e+i

text: e+δi

text: e

text: We

text: need

text: to

text: set

text: up

text: the

text: situation

text: before

text: deﬁning

text: the

text: rest

text: of

text: β

text: This

text: will

text: be

text: done

text: by

text: employing

text: the

text: i

text: Erd¨os-Rado

text: polarized

text: partition

text: theorem.

text: Assume

text: that

text: M∗

text: M

text: and

text: is

text: a

text: symbol

text: diﬀerent

text: from

text: e+δ≤d

text: all

text: elements

text: of

text: M.

text: let

text: χ

text: denotes

text: the

text: cardinality

text: of

text: M∗.

text: Now

text: for

text: i

text: d

text: deﬁne

text: the

text: cardinals

text: κ

text: λ

text: i

text: i

text: as

text: follows:

text: If

text: i

text: then

text: λ

text: max(µ

text: (λ

text: κ

text: θ.

text: If

text: i

text: then

text: λ

text: max(µ

text: κ

text: r

text: i

text: p+i

text: i

text: (λ

text: κ

text: θ.

text: By

text: Corollary

text: we

text: have

text: r

text: i

text: i

text: (κ

text: κ

text: (µ

text: µ

text: d

text: e

text: 2χ

text: Now

text: for

text: i

text: d

text: let

text: δ

text: be

text: the

text: least

text: ordinal

text: θ

text: such

text: that

text: δ

text: δ

text: and

text: there

text: is

text: |d+i

text: d+i

text: d+i

text: X

text: F

text: with

text: X

text: κ

text: Set

text: e+δd+i

text: e+δd+i

text: e+δd+i

text: i

text: β

text: (µ

text: µ

text: γ

text: (µ

text: µ

text: for

text: i

text: d

text: p+i

text: p+i

text: e+δd+i

text: e

text: Also

text: set

text: µp+i)

text: γe+δ

text: µe)

text: for

text: i

text: θ.

text: d+d

text: We

text: claim

text: that

text: the

text: strategy

text: β

text: deﬁned

text: above

text: constitutes

text: a

text: winning

text: strategy

text: for

text: the

text: player

text: II

text: in

text: the

text: i

text: game

text: G(S

text: e

text: Clearly

text: it

text: gives

text: a

text: strictly

text: increasing

text: sequence

text: of

text: moves

text: for

text: the

text: player

text: II.

text: We

text: shall

text: prove

text: that

text: there

text: are

text: sets

text: [F

text: [F

text: Y

text: F

text: for

text: i

text: θ

text: e

text: +i

text: e

text: +i

text: such

text: that

text: sup

text: Y

text: i

text: θ

text: θ

text: e

text: +i

text: and


text: 4 SHAHRAM MOHSENIPOUR ≥ (cid:54) where u i , q is the greatest integer such that i = i and l , . . . , l − are arbitrary ordinals (cid:104) n (cid:105) q n ·1· · n q and c = c , . . . , c . If there is no such q, namely i = = i , then obviously the above i1j1 iqjq 1 n equality becomes: τ(c , . . . , c ) = τ(c , . . . , c ). i1j1 injn ul1 uln We add that in the above axioms we suppose that in any expression of terms with constants (cid:104) (cid:105) such as τ(c , . . . , c ), the sequence c , . . . , c is increasing. m1n1 mknk m1n1 mknk Now we prove the part (ii) of Theorem 1.2. Notationally we will make no diﬀerence between the symbols of the language and their interpretations ∗ ≺ Proof of Theorem 1.2 (ii). Let N be a model of Σ + Σ and N N be generated by C under the 1 { | } Skolem functions and κ be any inﬁnite cardinal. Let D = d i < κ be a set of new constant symbols L i L ∪ which we add to the language S(C) and denote the resulting language by S(C D). We introduce L ∪ ∗ L a set of axioms Π in S(C D) and show that (i) Π is consistent with Th(N , S(C)) (ii) for any ∗ L ∗ ≺ ∪ ∗ ≺ ∗ model K of Π + Th(N , S(C)), if K K is generated by C D then we have N K . Let Π L ∪ eee be the following S(C D)-theory: (i) d < d iﬀ i < j. i j (ii) d > c for any i, j. 0 ij If τ(c , . . . , c , c , . . . , c ) < c for some i > i and j, then i1j1 injn (i+1)0 (cid:104) (i+1)m (cid:105) ij n (iii) for any increasing sequence d , . . . , d : l0 lm τ(c, d , . . . , d ) = τ(c, c , . . . , c ), (cid:104) (cid:105) l0 lm (i+1)0 (i+1)m where c = c , . . . , c . i1j1 injn If for any i > i and j, τ(c , . . . , c , c , . . . , c ) > c , then n i1(cid:104)j1 injn (cid:105) (i+1)0 (i+1)m ij (iv) for any increasing sequence d , . . . , d : l0 lm τ(c , . . . , c , d , . . . , d ) > c , for any j. i1j1 injn l0 lm ij ∗ L (cid:48) To prove the consistency of Π + Th(N , S(C)), we assume that Π is a ﬁnite part of Π. We ∗ (cid:48) show that N is a model of Π via interpreting the ﬁnitely many constant symbols d ’s appearing in (cid:48) i (cid:48) Π by some suitable c ’s. Let c , . . . , c be all the elements of C which appeared in Π where ≤ · · · ≤ ij i1j1 injn (cid:48) i i . Also suppose d , . . . , d are all the constant symbols from D appearing in Π . Now we 1 n l0 lm ∗ interpret d , . . . , d by c , . . . , c in N , respectively. We also interpret all the Skolem l0 lm ∗ (in+1)0 (in+1)m terms and all c ’s in N as in the previous. It is evident Σ (ii) will guarantee that all sentences of ij 1 (cid:48) ∗ types of Π(i) and Π(ii) occurring in Π hold in N . It remains to show how the above interpretation (cid:48) ∗ of Π makes those sentences of types Π(iii) and Π(iv) true in N . Consider a sentence of type Π(iii), say, (1) τ(c, d , . . . , d ) = τ(c, c , . . . , c ), k0 kq (a+1)0 (a+1)q (cid:104) (cid:105) where c = c , . . . , c and a1b1 apbp { } ∪ { } ⊂ { } c , . . . , c c , . . . , c c , . . . , c , a1b1 apbp (a+1)0 (a+1)q i1j1 injn { } ⊂ { } (cid:48) as well as d , . . . , d d , . . . , d . Since the sentence (1) is in Π , we can deduce that it k0 kq l0 lm ≤ must already happened that τ(c, c , . . . , c ) < c ,for some j. Then by recalling that a i , (a+1)0 (a+1)q aj n Σ (iv) would imply that 1 τ(c, c , . . . , c ) = τ(c, c , . . . , c ) (a+1)0 (a+1)q (in+1)e0 (in+1)eq for any e , . . . , e , in particular when e ’s are such that l = k , . . . , l = k . So c , . . . ,c 0 q i e∗0 0 eq q (in+1)e0 (in+1)eq interpret d , . . . , d , respectively in such a way that N satisﬁes the sentence (1). Similarly consider k0 kq a sentence of type Π(iv): ﬁx i∗, j∗ such that (2) τ(c, dk0, . . . , dkq) > ci∗j∗. ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine##

text: SHAHRAM

text: MOHSENIPOUR

label: list

font: default

text: where

text: u

text: i

text: q

text: is

text: the

text: greatest

text: integer

text: such

text: that

text: i

text: i

text: and

text: l

text: l

text: are

text: arbitrary

text: ordinals

text: n

text: q

text: n

text: ·1·

text: n

text: q

text: and

text: c

text: c

text: c

text: If

text: there

text: is

text: no

text: such

text: q,

text: namely

text: i

text: i

text: then

text: obviously

text: the

text: above

text: iqjq

text: n

text: equality

text: becomes:

text: τ(c

text: c

text: τ(c

text: c

text: injn

text: uln

text: We

text: add

text: that

text: in

text: the

text: above

text: axioms

text: we

text: suppose

text: that

text: in

text: any

text: expression

text: of

text: terms

text: with

text: constants

text: such

text: as

text: τ(c

text: c

text: the

text: sequence

text: c

text: c

text: is

text: increasing.

text: mknk

text: mknk

text: Now

text: we

text: prove

text: the

text: part

text: (ii)

text: of

text: Theorem

text: Notationally

text: we

text: will

text: make

text: no

text: diﬀerence

text: between

text: the

text: symbols

text: of

text: the

text: language

text: and

text: their

text: interpretations

text: Proof

text: of

text: Theorem

text: (ii).

text: Let

text: N

text: be

text: a

text: model

text: of

text: Σ

text: Σ

text: and

text: N

text: N

text: be

text: generated

text: by

text: C

text: under

text: the

text: Skolem

text: functions

text: and

text: κ

text: be

text: any

text: inﬁnite

text: cardinal.

text: Let

text: D

text: d

text: i

text: κ

text: be

text: a

text: set

text: of

text: new

text: constant

text: symbols

text: L

text: i

text: L

text: which

text: we

text: add

text: to

text: the

text: language

text: S(C)

text: and

text: denote

text: the

text: resulting

text: language

text: by

text: S(C

text: D).

text: We

text: introduce

text: L

text: L

text: a

text: set

text: of

text: axioms

text: Π

text: in

text: S(C

text: D)

text: and

text: show

text: that

text: (i)

text: Π

text: is

text: consistent

text: with

text: Th(N

text: S(C))

text: (ii)

text: for

text: any

text: L

text: model

text: K

text: of

text: Π

text: Th(N

text: S(C)),

text: if

text: K

text: K

text: is

text: generated

text: by

text: C

text: D

text: then

text: we

text: have

text: N

text: K

text: Let

text: Π

text: L

text: eee

text: be

text: the

text: following

text: S(C

text: D)-theory:

text: (i)

text: d

text: d

text: iﬀ

text: i

text: j.

text: i

text: j

text: (ii)

text: d

text: c

text: for

text: any

text: i,

text: j.

text: ij

text: If

text: τ(c

text: c

text: c

text: c

text: c

text: for

text: some

text: i

text: i

text: and

text: j,

text: then

text: injn

text: ij

text: n

text: (iii)

text: for

text: any

text: increasing

text: sequence

text: d

text: d

text: lm

text: τ(c,

text: d

text: d

text: τ(c,

text: c

text: c

text: lm

text: where

text: c

text: c

text: c

text: injn

text: If

text: for

text: any

text: i

text: i

text: and

text: j,

text: τ(c

text: c

text: c

text: c

text: c

text: then

text: n

text: injn

text: ij

text: (iv)

text: for

text: any

text: increasing

text: sequence

text: d

text: d

text: lm

text: τ(c

text: c

text: d

text: d

text: c

text: for

text: any

text: j.

text: injn

text: lm

text: ij

text: L

text: To

text: prove

text: the

text: consistency

text: of

text: Π

text: Th(N

text: S(C)),

text: we

text: assume

text: that

text: Π

text: is

text: a

text: ﬁnite

text: part

text: of

text: Π.

text: We

text: show

text: that

text: N

text: is

text: a

text: model

text: of

text: Π

text: via

text: interpreting

text: the

text: ﬁnitely

text: many

text: constant

text: symbols

text: d

text: ’s

text: appearing

text: in

text: i

text: Π

text: by

text: some

text: suitable

text: c

text: ’s.

text: Let

text: c

text: c

text: be

text: all

text: the

text: elements

text: of

text: C

text: which

text: appeared

text: in

text: Π

text: where

text: ij

text: injn

text: i

text: i

text: Also

text: suppose

text: d

text: d

text: are

text: all

text: the

text: constant

text: symbols

text: from

text: D

text: appearing

text: in

text: Π

text: Now

text: we

text: n

text: lm

text: interpret

text: d

text: d

text: by

text: c

text: c

text: in

text: N

text: respectively.

text: We

text: also

text: interpret

text: all

text: the

text: Skolem

text: lm

text: terms

text: and

text: all

text: c

text: ’s

text: in

text: N

text: as

text: in

text: the

text: previous.

text: It

text: is

text: evident

text: Σ

text: (ii)

text: will

text: guarantee

text: that

text: all

text: sentences

text: of

text: ij

text: types

text: of

text: Π(i)

text: and

text: Π(ii)

text: occurring

text: in

text: Π

text: hold

text: in

text: N

text: It

text: remains

text: to

text: show

text: how

text: the

text: above

text: interpretation

text: of

text: Π

text: makes

text: those

text: sentences

text: of

text: types

text: Π(iii)

text: and

text: Π(iv)

text: true

text: in

text: N

text: Consider

text: a

text: sentence

text: of

text: type

text: Π(iii),

text: say,

text: τ(c,

text: d

text: d

text: τ(c,

text: c

text: c

text: kq

text: where

text: c

text: c

text: c

text: and

text: apbp

text: c

text: c

text: c

text: c

text: c

text: c

text: apbp

text: injn

text: as

text: well

text: as

text: d

text: d

text: d

text: d

text: Since

text: the

text: sentence

text: is

text: in

text: Π

text: we

text: can

text: deduce

text: that

text: it

text: kq

text: lm

text: must

text: already

text: happened

text: that

text: τ(c,

text: c

text: c

text: c

text: ,for

text: some

text: j.

text: Then

text: by

text: recalling

text: that

text: a

text: i

text: aj

text: n

text: Σ

text: (iv)

text: would

text: imply

text: that

text: τ(c,

text: c

text: c

text: τ(c,

text: c

text: c

text: for

text: any

text: e

text: e

text: in

text: particular

text: when

text: e

text: ’s

text: are

text: such

text: that

text: l

text: k

text: l

text: k

text: So

text: c

text: ,c

text: q

text: i

text: eq

text: q

text: interpret

text: d

text: d

text: respectively

text: in

text: such

text: a

text: way

text: that

text: N

text: satisﬁes

text: the

text: sentence

text: Similarly

text: consider

text: kq

text: a

text: sentence

text: of

text: type

text: Π(iv):

text: ﬁx

text: i∗,

text: j∗

text: such

text: that

text: τ(c,

text: dkq)

text: ci∗j∗.

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##


text: ON KEISLER SINGULAR-LIKE MODELS II 5 According to Π(iv), it must already happened that for all j: (3) τ(c, c(i∗+1)0, . . . , c(i∗+1)q) > ci∗j. We claim that for any e , . . . , e and for all j: 0 q τ(c, c(in+1)e0, . . . , c(in+1)eq) > ci∗j. ∗ ∗ ∗ If not, then there are j and e , . . . , e such that 0 q τ(c, c(in+1)e∗0, . . . , c(in+1)e∗q) < ci∗j∗, ≤ but i∗ i and in this case, Σ (iv) implies that n 1 τ(c, c(i∗+1)0, . . . , c(i∗+1)q) = τ(c, c(in+1)e∗0, . . . , c(in+1)e∗q) therefore τ(c, c(i∗+1)0, . . . , c(i∗+1)q) < ci∗j∗, which contradicts the inequality (3), so we have proved the claim. Again, if e ’s are such that l = k , . . . , l = k , then c ,. . . , c do interpret i e0 0 ∗ eq q (in+1)e0 (in+1)eq d , . . . , d , respectively in such a way that N satisﬁes the sentence (2). This completes the proof k0 kq ∗ L of (i), namely, Π is consistent with Th(N , S(C)). To demonstrate (ii), let K be a model of Π + ∗ L ∗ ≺ ∪ ∗ Th(N , S(C)) and let K K be generated by C D. Obviously we can identify with N , that ∗ ∗ ≺ ∗ elementary submodel of K which is generated by C. We must show that N K . Consider ∗ eee a typical element τ(c , . . . , c , d , . . . , d ) of K . For the sake of brevity we write c = (cid:104) (cid:105) u1v1 unvn l0 lm uv c , . . . , c . It suﬃces to show: u1v1 unvn ∗ ∈ ∗ either τ(c , d , . . . , d ) > N or τ(c , d , . . . , d ) N . uv l0 lm uv l0 lm There are two separate cases: Case (I): for any u < u and v: n τ(c , c , . . . , c ) > c . uv (u+1)0 (u+1)m uv ≤ Case (II): for some u u∗ and v∗: n τ(cuv, c(u∗+1)0, . . . , c(u∗+1)m) < cu∗v∗. If Case (I) occurs then by Π(iv) we have for any u and v: τ(c , d , . . . , d ) > c . uv l0 lm uv ∗ Since c ’s are coﬁnal in N , this means that uv ∗ τ(c , d , . . . , d ) > N . uv l0 lm If Case (II) occurs, then Π(iii) implies that τ(c , d , . . . , d ) = τ(c , c , . . . , c ), uv l0 lm uv (u∗+1)0 (u∗+1)m which means that ∈ ∗ τ(c , d , . . . , d ) N . uv l0 lm ∗ ≺ ∗ Therefore the proof of N K and consequently the proof of the part (ii) of Theorem 1.2 is eee (cid:3) complete. ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine##

text: ON

text: KEISLER

text: SINGULAR-LIKE

text: MODELS

text: II

text: According

text: to

text: Π(iv),

text: it

text: must

text: already

text: happened

text: that

text: for

text: all

text: j:

label: equation

text: τ(c,

text: ci∗j.

text: We

text: claim

text: that

text: for

text: any

text: e

text: e

text: and

text: for

text: all

text: j:

text: q

text: τ(c,

text: ci∗j.

text: If

text: not,

text: then

text: there

text: are

text: j

text: and

text: e

text: e

text: such

text: that

text: q

text: τ(c,

text: ci∗j∗,

text: but

text: i∗

text: i

text: and

text: in

text: this

text: case,

text: Σ

text: (iv)

text: implies

text: that

text: n

text: τ(c,

text: τ(c,

text: therefore

text: τ(c,

text: ci∗j∗,

text: which

text: contradicts

text: the

text: inequality

text: so

text: we

text: have

text: proved

text: the

text: claim.

text: Again,

text: if

text: e

text: ’s

text: are

text: such

text: that

text: l

text: k

text: l

text: k

text: then

text: c

text: c

text: do

text: interpret

text: i

text: eq

text: q

text: d

text: d

text: respectively

text: in

text: such

text: a

text: way

text: that

text: N

text: satisﬁes

text: the

text: sentence

text: This

text: completes

text: the

text: proof

text: kq

text: L

text: of

text: (i),

text: namely,

text: Π

text: is

text: consistent

text: with

text: Th(N

text: S(C)).

text: To

text: demonstrate

text: (ii),

text: let

text: K

text: be

text: a

text: model

text: of

text: Π

text: L

text: Th(N

text: S(C))

text: and

text: let

text: K

text: K

text: be

text: generated

text: by

text: C

text: D.

text: Obviously

text: we

text: can

text: identify

text: with

text: N

text: that

text: elementary

text: submodel

text: of

text: K

text: which

text: is

text: generated

text: by

text: C.

text: We

text: must

text: show

text: that

text: N

text: K

text: Consider

text: eee

text: a

text: typical

text: element

text: τ(c

text: c

text: d

text: d

text: of

text: K

text: For

text: the

text: sake

text: of

text: brevity

text: we

text: write

text: c

text: unvn

text: lm

text: uv

text: c

text: c

text: It

text: suﬃces

text: to

text: show:

text: unvn

text: either

text: τ(c

text: d

text: d

text: N

text: or

text: τ(c

text: d

text: d

text: N

text: uv

text: lm

text: uv

text: lm

text: There

text: are

text: two

text: separate

text: cases:

text: Case

text: (I):

text: for

text: any

text: u

text: u

text: and

text: v:

text: n

text: τ(c

text: c

text: c

text: c

text: uv

text: uv

text: Case

text: (II):

text: for

text: some

text: u

text: u∗

text: and

text: v∗:

text: n

text: τ(cuv,

text: cu∗v∗.

text: If

text: Case

text: (I)

text: occurs

text: then

text: by

text: Π(iv)

text: we

text: have

text: for

text: any

text: u

text: and

text: v:

text: τ(c

text: d

text: d

text: c

text: uv

text: lm

text: uv

text: Since

text: c

text: ’s

text: are

text: coﬁnal

text: in

text: N

text: this

text: means

text: that

text: uv

text: τ(c

text: d

text: d

text: N

text: uv

text: lm

text: If

text: Case

text: (II)

text: occurs,

text: then

text: Π(iii)

text: implies

text: that

text: τ(c

text: d

text: d

text: τ(c

text: c

text: c

text: uv

text: lm

text: uv

text: which

text: means

text: that

text: τ(c

text: d

text: d

text: N

text: uv

text: lm

text: Therefore

text: the

text: proof

text: of

text: N

text: K

text: and

text: consequently

text: the

text: proof

text: of

text: the

text: part

text: (ii)

text: of

text: Theorem

text: is

text: eee

text: complete.

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##


text: ON KEISLER SINGULAR-LIKE MODELS II 7 the new set Y (if not, set Y = Z). Now it is easily seen that Y satisﬁes the condition. In fact between (cid:3) any two elements of Z there are inﬁnitely many elements of X. 1 L ∗ Lemma 3.3. Let σ be a S(C )-sentence with parameters and c , . . . , c be all constant symbols i1j1 injn occurring in σ and they are arranged in the increasing order. Assume that r, s are two positive integers ≤ ≤ such that i s and j , . . . , j r and κ , . . . , κ are given inﬁnite cardinals. Also suppose that there n · · · 1 n 1 s are ordinals β < < β < θ together with subsets: 1 s ∈ − ∈ − X [F 1(β )]κ1, . . . , X [F 1(β )]κs, 1 1 s s ∈ × · · · × | | such that far all a [X ]r [X ]r we have M = σ(a) or more precisely M = σ(a , . . . , a ). 1 s i1j1 injn Then there are subsets ⊂ ⊂ | | | | Y X , . . . , Y X , Y = κ , . . . , Y = κ 1 1 s s 1 1 s s ∈ × · · · × | such that for all a [Y ]r [Y ]r we have M = σ(a , . . . , a ) when 1 s k1l1 knln (cid:104) (cid:105) (cid:104) (cid:105) c , . . . , c , c , . . . , c i1j1 injn k1l1 knln ≤ are equivalent and l , . . . , l r. 1 n Proof. According to Fact 3.2, let ∈ •• ∈ •• Y X , . . . , Y X 1 1 s s ∈ × · · · × for i = 1, . . . , s. Now this gives us the possibility that for any a [Y ]r [Y ]r we can choose a ∈ × · · · × 1 s b [X ]r [X ]r such that 1 s (cid:104) (cid:105) (cid:104) (cid:105) b , . . . , b = a , . . . , a . i1j1 injn k1l1 knln | | Now by the hypothesis we have M = σ(b , . . . , b ), hence the above equality implies that M = i1j1 injn (cid:3) σ(a , . . . , a ) which proves the lemma. k1l1 knln ∗ Now suppose σ is a sentence of type Σ (iv). In order to state our proposition we need to keep track 1 of the index i occurring in σ in the course of the proof, so for the sake of the easy readability, we n denote it by the function ι(σ) = i . n ⊂ Proposition 3.4. Let S [F]r,s be an e-superlarge set (e < s). Suppose σ is a sentence of type ∗ ≤ ≤ (cid:48) Σ (iv) so that for all c occurring in σ we have i s and j r and ι(σ) = e > e. Then there is an (cid:48)1 (cid:48) ⊂ ij ∈ (cid:48) | e -superlarge set S S such that for any a S we have M = σ(a). ∗ Proof. Suppose τ(c , . . . , c , . . . , c ) and q are as in the item (iv) of Σ . Set i1j1 iqjq injn 1 (cid:48) { ∈ | | } S = a S M = σ(a) . (cid:48) (cid:48) We show that S is e -superlarge. This will be done if we ﬁnd a winning strategy: β (µ ), . . . , β (cid:48)(µ , . . . , µ (cid:48)), . . . , β (cid:48) (µ , . . . , µ (cid:48)), . . . , i < θ, 1 1 e 1 e e +i 1 e (cid:48) (cid:48) for the player II in the game G(S , e ). Suppose the player I plays with a strategy µ , µ (β ), . . . , µ (cid:48)(β , . . . , β (cid:48)− ). 1 2 1 e 1 e 1 So our task is ﬁnding β such that guarantee the win of the player II. Since S is e-superlarge, then i the player II has a winning strategy for the game G(S, e): γ (µ ), . . . , γ (µ , . . . , µ ), . . . , γ (µ , . . . , µ ), . . . , i < θ, 1 1 e 1 e e+i 1 e 1I thank Franc¸ois Dorais for giving the proof of the uncountable case in response to my Mathoverﬂow question. ##LTLine## ##LTLine##

text: ON

text: KEISLER

text: SINGULAR-LIKE

text: MODELS

text: II

text: the

text: new

text: set

text: Y

text: (if

text: not,

text: set

text: Y

text: Z).

text: Now

text: it

text: is

text: easily

text: seen

text: that

text: Y

text: satisﬁes

text: the

text: condition.

text: In

text: fact

text: between

text: any

text: two

text: elements

text: of

text: Z

text: there

text: are

text: inﬁnitely

text: many

text: elements

text: of

text: X.

text: L

text: Lemma

text: Let

text: σ

text: be

text: a

text: S(C

text: )-sentence

text: with

text: parameters

text: and

text: c

text: c

text: be

text: all

text: constant

text: symbols

text: injn

text: occurring

text: in

text: σ

text: and

text: they

text: are

text: arranged

text: in

text: the

text: increasing

text: order.

text: Assume

text: that

text: r,

text: s

text: are

text: two

text: positive

text: integers

text: such

text: that

text: i

text: s

text: and

text: j

text: j

text: r

text: and

text: κ

text: κ

text: are

text: given

text: inﬁnite

text: cardinals.

text: Also

text: suppose

text: that

text: there

text: n

text: n

text: s

text: are

text: ordinals

text: β

text: β

text: θ

text: together

text: with

text: subsets:

text: s

text: X

text: [F

text: X

text: [F

text: )]κs,

text: s

text: s

text: such

text: that

text: far

text: all

text: a

text: [X

text: ]r

text: [X

text: ]r

text: we

text: have

text: M

text: σ(a)

text: or

text: more

text: precisely

text: M

text: σ(a

text: a

text: s

text: injn

text: Then

text: there

text: are

text: subsets

text: Y

text: X

text: Y

text: X

text: Y

text: κ

text: Y

text: κ

text: s

text: s

text: s

text: s

text: such

text: that

text: for

text: all

text: a

text: [Y

text: ]r

text: [Y

text: ]r

text: we

text: have

text: M

text: σ(a

text: a

text: when

text: s

text: knln

text: c

text: c

text: c

text: c

text: injn

text: knln

text: are

text: equivalent

text: and

text: l

text: l

text: r.

text: n

text: Proof.

text: According

text: to

text: Fact

text: let

text: Y

text: X

text: Y

text: X

text: s

text: s

text: for

text: i

text: s.

text: Now

text: this

text: gives

text: us

text: the

text: possibility

text: that

text: for

text: any

text: a

text: [Y

text: ]r

text: [Y

text: ]r

text: we

text: can

text: choose

text: a

text: s

text: b

text: [X

text: ]r

text: [X

text: ]r

text: such

text: that

text: s

text: b

text: b

text: a

text: a

text: injn

text: knln

text: Now

text: by

text: the

text: hypothesis

text: we

text: have

text: M

text: σ(b

text: b

text: hence

text: the

text: above

text: equality

text: implies

text: that

text: M

text: injn

text: σ(a

text: a

text: which

text: proves

text: the

text: lemma.

text: knln

text: Now

text: suppose

text: σ

text: is

text: a

text: sentence

text: of

text: type

text: Σ

text: (iv).

text: In

text: order

text: to

text: state

text: our

text: proposition

text: we

text: need

text: to

text: keep

text: track

text: of

text: the

text: index

text: i

text: occurring

text: in

text: σ

text: in

text: the

text: course

text: of

text: the

text: proof,

text: so

text: for

text: the

text: sake

text: of

text: the

text: easy

text: readability,

text: we

text: n

text: denote

text: it

text: by

text: the

text: function

text: ι(σ)

text: i

text: n

text: Proposition

text: Let

text: S

text: [F]r,s

text: be

text: an

text: e-superlarge

text: set

text: (e

text: s).

text: Suppose

text: σ

text: is

text: a

text: sentence

text: of

text: type

text: Σ

text: (iv)

text: so

text: that

text: for

text: all

text: c

text: occurring

text: in

text: σ

text: we

text: have

text: i

text: s

text: and

text: j

text: r

text: and

text: ι(σ)

text: e

text: e.

text: Then

text: there

text: is

text: an

text: ij

text: e

text: -superlarge

text: set

text: S

text: S

text: such

text: that

text: for

text: any

text: a

text: S

text: we

text: have

text: M

text: σ(a).

text: Proof.

text: Suppose

text: τ(c

text: c

text: c

text: and

text: q

text: are

text: as

text: in

text: the

text: item

text: (iv)

text: of

text: Σ

text: Set

text: iqjq

text: injn

text: S

text: a

text: S

text: M

text: σ(a)

text: We

text: show

text: that

text: S

text: is

text: e

text: -superlarge.

text: This

text: will

text: be

text: done

text: if

text: we

text: ﬁnd

text: a

text: winning

text: strategy:

text: β

text: (µ

text: β

text: µ

text: β

text: (µ

text: µ

text: i

text: θ,

text: e

text: e

text: e

text: +i

text: e

text: for

text: the

text: player

text: II

text: in

text: the

text: game

text: G(S

text: e

text: Suppose

text: the

text: player

text: I

text: plays

text: with

text: a

text: strategy

text: µ

text: µ

text: (β

text: µ

text: β

text: e

text: e

text: So

text: our

text: task

text: is

text: ﬁnding

text: β

text: such

text: that

text: guarantee

text: the

text: win

text: of

text: the

text: player

text: II.

text: Since

text: S

text: is

text: e-superlarge,

text: then

text: i

text: the

text: player

text: II

text: has

text: a

text: winning

text: strategy

text: for

text: the

text: game

text: G(S,

text: e):

text: γ

text: (µ

text: γ

text: (µ

text: µ

text: γ

text: (µ

text: µ

text: i

text: θ,

text: e

text: e

text: e+i

text: e

text: thank

text: Franc¸ois

text: Dorais

text: for

text: giving

text: the

text: proof

text: of

text: the

text: uncountable

text: case

text: in

text: response

text: to

text: my

text: Mathoverﬂow

text: question.

text: ##LTLine##

text: ##LTLine##


text: 10 SHAHRAM MOHSENIPOUR (cid:89) (cid:2) (cid:3) (cid:2) (cid:91) (cid:3) (cid:48) × | ⊂ (cid:48) r r,f (14) Y F ( Y (cid:48) ) S , i e +i ≤ ≤ (cid:48) ≤ 1 i e 1 i<θ (cid:48) − (cid:48) where f = s e . ∗ Our strategy to deﬁne Y will be as follows: we ﬁrst deﬁne sets Y such that they satisfy the i i ∈ ∗ •• relations (11), (12), (13). Then by the support of Lemma 3.3 we will ﬁnd Y (Y ) which satisfy i i (14). Obviously Y will automatically satisfy (11), (12), (13). ≤ ≤ i ∗ (cid:48) ∗ ∗ For 1 i e, let Yi = Xi and for e < i < e , ∗let Yi = Xki−e. Also for i < θ, let Ye(cid:48)+i = Zg(h(i)). The corresponding relations (12), (11) hold for Y because i ∗ ∈ − − ≤ ≤ Yi = Xi [F 1(γi)]µi = [F 1(βi)]µi, for 1 i e. ∗ ∈ − − (cid:48) Yi = Xki−e [F 1(γki−e)]µi = [F 1(βi)]µi, for e < i < e . ∗ ⊂ ⊂ − − Y (cid:48) = Z X F 1(γ ) = F 1(β (cid:48) ), for i < θ. e +i g(h(i)) g(h(i)) g(h(i)) e +i −→ ≥ Note that since h: θ θ is a strictly increasing function, then we have h(i) i for each i < θ, hence for i < θ: (cid:8) (cid:9) | ∗ | | | ≥ | | ≥ Y (cid:48) = Z Z π+, e +i g(h(i)) g(i) i | ∗ | | ∗| ≥ ≥ So sup Ye(cid:48)+i ; i < θ =∗θ. Also Ye(cid:48) π0+ > π0 µe(cid:48). Of course this will not cause a problem since we can easily replace Ye(cid:48) by each(cid:89)one(cid:2)of (cid:3)its su(cid:2)bsets(cid:91)of cardina(cid:3)lity µe(cid:48). Also it is not hard to see that (cid:48) ∗ × | ∗ ⊂ r r,f (15) Y F ( Y (cid:48) ) S. i e +i ≤ ≤ (cid:48) ≤ 1 i e 1 i<θ (cid:89) (cid:2) (cid:3) (cid:2) (cid:91) (cid:3) (cid:89) (cid:2) (cid:3) (cid:89) (cid:2) (cid:3) (cid:2) (cid:91) (cid:3) [Why? Observe that (cid:48) (cid:48) ∗ × | ∗ ∗ × ∗ × | ∗ r r,f r r r,f Y F ( Y (cid:48) ) = Y Y F ( Y (cid:48) ) . i e +i i i e +i ≤ ≤ (cid:48) ≤ ≤ ≤ ≤ (cid:48) ≤ 1 i e 1 i<θ 1 i e e<i e 1 i<θ (cid:89) (cid:2) (cid:3) (cid:89) (cid:2) (cid:3) (cid:2) (cid:3) (cid:2) (cid:91) (cid:3) The right side of the above equality can be rewritten as (cid:48) × × × | r r r r,f ≤ ≤ Xi (cid:48) Xki−e Zg(h(0)) F ( ≤ Zg(h(i))) 1 i e e<i<e 1 i<θ (cid:89) (cid:2) (cid:3) (cid:89) (cid:2) (cid:3) (cid:2) (cid:3) (cid:2) (cid:91) (cid:3) which is a subset of (cid:48) ♣ × × × | r r r r,f ( ) ≤ ≤ Xi (cid:48) Xki−e Xg(h(0)) F ( ≤ Xg(h(i))) 1 i e e<i<e 1 i<θ − (cid:48) But we have (d 1) + 1 + f = f and for i < θ · · · · · · · · · e < k < < k − < g(h(0)) < g(h(1)) < < g(h(i)) < 1 d 1 ♣ (cid:89) (cid:2) (cid:3) (cid:2) (cid:91) (cid:3) so we deduce that ( ) is contained in × | r r,f X F ( X ) i e+i ≤ ≤ ≤ 1 i e 1 i<θ

text: SHAHRAM

text: MOHSENIPOUR

text: r

text: r,f

text: Y

text: F

text: Y

text: S

text: i

text: e

text: +i

text: i

text: e

text: i<θ

text: where

text: f

text: s

text: e

text: Our

text: strategy

text: to

text: deﬁne

text: Y

text: will

text: be

text: as

text: follows:

text: we

text: ﬁrst

text: deﬁne

text: sets

text: Y

text: such

text: that

text: they

text: satisfy

text: the

text: i

text: i

text: relations

text: Then

text: by

text: the

text: support

text: of

text: Lemma

text: we

text: will

text: ﬁnd

text: Y

text: (Y

text: which

text: satisfy

text: i

text: i

text: Obviously

text: Y

text: will

text: automatically

text: satisfy

text: i

text: For

text: i

text: e,

text: let

text: Yi

text: Xi

text: and

text: for

text: e

text: i

text: e

text: ∗let

text: Yi

text: Xki−e.

text: Also

text: for

text: i

text: θ,

text: let

text: Zg(h(i)).

text: The

text: corresponding

text: relations

text: hold

text: for

text: Y

text: because

text: i

text: Yi

text: Xi

text: [F

text: [F

text: for

text: i

text: e.

text: Yi

text: Xki−e

text: [F

text: [F

text: for

text: e

text: i

text: e

text: Y

text: Z

text: X

text: F

text: F

text: for

text: i

text: θ.

text: e

text: +i

text: g(h(i))

text: g(h(i))

text: g(h(i))

text: e

text: +i

text: Note

text: that

text: since

text: h:

text: θ

text: θ

text: is

text: a

text: strictly

text: increasing

text: function,

text: then

text: we

text: have

text: h(i)

text: i

text: for

text: each

text: i

text: θ,

text: hence

text: for

text: i

text: θ:

text: Y

text: Z

text: Z

text: π+,

text: e

text: +i

text: g(h(i))

text: g(i)

text: i

text: So

text: sup

text: i

text: θ

text: =∗θ.

text: Also

text: π0

text: Of

text: course

text: this

text: will

text: not

text: cause

text: a

text: problem

text: since

text: we

text: can

text: easily

text: replace

text: by

text: Also

text: it

text: is

text: not

text: hard

text: to

text: see

text: that

text: r

text: r,f

text: Y

text: F

text: Y

text: S.

text: i

text: e

text: +i

text: i

text: e

text: i<θ

text: [Why?

text: Observe

text: that

text: r

text: r,f

text: r

text: r

text: r,f

text: Y

text: F

text: Y

text: Y

text: Y

text: F

text: Y

text: i

text: e

text: +i

text: i

text: i

text: e

text: +i

text: i

text: e

text: i<θ

text: i

text: e

text: e<i

text: e

text: i<θ

text: The

text: right

text: side

text: of

text: the

text: above

text: equality

text: can

text: be

text: rewritten

text: as

text: r

text: r

text: r

text: r,f

text: Xi

text: Xki−e

text: F

text: Zg(h(i)))

text: i

text: e

text: e<i<e

text: i<θ

text: which

text: is

text: a

text: subset

text: of

text: r

text: r

text: r

text: r,f

text: Xi

text: Xki−e

text: F

text: Xg(h(i)))

text: i

text: e

text: e<i<e

text: i<θ

text: But

text: we

text: have

text: (d

text: f

text: f

text: and

text: for

text: i

text: θ

text: e

text: k

text: k

text: g(h(i))

text: d

text: so

text: we

text: deduce

text: that

text: is

text: contained

text: in

text: r

text: r,f

text: X

text: F

text: X

text: i

text: e+i

text: i

text: e

text: i<θ


text: ∈ ∗ Proof. We assume that there exists a factor of the form 3u1u3 in w, for some word u Σ . 4 From the deﬁnition of g, we observe that u can not be empty. Furthermore, we see that (cid:54) every 3 in w is preceded by either 0 or 1. If 1 u, then we had an occurrence of the s (cid:54) factor 11 in w, which is not possible by the deﬁnition of g, hence 0 u. Now, every 3 s is followed by either 0 or 2 in w and 01 is followed by either 2 or 3. Since both 3u and (cid:54) 01u are factors of w, we must have 2 u. This means that the factor 012 appears at p (cid:54) the center of u1u, which can only be followed by 1 in w, thus 21 u. However, this p results in the factor 321 as a preﬁx of 3u1u3, which does not appear in w, as seen from the deﬁnition of g. Lemma 2. The word w = gω(0) is square-free. { } Proof. We ﬁrst observe that g(0), g(1), g(2), g(3) is a biﬁx code. Furthermore, we can | | (cid:54) verify that there are no squares uu with u 3 in w. Let us assume now, that the square (cid:48) uu appears in w and that u is the shortest word with this property. If u = 02u , then (cid:48) (cid:48)(cid:48) u = u 03 must hold, since 02 appears only as a factor of g(3), and thus uu is a suﬃx (cid:48)(cid:48) (cid:48)(cid:48) − (cid:48)(cid:48) − (cid:48)(cid:48) of the factor g(3)u g(3)u in w. As w = g(w), also the shorter square 3g 1(u )3g 1(u ) appears in w, a contradiction. The same desubstitution principle also leads to occurrences (cid:48) ∈ { } of shorter squares in w if u = xu and x 01, 03, 10, 12, 13, 21, 30, 32 . (cid:48) (cid:54) (cid:54) (cid:54) If u = 2u then either 03 u or 030 u or 01 u, by the deﬁnition of g. In the (cid:54) s s (cid:54) s last case, that is when 01 u, we must have 21 u, which is covered by the previous (cid:48) (cid:48)(cid:48) s p paragraph. If u = u 030, then uu is followed by 2 in w and we can desubstitute to obtain − (cid:48)(cid:48) − (cid:48)(cid:48) (cid:48) (cid:48) (cid:48)(cid:48) the shorter square g 1(u )3g 1(u )3 in w. If u = 2u and u = u 03, and uu is preceded − (cid:48)(cid:48) − (cid:48)(cid:48) − (cid:48)(cid:48) − (cid:48)(cid:48) by 03 or followed by 2 in w, we can desubstitute to 1g 1(u )1g 1(u ) or g 1(u )1g 1(u )1, (cid:48)(cid:48) respectively. Therefore, assume that u = 2u 03 and uu is preceded by 030 and followed by 02 in w. This however means that we can desubstitu(cid:81)te to get an(cid:81)occurrence(cid:81)of the − (cid:48)(cid:48) − (cid:48)(cid:48) factor 3g 1(u )1g 1(u )3 in w, a contradiction to Lemma 1. ∞ ∞ ∞ We now show that w = gω(0) can be written as w = U V = U = V ∈ ∗ i=0 i i i=0 i i=0 i with U , V Σ . i i 4 Lemma 3. The word w = gω(0) is self-shuﬄing. − Proof. In what follows we use the notation x = v 1u meaning that u = vx for ﬁnite words x, u, v. We are going to show that the self-shuﬄe is given by the following: − − U = g2(0), U = 0, . . . , U = gi(0 1g(0)0), U = gi(0 1g(3)0), 0 1 6i+2 6i+3 − U = gi(0 1g(201)0), U = gi(30), 6i+4 6i+5 U = gi(2g(03)), U = gi+1(20), 6i+6 6i+7 − − V = g(0)03, V = 2g(2)0, . . . , V = gi(0 1g(1)0), V = gi(0 1g(03)0), 0 1 6i+2 6i+3 V = gi(1), V = gi(3), 6i+4 6i+5 − V = gi+1(0), V = gi+1(0 1g(2)0). 6i+6 6i+7 the electronic journal of combinatorics 16 (2009), #R00 3 ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine##

text: Proof.

text: We

text: assume

text: that

text: there

text: exists

text: a

text: factor

text: of

text: the

text: form

text: in

text: w,

text: for

text: some

text: word

text: u

text: Σ

text: From

text: the

text: deﬁnition

text: of

text: g,

text: we

text: observe

text: that

text: u

text: can

text: not

text: be

text: empty.

text: Furthermore,

text: we

text: see

text: that

text: every

text: in

text: w

text: is

text: preceded

text: by

text: either

text: or

text: If

text: u,

text: then

text: we

text: had

text: an

text: occurrence

text: of

text: the

text: s

text: factor

text: in

text: w,

text: which

text: is

text: not

text: possible

text: by

text: the

text: deﬁnition

text: of

text: g,

text: hence

text: u.

text: Now,

text: every

text: s

text: is

text: followed

text: by

text: either

text: or

text: in

text: w

text: and

text: is

text: followed

text: by

text: either

text: or

text: Since

text: both

text: and

text: are

text: factors

text: of

text: w,

text: we

text: must

text: have

text: u.

text: This

text: means

text: that

text: the

text: factor

text: appears

text: at

text: p

text: the

text: center

text: of

text: which

text: can

text: only

text: be

text: followed

text: by

text: in

text: w,

text: thus

text: u.

text: However,

text: this

text: p

text: results

text: in

text: the

text: factor

text: as

text: a

text: preﬁx

text: of

text: which

text: does

text: not

text: appear

text: in

text: w,

text: as

text: seen

text: from

text: the

text: deﬁnition

text: of

text: g.

text: Lemma

text: The

text: word

text: w

text: is

text: square-free.

text: Proof.

text: We

text: ﬁrst

text: observe

text: that

text: is

text: a

text: biﬁx

text: code.

text: Furthermore,

text: we

text: can

text: verify

text: that

text: there

text: are

text: no

text: squares

text: uu

text: with

text: u

text: in

text: w.

text: Let

text: us

text: assume

text: now,

text: that

text: the

text: square

text: uu

text: appears

text: in

text: w

text: and

text: that

text: u

text: is

text: the

text: shortest

text: word

text: with

text: this

text: property.

text: If

text: u

text: then

text: u

text: u

text: must

text: hold,

text: since

text: appears

text: only

text: as

text: a

text: factor

text: of

text: and

text: thus

text: uu

text: is

text: a

text: suﬃx

text: of

text: the

text: factor

text: in

text: w.

text: As

text: w

text: g(w),

text: also

text: the

text: shorter

text: square

text: appears

text: in

text: w,

text: a

text: contradiction.

text: The

text: same

text: desubstitution

text: principle

text: also

text: leads

text: to

text: occurrences

text: of

text: shorter

text: squares

text: in

text: w

text: if

text: u

text: xu

text: and

text: x

text: If

text: u

text: then

text: either

text: u

text: or

text: u

text: or

text: u,

text: by

text: the

text: deﬁnition

text: of

text: g.

text: In

text: the

text: s

text: s

text: s

text: last

text: case,

text: that

text: is

text: when

text: u,

text: we

text: must

text: have

text: u,

text: which

text: is

text: covered

text: by

text: the

text: previous

text: s

text: p

text: paragraph.

text: If

text: u

text: u

text: then

text: uu

text: is

text: followed

text: by

text: in

text: w

text: and

text: we

text: can

text: desubstitute

text: to

text: obtain

text: the

text: shorter

text: square

text: g

text: in

text: w.

text: If

text: u

text: and

text: u

text: u

text: and

text: uu

text: is

text: preceded

text: by

text: or

text: followed

text: by

text: in

text: w,

text: we

text: can

text: desubstitute

text: to

text: or

text: g

text: respectively.

text: Therefore,

text: assume

text: that

text: u

text: and

text: uu

text: is

text: preceded

text: by

text: and

text: followed

text: by

text: in

text: w.

text: This

text: however

text: means

text: that

text: we

text: can

text: to

text: get

text: the

text: factor

text: in

text: w,

text: a

text: contradiction

text: to

text: Lemma

text: We

text: now

text: show

text: that

text: w

text: can

text: be

text: written

text: as

text: w

text: U

text: V

text: U

text: V

text: i

text: i

text: i

text: i

text: with

text: U

text: V

text: Σ

text: i

text: i

text: Lemma

text: The

text: word

text: w

text: is

text: self-shuﬄing.

text: Proof.

text: In

text: what

text: follows

text: we

text: use

text: the

text: notation

text: x

text: v

text: meaning

text: that

text: u

text: vx

text: for

text: ﬁnite

text: words

text: x,

text: u,

text: v.

text: We

text: are

text: going

text: to

text: show

text: that

text: the

text: self-shuﬄe

text: is

text: given

text: by

text: the

text: following:

text: U

text: U

text: U

text: U

text: U

text: U

text: U

text: U

text: V

text: V

text: V

text: V

text: V

text: V

text: V

text: V

text: the

text: electronic

text: journal

text: of

text: combinatorics

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##


text: Fidelity threshold of the surface code beyond single-qubit error models Pejman Jouzdani,1 E. Novais,2 I. S. Tupitsyn,3,4 and Eduardo R. Mucciolo1 1Department of Physics, University of Central Florida, Orlando, Florida 32816, USA 2Centro de Ciˆencias Naturais e Humanas, Universidade Federal do ABC, Santo Andr´e, SP, Brazil 3Physics Department, University of Massachusetts, Amherst, MA 01003, USA 4Paciﬁc Institute of Theoretical Physics, University of British Columbia, Vancouver, BC V6T1Z1, Canada (Dated: May 26, 2020) The surface code is a promising alternative for implementing fault-tolerant, large-scale quantum information processing. Its high threshold for single-qubit errors under stochastic noise is one of its most attractive features. We develop an exact formulation for the ﬁdelity of the surface code that allows us to probe much further on this promise of strong protection. This formulation goes beyond the stochastic single-qubit error model approximation and can take into account both correlated errors and inhomogeneities in the coupling between physical qubits and the environment. For the case of a bit-ﬂipping environment, we map the complete evolution after one quantum error correction cycle onto the problem of computing correlation functions of a two-dimensional Ising model with boundary ﬁelds. Exact results for the ﬁdelity threshold of the surface code are then obtained for several relevant types of noise. Analytical predictions for a representative case are conﬁrmed by Monte Carlo simulations. PACS numbers: 03.67.Lx, 03.67.Pp, 03.65.Yz, 05.50.+q I. INTRODUCTION supported by Monte Carlo simulations. The remaining of the paper is organized as follows. In Quantum error correction (QEC) is one of the most Sec. we discuss the diﬀerence between intrinsic and important tools to reduce the eﬀects of decoherence in eﬀective thresholds, which is crucial for the understand- quantum systems that process information. Several dif- ing of our results. The next two sections are mainly a ferent protocols have been developed since QEC was ﬁrst review: Sec. contains a concise description of the sur- introduced [1], but particular attention has been given to face code and Sec. describes the code’s evolution, syn- stabilizer codes [2]. Among them, the surface code [3, 4] drome extraction, and error correction within one cycle is perhaps the most promising for large-scale implemen- in very general terms. The description of our work begins tations [5]. Its main virtues are: (i) qubits are dis≈posed in Sec. , where some basic assumptions and deﬁnitions in a planar array, only requiring local measurement o<per- are provided and a suitable expression for the ﬁdelity is ations; and (ii) early estimates based on stochastic error presented. This is followed by a discussion in Sec. of models indicated a very large threshold value, p 11% decoding and the thermodynamic limit in the determina- c [4], for the single-qubit error probability p. For p p , tion of the threshold. A realistic error model that induces c the probability of successful encoding tends to 1 as the bit-ﬂip errors is introduced in Sec. and consists of an ef- number of physical qubits is increased. fective action involving single-qubit and two-qubit inter- Despite the large theoretical eﬀort that has been de- action terms. Using this error model and considering the voted to characterizing the threshold of the surface code full quantum evolution of the physical qubits, in Sec. we [4, 6–10], the true nature of the transition has been hard map the ﬁdelity calculation after one QEC cycle onto the to assess due to the large Hilbert space that the code evaluation of correlation functions of a two-dimensional demands. Some criticism has also been raised by the Ising model. In Sec. we discuss several scenarios based use of simpliﬁed error models in these studies, since, for on that mapping, including cases with homogeneous and more traditional QEC schemes, error models that take inhomogeneous couplings. In Sec. we present the re- into account correlations can substantially alter or even sult of Monte Carlo simulations of the ﬁdelity threshold remove error thresholds [11–13]. In this paper we make and conﬁrm the analytical prediction based on the map- signiﬁcant progress on both issues. We consider more ping for the homogeneous coupling case. Conclusions are general bit-ﬂip error models with and without disorder provided in Sec. and correlations. We derive an exact mapping of a com- II. INTRINSIC AND EFFECTIVE plete QEC quantum evolution with arbitrary syndrome THRESHOLDS onto a two-dimensional Ising model with complex tem- perature. Exact results are then obtained for what we Two QEC strategies can be used for any stabilizer call the “one-cycle threshold”. Our main conclusion is a code. In the so-called active QEC, stabilizer operators positive one: a ﬁdelity threshold exists in most cases, al- are measured and, based on their syndromes, a recovery though its value is not universal, depending on the noise operation is chosen and implemented. In passive QEC, model. For a representative case, the analytical predic- the physical qubits are subjected to a Hamiltonian that tion for the threshold location based on the mapping is enforces an energy gap between the code word subspace

text: Fidelity

label: title

text: threshold

text: of

text: the

text: surface

text: code

text: beyond

text: single-qubit

text: error

text: models

text: Pejman

label: author

text: E.

text: I.

text: S.

text: and

text: Eduardo

text: R.

text: of

text: Physics,

text: University

text: of

text: Central

text: Florida,

text: Orlando,

text: Florida

text: USA

text: de

text: Ciˆencias

text: Naturais

text: e

text: Humanas,

text: Universidade

text: Federal

text: do

text: ABC,

text: Santo

text: Andr´e,

text: SP,

text: Brazil

text: Department,

text: University

text: of

text: Massachusetts,

text: Amherst,

text: MA

text: USA

text: Institute

text: of

text: Theoretical

text: Physics,

text: University

text: of

text: British

text: Columbia,

text: Vancouver,

text: BC

text: Canada

text: (Dated:

text: May

label: date

text: The

label: abstract

text: surface

text: code

text: is

text: a

text: promising

text: alternative

text: for

text: implementing

text: fault-tolerant,

text: large-scale

text: quantum

text: information

text: processing.

text: Its

text: high

text: threshold

text: for

text: single-qubit

text: errors

text: under

text: stochastic

text: noise

text: is

text: one

text: of

text: its

text: most

text: attractive

text: features.

text: We

text: develop

text: an

text: exact

text: formulation

text: for

text: the

text: ﬁdelity

text: of

text: the

text: surface

text: code

text: that

text: allows

text: us

text: to

text: probe

text: much

text: further

text: on

text: this

text: promise

text: of

text: strong

text: protection.

text: This

text: formulation

text: goes

text: beyond

text: the

text: stochastic

text: single-qubit

text: error

text: model

text: approximation

text: and

text: can

text: take

text: into

text: account

text: both

text: correlated

text: errors

text: and

text: inhomogeneities

text: in

text: the

text: coupling

text: between

text: physical

text: qubits

text: and

text: the

text: environment.

text: For

text: the

text: case

text: of

text: a

text: bit-ﬂipping

text: environment,

text: we

text: map

text: the

text: complete

text: evolution

text: after

text: one

text: quantum

text: error

text: correction

text: cycle

text: onto

text: the

text: problem

text: of

text: computing

text: correlation

text: functions

text: of

text: a

text: two-dimensional

text: Ising

text: model

text: with

text: boundary

text: ﬁelds.

text: Exact

text: results

text: for

text: the

text: ﬁdelity

text: threshold

text: of

text: the

text: surface

text: code

text: are

text: then

text: obtained

text: for

text: several

text: relevant

text: types

text: of

text: noise.

text: Analytical

text: predictions

text: for

text: a

text: representative

text: case

text: are

text: conﬁrmed

text: by

text: Monte

text: Carlo

text: simulations.

text: PACS

text: numbers:

text: I.

text: INTRODUCTION

text: supported

text: by

text: Monte

text: Carlo

text: simulations.

text: The

text: remaining

text: of

text: the

text: paper

text: is

text: organized

text: as

text: follows.

text: In

text: Quantum

text: error

text: correction

text: (QEC)

text: is

text: one

text: of

text: the

text: most

text: Sec.

text: we

text: discuss

text: the

text: diﬀerence

text: between

text: intrinsic

text: and

text: important

text: tools

text: to

text: reduce

text: the

text: eﬀects

text: of

text: decoherence

text: in

text: eﬀective

text: thresholds,

text: which

text: is

text: crucial

text: for

text: the

text: understand-

text: quantum

text: systems

text: that

text: process

text: information.

text: Several

text: dif-

text: ing

text: of

text: our

text: results.

text: The

text: next

text: two

text: sections

text: are

text: mainly

text: a

text: ferent

text: protocols

text: have

text: been

text: developed

text: since

text: QEC

text: was

text: ﬁrst

text: review:

text: Sec.

text: contains

text: a

text: concise

text: description

text: of

text: the

text: sur-

text: introduced

text: but

text: particular

text: attention

text: has

text: been

text: given

text: to

text: face

text: code

text: and

text: Sec.

text: describes

text: the

text: code’s

text: evolution,

text: syn-

text: stabilizer

text: codes

text: Among

text: them,

text: the

text: surface

text: code

text: drome

text: extraction,

text: and

text: error

text: correction

text: within

text: one

text: cycle

text: is

text: perhaps

text: the

text: most

text: promising

text: for

text: large-scale

text: implemen-

text: in

text: very

text: general

text: terms.

text: The

text: description

text: of

text: our

text: work

text: begins

text: tations

text: Its

text: main

text: virtues

text: are:

text: (i)

text: qubits

text: are

text: dis≈posed

text: in

text: Sec.

text: where

text: some

text: basic

text: assumptions

text: and

text: deﬁnitions

text: in

text: a

text: planar

text: array,

text: only

text: requiring

text: local

text: measurement

text: o<per-

text: are

text: provided

text: and

text: a

text: suitable

text: expression

text: for

text: the

text: ﬁdelity

text: is

text: ations;

text: and

text: (ii)

text: early

text: estimates

text: based

text: on

text: stochastic

text: error

text: presented.

text: This

text: is

text: followed

text: by

text: a

text: discussion

text: in

text: Sec.

text: of

text: models

text: indicated

text: a

text: very

text: large

text: threshold

text: value,

text: p

text: decoding

text: and

text: the

text: thermodynamic

text: limit

text: in

text: the

text: determina-

text: c

text: for

text: the

text: single-qubit

text: error

text: probability

text: p.

text: For

text: p

text: p

text: tion

text: of

text: the

text: threshold.

text: A

text: realistic

text: error

text: model

text: that

text: induces

text: c

text: the

text: probability

text: of

text: successful

text: encoding

text: tends

text: to

text: as

text: the

text: bit-ﬂip

text: errors

text: is

text: introduced

text: in

text: Sec.

text: and

text: consists

text: of

text: an

text: ef-

text: number

text: of

text: physical

text: qubits

text: is

text: increased.

text: fective

text: action

text: involving

text: single-qubit

text: and

text: two-qubit

text: inter-

text: Despite

text: the

text: large

text: theoretical

text: eﬀort

text: that

text: has

text: been

text: de-

text: action

text: terms.

text: Using

text: this

text: error

text: model

text: and

text: considering

text: the

text: voted

text: to

text: characterizing

text: the

text: threshold

text: of

text: the

text: surface

text: code

text: full

text: quantum

text: evolution

text: of

text: the

text: physical

text: qubits,

text: in

text: Sec.

text: we

text: the

text: true

text: nature

text: of

text: the

text: transition

text: has

text: been

text: hard

text: map

text: the

text: ﬁdelity

text: calculation

text: after

text: one

text: QEC

text: cycle

text: onto

text: the

text: to

text: assess

text: due

text: to

text: the

text: large

text: Hilbert

text: space

text: that

text: the

text: code

text: evaluation

text: of

text: correlation

text: functions

text: of

text: a

text: two-dimensional

text: demands.

text: Some

text: criticism

text: has

text: also

text: been

text: raised

text: by

text: the

text: Ising

text: model.

text: In

text: Sec.

text: we

text: discuss

text: several

text: scenarios

text: based

text: use

text: of

text: simpliﬁed

text: error

text: models

text: in

text: these

text: studies,

text: since,

text: for

text: on

text: that

text: mapping,

text: including

text: cases

text: with

text: homogeneous

text: and

text: more

text: traditional

text: QEC

text: schemes,

text: error

text: models

text: that

text: take

text: inhomogeneous

text: couplings.

text: In

text: Sec.

text: we

text: present

text: the

text: re-

text: into

text: account

text: correlations

text: can

text: substantially

text: alter

text: or

text: even

text: sult

text: of

text: Monte

text: Carlo

text: simulations

text: of

text: the

text: ﬁdelity

text: threshold

text: remove

text: error

text: thresholds

text: In

text: this

text: paper

text: we

text: make

text: and

text: conﬁrm

text: the

text: analytical

text: prediction

text: based

text: on

text: the

text: map-

text: signiﬁcant

text: progress

text: on

text: both

text: issues.

text: We

text: consider

text: more

text: ping

text: for

text: the

text: homogeneous

text: coupling

text: case.

text: Conclusions

text: are

text: general

text: bit-ﬂip

text: error

text: models

text: with

text: and

text: without

text: disorder

text: provided

text: in

text: Sec.

text: and

text: correlations.

text: We

text: derive

text: an

text: exact

text: mapping

text: of

text: a

text: com-

text: II.

text: INTRINSIC

text: AND

text: EFFECTIVE

text: plete

text: QEC

text: quantum

text: evolution

text: with

text: arbitrary

text: syndrome

text: THRESHOLDS

text: onto

text: a

text: two-dimensional

text: Ising

text: model

text: with

text: complex

text: tem-

text: perature.

text: Exact

text: results

text: are

text: then

text: obtained

text: for

text: what

text: we

text: Two

text: QEC

text: strategies

text: can

text: be

text: used

text: for

text: any

text: stabilizer

text: call

text: the

text: “one-cycle

text: threshold”.

text: Our

text: main

text: conclusion

text: is

text: a

text: code.

text: In

text: the

text: so-called

text: active

text: QEC,

text: stabilizer

text: operators

text: positive

text: one:

text: a

text: ﬁdelity

text: threshold

text: exists

text: in

text: most

text: cases,

text: al-

text: are

text: measured

text: and,

text: based

text: on

text: their

text: syndromes,

text: a

text: recovery

text: though

text: its

text: value

text: is

text: not

text: universal,

text: depending

text: on

text: the

text: noise

text: operation

text: is

text: chosen

text: and

text: implemented.

text: In

text: passive

text: QEC,

text: model.

text: For

text: a

text: representative

text: case,

text: the

text: analytical

text: predic-

text: the

text: physical

text: qubits

text: are

text: subjected

text: to

text: a

text: Hamiltonian

text: that

text: tion

text: for

text: the

text: threshold

text: location

text: based

text: on

text: the

text: mapping

text: is

text: enforces

text: an

text: energy

text: gap

text: between

text: the

text: code

text: word

text: subspace


text: 3 ∣ ( )⟩ = ∣↑ ⟩ where σx,z are the Pauli operators x and z of qubit i. The logicail operations are deﬁned as strings of physical Ψ 0 ¯,e . (9) qubit operations: = ∏ ( ) The logical qubit and the environment evolve under a ∈ X¯ σx (3) unitary evolution∣ op(er)a⟩to=r U( ∆)∣ fo(r )a⟩ time ∆, ΓX i i ΓX Ψ ∆ U ∆ Ψ 0 . (10) and = ∏ ± ∈ Z¯ σz, (4) Since we{a}re assuming only bit-ﬂip errors, stars will ΓZ i remain always with eigenvalue 1 under this evolution. i ΓZ On the other hand, plaquettes may have eigenvalue 1. Let us call p a set of plaquettes that return a nontrivial where Γ is a path that cuts through the lattice from Z syndrome, thus indicating an error. When the stabilizers left to right and Γ is a path that goes from top to X are measured, the system’s state vector is projected by bottom [23]. Finally, th∣↑e⟩c=ode∣wor⟩ds can be written as the operatPor = ∏( + )∏( − ) { } ◻ ¯ G Fz (5) 1◻ ◻′ ′ ◻ p 2N 1 B 1 Bp , (1+1) ′ p and ∣↓⟩ = ∣ ⟩ where is the set of plaSquettes with eigenvalue 1. The decoding procedure associates to a syndrome a cer- { } ¯ X¯ G F , (6) tain recovery operation. In t{he} surface code, this corre- ΓX z sponds to choosing a string x made of a product of σx p i operators that connect the plaquettes in p pairwise or where = √ ∏( + ) to the boundaries. This recovery operation results in the ♢ unnormaliz∣ed stat⟩e vec=toSr P ∣ ( )⟩ G 1 ♢ ♢ 1 A (7) { } = S{ }P{ } ( )∣↑ ⟩ 2N Ψ {x } { } Ψ ∆ QEC p p p x U ∆ ¯,e . (12) and ∣ ⟩ = ∣↑⟩ ⊗ ⋯ ⊗ ∣↑⟩ p p A small but important simpliﬁcation can be made: no- F (8) z 1 N tice thSat P = S ∏( + )∏( − ) ♢ { } { } { } ◻ phiyssitchael qfeurbroitms.agHneetre,stNate dinentohteeszthceomnpumonbeen∣r↓t⟩ooff stthaer xp p = 2N1◻ ∏xp( ◻+′ 1 )BS ′ 1 Bp operators on the lattice and N is the total number of ◻ { } p pthheyspiacratlicquulbaritcsh. oiTceheofpΓrodauncdt uX¯nΓiqXuGelyisdienﬁdneepsen¯de(nthtuosf, 2N1◻ ◻ 1 B xp , (13) X hereafter we wi+ll drop the path subscript in the logical op- erators). The logical space is a two-dimensional Hilbert where in the second line the product over plaquettes is space where all plaquettes and stars, when measu−red, re- unco∣ nstrai⟩ned.=There∏for(e, + )S ( )∣↑ ⟩ turn the value 1; by convention, this set is called the zero charge sector. All other sets deﬁne sectors with nonzero { } ◻ { } charge and are characterized by the number of 1 syn- Ψ 1◻ ◻ 1 B ∏x( U+ ∆ )¯,e . (14) drome values for the plaquette and star operators. QEC p 2N p ∣ ⟩ ◻ ◻ IV. QUANTUM EVOLUTION, SYNDROME, AND ERROR CORRECTION The presence of the projector 1 B on the right- h∣↑a⟩nd sid∣↓e⟩of Eq. (14) implies that ΨQEC contains only ∣↑⟩To make the discussion more concise, and wit∣h⟩out loss qubit statSes with all plaquettes positive∣↑, ⟩i.e., it can be of generality for the case of bit-ﬂip errors, let us assume represented by a superposition of the two logical states that the system is initially prepared in the logical state ¯ and ¯ .{T}he amplitude of each state depends on the ¯ and is not entangled with the environment e , choice of . A good choice will favor ¯ . p ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine##

text: where

text: σx,z

text: are

text: the

text: Pauli

text: operators

text: x

text: and

text: z

text: of

text: qubit

text: i.

text: The

text: logicail

text: operations

text: are

text: deﬁned

text: as

text: strings

text: of

text: physical

text: Ψ

text: ¯,e

text: qubit

text: operations:

text: The

text: logical

text: qubit

text: and

text: the

text: environment

text: evolve

text: under

text: a

text: X¯

text: σx

text: unitary

text: evolution∣

text: op(er)a⟩to=r

text: U(

text: fo(r

text: )a⟩

text: time

text: ΓX

text: i

text: i

text: ΓX

text: Ψ

text: U

text: Ψ

text: and

text: Z¯

text: σz,

text: Since

text: we{a}re

text: assuming

text: only

text: bit-ﬂip

text: errors,

text: stars

text: will

text: ΓZ

text: i

text: remain

text: always

text: with

text: eigenvalue

text: under

text: this

text: evolution.

text: i

text: ΓZ

text: On

text: the

text: other

text: hand,

text: plaquettes

text: may

text: have

text: eigenvalue

text: Let

text: us

text: call

text: p

text: a

text: set

text: of

text: plaquettes

text: that

text: return

text: a

text: nontrivial

text: where

text: Γ

text: is

text: a

text: path

text: that

text: cuts

text: through

text: the

text: lattice

text: from

text: Z

text: syndrome,

text: thus

text: indicating

text: an

text: error.

text: When

text: the

text: stabilizers

text: left

text: to

text: right

text: and

text: Γ

text: is

text: a

text: path

text: that

text: goes

text: from

text: top

text: to

text: X

text: are

text: measured,

text: the

text: system’s

text: state

text: vector

text: is

text: projected

text: by

text: bottom

text: Finally,

text: th∣↑e⟩c=ode∣wor⟩ds

text: can

text: be

text: written

text: as

text: the

text: operatPor

text: G

text: Fz

text: 1◻

text: p

text: B

text: Bp

text: p

text: and

text: where

text: is

text: the

text: set

text: of

text: plaSquettes

text: with

text: eigenvalue

text: The

text: decoding

text: procedure

text: associates

text: to

text: a

text: syndrome

text: a

text: cer-

text: X¯

text: G

text: F

text: tain

text: recovery

text: operation.

text: In

text: t{he}

text: surface

text: code,

text: this

text: corre-

text: ΓX

text: z

text: sponds

text: to

text: choosing

text: a

text: string

text: x

text: made

text: of

text: a

text: product

text: of

text: σx

text: p

text: i

text: operators

text: that

text: connect

text: the

text: plaquettes

text: in

text: p

text: pairwise

text: or

text: where

text: to

text: the

text: boundaries.

text: This

text: recovery

text: operation

text: results

text: in

text: the

text: unnormaliz∣ed

text: stat⟩e

text: vec=toSr

text: P

text: G

text: A

text: S{

text: }P{

text: Ψ

text: {x

text: Ψ

text: QEC

text: p

text: p

text: p

text: x

text: U

text: ¯,e

text: and

text: p

text: p

text: A

text: small

text: but

text: important

text: simpliﬁcation

text: can

text: be

text: made:

text: no-

text: F

text: z

text: N

text: tice

text: thSat

text: P

text: S

text: phiyssitchael

text: qfeurbroitms.agHneetre,stNate

text: dinentohteeszthceomnpumonbeen∣r↓t⟩ooff

text: stthaer

text: xp

text: p

text: ∏xp(

text: )BS

text: Bp

text: operators

text: on

text: the

text: lattice

text: and

text: N

text: is

text: the

text: total

text: number

text: of

text: p

text: pthheyspiacratlicquulbaritcsh.

text: oiTceheofpΓrodauncdt

text: B

text: xp

text: X

text: hereafter

text: we

text: wi+ll

text: drop

text: the

text: path

text: subscript

text: in

text: the

text: logical

text: op-

text: erators).

text: The

text: logical

text: space

text: is

text: a

text: two-dimensional

text: Hilbert

text: where

text: in

text: the

text: second

text: line

text: the

text: product

text: over

text: plaquettes

text: is

text: space

text: where

text: all

text: plaquettes

text: and

text: stars,

text: when

text: measu−red,

text: re-

text: unco∣

text: nstrai⟩ned.=There∏for(e,

text: )S

text: turn

text: the

text: value

text: by

text: convention,

text: this

text: set

text: is

text: called

text: the

text: zero

text: charge

text: sector.

text: All

text: other

text: sets

text: deﬁne

text: sectors

text: with

text: nonzero

text: charge

text: and

text: are

text: characterized

text: by

text: the

text: number

text: of

text: syn-

text: Ψ

text: 1◻

text: B

text: ∏x(

text: U+

text: )¯,e

text: drome

text: values

text: for

text: the

text: plaquette

text: and

text: star

text: operators.

text: QEC

text: p

text: p

text: IV.

text: QUANTUM

text: EVOLUTION,

text: SYNDROME,

text: AND

text: ERROR

text: CORRECTION

text: The

text: presence

text: of

text: the

text: projector

text: B

text: on

text: the

text: right-

text: h∣↑a⟩nd

text: sid∣↓e⟩of

text: Eq.

text: implies

text: that

text: ΨQEC

text: contains

text: only

text: ∣↑⟩To

text: make

text: the

text: discussion

text: more

text: concise,

text: and

text: wit∣h⟩out

text: loss

text: qubit

text: statSes

text: with

text: all

text: plaquettes

text: positive∣↑,

text: ⟩i.e.,

text: it

text: can

text: be

text: of

text: generality

text: for

text: the

text: case

text: of

text: bit-ﬂip

text: errors,

text: let

text: us

text: assume

text: represented

text: by

text: a

text: superposition

text: of

text: the

text: two

text: logical

text: states

text: that

text: the

text: system

text: is

text: initially

text: prepared

text: in

text: the

text: logical

text: state

text: and

text: .{T}he

text: amplitude

text: of

text: each

text: state

text: depends

text: on

text: the

text: and

text: is

text: not

text: entangled

text: with

text: the

text: environment

text: e

text: choice

text: of

text: A

text: good

text: choice

text: will

text: favor

text: p

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##


text: 1 Introduction We consider the synchronization problem for a network of coupled nonlinear agents with V { } agent set = 1, 2, . . . , N . Their interactions (communications in the network) are described G V E ∞ → P by a time-varying directed graph = ( , ), with σ : [0, ) as a piecewise constant σ(t) σ(t) P V ∈ V signal, where is a ﬁnite set of all possible graphs over . The state of agent i at time t is ∈ R denoted as x (t) n and evolves according to i (cid:88) − x˙ = f(t, x ) + a (t)(x x ), (1) i i ij j i ∈N j i(σ(t)) ∞ ×R → R where f(t, x ) : [0, ) n n is piecewise continuous in t and continuous in x represent- i i N ing the uncoupled inherent agent dynamics, (σ(t)) is the set of agent i’s neighbors at time t, i and a (t) > 0 is a piecewise continuous function marking the weight of edge (j, i) at time t. ij Systems of the form (1) have attracted considerable attention. Most works focus on the case G where the communication graph is ﬁxed, e.g., [1–7]. It is shown that for the case where σ(t) f(t, x ) satisﬁes a Lipschitz condition, synchronization is achieved for a connected graph provided i that the coupling strength is suﬃciently large. However, for the case where the communication graph is time-varying, the synchronization problem becomes much more challenging and existing literature mainly focuses on a few special cases when f(t, x ) is linear, e.g., the single-integrator i case [8–10], the double-integrator case [11], and the neutrally stable case [12,13]. Other studies assume some particular structures for the communication graph [14–16]. In particular, in [14], the authors focus on the case where the adjacency matrices associated with all communication graphs are simultaneously triangularizable. The authors of [15] consider switching communica- tion graphs that are weakly connected and balanced at all times. A more general case where the switching communication graph frequently has a directed spanning tree has been considered in [16]. These special structures on the switching communication graph are rather restrictive compared to joint connectivity where the communication can be lost at any time. This paper aims to investigate whether joint connectivity for switching communication graphs can render synchronization for the nonlinear dynamics (1). We distinguish two classes depending on whether the nonlinear agent dynamics f(t, x ) is expansive or not. For the non- i expansive case, we focus on the case where the nonlinear agent dynamics is stable with a convex 2

label: section

text: Introduction

text: We

text: consider

text: the

text: synchronization

text: problem

text: for

text: a

text: network

text: of

text: coupled

text: nonlinear

text: agents

text: with

text: V

text: agent

text: set

text: N

text: Their

text: interactions

text: (communications

text: in

text: the

text: network)

text: are

text: described

text: G

text: V

text: E

text: P

text: by

text: a

text: time-varying

text: directed

text: graph

text: with

text: σ

text: as

text: a

text: piecewise

text: constant

text: σ(t)

text: σ(t)

text: P

text: V

text: V

text: signal,

text: where

text: is

text: a

text: ﬁnite

text: set

text: of

text: all

text: possible

text: graphs

text: over

text: The

text: state

text: of

text: agent

text: i

text: at

text: time

text: t

text: is

text: R

text: denoted

text: as

text: x

text: (t)

text: n

text: and

text: evolves

text: according

text: to

text: i

text: x˙

text: f(t,

text: x

text: a

text: (t)(x

text: x

text: i

text: i

text: ij

text: j

text: i

text: ∈N

text: j

text: i(σ(t))

text: ×R

text: R

text: where

text: f(t,

text: x

text: n

text: n

text: is

text: piecewise

text: continuous

text: in

text: t

text: and

text: continuous

text: in

text: x

text: represent-

text: i

text: i

text: N

text: ing

text: the

text: uncoupled

text: inherent

text: agent

text: dynamics,

text: (σ(t))

text: is

text: the

text: set

text: of

text: agent

text: i’s

text: neighbors

text: at

text: time

text: t,

text: i

text: and

text: a

text: (t)

text: is

text: a

text: piecewise

text: continuous

text: function

text: marking

text: the

text: weight

text: of

text: edge

text: (j,

text: i)

text: at

text: time

text: t.

text: ij

text: Systems

text: of

text: the

text: form

text: have

text: attracted

text: considerable

text: attention.

text: Most

text: works

text: focus

text: on

text: the

text: case

text: G

text: where

text: the

text: communication

text: graph

text: is

text: ﬁxed,

text: e.g.,

text: It

text: is

text: shown

text: that

text: for

text: the

text: case

text: where

text: σ(t)

text: f(t,

text: x

text: satisﬁes

text: a

text: Lipschitz

text: condition,

text: synchronization

text: is

text: achieved

text: for

text: a

text: connected

text: graph

text: provided

text: i

text: that

text: the

text: coupling

text: strength

text: is

text: suﬃciently

text: large.

text: However,

text: for

text: the

text: case

text: where

text: the

text: communication

text: graph

text: is

text: time-varying,

text: the

text: synchronization

text: problem

text: becomes

text: much

text: more

text: challenging

text: and

text: existing

text: literature

text: mainly

text: focuses

text: on

text: a

text: few

text: special

text: cases

text: when

text: f(t,

text: x

text: is

text: linear,

text: e.g.,

text: the

text: single-integrator

text: i

text: case

text: the

text: double-integrator

text: case

text: and

text: the

text: neutrally

text: stable

text: case

text: Other

text: studies

text: assume

text: some

text: particular

text: structures

text: for

text: the

text: communication

text: graph

text: In

text: particular,

text: in

text: the

text: authors

text: focus

text: on

text: the

text: case

text: where

text: the

text: adjacency

text: matrices

text: associated

text: with

text: all

text: communication

text: graphs

text: are

text: simultaneously

text: triangularizable.

text: The

text: authors

text: of

text: consider

text: switching

text: communica-

text: tion

text: graphs

text: that

text: are

text: weakly

text: connected

text: and

text: balanced

text: at

text: all

text: times.

text: A

text: more

text: general

text: case

text: where

text: the

text: switching

text: communication

text: graph

text: frequently

text: has

text: a

text: directed

text: spanning

text: tree

text: has

text: been

text: considered

text: in

text: These

text: special

text: structures

text: on

text: the

text: switching

text: communication

text: graph

text: are

text: rather

text: restrictive

text: compared

text: to

text: joint

text: connectivity

text: where

text: the

text: communication

text: can

text: be

text: lost

text: at

text: any

text: time.

text: This

text: paper

text: aims

text: to

text: investigate

text: whether

text: joint

text: connectivity

text: for

text: switching

text: communication

text: graphs

text: can

text: render

text: synchronization

text: for

text: the

text: nonlinear

text: dynamics

text: We

text: distinguish

text: two

text: classes

text: depending

text: on

text: whether

text: the

text: nonlinear

text: agent

text: dynamics

text: f(t,

text: x

text: is

text: expansive

text: or

text: not.

text: For

text: the

text: non-

text: i

text: expansive

text: case,

text: we

text: focus

text: on

text: the

text: case

text: where

text: the

text: nonlinear

text: agent

text: dynamics

text: is

text: stable

text: with

text: a

text: convex


text:   (cid:88)  ≤1 max e−2L(t−t0) a (t)((cid:107)x − x (cid:107)2 − (cid:107)x − x (cid:107)2) 2 {i,j}∈V1×V2 (cid:88) k1∈Ni(σ(t)) ik1 j k1 i j  − − (cid:107) − (cid:107) − (cid:107) − (cid:107) +e 2L(t t0) a (t)( x x 2 x x 2)   (cid:88)∈N jk2 i k2 (cid:88)i j  k2 j(σ(t))   ≤ − − ≤ max a (t)(V V ) + a (t)(V V ) 0, (25) { }∈V ×V ik1 jk1 ij jk2 ik2 ij i,j 1 2 k1∈Ni(σ(t)) k2∈Nj(σ(t)) where the ﬁrst equality follows from Lemma 2 and (1), the ﬁrst inequality follows from (4) and ab ≤ a2+b2 and −ab ≤ a2+b2 for all a, b ∈ Rn, and the second inequality follows from (24). 2 2 G Lemma 6 Let Assumption 4 hold. Assume that is uniformly jointly strongly connected. σ(t) Then there exists 0 < β˜ < 1 such that ≤ ∗ ∀{ } ∈ V × V V (NT , x(NT )) β˜V , i, j , ij 0 0 − ∗ where N = N 1, T is given by (7) and V = V (t , x(t )). 0 0 0 { } ∈ Proof: The proof is based on the convergence analysis of V (t, x(t) for all agent pairs i, j ij V × V in several steps, which is similar to the proof of Lemma 3. Without loss of generality, we assume that t = 0. We also sometimes denote V (t, x(t)) and V (t, x(t)) as V and V , 0 ij ij respectively, for notational simpliﬁcation. ∈ V G Step 1. We begin by considering any agent i . Since is uniformly jointly strongly 1 σ(t) ∈ V \ { } connected, we know that i is the root and that there exists a time t and an agent i i 1 1 2 1 ∈ E ∈ ⊂ such that (i , i ) during t [t , t + τ ) [0, T ]. 1 2 1 1 D 0 ∈ We ﬁrst note that it follows from (23) and Lemma 5 that for all t [0, NT ], 0 ≤ ≤ ∗ ∀{ } ∈ V × V V (t, x(t)) V (t, x(t)) V , i, j . (26) ij  ∈ Taking the derivative of V along the trajectories of (1), we obt(cid:88)ain that for all t [t , t +τ ), ij 1 1 D  − − − (cid:107) − (cid:107) − − − − V˙ = Le 2L(t t0) x x 2 + e 2L(t t0)(x x )T a (t)(x x ) i1i2 i1 i2 i1 i2 i1k1 k1 i1 ∈N k1 i1(σ(t)) 16 ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine##

text: ≤1

text: max

text: a

text: x

text: x

text: j

text: i

text: j

text: +e

text: a

text: (t)(

text: x

text: x

text: x

text: x

text: i

text: j

text: j(σ(t))

text: max

text: a

text: (t)(V

text: V

text: a

text: (t)(V

text: V

text: }∈V

text: ×V

text: ij

text: ij

text: i,j

text: where

text: the

text: ﬁrst

text: equality

text: follows

text: from

text: Lemma

text: and

text: the

text: ﬁrst

text: inequality

text: follows

text: from

text: and

text: ab

text: and

text: −ab

text: for

text: all

text: a,

text: b

text: Rn,

text: and

text: the

text: second

text: inequality

text: follows

text: from

text: G

text: Lemma

text: Let

text: Assumption

text: hold.

text: Assume

text: that

text: is

text: uniformly

text: jointly

text: strongly

text: connected.

text: σ(t)

text: Then

text: there

text: exists

text: β˜

text: such

text: that

text: V

text: V

text: V

text: (NT

text: x(NT

text: β˜V

text: i,

text: j

text: ij

text: where

text: N

text: N

text: T

text: is

text: given

text: by

text: and

text: V

text: V

text: (t

text: x(t

text: Proof:

text: The

text: proof

text: is

text: based

text: on

text: the

text: convergence

text: analysis

text: of

text: V

text: (t,

text: x(t)

text: for

text: all

text: agent

text: pairs

text: i,

text: j

text: ij

text: V

text: V

text: in

text: several

text: steps,

text: which

text: is

text: similar

text: to

text: the

text: proof

text: of

text: Lemma

text: Without

text: loss

text: of

text: generality,

text: we

text: assume

text: that

text: t

text: We

text: also

text: sometimes

text: denote

text: V

text: (t,

text: x(t))

text: and

text: V

text: (t,

text: x(t))

text: as

text: V

text: and

text: V

text: ij

text: ij

text: respectively,

text: for

text: notational

text: simpliﬁcation.

text: V

text: G

text: Step

text: We

text: begin

text: by

text: considering

text: any

text: agent

text: i

text: Since

text: is

text: uniformly

text: jointly

text: strongly

text: σ(t)

text: V

text: connected,

text: we

text: know

text: that

text: i

text: is

text: the

text: root

text: and

text: that

text: there

text: exists

text: a

text: time

text: t

text: and

text: an

text: agent

text: i

text: i

text: E

text: such

text: that

text: (i

text: i

text: during

text: t

text: [t

text: t

text: τ

text: T

text: D

text: We

text: ﬁrst

text: note

text: that

text: it

text: follows

text: from

text: and

text: Lemma

text: that

text: for

text: all

text: t

text: NT

text: V

text: V

text: V

text: (t,

text: x(t))

text: V

text: (t,

text: x(t))

text: V

text: i,

text: j

text: ij

text: Taking

text: the

text: derivative

text: of

text: V

text: along

text: the

text: trajectories

text: of

text: we

text: that

text: for

text: all

text: t

text: [t

text: t

text: +τ

text: ij

text: D

text: V˙

text: Le

text: x

text: x

text: e

text: x

text: )T

text: a

text: (t)(x

text: x

text: ∈N

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##


text: additional agent, labeled as agent 0, which plays as a reference or leader for the agents in the V V V V ∪{ } set . In view of this we also call an agent in a follower, and denote ¯ = 0 as the overall agent set. The overall communication in the network is described by a time-varying directed G V E · graph ¯ = (¯, ¯ ). Here for the sake of simplicity we continue to use σ( ) to denote the σ(t) σ(t) piecewise constant graph signal. We also make a standard dwell time assumption [17] on the switching signal σ(t). For the leader-follower communication graph, we introduce the following deﬁnition. G ∈ V Deﬁnition 4 (i). ¯ is leader connected if for any follower agent i there is a directed σ(t) G G path from the leader 0 to follower agent i in ¯ at time t. Moreover, ¯ is jointly leader σ(t) σ(t) G connected in the time interval [t , t ) if the union graph ¯([t , t )) is leader connected. 1 2 1 2 G (ii). ¯ is uniformly jointly leader connected if there exists a constant T > 0 such that σ(t) G ≥ the union graph ¯([t, t + T )) is leader connected for any t 0. G G ∞ (iii). ¯ is inﬁnitely jointly leader connected if the union graph ¯([t, )) is leader con- σ(t) ≥ nected for any t 0. For leader-follower networks, the evolutions of the follower state x (t) and the leader state i y(t) are givenby  (cid:80)   − − ∈ V  x˙ = f(t, x ) + ∈N a (t)(x x ) + b (t)(y x ), i , i i j i(σ(t)) ij j i i i (32) y˙ = f(y, t), where the nonlinear function f(x , t) and a (t) follow from the same deﬁnitions as those of i ij the leaderless case in (1), and b (t) > 0 is a piecewise continuous function marking the strength i ≤ of the edge (0, i), if any. Assume that there is a constant b∗ > 0 such that b∗ b (t) for all i ≥ ≥ t 0. We also assume that the initial time is t = t 0 and denote the initial state for the 0 ∈ R leader as y(t ) n. 0 For the leader-follower networks, we are interested in the following synchronization problems. Deﬁnition 5 (i) The multi-agent system (32) achieves global asymptotic synchronization if − ∈ V ≥ ∈ R ∈ R lim →∞(x (t) y(t)) = 0 for any i , any t 0, any x(t ) nN, and y(t ) n. t i 0 0 0 ≥ (ii) Multi-agent system (32) achieves global exponential synchronization if there exist γ 1 ≥ and λ > 0 such that there exist γ 1 and λ > 0 such that 19

text: additional

text: agent,

text: labeled

text: as

text: agent

text: which

text: plays

text: as

text: a

text: reference

text: or

text: leader

text: for

text: the

text: agents

text: in

text: the

text: V

text: V

text: V

text: V

text: set

text: In

text: view

text: of

text: this

text: we

text: also

text: call

text: an

text: agent

text: in

text: a

text: follower,

text: and

text: denote

text: as

text: the

text: overall

text: agent

text: set.

text: The

text: overall

text: communication

text: in

text: the

text: network

text: is

text: described

text: by

text: a

text: time-varying

text: directed

text: G

text: V

text: E

text: graph

text: Here

text: for

text: the

text: sake

text: of

text: simplicity

text: we

text: continue

text: to

text: use

text: σ(

text: to

text: denote

text: the

text: σ(t)

text: σ(t)

text: piecewise

text: constant

text: graph

text: signal.

text: We

text: also

text: make

text: a

text: standard

text: dwell

text: time

text: assumption

text: on

text: the

text: switching

text: signal

text: σ(t).

text: For

text: the

text: leader-follower

text: communication

text: graph,

text: we

text: introduce

text: the

text: following

text: deﬁnition.

text: G

text: V

text: Deﬁnition

text: (i).

text: is

text: leader

text: connected

text: if

text: for

text: any

text: follower

text: agent

text: i

text: there

text: is

text: a

text: directed

text: σ(t)

text: G

text: G

text: path

text: from

text: the

text: leader

text: to

text: follower

text: agent

text: i

text: in

text: at

text: time

text: t.

text: Moreover,

text: is

text: jointly

text: leader

text: σ(t)

text: σ(t)

text: G

text: connected

text: in

text: the

text: time

text: interval

text: [t

text: t

text: if

text: the

text: union

text: graph

text: ¯([t

text: t

text: is

text: leader

text: connected.

text: G

text: (ii).

text: is

text: uniformly

text: jointly

text: leader

text: connected

text: if

text: there

text: exists

text: a

text: constant

text: T

text: such

text: that

text: σ(t)

text: G

text: the

text: union

text: graph

text: ¯([t,

text: t

text: T

text: is

text: leader

text: connected

text: for

text: any

text: t

text: G

text: G

text: (iii).

text: is

text: inﬁnitely

text: jointly

text: leader

text: connected

text: if

text: the

text: union

text: graph

text: ¯([t,

text: is

text: leader

text: con-

text: σ(t)

text: nected

text: for

text: any

text: t

text: For

text: leader-follower

text: networks,

text: the

text: evolutions

text: of

text: the

text: follower

text: state

text: x

text: (t)

text: and

text: the

text: leader

text: state

text: i

text: y(t)

text: are

text: givenby

text: V

text: x˙

text: f(t,

text: x

text: ∈N

text: a

text: (t)(x

text: x

text: b

text: (t)(y

text: x

text: i

text: i

text: i

text: j

text: i(σ(t))

text: ij

text: j

text: i

text: i

text: i

text: y˙

text: f(y,

text: t),

text: where

text: the

text: nonlinear

text: function

text: f(x

text: t)

text: and

text: a

text: (t)

text: follow

text: from

text: the

text: same

text: deﬁnitions

text: as

text: those

text: of

text: i

text: ij

text: the

text: leaderless

text: case

text: in

text: and

text: b

text: (t)

text: is

text: a

text: piecewise

text: continuous

text: function

text: marking

text: the

text: strength

text: i

text: of

text: the

text: edge

text: i),

text: if

text: any.

text: Assume

text: that

text: there

text: is

text: a

text: constant

text: b∗

text: such

text: that

text: b∗

text: b

text: (t)

text: for

text: all

text: i

text: t

text: We

text: also

text: assume

text: that

text: the

text: initial

text: time

text: is

text: t

text: t

text: and

text: denote

text: the

text: initial

text: state

text: for

text: the

text: R

text: leader

text: as

text: y(t

text: n.

text: For

text: the

text: leader-follower

text: networks,

text: we

text: are

text: interested

text: in

text: the

text: following

text: synchronization

text: problems.

text: Deﬁnition

text: (i)

text: The

text: multi-agent

text: system

text: achieves

text: global

text: asymptotic

text: synchronization

text: if

text: V

text: R

text: R

text: lim

text: →∞(x

text: (t)

text: y(t))

text: for

text: any

text: i

text: any

text: t

text: any

text: x(t

text: nN,

text: and

text: y(t

text: n.

text: t

text: i

text: (ii)

text: Multi-agent

text: system

text: achieves

text: global

text: exponential

text: synchronization

text: if

text: there

text: exist

text: γ

text: and

text: λ

text: such

text: that

text: there

text: exist

text: γ

text: and

text: λ

text: such

text: that