Rogers semilattices in the analytical hierarchy: The case of finite families

Abstract: A numbering of a countable family

S

is a surjective map from the set of natural numbers

o m e g a

onto

S

. The paper studies Rogers semilattices, i.e. upper semilattices induced by the reducibility between numberings, for families

S s u b s e t P (o m e g a)

. Working in set theory ZF+DC+PD, we obtain the following results on families from various levels of the analytical hierarchy. For a non-zero number

n

, by

E_{n}^{1}

we denote

P i_{n}^{1}

if

n

is odd, and

S i g m a_{n}^{1}

if

n

is even. We show that for a finite family

S

of

E_{n}^{1}

sets, its Rogers

E_{n}^{1}

-semilattice has the greatest element if and only if

S

contains the least element under set-theoretic inclusion. Furthermore, if

S

does not have the

s u b s e t e q

-least element, then the corresponding Rogers

E_{n}^{1}

-semilattice is upwards dense.

This page was built for publication: Rogers semilattices in the analytical hierarchy: The case of finite families