FREE ELECTRONIC LIBRARY - Dissertations, online materials

Pages:   || 2 | 3 |

«ALFRED DOLICH, JOHN GOODRICK, AND DAVID LIPPEL Abstract. We study the notion of dp-minimality, beginning by providing several essential facts about ...»

-- [ Page 1 ] --


arXiv:0910.3189v2 [math.LO] 12 Nov 2009


Abstract. We study the notion of dp-minimality, beginning by providing several

essential facts about dp-minimality, establishing several equivalent definitions for

dp-minimality, and comparing dp-minimality to other minimality notions. The majority of the rest of the paper is dedicated to examples. We establish via a simple proof that any weakly o-minimal theory is dp-minimal and then give an example of a weakly o-minimal group not obtained by adding traces of externally definable sets. Next we give an example of a divisible ordered Abelian group which is dp-minimal and not weakly o-minimal. Finally we establish that the field of p-adic numbers is dp-minimal.

1. introduction In this note we study many basic properties of dp-minimality as well as developing several fundamental examples. Dp-minimality—see Definition 2.2—was introduced by Shelah in [14] as possibly the strongest of a family of notions implying that a theory does not have the independence property—for which see [15]. The study of dp- minimality beyond Shelah’s original work was continued by Onshuus and Usvyatsov in [11] focusing primarily on the stable case and by the second author in [9] primarily in the case of theories expanding the theory of divisible ordered Abelian groups. Our goal in this paper is to provide many basic foundational facts on dp-minimality as well as to explore concrete examples of dp-minimality in the ordered context as well as the valued field context. Much of our motivation arises out of the program of attempting to explore the impact of


model theoretic notions, such as dp-minimality, in concrete situations such as ordered model theory on the reals or the study of valued

–  –  –

these facts are inherent in [14] but we isolate them here and provide straightforward proofs. Section 3 is a brief discussion of the relationship of dp-minimality to some other minimality notions. In Section 4 we focus weak on o-minimality—for which see [10]—and show that a weakly o-minimal theory is dp-minimal as well providing an example of a weakly o-minimal group which is not obtained by expanding on o-minimal structure by convex sets. Work in Section 3 as well as results from [9] indicate that a dp-minimal theory expanding that of divisible ordered Abelian groups has some similarity to a weakly o-minimal theory and we may naturally ask whether any such theory is weakly o-minimal. Section 5 provides a negative answer via an example arising form the valued field context. Our final section is dedicated to showing that the theory of the p-adic field is dp-minimal.

2. basic facts on dp-minimality We develop several basics facts about dp-minimality. The vast majority of the material found below is inherent in Shelah’s paper [14], but typically in the more general context of strong dependence. We provide proofs of these various facts for

clarity and ease of exposition. Recall:

Definition 2.1. Fix a structure M, An ICT pattern in M consists of a pair of formulae φ(x, y) and ψ(x, y); and sequences {ai : i ∈ ω} and {bi : i ∈ ω} from M so that for

all i, j ∈ ω the following is consistent:

φ(x, ai ) ∧ ψ(x, bj ) ∧ ¬φ(x, al ) ∧ ¬ψ(x, bk ).

l=i k=j Remark. Definition 2.1 should more formally be referred to as an ICT pattern of depth two but in this paper we only consider such ICT patterns and thus we omit this extra terminology.

Definition 2.2. A theory T is said to be dp-minimal if in no model M |= T is there an ICT pattern.

It is often very convenient to use the following definition and fact.

Definition 2.3. We say two sequences {ai : i ∈ I} and {bj : j ∈ J} are mutually indiscernible if {ai : i ∈ I} is indiscernible over j∈J bj and {bj : j ∈ J} is indiscernible over i∈I ai. We call an ICT pattern mutually indiscernible if the witnessing sequences are mutually indiscernible.

Fact 2.4.

T is dp-minimal if and only if in no model M |= T is there a mutually indiscernible ICT pattern.

Proof. This is a simple application of compactness and Ramsey’s theorem.

Before continuing we should mention another alternative characterization of dpminimality. To this end we have the following definition.


Definition 2.5. A theory T is said to be inp-minimal if there is no model of M of T formulae φ(x, y) and ψ(x, y), natural numbers k0 and k1, and sequences {ai : i ∈ ω} and {bi : i ∈ ω} so that {φ(x, ai ) : i ∈ ω} is k0 -inconsistent, {ψ(x, bj ) : j ∈ ω} is k1 -inconsistent and for any i, j ∈ ω the formula φ(x, ai ) ∧ ψ(x, bj ) is consistent.

With this definition we have the following fact:

Fact 2.6.

[11, Lemma 2.11] If T does not have the independence property and is inp-minimal then T is dp-minimal.

The next fact is extremely useful in showing that a theory is not dp-minimal. It is key in establishing the relationship between dp-minimality and indiscernible sequences that follows.

Fact 2.7.

Let T be a complete theory, we work in a monster model C. Suppose there are formulae φ0 (x, y) and φ1 (x, y) and mutually indiscernible sequences {ai : i ∈ ω} and {bi : i ∈ ω} so that φ0 (x, a0 ) ∧ ¬φ0 (x, a1 ) ∧ φ1 (x, b0 ) ∧ ¬φ1 (x, b1 ) is consistent then T is not dp-minimal.

Proof. By compactness there are mutually indiscernible sequences ai for i ∈ Z and bi for i ∈ Z and c so that |= φ0 (c, a0 ) ∧ ¬φ0 (c, a1 ) ∧ φ1 (c, b0 ), ∧¬φ1 (c, b1 ).

By applying compactness and Ramsey’s theorem we assume that {ai : i 0} and {ai : i 1} are both indiscernible over i∈ω bi ∪ {c} as well as that {bi : i 0} and {bi : i 1} are both indiscernible over i∈ω ai ∪ {c}. Let di = a2i a2i+1 and ei = b2i b2i+1 for i ∈ Z. Note that these two sequences are mutually indiscernible.

Let ψ0 (x, y 0 y 1 ) be φ0 (x, y 0 ) ↔ ¬φ0 (x, y 1 ) and ψ1 (x, y 0 y 1 ) be φ1 (x, y 0 ) ↔ ¬φ1 (x, y 1 ).

Then C |= ψ0 (c, d0 ) ∧ ψ1 (c, e0 ) and if i = 0 then |= ¬ψ0 (c, di ) ∧ ¬ψ1 (c, ei ) by the indiscernibility assumptions. It follows that ψ0, ψ1, {di : i ∈ ω} and {ei : i ∈ ω} witness that T is not dp-minimal.

Using the identical proof as above we show:

Fact 2.8. The following are equivalent:

(1) There are formulae φi (x, y) for 1 ≤ i ≤ N and sequences ai for 1 ≤ i ≤ N j

and j ∈ ω so that for every η : {1,..., N} → ω the type:

–  –  –

is consistent As in the case of the independence property and strong dependence we have a characterization of dp-minimality in terms of splitting indiscernible sequences.

Fact 2.9. The following are equivalent for a theory T :

(1) T is dp-minimal.

(2) If {ai : i ∈ I} is an indiscernible sequence and c is an element then there is a partition of I into finitely many convex sets I0,..., In, at most two of which are infinite, so that for any 1 ≤ l ≤ n if i, j ∈ Il then tp(ai /c) = tp(aj /c).

(3) If {ai : i ∈ I} is an indiscernible sequence and c is an element then there is a partition of I into finitely many convex sets I0,..., In, at most two of which are infinite, so that for any 1 ≤ l ≤ n the sequence {ai : i ∈ Il } is indiscernible over c.

Proof. (1) ⇒ (3): Suppose T is dp-minimal and for contradiction suppose that there is an indiscernible sequence (which for notational simplicity we assume consists of singletons) {ai : i ∈ I} and an element c witnessing the failure of (3). Without loss of generality we assume that I is a sufficiently saturated dense linear order without endpoints. By [1, Corollary 6] there is an initial segment I0 ⊆ I and a final segment I1 ⊆ I so that the sequences {ai : i ∈ I0 } and {ai : i ∈ I1 } are indiscernible over c. We may choose I0 to be maximal in the sense that for no convex J with I0 ⊂ J ⊆ I is {aj : j ∈ J} indiscernible over c and similarly for I1. If I \ (I0 ∪ I1 ) is finite then (3) holds so I \ (I0 ∪ I1 ) is infinite and thus contains an interval. Let J0 and J1 be disjoint convex sets so that I0 ⊂ J0 ⊂ I and I1 ⊂ J1 ⊂ I. We find ∗ ∗ j1 · · · jn ∈ J0 and a formula φ(x, y1,..., yn ) so that ¬φ(c, ai1,... ain ) holds for all i1 · · · in ∈ I0 but φ(c, aj1,..., ajm ) holds. We choose a sequence of n-tuples di ∗ ∗

–  –  –

(3) ⇒ (2): Immediate.

(2) ⇒ (1). For contradiction suppose there are formulae φ(x, y) and ψ(x, y) and mutually indiscernible sequences {ai : i ∈ 3 × ω} and {bi : i ∈ 3 × ω} which witness the failure of dp-minimality. Such sequences must exist by compactness. For i ∈ 3×ω

let ci = ai bi. Note this is an indiscernible sequence. Pick d realizing the type:

φ(x, aω ) ∧ ψ(x, a2×ω ) ∧ ¬φ(x, ai ) ∧ ¬ψ(x, bj ).

i=ω j=2×ω If i = ω or 2 × ω then |= ¬φ(d, ai ) ∧ ¬ψ(d, bi ), if i = ω then |= φ(d, aω ) ∧ ¬ψ(d, bω ) and if i = 2 × ω then |= ¬φ(d, a2×ω ) ∧ ψ(d, b2×ω ). It follows that the indiscernible sequence {ci : i ∈ 3 × ω} can not be decomposed into convex subsets of which at most two are infinite so that the type over d is constant on each convex set. Hence (2) fails.

We use the preceding fact to provide a characterization of dp-minimality which allows us to consider formulae with more than one free variable in a variant of Definition 2.2 as well as to consider sets of parameters of arbitrary size in a variant of Fact 2.9. The proof is immediate using Facts 2.8 and 2.9.

–  –  –

Given a dp-minimal theory T it is reasonable to ask if the bound in Fact 2.10(4) may be improved from 2n to n + 1. This holds in the stable case and we sketch the proof.

Fact 2.11.

If T is dp-minimal and stable then there is no sequence of formulae

–  –  –

is consistent.

Proof. (Sketch) By [11, Theorem 3.5] T is stable and dp-minimal if and only if every 1-type has weight 1. Thus if T is stable and dp-minimal every n-type has weight at most n. Apply [11, Lemma 2.3 and Lemma 2.11] and the result follows.

This fact also holds for weakly o-minimal T (we defer discussion of this to section 3).

In fact it is tempting to restate the result with stable replaced by rosy and use þweight as in [12] but at the moment it is not clear if the result follows. Overall we do not know whether these improved bounds hold for a general dp-minimal theory.

We finish with two facts which are useful in studying specific examples. The first of these is particularly useful when studying theories which admit some type of cell decomposition—viz. the p-adics.

Fact 2.12.

Suppose that φ(x, y) and ψ(x, y) are formulae witnessing that a theory T is not dp-minimal. Further suppose that φ(x, y) is φ1 (x, y) ∨ · · · ∨ φn (x, y). Then for some 1 ≤ l ≤ n φl (x, y) and ψ(x, y) witness that T is not dp-minimal.

Proof. There are mutually indiscernible sequences {ai : i ∈ Z} and bi : i ∈ Z} so that for any i∗, j ∗ ∈ Z the type φ(x, ai∗ ) ∧ ψ(x, bj ∗ ) ∧ ¬φ(x, ai ) ∧ ¬ψ(x, bj ) i=i∗ j=j ∗

–  –  –

Thus α realizes θ(x, ci ) and θ(x, dj ). If k = i then α realizes ¬φ(x, ai ) and ¬ψ(x, bi ) and hence realizes ¬θ(x, ci ). Finally if l = j then α realizes ¬θ(x, aω+l ) and ¬θ(x, bω+l ) and hence ¬θ(x, dj ) as desired.

3. Relationship with similar notions In this brief section we examine the relationship between dp-minimality and various other strong forms of dependence.

We begin with the notion of VC-density as studied in [3]. For the ensuing definition we fix ∆(x, y) a finite set of formulae where we consider y as the parameter variables. If A is a set of |y|-tuples we write S ∆ (A) for the set of complete ∆-types with parameters from A.

Definition 3.1. A theory T has VC-density one if for any finite set of formulae ∆(x, y) there is a constant C so that for any finite set, A, of |y|-tuples S ∆ (A) ≤ C |A||x|.

For example in [3] it is shown that any weakly o-minimal theory and any quasi o-minimal theory with definable bounds (for which see [4]) has VC-density one. We

have a strong relationship between VC-density one and dp-minimality:

Proposition 3.2. If T has VC-density one then T is dp-minimal.

Proof. Suppose that T is not dp-minimal. Apply Fact 2.13 to find a formula φ(x, y) and sequences ai and bj as described there. For N ∈ N let AN = {ai : i ≤ N} ∪ {bj : j ≤ N}.

|AN |2 for all 1 By the failure of dp-minimality we immediately see that S {φ} (AN ) ≥ 4 N. Thus T does not have VC-density one.

Note that the above proof only requires that we have that S ∆ (A) ≤ C |A| for ∆ consisting of formulae of the form φ(x, y), i.e. with only one free variable. We may use this fact to provide a novel proof for the dp-minimality of the theory of algebraically closed valued fields. This fact was already observed in [2] and as the proof is somewhat technical we do not include it here.

Corollary 3.3. Any weakly o-minimal theory as well as any quasi o-minimal theory with definable bounds is dp-minimal.


–  –  –

is consistent.

We consider the notion of VC-minimality as introduced in [2].

Definition 3.5. Fix a theory T and a monster model C |= T. T is VC-minimal if

there is a family of formulae Φ of the the form φ(x, y) so that:

• If φ(x, y), ψ(x, y) ∈ Φ and a, b ∈ C then one of:

– φ(C, a) ⊆ ψ(C, b), – ψ(C, b) ⊆ φ(C, a), – ¬φ(C, a) ⊆ ψ(C, b), – ψ(C, b) ⊆ ¬φ(C, a).

• If X ⊆ C then there are a finite collection of φi (x, y) from Φ and tuples ai ∈ C so that X is a Boolean combination of the sets φi (C, ai ).

Pages:   || 2 | 3 |

Similar works:

«Do-It-Yourself Eye Tracker: Low-Cost Pupil-Based Eye Tracker for Computer Graphics Applications Radoslaw Mantiuk, Michal Kowalik, Adam Nowosielski, and Bartosz Bazyluk West Pomeranian University of Technology in Szczecin, Faculty of Computer Science, ˙ Zolnierska 49, 71-210, Szczecin, Poland rmantiuk@wi.zut.edu.pl Abstract. Eye tracking technologies offer sophisticated methods for capturing humans’ gaze direction but their popularity in multimedia and computer graphics systems is still low....»

«  1   Excerpt from Wer ist Martha? By Marjana Gaponenko Translated by Arabella Spencer I Love is cold. Love is cold. But in the grave we burn and melt to gold. Levadski waited for the tears. The tears didn’t come. In spite of this he wiped his face. Disgusting! With a fixed stare he had just put the receiver on its cradle. What else, if not impatience, had he sensed in the breathing of his family doctor? Impatience and the buzzing of thoughts that had nothing to do with him, Levadski:...»

«April 2010 Learning from the 2009 H1N1 Influenza Pandemic RMS Special Report EXECUTIVE SUMMARY The 2009 H1N1 influenza pandemic illustrated how fast a new infectious disease can spread through modern  society. The speed at which the H1N1 virus spread to infect many millions of people was unprecedented for a disease of this scale. The 2009 H1N1 influenza virus became well-established in large numbers of countries within a few weeks. Though the novel virus was relatively mild when compared to...»

«A STORY ABOUT A LOVING FATHER AND HIS TWO WAYWARD SONS Reflection for the Fourth Sunday in Lent, Cycle C Today's parable is one of the best known and best loved stories in the Bible. While it is generally called the Parable of the Prodigal Son, scholars tell us that this story should really be renamed as the Parable of the Merciful Father, since its main focus is not the prodigal son and his sin, but the father and his mercy. Also, the story could be called the Parable of the Resentful Brother,...»

«[Cite as State v. Jacob, 2015-Ohio-4760.] Court of Appeals of Ohio EIGHTH APPELLATE DISTRICT COUNTY OF CUYAHOGA JOURNAL ENTRY AND OPINION No. 102076 STATE OF OHIO PLAINTIFF-APPELLEE vs. HARRY J. JACOB, III DEFENDANT-APPELLANT JUDGMENT: AFFIRMED Criminal Appeal from the Cuyahoga County Court of Common Pleas Case No. CR-14-584560-A BEFORE: Laster Mays, J., Boyle, P.J., and Blackmon, J. RELEASED AND JOURNALIZED: November 19, 2015 -iATTORNEY FOR APPELLANT Russell S. Bensing 600 IMG Building 1360...»


«In the United States Court of Federal Claims No. 06-287V March 19, 2007 To be Published ***************************** WILLIAM STEWART and LEONOR SOTELO, * on Behalf of WILLIAM STEWARTSOTELO, * a Minor, * * Petitioners, * * v. * Entitlement; acute cerebellar * ataxia caused by hepatitis A SECRETARY OF THE DEPARTMENT OF * vaccine HEALTH AND HUMAN SERVICES, * * Respondent. * ***************************** Richard Gage, Cheyenne, WY, for petitioners. Robin L. Brodrick, Washington, DC, for...»

«Pygmalion George Bernard Shaw This public-domain text was produced by Eve Sobol, South Bend, Indiana, USA. The Project Gutenberg edition (designated “pygml10”) was subsequently converted to LTEX using GutenMark software, and then A re-edited by Ron Burkey (for formatting only) using lyx software. Report problems to info@sandroid.org. Revision B1 differs from B in that “—-” was everywhere replaced by “—”. Revision: B1 Date: 02/02/2008 TRANSCRIBER’S NOTE: In the printed version...»

«Lancashire to Lahore William Titley 2010 A visual communication project between creative communities in the UK and Pakistan. Contents Introduction: William Titley 4 ‘Lancashire to Lahore’: Hayley Drayton 7 ‘This is Pakistan’ 8 Image Credits 9 Images: in alphabetical order 10 ‘This is England’ 26 Image Credits 27 Images: in alphabetical order 28 02 This page intentionally left blank 03 Introduction: William Titley In a world where forms of communication are developing in parallel...»

«This is a work of fiction. Names, characters, places, and incidents either are the product of the author’s imagination or are used fictitiously. Any resemblance to actual persons, living or dead, events, or locales is entirely coincidental. Copyright © 2009 by Gillian Flynn All rights reserved. Published in the United States by Shaye Areheart Books, an imprint of the Crown Publishing Group, a division of Random House, Inc., New York. www.crownpublishing.com Shaye Areheart Books with...»

«Draft 2015 National Convention Brandon, MB Annual General Meeting – August 21-22, 2015 Call to Order: National President Ron Hanishewsky March in of National Convention 85 first-timers and the official open National Convention 2015! Welcome delegates to National Convention “Back to the Future 2015” by NP Ron Hanishewsky. O ‘Canada – NVP Kim Peters Kin Song – Cameron Kemp NP Ron thanked the host club for all their hard work preparing for this weekend. Video – Kin week interview...»

«Beställning av ADSL / LAN TJÄNST PRIVAT i Laholms Stadsnät, 18 mån bindningstid, 3 mån uppsägningstid. Hastighet kan variera på grund av tekniska hinder såsom kvalitet på telekabel samt längd från telestation till fastighet. Upp till enligt hastighetsspecifikation. Se avtalsvillkor för tekniskt info. Modem/router-paket ingår med 12 månaders garanti. ADSL LAN Lan-telefoni Hastighet upp till: 24 Mbit 339:-/mån 100/10 Mbit 339:-/mån Endast telefoni 145:-/mån 8 Mbit 325:-/mån...»

<<  HOME   |    CONTACTS
2016 www.dissertation.xlibx.info - Dissertations, online materials

Materials of this site are available for review, all rights belong to their respective owners.
If you do not agree with the fact that your material is placed on this site, please, email us, we will within 1-2 business days delete him.