Filter quantifier

From testwiki
Jump to navigation Jump to search

In mathematics, a filter on a set X informally gives a notion of which subsets AβŠ†X are "large". Filter quantifiers are a type of logical quantifier which, informally, say whether or not a statement is true for "most" elements of X. Such quantifiers are often used in combinatorics, model theory (such as when dealing with ultraproducts), and in other fields of mathematical logic where (ultra)filters are used.

Background

Here we will use the set theory convention, where a filter β„± on a set X is defined to be an order-theoretic proper filter in the poset (𝒫(X),βŠ†), that is, a subset of 𝒫(X) such that:

  • βˆ…βˆ‰β„± and Xβˆˆβ„±;
  • For all A,Bβˆˆβ„±, we have A∩Bβˆˆβ„±;
  • For all AβŠ†BβŠ†X, if Aβˆˆβ„± then Bβˆˆβ„±.

Recall a filter β„± on X is an ultrafilter if, for every AβŠ†X, either Aβˆˆβ„± or Xβˆ–Aβˆˆβ„±.

Given a filter β„± on a set X, we say a subset AβŠ†X is β„±-stationary if, for all Bβˆˆβ„±, we have A∩Bβ‰ βˆ….[1]

Definition

Let β„± be a filter on a set X. We define the filter quantifiers βˆ€β„±x and βˆƒβ„±x as formal logical symbols with the following interpretation:

βˆ€β„±x Ο†(x)⟺{x∈X:Ο†(x)}βˆˆβ„±
βˆƒβ„±x Ο†(x)⟺{x∈X:Ο†(x)} is β„±-stationary

for every first-order formula Ο†(x) with one free variable. These also admit alternative definitions as

βˆ€β„±x Ο†(x)⟺βˆƒAβˆˆβ„±  βˆ€x∈A  Ο†(x)
βˆƒβ„±x Ο†(x)⟺βˆ€Aβˆˆβ„±  βˆƒx∈A  Ο†(x)

When β„± is an ultrafilter, the two quantifiers defined above coincide, and we will often use the notation β„±x instead. Verbally, we might pronounce β„±x as "for β„±-almost all x", "for β„±-most x", "for the majority of x (according to β„±)", or "for most x (according to β„±)". In cases where the filter is clear, we might omit mention of β„±.

Properties

The filter quantifiers βˆ€β„±x and βˆƒβ„±x satisfy the following logical identities,[1] for all formulae Ο†,ψ:

  • Duality: βˆ€β„±x Ο†(x)⟺Β¬βˆƒβ„±x Β¬Ο†(x)
  • Weakening: βˆ€x Ο†(x)⟹βˆ€β„±x Ο†(x)⟹βˆƒβ„±x Ο†(x)⟹βˆƒx Ο†(x)
  • Conjunction:
    • βˆ€β„±x (Ο†(x)∧ψ(x))⟺(βˆ€β„±x Ο†(x))∧(βˆ€β„±x Οˆ(x))
    • βˆƒβ„±x (Ο†(x)∧ψ(x))⟹(βˆƒβ„±x Ο†(x))∧(βˆƒβ„±x Οˆ(x))
  • Disjunction:
    • βˆ€β„±x (Ο†(x)∨ψ(x))⟸(βˆ€β„±x Ο†(x))∨(βˆ€β„±x Οˆ(x))
    • βˆƒβ„±x (Ο†(x)∨ψ(x))⟺(βˆƒβ„±x Ο†(x))∨(βˆƒβ„±x Οˆ(x))
  • If β„±βŠ†π’’ are filters on X, then:
    • βˆ€β„±x Ο†(x)⟹βˆ€π’’x Ο†(x)
    • βˆƒβ„±x Ο†(x)βŸΈβˆƒπ’’x Ο†(x)

Additionally, if β„± is an ultrafilter, the two filter quantifiers coincide: βˆ€β„±x Ο†(x)⟺βˆƒβ„±x Ο†(x).Template:Citation needed Renaming this quantifier β„±x, the following properties hold:

  • Negation: β„±x Ο†(x)⟺Β¬β„±x Β¬Ο†(x)
  • Weakening: βˆ€x Ο†(x)⟹β„±x Ο†(x)⟹βˆƒx Ο†(x)
  • Conjunction: β„±x (Ο†(x)∧ψ(x))⟺(β„±x Ο†(x))∧(β„±x Οˆ(x))
  • Disjunction: β„±x (Ο†(x)∨ψ(x))⟺(β„±x Ο†(x))∨(β„±x Οˆ(x))

In general, filter quantifiers do not commute with each other, nor with the usual βˆ€ and βˆƒ quantifiers.Template:Citation needed

Examples

  • If β„±={X} is the trivial filter on X, then unpacking the definition, we have βˆ€β„±x Ο†(x)⟺{x∈X:Ο†(x)}=X, and βˆƒβ„±x Ο†(x)⟺{x∈X:Ο†(x)}∩Xβ‰ βˆ…. This recovers the usual βˆ€ and βˆƒ quantifiers.
  • Let β„±βˆž be the FrΓ©chet filter on an infinite set X, Then, βˆ€β„±βˆžx Ο†(x) holds iff Ο†(x) holds for cofinitely many x∈X, and βˆƒβ„±βˆžx Ο†(x) holds iff Ο†(x) holds for infinitely many x∈X. The quantifiers βˆ€β„±βˆž and βˆƒβ„±βˆž are more commonly denoted βˆ€βˆž and βˆƒβˆž, respectively.
  • Let β„³ be the "measure filter" on [0,1], generated by all subsets AβŠ†[0,1] with Lebesgue measure ΞΌ(A)=1. The above construction gives us "measure quantifiers": βˆ€β„³x Ο†(x) holds iff Ο†(x) holds almost everywhere, and βˆƒβ„³x Ο†(x) holds iff Ο†(x) holds on a set of positive measure.[2]
  • Suppose β„±A is the principal filter on some set AβŠ†X. Then, we have βˆ€β„±Ax Ο†(x)⟺βˆ€x∈A Ο†(x), and βˆƒβ„±Ax Ο†(x)⟺βˆƒx∈A Ο†(x).
    • If 𝒰d is the principal ultrafilter of an element d∈X, then we have 𝒰dx Ο†(x)⟺Ο†(d).

Use

The utility of filter quantifiers is that they often give a more concise or clear way to express certain mathematical ideas. For example, take the definition of convergence of a real-valued sequence: a sequence (an)nβˆˆβ„•βŠ†β„ converges to a point aβˆˆβ„ if

βˆ€Ξ΅>0  βˆƒNβˆˆβ„•  βˆ€nβˆˆβ„• ( nβ‰₯N⟹|anβˆ’a|<Ξ΅ )

Using the FrΓ©chet quantifier βˆ€βˆž as defined above, we can give a nicer (equivalent) definition:

βˆ€Ξ΅>0  βˆ€βˆžnβˆˆβ„•: |anβˆ’a|<Ξ΅

Filter quantifiers are especially useful in constructions involving filters. As an example, suppose that X has a binary operation + defined on it. There is a natural way to extend[3] + to Ξ²X, the set of ultrafilters on X:[4]

π’°βŠ•π’±={AβŠ†X: π’°x π’±y  x+y∈A}

With an understanding of the ultrafilter quantifier, this definition is reasonably intuitive. It says that π’°βŠ•π’± is the collection of subsets AβŠ†X such that, for most x (according to 𝒰) and for most y (according to 𝒱), the sum x+y is in A. Compare this to the equivalent definition without ultrafilter quantifiers:

π’°βŠ•π’±={AβŠ†X: {x∈X: {y∈X: x+y∈A}βˆˆπ’±}βˆˆπ’°}

The meaning of this is much less clear.

This increased intuition is also evident in proofs involving ultrafilters. For example, if + is associative on X, using the first definition of βŠ•, it trivially follows that βŠ• is associative on Ξ²X. Proving this using the second definition takes a lot more work.[5]

See also

References

Template:Reflist

  1. ↑ 1.0 1.1 Template:Cite web
  2. ↑ Template:Cite web
  3. ↑ This is an extension of + in the sense that we can consider X as a subset of Ξ²X by mapping each x∈X to the principal ultrafilter 𝒰x on x. Then, we have 𝒰xβŠ•π’°y=𝒰(x+y).
  4. ↑ Template:Cite web
  5. ↑ Template:Cite book
Retrieved from "https://en.wiki.beta.math.wmflabs.org/w/index.php?title=Filter_quantifier&oldid=44498"