We show that infinite sets whose power-sets are Dedekind-finite can only carry N₀-categorical first order structures. We identify other subclasses of this class of Dedekind-finite sets, and discuss their possible first order structures.