Yes, this line of thought is perfectly fine.

A set is decidable if and only if it has complexity
$\Delta_1$ in the arithmetic
hiearchy,
which provides a way to measure the complexity of a
definable set in terms of the complexity of its defining
formulas. In particular, a set is decidable when both it
and its complement can be characterized by an existential
statement $\exists n\ \varphi(x,n)$, where $\varphi$ has
only bounded quantifiers.

Thus, if you have a mathematical structure whose set of
truths exceeds this level of complexity, then the theory
cannot be decidable.

To show that the true theory of arithmetic has this level
of complexity amounts to showing that the arithmetic
hierarchy does not collapse. For every $n$, there are sets
of complexity $\Sigma_n$ not arising earlier in the
hierarchy. This follows inductively, starting with a
universal $\Sigma_1$ set.

Tarski's theorem on the non-definability of
truth
goes somewhat beyond the statement you quote, since he
shows that the collection of true statements of arithmetic
is not only undecidable, but is not even definable---it
does not appear at any finite level of the arithmetic
hiearchy.

Finally, it may be worth remarking on the fact that there
are two distinct uses of the word *undecidable* in this
context. On the one hand, an assertion $\sigma$ is not
decided by a theory $T$, if $T$ neither proves nor refutes
$\sigma$. On the other hand, a set of numbers (or strings,
or statements, etc.) is undecidable, if there is no Turing
machine program that correctly computes membership in the
set. The connection between the two notions is that if a
(computably axiomatizable) theory $T$ is complete, then its
set of theorems is decidable, since given any statement
$\sigma$, we can search for a proof of $\sigma$ or a proof
of $\neg\sigma$, and eventually we will find one or the
other. Another way to say this is that every computably
axiomatization of arithmetic must have an undecidable
sentence, for otherwise arithmetic truth would be
decidable, which is impossible by the halting problem (or
because the arithmetic hierarchy does not collapse, or any
number of other ways).

logical(or quantifier) complexity, or ascomputationalcomplexity. In the former case, as J.D. Hamkins showed, the answer to your question is "yes". In the latter case, I would presume the answer might be "no". (On the other hand, Godel's incompleteness phenomenon does hold for weak theories (bounded arithmetic), which have formal relations with computational complexity classes.) – Iddo Tzameret Sep 3 '10 at 12:47computationalcomplexity, that is, computability? In fact, it's hard for me to imagine an interesting formulation of Godel's incompleteness that doesn't involve computability: you could just say that PA is incomplete, but that seems too localized to be interesting; or there's the cocktail-party version that "arithmetic can't be axiomatized" which, taken literally, is false (just take the set of all sentences true in the structure (N, +, times)). – John Goodrick Sep 4 '10 at 3:25