ordine

ordine

Dato un insieme qualsiasi è possibile organizzare i suoi elementi secondo una certa regola (o relazione) che definisce un ordine degli elementi nell’insieme. Si chiamano relazioni d’o. (o semplicemente o.) quelle relazioni che determinano l’ordinamento di un insieme. Dato un insieme A e una relazione binaria R in A, R è una relazione di o. parziale, se è antisimmetrica (per ogni coppia di elementi a, b di A, se aRb e bRa, allora a=b) e tran­sitiva (se aRb e bRc, allora aRc). Se R è inoltre riflessiva (per ogni elemento a di A, aRa) l’o. parziale si dice largo, se invece R è antiriflessiva (per ogni elemento a di A, non aRa), l’o. parziale si dice stretto. Infine, se R è antisimmetrica, transitiva e vale la tricotomia (per ogni coppia di elementi a, b di A, a=b o aRb o bRa), diciamo che R è una relazione di o. totale, il quale può essere largo o stretto a seconda che valga la riflessività o antiriflessività. Intuitivamente la tricotomia asserisce che dati due elementi qualsiasi di A si conosce, se sono diversi, in quale o. sono l’uno rispetto all’altro. Per es., l’inclusione tra sottoinsiemi di un insieme è un ordinamento parziale; la relazione di ‘minore o uguale’ è un o. totale largo nell’insieme dei numeri naturali. Il termine o. compare anche nella definizione dei vari livelli di logica. La logica dei predicati del primo o., per es., è la logica dei linguaggi nei quali i predicati prendono come argomenti solo individui e i quantificatori quantificano su variabili individuali; la logica dei predicati del secondo o. è quella che contiene anche variabili per proprietà, relazioni, funzioni e ammette la quantificazione su di loro. La costruzione dei livelli può essere continuata producendo la logica dei predicati del terzo o. (con variabili quantificabili per proprietà di proprietà e relazioni tra proprietà), ecc. Una logica è detta di o. superiore se essa è almeno del secondo ordine.