When you increase $\alpha$, you increase the probability of rejecting true nulls, and the way to achieve that is by making the rejection region larger. When that happens, the cases in which we reject can only increase (or in any case not decrease), be it when the null is true or when it is false. Then, $\beta$, the probability of a false acceptance, must decrease (or in any case not increase).
Of course, the reasoning works mutatis mutandis with decreasing $\alpha$.
To write that up a little more formally, denote by $\cal{T}$ the support of the test statistic $t$. A significance level $\alpha$ is associated with a critical value $c_\alpha$. W.l.o.g.$^*$ (take the absolute value of $t$ if the original test statistic implied a rejection when it took value less than $-c_\alpha$ or bigger than $c_\alpha$), we reject if $t>c_\alpha$.
This defines the rejection region $R_\alpha:=\{t\in\cal{T}:t>c_\alpha\}$.
We then obtain the rejection probability, given a true parameter $\theta$, as
$$
P_\theta(t\in R_\alpha)
$$
If we test the null $\theta=\theta_0$ and it is actually true (setting aside issues like errors in rejection probabilities stemming from using asymptotic tests and/or nuisance parameters),
$$
P_{\theta_0}(t\in R_\alpha)=\alpha
$$
When $\theta\neq\theta_0$,
$$
P_{\theta}(t\in R_\alpha)=1-\beta,
$$
the power of the test.
Now, if we want to make $\alpha$ smaller, we must make make $R_\alpha$ smaller, $$\alpha_1<\alpha_2\Rightarrow R_{\alpha_1}\subset R_{\alpha_2}.$$
Then, for any $\theta$, the probability that a random variable takes realizations in a smaller set is smaller (I am handwaiving over strict and weak inequalities here) than that it takes realizations in the larger set,
$$
P_{\theta}(t\in R_{\alpha_1}) < P_{\theta}(t\in R_{\alpha_2})
$$
$^*$: Actually, here we have a little scope for coming up with pathological cases to construct other cases: If we only require rejections with probability $\alpha$ under the null, we could also allocate the first, larger, rejection region of, say, a right-tailed test $\theta\leq\theta_0$ to the left tail of the null distribution. The probability that $t$ takes realizations in that region will be even smaller than $\alpha$ if the null is false in the sense that $\theta>\theta_0$. If we now decrease $\alpha$ and push that smaller rejection region to where it belongs, the right tail of the null distribution, power will be larger than before.
Of course, no sane person would have picked the first rejection region in that way, because a sensible auxiliary requirement for a rejection region is that it contains values which we would not expect to occur frequently if the null is actually true.
Now, when the null $\theta\leq\theta_0$ is true, small values of $t$ (i.e., values in the left tail of the least favorable distribution $\theta=\theta_0$) may not be evidence against the null at all.