FREE ELECTRONIC LIBRARY - Abstract, dissertation, book

Pages:   || 2 |

«Abstract. We give a new definition of Scott rank motivated by our main theorem: For every countable structure A and ordinal α ω1, we have that: ...»

-- [ Page 1 ] --




Abstract. We give a new definition of Scott rank motivated by our main theorem: For

every countable structure A and ordinal α ω1, we have that: every automorphism orbit is

Σin -definable without parameters if and only if A has a Πin Scott sentence, if and only if A

α α+1 is uniformly boldface ∆0 -categorical. As a corollary, we show that a structure is computably α categorical on a cone if and only if it is the model of a countably categorical Σin sentence.

1. Introduction This paper has two main objectives. One is to introduce what the author believes is the right definition of Scott rank. The other is to provide a simple structural characterization for the notion of computable categoricity on a cone.

1.1. Scott ranks. The Scott rank measures the complexity of a structure in terms of the complexity of the automorphism orbits of its tuples. It is a very useful tool in infinitary model theory, descriptive set theory, and computable structure theory. Its original formulation comes from Scott’s proof [Sco65] that every countable structure is the unique countable model of some Lω1,ω sentence. Since then, a few non-equivalent formulations of Scott rank have been proposed. We review them in Section 3.1.

It is known that the Scott rank of a structure is connected to the complexity of its Soctt sentence, which is connected to its level of categoricity, etc. One can prove that some of these measures of complexities provide upper and lower bounds for the others. Our main theorem exposes these connections in the sharpest possible way.

Theorem 1.1.

Let A be a countable structure and α be a countable ordinal. The following

are equivalent:

(U1) Every automorphism orbit is Σin -definable without parameters.

α (U2) A has a Πin Scott sentence.

α+1 (U3) A is uniformly boldface ∆0 -categorical.

α Let us quickly explain the terms in the theorem. The “in” in Σin is for “infinitary;” We α refer the reader to [AK00, Section 6.4] for background on the hierarchy of Lω1,ω formulas. The automorphism orbit of a tuple a in a structure A is the set of all other tuples automorphic to ¯ a. Since every definable set is a union of automorphism orbits, we have that (U1) is equivalent ¯ to saying that every Lω1,ω -definable relation in A is Σin -definable (definability being without α parameters). For (U2), recall that a Scott sentence for a countable structure A is an infinitary sentence whose only countable model is A. Scott [Sco65] proved that such a sentences always exist. In other words, part (U2) says that A is the model of a countably categorical Πin α+1 sentence. Part (U3) refers to a different notion of categoricity, the one used in computability theory. A structure is uniformly boldface ∆0 -categorical if it is uniformly ∆0 -categorical α α relative to some oracle; we will explain this in detail in Section 2.2.

Theorem 1.1 and its continuation below show the robustness of the statements (U1), (U2),

and (U3). Motivated by the theorem, we propose yet another notion of Scott rank:

–  –  –

In other words, the Scott rank of A is the least α satisfying the statements of Theorem 1.1.

We hope that having a robuster notion of Scott rank can help better understand it.

We continue our main theorem by adding four more properties. Depending on the background of the reader, some of these properties will sound more relevant than others. We will explain each of them briefly right after the theorem, and in more detail later in the paper.

Theorem (1.1 continued). The following are also equivalent to (U1), (U2) and (U3):

The set of presentations of A is Π0 (U4) α+1 in the Borel hierarchy.

Every Πin -type realized in A is Σin -supported within A.

(U5) α α There is a Πin -sentence ϕ true of A such that if B |= ϕ, then B ≡α+1 A.

(U6) α+1 No tuple in A is α-free.

(U7) In (U4), we are referring to the set of presentations of A as a set of reals, and looking at its complexity from the viewpoint of descriptive set theory. The equivalence between (U4) and (U2) follows from Lopez-Escobar’s theorem [LE65], that says that a class of presentations of structures, closed under isomorphism, is Π0 in the Borel hierarchy if and only if it is β Πin -axiomatizable.

β For part (U5), a type p(¯) is Σin -supported within A if there is a Σin -formula ϕ(¯) that x x α α implies, within A, all the formulas in p(¯), and of course that is realized in A. Part (U5) x follows trivially from (U1), as the Σin -formula defining the orbit clearly implies the Πin -type α α of the elements in the orbit. The reason we introduce this weakening of (U1) is that it will be very useful in our proof as a pivotal point to prove the rest of the statements.

In (U6), ≡α+1 refers to Σin -elementary equivalence, also known as (α + 1)-back-and-forth α+1 equivalence. Part (U6) follows trivially from (U2), as the Scott sentence of A serves as ϕ for (U6). The interesting feature about (U6) is that it implies that A has maximal under ≤α+1, which is a useful fact if one is trying to find the structures that satisfy the theorem.

(See Subsection 2.3 for a definition of the (α + 1)-back-and-forth relations ≤α+1.) When K has countably many Πin -types (i.e. it is Σin -small–see [Mon]), (U6) is equivalent to A being α α maximal under ≤α+1 (as it follows from [Mon10, Lemma 2.2]). Thus, in classes where we have a good understanding of the ≤n -back-and-forth types, like Boolean algebras [HM12] for instance, we can find the structures which satisfy Theorem 1.1 by searching for the ≤α+1 maximal ones.

Part (U7) is a very combinatorial property sometimes useful in proofs and constructions.

The notion of α-freeness was introduced by Ash and Knight and was used to give a characterization of ∆0 -categoricity for α-friendly structures. We will get back to this in Section α 2.3.

The proof of most of the equivalences in Theorem 1.1 are not particularly difficult, and require putting together variations of various known results. The most interesting implication is (U2) ⇒ (U5), which uses a sharper version of the usual omitting types theorem for infinitary logic. Once set up correctly, the proof of this omitting types theorem is very similar to the standard one. To avoid introducing the notions of consistency property, fragment, and other notions of infinitary logic, we prove a variation better suited for our purposes.

–  –  –

a cone. The reader only interested in the infinitary model theory part may skip this section and move on to Section 3.

2.1. Computable categoricity on a cone. The notion of computable categoricity, originally introduced by Mal’cev [Mal62], has been intensively studied in computability theory in the past decades. Many of the properties one considers in computable structure theory are not invariant under isomorphisms; that is, structures may have isomorphic computable presentations with different computational properties. For instance, there are computable presentations of the countable, infinite-dimensional Q-vector space, Q∞, where all the finitedimensional subspaces are computable, and computable presentations of Q∞ where no finitedimensional subspace is computable (see [DHK+ 07]). Computably categorical structures are

exactly the ones where this does not happen:

Definition 2.1. A computable structure A is computably categorical if there is a computable isomorphism between any two computable copies of A.

There has been a lot of work characterizing the computably categorical structures within certain classes of structures. Precise characterizations have been found for linear orders (Dzgoev and Goncharov [GD80]), Boolean algebras (Goncharov, and independently La Roche [LR78]), ordered abelian groups (Goncharov, Lempp, and Solomon [GLS03]), torsion-free abelian groups (Nurtazin [Nur74]), p-groups (Goncharov [Gon80] and Smith [Smi81]), trees of finite height (Lempp, McCoy, R. Miller, and Solomon [LMMS05]), etc.

On the other hand, there are many classes where we do not expect such characterization are even possible. Downey, Kach, Lempp, Lewis-Pye, Montalb´n and Turetsky [DKL+ ] recently a showed that there is no structural characterization for the notion of computable categoricity by showing that the index set of the computably categorical structures is Π1 -complete. In contrast, the relativized version of computable categoricity is relatively well-behaved, as proved by Goncharov [Gon75] long ago.

Definition 2.2. Given X ∈ 2ω, an X-computable structure A is X-computably categorical if there is an X-computable isomorphism between any two X-computable copies of A. A structure A is relatively computably categorical if it is X-computably categorical for all X ∈ 2ω.

Goncharov [Gon75] showed that a structure A is relative computably categorical if and only if it has a c.e. Scott family of ∃-formulas. In this paper, we look at a different variation of the definition of computable categoricity that has an even nicer structural classification.

Definition 2.3. A structure A is computably categorical on a cone if there is a Y ∈ 2ω such that A is X-computably categorical for all X ≥T Y.

We remark that, when we are looking at natural examples, most properties relativize.

Thus, for natural structures, the three notions, computable categoricity, relative computable categoricity and computable categoricity on a cone, coincide. As a corollary of Theorem 1.1, we get our second main result.

Theorem 2.4. Let A be a countable structure. The following are equivalent:

(1) A is computably categorical on a cone.

(2) A has a Σin Scott sentence.

Let us note that A has a Σin Scott sentence if and only if there exists a tuple a ∈ Aω such ¯ that (A, a) has a Πin -Scott sentence, which is equivalent to (A, a) having categoricity Scott ¯ ¯

rank 1. This generalizes through the transfinite in the expected way:

Theorem 2.5.

Let A be a countable structure and α a countable ordinal. The following are




–  –  –

The lightface version, with parameters, of the equivalence (U1) ⇔ (U7) appears in [AK00, Proposition 17.6 and Theorem 17.7] under the assumption that A satisfies an effectiveness condition called α-friendliness. To show that (U1) ⇔ (U7), all we need to do is observe that every structure is α-friendly relative to a large enough oracle, and that (U1) is equivalent to saying that A has a Σc -Scott family on a cone. We also need to observe that the parameter-free α version of [AK00, Proposition 17.6 and Theorem 17.7] holds via almost the same proofs.

–  –  –


[AK00] C.J. Ash and J. Knight. Computable Structures and the Hyperarithmetical Hierarchy. Elsevier Science, 2000.

[AKMS89] Chris Ash, Julia Knight, Mark Manasse, and Theodore Slaman. Generic copies of countable structures. Ann. Pure Appl. Logic, 42(3):195–205, 1989.

[Ash87] C. J. Ash. Categoricity in hyperarithmetical degrees. Ann. Pure Appl. Logic, 34(1):1–14, 1987.

[DHK03] R. Downey, D. Hirschfeldt, and B. Khoussainov. Uniformity in the theory of computable structures.

Algebra Logika, 42(5):566–593, 637, 2003.

[DHK+ 07] Downey, Hirschfeldt, Kach, Lempp, A. Montalb´n, and Mileti. Subspaces of computable vector a spaces. Journal of Algebra, 314(2):888–894, August 2007.

[DKL+ ] R. Downey, A. Kach, S. Lempp, A.E.M. Lewis-Pye, A. Montalb´n, and D. Turetsky. The complexity a of computable categoricity. Submitted for publication.

[Gao07] Su Gao. Complexity ranks of countable models. Notre Dame J. Formal Logic, 48(1):33–48 (electronic), 2007.

[GD80] S. S. Gonˇarov and V. D. Dzgoev. Autostability of models. Algebra i Logika, 19(1):45–58, 132, 1980.

c [GLS03] Sergey S. Goncharov, Steffen Lempp, and Reed Solomon. The computable dimension of ordered abelian groups. Adv. Math., 175(1):102–143, 2003.

[Gon75] S. S. Gonˇarov. Selfstability, and computable families of constructivizations. Algebra i Logika, c 14(6):647–680, 727, 1975.

[Gon80] Sergey S. Goncharov. Autostability of models and abelian groups. Algebra i Logika, 19(1):23–44, 132, 1980.

[HM12] Kenneth Harris and Antonio Montalb´n. On the n-back-and-forth types of Boolean algebras. Trans.

a Amer. Math. Soc., 364(2):827–866, 2012.

[Kei71] H. Jerome Keisler. Model theory for infinitary logic. Logic with countable conjunctions and finite quantifiers. North-Holland Publishing Co., Amsterdam, 1971. Studies in Logic and the Foundations of Mathematics, Vol. 62.

[LE65] E. G. K. Lopez-Escobar. An interpolation theorem for denumerably long formulas. Fund. Math., 57:253–272, 1965.

[LMMS05] Steffen Lempp, Charles McCoy, Russell Miller, and Reed Solomon. Computable categoricity of trees of finite height. J. Symbolic Logic, 70(1):151–215, 2005.

[LR78] Peter E. La Roche. Contributions to Recursive Algebra. ProQuest LLC, Ann Arbor, MI, 1978. Thesis (Ph.D.)–Cornell University.

[Mal62] Anatolii I. Mal’cev. On recursive Abelian groups. Dokl. Akad. Nauk SSSR, 146:1009–1012, 1962.

[Mon] Antonio Montalb´n. Computability theoretic classifications for classes of structures. Submitted for a publication.

[Mon10] Antonio Montalb´n. Counting the back-and-forth types. Journal of Logic and Computability, page a doi: 10.1093/logcom/exq048, 2010.

[Nur74] A. T. Nurtazin. Computable classes and algebraic criteria for autostability. PhD thesis, Institute of Mathematics and Mechanics, Alma-Ata, 1974.

[Sac07] Gerald E. Sacks. Bounds on weak scattering. Notre Dame J. Formal Logic, 48(1):5–31, 2007.

[Sco65] Dana Scott. Logic with denumerably long formulas and finite strings of quantifiers. In Theory of Models (Proc. 1963 Internat. Sympos. Berkeley), pages 329–341. North-Holland, Amsterdam, 1965.

Pages:   || 2 |

Similar works:

«Hospitals As Hotels: The Role of Patient Amenities in Hospital Demand Dana Goldman University of Southern California and NBER John A. Romley RAND April 19, 2010 Abstract Amenities such as good food, attentive sta¤, and pleasant surroundings may play an important role in hospital demand. We use a marketing survey to measure amenities at hospitals in greater Los Angeles and analyze the choice behavior of Medicare pneumonia patients in this market. We.nd that a one-standard-deviation increase in...»

«Geographisches Institut Abt. Humangeographie Zusammenfassung der wichtigsten Ergebnisse zur Projektstudie Der demographische Wandel und seine Auswirkungen auf die Samtgemeinde Gieboldehausen Projektleitung: Dr. Michael Waibel Projektbearbeitung: Brigitta Arend, Sinah Theres Kloß, Stefanie Kegler Das innovative Bevölkerungsprognosemodell Der demographische Wandel verläuft in Deutschland regional sehr unterschiedlich. In der Samtgemeinde Gieboldehausen sind seine Auswirkungen bereits heute...»

«2 Część pierwsza: ?? NR 2965 4 Część pierwsza: ?? Redaktor serii: Filozofia Andrzej Kiepas Recenzent Mirosław Żelazny Publikacja będzie dostępna — po wyczerpaniu nakładu — w wersji internetowej: Śląska Biblioteka Cyfrowa www.sbc.org.pl Redaktor Małgorzata Pogłódek Projektant okładki Paulina Dubiel Redaktor techniczny Barbara Arenhövel Korektor Luiza Przełożny Skład i łamanie Edward Wilk Copyright © 2012 by Wydawnictwo Uniwersytetu Śląskiego Wszelkie prawa...»

«Интернет-портал «Наука и религия» http://atheo-club.ru/ Ричард Эллиотт Фридман КТО НАПИСАЛ БИБЛИЮ? Переводчики Дмитрий Лысенко Арсений Енин Тарас Свитлык ( http://tarasskeptic.blogspot.com/ ) Юрий Клименковский (http://www.svob.narod.ru/bibl.htm/) Обсуждение книги http://atheo-club.ru/newphpBB/viewtopic.php?f=5&t=2244 Права на данный...»

«STATE OF MICHIGAN COURT OF APPEALS JOEL CAMERON and KRISTI CAMERON, on UNPUBLISHED behalf of ASHLEY CAMERON, a Minor, and January 15, 2015 KRISTI CAMERON, Plaintiffs-Appellants, v No. 318887 Wayne Circuit Court HURON CLINTON METROPOLITAN LC No. 12-007767-NO AUTHORITY, JEFFREY W. SCHUMAN, and RICHARD E. SOBECKI, Defendants-Appellees. Before: FORT HOOD, P.J., AND HOEKSTRA AND O’CONNELL, JJ. PER CURIAM. In this personal injury action, plaintiffs appeal as of right an order of the trial court...»

«This is an extract from: Byzantine Magic edited by Henry Maguire published by Dumbarton Oaks Research Library and Collection Washington, D.C. © 1995 Dumbarton Oaks Trustees for Harvard University Washington, D.C. Printed in the United States of America www.doaks.org/etexts.html Byzantine Magic Byzantine Magic Edited by Henry Maguire Dumbarton Oaks Research Library and Collection Washington, D.C. Distributed by Harvard University Press Copyright © 1995 by Dumbarton Oaks Trustees for Harvard...»

«Correct as of 7th Nov 2014 Movies Content Comparison Notes: 1. Pay TV and online services 2. Subscription and rental movies only. Purchase movies not included 3. SD/HD/3D titles counted once 4. Movies defined as: feature-length films, not including trailers, featurettes, try before you buy or children’s features.5. Correct as of 7th Nov 2014 Virgin Media + Netflix Total title count: 3,751 (A) Sexual 1 Chance 2 Dance 1:1 Thierry Henry 10 Rules For Sleeping Around 10 Things I Hate About You 10...»

«Poguntke   Für eine Direktwahl des Präsidenten der Europäischen Kommission? Referat für das Seminar Demokratische Legitimität und politische Führung in der Europäischen Union: Der Weg zur Europawahl 2014 Internationales Seminar organisiert von der Foundation for European Progressive Studies mit Unterstützung der Friedrich-Ebert-Stiftung und der Fondazione Italianieuropei Rom, 18. Januar 2013 Thomas Poguntke  Institut für Deutsches und Internationales Parteienrecht und...»

«Arkansas State University Beebe 2015-2016 University Catalog P. O. Box 1000 Beebe, Arkansas 72012-1000 501-882-3600 1-800-632-9985 (Admissions Only) www.asub.edu Arkansas State University Beebe TABLE OF CONTENTS Phone Directory Mission Statement Accreditation University Calendar Helpful Definitions Release of Student Information (Privacy Policy) Admissions and Transfer Policies Fees and Expenses Academic Policies Degrees and Certificates Special Academic Programs Transfer to Baccalaureate...»

«Important Dates for Planning Your Travel to NYC 2 Official Hotels 3 Bike Transport / Bike Shipping / Bike Rental 5 Schedule of Events 7 Partner Bike Shops 8 International Travel Partners 9 Frequently Asked Questions 10 Your GFNY World Travels 11 Thank you for your interest in Campagnolo GFNY Championship 2016! If you have any questions not covered in this Travel Guide, please refer to the GFNY website at www.gfny.com where a lot of race information is provided. If you don’t find the answer to...»

«Empirische Pädagogik 2009, 23 (4), 392-409 © Empirische Pädagogik 2009, 23 (4), 392-409 Zeitschrift zu Theorie und Praxis erziehungswissenschaftlicher Forschung Originalbeitrag Christian Imdorf Die betriebliche Verwertung von Schulzeugnissen bei der Ausbildungsstellenvergabe1 Zusammenfassung: Im Widerspruch zum öffentlichen Diskurs belegt die internationale Forschungslage, dass Schulqualifikationen bei der (Ausbildungs-)Stellenvergabe oft nur zweitrangig sind. Gleichwohl können...»

«The Plasticity of Barley (Hordeum vulgare) Leaf Wax Characteristics and their Effects on Early Events in the Powdery Mildew Fungus (Blumeria graminis f.sp. hordei): Interactive Adaptations at the Physiological and the Molecular Level Dissertation zur Erlangung des naturwissenschaftlichen Doktorgrades der Bayerischen Julius-Maximilians-Universität Würzburg vorgelegt von Vanessa Zabka aus Wuppertal Würzburg 2007 Eingereicht am: Mitglieder der Promotionskommission: Vorsitzender: Prof. Dr....»

<<  HOME   |    CONTACTS
2016 www.abstract.xlibx.info - Free e-library - Abstract, dissertation, book

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.