[過去ﾛｸﾞ] 基礎論者「ゲーデルの不完全性定理は間違った解説が多い」←どうでもよくね？ (645ﾚｽ)
上下前次1-新
抽出解除 ﾚｽ栞
このｽﾚｯﾄﾞは過去ﾛｸﾞ倉庫に格納されています｡
次ｽﾚ検索 歴削→次ｽﾚ 栞削→次ｽﾚ 過去ﾛｸﾞﾒﾆｭｰ
203(2): 2024/05/23(木)09:25 ID:67yCU2qb(4/5) AAS
要は証明可能な論理式の集合って再帰的可算集合だけど再帰的集合じゃねえよ、ってのがミソで
そこから先のシェファードソンとかはまあオマケ
ちなみに再帰的集合はΣ₁集合かつΠ₁集合ってのは知ってる？
204: 2024/05/23(木)09:32 ID:57Sqch+C(140/218) AAS
>>203
再帰的集合（recursive set）がΣ₁集合かつΠ₁集合であることについて説明します。
### 再帰的集合の定義
再帰的集合 \(R\) は、その要素が集合に属するかどうかを決定するアルゴリズムが存在する集合です。これは、任意の要素 \(x\) に対して、有限時間内に「はい」または「いいえ」と答えるアルゴリズムが存在することを意味します。
### Σ₁集合の定義
Σ₁集合 \(S\) は、次の形式の論理式で定義される集合です：
\[
省15
205: 2024/05/23(木)09:32 ID:57Sqch+C(141/218) AAS
>>203
### 再帰的集合がΠ₁集合であることの証明
再帰的集合 \(R\) は、その要素が集合に属するかどうかを決定するアルゴリズムが存在するため、次のように全称量化子を使って表現できます：
\[
R = \{ x \mid \forall n \, (\text{アルゴリズムが } n \text{ ステップ以内に } x \text{ が } R \text{ に属さない場合を示さない}) \}
\]
ここで、\(\text{アルゴリズムが } n \text{ ステップ以内に } x \text{ が } R \text{ に属さない場合を示さない\) という条件は量化子を含まない論理式で表現できます。このため、再帰的集合はΠ₁集合でもあります。
省3
上下前次1-新書関写板覧索設栞歴
ｽﾚ情報 赤ﾚｽ抽出 画像ﾚｽ抽出 歴の未読ｽﾚ AAｻﾑﾈｲﾙ
ぬこの手 ぬこTOP 1.823s*