6533b853fe1ef96bd12aca87

RESEARCH PRODUCT

Category, Measure, Inductive Inference: A Triality Theorem and Its Applications

Carl SmithRusins Freivalds

subject

Discrete mathematicsCategoryConcrete categoryCategory of setsCategory theoryEnriched categoryPrevalent and shy setsMathematics2-categoryDual (category theory)

description

The famous Sierpinski-Erdos Duality Theorem [Sie34b, Erd43] states, informally, that any theorem about effective measure 0 and/or first category sets is also true when all occurrences of "effective measure 0" are replaced by "first category" and vice versa. This powerful and nice result shows that "measure" and "category" are equally useful notions neither of which can be preferred to the other one when making formal the intuitive notion "almost all sets." Effective versions of measure and category are used in recursive function theory and related areas, and resource-bounded versions of the same notions are used in Theory of Computation. Again they are dual in the same sense.We show that in the world of recursive functions there is a third equipotent notion dual to both measure and category. This new notion is related to learnability (also known as inductive inference or identifiability). We use the term "triality" to describe this three-party duality.

yearjournalcountryeditionlanguage
2002-01-01
https://doi.org/10.1007/3-540-45995-2_35