Associativity vs blocks per set in fixed size caches
The number of sets determines the size of the index, because the index tells you what set to refer to.  If you increase associativity by giving more blocks to each set then you run out of blocks sooner and so you can afford fewer sets.  If you have fewer sets then you have a smaller index.

If half the sets disappear then those addresses have to be handled by the remaining sets.  Because each set now has more addresses that it serves, it needs an extra bit of tag to distinguish them.