Σύνολα, σχέσεις και συναρτήσεις

Η γλώσσα του κύκλου μαθημάτων

Το μάθημα που ακολουθεί ορίζει τους φυσικούς αριθμούς μέσω μιας συνάρτησης, του επόμενου, η οποία είναι ένα προς ένα και δεν φτάνει στο $1$. Η ενότητα που ακολουθεί κατασκευάζει τους ακεραίους και τους ρητούς ως κλάσεις μιας σχέσης ισοδυναμίας· το μάθημα της συνδυαστικής ορίζει το πλήθος των στοιχείων μέσω αμφιμονοσήμαντων αντιστοιχιών· η διάταξη των φυσικών είναι σχέση διάταξης· και η τρίτη ενότητα συνθέτει και αντιστρέφει πραγματικές συναρτήσεις. Όλες αυτές οι λέξεις ανήκουν σε μία και την ίδια γλώσσα, την οποία συμφέρει να καθορίσουμε πριν τη χρησιμοποιήσουμε, μαζί με τα πρώτα θεωρήματα που ο κύκλος μαθημάτων θα επικαλεστεί αργότερα.

Αξίζει να επισημάνουμε τι χρησιμοποιείται εκ των προτέρων. Τα παραδείγματα χρησιμοποιούν μικρούς φυσικούς αριθμούς με τη διάταξή τους, την πρόσθεση, τον πολλαπλασιασμό, τη διαιρετότητα και το υπόλοιπο μιας διαίρεσης, όπως τα μαθαίνουμε στο σχολείο. Το μάθημα που ακολουθεί ορίζει τους φυσικούς μέσω των αξιωμάτων του Πεάνο, και τα μαθήματα της ενότητας ορίζουν αυτές τις πράξεις και αποδεικνύουν τις ιδιότητές τους χωρίς να χρησιμοποιούν κανένα παράδειγμα του παρόντος, ώστε δεν υπάρχει φαύλος κύκλος. Κανένα θεώρημα αυτού του μαθήματος δεν εξαρτάται από τα παραδείγματα: οι αριθμοί χρησιμεύουν μόνο για να δούμε τα θεωρήματα σε δράση.

Τι δεχόμαστε

Ένα σύνολο είναι μια συλλογή αντικειμένων, των στοιχείων του· γράφουμε $a \in A$ για να πούμε ότι το $a$ ανήκει στο $A$, και $a \notin A$ για να το αρνηθούμε. Το σύνολο και το ανήκειν δεν ορίζονται: είναι πρωταρχικές έννοιες, όπως το $1$ και ο επόμενος στην αριθμητική. Ωστόσο, δεν ορίζει κάθε ιδιότητα ένα σύνολο. Αν υπήρχε το σύνολο $R$ όλων των συνόλων που δεν ανήκουν στον εαυτό τους, το ερώτημα αν το $R$ ανήκει στο $R$ δεν θα είχε απάντηση, γιατί από τον ορισμό του $R$ θα είχαμε $R \in R \leftrightarrow R \notin R$. Αυτή η αντίφαση, που ανακάλυψε ο Ράσελ το 1901, υποχρεώνει να περιοριστεί ο σχηματισμός συνόλων: μια ιδιότητα μόνο επιλέγει στοιχεία ενός ήδη δοσμένου συνόλου.

Γεγονός που δεχόμαστε χωρίς απόδειξη (κανόνες της αφελούς θεωρίας συνόλων). Δεχόμαστε χωρίς απόδειξη τους κανόνες της αφελούς θεωρίας συνόλων που χρησιμοποιεί αυτό το μάθημα: δύο σύνολα με τα ίδια στοιχεία είναι ίσα· από ένα δοσμένο σύνολο $A$ και μια ιδιότητα $P$ σχηματίζεται το σύνολο $\{ x \in A : P(x) \}$ των στοιχείων του $A$ που την ικανοποιούν· και υπάρχουν το κενό σύνολο, το σύνολο $\{a, b\}$ του οποίου τα μόνα στοιχεία είναι τα $a$ και $b$, η ένωση των στοιχείων ενός συνόλου συνόλων και το σύνολο των υποσυνόλων ενός συνόλου. Η ύπαρξη ενός συνόλου με τις ιδιότητες του συνόλου των φυσικών γίνεται δεκτή στο μάθημα που ακολουθεί.

Οι κανόνες αυτοί αποτελούν μέρος των αξιωμάτων των Τσερμέλο και Φρένκελ, η μελέτη των οποίων ανήκει στη θεωρία συνόλων και ξεπερνά αυτόν τον κύκλο μαθημάτων· γι’ αυτό γίνονται δεκτοί, και δηλώνονται ώστε να είναι γνωστό ακριβώς τι χρησιμοποιείται.

Λογική των ποσοδεικτών

Οι αποδείξεις συνδυάζουν αποφάνσεις με τους συνδέσμους $\neg$, $\wedge$, $\vee$, $\rightarrow$ και $\leftrightarrow$, οι νόμοι των οποίων μελετώνται στον συμπληρωματικό κύκλο μαθημάτων Μαθηματική λογική I: προτασιακή λογική, ξεκινώντας από τη γλώσσα της· εδώ αρκεί να θυμηθούμε ότι η συνεπαγωγή $p \rightarrow q$ είναι ψευδής μόνο όταν η $p$ είναι αληθής και η $q$ ψευδής, ότι είναι ισοδύναμη με την αντιθετοαντίστροφή της $\neg q \rightarrow \neg p$, και ότι οι νόμοι του Ντε Μόργκαν αρνούνται μια σύζευξη ή μια διάζευξη:

Για να μιλήσουμε για σύνολα χρειάζονται, επιπλέον, αποφάνσεις για όλα τα στοιχεία ή για κάποιο από αυτά. Αν $P(x)$ είναι μια ιδιότητα των στοιχείων του $A$, η απόφανση $(\forall x \in A)\,P(x)$, που διαβάζεται «για κάθε $x$ του $A$, $P(x)$», βεβαιώνει ότι όλα τα στοιχεία του $A$ την ικανοποιούν· η απόφανση $(\exists x \in A)\,P(x)$, «υπάρχει $x$ του $A$ τέτοιο ώστε $P(x)$», βεβαιώνει ότι τουλάχιστον ένα την ικανοποιεί· και η $(\exists! x \in A)\,P(x)$ βεβαιώνει ότι ακριβώς ένα την ικανοποιεί. Τα σύμβολα $\forall$ και $\exists$ λέγονται ποσοδείκτες, καθολικός και υπαρξιακός.

Γεγονός που δεχόμαστε χωρίς απόδειξη (άρνηση των ποσοδεικτών). Το να αρνηθούμε ότι όλα τα στοιχεία ικανοποιούν μια ιδιότητα σημαίνει να βεβαιώσουμε ότι κάποιο δεν την ικανοποιεί, και το να αρνηθούμε ότι κάποιο την ικανοποιεί σημαίνει να βεβαιώσουμε ότι κανένα δεν την ικανοποιεί:

Οι κανόνες αυτοί, που ανήκουν στη λογική πρώτης τάξης, γίνονται δεκτοί· επεκτείνουν τους νόμους του Ντε Μόργκαν, γιατί αν $A = \{a, b\}$, η καθολική απόφανση είναι η $P(a) \wedge P(b)$ και η υπαρξιακή είναι η $P(a) \vee P(b)$. Η σειρά των ποσοδεικτών έχει σημασία: η απόφανση $(\forall n \in \mathbb{N})(\exists m \in \mathbb{N})(n < m)$ λέει ότι κάθε φυσικός έχει έναν άλλο μεγαλύτερο, και είναι αληθής· η απόφανση $(\exists m \in \mathbb{N})(\forall n \in \mathbb{N})(n < m)$ λέει ότι υπάρχει ένας φυσικός μεγαλύτερος από όλους, άρα και από τον εαυτό του, και είναι ψευδής.

Η λογική μορφή μιας απόφανσης υπαγορεύει τον τρόπο με τον οποίο αποδεικνύεται. Οι στρατηγικές που χρησιμοποιεί αυτό το μάθημα είναι οι εξής· η λογική τους αιτιολόγηση μελετάται στο μάθημα για τις τεχνικές παραγωγής.

• Για να αποδείξουμε την $(\forall x \in A)\,P(x)$, παίρνουμε ένα οποιοδήποτε στοιχείο $x$ του $A$, χωρίς να υποθέσουμε γι’ αυτό τίποτε άλλο εκτός από το ότι ανήκει στο $A$, και αποδεικνύουμε την $P(x)$.
• Για να αποδείξουμε την $(\exists x \in A)\,P(x)$, παρουσιάζουμε ένα συγκεκριμένο στοιχείο του $A$ που ικανοποιεί την $P$· για να ανασκευάσουμε την $(\forall x \in A)\,P(x)$, αρκεί ένα αντιπαράδειγμα, ένα στοιχείο που δεν την ικανοποιεί.
• Για να αποδείξουμε την $p \rightarrow q$, υποθέτουμε την $p$ και συνάγουμε την $q$· ή αποδεικνύουμε την αντιθετοαντίστροφη $\neg q \rightarrow \neg p$· ή υποθέτουμε την $p \wedge \neg q$ και καταλήγουμε σε αντίφαση.
• Για να αποδείξουμε την $p \leftrightarrow q$, αποδεικνύουμε τις δύο συνεπαγωγές $p \rightarrow q$ και $q \rightarrow p$.

Σύνολα

Ανήκειν, ισότητα και εγκλεισμός

Ένα σύνολο περιγράφεται με αναγραφή, απαριθμώντας τα στοιχεία του μέσα σε άγκιστρα, όπως $\{1, 2, 3\}$, ή με περιγραφή, μέσω μιας ιδιότητας, όπως $\{ n \in \mathbb{N} : n \leq 3 \}$, που είναι το ίδιο σύνολο. Ο κανόνας της εκτατικότητας λέει ότι ένα σύνολο καθορίζεται από τα στοιχεία του:

Από αυτό έπεται ότι σε μια περιγραφή με αναγραφή δεν έχουν σημασία ούτε η σειρά ούτε οι επαναλήψεις: τα $\{1, 2, 2\}$ και $\{2, 1\}$ είναι το ίδιο σύνολο, γιατί έχουν τα ίδια στοιχεία. Έπεται επίσης ότι υπάρχει ένα μόνο σύνολο χωρίς στοιχεία, το κενό σύνολο $\emptyset$: δύο σύνολα χωρίς στοιχεία έχουν τα ίδια στοιχεία, δηλαδή κανένα.

Ορισμός (εγκλεισμός). Ένα σύνολο $A$ περιέχεται σε ένα σύνολο $B$, ή είναι υποσύνολο του $B$, όταν κάθε στοιχείο του $A$ είναι στοιχείο του $B$:

Αν επιπλέον $A \neq B$, λέμε ότι το $A$ είναι γνήσιο υποσύνολο του $B$.

Το κενό σύνολο περιέχεται σε κάθε σύνολο $A$, γιατί η συνεπαγωγή $x \in \emptyset \rightarrow x \in A$ έχει πάντα ψευδές ηγούμενο και είναι, επομένως, αληθής. Πρέπει να διακρίνουμε το ανήκειν από τον εγκλεισμό: οι $1 \in \{1, 2\}$ και $\{1\} \subseteq \{1, 2\}$ είναι αληθείς, ενώ η $\{1\} \in \{1, 2\}$ είναι ψευδής, γιατί τα μόνα στοιχεία του $\{1, 2\}$ είναι το $1$ και το $2$, και το σύνολο $\{1\}$ δεν είναι ίσο με κανένα από αυτά: $\{1\} \neq 1$, γιατί το σύνολο που έχει ως μόνο στοιχείο το $1$ δεν συγχέεται με το $1$, και $\{1\} \neq 2$.

Ένωση, τομή και διαφορά

Ορισμός (πράξεις με σύνολα). Η ένωση των $A$ και $B$ είναι το σύνολο των στοιχείων που ανήκουν σε κάποιο από αυτά· η τομή, το σύνολο εκείνων που ανήκουν και στα δύο· και η διαφορά $A \setminus B$, το σύνολο εκείνων που ανήκουν στο $A$ και όχι στο $B$:

Αν $B \subseteq A$, η διαφορά $A \setminus B$ λέγεται συμπλήρωμα του $B$ ως προς το $A$. Δύο σύνολα είναι ξένα όταν η τομή τους είναι κενή.

Κάθε πράξη μεταφράζει έναν σύνδεσμο: η ένωση τη διάζευξη· η τομή τη σύζευξη· η διαφορά τη σύζευξη με μια άρνηση. Αν αυτό ισχύει, κάθε λογικός νόμος παράγει έναν νόμο των συνόλων: η ένωση και η τομή είναι αντιμεταθετικές, προσεταιριστικές και επιμεριστικές η μία ως προς την άλλη επειδή είναι τέτοιοι οι σύνδεσμοι, και όλοι αυτοί οι νόμοι αποδεικνύονται όπως το θεώρημα που ακολουθεί. Το συμπλήρωμα λαμβάνεται πάντα ως προς ένα σύνολο αναφοράς, γιατί ένα σύνολο όλων όσων δεν βρίσκονται στο $B$ θα αναπαρήγαγε το παράδοξο του Ράσελ.

Το δυναμοσύνολο

Τα υποσύνολα ενός συνόλου σχηματίζουν με τη σειρά τους ένα σύνολο, η ύπαρξη του οποίου έγινε δεκτή στην αρχή. Το δυναμοσύνολο του $A$, που συμβολίζεται $\mathcal{P}(A)$, είναι το σύνολο του οποίου τα στοιχεία είναι τα υποσύνολα του $A$:

Για παράδειγμα, το δυναμοσύνολο του $\{1, 2, 3\}$ έχει οκτώ στοιχεία: το κενό, τρία σύνολα ενός στοιχείου, τρία σύνολα δύο στοιχείων και το ίδιο το $\{1, 2, 3\}$.

Για κάθε σύνολο $A$, το κενό και το ίδιο το $A$ είναι στοιχεία του $\mathcal{P}(A)$, και για κάθε $a$ του $A$ ισχύει $\{a\} \in \mathcal{P}(A)$, ενώ το $a$ δεν είναι, εν γένει, στοιχείο του $\mathcal{P}(A)$. Στο μάθημα για τη συνδυαστική θα αποδειχθεί ότι ένα σύνολο $n$ στοιχείων έχει $2^n$ υποσύνολα.

Διατεταγμένα ζεύγη και καρτεσιανό γινόμενο

Ένα σημείο του επιπέδου, ένα κλάσμα ή μια αφαίρεση που μένει να γίνει περιγράφονται με δύο αντικείμενα σε ορισμένη σειρά: το ζεύγος $(3, 5)$ δεν είναι το ζεύγος $(5, 3)$. Το σύνολο $\{3, 5\}$ δεν χρησιμεύει για να το αναπαραστήσει, γιατί είναι ίσο με το $\{5, 3\}$. Το μόνο που απαιτείται από ένα διατεταγμένο ζεύγος είναι η χαρακτηριστική ιδιότητα του: δύο ζεύγη είναι ίσα αν και μόνο αν έχουν την ίδια πρώτη συνιστώσα και την ίδια δεύτερη συνιστώσα. Ο Κουρατόφσκι παρατήρησε το 1921 ότι αρκεί η έννοια του συνόλου για να κατασκευαστεί ένα αντικείμενο με αυτή την ιδιότητα.

Ορισμός (διατεταγμένο ζεύγος). Το διατεταγμένο ζεύγος με πρώτη συνιστώσα $a$ και δεύτερη συνιστώσα $b$ είναι το σύνολο

Αφού αποδείχθηκε η χαρακτηριστική ιδιότητα, η κατασκευή του Κουρατόφσκι μπορεί να ξεχαστεί: ό,τι λέει ο κύκλος μαθημάτων για τα ζεύγη συνάγεται από αυτήν.

Ορισμός (καρτεσιανό γινόμενο). Το καρτεσιανό γινόμενο των $A$ και $B$ είναι το σύνολο των ζευγών των οποίων η πρώτη συνιστώσα ανήκει στο $A$ και η δεύτερη συνιστώσα ανήκει στο $B$:

Η γραφή $\{ (a, b) : a \in A \wedge b \in B \}$ δεν είναι από μόνη της ένας από τους κανόνες που έγιναν δεκτοί, οι οποίοι επιτρέπουν μόνο να διαχωρίζουμε στοιχεία ενός ήδη σχηματισμένου συνόλου. Ωστόσο, το σύνολο αυτό υπάρχει: αν $a \in A$ και $b \in B$, τα σύνολα $\{a\}$ και $\{a, b\}$ περιέχονται στο $A \cup B$, και επομένως είναι στοιχεία του $\mathcal{P}(A \cup B)$· από αυτό έπεται ότι το ζεύγος $(a, b) = \{ \{a\}, \{a, b\} \}$ περιέχεται στο $\mathcal{P}(A \cup B)$, δηλαδή είναι στοιχείο του $\mathcal{P}(\mathcal{P}(A \cup B))$. Επομένως, το καρτεσιανό γινόμενο σχηματίζεται με διαχωρισμό μέσα σε αυτό το σύνολο, που υπάρχει από τους κανόνες που έγιναν δεκτοί: το $A \cup B$ είναι η ένωση των στοιχείων του $\{A, B\}$, και λαμβάνεται δύο φορές το δυναμοσύνολο.

Το όνομα θυμίζει τον Καρτέσιο: το επίπεδο της αναλυτικής γεωμετρίας είναι το $\mathbb{R} \times \mathbb{R}$. Το γινόμενο δεν είναι αντιμεταθετικό: το $\{1\} \times \{2\}$ περιέχει μόνο το $(1, 2)$, και το $\{2\} \times \{1\}$ μόνο το $(2, 1)$, που είναι διαφορετικό λόγω της χαρακτηριστικής ιδιότητας.

Σχέσεις

Το να πούμε ότι ο $2$ διαιρεί τον $6$, ότι ο $3$ είναι μικρότερος από τον $5$ ή ότι δύο ημερομηνίες πέφτουν την ίδια ημέρα της εβδομάδας σημαίνει να βεβαιώσουμε ότι ορισμένα ζεύγη αντικειμένων σχετίζονται. Αν αυτό ισχύει, μια σχέση καθορίζεται από τα ζεύγη που συσχετίζει, και μπορεί να οριστεί ως ένα σύνολο ζευγών.

Ορισμός (σχέση). Μια σχέση από το $A$ στο $B$ είναι ένα υποσύνολο $R$ του γινομένου $A \times B$· μια σχέση στο $A$ είναι μια σχέση από το $A$ στο $A$. Αν $(a, b) \in R$, λέμε ότι το $a$ σχετίζεται με το $b$ μέσω της $R$.

Για παράδειγμα, η σχέση «μικρότερο ή ίσο» στο $\{1, 2, 3\}$ είναι το σύνολο ζευγών $\{(1, 1), (1, 2), (1, 3), (2, 2), (2, 3), (3, 3)\}$. Για τις σχέσεις που χρησιμοποιούνται συχνά γράφουμε ένα σύμβολο ανάμεσα στους όρους, όπως $a \leq b$ ή $a \mid b$, αντί για $(a, b) \in R$. Τέσσερις ιδιότητες μιας σχέσης σε ένα σύνολο επανέρχονται σε όλο τον κύκλο μαθημάτων.

Ορισμός (ιδιότητες των σχέσεων). Μια σχέση $R$ στο $A$ είναι ανακλαστική, συμμετρική, αντισυμμετρική ή μεταβατική όταν ικανοποιεί, αντίστοιχα, τις ακόλουθες συνθήκες.

• Είναι ανακλαστική αν κάθε στοιχείο σχετίζεται με τον εαυτό του: $(\forall a \in A)\,((a, a) \in R)$·
• Είναι συμμετρική αν η σχέση του $a$ με το $b$ συνεπάγεται τη σχέση του $b$ με το $a$: $(\forall a, b \in A)\,((a, b) \in R \rightarrow (b, a) \in R)$·
• Είναι αντισυμμετρική αν δύο στοιχεία που σχετίζονται και προς τις δύο κατευθύνσεις είναι ίσα: $(\forall a, b \in A)\,((a, b) \in R \wedge (b, a) \in R \rightarrow a = b)$·
• Είναι μεταβατική αν η σχέση του $a$ με το $b$ και η σχέση του $b$ με το $c$ συνεπάγονται τη σχέση του $a$ με το $c$: $(\forall a, b, c \in A)\,((a, b) \in R \wedge (b, c) \in R \rightarrow (a, c) \in R)$.

Στο πλέγμα του $A \times A$, μια σχέση είναι ένα σύνολο σημείων. Είναι ανακλαστική όταν περιέχει ολόκληρη τη διαγώνιο, εκείνη των ζευγών $(a, a)$· είναι συμμετρική όταν το σχέδιό της είναι συμμετρικό ως προς τη διαγώνιο· και είναι αντισυμμετρική όταν κανένα σημείο εκτός της διαγωνίου δεν έχει το συμμετρικό του μέσα στη σχέση. Αντισυμμετρική δεν σημαίνει «μη συμμετρική»: η ισότητα είναι και τα δύο, και το προτεινόμενο πρόβλημα 1 ζητά μια σχέση που να μην είναι κανένα από τα δύο.

Σχέσεις ισοδυναμίας

Η σχέση «έχουν την ίδια αρτιότητα» συμπεριφέρεται σαν μια μερική ισότητα: ταυτίζει τους αριθμούς που συμπίπτουν σε μια όψη, την αρτιότητά τους, και αγνοεί τις υπόλοιπες. Οι τρεις ιδιότητες που την κάνουν να συμπεριφέρεται έτσι παίρνουν ένα όνομα.

Ορισμός (σχέση ισοδυναμίας). Μια σχέση στο $A$ είναι σχέση ισοδυναμίας όταν είναι ανακλαστική, συμμετρική και μεταβατική. Γράφουμε τότε $a \sim b$ και λέμε ότι το $a$ είναι ισοδύναμο με το $b$. Η κλάση του $a$ είναι το σύνολο των στοιχείων που είναι ισοδύναμα με το $a$, και καθένα από αυτά είναι ένας αντιπρόσωπος της κλάσης:

Το σύνολο όλων των κλάσεων λέγεται σύνολο πηλίκο και συμβολίζεται $A/{\sim}$.

Σχέσεις ισοδυναμίας είναι η ισότητα, της οποίας οι κλάσεις έχουν ένα μόνο στοιχείο· η ίδια αρτιότητα, με δύο κλάσεις· το να αφήνουν το ίδιο υπόλοιπο στη διαίρεση με το $3$, με τρεις· και το να πέφτουν την ίδια ημέρα της εβδομάδας, με επτά, που είναι το λυμένο πρόβλημα 3. Γενικά, αν $g$ είναι μια συνάρτηση ορισμένη στο $A$, η σχέση $g(x) = g(y)$ κληρονομεί από την ισότητα τις τρεις ιδιότητες, και το λυμένο πρόβλημα 5 δείχνει ότι κάθε ισοδυναμία είναι αυτής της μορφής.

Οι κλάσεις χωρίζουν, επομένως, το σύνολο σε μπλοκ που δεν επικαλύπτονται. Αυτός ο τρόπος να χωρίζεται ένα σύνολο αξίζει δικό του ορισμό.

Ορισμός (διαμέριση). Μια διαμέριση ενός συνόλου $A$ είναι ένα σύνολο υποσυνόλων του $A$, που λέγονται μπλοκ, τα οποία δεν είναι κενά, είναι ανά δύο ξένα και έχουν ένωση το $A$· ισοδύναμα, κάθε στοιχείο του $A$ ανήκει σε ακριβώς ένα μπλοκ.

Το να δώσουμε μια ισοδυναμία στο $A$ και το να δώσουμε μια διαμέριση του $A$ είναι, επομένως, δύο τρόποι να πούμε το ίδιο πράγμα· το λυμένο πρόβλημα 4 το αξιοποιεί για να μετρήσει ισοδυναμίες. Το σύνολο πηλίκο είναι η διαμέριση ιδωμένη ως ένα νέο σύνολο: όταν περνάμε από το $A$ στο $A/{\sim}$, τα ισοδύναμα στοιχεία συγχωνεύονται σε ένα μόνο.

Με τον ίδιο τρόπο, στο μάθημα για τους ρητούς αριθμούς δύο κλάσματα $(p, q)$ και $(r, s)$ είναι ισοδύναμα όταν $ps = qr$, και ένας ρητός είναι μια κλάση· και στο μάθημα για τις ισοτιμίες, τα υπόλοιπα κατά μέτρο $n$ είναι οι κλάσεις μιας ισοδυναμίας μεταξύ ακεραίων.

Σχέσεις διάταξης

Η διαιρετότητα του προηγούμενου παραδείγματος δεν είναι συμμετρική αλλά αντισυμμετρική: αντί να ταυτίζει στοιχεία, τα διατάσσει. Οι σχέσεις αυτού του είδους παίρνουν δικό τους όνομα.

Ορισμός (διάταξη). Μια σχέση στο $A$ είναι σχέση διάταξης, ή μερική διάταξη, όταν είναι ανακλαστική, αντισυμμετρική και μεταβατική· γράφουμε τότε $a \preceq b$ και λέμε ότι το $a$ προηγείται του $b$. Η διάταξη είναι ολική όταν δύο οποιαδήποτε στοιχεία είναι συγκρίσιμα, δηλαδή όταν για όλα τα $a$ και $b$ ισχύει $a \preceq b$ ή $b \preceq a$.

Διατάξεις είναι η σχέση $\leq$ μεταξύ φυσικών, που είναι ολική λόγω της τριχοτομίας που αποδεικνύεται στο μάθημα για τις πράξεις με φυσικούς αριθμούς· ο εγκλεισμός, από το θεώρημα των ιδιοτήτων του, που δεν είναι ολική διάταξη, γιατί τα $\{1\}$ και $\{2\}$ δεν είναι συγκρίσιμα· και η διαιρετότητα μεταξύ φυσικών, της οποίας η αντισυμμετρία αποδεικνύεται στο μάθημα για τη διαιρετότητα, που δεν είναι ολική, γιατί ούτε $2 \mid 3$ ούτε $3 \mid 2$. Μια πεπερασμένη διάταξη σχεδιάζεται με ένα διάγραμμα Χάσε: ένα σημείο για κάθε στοιχείο, με το $b$ ψηλότερα από το $a$ όταν το $a$ προηγείται του $b$, και ένα ευθύγραμμο τμήμα όταν ανάμεσά τους δεν υπάρχει κανένα άλλο στοιχείο· η μεταβατικότητα επιτρέπει να παραλειφθούν τα υπόλοιπα τμήματα.

Ορισμός (φράγματα και ακραία στοιχεία). Έστω $\preceq$ μια διάταξη στο $A$ και $X$ ένα υποσύνολο του $A$. Τα φράγματα και τα ακραία στοιχεία του $X$ ορίζονται ως εξής.

• Ένα στοιχείο $c$ του $A$ είναι κάτω φράγμα του $X$ αν προηγείται όλων των στοιχείων του $X$, και άνω φράγμα αν όλα τα στοιχεία του $X$ προηγούνται αυτού.
• Ελάχιστο του $X$ είναι ένα κάτω φράγμα του $X$ που ανήκει στο $X$, και μέγιστο ένα άνω φράγμα που ανήκει στο $X$.
• Ένα στοιχείο $m$ του $X$ είναι ελαχιστικό αν κανένα στοιχείο του $X$ διαφορετικό από αυτό δεν προηγείται αυτού, και μεγιστικό αν το ίδιο δεν προηγείται κανενός στοιχείου του $X$ διαφορετικού από τον εαυτό του.
• Το μέγιστο κάτω φράγμα του $X$ είναι το μέγιστο του συνόλου των κάτω φραγμάτων του, και το ελάχιστο άνω φράγμα είναι το ελάχιστο του συνόλου των άνω φραγμάτων του, όταν υπάρχουν.