カービー と パリス は 後 に グッドスタイン の 定理 （ 自然 数 の 数列 に関する 命題 で あり 、 パリス・ハーリントン の 原理 より も いくら か 易しい ） が ペアノ 算術 で は 決定 不能 で ある こと を 示し た 。

計算 機 科学 で 応用 さ れる { 仮 リンク | Kruskal の 木 定理 | en | Kruskal ' s tree theorem } は ペアノ 算術 で は 決定 不能 だ が 集合 論 で は 証明 できる 。

実際 、 Kruskal の 木 定理 （ または その 有限 版 ） は 、 { 仮 リンク | 他 叙 主義 | en | predicativism } と 呼ば れる 数学 的 哲学 に 基づい て 構築 さ れ た もっと 強い 体系 の 下 で も 決定 不能 で ある 。

これ に 関連 し 、 更に 一般 的 な { 仮 リンク | graph minors 定理 | en | graph minor theorem }（ 2003 年 ） は 計算 複雑 性 理論 に 影響 する 。

グレゴリー・チャイティン は アルゴリズム 情報 理論 における 決定 不能 命題 を 発見 し 、 その 状況 下 で 新た な 不完全性 定理 を 得 た 。

チャイティン の 定理 に よる と 、 十分 な 算術 を 表現 可能 な いかなる 理論 において も 、 どの よう な 数 で あっ て も c より も 大きな コルモゴロフ 複雑 性 を 有する こと が その 理論 上 で は 証明 でき ない よう な 、 上限 c が 存在 する 。

ゲーデル の 定理 が 嘘つき の パラドックス と 関係 し て いる の に対し 、 チャイティン の 結果 は ベリー の パラドックス に 関係 し て いる 。

第 1 不完全性 定理 は ロビンソン 算術 を 含ん で いれ ば 十分 で ある 。

第 2 不完全性 定理 は ロビンソン 算術 に Σ 1 論理 式 に対する 数学 的 帰納 法 の 公理 図式 を 追加 し た 体系 （ I Σ 1 ） を 含ん で いれ ば 十分 で ある 。

ペアノ 算術 は これ を 含む から 、 ペアノ 算術 を 含む 理論 は 第 2 不完全性 定理 の 適用 範囲 で ある 。

ゲーデル の 定理 は 無矛盾 な 理論 について のみ 適用 できる 。

ゲーデル の 定理 が 成り立つ の は 、 飽くまで 定理 が 必要 と し て いる 仮定 を 満足 する よう な 形式 的 体系 に 限ら れる 。

例えば 、 ユークリッド 幾何 学 の 一 階 公理 化 理論 、 実 閉体 の 理論 、 乗算 が 全域 で 可能 な こと を 証明 でき ない よう な 算術 理論 、 これら は 何れ も ゲーデル の 定理 に 必要 な 仮定 を 満たさ ない 。

三つ 目 の 例 に関して 言え ば 、 Dan E . Willard は 第 二 不完全性 定理 に 必要 な 仮定 を 満たさ ない よう な 様々 な 弱い 算術 理論 を 調べ た （ 例えば Willard 2001 ） 。

ゲーデル の 定理 は 実効 的 に 生成 さ れ た （ 即ち 、 帰納的 可算 な ） 理論 について のみ 適用 できる 。

もし 自然 数 に関する 真 で ある 文 を 全て 公理 と する よう な 理論 が ある と する と 、 この 理論 は 無矛盾 かつ 完全 で あり 、 ペアノ 算術 を 含み つつ ゲーデル の 定理 は 全く 成立 し なく なる 。

第 二 不完全性 定理 が 示す の は 、 ある 公理系 の 無 矛盾 性 は その 公理系 自身 で は 証明 でき ない という こと で あっ て 、 他 の 無矛盾 な 公理系 から も 証明 でき ない と は 言っ て い ない 。

不完全性 定理 は 「 『 自然 数 論 を 含む 帰納的 公理 化 可能 な 理論 が 、 無 矛盾 （ ω 無 矛盾 ） で あれ ば 』 ～ 」 という 形 の 定理 で ある 。

したがって 、 自然 数 論 を 含ま ない 公理系 や 、 帰納的 公理 化 可能 で ない 理論 が 完全 で あっ て も 、 不完全性 定理 と は 矛盾 し ない 。

その ため 、 不完全性 定理 は 適用 でき ない 。