h+1 heads express more than h heads

We prove the existence of the following hierarchy: for each $h$ there exists a decision problem which can be solved by a one layer transformer with $h+1$ heads but not with only $h$ heads. The result holds for a standard transformer architecture, which includes both attention and feed-forward blocks.