Diagonalization argument for MAJORITY
Let $T_1,T_2,\ldots$ be an enumeration of all timed polytime machines, machine $T_i$ running in time $p_i(n)$. We will construct $A$ in stages. At each stage, the truth value of $A$ is defined on only finitely many inputs.

Stage $i$ handles $T_i$. Choose an input length $n$ such that (i) $A$ is completely undefined and (ii) $p_i(n) &lt; 2^{n-1}$. Run $T_i$ on $0^n$. Each time $T_i$ queries some yet undefined string in $A$, answer arbitrarily and fix the value of this string in $A$. Since $p_i(n) &lt; 2^{n-1}$, in particular $T_i$ queries fewer than $2^{n-1}$ strings of length $n$. If $T_i$ answered "Yes", then define all remaining strings of length $n$ to be outside $A$. If $T_i$ answered "No", then define all remaining strings of length $n$ to be inside $A$. Either way, the machine $T_i$ is wrong on input $0^n$.

After infinitely many steps, we have defined $A$ at infinitely many strings, but probably not all strings. Define $A$ arbitrarily on all remaining strings.

We note that the same proof works for every (time constructible) complexity class in which a machine cannot make at least $2^{n-1}$ queries on input of length $n$.