論理式のセットの可算性について
Sep 26 2020
私はここMathSEでこれに対する答えを読みましたが、議論の詳細はまだ私にはぼんやりしています。
ユーザーの1人は、次の理由でWFFのセットが可算であると提案しました。
S = $A \cup \{\neg,\lor,\land, (, )\}$ある可算集合のシンボルは、（$A$ 命題変数の可算無限集合です）。
$S_f$、からの記号の有限文字列のセット $S$、可算です。
すべての整形式のセットはのサブセットであるため$S_f$、可算です。
私の質問：なぜですか$S_f$可算？間の全単射を提案できますか$S_f$ そして $\mathbb{N}$？（もし$S_f$ 可算です、それは可算無限でなければなりません）
回答
1 Gödel Sep 27 2020 at 05:03
ヒント：として$S$ 可算です、あなたは全単射を得ることができます $f:S\rightarrow P$ どこ $P$すべての素数のセットです。さて、$a_1\dots a_n$ の記号の文字列です $S$、あなたはそれを番号で成文化することができます $f(a_1)\times...\times f(a_n)$。
1 J.-E.Pin Sep 27 2020 at 05:25
しましょう $S = \{a_n \mid n \in {\Bbb N}\}$可算アルファベットになります。からの記号の有限文字列のセット$S$上の自由モノイドです$S$、通常は $S^*$。今地図$f:S^* \to {\Bbb N}$ どこ $f(a_{i_1}a_{i_2} \dotsm a_{i_n})$ 2進整数です $10^{i_1}10^{i_2} \dotsm 10^{i_n}$明らかに単射です。したがって、$S^*$ 可算です。