Given that for any $n \in \mathbb{N}$, there are $2^n$ consistent, axiomatizable extensions of $\mathbf{Q}$ that are pairwise inconsistent, show that there is a nondenumerable set of such consistent extensions of $\mathbf{Q}$ that are pairwise inconsistent.
non-denumerable means an infinite set which cannot be put in one-to-one correspondence with the set of natural numbers.
Do I use the fact that the set of all sets of positive integers $P^*$ is not enumerable? I need a hint on this.
First, let's tweak the problem a bit. Note that if $T_1,T_2$ are individually consistent but mutually inconsistent and $S_1\supseteq T_1,S_2\supseteq T_2$ are complete and individually consistent, then $S_1\not=S_2$. This means that we can rewrite our initial result as "$\mathsf{Q}$ has infinitely many complete consistent extensions," and rewrite our goal as "$\mathsf{Q}$ has uncountably many complete consistent extensions." This isn't essential, but thinking about complete theories is in my opinion a bit easier than thinking about incomplete ones.
Next, let's rule out a plausible attempt. A natural thing to hope at this point is that there's a very general result here - namely, that every theory with infinitely many consistent complete extensions has uncountably many consistent complete extensions. However, this is false. Consider for example the empty language. There are countably infinitely many consistent complete theories in this language (so the empty theory in the empty language is a counterexample to the hope above):
For each $n\in\mathbb{N}$, the deductive closure $A_n$ of the one-sentence theory$$\{\exists x_1,...,x_n[(\bigwedge_{1\le i<j\le n}x_i\not=x_j)\wedge\forall y(\bigvee_{1\le i\le n}y=x_i)]\}$$ is complete, and clearly $A_n\not=A_m$ if $m\not=n$.
The only remaining complete consistent theory is the deductive closure of the following infinite set of axioms: $$\{\forall x_1,...,x_n\exists y(\bigwedge_{1\le i\le n}x_i\not=y):n\in\mathbb{N}\}.$$
(Verifying the above is a good exercise.) So we need to use something particular to $\mathsf{Q}$, here.
OK, now finally let's get to the answer to the problem.
The key fact about $\mathsf{Q}$ we'll use is ... Godel's first incompleteness theorem! There are various forms of the first incompleteness theorem; the one we'll want is the following:
(You should check that this does in fact follow from whichever version of the incompleteness theorem you're familiar with.)
Fix some enumeration $(\varphi_i)_{i\in\mathbb{N}}$ of the sentences in the language of $\mathsf{Q}$. We can build a binary tree $\mathbb{T}\subseteq 2^{<\mathbb{N}}$ of "ways to extend $\mathsf{Q}$" as follows: $\mathbb{T}$ is the set of all finite binary sequences $\sigma$ such that the theory $$X_\sigma:=\mathsf{Q}\cup\{\varphi_i: i<\vert\sigma\vert, \sigma(i)=1\}\cup\{\neg\varphi_i: i<\vert\sigma\vert, \sigma(i)=0\}$$ is consistent. This is in fact a tree (that is, it is closed downwards) since a subtheory of a consistent theory is again consistent. Infinite paths through $\mathbb{T}$ correspond exactly to complete consistent extensions of $\mathsf{Q}$, so we just need to count the paths.
Now the consistency of $\mathsf{Q}$ means that $\mathbb{T}$ has no "dead end" nodes - if $\sigma\in \mathbb{T}$ then there is some $\tau\succ\sigma$ with $\tau\in\mathbb{T}$. However, the incompleteness fact $(*)$ above lets us do even better: it implies that $\mathbb{T}$ has no non-splitting nodes. That is, if $\sigma\in\mathbb{T}$ then there are incompatible extensions $\tau_1,\tau_2\succ\sigma$ with $\tau_1,\tau_2\in\mathbb{T}$. Our goal then follows from the following purely combinatorial fact, which is a good exercise:
HINT: think about how the splitting criterion lets us embed the full binary tree $2^{<\mathbb{N}}$ into $\mathbb{A}$, and how that in turn yields an embedding of the set of all infinite binary sequences into the set of paths through $\mathbb{A}$.
What if we didn't have $(*)$? Well, consider the obstacle pointed out in the previous section: the empty theory in the empty language. The corresponding tree $\mathbb{E}$ for this theory is still infinite and still has no dead ends; however, it has lots of non-splitting nodes. In fact, there is exactly one complete theory in the empty language whose corresponding path through $\mathbb{E}$ does not go through a non-splitting node; can you figure out which it is? (HINT: you should have in mind a picture like $\{0\}\cup\{{1\over n}:n\in\mathbb{N}\}$.)
As a coda, note that we can think of the above argument as essentially topological in nature, as follows. Every consistent theory $T$ has a corresponding nonempty space $Comp(T)$ whose points are complete consistent extensions of $T$. Finite axiomatizability modulo a theory corresponds to isolatedness in this space, so $(*)$ says that $Comp(T)$ has no isolated points. While nonempty spaces without isolated points could still only have countably many points (e.g. $\mathbb{Q}$ with the usual topology), no such space can be compact - and by the compactness theorem, $Comp(T)$ is always compact. We won't actually use the language of topology - instead we'll just talk about paths through trees - but the topological "flavor" is absolutely worth pointing out and will become crucial in more advanced situations.