2 edited tags
1

# Equivalence of families of objects with the same counting function

Consider two countable families of objects, given as unions of finite subfamilies:

$F^k = \bigcup_{n \in \mathbb{N}} F^k_n$, k = 1,2.

Let there be a bijection $f: F^1 \rightarrow F^2$ such that $x \in F^1_n \Leftrightarrow f(x) \in F^2_n$ for all n $\in \mathbb{N}$.

This means: The two families have the same counting functions $f^1(n) = f^2(n)$ for all n $\in \mathbb{N}$ with $f^k(n) = |F^k_n|$.

This may be by sheer accident, or it may be because the two families are in some sense essentially the same.

Can the notions of "by accident" and "essentially the same" be distinguished in this context, and how?

"Essentially the same" might mean: "there is a computable bijection" and "by accident" might mean: "there is no computable bijection". Or might category theoretical notions lead further?

Are there known examples of two families as above that have the same counting functions by accident (in the meaning just mentioned or another one)?

PS: More sensible tags are welcome!