Generic filter
Encyclopedia
In the mathematical field of set theory
, a generic filter is a kind of object used in the theory of forcing
, a technique used for many purposes, but especially to establish the independence
of certain propositions from certain formal theories, such as ZFC. For example, Paul Cohen
used the method to establish that ZFC, if consistent, cannot prove the continuum hypothesis
, which states that there are exactly aleph-one real number
s. In the contemporary re-interpretation of Cohen's proof, it proceeds by constructing a generic filter that codes more than
reals, without changing the value of 
.
Formally, let P be a poset (partially ordered set), and let F be a filter
on P; that is, F is a subset of P such that:
Now if D is a collection of dense
open
subsets of P, in the topology whose basic open sets are all sets of the form {q|q≤p} for particular p in P, then F is said to be D-generic if F meets all sets in D; that is,
for all E ∈ D
Similarly, if M is a transitive
model
of ZFC (or some sufficient fragment thereof), with P an element of M, then F is said to be M-generic, or sometimes generic over M, if F meets all dense open subsets of P that are elements of M.
Set theory
Set theory is the branch of mathematics that studies sets, which are collections of objects. Although any type of object can be collected into a set, set theory is applied most often to objects that are relevant to mathematics...
, a generic filter is a kind of object used in the theory of forcing
Forcing (mathematics)
In the mathematical discipline of set theory, forcing is a technique invented by Paul Cohen for proving consistency and independence results. It was first used, in 1963, to prove the independence of the axiom of choice and the continuum hypothesis from Zermelo–Fraenkel set theory...
, a technique used for many purposes, but especially to establish the independence
Independence (mathematical logic)
In mathematical logic, independence refers to the unprovability of a sentence from other sentences.A sentence σ is independent of a given first-order theory T if T neither proves nor refutes σ; that is, it is impossible to prove σ from T, and it is also impossible to prove from T that...
of certain propositions from certain formal theories, such as ZFC. For example, Paul Cohen
Paul Cohen (mathematician)
Paul Joseph Cohen was an American mathematician best known for his proof of the independence of the continuum hypothesis and the axiom of choice from Zermelo–Fraenkel set theory, the most widely accepted axiomatization of set theory.-Early years:Cohen was born in Long Branch, New Jersey, into a...
used the method to establish that ZFC, if consistent, cannot prove the continuum hypothesis
Continuum hypothesis
In mathematics, the continuum hypothesis is a hypothesis, advanced by Georg Cantor in 1874, about the possible sizes of infinite sets. It states:Establishing the truth or falsehood of the continuum hypothesis is the first of Hilbert's 23 problems presented in the year 1900...
, which states that there are exactly aleph-one real number
Real number
In mathematics, a real number is a value that represents a quantity along a continuum, such as -5 , 4/3 , 8.6 , √2 and π...
s. In the contemporary re-interpretation of Cohen's proof, it proceeds by constructing a generic filter that codes more than
reals, without changing the value of .Formally, let P be a poset (partially ordered set), and let F be a filter
Filter (mathematics)
In mathematics, a filter is a special subset of a partially ordered set. A frequently used special case is the situation that the ordered set under consideration is just the power set of some set, ordered by set inclusion. Filters appear in order and lattice theory, but can also be found in...
on P; that is, F is a subset of P such that:
- F is nonempty
- If p,q∈P and p≤q and p is an element of F, then q is an element of F (F is closed upward)
- If p and q are elements of F, then there is an element r of F such that r≤p and r≤q (any two elements of F are compatible)
Now if D is a collection of dense
Dense set
In topology and related areas of mathematics, a subset A of a topological space X is called dense if any point x in X belongs to A or is a limit point of A...
open
Open set
The concept of an open set is fundamental to many areas of mathematics, especially point-set topology and metric topology. Intuitively speaking, a set U is open if any point x in U can be "moved" a small amount in any direction and still be in the set U...
subsets of P, in the topology whose basic open sets are all sets of the form {q|q≤p} for particular p in P, then F is said to be D-generic if F meets all sets in D; that is,
for all E ∈ DSimilarly, if M is a transitive
Transitive set
In set theory, a set A is transitive, if* whenever x ∈ A, and y ∈ x, then y ∈ A, or, equivalently,* whenever x ∈ A, and x is not an urelement, then x is a subset of A....
model
Model theory
In mathematics, model theory is the study of mathematical structures using tools from mathematical logic....
of ZFC (or some sufficient fragment thereof), with P an element of M, then F is said to be M-generic, or sometimes generic over M, if F meets all dense open subsets of P that are elements of M.