無限の木に生き物のような性質を証明する

(文脈:これは私の論文の途中から問題があり、より一般的な問題に抽象化されています。それはいくつかの活性プロパティが保持されていることを示すことに関連しています。

ルートノード$ n_0 $でおそらく無限深さのツリーがあるとします。
(EDIT:ノードあたりの子供の数は有益な場合には有界です。)$ N_0 $からのすべてのパスに対してツリーに
“良い”ノードの特別なセット$ G $が存在しますそのパスには$ G
$のノードが含まれています(ただし、そのノードは任意の深さにあります)。

今、ツリーのノード上にいくつかのプロパティ$ P $が存在し、$ P(n)$が以下の場合にのみ保持されるとします。

  • G $の$ n 、または
  • すべての子ノード$ n ‘$ of $ n $、$ P(n’)$が保持されます。

To prove: $P(n_0)$ holds

$ P $は “すべての経路に$ G
$のノードがある”という事実上別の言い方なので、これはほんの些細なことです。しかし、私は正式にそれを証明することはできません。帰納的証明は、私が$
G $にいなければ私の子供たちがPにいると期待しているので、$ P $は私のために保持するはずです。
「最も遠い」良い「ノード」までの距離のようなものは自然のようですが、そのような境界が存在するかどうかはわかりません。

私は合理的にこの声明が証明できると確信しているので、それを証明する方法は?最も遠い「良いノード」には本当に束縛がありますか?そうであれば、そのような境界が存在するという議論は何ですか?

ベストアンサー

上記の質問に対するコメントを参照してください。矛盾による証明とKönigの補題の使用の両方で十分です。

返信を残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です