Orbit-finite sets

Orbit finite sets are sets which, on the one hand, appear to be infinite, yet on the other hand are "finite enough" (up to some notion of equality) to have algorithms run on them.

Intuition

For example, consider the set

\{ X \mid X \subseteq \mathbb{N} \land \vert X \vert \leq 3 \}

This set consists of all subsets of \mathbb{N} of cardinality less than or equal to 3. It is clearly infinite. Yet, up to automorphism, the set "essentially" has four elements, namely

\begin{aligned}
&\emptyset \\
&\{ 0 \} \\
&\{ 0, 1 \} \\
&\{ 0, 1, 2 \} \\
\end{aligned}

It is thus an orbit-finite set.

References

A "gentle" introduction to orbit-finite sets was delivered as an invited talk at ICALP 2017:

Bojanczyk, Mikolaj. Orbit-Finite Sets and Their Algorithms (Invited Talk). ICALP 2017. https://drops.dagstuhl.de/opus/volltexte/2017/7429/

@InProceedings{bojanczyk_2017,
  author =	{Mikolaj Bojanczyk},
  title =	{{Orbit-Finite Sets and Their Algorithms (Invited Talk)}},
  booktitle =	{44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)},
  pages =	{1:1--1:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  year =	{2017},
  volume =	{80},
  editor =	{Ioannis Chatzigiannakis and Piotr Indyk and Fabian Kuhn and Anca Muscholl},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  doi =		{10.4230/LIPIcs.ICALP.2017.1}
}