avewright/proofwiki-math huggingface dataset:
Theorem: Negated Upper Index of Binomial Coefficient

:$\dbinom r k = \paren {-1}^k \dbinom {k - r - 1} k$

Proof:
{{begin-eqn}}
{{eqn | l = \binom {-r} k
      | r = \frac {\paren {-r}^{\underline k} } {k!}
      | c = {{Defof|Binomial Coefficient}}
}}
{{eqn | r = \frac {-r \paren {-r - 1} \paren {-r - 2} \dotsm \paren {-r - k + 1} } {k!}
      | c = 
}}
{{eqn | r = \paren {-1}^k \frac {\paren r \paren {r + 1} \paren {r + 2} \dotsm \paren {r + k - 1} }{k!}
      | c = 
}}
{{eqn | r = \paren {-1}^k \frac {\paren {r + k - 1} \paren {r + k - 2} \paren {r + k - 3} \dotsm \paren {r + k - k} } {k!}
      | c = reversing the order
}}
{{eqn | r = \paren {-1}^k \frac {\paren {r + k - 1} \paren {r + k - 2} \paren {r + k - 3} \dotsm \paren {r + k - 1 - \paren {k - 1} } } {k!}
      | c = 
}}
{{eqn | r = \paren {-1}^k \binom {r + k - 1} k
      | c = 
}}
{{end-eqn}}
{{qed}}
Theorem: Alternating Sum and Difference of r Choose k up to n

:$\ds \sum_{k \mathop \le n} \paren {-1}^k \binom r k = \paren {-1}^n \binom {r - 1} n$

Proof:
{{begin-eqn}}
{{eqn | l = \sum_{k \mathop \le n} \paren {-1}^k \binom r k
      | r = \sum_{k \mathop \le n} \binom {k - r - 1} k
      | c = Negated Upper Index of Binomial Coefficient
}}
{{eqn | r = \binom {-r + n} n
      | c = Sum of r+k Choose k up to n
}}
{{eqn | r = \paren {-1}^n \binom {r - 1} n
      | c = Negated Upper Index of Binomial Coefficient
}}
{{end-eqn}}
{{qed}}
Theorem: Alternating Sum and Difference of r Choose k up to n

:$\ds \sum_{k \mathop \le n} \paren {-1}^k \binom r k = \paren {-1}^n \binom {r - 1} n$

Proof:
The proof proceeds by induction.
For all $n \in \Z_{\ge 0}$, let $\map P n$ be the proposition:
:$\ds \sum_{k \mathop \le n} \paren {-1}^k \binom r k = \paren {-1}^n \binom {r - 1} n$
$\map P 0$ is the case:
{{begin-eqn}}
{{eqn | l = \sum_{k \mathop \le 0} \paren {-1}^k \binom r k
      | r = \paren {-1}^0 \binom r 0
      | c = 
}}
{{eqn | r = 1
      | c = Binomial Coefficient with Zero
}}
{{eqn | r = \paren {-1}^n \binom {r - 1} 0
      | c = Binomial Coefficient with Zero
}}
{{end-eqn}}
Thus $\map P 0$ is seen to hold.
=== Basis for the Induction ===
$\map P 1$ is the case:
{{begin-eqn}}
{{eqn | l = \sum_{k \mathop \le 1} \paren {-1}^k \binom r k
      | r = \paren {-1}^0 \binom r 0 + \paren {-1}^1 \binom r 1
      | c = 
}}
{{eqn | r = 1 - r
      | c = Binomial Coefficient with Zero, Binomial Coefficient with One
}}
{{eqn | r = \paren {-1}^1 \binom {r - 1} 1
      | c = Binomial Coefficient with One
}}
{{end-eqn}}
Thus $\map P 1$ is seen to hold.
This is the basis for the induction.
=== Induction Hypothesis ===
Now it needs to be shown that, if $\map P m$ is true, where $m \ge 1$, then it logically follows that $\map P {m + 1}$ is true.
So this is the induction hypothesis:
:$\ds \sum_{k \mathop \le m} \paren {-1}^k \binom r k = \paren {-1}^m \binom {r - 1} m$
from which it is to be shown that:
:$\ds \sum_{k \mathop \le m + 1} \paren {-1}^k \binom r k = \paren {-1}^{m + 1} \binom {r - 1} {m + 1}$
=== Induction Step ===
This is the induction step:
{{begin-eqn}}
{{eqn | l = \sum_{k \mathop \le m + 1} \paren {-1}^k \binom r k
      | r = \sum_{k \mathop \le m} \paren {-1}^k \binom r k + \paren {-1}^{m + 1} \binom r {m + 1}
      | c = {{Defof|Summation}}
}}
{{eqn | r = \paren {-1}^m \binom {r - 1} m + \paren {-1}^{m + 1} \binom r {m + 1}
      | c = 
}}
{{eqn | r = \paren {-1}^{m + 1} \paren {\binom r {m + 1} - \binom {r - 1} m }
      | c = 
}}
{{eqn | r = \paren {-1}^{m + 1} \binom {r - 1} {m + 1}
      | c = Pascal's Rule
}}
{{end-eqn}}
So $\map P m \implies \map P {m + 1}$ and the result follows by the Principle of Mathematical Induction.
Therefore:
:$\forall n \in \Z_{\ge 0}: \ds \sum_{k \mathop \le n} \paren {-1}^k \binom r k = \paren {-1}^n \binom {r - 1} n$
Theorem: Product of r Choose m with m Choose k

:$\dbinom r m \dbinom m k = \dbinom r k \dbinom {r - k} {m - k}$

Proof:
=== Integral Index ===
Let $r \in \Z$.
Then:
{{begin-eqn}}
{{eqn | l = \binom r m \binom m k
      | r = \frac {r^{\underline m} } {m!} \frac {m^{\underline k} } {k!}
      | c = 
}}
{{eqn | r = \frac {r! m!} {m! \paren {r - m}! k! \paren {m - k}!}
      | c = 
}}
{{eqn | r = \frac {r! \paren {r - k}!} {k! \paren {r - k}! \paren {m - k}! \paren {r - m}!}
      | c = 
}}
{{eqn | r = \binom r k \binom {r - k} {m - k}
      | c = 
}}
{{end-eqn}}
{{qed|lemma}}
=== Real Index ===
Both sides of the above equation are polynomials in $r$.
Since these polynomials agree for all $r \in \Z$, they must agree for all $r \in \R$.
{{qed}}
Theorem: Product of r Choose m with m Choose k

:$\dbinom r m \dbinom m k = \dbinom r k \dbinom {r - k} {m - k}$

Proof:
Consider the trinomial coefficient:
:$\dbinom r {k, m - k, r - m}$
We use Multinomial Coefficient expressed as Product of Binomial Coefficients:
:$\dbinom {k_1 + k_2 + k_3} {k_1, k_2, k_3} = \dbinom {k_1 + k_2} {k_1} \dbinom {k_1 + k_2 + k_3} {k_1 + k_2}$
and substitute as appropriate for $k_1, k_2, k_3$.
We have:
{{begin-eqn}}
{{eqn | r = \dbinom r {k, m - k, r - m}
      | o = 
      | c = 
}}
{{eqn | r = \dbinom {\paren {m - k} + \paren {r - m} + k} {m - k, r - m, k}
      | c = 
}}
{{eqn | r = \dbinom {\paren {m - k} + \paren {r - m} } {m - k} \dbinom {\paren {m - k} + \paren {r - m} + k} {\paren {m - k} + \paren {r - m} }
      | c = Multinomial Coefficient expressed as Product of Binomial Coefficients
}}
{{eqn | r = \dbinom {r - k} {m - k} \dbinom r m
      | c = 
}}
{{end-eqn}}
Similarly:
{{begin-eqn}}
{{eqn | r = \dbinom r {k, m - k, r - m}
      | o = 
      | c = 
}}
{{eqn | r = \dbinom {k + \paren {m - k} + \paren {r - m} } {k, m - k, r - m}
      | c = 
}}
{{eqn | r = \dbinom {k + \paren {m - k} } k \dbinom {k + \paren {m - k} + \paren {r - m} } {\paren {m - k} + k}
      | c = Multinomial Coefficient expressed as Product of Binomial Coefficients
}}
{{eqn | r = \dbinom m k \dbinom r m
      | c = 
}}
{{end-eqn}}
{{qed}}
The result follows on equating the two expressions.
Theorem: Chu-Vandermonde Identity

{{begin-eqn}}
{{eqn | l = \sum_{k \mathop = 0}^n \binom r k \binom s {n - k}
      | r = \binom r 0 \binom s n + \binom r 1 \binom s {n - 1} + \binom r 2 \binom s {n - 2} + \cdots + \binom r n \binom s 0
      | c = 
}}
{{eqn | r = \binom {r + s} n
      | c = 
}}
{{end-eqn}}

Proof:
From the Chu-Vandermonde Identity:
{{:Chu-Vandermonde Identity}}
The result follows on setting $r = e$, $s = \pi$ and $n = 2$.
{{qed}}
Theorem: Chu-Vandermonde Identity

{{begin-eqn}}
{{eqn | l = \sum_{k \mathop = 0}^n \binom r k \binom s {n - k}
      | r = \binom r 0 \binom s n + \binom r 1 \binom s {n - 1} + \binom r 2 \binom s {n - 2} + \cdots + \binom r n \binom s 0
      | c = 
}}
{{eqn | r = \binom {r + s} n
      | c = 
}}
{{end-eqn}}

Proof:
{{begin-eqn}}
{{eqn | l = \binom {e + \pi} 2
      | r = \dfrac {\paren {e + \pi} \times \paren {e + \pi - 1} } {2 \times 1}
      | c = {{Defof|Binomial Coefficient}}
}}
{{eqn | r = \dfrac 1 2 \paren {\paren {e + \pi}^2 - \paren {e + \pi} }
      | c = multiplying out
}}
{{eqn | r = \dfrac 1 2 \paren {e^2 + 2e\pi + \pi^2 - e - \pi}
      | c = simplifying
}}
{{end-eqn}}
{{begin-eqn}}
{{eqn | l = \sum_{k \mathop = 0}^2 \binom e k \binom \pi {2 - k}
      | r = \binom e 0 \binom {\pi} 2 + \binom e 1 \binom {\pi} 1 + \binom e 2 \binom {\pi} 0
      | c = {{Defof|Summation}}
}}
{{eqn | r = 1 \times \dfrac {\paren {\pi} \paren {\pi - 1} } 2 + e \times \pi + \dfrac {\paren {e} \paren {e - 1} } 2 \times 1
      | c = {{Defof|Binomial Coefficient}}
}}
{{eqn | r = \dfrac 1 2 \paren {\pi^2 - \pi + 2e\pi + e^2 - e}
      | c = simplifying
}}
{{eqn | r = \dfrac 1 2 \paren {e^2 + 2e\pi + \pi^2 - e - \pi}
      | c = rearranging
}}
{{eqn | r = \binom {e + \pi} 2
      | c = from above
}}
{{end-eqn}}
{{qed}}
Theorem: Chu-Vandermonde Identity

{{begin-eqn}}
{{eqn | l = \sum_{k \mathop = 0}^n \binom r k \binom s {n - k}
      | r = \binom r 0 \binom s n + \binom r 1 \binom s {n - 1} + \binom r 2 \binom s {n - 2} + \cdots + \binom r n \binom s 0
      | c = 
}}
{{eqn | r = \binom {r + s} n
      | c = 
}}
{{end-eqn}}

Proof:
From the Chu-Vandermonde Identity:
{{:Chu-Vandermonde Identity}}
The result follows on setting $r = 4$, $s = 5$ and $n = 3$.
{{qed}}
Theorem: Chu-Vandermonde Identity

{{begin-eqn}}
{{eqn | l = \sum_{k \mathop = 0}^n \binom r k \binom s {n - k}
      | r = \binom r 0 \binom s n + \binom r 1 \binom s {n - 1} + \binom r 2 \binom s {n - 2} + \cdots + \binom r n \binom s 0
      | c = 
}}
{{eqn | r = \binom {r + s} n
      | c = 
}}
{{end-eqn}}

Proof:
{{begin-eqn}}
{{eqn | l = \binom 9 3
      | r = \binom {4 + 5} 3
      | c = 
}}
{{eqn | r = \dfrac {9!} {3! \times 6!}
      | c = {{Defof|Binomial Coefficient}}
}}
{{eqn | r = \dfrac {9 \times 8 \times 7} {3 \times 2 \times 1}
      | c = {{Defof|Factorial}}
}}
{{eqn | r = 84
      | c = 
}}
{{end-eqn}}
{{qed|lemma}}
{{begin-eqn}}
{{eqn | l = \sum_{k \mathop = 0}^3 \binom 4 k \binom 5 {3 - k}
      | r = \binom 4 0 \binom 5 3 + \binom 4 1 \binom 5 2 + \binom 4 2 \binom 5 1 + \binom 4 3 \binom 5 0
      | c = {{Defof|Summation}}
}}
{{eqn | r = \dfrac {4!} {0! \times 4!} \times \dfrac {5!} {3! \times 2!} + \dfrac {4!} {1! \times 3!} \times \dfrac {5!} {2! \times 3!} + \dfrac {4!} {2! \times 2!} \times \dfrac {5!} {1! \times 4!} + \dfrac {4!} {3! \times 1!} \times \dfrac {5!} {0! \times 5!}
      | c = {{Defof|Binomial Coefficient}}
}}
{{eqn | r = 1 \times \dfrac {5 \times 4} {2 \times 1} + \dfrac 4 1 \times \dfrac {5 \times 4} {2 \times 1} + \dfrac {4 \times 3} {2 \times 1} \times \dfrac 5 1 + \dfrac 4 1 \times 1
      | c = {{Defof|Factorial}}
}}
{{eqn | r = 1 \times 10 + 4 \times 10 + 6 \times 5 + 4 \times 1
      | c = 
}}
{{eqn | r = 10 + 40 + 30 + 4
      | c = 
}}
{{eqn | r = 84
      | c = 
}}
{{end-eqn}}
{{qed}}
Theorem: Chu-Vandermonde Identity

{{begin-eqn}}
{{eqn | l = \sum_{k \mathop = 0}^n \binom r k \binom s {n - k}
      | r = \binom r 0 \binom s n + \binom r 1 \binom s {n - 1} + \binom r 2 \binom s {n - 2} + \cdots + \binom r n \binom s 0
      | c = 
}}
{{eqn | r = \binom {r + s} n
      | c = 
}}
{{end-eqn}}

Proof:
{{begin-eqn}}
{{eqn | l = \sum_{n \mathop = 0}^{r + s} \binom {r + s} n x^n
      | r = \paren {1 + x}^{r + s}
      | c = Binomial Theorem for Integral Index
}}
{{eqn | r = \paren {1 + x}^r \paren {1 + x}^s
      | c = Exponent Combination Laws
}}
{{eqn | r = \sum_{k \mathop = 0}^r \binom r k x^k \sum_{k \mathop = 0}^s \binom s k x^k
      | c = Binomial Theorem for Integral Index
}}
{{eqn | r = \sum_{n \mathop = 0}^{r + s} \paren {\sum_{k \mathop = 0}^n \binom r k \binom  s {n - k} } x^n
      | c = Product of Absolutely Convergent Series
}}
{{end-eqn}}
Therefore:
:$\ds \binom {r + s} n = \sum_{k \mathop = 0}^n \binom r k \binom s {n - k}$
{{qed}}
Theorem: Chu-Vandermonde Identity

{{begin-eqn}}
{{eqn | l = \sum_{k \mathop = 0}^n \binom r k \binom s {n - k}
      | r = \binom r 0 \binom s n + \binom r 1 \binom s {n - 1} + \binom r 2 \binom s {n - 2} + \cdots + \binom r n \binom s 0
      | c = 
}}
{{eqn | r = \binom {r + s} n
      | c = 
}}
{{end-eqn}}

Proof:
From Sum over $k$ of $\dbinom {r - t k} k \dbinom {s - t \paren{n - k}} {n - k} \dfrac r {r - t k}$:
{{:Sum over k of r-tk Choose k by s-t(n-k) Choose n-k by r over r-tk}}
where $r, s, t \in \R, n \in \Z$.
Setting $t = 0$:
:$\ds \sum_{k \mathop \ge 0} \binom r k \binom s {n - k} = \binom {r + s} n$
which is the result required.
{{qed}}
Theorem: Lucas' Theorem

Let $p$ be a prime number.
Let $n, k \in \Z_{\ge 0}$.
Then:
:$\dbinom n k \equiv \dbinom {\floor {n / p} } {\floor {k / p} } \dbinom {n \bmod p} {k \bmod p} \pmod p$
where:
:$\dbinom n k$ denotes a binomial coefficient
:$n \bmod p$ denotes the modulo operation
:$\floor \cdot$ denotes the floor function.

Proof:
First we show that:
:$\dbinom n k \equiv \dbinom {\floor {n / p} } {\floor {k / p} } \dbinom {n \bmod p} {k \bmod p} \pmod p$
Consider $\dbinom n k$ as the fraction:
:$\dfrac {n \paren {n - 1} \paren {n - 2} \cdots \paren {n - k + 1} } {k \paren {k - 1} \paren {k - 2} \cdots 1}$
This can be expressed as:
:$(1): \quad \dbinom n k = \paren {\dfrac n k} \paren {\dfrac {n - 1} {k - 1} } \paren {\dfrac {n - 2} {k - 2} } \cdots \paren {\dfrac {n - k + 1} 1}$
Let $k = s p + t$ from the Division Theorem.
Thus:
: $t = k \bmod p$
The denominators of the first $t$ factors in $(1)$ do not have $p$ as a divisor.
Now let $n = u p + v$, again from the Division Theorem.
Thus:
:$v = n \bmod p$
Now, when dealing with non-multiples of $p$, we can work modulo $p$ in both the numerator and denominator, from Common Factor Cancelling in Congruence.
So we consider the first $t$ factors of $(1)$ modulo $p$.
These are:
:$\paren {\dfrac {u p + v} {s p + t} } \paren {\dfrac {u p + v - 1} {s p + t - 1} } \cdots \paren {\dfrac {u p + v - t + 1} {s p + 1} } \equiv \paren {\dfrac v t} \paren {\dfrac {v - 1} {t - 1} } \cdots \paren {\dfrac {v - t + 1} 1} \pmod p$
So, these first $t$ terms of $(1)$ taken together are congruent modulo $p$ to the corresponding terms of:
:$\dbinom {n \bmod p} {k \bmod p}$
These differ by multiples of $p$.
So we are left with $k - k \bmod p$ factors.
These fall into $\floor {k / p}$ groups, each of which has $p$ consecutive values.
Each of these groups contains exactly one multiple of $p$.
The other $p - 1$ factors in a given group are congruent (modulo $p$) to $\paren {p - 1}!$ so they cancel out in numerator and denominator.
We now need to investigate the $\left \lfloor {k / p} \right \rfloor$ multiples of $p$ in the numerator and denominator.
We divide each of them by $p$ and we are left with the binomial coefficient:
:$\dbinom {\floor {\paren {n - k \bmod p} / p} } {\floor {k / p} }$
Now, if $k \bmod p \le n \bmod p$, this equals:
:$\dbinom {\floor {n / p} } {\floor {k / p} }$
Otherwise, if $k \bmod p > n \bmod p$, the other factor:
:$\dbinom {n \bmod p} {k \bmod p}$
is zero.
So the formula holds in general.
{{qed}}
{{Namedfor|François Édouard Anatole Lucas|cat = Lucas}}
Theorem: Equivalence of Definitions of Congruence

{{TFAE|def = Congruence (Number Theory)|view = Congruence|context = Number Theory}}
Let $z \in \R$.

Proof:
Let $x_1, x_2, z \in \R$.
Let $x_1 \equiv x_2 \pmod z$ as defined by an equivalence relation.
That is, let $\RR_z$ be the relation on the set of all $x, y \in \R$:
:$\RR_z = \set {\tuple {x, y} \in \R \times \R: \exists k \in \Z: x = y + k z}$
Let $\tuple {x_1, x_2} \in \RR_z$.
Then by definition, $\exists k \in \Z: x_1 = x_2 + k z$.
So, by definition of the modulo operation, we have:
{{begin-eqn}}
{{eqn | l = x_1 \bmod z
      | r = \paren {x_2 + k z} - z \floor {\frac {x_2 + kz} z}
      | c = 
}}
{{eqn | r = \paren {x_2 + k z} - z \floor {\frac {x_2} z + k}
      | c = 
}}
{{eqn | r = \paren {x_2 + k z} - z \floor {\frac {x_2} z} + k z
      | c = 
}}
{{eqn | r = x_2 - z \floor {\frac {x_2} z}
      | c = 
}}
{{eqn | r = x_2 \bmod z
      | c = 
}}
{{end-eqn}}
So:
:$x_1 \equiv x_2 \pmod z$
in the sense of definition by modulo operation.
{{qed|lemma}}
Now let $x_1 \equiv x_2 \pmod z$ in the sense of definition by modulo operation.
That is, :$x_1 \equiv x_2 \pmod z \iff x_1 \bmod z = x_2 \bmod z$.
Let $z = 0$.
Then by definition, $x_1 \bmod 0 = x_1$ and $x_2 \bmod 0 = x_2$.
So as $x_1 \bmod 0 = x_2 \bmod 0$ we have that $x_1 = x_2$.
So $x_1 - x_2 = 0 = 0.z$ and so $x_1 \equiv x_2 \pmod z$ in the sense of definition by integer multiple.
Now suppose $z \ne 0$.
Then from definition of the modulo operation:
:$x_1 \bmod z = x_1 - z \floor {\dfrac {x_1} z}$
:$x_2 \bmod z = x_2 - z \floor {\dfrac {x_2} z}$
Thus:
:$x_1 - z \floor {\dfrac {x_1} z} = x_2 - z \floor {\dfrac {x_2} z}$
and so:
:$x_1 - x_2 = z \paren {\floor {\dfrac {x_1} z} - \floor {\dfrac {x_2} z} }$
From the definition of the floor function, we see that both $\floor {\dfrac {x_1} z}$ and $\floor {\dfrac {x_2} z}$ are integers.
Therefore, so is $\floor {\dfrac {x_1} z} - \floor {\dfrac {x_2} z}$ an integer.
So $\exists k \in \Z: x_1 - x_2 = k z$.
Thus $x_1 - x_2 = k z$ and:
:$x_1 \equiv x_2 \pmod z$
in the sense of definition by integer multiple.
{{qed|lemma}}
Now let $x_1 \equiv x_2 \pmod z$ in the sense of definition by integer multiple.
That is, $\exists k \in \Z: x_1 - x_2 = k z$.
Then $x_1 = x_2 + k z$ and so $\tuple {x_1, x_2} \in \RR_z$ where:
:$\RR_z = \set {\tuple {x, y} \in \R \times \R: \exists k \in \Z: x = y + k z}$
and so
:$x_1 \equiv x_2 \pmod z$
in the sense of definition by equivalence relation.
{{qed|lemma}}
So all three definitions are equivalent: $(1) \implies (2) \implies (3) \implies (1)$.
{{qed}}
Theorem: Congruence Modulo Real Number is Equivalence Relation

For all $z \in \R$, congruence modulo $z$ is an equivalence relation.

Proof:
Checking in turn each of the criteria for equivalence:
Theorem: Congruence Modulo Zero is Diagonal Relation

Congruence modulo zero is the diagonal relation.
That is:
:$x \equiv y \pmod 0 \iff x = y$

Proof:
Follows directly from the definition of congruence:
:$x \equiv y \pmod z \iff x \bmod z = y \bmod z$ 
When $z = 0$ we have by definition:
:$x \bmod 0 := x$
And so $x \bmod 0 = y \bmod 0 \iff x = y$.
Hence the result.
{{qed}}
Category:Modulo Arithmetic
cekrtgnb3larl48i6x3esxn6kisvbjy
Theorem: Filter Basis Generates Filter

Let $S$ be a set.
Let $\powerset S$ be the power set of $S$.
Let $\BB \subset \powerset S$.
Then:
:$\FF = \set {V \subseteq S: \exists U \in \BB: U \subseteq V}$ is a filter on $S$
{{iff}}:
:$(1): \quad \forall V_1, V_2 \in \BB: \exists U \in \BB: U \subseteq V_1 \cap V_2$
:$(2): \quad \O \notin \BB, \BB \ne \O$
That is, $\BB$ is a filter basis of the filter $\FF$, which is generated by $\BB$.

Proof:
Assume first that $\FF$ is a filter on $S$.
Then $S \in \FF$ and thus $\BB \ne \O$.
Because $\O \notin \FF$ we have that $\O \notin \BB$, since $\BB \subseteq \FF$.
Let $V_1, V_2 \in \BB$.
Then:
:$V_1, V_2 \in \FF$
Because $\FF$ is a filter:
:$V := V_1 \cap V_2 \in \FF$
The definition of $\FF$ implies therefore that there is $U \in \BB$ such that $U \subseteq V = V_1 \cap V_2$.
{{qed|lemma}}
Assume now that $\BB$ satisfies conditions $(1)$ and $(2)$.
To show that $\FF$ is a filter, note that because $\BB \ne \O$ there is a $B \in \BB$.
Because $\BB \subset \powerset S$:
:$B \subseteq S$
and thus by the definition of filter:
:$S \in \FF$
Because:
:the only subset of $\O$ is $\O$
and:
:since $\O \notin \BB$
it follows that:
:$\O \notin \FF$
Let $V_1, V_2 \in \FF$.
Then there exist $U_1, U_2 \in \BB$ such that $U_1 \subseteq V_1$ and $U_2 \subseteq V_2$.
Because $\BB$ satisfies condition $(1)$ there exists a set $U \in \BB$ for which $U \subseteq U_1 \cap U_2$ holds.
Because $U_1 \cap U_2 \subseteq V_1 \cap V_2$ this implies that:
:$U \subseteq V_1 \cap V_2$
and therefore:
:$V_1 \cap V_2 \in \FF$
{{qed}}
Theorem: Adherent Point of Filter iff Superfilter Converges

Let $T = \struct {S, \tau}$ be a topological space.
Let $\FF$ be a filter on $S$.
Let $x \in S$.
Then $x$ is a adherent point of $\FF$ {{iff}} there exists a superfilter $\FF'$ of $\FF$ on $S$ which converges to $x$.

Proof:
Let $x$ be a adherent point of $\FF$.
Define:
:$\BB := \set {F \cap U : F \in \FF \text{ and } U \text{ is a neighborhood of } x}$
Then $\BB$ is filter basis by definition.
Let $\FF'$ be the corresponding generated filter.
By construction we have $\FF \subseteq \FF'$ and $U \in \FF'$ for every neighborhood $U$ of $x$.
Thus $\FF'$ converges to $x$.
{{qed|lemma}}
Let there be a filter $\FF'$ on $X$ satisfying $\FF \subseteq \FF'$ which converges to $x$.
Let $U \subseteq X$ be a neighborhood of $x$.
Let $F \in \FF$.
Then:
:$U, F \in \FF'$
and therefore:
: $U \cap F \in \FF'$
Because $\O \notin \FF'$ it follows that:
: $U \cap F \ne \O$
This holds for any neighborhood $U$ of $x$.
Hence $x$ is a adherent point of $F$.
Therefore:
:$x \in \overline F$
Because this holds for all $F \in \FF$:
:$\ds x \in \bigcap_{F \mathop \in \FF} \overline F$
and so $x$ is a adherent point of $\FF$.
{{qed}}
Category:Adherent Points of Filters
Category:Filter Theory
tgzzm23890cwdjt7ownk9qzttnz88dr
Theorem: Ultrafilter Lemma

Let $S$ be a set.
Every filter on $S$ is contained in an ultrafilter on $S$.

Proof:
Let $\Omega$ be the set of filters on $S$.
From Subset Relation is Ordering, the subset relation makes $\struct {\Omega, \subseteq}$ a partially ordered set.
Let $C \subseteq \Omega$ be a non-empty chain.
Then $\bigcup C$ is again a filter on $S$.
Thus $\bigcup C$ is an upper bound of $C$.
Indeed, if $A, B \in \bigcup C$ then there there are filters $\FF, \FF' \in C$ with $A \in \FF$ and $B \in \FF'$.
We have that $C$ is a chain.
{{WLOG}}, let $\FF \subset \FF'$.
Thus $A \in \FF'$.
Hence:
:$A \cap B \in \FF'$
In particular:
:$A, B \in \bigcup C$
For any $\FF \in \Omega$ there is therefore by Zorn's Lemma a maximal element $\FF'$ such that:
:$\FF \subseteq \FF'$
The maximality of $\FF'$ is in this context equivalent to $\FF'$ being an ultrafilter.
{{qed}}
Theorem: Ultrafilter Lemma

Let $S$ be a set.
Every filter on $S$ is contained in an ultrafilter on $S$.

Proof:
Let $\FF$ be a filter on $S$.
Let the power set of $S$ be ordered by inclusion.
Then, by Filter on Set is Proper Filter, $\FF$ is a proper filter on $\powerset S$.
By Filter is Ideal in Dual Ordered Set, $\FF$ is an ideal in the dual of $\powerset S$.
By Singleton of Bottom is Ideal, $\set \O$ is an ideal in $\powerset S$.
By Ideal is Filter in Dual Ordered Set, $\set \O$ is a filter on the dual of $\powerset S$.
By the definition of Filter on Set, $\O \notin \FF$, so $\FF$ and $\set \O$ are disjoint.
Therefore, by the Boolean Prime Ideal Theorem, there is a prime ideal $\GG \supseteq \FF$ that is disjoint from $\set \O$.
By Prime Ideal is Prime Filter in Dual Lattice, $\GG$ is a prime filter on the dual of the dual of $\powerset S$.
Thus, $\GG$ is a prime filter on $\powerset S$ by Dual of Dual Ordering.
But $\GG$ is disjoint from $\set \O$, which implies that $\O \notin \GG$.
Therefore, $\GG$ is a proper filter.
Thus, by Proper and Prime iff Ultrafilter in Boolean Lattice, $\GG$ is an ultrafilter on $\powerset S$.
But by comparing the definitions, $\GG$ is thus an ultrafilter on $S$.
{{qed}}
Theorem: Generated Topology is a Topology

Let $X$ be a set.
Let $\SS \subseteq \powerset X$, where $\powerset X$ is the power set of $X$.
Let $\TT_\SS$ be the generated topology for $\SS$.
Then $\TT_\SS$ is a topology on $X$.

Proof:
We show that $\SS^* = \set {\bigcap S: S \subseteq \SS \text{ finite} }$ (cf. the definition of the generated topology) is a basis.
By definition of synthetic basis, we need to prove:
:$(1): \quad X = \bigcup \SS^*$
:$(2): \quad$ For any $U_1, U_2 \in \SS^*$ and $x \in U_1 \cap U_2$ there is a $U \in \SS^*$ such that $x \in U \subseteq U_1 \cap U_2$
First note that $X = \bigcap \O \in \SS^*$ and therefore $\bigcup \SS^* = X$.
Additionally, if $U_1, U_2 \in \SS^*$, then there exist finite sets $S_1, S_2 \subseteq \SS$ such that $U_1 = \bigcap S_1$ and $U_2 = \bigcap S_2$ by the definition of $\SS^*$.
Thus we have:
:$U_1 \cap U_2 = \bigcap \paren {S_1 \cup S_2}$
Because $S_1 \cup S_2$ is again a finite set it follows that $U_1 \cap U_2 \in \SS^*$.
This implies $(2)$.
{{qed}}
Category:Topology
lzb94fu4slqcjfaopif7g23gy68jyvd
Theorem: Finite Fourier Series

Let $\map a n$ be any finite periodic real function on $\Z$ with period $b$.
Let $\xi = e^{2 \pi i/ b}$ be the first $b$th root of unity.
Then:
:$\ds \map a n = \sum_{k \mathop = 0}^{b - 1} \map {a_*} k \xi^{n k}$
where:
:$\ds \map {a_*} n = \frac 1 b \sum_{k \mathop = 0}^{b - 1} \map a k \xi^{-n k}$

Proof:
Since $a$ has period $b$, we have:
:$\map a {n + b} = \map a n$
So if we define:
:$\ds \map F z = \sum_{n \mathop \ge 0} \map a n z^n$
we have:
{{begin-eqn}}
{{eqn | l = \map F z)
      | r = \paren {\sum_{k \mathop = 0}^{b - 1} \map a k z^k} + z^b \paren {\sum_{k \mathop = 0}^{b - 1} \map a k z^k} + z^{2 b} \paren {\sum_{k \mathop = 0}^{b - 1} \map a k z^k} + \cdots
      | c = 
}}
{{eqn | r = \frac 1 {1 - z^b} \paren {\sum_{k \mathop = 0}^{b - 1} \map a k z^k}
      | c = 
}}
{{eqn | r = \frac {\map P z} {1 - z^b}
      | c = 
}}
{{end-eqn}}
where the last step defines the polynomial $P$.
If we expand $F$ now using partial fractions, we get
{{finish}}
{{Namedfor|Joseph Fourier|cat = Fourier}}
Category:Fourier Analysis
bbrax01npxvtlk5cw1obugjdiy65mu1