mathematica.gr

Δημοσιεύτηκε: **Σάβ Ιούλ 01, 2017 4:35 pm**

ΠΡΟΒΛΗΜΑ. Ἔστω $\mathscr P$ τὸ δυναμοσύνολο τοῦ $\{1,2,\ldots,n\}$ καὶ $\mathcal S\subset\mathscr P$ , μὲ τὴν ἰδιότητα
$\displaystyle{ A,B\in \mathcal S\quad\Longrightarrow\quad A\cap B\ne\varnothing. }$
Ἄν τὸ $\mathcal S$ εἶναι μεγιστικὸ μὲ αὐτὴ τὴν ἰδιότητα, δείξατε ὅτι $|\mathcal S|=2^{n-1}$ .

ΣΗΜΕΙΩΣΗ. Τὸ $\mathcal S$ εἶναι μεγιστικὸ μὲ αὐτὴ τὴν ἰδιότητα σημαίνει ὅτι, ἄν $\mathcal S\subsetneqq \mathcal T\subset \mathscr P$ , τότε ὑπάρχουν $A,B\in \mathcal T$ , ὥστε $A\cap B=\varnothing$ .

Δημοσιεύτηκε: **Σάβ Ιούλ 01, 2017 6:36 pm**

Γ.-Σ. Σμυρλής έγραψε:ΠΡΟΒΛΗΜΑ. Ἔστω $\mathscr P$ τὸ δυναμοσύνολο τοῦ $\{1,2,\ldots,n\}$ καὶ $\mathcal S\subset\mathscr P$ , μὲ τὴν ἰδιότητα
$\displaystyle{ A,B\in \mathcal S\quad\Longrightarrow\quad A\cap B\ne\varnothing. }$
Ἄν τὸ $\mathcal S$ εἶναι μεγιστικὸ μὲ αὐτὴ τὴν ἰδιότητα, δείξατε ὅτι $|\mathcal S|=2^{n-1}$ .

ΣΗΜΕΙΩΣΗ. Τὸ $\mathcal S$ εἶναι μεγιστικὸ μὲ αὐτὴ τὴν ἰδιότητα σημαίνει ὅτι, ἄν $\mathcal S\subsetneqq \mathcal T\subset \mathscr P$ , τότε ὑπάρχουν $A,B\in \mathcal T$ , ὥστε $A\cap B=\varnothing$ .

Νομίζω ότι είναι απλό.

θα δείξουμε ότι σε ένα μεγιστικό θα ανήκει ένα ακριβώς από τα

,

.

Είναι προφανές ότι και τα δύο δεν ανήκουν συγχρόνως.

Αν υποθέσουμε ότι και τα δύο δεν ανήκουν τότε υπάρχουν στο μεγιστικό K,L

με

$A\cap K=0,(X-A)\cap L=0$ που οδηγεί σε άτοπο γιατί $K\cap L\neq 0$

Αρα ακριβώς ένα από τα

,

ανήκει στο μεγιστικό οπότε έχει τα μισά υποσύνολα του συνόλου.

Ζητώ προκαταβολικά συγνώμμη για την εμφάνηση αλλά γράφω από μικρό υπολογιστή.

Δημοσιεύτηκε: **Σάβ Ιούλ 01, 2017 9:30 pm**

Σωστά

Δημοσιεύτηκε: **Σάβ Ιούλ 01, 2017 10:15 pm**

Γ.-Σ. Σμυρλής έγραψε:Σωστά

Για αυτό ήμουν σχεδόν σίγουρος. Η αλήθεια είναι ότι το έλυσα χωρίς να καταλάβω.
Νομίζω ότι έχει ενδιαφέρον τι δομή έχουν αυτές.
Θα γράψω κάποια πράγματα όταν βρεθώ σε κανονικό υπολογιστή.
Από που προέρχεται το πρόβλημα;

Δημοσιεύτηκε: **Κυρ Ιούλ 02, 2017 12:05 am**

ΠΑΠΑΔΟΠΟΥΛΟΣ ΣΤΑΥΡΟΣ έγραψε: Νομίζω ότι έχει ενδιαφέρον τι δομή έχουν αυτές.

Είναι τα λεγόμενα ultrafilers. Στις Τοπολογίες χρησιμοποιούν συνήθως δίκτυα (nets)
για την σύγκλιση αλλά αραιά και που εργάζονται στην θέση τους με filters και ultrafilters.
Αν θυμάμαι καλά, η Toπολογία του Bourbaki εργάζεται με filters και ultrafilters.
To κλασικό βιβλίο Ultafilters είναι βέβαια των Νεγρεπόντη, Comfort.

Δημοσιεύτηκε: **Κυρ Ιούλ 02, 2017 12:28 am**

Mihalis_Lambrou έγραψε:
ΠΑΠΑΔΟΠΟΥΛΟΣ ΣΤΑΥΡΟΣ έγραψε: Νομίζω ότι έχει ενδιαφέρον τι δομή έχουν αυτές.
Είναι τα λεγόμενα ultrafilers. Στις Τοπολογίες χρησιμοποιούν συνήθως δίκτυα (nets)
για την σύγκλιση αλλά αραιά και που εργάζονται στην θέση τους με filters και ultrafilters.
Αν θυμάμαι καλά, η Toπολογία του Bourbaki εργάζεται με filters και ultrafilters.
To κλασικό βιβλίο Ultafilters είναι βέβαια των Νεγρεπόντη, Comfort.

Καλησπέρα Μιχάλη. Δεν νομίζω,
https://en.wikipedia.org/wiki/Ultrafilter

Αν πάρουμε ένα σύνολο με 2n+1

στοιχεία τα υποσύνολά του που έχουν περισσότερα από

στοιχεία αποτελουν ένα μεγιστικό όπως όρισε ο Γιώργος αλλά δεν είναι filters η ultrafilters.
Βέβαια αν πάρουμε ένα σύνολο με

στοιχεία και όλα τα υποσύνολά του που περιέχουν ένα συγκεκριμένο στοιχείο τότε αυτό είναι μεγιστικό και αν δεν κάνω λάθος ultrafilters.

Δημοσιεύτηκε: **Κυρ Ιούλ 02, 2017 2:30 am**

Τα ὑπερφίλτρα πράγματι ἔχουν τὴν μεγιστικότητα ποὺ ἀπαιτεῖ ἡ ἄσκηση. Ὅμως, ἐνδέχεται ἕνα μεγιστικὸ σύνολο ποὺ ἱκανοποιεῖ τὰ δεδομένα τῆς ἀσκήσεως νὰ μὴν εἶναι ὑπερφίλτρο.

Παράδειγμα: n=3

, $\,\,\mathcal S=\big\{\{1,2\},\{1,3\},\{2,3\},\{1,2,3\}\big\}$ .

Δημοσιεύτηκε: **Κυρ Ιούλ 02, 2017 10:47 am**

Η αρχική άσκηση είναι μια από τις πρώτες ασκήσεις που συναντάει κανείς σε ένα τομέα της συνδυαστικής που ονομάζεται extremal set theory. Σε αυτό τον τομέα οι ερωτήσεις που συναντάμε είναι της μορφής: «Ποιο είναι το μεγαλύτερο μέγεθος μιας οικογένειας υποσυνόλων του $\{1,2,\ldots,n\}$ η οποία να έχει μια συγκεκριμένη ιδιότητα;»

Ακόμη όμως και από αυτήν την απλή ερώτηση πηγάζουν δύσκολα ερωτήματα. Π.χ. αφού βρήκαμε ότι το μέγιστο μέγεθος είναι $2^{n-1}$ και μάλιστα αποδείξαμε το πιο ισχυρό ότι κάθε μεγιστική οικογένεια είναι μέγιστη, η επόμενη ερώτηση είναι να περιγράψουμε όλες αυτές τις μέγιστες οικογένειες και αν είναι δυνατόν να τις μετρήσουμε.

Αυτά τα δύο ερωτήματα στην συγκεκριμένη περίπτωση είναι ανοικτά. Ένα πράγμα που γνωρίζουμε είναι το εξής:

Ας πάρουμε την περίπτωση n = 2m

άρτιος. Μια μέγιστη οικογένεια είναι να πάρουμε όλα τα σύνολα με τουλάχιστον m+1

στοιχεία μαζί με ένα σύνολο από κάθε ζεύγος συμπληρωματικών συνόλων μεγέθους

. Είναι εύκολο να δειχθεί ότι αυτή είναι μέγιστη οικογένεια και ότι υπάρχουν $2^{\frac{1}{2}\binom{2m}{m}}$ τέτοιες οικογένειες.

Έχει αποδειχθεί ότι ασυμπτωτικά υπάρχουν $2^{\frac{(1+o(1))}{2}\binom{2m}{m}}$ μέγιστες οικογένειες. Δηλαδή υπό μια έννοια οι πλείστες μέγιστες οικογένειες μοιάζουν με αυτήν την πιο πάνω παραγράφου. (Αν και αυτό δεν είναι ακριβώς σωστό αφού το (1+o(1))

είναι στον εκθέτη.)

Είχα γράψει κάποια πράγματα για αυτό το πρόβλημα εδώ τον καιρό που ασχολούμουν με το blog μου.

Δημοσιεύτηκε: **Κυρ Ιούλ 02, 2017 7:21 pm**

Να δώσω ακόμα μια μορφή τέτοιου συνόλου.

Εστω σύνολο

με $\left | A \right |=n$

Παίρνουμε υποσύνολο του

με $\left | B \right |=2k+1< n$

Παίρνουμε όλα τα υποσύνολα του

που έχουν περισσότερα από

στοιχεία.

Τα σύνολα είναι $S\cup D$

όπου $S\subset B$ με περισσότερα από

στοιχεία και $D\subseteq A-B$

Δημοσιεύτηκε: **Κυρ Ιούλ 02, 2017 8:42 pm**

Μπορούμε να γενικεύσουμε το αρχικό πρόβλημα.

Έστω $\displaystyle{\left(R,+,\cdot\right)}$ πεπερασμένος μεταθετικός δακτύλιος του Boole ( $\displaystyle{\,\,\,x^2=x\,,\forall\,x\in R}$ ) με μονάδα

και $\displaystyle{S\subseteq R}$ με την ιδιότητα $\displaystyle{x\in S\,\,\land\,\,y\in S\implies x\,y\neq 0}$ που είναι μεγιστικό ως

προς αυτή την ιδιότητα, δηλαδή αν $\displaystyle{S\subset T\subseteq R}$ , τότε υπάρχουν $\displaystyle{x\,,y\in T}$ με $\displaystyle{x\,y=0}$

Τότε, $\displaystyle{2\,|S|=|R|}$ .

mathematica.gr

Μεγιστικὴ ὑποκλάση τοῦ δυναμοσυνόλου

Μεγιστικὴ ὑποκλάση τοῦ δυναμοσυνόλου

Re: Μεγιστικὴ ὑποκλάση τοῦ δυναμοσυνόλου

Re: Μεγιστικὴ ὑποκλάση τοῦ δυναμοσυνόλου

Re: Μεγιστικὴ ὑποκλάση τοῦ δυναμοσυνόλου

Re: Μεγιστικὴ ὑποκλάση τοῦ δυναμοσυνόλου

Re: Μεγιστικὴ ὑποκλάση τοῦ δυναμοσυνόλου

Re: Μεγιστικὴ ὑποκλάση τοῦ δυναμοσυνόλου

Re: Μεγιστικὴ ὑποκλάση τοῦ δυναμοσυνόλου

Re: Μεγιστικὴ ὑποκλάση τοῦ δυναμοσυνόλου

Re: Μεγιστικὴ ὑποκλάση τοῦ δυναμοσυνόλου