Catene e anticatene di divisibilità

[piever]

Sia $ \mathbb{A}\subset \mathbb{N}_+ $ un insieme di cardinalità $ mn+1 $

Se $ \mathbb{S}\subset\mathbb{A} $ e' un sottoinsieme di cardinalità $ m+1 $, allora esistono due elementi distinti $ a,b\in\mathbb{S} $ tali che $ a|b $

Si dimostri che esistono $ n+1 $ elementi distinti $ a_1,\dots ,a_{n+1}\in\mathbb{A} $ tali che $ a_1|a_2|\dots |a_{n+1} $


Buon lavoro!

[SkZ]

mi sa che mancano delle condizioni per $ ~\mathbb{A} $ perche' se lo prendiamo come sottoinsieme dei numeri primi, il tutto non funziona piu'

[EvaristeG]

(credo che le prime due righe siano le ipotesi, la terza la tesi)

[mattilgale]

dimostriamo la tesi per induzione su n

per n=1 la tesi segue direttamente dall'ipotesi

supponiamo che la tesi sia valida per un generico n e consideriamo e consideriamo

$ \mathbb{A}\subset \mathbb{N}_+:\ |\mathbb{A}|=m(n+1)+1=mn+1+m $

consideriamo adesso un insieme S inizialmente vuoto
adesso consideriamo un catena di divisibilità lunga n che si trova certamente in A poiché |A|>=mn+1 e poniamo il primo elemento della catena in S

adesso |S|=1 e |A-S|>=mn+1 quindi in A-S esiste ancora una catena di lunghezza n, prendiamo il suo primo elemento e mettiamolo in S, ripetiamo l'operazione fino a che |S|=m+1
per ipotesi esistono due elementi a e b di S tali che
a|b

ora, poiché b è il primo elemento di una catena di divisibilità lunga n in A, abbiamo che in A esiste almeno una catena lunga n+1

[piever]

Pero', carina questa soluzione...

(Non tutti ci prendono gusto a complicarsi la vita...)

Volendo si possono anche dimostrare 2 tesi un po' piu' forti per un qualunque insieme parziamente ordinato:

A) la massima catena e' uguale al numero minimo di anticatene in cui puo' essere partizionato l'insieme.

B) la massima anticatena e' uguale al numero minimo di catene in cui puo' essere partizionato l'insieme.

Ovviamente sia A) che B) implicano la tesi.

Chi vuole puo' provare a dimostrarle...