Almost Disjoint Large Subsets of Semigroups

Lesson7_Martingale宋逢明金融工程习题Harrison and Kreps: Martingales and Arbitrage in Multiperiod Securities MktsJ. of Econ Theory 20(1979)Contingent claim valuation1.single period economy with uncertainty-The dates t=0,T; and consumption bundle (r,x)with x defined below-probability space(PF,,Ω)-M: a Subspace of x-Price system (M,∏); ∏is linear functional on M, in unit of consumption good in period 0.Def:A Price system (M,∏) is viable if ?an agent (represented by)and a bundle(r*,m*)R M∈?such that r*+∏(m*)≤0 and (r*,m*)(r, m) for all (r,m)R M∈?.S.t. r+∏(m)≤0Given viable price system(M, ∏)and contingent claim x∈X, what should be x’s price p in unit of time 0 consumption?-Ans: the extended price system on (M,x)should be viable, i.e., consistent with(M,∏).Theorem 1: A price system (M,∏)is viable iff ?an extension of ∏to all x that is strictly positive linear functional on X,call it ψ.Separating hyperplane theorem: suppose A and B are convexdisjoint subsets of R n There is some nonzero linear fanctional F s.t. F(x)≤F(y) for each x∈A and y∈B. Key steps of proof.Step 1: (if part) identifyon R Xas ≥:(r,x)(r′, x′) if r+ψ(x) ≥r′+ψ(x′) with this choice, (r*,m*)=(0,0)Step 2: only if part. Support (M,∏) is viable .Define two sets in R X ?:{}(,):(,)(0,0)G r x R X r x =∈?and {}(,):()0H r m R M r m =∈?+∏≤These two sets are disjoint and convex. Use separating Hyperplane theorem, ?continuous linear functional on R X φ?s.t.φ(r,x) ≥0 for G and H or x r 0),(≤φStep 3: choose φ(r,x)=r+ψ(x)Verify ①positive strictly is x )(ψ② m ψ=∏Corollary 1: If a price system(M,∏) is viable then for all ,x X ∈?some price that is consistent to (M,∏).Arbitrage price of x X ∈: the unique price for claim x that is consistent to (M,∏).Corolloary 2: If a price system (M,∏)is viable, then the price of x X ∈is determined by arbitrage iff the set {():x ψpositive linear functional ,and M ψ=∏} is unique. And this unique ():x ψis the arbitrage value of x.2. Multiperiod security market and SF simple trading strategy .Intertemperal information structure.-The economy spans: T periods: t=0,1,…T.-State of the economy: a set of possible paths of theeconomy from 0 to T, denoted by w. {}w Ω the set of all possible states-Event:-a subset of Ω-Two events are disjoint if 21E E φ?=-A partition of Ω is a collection of event {}n E E ,1, s.t.(),()i j i i i E E i jii E φ?=?≠?=Ω-The information about the state of economy at time t is represented by a partition of Ω:{},1,,:t t t t n E E σ= F -Information structure or Event treeThe true state of economy is gradually revealed over time: 二叉树2223()()S E S E =?recombined binomial.11123{,,}E w w w ={}0E =Ω1245{,}E w w =0E 11E12E21E 22E 23E24E{}0E =Ω11232342122334{{,,},{,,}}{{,},{,},{,}}E w w w w w w E w w w w w w ==-{},1,,:t t t t n E E σ= F then 1t t s for s +?≥F F-probability measure defined on the state space {}:w Ω∏=∏For any event E,w E w E ∏∑=∏∈Security price process and simple trading strategy -A security is a claim that pays ()t t d E at time t in the event Et t t E ∈F i.e. t d is a stochastic process that is measurable w.r.t. t F .-A basic security: pays $1 only at t in an event t t E ∈F .-Assume N+1 securities traded in security market. Let ,i t S be the price of security i att. ,i t S is a function of t E , i.e., ,i t S is measurable w.r.t. t F t 1,t n,t S =(S ,S ) , N dimension.-Simple trading strategy t θ: an (N ×1)-dimensional process that is adapted to t F , 0E 11E12E 22E23E 311E w =322E w = 333E w =344E w = 21Ei.e., t θ only depends on time t information.M-payoff generated by simple trading strategy-Self-financing simple trading strategy:11()Nt t t t t PL S S d θ+==-+∑ Let t d =0, in continuous time ()t o PL S dS θ=? in ito ’s sense.No arbitrage2.3.1 Definition: Arbitrage or free lunch: If ? SF t θ, let t t P S θ≡? ,① P 0≤0 and P T ≥0,with prob(P T >0)＞0,or ②P 0＜0 and P T ≥0.000()S θθ?∏=? linear, positive.2.3.2 Dynamic completeness: For any payoff x T , ? a simple trading strategy,000..()T T s t x S S dS θθ=?+??3. Equivalent martingale measure3.1 Def: On a probability space (,F Ω), define two measures P and Q. If for any F E ∈, ()0()0P E Q E >?>, then Q is equivalent to P.3.2 Def: Martingale: On a filtered probability space (P F t ,,Ω), S t is an adaptive stochastic process w.r.t. F t . If for any 0≤s ≤t, we have ()()p s E S t S s ??=??F , then S(t) is a martingale. P is the martingale measure4. Foundamental theorem4.1 Theorem 1: In the security market defined above, there exists no arbitrage iff there exists an equivalent martingale measure.4.2 Theorem 2: The market is dynamically complete iff there exists a unique equivalent martingale measure. (M=X) Sketch of proof: 4.1 M: the set of payoff genated by SF simple trading strategyStep 1: no arbitrage ∏? is positive linear functional on M.Step 2: Use theorem 1 from previous section (,)(,)M viable X ψ∏? extensionSuppose :s F R R →is linear. Then ?a unique ρ in s R s.t. for s x R ∈, we have F(x)=E(ρx). 2211()...(,,),()s s s sE x Px P x R LF p x R E x =++=Ω∈<∞. Step 3: Riesz representation Theorem: 220()()(,,)*.0*()[]0Tx y t t t t t x t x E x L F P E dP define dPstrctly positive P and P equivalent M E X E S dS S E dS ψρρρρψρψθθθθ=∈Ω<∞=?>?=∏?=+?== S is martingale under P*. Example: f r =010 10 1/3 1/3 1/3 11 9 11 10 8 111/4 1/5 11/20 1/4 1/2 1/2 1/5 1/5 3/5 14,9 w110,13 w210,8 w314,9 w410,13 w510,9 w612,10 w77,15 w87,10 w911234567892{{,,},{,,},{,,}}()F w w w w w w w w w F F σσ==。

a r X i v :m a t h /9303207v 1 [m a t h .L O ] 15 M a r 1993On closed P -sets with ccc in the space ω∗R.Frankiewicz(Warsaw)S.Shelah(Jerusalem)P.Zbierski(Warsaw)Abstract.It is proved that –consistently –there can be no ccc closed P -sets in the remainder space ω∗.In this paper we show how to construct a model of set theory in which there are no P -sets satisfying ccc (countable antichain condition)in the ultrafilter space ω∗=β⋄ω|\ω.The problem of the existence of such sets (which are generalizations of P -points)was known since some time and occurred explicitly in œvM-R—.In the proof we follow the construction from œS—of a model in which there are no P -points.A particular case of P -sets,which are supports of approximative measures has been settled in œM—,where the author shows that there can be no such measures on P (ω)/fin .(Under CH ,e.g.the Gleason space G (2ω)of the Cantor space is a ccc P -set in ω∗which carries no approximative measure).Sec.1.Closed P -sets in the space ω∗can be identified with P -filters F on ω.Thus,the dual ideal I ={ω\A :A ∈F }has the property:(1.1)If A n ∈I ,for n ∈ω,then there is an A ∈I such that A n ⊆∗A ,for each n ∈ω.Further,the countable chain condition imposed upon F implies that I is fat in the following sense (see œF-Z—):(1.2)if A n ∈I ,for n ∈ωand lim n min A n =∞,then there is an infinite Z ⊆ωsuch that n ∈Z A n ∈I .Indeed,let e n =A n \A ,where A ∈I is as in (1.1).Since min A n are arbitrarily large,we can find an infinite set Y ⊆ωsuch that the family {e n :n ∈Y }is disjoint.If{Y α:α<c }is an almost disjoint family of subsets of Y ,then the unionsS α= {e n :n ∈Y α},α<care almost disjoint and hence the closures S ∗αin the space ω∗are disjoint.By ccc we haveS ∗α∩ {B ∗:B ∈F }=∅,for some αand consequently S α∈I .It follows that th e unionn ∈Y αA n = n ∈Y α(A n ∩A )∪ n ∈Y α(A n \A )is in I as a subset of Sα∪A.Let usfix a given ccc P-filter F and its dual I.We shall define a forcing P=P(F).A partial ordering(T,≤T),where T⊆ω,will be called a tree,if for each i∈T the set of predecessors{j∈T:j≤T i}is linearly ordered andi≤T j implies i≤j,for all i,j∈T.We define a partial ordering for treesT≤t S iff(S,≤S)is a subordering of(T,≤T)and each branch of T contains cofinally a(unique)branch of S.There is a tree T0such that T0∈I and T0is order isomorphic to the full binary tree of heightω.Deleting the numbers≤n from T0we obtain a subtree denoted by T(n)(we haveT(n) 0≤t T(m),for n≤m).Let T consist of all the trees T∈I such thatT≤t T(n),for some n∈ω.Note that each tree T∈T hasfinitely many roots.Definition.Elements of the forcing P are of the form p=<T p,f p>,where T p∈Tand f p:T p−→{0,1}.The ordering of P is defined thusp≤q iffT p≤t T q and f p⊇f q.Let{bα:α<c}be afixed enumeration of all the branches of T0in V.For a generic G⊆P let T G= p∈G T p and f G= p∈G f p.Each branch B of T G contains cofinally a unique bα.Let us write B=Bαand defineXα={i∈ω:i∈Bαand f G(i)=1}Since T p∈I,for any p∈P,henceω\T p∩A is infinite,for each A∈F.It follows that the setsD Aαnε={p∈P:∃i>n⋄i∈b pαand f p(i)=ε|}are dense,for each A∈F,n∈ω,α<c andε=0,1(here b pαdenotes the branch of T p extending bα).Thus,P adds uncountably many almost disjoint Gregorieff-like sets.Sec.2.Let Q=Q(F)be a countable product of P=P(F).Thus the elements q∈Q can be written in the formq=<f q0,f q1,...>,where<dm(f q i),f q i>∈P,for each i<ω.By q(n)we denote the condition<g i:i<ω>whereg i= f q i|dm(f q i)(n),for i<nf q i for i≥nHere T(n)is a tree obtained from T by deleting the numbers≤n.Lemma 2.1.For each decreasing sequence p0≥p1≥...there is a q and an infinite Z⊆ωsuch thatq≤p(n)n,for each n∈Z.Proof.Let T ni=dm(f p n i),where p n=<f p n i:i<ω>.Since min T(n)ni ≥n,we may use(1.2)to define by induction a descending sequence Z0⊇Z1⊇...of infinite subsets ofωsuch thatn∈Z i T(n)ni is in I,for each i<ω.There is an infinite Z⊆ω,such that Z⊆∗Z i,for each i<ω.DefineT i=T ii∪ n∈Z T(n)niandf q i=f p i i∪ n∈Z f p n i|T(n)ni.Then,dm(f q i)=T i and q=<f q i:i<ω>is as required.QEDFor q∈Q and n∈ωlet S(q,n)be the set of all sequences s=<s0,...,s n−1> satisfying the following properties1.s0,...,s n−1arefinite zero-one functions.2.The domains t0=dm(s0),...,t n−1=dm(s n−1)arefinite trees such thatt0∩T(n)0=...=t n−1∩T(n)n−1=∅,where T0=dm(f q0),...,T n−1=dm(f q n−1)3.Ordered sums t0⊕T(n)0,...,t n−1⊕T(n)n−1are trees belonging to T.Note that from the definition of T it follows that S(q,n)is alwaysfinite.Let us denote s∗q(n)=<s0∪f q0,...,s n−1∪f q n−1,f q n,...>for q,n,s as above.Obviously,we have(2.2)the set{s∗q(n):s∈S(q,n)}is predense below q(n)(i.e.the boolean sum s∈S(q,n)s∗q(n)=q(n)).Now,we obtain easily an analogue of VI,4.5inœS—.(2.3)For arbitrary p∈Q,n<ωandτ∈V(Q) such that Q “τis an ordinal”there is a q≤p and ordinals{α(s):s∈S(p,n)} so thatq(n) “ sτ=α(s)”Indeed,if S(q,n)={s0,...,s m−1},then we define inductively conditions p0,...,p m so that p0=p and p k+1≤s k∗p(n)kis such thatp k+1 “τ=α”,for some ordinalα=α(s k)Now,q=s∗p(n)m,where s is such that p=s∗p(k)(we may assume s∈S(p,n)), satisfies(2.3).2.4.Theorem.Q isα-proper,for everyα<ω1,and has the strong P P-property.Proof.Let countable N≺H(κ)for sufficiently largeκ,be such that Q∈N and suppose that p∈Q∩N.To prove that Q is proper we have tofind a q≤p,which is N-generic.Let{τn:n<ω}be an enumeration of all the Q-names for ordinals,such that τn∈N,for n<ω.Using(2.3)we define inductively a sequence p0=p≥p1≥...and ordinalsα(n,s)so thatp(n)n“ i≤n sτi=α(n,s)”for each n<ω(i.e.in the n-th step we apply(2.3)for all namesτ0,...,τn).Note that the p′s andα′s can be found in N,since N≺H(κ).By Lemma2.1there is a q and an infinite Z⊆ωsuch thatq≤p(n)n,for each n∈Z.Hence also q(m)≤p(n)nholds for arbitrarily large n and all m<ωand thusq(m) “τn∈N”,for all n,m<ω.By III,2.6ofœS—,each q(m)is N-generic.To see that Q isα-proper let<Nξ:ξ≤α>be a continuous sequence of elementary countable submodels of H(κ)such that Q∈N0and<Nξ:ξ≤η>∈Nη+1,for eachη<α.Assume that Q is β-proper,for each β<αand let q 0∈Q ∩N 0.If α=β+1,we have a q ≤q 0which is N ξ-generic,for each ξ≤βand we may assume that the q (n )have the same property,for all n <ω.since N α≺H (κ)and all the parameters are in N α,such a q can be found in N αand as above we construct a q α≤q which is N α-generic and so are the q (n )α,for n <ω.Thus,q αand all the q (n )αare N ξ-generic for all ξ≤α.If αis a limit ordinal,we fix an increasing sequence <ξn :n <ω>such that α=sup n<ωξn and by the inductive hypothesis there is a sequence q 0≥q ξ0≥q ξ1≥...such that,for each n <ω,q ξn is N ξ-generic,for each ξ≤ξn and q ξn ∈N ξn +1and that q (m )ξn have the same propertyfor each m <ω.By Lemma 2.1there is a q ∈Q such that q ≤q (n )ξn ,for infinitely many n <ω.Thus,q ≤q 0and q is N ξ-generic for each ξ<αand hence also for each ξ≤α.Finally,to prove the P P -property let h :ω−→ωdiverge to infinity and suppose that p “f :ω−→ω”.Definek n =min {i :h (i )>2n ·card S (p,n )},for n <ωand,using (2.3),define inductively the sequence p =p 0≥p 1≥...such thatp (n )n “i<k n s ∈S (p i ,i )f (i )=α(s,i )”for each n <ωand some integers α(s,i )<ω.Let T be the tree built up of integers{α(s,i ):i <ωand s ∈S (p i ,i )}.If q ≤p (n )n ,for infinitely many n ,then we have q “f ∈Lim T ”and T ∩ωk n has less elements than h (k n ),for all n <ω,which finishes the proof.QEDThe last point to be discussed is how does Q =Q (F )act in the course of iteration.2.5.Lemma.If R is ωω-bounding (i.e.the set of old functions :ω−→ωdominates)and Q (F )is a complete subforcing of R ,then in V (R )the filter F cannot be extended to a ccc P -filter.Proof.Let X n αbe the α-th set added by n -th factor of the product Q =P ω.Supposethat for some r ∈R and a ccc P -filter E ∈V (R )we haver “F ⊆E ”Note that for each n <ω,the relation X n α∈E hold for at most countably many α’s,since E is ccc .Hence,there is an αsuch that for all n <ωwe have ω\X n α∈E and,since E is a P -filter,there is an A ∈E and a function g ,so that A ⊆ n<ω(ω\X n α)∪⋄0,g (n ))i.e.for some r 1≤r we have(2.6)r 1 “n<ω(ω\X n α)∪⋄0,g (n ))∈E ”Since R isωω-bounding we may assume that g∈V.By the assumption,Q is a complete subforcing of R and hence there is a q∈Q such that r is compatible with each q′≤q.On the other hand,since T n=dm(f q n)∈T,there is a set B∈I and an increasing sequence a0<a1<...such that T n\⋄0,a n)⊆B,g(n)<a n and⋄a n,a n+1)\B=∅, for each n<ω.Define q′≤q as follows.For a given n extend T n by adding elements of⋄a n,a n+1)\B on theα-th branch b qαand put f q′n(i)=1,for each i∈⋄a n,a n+1)\B. Obviously,we haveq′ “(ω\X nα)∪⋄0,g(n))∩⋄a n,a n+1)\B=∅”,for each nand henceq′ “ n<ω(ω\X nα)∪⋄0,g(n))\B∩ n<ω⋄a n,a n+1)=∅”Consequently q′ “ n<ω(ω\X nα)∪⋄0,g(n))⊆∗B”,which contradicts(2.6).QED The rest of the proof is routine.Beginning with a model V of2ω=ω1and2ω1=ω2 we iterate with countable supports the forcings Q(F),for all ccc P-filters F booked at each stageα<ω2of the iteration.FromœS—,V.4we know that the resulting forcing R (obtained afterω2stages)is proper andωω-bounding.Hence,in V⋄G|there are no ccc P-sets.ReferencesœF-Z—R.Frankiewicz,P.Zbierski“Strongly discrete subsets inω∗”Fund.Math.129 (1988)pp173-180œM—A.H.Mekler“Finitely additive measures on N and the additive property”Proc.AMS Vol.92No3Nov.1984pp439-444œvM-R—J.vanMill,G.M.Reed editors“Open problems in topology”,North Holland Elsevier Science Publishers B.V1990œS—S.Shelah“Proper forcing”Lecture Notes in Mathematics940Springer Verlag Ryszard Frankiewicz Institute of Mathematics,Polish Academy of Sciences,War-saw,PolandSaharon Shelah Institute of Mathematics,The Hebrew University,Jerusalem,Israel Pawe l Zbierski Institute of Mathematics,Warsaw University,Warsaw,Poland。

a r X i v :m a t h /0703504v 2 [m a t h .C A ] 11 O c t 2007Ubiquity of simplices in subsets of vector spaces over finitefieldsDerrick Hart and Alex IosevichFebruary 2,2008AbstractWe prove that a sufficiently large subset of the d -dimensional vector space over a finite field with q elements,F d q ,contains a copy of every k -simplex.Fourier analytic methods,Kloosterman sums,and bootstrapping play an important role.Contents1Introduction12Preliminaries and Definitions32.1Notation ......................................33Proof of the main result43.1Proof of Theorem 3.1-the main result reformulated in terms of ”distances”.54Proof of Lemma 3.275Estimation of the Fourier transform of the sphere:proof of Lemma 3.391IntroductionMany problems in combinatorial geometry ask,in one form or another,whether a certain structure must be present in a set of sufficiently large size.Perhaps the most celebrated result of this type is Szemeredi’s theorem ([10])which says that if a subset of the integers has positive density,then it contains an arbitrary large arithmetic progression.The conclusion has recently been extended to the subsets of prime numbers by Green and Tao ([4]).In Euclidean space,a result due to Katznelson and Weiss ([3])says that a subset of Euclidean space of positive Lebesgue upper density contains every sufficiently large distance.A1subsequent result by Bourgain([1]),says that a subset of R k of positive Lebesgue upper density contains an isometric copy of all large dilates of a set of k points spanning a(k−1)-dimensional hyperplane.Ergodic theory has been used to show that positive upper density implies that the set contains a copy of a sufficiently large dilate of every convex polygon withfinitely many sides.See,for example,a recent survey by Bryna Kra([7]).Let F d q be a d-dimensional vector space over afinitefield F q of odd characteristic.A plausible analogy to Bourgain’s result([1])in this context would be to consider whether a subset of positive density contains a isometric copy of a set of k points spanning a(k−1)-dimensional hyperplane.It turns out however,that the positive density condition is much too strong in the context of vector spaces overfinitefields and the same conclusion follows from a much weaker assumption on the size of the underlying set.Definition1.1.Let a k-simplex be a set of k+1points in general position,which means that no n+1of these points,n≤k,lie in a(n−1)-dimensional sub-space of F d q.Definition1.2.We say that a linear transformation T on F d q is an isometry if||T x||=||x||,where||x||=x21+x22+···+x2d,an element of F q.The question we ask in this paper is how large does E⊂F d q need to be in order to be sure that it contains a copy of every k-simplex.Our main result is the following. Theorem1.3.Let E⊂F d q,d> k+12 ,such that|E|≥Cq k2with a sufficiently large constant C>0.Then E contains an isometric copy of every k-simplex.√Note that we obtain non-trivial results only when k<<2Preliminaries and DefinitionsLet F d q be the d-dimensional vector space over thefinitefield F q.The Fourier transform ofa functionf:F d q→Cis given byf(m):=q−d x∈F d q f(x)χ(−x·m),whereχis an additive character on F q.The orthogonality property of the Fourier Transform says thatq−d x∈F d qχ(−x·m)=1for m=(0,...,0)and0otherwise yields many standard properties of the Fourier Trans-form.We summarize some of the properties of the Fourier Transform as follows.Lemma2.1(The Fourier Transform).Letf,g:F d q→C.ˆf(0,...,0)=q−d x∈F d q f(x),(Plancherel)q−d x∈F d q f(x)ˆg(m),(Inversion)f(x)= m∈F d qˆf(m)χ(x·m).2.1NotationThroughout the paper X Y means that there exists C>0such that X≤CY,X Y means Y X,and X≈Y if both X Y and X Y.Along the same lines,X≪Ymeans that XY→1as q→∞.33Proof of the main resultEven though afinitefield with q elements,F q,is not a metric space,we define the”distance”between two points x and y in F d q by the formula||x−y||=(x1−y1)2+(x2−y2)2+···+(x d−y d)2.The same notion of”distance”was used by Bourgain,Katz and Tao([2]),and Iosevich and Rudnev([5])in their study of the Erd˝o s distance problem in vector spaces overfinitefields.As we noted above,a geometric justification of this notion of distance is that an orthogonal transformation on F d q,a matrix O such that O t·O=I,preserves this notion of a”distance”.Represent a k-simplex in a subset E⊂F d q on k+1points recursively by settingT l k={(x0,...,x k−1,x k)∈T l k−1×E:||x0−x k||=t1,k,||x1−x k||=t2,k,...,||x k−1−x k||=t k,k}, for l k=l k−1∪{t1,k,...t k,k},t i,j∈F∗q whereT l1={(x0,x1)∈E2:||x0−x1||=t1,1}.This representation does not,in general,always embody a simplex as T k lk is not guaran-teed to be in general position.However,as we show below,”legitimate”k-simplices are equivalent up to an orthogonal transformation.Theorem3.1.Let E⊂F d q,d> k+12 ,such that|E|≥Cq k2,with a sufficiently large constant C.Then for every side length set l k,l k∈(F∗q)(k+12)we have that|T l k|>0. Furthermore,|T l k|∼|E|k+1q−(k+12).Using this theorem we recover the main result of the paper using the following linear algebraic observation.Lemma3.2.Let P be a simplex with vertices V0,V1,...,V k,V j∈F d q.Let P′be another simplex with vertices V′0,V′1,...,V′k.Suppose that||V i−V j||=||V′i−V′j||(3.1) for all i,j.Then there exists an orthogonal,affine transformation O on F d q such that O(P)=P′.43.1Proof of Theorem3.1-the main result reformulated in terms of”dis-tances”The proof proceeds by induction.Thefirst step is the case k=2.For a set E we define the characteristic or indicator function to be E(x).Now define the sphere of radius t1,1∈F∗q to be={x∈F d q:||x||=t1,1},S t1,1then|T l1|=|{(x0,x1)∈E×E:||x0−x1||=t1,1}|= x0,x1E(x0)E(x1)S t1,1(x0−x1).In order to obtain information from this quantity the behavior of incidences of spheres and points in E will be critical.The following classical fact,whose proof will be given in a subsequent section,states that the sphere has optimal Fourier decay away from the origin. Lemma3.3.Let S t,t∈F∗q be defined as above.If m=(0,...,0)then| S t(m)| q−d+1,qand using Lemma3.3once again,|R| q2d·q−d+12·|E|,5which is smaller than M if|E|≥Cq d+12,we get the”statistically expected”number of distances,|T l1|∼|E|2Then for each term in the sum corresponding to a partition I∪I′we apply Cauchy-Schwarz,m i=0(i∈I)m i=0(i/∈I)| T l k−1(−m0,...,−m k−1)|| E(m0+···+m k−1)| A1/2B1/2. Applying Plancherel and the induction hypothesis,A≤ m0,...,m k−1| T l k−1(−m0,...,−m k−1)|2=q−kd|T l k−1|∼q−kd q−(k2)|E|k.NowB= m i(i∈I′) E i∈I′m i 2=q|I′|d q−2d|E|.This implies that|R| q kd4|E|k+12q−k(k+1)2.The term R is smaller than,say,M2q−k(k+1)2≤C|E|k+1q−(k+12),with a sufficiently large constant C,which happens if|E|≥C′q k2,with a sufficiently large constant C′depending on the constants implicit in the estimates above.This completes the proof.4Proof of Lemma3.2To prove Lemma3.2,letπr(x)denote the r th coordinate of x.There is no harm in assuming that V0=(0,...,0).We may also assume that V1,...,V k are contained in F k q. The condition(3.1)implies thatkr=1πr(V i)πr(V j)=k r=1πr(W i)πr(W j).(4.1)7Let T be the linear transformation uniquely determined by the conditionT(V i)=V′i.In order to prove that T is orthogonal,it suffices to show that||T x||=||x||for any x=(0,...,0).Since V j s form a basis,by assumption,we havex= i t i V i,so it suffices to show that||x||= r i,j t i t jπr(V i)πr(V j)= r i,j t i t jπr(V′i)πr(V′j)=||T x||,which follows immediately from(4.1).Observe that we used the fact that orthogonality of T,the condition that T t·T=I is equivalent to the condition that||T x||=||x||.To see this observe that to show that T t·T=I it suffices to show that T t T x=x for all non-zero x.This,in turn,is equivalent to the statement that<T t T x,x>=||x||,where<x,y>=k i=1x i y i.Now,<T t T x,x>=<T x,T x>by definition of the transpose,so the stated equivalence is established.This completes the proof of Lemma3.2.85Estimation of the Fourier transform of the sphere:proof of Lemma 3.3The proof of Lemma 3.3is fairly standard,but we outline the argument for reader’s con-venience.For any m ∈F d q ,we haveS t (m )=q −d x ∈F d qq −1 j ∈F q χ(j ( x −t ))χ(−x ·m )=q −1δ(m )+q −d −1j ∈F ∗qχ(−jt )x χ(j x )χ(−x·m )=q −1δ(m )+Q d q −d +24j+jtηd (−j ),(5.1)where the notation δ(m )=1if m =(0...,0)and δ(m )=0otherwise.In the last line wehave completed the square,changed j to −j ,and used d times the Gauss sum equalityc ∈F qχ(jc 2)=η(j ) c ∈F qη(c )χ(c )=η(j ) c ∈F ∗qη(c )χ(c )=Q√qif a =0.9References[1]J.Bourgain,A Szemer´e di type theorem for sets of positive density in R k.Isr.J.Math54(1986)307-316.[2]J.Bourgain,N.Katz and T.Tao,A sum-product estimate infinitefields,and appli-cations,Geom.Func.Anal.14(2004)27-57.[3]H.Furstenberg,Y.Katznelson,and B.Weiss,Ergodic theory and configurations insets of positive density.In Mathematics of Ramsey theory,pages184-198,Algorithms Combin.,5,Springer,Berlin,(1990).[4]B.Green and T.Tao,The primes contain arbitrarily long arithmetic progressions,Ann.of Math.(to appear),(2007).[5]A.Iosevich and M.Rudnev,Erdos distance problem in vector spaces overfinitefields,Transactions of the AMS(accepted for publication)(2007).[6]A.Magyar,K-point configurations in sets of positive density of Z n,preprint.[7]B.Kra,Ergodic methods in additive combinatorics,Lecture notes from the MontrealWorkshop on Additive Combinatorics(2006).[8]J.Matousek,Lectures on Discrete Geometry,Graduate Texts in Mathematics,Springer202(2002).[9]L.A.Sz´e kely,Remarks on the chromatic number of geometric graphs.In Graphs andother combinatorial topics(Prague,1982),pages312-315,Algorithms Combin.,59, Teubner-Texte Math,Leipzig,1983.[10]E.Szemer´e di,On sets of integers containing no k elements in arithmetic progression.Acta.Arith.27(1975)199-245.[11]A.Weil,On some exponential sums,Proc.Nat.Acad.Sci.U.S.A.34(1948)204-207.10。

近世代数中英对照学习一、字母表atom：原子automorphism：自同构binary operation：二元运算Boolean algebra：布尔代数bounded lattice：有界格center of a group：群的中心closure：封闭commutative(Abelian) group：可交换群，阿贝尔群commutative(Abelian) semigroup：可交换半群comparable：可比的complement：补concatenation：拼接congruence relation：同余关系cycle：周期cyclic group：循环群cyclic semigroup：循环半群determinant：行列式disjoint：不相交distributive lattice：分配格entry：元素epimorphism：满同态factor group：商群free semigroup：自由半群greatest element：最大元greatest lower bound：最大下界，下确界group：群homomorphism：同态idempotent element：等幂元identity：单位元，么元identity：单位元，么元inverse：逆元isomorphism：同构join：并kernel：同态核lattice：格least element：最小元least upper bound：最小上界，上确界left coset：左陪集lower bound：下界lower semilattice：下半格main diagonal：主对角线maximal element：极大元meet：交minimal element：极小元minimal generating set：最小生成集monomorphism：单同态normal subgroup：正规子群，不变子群octic group(group of symmetries of the square)：八阶群，平方对称群orbit：轨道order：群的阶，元素的阶partially ordered set (poset)：偏序集partition：分割quotient semigroup：商半群retract：收缩retraction map：收缩映射semigroup with identity, monoid：含么半群，独异点semigroup：半群semilattice：子半格string, word：字符串，单词subgroup：子群sublattice：子格subsemigroup：子半群symmetric group：对称群total ordering, chain, linear ordering：全序，链，线序upper bound：上界upper semilattice：上半格二、本章内容及教学要点：8.1Partially Ordered Sets Revisited教学内容：poset，(least)upper bound，greatest element，(greatest)lower bound，least element，maximal(minimal) element，upper(lower) semilattice8.2Semigroups and Semilattices教学内容: semigroup，Abelian semigroup，monoid，subsemigroup，free semigroup，minimal generating set，congruence relation，quotient semigroup，semilattice，idempotent element8.3 Lattices教学内容：lattice，sublattice，bounded lattice，distributive lattice，Boolean algebra，complement，atom8.4 Groups教学内容：group，identity，inverse，commutative(Abelian) group，order，subgroup，cyclic group，left coset8.5 Groups and Homomorphisms教学内容：monomorphism，epimorphism，isomorphism，normal subgroup，octic group(group of symmetries of the square)定理证明及例题解答三、前言代数的概念与方法是研究计算机科学和工程的重要数学工具. 众所周知，在许多实际问题的研究中都离不开数学模型，而构造数学模型就要用到某种数学结构，而近世代数研究的中心问题是代数系统的结构：半群、群、格与布尔代数等等. 近世代数的基本概念、方法和结果已成为计算机科学与工程领域中研究人员的基本工具. 在研究形式语言与自动机理论、编码理论、关系数据库理论、抽象数据类型理论中，在描述机器可计算的函数、研究计算复杂性、刻画抽象数据结构、研究程序设计学中的语义学、设计逻辑电路中有着十分广泛的应用.为什么要研究代数系统？代数是专门研究离散对象的数学，是对符号的操作.它是现代数学的三大支柱之一（另两个为分析与几何）.代数从19世纪以来有惊人的发展，带动了整个数学的现代化.随着信息时代的到来，计算机、信息都是数字（离散化）的，甚至电视机．摄像机、照相机都在数字化.知识经济有人也称为数字经济.这一切的背后的科学基础，就是数学，尤其是专门研究离散对象的代数.代数发端于“用符号代替数”，后来发展到以符号代替各种事物.在一个非空集合上，确定了某些运算以及这些运算满足的规律，于是该非空集合中的元素就说是有了一种代数结构.现实世界中可以有许多具体的不相同的代数系统. 但事实上，不同的代数系统可以有一些共同的性质. 正因为此，我们要研究抽象的代数系统，并假设它具有某一类具体代数系统共同拥有的性质.任何在这个抽象系统中成立的结论，均可适用于那一类代数系统中的任何一个.代数学历史悠久. 代数的发展可分成两个阶段. 19世纪这前的代数称为古典代数，19世纪至今的代数称为近世代数（抽象代数）.远在古希腊时期，人们就知道可以用符号代表所解问题中的未知数，并且这些符号可以像数一样进行运算，直到获得问题的解.古典代数的基本研究对象是方程，它是以讨论方程的解法为中心. 在古典代数中，每一个符号代表的总是一个数，但这个数可以是整数也可以是实数. 古典代数的主要目标是用代数运算解一元多次方程. 它成功地解决了一元二次、一元三次和一元四次方程的求解问题.19世纪初，人们逐渐认识到，符号不仅可以代表数，而且可以代表任何事物. 在这种思想认识的支配下，人们开始将任意集合上所进行的代数运算作为研究的对象，从而出现了近世代数体系和方法.19世纪30年代，在寻找一元五次方程根式求解方法的过程中，年青的法国数学家伽罗瓦(E. Galois)首次得出了群的概念—用置换群的方法彻底证明了高于四次的代数方程的根式不可解性. 起初他的奇思妙想和巧妙方法虽然并不被当时人接受和理解，却发展出了一门新的学科—抽象代数学.抽象代数学的研究对象是抽象的，它不是以某一具体事物为研究对象，而是以一大类具有共同性质的事物为研究对象. 因此其研究成果适用于这一类事物中的每一个，从而收到事半功倍之效.抽象代数学的主要内容是研究各种各样的代数系统.它把一些形式上很不相同的代数系统，用统一的方法描述、研究和推理，从而得到反映出它们共性的一些本质的结论，然后再把这些结论应用到具体的代数系统中. 从而抽象产生了广泛的应用.抽象代数学在计算机中有着十分重要的应用. 100多年来，随着科学的发展，抽象代数越来越显示出它在数学的各个分支、物理学、化学、力学、生物学等科学领域的重要作用. 抽象代数的概念和方法也是研究计算科学的重要数学工具.有经验和成熟的计算科学家都知道，除了数理逻辑外，对计算科学最有用的数学分支学就是代数，特别是抽象代数. 抽象代数是关于运算的学问，是关于计算规则的学问.在许多实际问题的研究中都离不开数学模型，而构造数学模型就要用到某种数学结构，而抽象代数研究的中心问题就是一种很重要的数学结构—代数系统：半群、群、格与布尔代数等等. 计算科学的研究也离不开抽象代数的应用：半群理论在自动机理论和形式语言中发挥了重要作用；有限域理论是编码理论的数学基础，在通讯中起过重要的作用；至于格和布尔代数则更不用说了，是电子线路设计、电子计算机硬件设计和通讯系统设计的重要工具.另外描述机器可计算的函数、研究算术计算的复杂性、刻画抽象数据结构、描述作为程序设计基础的形式语义学，都需要抽象代数知识.这一章我们将介绍近世代数中最基本的代数系统：群和半群，它们在计算学科中有十分广泛的应用：半群在形式语言和自动机理论中有着重要的应用，群则可应用于编码理论之中.四、中英对照8.1 Partially Ordered Sets Revisited定义8.1.1 A relation R on A is a partial ordering(偏序) if it is reflexive, antisymmetric, and transitive.If the relation R on A is a partial ordering, then (A,R) is a partially ordered set or poset (偏序集)with ordering R.由于集合中的偏序关系是Z，R上的“≤”、“≥”的推广，故常用“≤”表示一般的偏序关系，偏序集用(A, ≤)表示. Note that the symbol ≤ is being used to denote the distinct partial orders.定义8.1.2Two elements a and b of the partially ordered set (S,≤) are comparable if either a≤b or b≤a. If every two elements of a poset (S, ≤) are comparable,then ≤ is a total ordering.在一个偏序集中，往往有一些特殊元素需要加以注意和研究：定义8.1.3Let (A, ≤) be a poset and B a nonempty subset of A. An element a in A is called an upper bound of B(B的上界)if b≤a for all b in B. The element a is called a least upper bound(B 的上确界) of B if (1) a is an upper bound of B and (2) any other upper bound a1of B, if exists, then a≤a1.An element a in B is called a greatest element(B的最大元) of B if x≤a for all x in B.An element a in A is called a lower bound of B(B的下界)if a≤b for all b in B. The element a is called a greatest lower bound(B的下确界) of B if (1) a is a lower bound of B and (2) any other lower bound a1 of B, if exists, then a1≤a. An element a in B is called a least element(B的最小元) of B if a≤x for all x in B.定义8.1.4Let (A, ≤) be a poset and B a nonempty subset of A. An element a in B is called a maximal element of B(B的极大元)if for every element b of B, a≤b implies a=b. An element a in B is called a minimal element of B(B的极小元)if for every e lement b of B, b≤a implies a=b.例8.1.1 Let A be the poset of nonnegative real numbers with the usual partial order ≤.Then 0 is a minimal element of A. There are no maximal element of A. The poset Z with the usual partial order ≤ has no minimal elements a nd no maximal elements.例8.1.2 Let A={a,b,c}. Then in the poset (P(A),⊆), the empty set Φis a least element of A, and the set A is a greatest element of A.例8.1.3 设A=P({a，b，c})，偏序关系为集合的包含关系“⊆”，B={{b，c}，{a，c}}，则B的上界为{a，b，c}，下界为{c}，Ф；最大(小)元不存在，极大(小)元都是{b，c}，{a，c}.例8.1.4 设A={2，3，4，6，7，8，12}，A上的偏序关系为|(整除关系)；B={8，12}，C={2，4，12}，则B无上界，下界为2，4；最大(小)元无，极大(小)元8，12；C的上界12，下界为2；最大元为12，最小元为2，极大元12，极小元为2.定理8.1.1 Let A be a finite nonempty p oset with partial order ≤. Then A has at least one maximal element and at least one minimal element.定理8.1.2 A poset has at most one greatest element and at most one least element.定理8.1.3 Let (A, ≤) be a poset. Then a nonempty subset B of A has at most one lub and at most glb.(设(A, ≤)为偏序集，Φ≠B⊆A. 若B有上(下)确界，则它们是惟一的)证明定理8.1.3定义8.1.5 A poset A for which all two-element subsets have a least upper bound in A is called an upper semilattice(上半格).In an upper semilattice A, we can define a binary operation ∨(+) as a∨b=lub{a,b}. Then (A, ∨) is an algebraic structure.定义8.1.6 A poset A for which all two-element subsets have a greatest lower bound in A is called an lower semilattice(下半格).In a lower semilattice A, we can define a binary operation ∧(〃) as a∧b=glb{a,b}. Then (A, ∧) is an algebraic structure.定理8.1.4(a)Let A be a n upper semilattice. Then for all a,b,c∈A, a∨(b∨c)=(a∨b)∨c, a∨a=a and a∨b=b∨a.(b) Let A be a lower semilattice.Then for all a,b,c∈A, a∧(b∧c)=(a∧b)∧c, a∧a=a and a∧b=b∧a.ASSIGNMENTS：PP209-210：6，8，9，10，11，12，30，328.2Semigroups and Semilattices定义8.2.1 A binary operation(二元运算)on the set S is a function f: S×S→S.A binary operation exhibits the property of closure wherein the result of the operation on two members a and b of S is also a member of S.定义8.2.2 A set S with a binary operation﹡on S such that for all a,b and c in S, (a﹡b)﹡c=a﹡(b﹡c) is called a semigroup(半群) and is denoted by (S,﹡) of simply S if the operation is understood.设(S,﹡)是一个代数结构. 若﹡是一个可结合的二元运算，即：∀a，b，c∈S，(a﹡b)﹡c=a﹡(b﹡c)，则称(S,﹡)为半群.定义8.2.3Let (S,﹡) be a semigroup. If a﹡b=b﹡a for all a,b in S, then (S,﹡) is called a(commutative) Abelian semigroup(可交换半群，阿贝尔半群). If there is an element 1 in (S,﹡) such that 1﹡a=a﹡1=a for all a in S, then 1 is called the identity(单位元，么元) of (S,﹡) and (S,﹡) is called a semigroup with identity or a monoid(含么半群，独异点).例8.2.1 (Z,+)，(Z,×)都是半群；(Z,－)不是半群；设A为任一集合，则(P(A),∪)，(P(A),∩)都是半群. (Z,+)，(Z,×)，(P(A),∪)，(P(A),∩)都是可交换半群. (Z,+)，(Z,×)都是含么半群，么元分别是0和1. (P(A),∪)，(P(A),∩)也都是含么半群，么元分别是Φ和A.定义8.2.4Let (S,﹡) be a semigroup and T be a nonempty subset of S.If ﹡is a binary operation on T, then T is a subsemigroup(子半群) of S.(T, ﹡) is a subsemigroup of (S, ﹡) if and only if T is a nonempty subset of S and for every a, b∈T, a﹡b∈T.例8.2.2 ({所有偶数},+)是(Z，+)的子半群.例8.2.3 Let S be the set of all functions from a nonempty set A to itself with the binary operation composition of functions. Then S is a semigroup and the identity function I:A→A, defined by I(a)=a for all a∈A, is the identity of A so that S is a monoid.例8.2.4 设A是有限个符号组成的集合，称为字母表，A上的串就是A 中有限个字母组成的有序集合，空串记为 .A*表示A上的串集合，A*上的连接运算 定义为α,β∈A*，α β=αβ，则(A*, )是一个含么半群，称为由A上的自由半群(The free semigroup on the alphabet A).例8.2.5 Let Z n={[0],[1],[2],…,[n-1]} be the set of integers modulo n. Then (Z n,+) and (Z n,〃) are both commutative monoid.定义8.2.5Let (S,﹡) be a semigroup and a be a element of S. Define a n recursively by a1=a and a n=a﹡a n-1 for n>1.Obviously, a k﹡a m=a k+m for all integers k,m>0.定义8.2.6Let (S,﹡) be a semigroup and a be a element of S. Let the set <a>={a n:n>0}={a,a2,a3,…}.Then <a> is a subsemigroup of S. It is called the cyclic semigroup generated by a(由a生成的循环子半群).定理8.2.1 Let (S,﹡) be a semigroup and a1,a2,…,a k∈S.Let A={a1,a2,…,a k} and A*=<a1,a2,…,a k> be the set consisiting of all finite products of a1,a2,…,a k.Then A* is a semigroup. Furthermore, A* is the smallest semigroup of S containing A.定义8.2.7The semigroup A* is called the semigroup generated by A. If for every proper subset B of A, B*≠A*, then A is called a minimal generating set of A*(最小生成集).定义8.2.8Let (S,﹡) and (T,〃) be semigroups and f:S→T be a function such that f(a﹡b)=f(a)〃f(b) for all a,b in S. The function f is called a homomorphism from S to T (从S到T的同态映射).定理8.2.2 Let (S,﹡) and (T,〃) be semigroups and f:S→T be a homomorphism from S to T.(a) If S1 is a subsemigroup of S, then f(S1) is a subsemigroup of T.(b) If T1 is a subsemigroup of T, then f-1(T1) is a subsemigroup of S.定义8.2.9Let (S,﹡) be a semigroup and R be an equivalence relation on S. If R has the property that if aRb and cRd then (a ﹡c)R(b﹡d) for all a,b,c,d ∈S, Then R is called a congruence relation(同余关系).定理8.2.3 The equivalence classes of a congruence relation R on a semigroup （S,﹡) form a semigroup under the binary operation 。

英语专八阅读理解模拟试题(附带翻译及解析)考研英语阅读理解模拟试题及解析一The majority of successful senior managers do not closely follow the classical rational model of first clarifying goals, assessing the problem, formulating options, estimating likelihoods of success, making a decision, and only then taking action to implement the decision. Rather, in their day-by-day tactical maneuvers, these senior executives rely on what is vaguely termed intuition to manage a network of interrelated problems that require them to deal with ambiguity, inconsistency, novelty, and surprise；and to integrate action into the process of thinking.Generations of writers on management have recognized that some practicing managers rely heavily on intuition. In general, however, such writers display a poor grasp of what intuition is. Some see it as the opposite of rationality; others view it as an excuse for capriciousness.Isenberg&#39;s recent research on the cognitive processes of senior managers reveals that managers&#39; intuition is neither of these. Rather, senior managers use intuition in at least five distinct ways. First, they intuitively sense when a problem exists. Second, managers rely on intuition to perform well-learned behavior patterns rapidly. This intuition is not arbitrary or irrational, but is based on years of painstaking practice and hands-on experience that build skills. A third function of intuition is to synthesize isolated bits of data and practice into an integrated picture, often in an Aha！experience. Fourth, some managers use intuition as a check on the results of more rational analysis. Most senior executives are familiar with the formal decision analysis models and tools, and those who use such systematic methods for reaching decisions are occasionally leery of solutions suggested by these methods which run counter to their sense of the correct course of action. Finally, managers can use intuition to bypass in-depth analysis and move rapidly to engender a plausible solution. Used in this way, intuition is an almost instantaneous cognitive process in which a manager recognizes familiar patterns.One of the implications of the intuitive style of executive management is that thinking is inseparable from acting. Since managers often know what is right before they can analyze and explain it, they frequently act first and explain later. Analysis is inextricably tied to action in thinking/acting cycles, in which managers develop thoughts about their companies and organizations not by analyzing a problematic situation and then acting, but by acting and analyzing in close concert.Given the great uncertainty of many of the management issues that they face, senior managers often instigate a course of action simply to learn more about an issue. They then use the results of the action to develop a more complete understanding of the issue. One implication of thinking/acting cycles is that action is often part of defining the problem, not just ofimplementing the solution.1. According to the text, senior managers use intuition in all of the following ways EXCEPT to[A] Speed up of the creation of a solution to a problem.[B] Identify a problem.[C] Bring together disparate facts.[D] Stipulate clear goals.2. The text suggests which of the following about the writers on management mentioned in line 1, paragraph 2？[A] They have criticized managers for not following the classical rational model of decision analysis.[B] They have not based their analyses on a sufficiently large sample of actual managers.[C] They have relied in drawing their conclusions on what managers say rather than on what managers do.[D] They have misunderstood how managers use intuition in making business decisions.3. It can be inferred from the text that which of the following would most probably be one major difference in behavior between Manager X, who uses intuition to reach decisions, and Manager Y, who uses only formal decision analysis？[A] Manager X analyzes first and then acts；Manager Y does not.[B] Manager X checks possible solutions to a problem by systematic analysis；Manager Y does not.[C] Manager X takes action in order to arrive at the solution to a problem；Manager Y does not.[D] Manager Y draws on years of hands-on experience in creating a solution to a problem；Manager X does not.4. The text provides support for which of the following statements？[A] Managers who rely on intuition are more successful than those who rely on formal decision analysis.[B] Managers cannot justify their intuitive decisions.[C] Managers&#39;&#39; intuition works contrary to their rational and analytical skills.[D] Intuition enables managers to employ their practical experience more efficiently.5. Which of the following best describes the organization of the first paragraph of the text？[A] An assertion is made and a specific supporting example is given.[B] A conventional model is dismissed and an alternative introduced.[C] The results of recent research are introduced and summarized.[D] Two opposing points of view are presented and evaluated.答案与考点解析1. 「答案」D「考点解析」这是一道归纳推导题。

PROCEEDINGS OF THEAMERICAN MATHEMATICAL SOCIETYVolume 133,Number 9,Pages 2737–2739S 0002-9939(05)07824-XArticle electronically published on March 22,2005ALMOST-DISJOINT CODINGAND STRONGLY SATURATED IDEALSPAUL RSON(Communicated by Alan Dow)Abstract.We show that Martin’s Axiom plus c =ℵ2implies that there isno (ℵ2,ℵ2,ℵ0)-saturated σ-ideal on ω1.Given cardinals λ,κand γ,a σ-ideal I on a set X is said to be (λ,κ,γ)-saturated if for every set {A α:α<λ}⊂P (X )\I there exists a set Y ∈[λ]κsuch that for all Z ∈[Y ]γ, {A α:α∈Z }∈I .Laver [6]was the first to show the consistency of an (ℵ2,ℵ2,ℵ0)-saturated ideal on ω1,using a huge cardinal.Shelah [10]later showed that the nonstationary ideal on ω1restricted to a given stationary set can be (ℵ2,ℵ2,ℵ0)-saturated,using a supercompact cardinal.The cardinal characteristic ap is defined to be the least κsuch that there exist an almost disjoint family {e α:α<κ}(i.e.,each e αis an infinite subset of ω,and for each distinct pair α,β<κ,e α∩e βis finite)and a set A ⊂κsuch that for no x ⊂ωdoes it hold for all α<κthat α∈A if and only if e α∩x is infinite (in [5]we called this q ,but [1]shows that we should not have,as consistently every set of reals of cardinality ap is a Q-set).We let c denote the cardinality of the continuum.It follows easily that 2γ=c for every infinite γ<ap .Given a cardinal γ,MA γis the variant of Martin’s Axiom that says that if P is a c.c.c.partial order and D α(α<γ)are dense subsets of P ,then there is a filter G ⊂P such that G ∩D αis nonempty for each α<γ.It is a standard fact that MA γimplies that ap >γ[4].In this note,we show that the statement ap =c =ℵ2implies that there is no countably complete (ℵ2,ℵ2,ℵ0)-saturated σ-ideal on ω1.This contradicts state-ments in [7,8]to the effect that the axiom PFA (see [10])had been shown to be consistent with the existence of a stationary subset of ω1such that the nonstation-ary ideal restricted to this set is (ℵ2,ℵ2,ℵ0)-saturated.This situation is addressed by Nyikos in [9]and in another corrigendum to appear.For a fixed cardinal κ,an ideal on a set X is κ-dense if there is a subset A of P (X )\I of cardinality κsuch that every I -positive subset of X contains a member of A modulo I .It follows easily that every ℵ1-dense σ-ideal is (ℵ2,ℵ2,ℵ0)-saturated.Received by the editors May 9,2003and,in revised form,May 14,2004.2000Mathematics Subject Classification.Primary 03E50;Secondary 54D15.The research in this paper was conducted with the support of a F APESP fellowship (Grant #02/11551-3)at the University of S˜a o Paulo.c2005American Mathematical Society Reverts to public domain 28years from publication27372738PAUL RSONIt is a classical fact due to Ulam that there is no ℵ0-dense σ-ideal on ω1(see,for instance,Lemma 10.13of [3]).Taylor [11]showed that under MA ℵ1there is no ℵ1-dense σ-ideal on ω1.The proof of Theorem 18in [2]shows that ap >ℵ1suffices,i.e.,that the following holds (a version of the argument appears also in [5]).Fact 0.1.If ap >ℵ1,then there is no ℵ1-dense σ-ideal on ω1.For the rest of this note,we fix an almost disjoint family {e α:α<ω1}.For each n ∈ωand each (possibly finite)σ⊂ω,we let E n σ={α<ω1||e α∩σ|≥n },and we let F n σ=ω1\E n σ.Lemma 0.2.Assume that ap >ℵ1.Let I be a σ-ideal on ω1and let βbe a cardinal such that P (ω1)/I is not β-dense.Let {A α:α<β}be a subset of P (ω1)\I .Then there exist an x ⊂ωand an n ∈ωsuch that•F n x ∈I ,•for each α<βthere exists an m ∈ωsuch that E n x ∩m ∩A α∈I .Proof.Since P (ω1)/I is not β-dense,we may fix {B α:α<β}⊂P (ω1)\I andD ∈P (ω1)\I such that each B α⊂A αand each B α∩D =∅.Since ap >ℵ1,there exists an x ⊂ωsuch that e γ∩x is infinite for each γ∈ {B α:α<β}and e γ∩x is finite for each γ∈D .Since D ⊂ {F n x :n <ω},we may fix an n ∈ωsuch that F n x ∈I .Similarly,for each α<β,since B α⊂ {E n x ∩m :m <ω},there is anm ∈ωsuch that E n x ∩m ∩A α∈I .The following theorem shows that ap >ℵ1implies that there is no σ-ideal I on ω1which is (γ,γ,ℵ0)-saturated,where γis the least cardinality of a dense subset of P (ω1)/I .In particular,if ap =c =ℵ2,then there is no (ℵ2,ℵ2,ℵ0)-saturated σ-ideal on ω1.Theorem 0.3.Assume that ap >ℵ1,and let I be a σ-ideal on ω1.Let γbe the least cardinal such that there exists a dense (modulo I )subset of P (ω1)\I of cardinality γ.Then there is a sequence D α:α<γ of members of P (ω1)\I such that for every cofinal X ⊂γthere exists a countable y ⊂X such that {D α:α∈y }∈I .Proof.Let {A α:α<γ}enumerate a dense subset of P (ω1)\I modulo I .For each β<γ,apply Lemma 0.2to {A α:α<β},obtaining x β,n βand D β=F n βx βsuch that D β∈I and such that for each α<βthere exists an m ∈ωsuch that A α∩E n βx β∩m ∈I .Now let X ⊂γbe cofinal.Let Z be the set of pairs (n,σ)(n ∈ω,σ⊂ωfinite)such that there exists a β∈X with E n σ∩D β∈I .We claim that {E n σ:(n,σ)∈Z }is predense in P (ω1)\I ,i.e.,that for every α<γthere exist a β∈X ,an n ∈ωand a finite σ⊂ωsuch that E n σ∩D β∈I and E n σ∩A α∈I .To verify this,fix α<γand let βbe any member of X greater than α.Then D β=F n βx βand there exists an m such that E n βx β∩m ∩A α∈I ,so β,n βand x β∩m suffice for α.Now,for each (n,σ)∈Z ,choose β(n,σ)∈X such that E n σ∩D β(n,σ)∈I .Then since {E n σ:(n,σ)∈Z }is predense in P (ω1)\I , {D β(n,σ):(n,σ)∈Z }∈I .We do not know whether some forcing axiom implies that the nonstationary ideal on ω1is not (ℵ2,ℵ1,ℵ0)-saturated.On the other hand,for all we know,some forcing axiom implies that the nonstationary ideal on ω1is (ℵ2,ℵ1,ℵ0)-saturated.ALMOST-DISJOINT CODING AND STRONGLY SATURATED IDEALS2739References[1]J.Brendle,Dow’s principle and Q-sets,Canad.Math.Bull.42(1999),no.1,13–24MR1695894(2000h:03093)[2]M.Foreman,M.Magidor,S.Shelah,Martin’s Maximum,saturated ideals,and non-regularultrafilters.Part I,Annals of Mathematics127(1988),1–47MR0924672(89f:03043)[3]T.Jech,Set Theory,The third millennium edition,revised and expanded.Springer Mono-graphs in Mathematics.Springer-Verlag,Berlin,2003MR1940513(2004g:03071)[4]R.B.Jensen,R.M.Solovay,Some applications of almost disjoint sets,Mathematical Logicand Foundations of Set Theory(Proc.Internat.Colloq.,J erusalem,1968),North-Holland, Amsterdam,pp.84–104,1970MR0289291(44:6482)[5]rson,A uniqueness theorem for iterations,J.Symbolic Logic67(2002),no.4,1344–1350MR1955241(2003m:03081)[6]ver,An(ℵ2,ℵ2,ℵ0)-saturated ideal onω1,Logic Colloquium’80(Prague,1980),pp.173–180,Stud.Logic Foundations Math.,108,North-Holland,Amsterdam-New York,1982.MR0673792(84a:03060)[7]P.Nyikos,Complete normality and metrization theory of manifolds,Top.Appl.123(1)(2002),181–192MR1921659(2003f:54048)[8]P.Nyikos,Applications of some strong set-theoretic axioms to locally compact T5and hered-itarily scwH spaces,Fund.Math.176(2003),no.1,25–45MR1971471(2004k:54008)[9]P.Nyikos,Correction to:“Complete normality and metrization theory of manifolds”[Topol-ogy Appl.123(2002),no.1,181–192],Topology Appl.138(2004),no.1-3,325–327 MR2035491(2004k:54030)[10]S.Shelah,Proper and improper forcing,Perspectives in Mathematical Logic,Springer-Verlag,Berlin,1998MR1623206(98m:03002)[11]A.D.Taylor,Regularity properties of ideals and ultrafilters,Ann.Math.Logic16(1979),no.1,33–55MR0530430(83b:04003)Department of Mathematics,Miami University,Oxford,Ohio45056E-mail address:larsonpb@。

2002I 1Many states use a sequence of three letters followed by a sequence of three digits as their standard license-plate pattern.Given that each three-letter three-digit arrangement is equally likely,the probability that such a license plate will contain at least one palindrome (a three-letter arrangement or a three-digit arrangement that reads the same left-to-right as it does right-to-left)is m/n ,where m and n are relatively prime positive integers.Find m +n .2The diagram shows twenty congruent circles arranged in three rows and enclosed in a rect-angle.The circles are tangent to one another and to the sides of the rectangle as shown in the diagram.The ratio of the longer dimension of the rectangle to the shorter dimension can be written as 12(√p −q ),where p and q are positive integers.Find p +q.[img]6601[/img]3Jane is 25years old.Dick is older than Jane.In n years,where n is a positive integer,Dick’s age and Jane’s age will both be two-digit number and will have the property that Jane’s age is obtained by interchanging the digits of Dick’s age.Let d be Dick’s present age.How many ordered pairs of positive integers (d,n )are possible?4Consider the sequence defined by a k =1k 2+k for k ≥1.Given that a m +a m +1+···+a n −1=1/29,for positive integers m and n with m <n ,find m +n.5Let A 1,A 2,A 3,...,A 12be the vertices of a regular dodecagon.How many distinct squares in the plane of the dodecagon have at least two vertices in the set {A 1,A 2,A 3,...,A 12}?6The solutions to the system of equationslog 225x +log 64y =4log x 225−log y 64=1are (x 1,y 1)and (x 2,y 2).Find log 30(x 1y 1x 2y 2).7The Binomial Expansion is valid for exponents that are not integers.That is,for all real numbers x,y,and r with |x |>|y |,(x +y )r =x r +rx r −1+r (r −1)2x r −2y 2+r (r −1)(r −2)3!x r −3y 3+···What are the first three digits to the right of the decimal point in the decimal representation of 102002+1 10/7?/This file was downloaded from the AoPS −MathLinks Math Olympiad Resources Page Page 1http://www.mathlinks.ro/20028Find the smallest integer k for which the conditions (1)a 1,a 2,a 3,...is a nondecreasing sequence of positive integers (2)a n =a n −1+a n −2for all n >2(3)a 9=k are satisfied by more than one sequence.9Harold,Tanya,and Ulysses paint a very long picket fence.Harold starts with the first picket and paints every h th picket;Tanya starts with the second picket and paints everth t th picket;and Ulysses starts with the third picket and paints every u th picket.Call the positive integer 100h +10t +u paintable when the triple (h,t,u )of positive integers results in every picket being painted exaclty once.Find the sum of all the paintable integers.10In the diagram below,angle ABC is a right angle.Point D is on BC ,and AD bisects angleCAB .Points E and F are on AB and AC ,respectively,so that AE =3and AF =10.Given that EB =9and F C =27,find the integer closest to the area of quadrilateral DCF G.[img]6604[/img]11Let ABCD and BCF G be two faces of a cube with AB =12.A beam of light emanates fromvertex A and reflects offface BCF G at point P,which is 7units from BG and 5units from BC.The beam continues to be reflected offthe faces of the cube.The length of the light path from the time it leaves point A until it next reaches a vertex of the cube is given by m √n,where m and n are integers and n is not divisible by the square of any prime.Find m +n.12Let F (z )=z +i z −i for all complex numbers z =i,and let z n =F (z n −1)for all positive integers n.Given that z 0=1137+i and z 2002=a +bi,where a and b are real numbers,find a +b.13In triangle ABC the medians AD and CE have lengths 18and 27,respectively,and AB =24.Extend CE to intersect the circumcircle of ABC at F .The area of traingle AF B is m √n ,where m and n are positive integers and n is not divisible by the square of any prime.Find m +n .14A set S of distinct positive integers has the following property:for every integer x in S ,thearithmetic mean of the set of values obtained by deleting x from S is an integer.Given that 1belongs to S and that 2002is the largest element of S ,what is the greatet number of elements that S can have?15Polyhedron ABCDEF G has six faces.Face ABCD is a square with AB =12;face ABF Gis a trapezoid with AB parallel to GF ,BF =AG =8,and GF =6;and face CDE has CE =DE =14.The other three faces are ADEG,BCEF,and EF G.The distance from E to face ABCD is 12.Given that EG 2=p −q √r,where p,q,and r are positive integers and r is not divisible by the square of any prime,find p +q +r.2002II 1Given that(1)x and y are both integers between 100and 999,inclusive;(2)y is the number formed by reversing the digits of x;and(3)z =|x −y |.How many distinct values of z are possible?2Three vertices of a cube are P =(7,12,10),Q =(8,8,1),and R =(11,3,9).What is the surface area of the cube?3It is given that log 6a +log 6b +log 6c =6,where a,b,and c are positive integers that form an increasing geometric sequence and b −a is the square of an integer.Find a +b +c.4Patio blocks that are hexagons 1unit on a side are used to outline a garden by placing the blocks edge to edge with n on each side.The diagram indicates the path of blocks around the garden when n =5.[img]6613[/img]If n =202,then the area of the garden enclosed by the path,not including the path itself,is m (√3/2)square units,where m is a positive integer.Find the remainder when m is divided by 1000.5Find the sum of all positive integers a =2n 3m ,where n and m are non-negative integers,for which a 6is not a divisor of 6a .6Find the integer that is closest to 100010000n =31n −4.7It is known that,for all positive integers k,12+22+32+···+k 2=k (k +1)(2k +1)6.Find the smallest positive integer k such that 12+22+32+···+k 2is a multiple of 200.8Find the least positive integer k for which the equation 2002n =k has no integer solutions for n.(The notation x means the greatest integer less than or equal to x.)20029Let S be the set {1,2,3,...,10}.Let n be the number of sets of two non-empty disjoint subsets of S .(Disjoint sets are defined as sets that have no common elements.)Find the remainder obtained when n is divided by 1000.10While finding the sine of a certain angle,an absent-minded professor failed to notice that hiscalculator was not in the correct angular mode.He was lucky to get the right answer.The two least positive real values of x for which the sine of x degrees is the same as the sine of x radians are mπn −πand pπq +π,where m,n,p and q are positive integers.Find m +n +p +q.11Two distinct,real,infinite geometric series each have a sum of 1and have the same secondterm.The third term of one of the series is 1/8,and the second term of both series can bewritten in the form √m −n p ,where m,n,and p are positive integers and m is not divisible by the square of any prime.Find 100m +10n +p.12A basketball player has a constant probability of .4of making any given shot,independantof previous shots.Let a n be the ratio of shots made to shots attempted after n shots.The probability that a 10=.4and a n ≤.4for all n such that 1≤n ≤9is given to be p a q b r/(s c ),where p,q,r,and s are primes,and a,b,and c are positive integers.Find (p +q +r +s )(a +b +c ).13In triangle ABC,point D is on BC with CD =2and DB =5,point E is on AC withCE =1and EA =32,AB =8,and AD and BE intersect at P.Points Q and R lie on AB so that P Q is parallel to CA and P R is parallel to CB.It is given that the ratio of the area of triangle P QR to the area of triangle ABC is m/n,where m and n are relatively prime positive integers.Find m +n.14The perimeter of triangle AP M is 152,and the angle P AM is a right angle.A circle ofradius 19with center O on AP is drawn so that it is tangent to AM and P M.Given that OP =m/n,where m and n are relatively prime positive integers,find m +n.15Circles C 1and C 2intersect at two points,one of which is (9,6),and the product of the radiiis 68.The x-axis and the line y =mx ,where m >0,iare tangent to both circles.It is given that m can be written in the form a √b/c,where a,b,and c are positive integers,b is not divisible by the square of any prime,and a and c are relatively prime.Find a +b +c.。

数学上，测度(Measure)是一个函数，它对一个给定集合的某些子集指定一个数，这个数可以比作大小、体积、概率等等。

传统的积分是在区间上进行的，后来人们希望把积分推广到任意的集合上，就发展出测度的概念，它在数学分析和概率论有重要的地位。

测度论是实分析的一个分支，研究对象有σ代数、测度、可测函数和积分，其重要性在概率论和统计学中有所体现。

目录[隐藏]• 1 定义• 2 性质o 2.1 单调性o 2.2 可数个可测集的并集的测度o 2.3 可数个可测集的交集的测度• 3 σ有限测度• 4 完备性• 5 例子• 6 自相似分形测度的分维微积分基础引论•7 相关条目•8 参考文献[编辑]定义形式上说，一个测度（详细的说法是可列可加的正测度）是个函数。

设是集合上的一个σ代数，在上定义，于扩充区间中取值，并且满足以下性质：•空集的测度为零：。

•可数可加性，或称σ可加性：若为中可数个两两不交的集合的序列，则所有的并集的测度，等于每个的测度之总和：。

这样的三元组称为一个测度空间，而中的元素称为这个空间中的可测集。

[编辑]性质下面的一些性质可从测度的定义导出：[编辑]单调性测度的单调性：若和为可测集，而且，则。

[编辑]可数个可测集的并集的测度若为可测集（不必是两两不交的），并且对于所有的，⊆，则集合的并集是可测的，且有如下不等式（“次可列可加性”）：以及如下极限：[编辑]可数个可测集的交集的测度若为可测集，并且对于所有的，⊆，则的交集是可测的。

进一步说，如果至少一个的测度有限，则有极限：如若不假设至少一个的测度有限，则上述性质一般不成立（此句的英文原文有不妥之处）。

例如对于每一个，令这里，全部集合都具有无限测度，但它们的交集是空集。

[编辑]σ有限测度详见σ有限测度如果是一个有限实数（而不是），则测度空间称为有限测度空间。

如果可以表示为可数个可测集的并集，而且这些可测集的测度均有限，则该测度空间称为σ有限测度空间。