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

Άβαταρ μέλους
Γ.-Σ. Σμυρλής
Δημοσιεύσεις: 553
Εγγραφή: Κυρ Οκτ 14, 2012 9:47 am
Τοποθεσία: Λευκωσία, Κύπρος

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

#1

Μη αναγνωσμένη δημοσίευση από Γ.-Σ. Σμυρλής » Σάβ Ιούλ 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.



Λέξεις Κλειδιά:
ΠΑΠΑΔΟΠΟΥΛΟΣ ΣΤΑΥΡΟΣ
Δημοσιεύσεις: 2677
Εγγραφή: Πέμ Φεβ 27, 2014 9:05 am
Τοποθεσία: ΧΑΛΚΙΔΑ- ΑΘΗΝΑ-ΚΡΗΤΗ

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

#2

Μη αναγνωσμένη δημοσίευση από ΠΑΠΑΔΟΠΟΥΛΟΣ ΣΤΑΥΡΟΣ » Σάβ Ιούλ 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.
Νομίζω ότι είναι απλό.

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

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

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

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

Αρα ακριβώς ένα από τα A,X-A ανήκει στο μεγιστικό οπότε έχει τα μισά υποσύνολα του συνόλου.

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


Άβαταρ μέλους
Γ.-Σ. Σμυρλής
Δημοσιεύσεις: 553
Εγγραφή: Κυρ Οκτ 14, 2012 9:47 am
Τοποθεσία: Λευκωσία, Κύπρος

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

#3

Μη αναγνωσμένη δημοσίευση από Γ.-Σ. Σμυρλής » Σάβ Ιούλ 01, 2017 9:30 pm

Σωστά


ΠΑΠΑΔΟΠΟΥΛΟΣ ΣΤΑΥΡΟΣ
Δημοσιεύσεις: 2677
Εγγραφή: Πέμ Φεβ 27, 2014 9:05 am
Τοποθεσία: ΧΑΛΚΙΔΑ- ΑΘΗΝΑ-ΚΡΗΤΗ

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

#4

Μη αναγνωσμένη δημοσίευση από ΠΑΠΑΔΟΠΟΥΛΟΣ ΣΤΑΥΡΟΣ » Σάβ Ιούλ 01, 2017 10:15 pm

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


Mihalis_Lambrou
Επιμελητής
Δημοσιεύσεις: 11534
Εγγραφή: Κυρ Δεκ 21, 2008 2:04 am

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

#5

Μη αναγνωσμένη δημοσίευση από Mihalis_Lambrou » Κυρ Ιούλ 02, 2017 12:05 am

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


ΠΑΠΑΔΟΠΟΥΛΟΣ ΣΤΑΥΡΟΣ
Δημοσιεύσεις: 2677
Εγγραφή: Πέμ Φεβ 27, 2014 9:05 am
Τοποθεσία: ΧΑΛΚΙΔΑ- ΑΘΗΝΑ-ΚΡΗΤΗ

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

#6

Μη αναγνωσμένη δημοσίευση από ΠΑΠΑΔΟΠΟΥΛΟΣ ΣΤΑΥΡΟΣ » Κυρ Ιούλ 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 στοιχεία τα υποσύνολά του που έχουν περισσότερα από n στοιχεία αποτελουν ένα μεγιστικό όπως όρισε ο Γιώργος αλλά δεν είναι filters η ultrafilters.
Βέβαια αν πάρουμε ένα σύνολο με n στοιχεία και όλα τα υποσύνολά του που περιέχουν ένα συγκεκριμένο στοιχείο τότε αυτό είναι μεγιστικό και αν δεν κάνω λάθος ultrafilters.


Άβαταρ μέλους
Γ.-Σ. Σμυρλής
Δημοσιεύσεις: 553
Εγγραφή: Κυρ Οκτ 14, 2012 9:47 am
Τοποθεσία: Λευκωσία, Κύπρος

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

#7

Μη αναγνωσμένη δημοσίευση από Γ.-Σ. Σμυρλής » Κυρ Ιούλ 02, 2017 2:30 am

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

Παράδειγμα: n=3, \,\,\mathcal S=\big\{\{1,2\},\{1,3\},\{2,3\},\{1,2,3\}\big\}.


Άβαταρ μέλους
Demetres
Γενικός Συντονιστής
Δημοσιεύσεις: 8259
Εγγραφή: Δευ Ιαν 19, 2009 5:16 pm
Τοποθεσία: Λεμεσός/Πύλα
Επικοινωνία:

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

#8

Μη αναγνωσμένη δημοσίευση από Demetres » Κυρ Ιούλ 02, 2017 10:47 am

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

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

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

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

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

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


ΠΑΠΑΔΟΠΟΥΛΟΣ ΣΤΑΥΡΟΣ
Δημοσιεύσεις: 2677
Εγγραφή: Πέμ Φεβ 27, 2014 9:05 am
Τοποθεσία: ΧΑΛΚΙΔΑ- ΑΘΗΝΑ-ΚΡΗΤΗ

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

#9

Μη αναγνωσμένη δημοσίευση από ΠΑΠΑΔΟΠΟΥΛΟΣ ΣΤΑΥΡΟΣ » Κυρ Ιούλ 02, 2017 7:21 pm

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

Εστω σύνολο A με \left | A \right |=n

Παίρνουμε υποσύνολο του B με \left | B \right |=2k+1< n

Παίρνουμε όλα τα υποσύνολα του B που έχουν περισσότερα από k στοιχεία.

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

όπου S\subset B με περισσότερα από k στοιχεία και D\subseteq A-B


BAGGP93
Δημοσιεύσεις: 1353
Εγγραφή: Σάβ Ιούλ 02, 2011 8:48 pm
Τοποθεσία: Ιωάννινα - Αθήνα

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

#10

Μη αναγνωσμένη δημοσίευση από BAGGP93 » Κυρ Ιούλ 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|} .


Παπαπέτρος Ευάγγελος
Απάντηση

Επιστροφή σε “Μαθηματική Λογική & Θεμέλια Μαθηματικών”

Μέλη σε σύνδεση

Μέλη σε αυτήν τη Δ. Συζήτηση: Δεν υπάρχουν εγγεγραμμένα μέλη και 1 επισκέπτης