Principio di casellario e grafo casuale

Question

Ho questo esercizio

(Peter J. Cameron) Dimostralo per ogni grafo numerabile infinito $M$ i seguenti sono equivalenti

• $M$ è casuale, completo o vuoto (es $r^M = \emptyset$, in altre parole ogni punto è isolato)
• Se $M_1, M_2 \subseteq M$ sono tali $M_1 \sqcup M_2 = M$ (cioè formano una partizione) quindi $M_1 \simeq M$ o $M_2 \simeq M$ (Cameron chiama questa proprietà principio della casella di posta)

Ora ho alcuni problemi nel dimostrare questa affermazione. Ho rintracciato l'articolo ( link ) di Cameron in cui compare questa proposizione (Prop. 4 pagina 5) ma faccio fatica a dare un senso alla dimostrazione presentata. In particolare non capisco come possiamo dirlo$X$ e $Y$(definito nella prova dell'articolo) formano una partizione. Qualche suggerimento?

Grazie

Answer 1

Iniziamo con due sottoinsiemi non vuoti disgiunti $A$ e $B$ tale che $A\cup B$ non ha un vertice "unito correttamente" corrispondente $\Gamma$. Quindi miglioriamo$A$ in $X$: un sottoinsieme di quei vertici non in $B$ che non sono collegati correttamente con $A$. Poiché abbiamo esplicitamente evitato di includere$B$ vertici in questa definizione, $X$ e $B$sono anche disgiunti. Ora miglioriamo$B$ con vertici non in $X$ che non sono collegati correttamente con $B$e ottieni un sottoinsieme $Y$. Ancora una volta, con questa definizione,$X$ e $Y$sono disgiunti. Inoltre, se supponiamo che esista un file$z\in\Gamma$ che ha evitato di essere raccolto in nessuno di $X$ e $Y$, quindi viene unito correttamente con entrambi $A$ e $B$, che contraddice la scelta iniziale di $A\cup B$. Così$X\cup Y=\Gamma$, come richiesto.

Ora, in base al principio della casella, $X$ o $Y$ è isomorfo a $\Gamma$. Prendendo l'isomorismo, diciamo,$f\colon X\to \Gamma$, lo otteniamo $f(A)$ è un minore (di $A\cup B$) sottoinsieme in $\Gamma$che non ha un vertice "unito correttamente" corrispondente. Se abbiamo preso$A\cup B$ per essere il minimo di tali sottoinsiemi, otteniamo una contraddizione: l'unico modo per evitarlo è assumere che il minimo di tali sottoinsiemi sia di dimensione 1 e non possa $A$ e $B$, che è trattato sopra nella prova dell'articolo.