0
$\begingroup$

I am having difficulties proving the following: If $\cal{A}$ is a connected class (i.e $\cal{A_\emptyset} = \emptyset$), then I need to show that the powers of $\mathcal{A}$ form a locally finite sequence. In other words, the sequence $\mathcal{S} = (\mathcal{A}^0, \mathcal{A}^1, \mathcal{A}^2, ...)$ is locally finite.

I know that to show that $\mathcal{S}$ is locally finite, i need to show that for any fintie set $X$, there are at most a finite amount sets $[(\mathcal{A}^i)_{X} : i \ge 0]$ that are not empty. However, I am quite unsure as to how to start.

If I could have a hint on how to do this, it would be greatly appreciated. I should also add that I don't have any other theorems to work with, besides for the basic definitions provided.

Thanks!

EDIT: I would also like a reference to material like this, if possible. I have no idea what this would be classified as though. We are seeing this in my enumeration course, but searching on Google does not seem to yield much information. On Wikipedia, I found a list of structures/classes (http://en.wikipedia.org/wiki/Algebraic_structure), though I am unsure as to what I should be looking up.

  • 1
    You could search for [combinatorial classes](http://en.wikipedia.org/wiki/Symbolic_combinatorics) and [combinatorial species](http://en.wikipedia.org/wiki/Combinatorial_species). You should definitely download Flajolet & Sedgewick, [*Analytic Combinatorics*](http://algo.inria.fr/flajolet/Publications/AnaCombi/anacombi.html).2012-11-20

1 Answers 1

1

You want to show that if $\mathcal A_\varnothing=\varnothing$, then for each finite set $X$ there is an $n_X\in\Bbb Z^+$ such that $\mathcal A_X^k=\varnothing$ for all $k\ge n_X$.

An $\mathcal A^k$-structure on $X$ is essentially an ordered $k$-tuple $\langle\alpha_1,\dots,\alpha_k\rangle$ such that:

  1. $\alpha_i$ is an $\mathcal A$-structure on some $S_i\subseteq X$ for $i=1,\dots,k$,
  2. $\{S_1,\dots,S_k\}$ are pairwise disjoint, and
  3. $\bigcup_{i=1}^kS_i=X$.

(This isn’t exactly right, assuming that you’re using the definition in David Wagner’s CO 430 notes that I found online: that definition makes it $\langle\langle\langle\dots\langle\alpha_1,\alpha_2\rangle,\alpha_3\rangle,\dots,\alpha_{k-1}\rangle,\alpha_k\rangle$, but the two are equivalent.)

If $\mathcal A_\varnothing=\varnothing$, each of the sets $S_i$ must be non-empty, so they partition $X$. How many of them can there be at most?

  • 0
    @Nizbel99: You’re welcome. I figured that they probably were, given the identical terminology and notation and the fact that you’re at Waterloo.2012-11-20