Παράρτημα AΣτοιχεία από τη Θεωρία Συνόλων

Ας ξενικήσουμε με μερικούς συμβολισμούς. Για δύο σύνολα Α,Β ορίζουμε τα εξής σύνολα: ένωση ($A\cup B$), τομή ($A\cap B$), διαφορά ($A\backslash B$) και καρτεσιανό γινόμενο ($A\times B$):

$$A\cup B:=\{x:x\in A\text{ ή }x\in B\},A\cap B:=\{x:x\in A\text{ και }x\in B\},$$

$$A\backslash B:=\{x:x\in A\text{ και }x\notin B\},A\times B:=\{(\alpha ,\beta ):\alpha \in A,\beta \in B\}$$

όπου το $\in$ σημαίνει «ανήκει», το $\notin$ σημαίνει ((δεν ανήκει)), με $:=$ συμβολίζουμε το «ορίζω» και με $\mathrm{\varnothing }$ συμβολίζουμε το κενό σύνολο, δηλ. $\{\}$ και το σύμβολο $\forall$ σημαίνει «για κάθε».

Αν $X$ είναι ένα μη κενό σύνολο σχέση (relation) στο $X$ λέγεται ένα υποσύνολο του καρτεσιανού γινομένου $X\times X=\{(x,y):x,y\in X\}$.
Έστω $R\subset X\times X$ μία σχέση στο $X$. Η $R$ λέγεται:

• i.

  ανακλαστική (reflective), αν $(x,x)\in R$, $\forall x\in X$,

• ii.

  συμμετρική (symmetric), αν για κάθε $(x,y)\in R$, τότε $(y,x)\in R$,

• iii.

  μεταβατική (transitive), αν $(x,y)\in R$ και $(y,z)\in R$ συνεπάγεται ότι $(x,z)\in R$.

Μία σχέση $R$ στο Χ λέγεται σχέση ισοδυναμίας (equivalence relation) αν είναι ανακλαστική, συμμετρική και μεταβατική. Για μία σχέση ισοδυναμίας $R$ στο σύνολο Χ, κλάση του σημείου $x\in X$ λέγεται το σύνολο $\{y\in X:(x,y)\in R\}$ και συμβολίζεται $[x]$.

Απόδειξη Έστω ότι $[x]\cap [y]\ne \mathrm{\varnothing }$ και $z\in \left[x\right]\cap \left[y\right]$. Τότε $(x,z),(y,z)\in R$ $\Rightarrow$ $(x,z),(z,y)\in R$ $\Rightarrow$ $(x,y)\in R$ $\Rightarrow$ $y\in \left[x\right]$ $\Rightarrow$ $[y]\subset [x]$. Για το αντίστροφο από τη σχέση $(x,y)\in R$ $\Rightarrow$ $(y,x)\in R$ $\Rightarrow$ $x\in \left[y\right]$ $\Rightarrow$ $[x]\subset [y]$. Άρα $[x]=[y]$ και αποδείχθηκε το πρώτο μέρος της πρότασης. Το δεύτερο μέρος προκύπτει αμέσως από το πρώτο και το γεγονός ότι η $R$ είναι ανακλαστική. $\mathrm{■}$

Από την Πρόταση (A.1) συνάγεται ότι μία σχέση ισοδυναμίας στο μη κενό σύνολο $X$ χωρίζεται με υποσύνολα, τις κλάσεις, που είναι ξένα μεταξύ τους ανά δυο και η ένωσή τους είναι όλο το σύνολο $X$. Ένας τέτοιος χωρισμός του $X$ λέγεται διαμέριση (partition). Αλλά και αντίστροφα κάθε διαμέριση του $X$ οδηγεί σε μία σχέση ισοδυναμίας στο $X$. Πράγματι, έστω

(A.2)

μία διαμέριση του $X$. Τότε η σχέση $R$ στο $X$ που ορίζεται ως εξής

(A.3)

είναι εύκολο να αποδειχθεί ότι είναι σχέση ισοδυναμίας.

Κάθε στοιχείο μίας κλάσης ισοδυναμίας λέγεται αντιπρόσωπος της κλάσης αυτής. Πλήρες σύστημα αντιπροσώπων (complete representative system) της σχέσης ισοδυναμίας $R$ στο σύνολο $X$ λέγεται ένα σύνολο με στοιχεία έναν ακριβώς αντιπρόσωπο από κάθε κλάση ισοδυναμίας.

Το σύνολο των κλάσεων ισοδυναμίας της σχέσης ισοδυναμίας $R$ λέγεται σύνολο πηλίκο (quotient set) και συμβολίζεται $X/R$, δηλ.

$$X/R=\{[X]:x\in I\}=\{\left[x\right]:x\in X\}.$$

(A.4)

όπου $I$ είναι ένα σύστημα αντιπροσώπων της σχέσης $R$.

Μία σχέση στο μη κενό σύνολο $X$ λέγεται διάταξη (order) στο $X$ αν είναι:

1. i.

   ανακλαστική, δηλ. , $\forall x\in X$,

2. ii.

   αντισυμμετρική (antisymmetric), δηλ. αν και τότε $x=y$, και

3. iii.

   μεταβατική, δηλ. αν και , τότε .

Ένα σύνολο $X\ne \mathrm{\varnothing }$ στο οποίο έχει οριστεί μία σχέση διάταξης λέγεται μερικά διατεταγμένο (partially ordered) ή διατεταγμένο (ordered) και συμβολίζεται .

Σε ένα μερικά διατεταγμένο σύνολο $X$ είναι δυνατό να υπάρχουν στοιχεία $x,y$ που να μη συνδέονται με τη σχέση ή με τη σχέση . Αν, όμως, για κάθε ζεύγος στοιχείων $x,y$ του $X$ συμβαίνει ή , τότε η σχέση στο $X$ λέγεται σχέση ολικής διάταξης (total order) και το $X$ ολικά διατεταγμένο (totally ordered) ή γραμμικά διατεταγμένο (linearly ordered) σύνολο.

Αν είναι ένα μερικά διατεταγμένο σύνολο και $x,y\in X,$ τότε το $x$ λέγεται προηγούμενο (precedent) του $y$ ή το $y$ επόμενο (next) του $x$ αν . Το $y$ λέγεται αμέσως επόμενο του $x$ αν $\mathrm{\nexists }z$: . Σε αυτή την περίπτωση το $x$ λέγεται αμέσως προηγούμενο του $y$. Συνήθως παριστάνουμε τα στοιχεία του με σημεία και αν το $y$ είναι αμέσως επόμενο του $x$, τότε θέτουμε το $y$ υψηλότερα του $x$ και ενώνουμε το $x$ με το $y$ με μία ευθεία γραμμή. Έτσι αν δύο στοιχεία του $X$ συνδέονται με τη σχέση , τότε θα ενώνονται με μία πολυγωνική γραμμή. Το διάγραμμα που δημιουργείται με αυτόν τον τρόπο λέγεται διάγραμμα του Hasse (Hasse diagram). Π.χ. το σύνολο $\{1,2,3,4,5\}$ με τη συνήθη διάταξη $\le$ του συνόλου των φυσικών αριθμών παριστάνεται με ένα διάγραμμα όπως το σχήμα 1. Το σύνολο των υποσυνόλων του συνόλου $\{\alpha ,\beta ,\gamma \}$ είναι μερικά διατεταγμένο με τη σχέση $\subseteq$ και παριστάνεται με το διάγραμμα του σχήματος 2.

Σχήμα Π.1

Σχήμα Π.2

(A.5)

Ένα στοιχείο $x$ του διατεταγμένου συνόλου λέγεται μέγιστο (maximal) αν δεν είναι προηγούμενο κανενός στοιχείου του $X$ και ελάχιστο (minimal) αν δεν είναι επόμενο κανενός στοιχείου του $X$. Πρώτο (first ή least ή minimum) λέγεται ένα στοιχείο του που είναι προηγούμενο όλων των άλλων στοιχείων του $X$ και τελευταίο (maximum greater) αν είναι επόμενο όλων των άλλων στοιχείων του $X$. Από τους ορισμούς αυτούς φαίνεται ότι το πρώτο στοιχείο του $X$ είναι και ελάχιστο στοιχείο και το τελευταίο είναι και μέγιστο στοιχείο. Δεν ισχύει, όμως, το αντίστροφο κάθε μίας εκ των δύο αυτών προτάσεων. Ακόμα από τους παραπάνω ορισμούς είναι φανερό ότι το πρώτο και το τελευταίο στοιχείο, αν υπάρχουν, είναι μοναδικά ενώ είναι δυνατόν να υπάρχουν περισσότερα από ένα μέγιστα ή ελάχιστα στοιχεία. Π.χ. στο διάγραμμα

Σχήμα Π.3

(A.6)

υπάρχουν τρία μέγιστα στοιχεία, ένα ελάχιστο στοιχείο που είναι και πρώτο, αλλά δεν υπάρχει τελευταίο στοιχείο.

Έστω $A$, $B$ δύο μη κενά σύνολα. Συνάρτηση (function ή map) από το $A$ στο $B$ είναι μία αντιστοιχία που σε κάθε στοιχείο του $A$ αντιστοιχεί ένα μόνο στοιχείο του $B$. Το σύνολο $A$ λέγεται σύνολο ορισμού (domain) και το $B$ σύνολο τιμών (codomain). Ο τρόπος που απεικονίζεται το τυχόν στοιχείο του $A$ μέσω της συνάρτησης λέγεται κανόνας αντιστοιχίας. Μία συνάρτηση $f$ από το $A$ στο $B$ συμβολίζεται ως εξής: $f:A\to B$, $\alpha \mapsto f(\alpha )$, όπου $f(\alpha )$ είναι η εικόνα (image) του $\alpha$ μέσω της $f$. Δύο συναρτήσεις λέγονται ίσες αν έχουν ίσα σύνολα ορισμού, ίσα σύνολα τιμών και τον ίδιο κανόνα αντιστοιχίας.

Έστω $f:A\to B$, $\alpha \mapsto f(\alpha )$ μία συνάρτηση. Το σύνολο $f(A)=\{f(\alpha ):\alpha \in A\}$ λέγεται σύνολο εικόνων του $A$ ή εικόνα του $A$ μέσω της $f$. Είναι φανερό ότι $f(A)\subseteq B$. Αν $f(A)=B$, τότε η $f$ λέγεται επί συνάρτηση (surjection). Αν από τη σχέση $f(\alpha )=f(\beta )$ συνεπάγεται $\alpha =\beta$, όπου $\alpha ,\beta \in A$, τότε η $f$ λέγεται αμφιμονότιμη συνάρτηση (injection). Μία αμφιμονότιμη και επί συνάρτηση λέγεται επίσης ένα προς ένα και συμβολίζεται $1-1$. Ιδιαίτερα η $1-1$ συνάρτηση $A\to A$, $\alpha \mapsto f(\alpha )$ λέγεται ταυτοτική συνάρτηση (identity map) στο $A$ και συμβολίζεται $1_A$.
Αν $Y\subseteq B$, το σύνολο $\{\alpha \in A:f\left(\alpha \right)\in Y\}$ λέγεται αντίστροφη εικόνα (inverse image) του $Y$ και συμβολίζεται $f^{-1}(Y)$.

Αν $A$, $B$, $\mathrm{\Gamma }$ είναι μη κενά σύνολα και $f:A\to B$, $\alpha \mapsto f(\alpha )$, $g:B\to \mathrm{\Gamma }$, $\beta \mapsto g(\beta )$ είναι δύο συναρτήσεις, τότε ορίζεται μία νέα συνάρτηση $A\to \mathrm{\Gamma }$, $\alpha \mapsto g(f(\alpha ))$ η οποία λέγεται σύνθεση των συναρτήσεων $g,f$ και συμβολίζεται $g\circ f$. Η $g\circ f$ περιγράφεται με το διάγραμμα

(A.7)

Έστω $f:A\to B$ μία $1-1$ συνάρτηση. Μπορούμε τότε να ορίσουμε τη συνάρτηση $B\to A$, $f(\alpha )\mapsto \alpha ,$ που λέγεται αντίστροφη συνάρτηση (inverse map) της $f$ και συμβολίζεται $f^{-1}$. Είναι εύκολο να διαπιστωθεί ότι η $f^{-1}$ ικανοποιεί τις σχέσεις

(A.8)

Απόδειξη i.. Έστω $f:A\to B$ μία αμφιμονότιμη συνάρτηση. Ορίζουμε μία αντιστοιχία $g:B\to A$ ως εξής: Κάθε στοιχείο $\beta \in B$ της μορφής $\beta =f(\alpha )$, για κάποιο στοιχείο $\alpha \in A$ αντιστοιχείται στο στοιχείο $\alpha$, που είναι μοναδικό για το $\beta$, αφού η $f$ είναι αμφιμονότιμη. Κάθε στοιχείο του $B$ που δεν ανήκει στο σύνολο $f(A)$ αντιστοιχείται στο στοιχείο ${\alpha }_0\in A$ για κάποιο τυχαίο αλλά από τη στιγμή της επιλογής του σταθερό στοιχείο του $A$. Είναι εύκολο να διαπιστώσει κανείς ότι η $g$ είναι συνάρτηση και ικανοποιεί τη σχέση $g\circ f=1_A$. Αντίστροφα, τώρα, έστω $g:B\to A$ μία συνάρτηση που ικανοποιεί τη σχέση $g\circ f=1_A$. Τότε από τη σχέση $f(\alpha )=f(\beta )$ για δύο στοιχεία $\alpha ,\beta$ του $\mathrm{{\rm A}}$, έπεται ότι $g(f(\alpha ))=g(f(\beta ))$, δηλ. $g\circ f(\alpha )=g\circ f(\beta )$, επομένως $\alpha =\beta$, που σημαίνει ότι η $f$ είναι αμφιμονότιμη.

ii.. Έστω $f:A\to B$ μία επί συνάρτηση. Για κάθε $\beta \in B$ εκλέγουμε ένα στοιχείο ${\alpha }_{\beta }$ του συνόλου $f^{-1}(\beta )=\{\alpha \in A:f\left(\alpha \right)=\beta \}$ που από τη στιγμή της επιλογής του είναι σταθερό. Θεωρούμε, τώρα, την αντιστοιχία $h:B\to A$, $\beta \mapsto {\alpha }_{\beta }$. Είναι εύκολο να αποδειχθεί ότι η $h$ είναι συνάρτηση και ότι ικανοποιεί τη σχέση $f\circ h=1_B$.

Αντίστροφα, τώρα, έστω $h:B\to A$ μία συνάρτηση τέτοια ώστε $f\circ h=1_B$. Τότε $f(h(\beta ))=\beta$ για κάθε $\beta \in B$, δηλ. για κάθε $\beta \in B$ υπάρχει το στοιχείο $h(\beta )\in A$ έτσι ώστε $f(h(\beta ))=\beta$, που σημαίνει ότι η $f$ είναι επί συνάρτηση. $\mathrm{■}$

$1$. Από την απόδειξη του θεωρήματος (A.2) παρατηρούμε ότι μπορούν να οριστούν περισσότερες από μία συναρτήσεις $g$ (ίσως και άπειρες αν τόσες είναι οι δυνατές επιλογές του στοιχείου ${\alpha }_0$) που να ικανοποιούν τις απαιτήσεις του i). Ανάλογη παρατήρηση μπορεί να γίνει για το πλήθος των συναρτήσεων $h$ του ii).

$2$. Η απόδειξη του ii) στηρίχθηκε στο Αξίωμα της Επιλογής (Axiom of Choise): αν $A=\{A_i:i\in I\}$ τότε μπορούμε να επιλέξουμε ένα στοιχείο από κάθε σύνολο $A_i,i\in I$.

Πράξη σε ένα μη κενό σύνολο $A$ λέγεται μία συνάρτηση

(A.9)

Συνήθως μία πράξη στο σύνολο $A$ συμβολίζεται με τα σύμβολα $\ast$, $+$, $\cdot$, $\circ$.

Ένα σύνολο $A\ne \mathrm{\varnothing }$ εφοδιασμένο με μία πράξη, έστω $\ast$, λέγεται αλγεβρική δομή (algebraic structure) και συμβολίζεται με $(A,\ast )$. Ιδιαίτερα μία αλγεβρική δομή που το σύνολο $A$ είναι ένα υποσύνολο του συνόλου $ℂ$ των μιγαδικών αριθμών και η πράξη $\ast$ είναι η πρόσθεση ή ο πολλαπλασιασμός των αριθμών, τότε η $(A,\ast )$ λέγεται αριθμητική δομή (arithmetic structure) ή αριθμητικό σύστημα (arithmetic system). Έτσι έχουμε τις αριθμητικές δομές $(\mathbb{Z},+)$, $(\mathbb{Z},\cdot )$, , $(\mathbb{Q},\cdot )$, $(ℝ,+)$, $(ℝ,\cdot )$, $(ℂ,+)$, $(ℂ,\cdot )$, όπου $\mathbb{Z}$ είναι το σύνολο των ακεραίων αριθμών, $\mathbb{Q}$ είναι το σύνολο των ρητών αριθμών, $ℝ$ είναι το σύνολο των πραγματικών αριθμών και $ℂ$ είναι το σύνολο των μιγαδικών αριθμών.

Σε ένα σύνολο $A\ne \mathrm{\varnothing }$ μπορούν να οριστούν περισσότερες από μία πράξεις, έστω οι $\ast$ και $\circ$ και τότε η αλγεβρική αυτή δομή συμβολίζεται ως $(A,\ast ,\circ )$. Τέτοια παραδείγματα μας προσφέρουν οι αριθμητικές δομές. Μας είναι γνωστές από τη μέση εκπαίδευση οι αριθμητικές δομές: $(\mathbb{Z},+,\cdot )$, $(\mathbb{Q},+,\cdot )$, $(ℝ,+,\cdot )$, $(ℂ,+,\cdot )$. Θα αναφέρουμε τις βασικές ιδιότητες των πράξεων σε ένα σύνολο που κυρίως θα χρησιμοποιούμε σε αυτό το κείμενο.

Μία πράξη $\ast$ στο σύνολο $A\ne \mathrm{\varnothing }$ λέγεται προσεταιριστική (associative) αν

$$(\alpha \ast \beta )\ast \gamma =\alpha \ast (\beta \ast \gamma ),$$

(A.10)

για όλα τα $\alpha ,\beta ,\gamma \in A$.

Μία πράξη $\ast$ στο σύνολο $A\ne \mathrm{\varnothing }$ λέγεται αντιμεταθετική (commutative) αν

$$\alpha \ast \beta =\beta \ast \alpha ,$$

(A.11)

για όλα τα $\alpha ,\beta \in A$.

Η αλγεβρική δομή $(A,\ast )$, όπου η $\ast$ είναι μία προσεταιριστική πράξη λέγεται ημιομάδα (semigroup), ενώ αν η $\ast$ είναι μία αντιμεταθετική πράξη η $(A,\ast )$ λέγεται αντιμεταθετική. Έτσι παρατηρούμε ότι οι αριθμητικές δομές $(\mathbb{Z},+)$, $(\mathbb{Z},\cdot )$ είναι αντιμεταθετικές ημιομάδες. Επίσης η $(\mathbb{Z},+,\cdot )$ είναι αντιμεταθετική ημιομάδα ως προς τις δύο πράξεις.

Συμβολίζουμε με

$$\mathbb{{\rm N}}=\{0,1,2,3,\mathrm{\dots },n,\mathrm{\dots }\}$$

(A.12)

το σύνολο των φυσικών αριθμών και με

$$\mathbb{Z}=\{\mathrm{\dots },-n,\mathrm{\dots }-1,0,1,\mathrm{\dots },n,\mathrm{\dots }\}$$

(A.13)

το σύνολο των ακεραίων αριθμών.

Αρχή της Μαθηματικής Επαγωγής (Principle of Mathematical Induction): Έστω $A$ ένα υποσύνολο του συνόλου των φυσικών αριθμών $\mathbb{N}$ που περιέχει το $0$ και για κάθε $n\in A$, το $n+1\in A$. Τότε το $A$ περιέχει όλους τους φυσικούς αριθμούς, δηλαδή $A=\mathbb{N}$.

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

Μέθοδος της μαθηματικής επαγωγής (Mathematical Induction): Έστω $P(n)$ μία πρόταση που εξαρτάται από τον φυσικό αριθμό $n$.

1. (i)

   Η πρόταση $P(0)$ είναι αληθής (απόδειξη).

2. (i)

   Με την υπόθεση ότι η $P(k)$ είναι αληθής, για κάποιον φυσικό αριθμό $k$, αποδεικνύεται ότι η $P(k+1)$ είναι αληθής.

Αν τα $i.$ και $ii.$, ισχύουν τότε η πρόταση είναι αληθής για κάθε φυσικό αριθμό $n$.

Η υπόθεση ότι η $P(k)$ είναι αληθής αναφέρεται και ως υπόθεση της μαθηματικής επαγωγής.

Η μέθοδος της μαθηματικής επαγωγής προκύπτει αμέσως από την Αρχή της Μαθηματικής Επαγωγής.

Αναφέρουμε τώρα την αρχή της καλής διάταξης την οποία δεχόμαστε ως αξίωμα επίσης.

Αρχή της Καλής Διάταξης (Principle of Well ordering): Κάθε μη κενό υποσύνολο του συνόλου των φυσικών αριθμών έχει ελάχιστο στοιχείο.

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

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

Στην πράξη, ως αποδεικτικό εργαλείο επίσης, είναι χρήσιμη η λεγόμενη Β μορφή της Μαθηματικής Επαγωγής, που διατυπώνεται με το επόμενο θεώρημα και αποδεικνύεται με τη χρήση της αρχής της καλής διάταξης.

Τέλος αναφέρουμε μία ακόμη πρόταση χρήσιμη ως επαγωγική αποδεικτική μέθοδος.