| Ambos lados da revisão anterior Revisão anterior Próxima revisão | Revisão anterior |
| grafos:provaprop3rayless [2024/04/25 17:18] – maugsia | grafos:provaprop3rayless [2024/04/29 16:50] (atual) – maugsia |
|---|
| *Assim nosso novo redutor \(F`\) "reduz mais ainda as componentes de \(G\)", assim pelo item anterior como \(C_i \in A(\alpha)\) para todo \(i\) e \(\alpha < \lambda\), então \(\circ(G) < \lambda\), um absurdo, portanto devem existir infinitos conjuntos de tal ordem, para assim não podermos tomar um redutor que "quebra todas as componentes de tal ordem" | *Assim nosso novo redutor \(F`\) "reduz mais ainda as componentes de \(G\)", assim pelo item anterior como \(C_i \in A(\alpha)\) para todo \(i\) e \(\alpha < \lambda\), então \(\circ(G) < \lambda\), um absurdo, portanto devem existir infinitos conjuntos de tal ordem, para assim não podermos tomar um redutor que "quebra todas as componentes de tal ordem" |
| |
| b) \(\implies\) c) | a) + b) \(\implies\) c) |
| |
| Vamos realizar indução em \(\circ(G)\), se \(\lambda = 0 \) | Vamos realizar indução em \(\circ(G)\), se \(\lambda = 0 \) |
| *Caso \(\circ(G)>0\) é trivial, pois todos os grafos finitos tem ordem 0 | *Caso \(\circ(G)>0\) é trivial, pois todos os grafos finitos tem ordem 0 |
| *HI existem infinitos grafos conexos disjuntos de ordem \(\lambda\) | *HI existem infinitos grafos conexos disjuntos de ordem \(\lambda\) |
| *Se \(\circ(G)> \lambda^+\), então por b) temos duas opções, ou existem infinitas componente \(C\) de tamanho exatamente \(\lambda\), neste caso terminamos, ou existem infinitas componentes de tamanho \(> \lambda\), ou seja, \(\lambda < \circ(C) < \circ(G)\), assim com cada \(C \in A\) construímos subconjuntos de de \(G\) através dos subconjuntos dos \(C\), dessa forma pela hipótese de indução + b) temos o que queríamos | *Se \(\circ(G)> \lambda^+\), então por b) temos duas opções, ou existem infinitas componente \(C\) de tamanho exatamente \(\lambda\), neste caso terminamos, ou existem infinitas componentes de tamanho \(> \lambda\), neste caso tomemos uma destas componentes \(C\) e vamos realizar um redução nela gerando novas componentes \(C_i^*\) de ordem menor valendo b), dessa forma pela hipótese de indução temos que infinitas \(C_i^*\) tem ordem \(\lambda\), como queríamos |
| |
| c) \(\implies\) a) | c) \(\implies\) a) |
| |
| Se \(H_1, H_2, \dots\) são infinitos grafos conexos e disjuntos de \(G\) com \(\circ(H_i) = \lambda\), temos que \(\circ(\bigcup H_i)>\lambda\), pela definição da classe, como sabemos que se \(H \subset G\) então \(\circ(H) \leq \circ(G)\) implica que \(\circ(\bigcup H_i) < \circ(G)\) e portanto \(\circ(G) > \lambda\), mesmo que neste processo de união sem querer tenhamos omitido alguns vértices do conjunto redutor de \(G\), ainda existirão infinitas componentes de tal forma | Se \(H_1, H_2, \dots\) são infinitos grafos conexos e disjuntos de \(G\) com \(\circ(H_i) = \lambda\), temos que \(\circ(\bigcup H_i)>\lambda\), pela definição da classe, como sabemos que se \(H \subset G\) então \(\circ(H) \leq \circ(G)\) implica que \(\circ(\bigcup H_i) < \circ(G)\) e portanto \(\circ(G) > \lambda\) |
| |