[過去ﾛｸﾞ] 基礎論者「ゲーデルの不完全性定理は間違った解説が多い」←どうでもよくね？ (645ﾚｽ)
上下前次1-新
抽出解除 ﾚｽ栞
このｽﾚｯﾄﾞは過去ﾛｸﾞ倉庫に格納されています｡
次ｽﾚ検索 歴削→次ｽﾚ 栞削→次ｽﾚ 過去ﾛｸﾞﾒﾆｭｰ
195(7): 2024/05/23(木) 09:02:26.56 ID:iy+WwMGU(14/26)調 AAS
>>192 再帰的集合と再帰的可算集合(r.e.集合)の違い、分かる？
196(1): 2024/05/23(木) 09:04:09.44 ID:57Sqch+C(133/218)調 AAS
>>195
再帰的集合（recursive set）と再帰的可算集合（recursively enumerable set, r.e.集合）の違いについて説明します。
1. **再帰的集合（recursive set）**:
- **定義**: 再帰的集合は、その要素が与えられたときに、その要素が集合に属するかどうかを決定するアルゴリズム（決定手続き）が存在する集合です。
- **特徴**: 再帰的集合は決定可能集合とも呼ばれ、すべての要素に対して必ず有限時間内に「はい」か「いいえ」を返すアルゴリズムが存在します。
2. **再帰的可算集合（recursively enumerable set, r.e.集合）**:
- **定義**: 再帰的可算集合は、その要素が集合に属するならば、あるアルゴリズムが有限時間内に「はい」と答える集合です。ただし、要素が集合に属さない場合には、そのアルゴリズムが「いいえ」を返すとは限らず、無限ループに入る可能性があります。
- **特徴**: 再帰的可算集合は列挙可能集合とも呼ばれ、その要素をすべて列挙するアルゴリズムが存在します。このアルゴリズムは集合のすべての要素を順に出力し続けますが、要素が属さない場合に終了しないことがあります。
### 具体的な違い
- **決定可能性**:
- 再帰的集合は決定可能であり、任意の要素について属するかどうかを有限時間で判定できます。
- 再帰的可算集合は必ずしも決定可能ではなく、要素が集合に属さない場合に無限ループに陥る可能性があります。
- **アルゴリズムの性質**:
- 再帰的集合に対するアルゴリズムは「属するか否か」を常に判定可能です。
- 再帰的可算集合に対するアルゴリズムは「属する場合に属することを示す」だけで、「属さない場合には何も示さない」ことがあります。
シェファードソンの表現定理に関連する論文においても、再帰的可算集合が理論的にどのように扱われるかが議論されています [oai_citation:1,シェファードソンの表現定理.pdf](file-service://file-oFDn3Fzb9nP0s6Ybw9BIRxGJ)。
197: 2024/05/23(木) 09:05:54.72 ID:57Sqch+C(134/218)調 AAS
>>195
はい、その通りです。再帰的集合（recursive set）は再帰的可算集合（recursively enumerable set, r.e.集合）の部分集合です。すべての再帰的集合は再帰的可算集合ですが、すべての再帰的可算集合が再帰的集合であるわけではありません。
具体的には：
- 再帰的集合は、その要素が与えられたときに、集合に属するかどうかを決定するアルゴリズムが存在します。
- 再帰的可算集合は、その要素が集合に属するならば、それを示すアルゴリズムが存在しますが、属さない場合には無限ループに陥る可能性があります。
したがって、すべての再帰的集合はその要素を決定可能であるため、再帰的可算集合の一部です。逆に、再帰的可算集合の中には、決定可能でないものも含まれます。
この関係は以下のように表せます：
再帰的集合 ⊆ 再帰的可算集合
198: 2024/05/23(木) 09:11:14.13 ID:57Sqch+C(135/218)調 AAS
>>195
Σ₁集合について説明します。
Σ₁集合は、算術階層における最も基本的なレベルの集合です。算術階層は、数論的な定義可能性を階層化したものであり、Σ₁集合はこの階層の最下層に位置します。
### 定義
Σ₁集合（Σ₁ set）は、次の形式の論理式で定義される集合です：
- 存在量化子のみを先頭に持つ形式の論理式（∃n₁ ∃n₂ ... ∃nk ϕ(n₁, n₂, ..., nk, x)）で定義できる集合
ここで、ϕは量化子のない（すなわち、開）論理式です。
199: 2024/05/23(木) 09:11:21.88 ID:57Sqch+C(136/218)調 AAS
>>195
### 特徴
- **表現形式**: Σ₁集合は存在量化子のみを先頭に持つ形式の論理式で表現されます。この形式は、「あるn₁, n₂, ..., nkが存在して、ϕが成り立つ」という条件を意味します。
- **再帰的可算集合**: Σ₁集合は再帰的可算集合（recursively enumerable set, r.e.集合）と一致します。すなわち、Σ₁集合は再帰的可算集合であり、すべての再帰的可算集合はΣ₁集合として表現できます。
### 例
例えば、以下のような集合がΣ₁集合です：
- {x | ∃n (n > 0 ∧ x = 2^n)}
- この集合は「ある自然数nが存在して、nが0より大きく、xが2のn乗に等しい」という条件を満たすxの集合です。
シェファードソンの表現定理に関連する論文においても、再帰的可算集合が理論的にどのように扱われるかが議論されています [oai_citation:1,シェファードソンの表現定理.pdf](file-service://file-oFDn3Fzb9nP0s6Ybw9BIRxGJ)。これらの議論はΣ₁集合の特性とも関連しています。
200: 2024/05/23(木) 09:15:04.23 ID:57Sqch+C(137/218)調 AAS
>>195
再帰的可算集合（recursively enumerable set, r.e.集合）がΣ₁集合（Σ₁ set）と一致することの証明をテキスト形式で表現します。
### 定義
- **Σ₁集合**: 存在量化子のみを先頭に持つ形式の論理式で定義される集合。形式的には、∃n₁ ∃n₂ ... ∃nk ϕ(n₁, n₂, ..., nk, x) という形を持ち、ここで ϕ は量化子を含まない（開）論理式です。
- **再帰的可算集合**: その要素が集合に属する場合にそれを有限時間で示すアルゴリズムが存在する集合。ただし、要素が属さない場合にはアルゴリズムが停止しないことがあります。
201: 2024/05/23(木) 09:15:23.85 ID:57Sqch+C(138/218)調 AAS
>>195
### 証明の概要
Σ₁集合と再帰的可算集合の一致は以下のステップで証明されます：
1. **Σ₁集合は再帰的可算集合**:
存在量化子のみを先頭に持つ形式の論理式で定義された集合は、その要素を列挙するアルゴリズムを構築できます。これは、その論理式が「ある自然数 n₁, n₂, ..., nk が存在して、条件 ϕ が成り立つ」という形を持つためです。このようなアルゴリズムは、全ての可能な n₁, n₂, ..., nk を試行し、条件 ϕ を満たすかをチェックします。したがって、Σ₁集合は再帰的可算集合です。
2. **再帰的可算集合はΣ₁集合**:
再帰的可算集合は、その要素が属する場合にそれを示すアルゴリズムが存在します。これは、アルゴリズムが入力を受け取って、それが属する場合に停止して「はい」と答えることを意味します。このアルゴリズムの動作は、存在量化子の連鎖で表現できます。つまり、「ある計算ステップ t が存在して、計算が停止し、入力が集合に属することを示す」という形式になります。これにより、再帰的可算集合もΣ₁集合として表現できます。
202: 2024/05/23(木) 09:15:33.05 ID:57Sqch+C(139/218)調 AAS
>>195
### Unicodeでの表現
以下に、Σ₁集合と再帰的可算集合の一致をUnicodeを使って表現します：
1. **Σ₁集合の定義**:
S_{Σ1} = { x | ∃ n₁ ∃ n₂ ... ∃ nk ϕ(n₁, n₂, ..., nk, x) }
2. **再帰的可算集合の定義**:
S_{r.e.} = { x | 存在するアルゴリズムが x を列挙する }
### 証明
1. **Σ₁集合は再帰的可算集合**:
x ∈ S_{Σ1} → ∃ n₁, n₂, ..., nk ϕ(n₁, n₂, ..., nk, x) → アルゴリズムが n₁, n₂, ..., nk を試行し、条件 ϕ を満たすかチェックする → x ∈ S_{r.e.}
2. **再帰的可算集合はΣ₁集合**:
x ∈ S_{r.e.} → アルゴリズムが x を列挙する → ∃ t (計算ステップ t が存在し、計算が停止して x が属することを示す) → x ∈ S_{Σ1}
このように、Σ₁集合と再帰的可算集合が一致することが証明されました。
上下前次1-新書関写板覧索設栞歴
ｽﾚ情報 赤ﾚｽ抽出 画像ﾚｽ抽出 歴の未読ｽﾚ
ぬこの手 ぬこTOP 0.270s*