Cover Image
QR Code

INTROENUMERABILITY, AUTOREDUCIBILITY, AND RANDOMNESS.

We define upper Psi $\Psi $ Ψ -autoreducible sets given an autoreduction procedure upper Psi $\Psi $ Ψ. Then, we show that for any upper Psi $\Psi $ Ψ , a measurable class of upper Psi $\Psi $ Ψ -autoreducible sets has measure zero. Using this, we show that classes of cototal, uniformly introenumera...

Full description

Published in:Journal of Symbolic Logic Vol. 91; no. 2; pp. 617 - 626
Main Author: LI, ANG
Format: Article
Published: Cambridge University Press Jun2026
Subjects:
Recursion theory
Uncertainty (Information theory)
Online Access:View this record in EBSCOhost
fields @attributes:
  recordID: 1
pdfLink:
plink: https://search.ebscohost.com/login.aspx?direct=true&db=hlh&AN=194236703&site=ehost-live
header:
  @attributes:
    shortDbName: hlh
    uiTerm: 194236703
    longDbName: Humanities International Complete
    uiTag: AN
  controlInfo:
    bkinfo:
    jinfo:
      jid:
        00224812
        3TY
      jtl: Journal of Symbolic Logic
      issn: 00224812
      maglogo: N
    pubinfo:
      dt: Jun2026
      vid: 91
      iid: 2
      pid: 15979
      pub: Cambridge University Press
    artinfo:
      ui:
        194236703
        10.1017/jsl.2023.95
      ppf: 617
      ppct: 9
      formats:
      tig:
        atl: INTROENUMERABILITY, AUTOREDUCIBILITY, AND RANDOMNESS.
      aug:
        au: LI, ANG
        affil: DEPARTMENT OF MATHEMATICS UNIVERSITY OF WISCONSIN–MADISON 480 LINCOLN DRIVE MADISON, WI 53706, USA
      su:
        Recursion theory
        Uncertainty (Information theory)
      sug:
        subj:
          Recursion theory
          Uncertainty (Information theory)
      keyword:
        algorithmic randomness
        autoreducible
        computability theory
        cototal
        enumeration degree
        introenumerable
        logic
        measure
      ab: We define upper Psi $\Psi $ Ψ -autoreducible sets given an autoreduction procedure upper Psi $\Psi $ Ψ. Then, we show that for any upper Psi $\Psi $ Ψ , a measurable class of upper Psi $\Psi $ Ψ -autoreducible sets has measure zero. Using this, we show that classes of cototal, uniformly introenumerable, introenumerable, and hyper-cototal enumeration degrees all have measure zero. By analyzing the arithmetical complexity of the classes of cototal sets and cototal enumeration degrees, we show that weakly 2-random sets cannot be cototal and weakly 3-random sets cannot be of cototal enumeration degree. Then, we see that this result is optimal by showing that there exists a 1-random cototal set and a 2-random set of cototal enumeration degree. For uniformly introenumerable degrees and introenumerable degrees, we utilize upper Psi $\Psi $ Ψ -autoreducibility again to show the optimal result that no weakly 3-random sets can have introenumerable enumeration degree. We also show that no 1-random set can be introenumerable.
      pubtype: Academic Journal
      doctype: Article
      src: R
    language: English
    refInfo:
    copyright:
      @attributes:
        flag: Y
      dt:
        @attributes:
          year: 2026
    holdings:
      @attributes:
        islocal: N