Filter (matematika)

U matematici, filter je poseban podskup parcijalno uređenog skupa. Filteri se javljaju u teoriji uređenja i teoriji mreža, a takođe i u topologiji, gde su i nastali. Dualan pojam pojmu filtera je ideal.

Motivacija[уреди | уреди извор]

Intuitivno, filter u parcijalno uređenom skupu (posetu), P, je podskup od P koji sadrži one elemente koji zadovoljavaju neke zadate kriterijume. Na primer, ako je x element poseta, onda je skup elemenata većih od x filter, nazvan glavnim filterom nad x. (Ako su x i y neuporedivi elementi poseta, onda nijedan od glavnih filtera nad x i nad y nije sadržan u drugom, i obrnuto.)

Slično, filter na skupu sadrži one podskupove koji su dovoljno veliki da ispunjavaju zadati uslov. Na primer, ako je skup realna prava i x jedna od njenih tačaka, onda je familija skupova koja sadrži x u svojoj unutrašnjosti filter, nazvan filter okolina od x. U ovom slučaju uslov je malo veći od x, ali još ne sadrži ni jednu određenu tačku prave.

Gornje interpretacije objašnjavaju uslove 1 i 3 u odeljku Opšta definicija: Očigledno prazan skup nije "dovoljno veliki", i očigledno skup "dovoljno velikih" elemenata trebalo bi da bude "odozgo zatvoren". Međutim, one zapravo ne objašnjavaju uslov 2 opšte definicije. Zašto bi dva "dovoljno velika" elementa sadržala zajednički "dovoljno veliki" element?

Alternativno, filter se može posmatrati kao "šema lociranja": Kada pokušavamo da lociramo nešto (tačku ili podskup) u prostoru X, nazovimo filter skupom podskupova od X koji mora sadržati "ono što je traženo". Onda taj "filter" prirodno mora imati sledeću strukturu:

1. Prazan skup ne sadrži ništa tako da on ne može pripadati filteru.

2. Ako dva podskupa, E i F, sadržate "ono što je traženo", onda i njihov presek to sadrži. Shodno tome, trebalo bi da je filter zatvoren zbog konačnog preseka.

3. Ako skup E sadrži "šta je traženo", to takođe mora i svaki njegov podskup. Shodno tome, filter je odozgo zatvoren.

Ultrafilter se može posmatrati kao "savršena šema lociranja" gde svaki podskup E prostora X može biti korišćen u odlučivanju da li se "ono što je traženo" može nalazti u E.

Iz ove interpretacije, kompaktnost se može posmatrati kao osobina da se "ni jedna šema lociranja ne može završiti ničim", ili, drugačije rečeno, "uvek postoji nešto što će se pronaći".

Matematički pojam filtera pruža precizan jezik za postupanje u ovim situacijama na rigorozan i opšti način, koji je koristan u analizi, topologiji i logici.

Opšta definicija[уреди | уреди извор]

Podskup F parcijalno uređenog skupa (P,≤) je filter ako važe sledeći uslovi:

F je neprazan.
Za svako x, y iz F, postoji z iz F takvo da z≤x i z≤y. (F opadajuće usmeren)
Za svako x iz F i y iz P, x≤y sledi da je y iz F. (F je gornji skup, ili odozgo zatvoren)

Filter je pravi ako nije jednak celom skupu P. Ovaj uslov se ponekad dodaje definiciji filtera.

Iako je ovo najopštiji način za definisanje filtera za proizvoljne posete, prvobitno je bio definisan samo za mreže. U tom slučaju, gornja definicija se može zameniti sledećom ekvivalentnom izjavom: Podskup F mreže (P,≤) je filter, akko je neprazan gornji skup koji je zatvoren konačnim infimumima, odnosno, za sve x, y iz F, to je takođe slučaj kada je x ∧ y iz F.^[1]^‍:184 Podskup S od F je baza filtera ako je gornji skup generisan S celo F.

Najmanji filter koji sadrži dati element p je glavni filter i p je glavni element u tom slučaju. Glavni filter za p je upravo zadat skupom $\{x\in P\ |\ p\leq x\}$ i označen je prefiksom p sa strelicom usmerenom na gore: $\uparrow p$ .

Dualan pojam filteru, odnosno pojam dobijen obrtanjem svih ≤ i zamenom ∧ sa ∨, je ideal. Zbog dualnosti, rasprva o filterima se obično svodi na raspravu o idealima.

Filter na skupu[уреди | уреди извор]

Specijalan slučaj filtera su filteri definisani na skupu. Za dati skup S, parcijalno uređenje ⊆ se može definisati na partitivnom skupu P(S) sa relacijom podskup, pretvarajući (P(S),⊆) u mrežu. Definišimo filter F na S kao neprazan podskup partitivnog skupa P(S) sa sledećim osobinama:

Ako su A i B iz F, onda je takođe i njihov presek. (F je zatvoren konačnim presekom)
Ako je A iz F i A je podskup od B, onda je B iz F, za sve podskupove B od S. (F je odozgo zatvoren)

Iz ove definicije, filter na skupu je zaista filter.

Druga osobina podrazumeva da je S iz F (odakle važi da je F neprazan podskup partitivnog skupa P(S)).

Ako neprazan skup ne pripada F, kažemo da je F pravi filter.^[2] Osobina 1 implicira da pravi filter na skupu ima osobinu konačnog preseka. Jedini filter na S koji nije pravi je P(S).

Baza filtera (ili beze filtera) je podskup B od P(S) sa osobinom da je B neprazan i presek bilo koja dva elementa skupa B sadrži (kao podskup) element skupa B (B je opadajuće usmeren). Ako prazan skup ne pripada B, kažemo da je B prava baza filtera.

Dati filter baze B, filter generisan ili razapet sa B je definisan kao najmanji filter koji sadrži B. To je familija svih podskupova od S koja uključuje elementB. Svaki filter je takođe filter baze, pa se proces prelaska sa filtera beze na filter može videti kao neka vrsta upotpunjavanja.

Ako su B i C dve baze filtera na S, kaže se da je C finija od B (ili da je C usitnjenje od B)ako za svaku B₀ ∈ B, postoji C₀ ∈ C takva da C₀ ⊆ B₀. Takođe ako je B finija C, kaže se da su one ekvivalentne baze filtera.

Ako su B i C baze filtera, onda je C finija od B akko the filter razapet sa C sadrži filter razapet sa B. Odatle, B i C su ekvivalentne baze filtera akko generišu isti filter.
Za baze filtera A, B, i C, ako je A finija od B i B finija od C onda je A finija od C. Prema tome relacija usitnjavanja je preuređenje na skupu baza filtera, i prelazak sa baze filtera na filter je vrsta prelaska sa preuređenja na povezano parcijalno uređenje.

Za svaki podskup T od P(S) postoji najmanji (verovatno ne pravi) filter F koji sadrži T, nazvan filterom generisanim ili razvučenim sa T. Konstruisan je uzimanjem svih konačnih preseka od T, koji onda formiraju bazu filtera za F. Taj filter je pravi akko je konačan presek elemenata od T neprazan, u tom slučaju kažemo da je T podbaza filtera.

Primeri[уреди | уреди извор]

Neka je S skup i C neprazan podskup odS. Tada je $\{C\}$ baza filtera. Filter koji generiše (odnosno, skup svih podskupova koji sadrže containing C) se naziva glavni filter generisan sa C.
Filter je slobodan filter ako je presek svih njegovih članova prazan. Pravi glavni filter nije slobodan. Budući da je presek bilo kog konačnog broja članova filtera takođe član, ne postoji pravi filter na konačnom skupu koji je slobodan, i zaista glavni filter je generisan zajedničkim svih svojih članova. Filter koji nije glavni na beskonačnom skupu nije nužno slobodan.
Frešeov filter na beskonačnom skupu S je skup svih podskupova od Skoji imaju konačan komplement. Filter na S je slobodan akko sadrži Frešeov filter.
Svaka uniformna struktura na skupu X je filter na X×X.
Filter na posetu može biti napravljen korišćenjem Rasiova-Sikorski leme, često korišćene u forsiranju.
Skup $\{\{N,N+1,N+2,\dots \}:N\in \{1,2,3,\dots \}\}$ je nazvan baza filtera repova niza prirodnih brojeva $(1,2,3,\dots )$ . Baza filtera repova može biti napravljena od bilo koje mreže $(x_{\alpha })_{\alpha \in A}$ korišćenjem konstrukcije $\{\{x_{\alpha }:\alpha \in A,\alpha _{0}\leq \alpha \}:\alpha _{0}\in A\}$ , gde je filter koji ta baza generiše nazvan filter slučajnosti mreže. Stoga, sve mreže generišu bazu filtera (i odatle filter). Kako su svi nizovi mreže, ovo važi takođe važi i za nizove.

Filteri u teoriji modela[уреди | уреди извор]

Za svaki filter F na skupu S, skup funkcija definisan sa:

$m(A)={\begin{cases}1&{\text{if }}A\in F\\0&{\text{if }}S\setminus A\in F\\{\text{nedefinisano}}&{\text{inače}}\end{cases}}$

je konačno aditivan "mera" ako se taj termin slobodno tumači. Dakle, tvrđenje: $\left\{\,x\in S:\varphi (x)\,\right\}\in F$

može se smatrati donekle analognim tvrđenju da φ važi "skoro svugde". To tumačenje pripadanja filteru se koristi (za motivaciju, iako nije potrebna za stvarne dokaze) u teoriji ultraproizvoda u teoriji modela, grani matemetičke logike.

Filteri u topologiji[уреди | уреди извор]

U topologiji i analizi, filteri se koriste za definisanje konvergencije slično nizovima u metričkim prostorima.

U topologiji i s njom povezanim oblastima matematike, filter je uopštenje mreža. Oboje, mreže i filteri, pružaju veoma opšte kontekste za objedinjavanje različitih pojmova limesa u proizvoljnim topološkim prostorima.

Niz je obično indeksiran prirodnim brojevima, koji čine totalno uređen skup. Prema tome, limesi u prvobrojnim prostorima mogu biti opisani pomoću nizova. Međutim, ako prostor nije prvoprebrojiv, mreže ili filteri mogu biti korišćeni. Mreže uopštavaju pojam niza zahtevajući da skup indeksa bude usmeren. Filteri se mogu smatrati skupovima izgrađenim iz više mreža. Stoga su i limes filtera i limes mreže pojmovno jednake limesu niza.

Baze okolina[уреди | уреди извор]

Neka je X topološki prostor i x tačka iz X.

Uzmimo da je N_x filter okolina u tački x za X. To znači da je N_x skup svih topoloških okolina tačke x. Može se proveriti da je N_x filter. Sistem okolina je drugo ime za filter okolina.
Kada se kaže da je N baza okolina u x za X to znači da je svaki podskup V₀ od X okolina tačke x akko postoji N₀ ∈ N takav da N₀ ⊆ V₀. Svaka baza okoline u x je baza filtera koji generiše filter okolina u x.

Konvergentne baze filtera[уреди | уреди извор]

Neka je X topološki prostor i x tačka iz X.

Kaže se da baza filtera B konvergira ka x, u oznaci B → x, što znači da za svaku okolinu U od x, postoji B₀ ∈ B takva da B₀ ⊆ U. U tom slučaju, x se naziva limes od B, a B se naziva konvergentna baza filtera.
Svaka okolina baze N od x konvergira ka x.
- Ako je N okolina baze u x i C baza filtera na X, onda C → x akko je C finija od N.
- Ako Y ⊆ X, tačka p ∈ X se naziva granična tačka od Y u X akko svaka okolina U od p u X seče Y. To se dešava akko postoji baza filtera podskupa od Y koja konvergira ka p u X.
Za Y ⊆ X, sledeće je ekvivalentno:
- (i) Postoji baza filtera F čiji elementi su svi sadržani u Y takva da F → x.
- (ii) Postoji filter F takav da je Y pripada F i F → x.
- (iii) Tačka x se nalazi u zatvorenju od Y.

Zaista:

Iz (i) sledi (ii): ako je F baza filtera koja zadovoljava osobinu (i), onda filter pridružen F zadovoljava osobinu (ii).

Iz (ii) sledi (iii): ako je U proizvoljna otvorena okolina x onda po definiciji konvergencije U sadrži element iz F; kako je takođe Y element iz F, U i Y imaju neprazan presek.

Iz (iii) sledi (i): Definišimo $F=\{U\cap Y\ |\ U\in N_{x}\}$ . Odavde je F baza filtera koja zadovoljava osobinu (i).

Grupisanje[уреди | уреди извор]

Neka je X topološki prostor i x tačka iz X.

Za bazu filtera B na X kažemo da se nagomilava u x (ili je x tačka nagomilavanja) akko Svaki element iz B ima neprazan presek sa svakom okolinom od x.
- Ako se baza filtera B nagomilava u x i finija je od baze filtera C, onda se C takođe nagomilava u x.
- Svaki limes baze filtera je takođe tačka nagomilavanja te baze.
- Baza filtera B koji ima x kao tačku nagomilavanja ne mora konvergirati kax, ali postoji finija baza filtera koja hoće. Na primer, baza filtera konačnog preseka skupova podbaze $B\cup N_{x}$ .
- Za bazu filtera B, skup ∩{cl(B₀) : B₀∈B} je skup svih tačaka nagomilavanja B (zatvorenje od B₀ je cl(B₀)). Pretpostavimo da je X potpuna mreža.
  - Limes inferior skupa B je infimum skupa svih tačaka nagomilavanja skupa B.
  - Limes superior skupa B je supremum skupa svih tačaka nagomilavanja skupa B.
  - B je konvergentna baza filtera akko su njeni limes superior i limes inferior jednaki; u tom slučaju, ta vrednost predstavlja limes baze filtera.

Vidite još[уреди | уреди извор]

Референце[уреди | уреди извор]

^ B.A. Davey and H.A. Priestley (1990). Introduction to Lattices and Order. Cambridge Mathematical Textbooks. Cambridge University Press.
^ Goldblatt, R. Lectures on the Hyperreals: an Introduction to Nonstandard Analysis. стр. 32.

Reference[уреди | уреди извор]

Nicolas Bourbaki, General Topology (Topologie Générale). ISBN 978-0-387-19374-8. (Ch. 1-4): Provides a good reference for filters in general topology (Chapter I) and for Cauchy filters in uniform spaces (Chapter II)
Stephen Willard, General Topology, (1970) Addison-Wesley Publishing Company, Reading Massachusetts. (Provides an introductory review of filters in topology.)
David MacIver, Filters in Analysis and Topology (2004) (Provides an introductory review of filters in topology and in metric spaces.)
Burris, Stanley N., and H.P. Sankappanavar, H. P., 1981. A Course in Universal Algebra. Springer-Verlag. ISBN 978-3-540-90578-3..

[1] B.A. Davey and H.A. Priestley (1990). Introduction to Lattices and Order. Cambridge Mathematical Textbooks. Cambridge University Press.

[2] Goldblatt, R. Lectures on the Hyperreals: an Introduction to Nonstandard Analysis. стр. 32.

[1]

[2]