SUPPORT THE WORK

GetWiki

ultrafilter

ARTICLE SUBJECTS
aesthetics  →
being  →
complexity  →
database  →
enterprise  →
ethics  →
fiction  →
history  →
internet  →
knowledge  →
language  →
licensing  →
linux  →
logic  →
method  →
news  →
perception  →
philosophy  →
policy  →
purpose  →
religion  →
science  →
sociology  →
software  →
truth  →
unix  →
wiki  →
ARTICLE TYPES
essay  →
feed  →
help  →
system  →
wiki  →
ARTICLE ORIGINS
critical  →
discussion  →
forked  →
imported  →
original  →
ultrafilter
[ temporary import ]
please note:
- the content below is remote from Wikipedia
- it has been imported raw for GetWiki
{{About|the mathematical concept|the physical device|ultrafiltration}}File:Filter vs ultrafilter.svg|thumb|The powerset lattice of the set {1,2,3,4}, with the upper setupper setIn the mathematical field of set theory, an ultrafilter on a given partially ordered set (poset) P is a maximal filter on P, that is, a filter on P that cannot be enlarged. Filters and ultrafilters are special subsets of P. If P happens to be a Boolean algebra, each ultrafilter is also a prime filter, and vice versa.BOOK, B.A. Davey and H.A. Priestley, Introduction to Lattices and Order, Cambridge University Press, Cambridge Mathematical Textbooks, 1990, {{rp|186}} If X is an arbitrary set, its power set ℘(X), ordered by set inclusion, is always a Boolean algebra, and (ultra)filters on ℘(X) are usually called "(ultra)filters on X".If X happens to be partially ordered, too, particular care is needed to understand from the context whether an (ultra)filter on ℘(X) or an (ultra)filter just on X is meant; both kinds of (ultra)filters are quite different. Some authors{{cn|date=July 2016}} use "(ultra)filter" of a partial ordered set" vs. "on an arbitrary set"; i.e. they write "(ultra)filter on X" to abbreviate "(ultra)filter of ℘(X)".Ultrafilters have many applications in set theory, model theory, and topology.{{rp|186}} An ultrafilter on a set X may be considered as a finitely additive measure. In this view, every subset of X is either considered "almost everything" (has measure 1) or "almost nothing" (has measure 0).{{cn|date=July 2016}}

Ultrafilters on partial orders

In order theory, an ultrafilter is a subset of a partially ordered set that is maximal among all proper filters. This implies that any filter that properly contains an ultrafilter has to be equal to the whole poset.Formally, if P is a set, partially ordered by (≤), then
  • a subset F of P is called a filter on P if
    • F is nonempty,
    • for every x, y in F, there is some element z in F such that z ≤ x and z ≤ y, and
    • for every x in F and y in P, x ≤ y implies that y is in F, too;
  • a proper subset U of P is called an ultrafilter on P if
    • U is a filter on P, and
    • there is no filter F on P such that U ⊊ F ⊊ P.

Special case: Boolean algebra

An important special case of the concept occurs if the considered poset is a Boolean algebra. In this case, ultrafilters are characterized by containing, for each element a of the Boolean algebra, exactly one of the elements a and ¬a (the latter being the Boolean complement of a):If P is a Boolean algebra and F ⊊ P is a proper filter, then the following statements are equivalent:
  1. F is an ultrafilter on P,
  2. F is a prime filter on P,
  3. for each a in P, either a is in F or (¬a) is in F.{{rp|186}}
A proof of 1.⇔2. is also given in (Burris, Sankappanavar, 2012, Cor.3.13, p.133)BOOK,weblink 978-0-9880552-0-9, Stanley N. Burris and H.P. Sankappanavar, A Course in Universal Algebra, 2012, Moreover, ultrafilters on a Boolean algebra can be related to prime ideals, maximal ideals, and homomorphisms to the 2-element Boolean algebra {true, false}, as follows:
  • Given a homomorphism of a Boolean algebra onto {true, false}, the inverse image of "true" is an ultrafilter, and the inverse image of "false" is a maximal ideal.
  • Given a maximal ideal of a Boolean algebra, its complement is an ultrafilter, and there is a unique homomorphism onto {true, false} taking the maximal ideal to "false".
  • Given an ultrafilter of a Boolean algebra, its complement is a maximal ideal, and there is a unique homomorphism onto {true, false} taking the ultrafilter to "true".{{cn|date=July 2016}}

Special case: ultrafilter on the powerset of a set

Given an arbitrary set X, its power set ℘(X), ordered by set inclusion, is always a Boolean algebra; hence the results of the above section (#Special case: Boolean algebra) apply. An (ultra)filter on ℘(X) is often called just an "(ultra)filter on X". The above formal definitions can be particularized to the powerset case as follows:Given an arbitrary set X, an ultrafilter on ℘(X) is a set U consisting of subsets of X such that:
  1. The empty set is not an element of U.
  2. If A and B are subsets of X, the set A is a subset of B, and A is an element of U, then B is also an element of U.
  3. If A and B are elements of U, then so is the intersection of A and B.
  4. If A is a subset of X, then eitherProperties 1 and 3 imply that A and {{nowrap|X A}} cannot both be elements of U. A or its relative complement X A is an element of U.
A characterization is given by the following theorem.A filter U on ℘(X) is an ultrafilter if any of the following conditions are true:
  1. There is no filter F strictly finer than U, that is, U ⊆ F implies U = F.
  2. If a union A∪B is in U, then A is in U or B is.
  3. For each subset A of X, either A is in U or (X A) is.
Another way of looking at ultrafilters on a power set ℘(X) is to define a function m on ℘(X) by setting m(A) = 1 if A is an element of U and m(A) = 0 otherwise. Such a function is called a 2-valued morphism. Then m is finitely additive, and hence a content on ℘(X), and every property of elements of X is either true almost everywhere or false almost everywhere. However, m is usually not countably additive, and hence does not define a measure in the usual sense.For a filter F that is not an ultrafilter, one would say m(A) = 1 if A âˆˆ F and m(A) = 0 if X A âˆˆ F, leaving m undefined elsewhere.{{cn|date=July 2016}}{{clarify|reason=A function m can certainly be defined in that way. However, this is pointless unless such an m can be shown to have some useful properties (e.g. being a 'content'). They should be stated here.|date=July 2016}}

Completeness

The completeness of an ultrafilter U on a powerset is the smallest cardinal κ such that there are κ elements of U whose intersection is not in U. The definition implies that the completeness of any powerset ultrafilter is at least aleph_0. An ultrafilter whose completeness is greater than aleph_0—that is, the intersection of any countable collection of elements of U is still in U—is called countably complete or σ-complete.The completeness of a countably complete nonprincipal ultrafilter on a powerset is always a measurable cardinal.{{cn|date=July 2016}}

{{vanchor|Types and existence of ultrafilters|Types}}

There are two very different types of ultrafilter: principal and free. A principal (or fixed, or trivial) ultrafilter is a filter containing a least element. Consequently, principal ultrafilters are of the form F'a = {x | a ≤ x} for some (but not all) elements a of the given poset. In this case a is called the principal element of the ultrafilter. Any ultrafilter that is not principal is called a free (or non-principal''') ultrafilter. For ultrafilters on a powerset ℘(S), a principal ultrafilter consists of all subsets of S that contain a given element s of S. Each ultrafilter on ℘(S) that is also a principal filter is of this form.{{rp|187}} Therefore, an ultrafilter U on ℘(S) is principal if and only if it contains a finite set.To see the "if" direction: If {s1,...,s'n} ∈ U, then {s1} ∈ U, or ..., or {s'n} ∈ U by induction on n, using Nr.2 of the (#Special case: ultrafilter on the powerset of a set|above) characterization theorem. That is, some {si} is the principal element of U. If S is infinite, an ultrafilter U on ℘(S) is hence non-principal if and only if it contains the Fréchet filter of cofinite subsets of S.U is non-principal iff it contains no finite set, i.e. (by Nr.3 of the (#Special case: ultrafilter on the powerset of a set|above) characterization theorem) iff it contains every cofinite set, i.e. every member of the Fréchet filter.{{cn|date=July 2016}} If S is finite, each ultrafilter is principal.{{rp|187}}One can show that every filter of a Boolean algebra (or more generally, any subset with the finite intersection property) is contained in an ultrafilter (see Ultrafilter lemma) and that free ultrafilters therefore exist, but the proofs involve the axiom of choice (AC) in the form of Zorn's Lemma. On the other hand, the statement that every filter is contained in an ultrafilter does not imply AC. Indeed, it is equivalent to the Boolean prime ideal theorem (BPIT), a well-known intermediate point between the axioms of Zermelo-Fraenkel set theory (ZF) and the ZF theory augmented by the axiom of choice (ZFC). In general proofs involving the axiom of choice do not produce explicit examples of free ultrafilters, though it is possible to find explicit examples in some models of ZFC; for example, Godel showed that this can be done in the constructible universe where one can write down an explicit global choice function. In ZF without the axiom of choice, it is possible that every ultrafilter is principal.{see p.316, [Halbeisen, L.J.] "Combinatorial Set Theory", Springer 2012}

Applications

Ultrafilters on powersets are useful in topology, especially in relation to compact Hausdorff spaces, and in model theory in the construction of ultraproducts and ultrapowers. Every ultrafilter on a compact Hausdorff space converges to exactly one point. Likewise, ultrafilters on Boolean algebras play a central role in Stone's representation theorem.The set G of all ultrafilters of a poset P can be topologized in a natural way, that is in fact closely related to the above-mentioned representation theorem. For any element a of P, let D'a = {U ∈ G | a ∈ U}. This is most useful when P is again a Boolean algebra, since in this situation the set of all D'a is a base for a compact Hausdorff topology on G. Especially, when considering the ultrafilters on a powerset ℘(S), the resulting topological space is the Stone–Čech compactification of a discrete space of cardinality |S|.The ultraproduct construction in model theory uses ultrafilters to produce elementary extensions of structures. For example, in constructing hyperreal numbers as an ultraproduct of the real numbers, the domain of discourse is extended from real numbers to sequences of real numbers. This sequence space is regarded as a superset of the reals by identifying each real with the corresponding constant sequence. To extend the familiar functions and relations (e.g., + and

- content above as imported from Wikipedia
- "ultrafilter" does not exist on GetWiki (yet)
- time: 2:59pm EDT - Tue, Oct 23 2018
[ this remote article is provided by Wikipedia ]
LATEST EDITS [ see all ]
GETWIKI 09 MAY 2016
GETWIKI 18 OCT 2015
M.R.M. Parrott
Biographies
GETWIKI 20 AUG 2014
GETWIKI 19 AUG 2014
GETWIKI 18 AUG 2014
Wikinfo
Culture
CONNECT