Hypersimplicity and semicomputability in the weak truth table degrees View Full Text


Ontology type: schema:ScholarlyArticle      Open Access: True


Article Info

DATE

2005-11

AUTHORS

George Barmpalias

ABSTRACT

We study the classes of hypersimple and semicomputable sets as well as their intersection in the weak truth table degrees. We construct degrees that are not bounded by hypersimple degrees outside any non-trivial upper cone of Turing degrees and show that the hypersimple-free c.e. wtt degrees are downwards dense in the c.e. wtt degrees. We also show that there is no maximal (w.r.t. ≤wtt) hypersimple wtt degree. Moreover, we consider the sets that are both hypersimple and semicomputable, characterize them as the (bi-infinite) c.e. cuts of computable orderings of ℕ of order type ω+ω* and study their wtt degrees. We show that there are hypersimple degrees that are not bounded by any hypersimple semicomputable degree, investigate relationships with the join and look for maximal and minimal elements of related classes. More... »

PAGES

1045-1065

References to SciGraph publications

  • 2004-11. Approximation Representations for Δ2 Reals in ARCHIVE FOR MATHEMATICAL LOGIC
  • 1987. Recursively Enumerable Sets and Degrees in NONE
  • Journal

    TITLE

    Archive for Mathematical Logic

    ISSUE

    8

    VOLUME

    44

    Author Affiliations

    Identifiers

    URI

    http://scigraph.springernature.com/pub.10.1007/s00153-005-0288-9

    DOI

    http://dx.doi.org/10.1007/s00153-005-0288-9

    DIMENSIONS

    https://app.dimensions.ai/details/publication/pub.1038866740


    Indexing Status Check whether this publication has been indexed by Scopus and Web Of Science using the SN Indexing Status Tool
    Incoming Citations Browse incoming citations for this publication using opencitations.net

    JSON-LD is the canonical representation for SciGraph data.

    TIP: You can open this SciGraph record using an external JSON-LD service: JSON-LD Playground Google SDTT

    [
      {
        "@context": "https://springernature.github.io/scigraph/jsonld/sgcontext.json", 
        "about": [
          {
            "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/1608", 
            "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
            "name": "Sociology", 
            "type": "DefinedTerm"
          }, 
          {
            "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/16", 
            "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
            "name": "Studies in Human Society", 
            "type": "DefinedTerm"
          }
        ], 
        "author": [
          {
            "affiliation": {
              "alternateName": "University of Leeds", 
              "id": "https://www.grid.ac/institutes/grid.9909.9", 
              "name": [
                "School of Mathematics, University of Leeds, LS2 9JT, Leeds, United Kingdom"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Barmpalias", 
            "givenName": "George", 
            "id": "sg:person.013527770623.53", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013527770623.53"
            ], 
            "type": "Person"
          }
        ], 
        "citation": [
          {
            "id": "https://doi.org/10.1002/malq.200310105", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1000171622"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/s00153-004-0234-2", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1032656808", 
              "https://doi.org/10.1007/s00153-004-0234-2"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/s00153-004-0234-2", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1032656808", 
              "https://doi.org/10.1007/s00153-004-0234-2"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/s00153-004-0234-2", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1032656808", 
              "https://doi.org/10.1007/s00153-004-0234-2"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1090/s0002-9947-1968-0220595-7", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1036659697"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.2178/jsl/1058448447", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1051589702"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-662-02460-7", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1109712107", 
              "https://doi.org/10.1007/978-3-662-02460-7"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-662-02460-7", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1109712107", 
              "https://doi.org/10.1007/978-3-662-02460-7"
            ], 
            "type": "CreativeWork"
          }
        ], 
        "datePublished": "2005-11", 
        "datePublishedReg": "2005-11-01", 
        "description": "We study the classes of hypersimple and semicomputable sets as well as their intersection in the weak truth table degrees. We construct degrees that are not bounded by hypersimple degrees outside any non-trivial upper cone of Turing degrees and show that the hypersimple-free c.e. wtt degrees are downwards dense in the c.e. wtt degrees. We also show that there is no maximal (w.r.t. \u2264wtt) hypersimple wtt degree. Moreover, we consider the sets that are both hypersimple and semicomputable, characterize them as the (bi-infinite) c.e. cuts of computable orderings of \u2115 of order type \u03c9+\u03c9* and study their wtt degrees. We show that there are hypersimple degrees that are not bounded by any hypersimple semicomputable degree, investigate relationships with the join and look for maximal and minimal elements of related classes.", 
        "genre": "research_article", 
        "id": "sg:pub.10.1007/s00153-005-0288-9", 
        "inLanguage": [
          "en"
        ], 
        "isAccessibleForFree": true, 
        "isPartOf": [
          {
            "id": "sg:journal.1136186", 
            "issn": [
              "0933-5846", 
              "1432-0665"
            ], 
            "name": "Archive for Mathematical Logic", 
            "type": "Periodical"
          }, 
          {
            "issueNumber": "8", 
            "type": "PublicationIssue"
          }, 
          {
            "type": "PublicationVolume", 
            "volumeNumber": "44"
          }
        ], 
        "name": "Hypersimplicity and semicomputability in the weak truth table degrees", 
        "pagination": "1045-1065", 
        "productId": [
          {
            "name": "readcube_id", 
            "type": "PropertyValue", 
            "value": [
              "b92487fb254a1589a4d5f0aee515cc1bf3665749ddf56a51ac938fdf6f3b99ae"
            ]
          }, 
          {
            "name": "doi", 
            "type": "PropertyValue", 
            "value": [
              "10.1007/s00153-005-0288-9"
            ]
          }, 
          {
            "name": "dimensions_id", 
            "type": "PropertyValue", 
            "value": [
              "pub.1038866740"
            ]
          }
        ], 
        "sameAs": [
          "https://doi.org/10.1007/s00153-005-0288-9", 
          "https://app.dimensions.ai/details/publication/pub.1038866740"
        ], 
        "sdDataset": "articles", 
        "sdDatePublished": "2019-04-11T14:30", 
        "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
        "sdPublisher": {
          "name": "Springer Nature - SN SciGraph project", 
          "type": "Organization"
        }, 
        "sdSource": "s3://com-uberresearch-data-dimensions-target-20181106-alternative/cleanup/v134/2549eaecd7973599484d7c17b260dba0a4ecb94b/merge/v9/a6c9fde33151104705d4d7ff012ea9563521a3ce/jats-lookup/v90/0000000373_0000000373/records_13090_00000001.jsonl", 
        "type": "ScholarlyArticle", 
        "url": "https://link.springer.com/10.1007%2Fs00153-005-0288-9"
      }
    ]
     

    Download the RDF metadata as:  json-ld nt turtle xml License info

    HOW TO GET THIS DATA PROGRAMMATICALLY:

    JSON-LD is a popular format for linked data which is fully compatible with JSON.

    curl -H 'Accept: application/ld+json' 'https://scigraph.springernature.com/pub.10.1007/s00153-005-0288-9'

    N-Triples is a line-based linked data format ideal for batch operations.

    curl -H 'Accept: application/n-triples' 'https://scigraph.springernature.com/pub.10.1007/s00153-005-0288-9'

    Turtle is a human-readable linked data format.

    curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/s00153-005-0288-9'

    RDF/XML is a standard XML format for linked data.

    curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/s00153-005-0288-9'


     

    This table displays all metadata directly associated to this object as RDF triples.

    78 TRIPLES      21 PREDICATES      32 URIs      19 LITERALS      7 BLANK NODES

    Subject Predicate Object
    1 sg:pub.10.1007/s00153-005-0288-9 schema:about anzsrc-for:16
    2 anzsrc-for:1608
    3 schema:author N511baf68c16d41818dc7de930f4e97a2
    4 schema:citation sg:pub.10.1007/978-3-662-02460-7
    5 sg:pub.10.1007/s00153-004-0234-2
    6 https://doi.org/10.1002/malq.200310105
    7 https://doi.org/10.1090/s0002-9947-1968-0220595-7
    8 https://doi.org/10.2178/jsl/1058448447
    9 schema:datePublished 2005-11
    10 schema:datePublishedReg 2005-11-01
    11 schema:description We study the classes of hypersimple and semicomputable sets as well as their intersection in the weak truth table degrees. We construct degrees that are not bounded by hypersimple degrees outside any non-trivial upper cone of Turing degrees and show that the hypersimple-free c.e. wtt degrees are downwards dense in the c.e. wtt degrees. We also show that there is no maximal (w.r.t. ≤wtt) hypersimple wtt degree. Moreover, we consider the sets that are both hypersimple and semicomputable, characterize them as the (bi-infinite) c.e. cuts of computable orderings of ℕ of order type ω+ω* and study their wtt degrees. We show that there are hypersimple degrees that are not bounded by any hypersimple semicomputable degree, investigate relationships with the join and look for maximal and minimal elements of related classes.
    12 schema:genre research_article
    13 schema:inLanguage en
    14 schema:isAccessibleForFree true
    15 schema:isPartOf N3a8d8dfdb0154201b3eb039085483a8e
    16 N7711246d6bed46a9930b86a0d4088e91
    17 sg:journal.1136186
    18 schema:name Hypersimplicity and semicomputability in the weak truth table degrees
    19 schema:pagination 1045-1065
    20 schema:productId N7cb90171ff3e402081140d828badff89
    21 Ne1bade958ed2443da9a51dab2c3dfac3
    22 Nff78910700f54083a477bf41a12369d0
    23 schema:sameAs https://app.dimensions.ai/details/publication/pub.1038866740
    24 https://doi.org/10.1007/s00153-005-0288-9
    25 schema:sdDatePublished 2019-04-11T14:30
    26 schema:sdLicense https://scigraph.springernature.com/explorer/license/
    27 schema:sdPublisher N86e0926e62c44575a450bdce8f2f5659
    28 schema:url https://link.springer.com/10.1007%2Fs00153-005-0288-9
    29 sgo:license sg:explorer/license/
    30 sgo:sdDataset articles
    31 rdf:type schema:ScholarlyArticle
    32 N3a8d8dfdb0154201b3eb039085483a8e schema:volumeNumber 44
    33 rdf:type schema:PublicationVolume
    34 N511baf68c16d41818dc7de930f4e97a2 rdf:first sg:person.013527770623.53
    35 rdf:rest rdf:nil
    36 N7711246d6bed46a9930b86a0d4088e91 schema:issueNumber 8
    37 rdf:type schema:PublicationIssue
    38 N7cb90171ff3e402081140d828badff89 schema:name dimensions_id
    39 schema:value pub.1038866740
    40 rdf:type schema:PropertyValue
    41 N86e0926e62c44575a450bdce8f2f5659 schema:name Springer Nature - SN SciGraph project
    42 rdf:type schema:Organization
    43 Ne1bade958ed2443da9a51dab2c3dfac3 schema:name doi
    44 schema:value 10.1007/s00153-005-0288-9
    45 rdf:type schema:PropertyValue
    46 Nff78910700f54083a477bf41a12369d0 schema:name readcube_id
    47 schema:value b92487fb254a1589a4d5f0aee515cc1bf3665749ddf56a51ac938fdf6f3b99ae
    48 rdf:type schema:PropertyValue
    49 anzsrc-for:16 schema:inDefinedTermSet anzsrc-for:
    50 schema:name Studies in Human Society
    51 rdf:type schema:DefinedTerm
    52 anzsrc-for:1608 schema:inDefinedTermSet anzsrc-for:
    53 schema:name Sociology
    54 rdf:type schema:DefinedTerm
    55 sg:journal.1136186 schema:issn 0933-5846
    56 1432-0665
    57 schema:name Archive for Mathematical Logic
    58 rdf:type schema:Periodical
    59 sg:person.013527770623.53 schema:affiliation https://www.grid.ac/institutes/grid.9909.9
    60 schema:familyName Barmpalias
    61 schema:givenName George
    62 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013527770623.53
    63 rdf:type schema:Person
    64 sg:pub.10.1007/978-3-662-02460-7 schema:sameAs https://app.dimensions.ai/details/publication/pub.1109712107
    65 https://doi.org/10.1007/978-3-662-02460-7
    66 rdf:type schema:CreativeWork
    67 sg:pub.10.1007/s00153-004-0234-2 schema:sameAs https://app.dimensions.ai/details/publication/pub.1032656808
    68 https://doi.org/10.1007/s00153-004-0234-2
    69 rdf:type schema:CreativeWork
    70 https://doi.org/10.1002/malq.200310105 schema:sameAs https://app.dimensions.ai/details/publication/pub.1000171622
    71 rdf:type schema:CreativeWork
    72 https://doi.org/10.1090/s0002-9947-1968-0220595-7 schema:sameAs https://app.dimensions.ai/details/publication/pub.1036659697
    73 rdf:type schema:CreativeWork
    74 https://doi.org/10.2178/jsl/1058448447 schema:sameAs https://app.dimensions.ai/details/publication/pub.1051589702
    75 rdf:type schema:CreativeWork
    76 https://www.grid.ac/institutes/grid.9909.9 schema:alternateName University of Leeds
    77 schema:name School of Mathematics, University of Leeds, LS2 9JT, Leeds, United Kingdom
    78 rdf:type schema:Organization
     




    Preview window. Press ESC to close (or click here)


    ...