nyuuzyou/wikis huggingface dataset:
Directed Smooth Curve Relation is Equivalence

== Theorem ==
Let $\sim$ denote a relation on the set of all smooth paths: $\set {\gamma: I \to \C : \text{$I$ is a closed real interval, $\gamma$ is a smooth path} }$.
Let $\gamma: \closedint a b \to \C$ and $\sigma : \closedint c d \to \C$ be smooth paths.
Define $\sim$ as follows: 
:$\gamma \sim \sigma$ there exists a bijective differentiable strictly increasing real function $\phi: \closedint c d \to \closedint a b$ such that $\sigma = \gamma \circ \phi$.
Then $\sim$ is an equivalence relation on the set of all smooth paths.
== Proof ==
Checking in turn each of the criteria for an equivalence:
=== Reflexive ===
Let $\gamma: \closedint a b \to \C$ be a smooth path.
Define $\phi: \closedint a b \to \closedint a b$ as the identity function, so:
$\map \phi t = t$ for all $t \in \closedint a b$
From Identity Mapping is Bijection, it follows that $\phi$ is bijective.
From Derivative of Identity Function, it follows that:
:$\map {\phi'} t = 1 > 0$
for all $t \in \closedint a b$.
Then Derivative of Monotone Function shows that $\phi$ is strictly increasing.
Hence, $\gamma \sim \gamma$, so $\sim$ is reflexive.
=== Symmetric ===
Let $\gamma: \closedint a b \to \C$ and $\sigma: \closedint c d \to \C$ be smooth paths such that $\gamma \sim \sigma$.
That is, $\sigma = \gamma \circ \phi$ where $\phi: \closedint c d \to \closedint a b$ is bijective, differentiable and strictly increasing.
From Bijection iff Inverse is Bijection, it follows that $\phi$ has an inverse function:
:$\phi^{-1}: \closedint a b \to \closedint c d$
Then:
:$\gamma = \sigma \circ \phi^{-1}$
From Derivative of Inverse Function:
:$D \map {\phi^{-1} } t = \dfrac 1 {\map {\phi'} {\map {\phi^{-1} } t} }$
for all $t \in \closedint a b$.
From Derivative of Monotone Function:
:$\map {\phi'} {\map {\phi^{-1} } t} > 0$
Then:
:$D \map {\phi^{-1} } t > 0$
so $\phi^{-1}$ is strictly increasing.
Hence, $\sigma \sim \gamma$, so $\sim$ is symmetric.
=== Transitive ===
Let $\gamma: \closedint a b \to \C$, $\sigma: \closedint c d \to \C$ and $\rho: \closedint g h \to \C$ be smooth paths such that $\gamma \sim \sigma$ and $\sigma \sim \rho$.
That is:
:$\sigma = \gamma \circ \phi$ and $\rho = \sigma \circ \psi$
where $\phi: \closedint c d \to \closedint a b$ and $\psi: \closedint g h \to \closedint c d$ are bijective, differentiable and strictly increasing.
Then:
:$\rho = \gamma \circ \paren {\phi \circ \psi}$
From Composite of Bijections is Bijection, it follows that $\phi \circ \psi$ is bijective.
From Derivative of Composite Function, it follows that:
:$D \map {\paren {\phi \circ \psi} } t = \map {\phi'} {\map \psi t} \map {\psi'} t$
for all $t \in \closedint g h$.
As $\map {\phi'} {\map \psi t} > 0$ and $\map {\psi'} t > 0$, this implies that:
:$D \map {\paren {\phi \circ \psi} } t > 0$
so $\phi \circ \psi$ is strictly increasing.
Hence, $\gamma \sim \rho$, so $\sim$ is transitive.
Therefore, $\sim$ is an equivalence relation.
== Sources ==
* $\S 2.2$
Category:Smooth Paths (Complex Analysis)
Category:Examples of Equivalence Relations
Directed Suprema Preserving Mapping at Element is Supremum

== Theorem ==
Let $\struct {S, \vee, \wedge, \preceq}$ and $\struct {T, \vee_2, \wedge_2, \precsim}$ be bounded below continuous lattices.
Let $f: S \to T$ be a mapping such that
:$f$ preserves directed suprema.
Let $x \in S$.
Then:
:$\map f x = \sup \set {\map f w: w \in S \land w \ll x}$
== Proof ==
By definition of continuous:
:$x^\ll$ is directed
and
:$\struct {S, \vee, \wedge, \preceq}$ is up-complete
and
:$\struct {S, \vee, \wedge, \preceq}$ satisfies the .
By definition of mapping preserves directed suprema:
:$f$ preserves the supremum of $x^\ll$.
By definition of up-complete:
:$x^\ll$ admits a supremum.
Thus
== Sources ==
* 
Category:Continuous Lattices
Directed Suprema Preserving Mapping is Increasing

== Theorem ==
Let $L = \struct {S, \vee, \preceq}$ be a join semilattice.
Let $f: S \to S$ be a mapping that preserves directed suprema.
Then $f$ is an increasing mapping.
== Proof ==
Let $x, y \in D$ such that
:$x \preceq y$
Then by definition of reflexivity:
:$\forall a, b \in \set {x, y}: \exists z \in \set {x, y}: a \preceq z \land b \preceq z$
By definition:
:$\set {x, y}$ is directed.
By definition of mapping preserves directed suprema:
:$f$ preserves the supremum of $\set {x, y}$.
By definition of join semilattice:
:$\set {x, y}$ admits a supremum.
By Image of Doubleton under Mapping:
:$f \sqbrk {\set {x, y} } = \set {\map f x, \map f y}$
Thus by definitions of supremum and upper bound:
:$\map f x \preceq \map f y$
== Sources ==
* 
Category:Increasing Mappings
Directed iff Filtered in Dual Ordered Set

== Theorem ==
Let $\struct {S, \preceq_1}$ be an ordered set.
Let $\struct {S, \preceq_2}$ be a dual ordered set of $\struct {S, \preceq_1}$
Let $X \subseteq S$.
Then:
:$X$ is directed in $\struct {S, \preceq_1}$
:
:$X$ is filtered in $\struct {S, \preceq_2}$.
== Proof ==
=== Sufficient Condition ===
Assume that:
:$X$ is directed in $\struct {S, \preceq_1}$
Thus $X$ is non-empty.
Let $x, y \in S$.
By definition of directed:
:$\exists z \in S: x \preceq_1 z \land y \preceq_1 z$
Thus by definition of dual ordered set:
:$z \preceq_2 x \land z \preceq_2 y$
=== Necessary Condition ===
Assume that:
:$X$ is filtered in $\struct {S, \preceq_2}$
Thus $X$ is non-empty.
Let $x, y \in S$.
By definition of filtered:
:$\exists z \in S: z \preceq_2 x \land z \preceq_2 y$
Thus by definition of dual ordered set:
:$x \preceq_1 z \land y \preceq_1 z$
== Sources ==
* 
Category:Dual Orderings
Directed iff Finite Subsets have Upper Bounds

== Theorem ==
Let $\struct {S, \precsim}$ be a preordered set.
Let $H$ be a non-empty subset of $S$.
Then $H$ is directed :
:for every finite subset $A$ of $H$:
::$\exists h \in H: \forall a \in A: a \precsim h$
== Proof ==
=== Sufficient Condition ===
Let $R$ be directed.
We will prove by induction of the cardinality of finite subset of $H$.
==== Base case ====
:$\forall A \subseteq H: \card A = 0 \implies \exists h \in H: \forall a \in A: a \precsim h$
where $\card A$ denotes the cardinality of $A$.
Let $A \subseteq H$ such that
:$\card A = 0$
By Cardinality of Empty Set:
:$A = \O$
By definition of empty set:
:$\exists h: h \in H$
Thus by definition of empty set:
:$\exists h \in H: \forall a \in A: a \precsim h$
==== Induction Hypothesis ====
:$\forall A \subseteq H: \card A = n \implies \exists h \in H: \forall a \in A: a \precsim h$
==== Induction Step ====
:$\forall A \subseteq H: \card A = n + 1 \implies \exists h \in H: \forall a \in A: a \precsim h$
Let $A \subseteq H$ such that
:$\card A = n + 1$
By definition of cardinality of finite set:
:$A \sim \N_{< n + 1}$
where $\sim$ denotes set equivalence.
By definition of set equivalence:
:there exists a bijection $f: \N_{< n + 1} \to A$
By Restriction of Injection is Injection:
:$f \restriction_{\N_{< n} }: \N_{< n} \to \map {f^\to} {\N_{<n} }$ is an injection.
By definition
:$f \restriction_{\N_{< n} }: \N_{< n} \to \map {f^\to} {\N_{<n} }$ is a surjection.
By definition
:$f \restriction_{\N_{< n} }: \N_{< n} \to \map {f^\to} {\N_{<n} }$ is a bijection.
By definition of set equivalence:
:$\N_{< n} \sim \map {f^\to} {\N_{<n} }$
By definition of cardinality of finite set:
:$\card {\map {f^\to} {\N_{<n} } } = n$
By definitions of image of set and subset:
:$\map {f^\to} {\N_{<n} } \subseteq A$
By Subset Relation is Transitive:
:$\map {f^\to} {\N_{<n} } \subseteq H$
By Induction Hypothesis:
:$\exists h \in H: \forall a \in \map {f^\to} {\N_{<n} }: a \precsim h$
By definition $\N_{< n + 1}$
:$n \in \N_{< n + 1}$
By definition of mapping:
:$\map f n \in A$
By definition of subset:
:$\map f n \in H$
By definition of directed subset:
:$\exists h' \in H: \map f n \precsim h' \land h \precsim h'$
Let $a \in A$.
Then by definitions of union and singleton:
:$a \in \map {f^\to} {\N_{< n} } \lor a = \map f n$
So:
:$a \precsim h \lor a = \map f n$
Thus by definition of transitivity:
:$a \precsim h'$
Thus:
:$\exists h' \in H: \forall a \in A: a \precsim h'$
=== Necessary Condition ===
Assume that:
:for every a finite subset $A$ of $H$
::$\exists h \in H: \forall a \in A: a \precsim h$
Let $a, b \in H$.
By definition of subset:
:$\set {a, b} \subseteq H$
:$\set {a, b}$ is finite
By assumption:
:$\exists h \in H: \forall c \in set {a, b}: c \precsim h$
Thus by definition of unordered tuple:
:$\exists h \in H: a \precsim h \land b \precsim h$
Thus by definition:
:$H$ is directed.
== Sources ==
* 
* 
Category:Preorder Theory
Directed iff Lower Closure Directed

== Theorem ==
Let $\struct {S, \precsim}$ be a preordered set.
Let $H$ be a non-empty subset of $S$.
Then $H$ is directed :
:$H^\precsim$ is directed
where $H^\precsim$ denotes the lower closure of $H$ with respect to $\precsim$.
== Proof ==
=== Sufficient Condition ===
Let us assume that $H$ is directed.
Let $x, y \in H^\precsim$.
By definition of lower closure:
:$\exists x' \in H: x \precsim x'$
and
:$\exists y' \in H: y \precsim y'$
By definition of directed subset:
:$\exists z \in H: x' \precsim z \land y' \precsim z$
By definition of reflexivity;
:$z \precsim z$
By definition of lower closure:
:$z \in H^\precsim$
Thus by definition of transitivity:
:$\exists z \in H^\precsim: x \precsim z \land y \precsim z$
Thus by definition:
:$H^\precsim$ is directed.
=== Necessary Condition ===
Let us assume that $H^\precsim$ is directed.
Let $x, y \in H$.
By definition of reflexivity:
:$x \precsim x \land y \precsim y$
By definition of lower closure:
:$x, y \in H^\precsim$
By definition of directed subset:
:$\exists z \in H^\precsim: x \precsim z \land y \precsim z$
By definition of lower closure:
:$\exists z' \in H: z \precsim z'$
Thus by definition of transitivity
:$\exists z' \in H: x \precsim z' \land y \precsim z'$
Thus by definition:
:$H$ is directed.
== Sources ==
* 
* 
Category:Preorder Theory
Directed in Join Semilattice

== Theorem ==
Let $\struct {S, \preceq}$ be a join semilattice.
Let $H$ be a non-empty lower section of $S$.
Then $H$ is directed 
:$\forall x, y \in H: x \vee y \in H$
== Proof ==
=== Sufficient Condition ===
Let us assume that
:$H$ is directed.
Let $x, y \in H$.
By definition of directed:
:$\exists z \in H: x \preceq z \land y \preceq z$
By definition
:$z$ is upper bound of $\set {x, y}$
By definitions of supremum and join:
:$x \vee y = \sup \set {x, y} \preceq z$
Thus by definition of lower section:
:$x \vee y \in H$
=== Necessary Condition ===
Let us assume that
:$\forall x, y \in H: x \vee y \in H$
Let $x, y \in H$.
By assumption:
:$x \vee y \in H$
By definition of supremum:
:$x \vee y$ is upper bound of $\set {x, y}$
Thus
:$x \preceq x \vee y \land y \preceq x \vee y$
Thus by definition
:$H$ is directed.
== Sources ==
* 
* 
Category:Join and Meet Semilattices
Category:Lower Sections
Directed in Join Semilattice with Finite Suprema

== Theorem ==
Let $\struct {S, \preceq}$ be a join semilattice.
Let $H$ be a non-empty lower section of $S$.
Then $H$ is directed 
:for every non-empty finite subset $A$ of $H$, $\sup A \in H$
== Proof ==
=== Sufficient Condition ===
Let us assume that
:$H$ is directed.
Let $A$ be a non-empty finite subset of $H$.
By Directed iff Finite Subsets have Upper Bounds:
:$\exists h \in H: \forall a \in A: a \preceq h$
By definition
:$z$ is upper bound of $A$
By Existence of Non-Empty Finite Suprema in Join Semilattice:
:$\sup A$ exists in $\struct {S, \preceq}$
By definition of supremum:
:$\sup A \preceq h$
Thus by definition of lower section:
:$\sup A \in H$
=== Necessary Condition ===
Let us assume that
:for every non-empty finite subset $A$ of $H$, $\sup A \in H$
Let $x, y \in H$.
:$A := \set {x, y}$ is a non-empty finite subset of $H$
By assumption:
:$\sup \set {x, y} \in H$
By definition of supremum:
:$\sup A$ is upper bound for $\set {x, y}$
Thus
:$x \preceq \sup A \land y \preceq \sup A$
Thus by definition
:$H$ is directed.
== Sources ==
* 
* 
Category:Join and Meet Semilattices
Category:Lower Sections
Direction Angle of 2D Vector in Terms of Arctangent

== Theorem ==
Let $\mathbf a$ be a vector quantity embedded in a Cartesian plane $P$ expressed in component form as:
:$\mathbf a = x \mathbf i + y \mathbf j$
Let $\theta$ denote the direction of $\mathbf a$.
Then:
:$\theta = \begin{cases} 
\map \arctan {\dfrac y x} & : x > 0 \\
\map \arctan {\dfrac y x} + \pi & : x < 0 \text{ and } y \ge 0 \\
\map \arctan {\dfrac y x} - \pi & : x < 0 \text{ and } y < 0 \\
\dfrac \pi 2 & : x = 0 \text{ and } y > 0 \\
-\dfrac \pi 2 & : x = 0 \text{ and } y < 0 \\
\text{undefined} & : x = 0 \text { and } y = 0
\end{cases}$
where:
:$\arctan$ denotes the real arctangent function, defined on the real interval $\openint {-\dfrac \pi 2} {\dfrac \pi 2}$
:$\theta$ is conventionally measured from the positive direction of the $x$-axis in the interval $\hointl {-\pi} \pi$.
== Proof ==
Let $\mathbf a$ be such that one of the following holds:
:$\mathbf a$ is in Quadrant $\text{I}$ or Quadrant $\text{IV}$
:$\mathbf a$ is on the positive direction of the $x$-axis.
Then:
:$x > 0$
and:
:$-\dfrac \pi 2 < \theta < \dfrac \pi 2$
The components of $\mathbf a$ form the legs of a right triangle where:
Let $\mathbf a$ be such that one of the following holds:
:$\mathbf a$ is in Quadrant $\text{II}$
:$\mathbf a$ is on the negative direction of the $x$-axis.
Then:
:$x < 0$
:$y \ge 0$
and:
:$\dfrac \pi 2 < \theta \le \pi$
Let $\mathbf a$ be in Quadrant $\text{III}$.
Then:
:$x < 0$
:$y < 0$
and:
:$-\pi < \theta < \dfrac {-\pi} 2$
Let $\mathbf a$ be on the positive direction of the $y$-axis.
Then:
:$x = 0$
:$y > 0$
Then the arctangent of $\theta$ is undefined.
We have:
Let $\mathbf a$ be on the negative direction of the $y$-axis.
Then:
:$x = 0$
:$y < 0$
Then the arctangent of $\theta$ is undefined.
We have:
Finally, let $\mathbf a$ be the zero vector.
We have:
:$x = 0$
:$y = 0$
and hence:
Hence, $\theta$ can be described using the following piecewise function:
Hence the result.
== Also defined as ==
Some sources define the codomain as the interval $\hointr 0 {2 \pi}$.
== Also known as ==
This piecewise function is often presented in computer languages as $\map {\text {atan2} } {y, x}$.
Category:Vectors
Category:Arctangent Function
Direction Cosines/Examples/Example 1

== Example of Direction Cosines ==
Let $\mathbf A$ be a vector quantity of magnitude $10$ embedded in Cartesian $3$-space.
Let $\mathbf A$ make equal angles with the coordinate axes $x$, $y$ and $z$.
Then the magnitudes of the components of $\mathbf A$ are all equal to $\dfrac {10 \sqrt 3} 3$.
== Proof ==
From Magnitude of Vector Quantity in terms of Components:
:$\size {\mathbf A} = \sqrt {x^2 + y^2 + z^2}$
where $x$, $y$ amd $z$ are the magnitudes of the components of $\mathbf A$ in the $\mathbf i$, $\mathbf j$ and $\mathbf k$ directions respectively.
From Components of Vector in terms of Direction Cosines:
We are given that:
:$\alpha = \beta = \gamma$
and that:
:$\size {\mathbf A} = 10$
Hence:
== Sources ==
* : Chapter $1$ Vector Analysis $1.1$ Definitions, Elementary Approach: Exercise $1.1.2$
Category:Examples of Direction Cosines
Direction of Electric Field caused by Point Charge

== Theorem ==
Let $q$ be a point charge.
Let $\map {\mathbf E} {\mathbf r}$ be the electric field strength due to $q$ at a point $P$ whose position vector is $\mathbf r$.
The direction of the electric field due to $q$ at $P$ is:
:for positive $q$, directly away from $q$ 
:for negative $q$, directly towards $q$.
== Proof ==
From Electric Field caused by Point Charge:
By definition of vector subtraction, $\mathbf r - \mathbf r_q$ is the vector from $\mathbf r_q$ to $\mathbf r$.
Hence if $q$ is positive, the direction of $\map {\mathbf E} {\mathbf r}$ is towards $\mathbf r$, which is directly away from $q$.
Similarly, if $q$ is negative, the direction of $\map {\mathbf E} {\mathbf r}$ is $-\paren {\mathbf r - \mathbf r_q}$.
That is, the direction of $\map {\mathbf E} {\mathbf r}$ is $\mathbf r_q - \mathbf r$.
By definition of vector subtraction, $\mathbf r_q - \mathbf r$ is the vector from $\mathbf r$ to $\mathbf r_q$.
This is directly towards $q$.
The following diagram shows the lines of force of $\map {\mathbf E} {\mathbf r}$ as arrows, pointing away from $+q$:
:
The following diagram shows the lines of force of $\map {\mathbf E} {\mathbf r}$ as arrows, pointing towards $-q$:
:
== Sources ==
* : Chapter $1$: Force and energy in electrostatics: $1.2$ The Electric Field
Category:Electric Fields
Category:Point Charges
Direction of Line of Electric Force

== Theorem ==
Let $\mathbf E$ be an electric field.
Let $L$ be a line of force within $\mathbf E$.
Then $L$ has one of the following properties:
:$(1): \quad$ Begins on a positively charged body and ends on a negatively charged body
:$(2): \quad$ Begins on a positively charged body and goes to infinity without terminating
:$(3): \quad$ Comes from infinity without a start point and ends on a negatively charged body.
== Proof ==
== Sources ==
* : Chapter $1$: Force and energy in electrostatics: $1.2$ The Electric Field
Category:Lines of Electric Force
Direction of Rotation of Plane of Oscillation of Foucault's Pendulum

== Theorem ==
Let $P$ be a Foucault pendulum.
The rotation $\alpha$ of the plane of oscillation of $P$ is:
:clockwise in the northern hemisphere
:anticlockwise in the southern hemisphere.
== Proof ==
== Sources ==
* 
* 
Category:Foucault's Pendulum
Directional Data/Examples/Arbitrary Example 1

== Example of Directional Data ==
Consider the following set of directional data measured over the range $0 \degrees$ to $360 \degrees$:
:$\set {1 \degrees, 5 \degrees, 10 \degrees, 350 \degrees, 355 \degrees, 359 \degrees}$
If this were treated as linear data, the arithmetic mean and median are both $180 \degrees$.
:
However, if this directional data was measured with the same zero, but with a range from $-180 \degrees$ to $+180 \degrees$, it becomes:
:$\set {1 \degrees, 5 \degrees, 10 \degrees, -10 \degrees, -5 \degrees, -1 \degrees}$
which gives a arithmetic mean and median of $0 \degrees$.
By visual inspection, it is apparent that the second of these is a more sensible interpretation of centrality
== Sources ==
* 
Category:Examples of Directional Data
Dirichlet's Approximation Theorem

== Theorem ==
Let $\alpha, x \in \R$.
Then there exist integers $a, q$ such that:
: $\gcd \set {a, q} = 1$, $1 \le q \le x$
and:
:$\size {\alpha - \dfrac a q} \le \dfrac 1 {q x}$
== Proof ==
It is sufficient to find $a, q$ not necessarily coprime.
Once such an $a, q$ have been found, then a coprime pair can be found by dividing numerator and denominator of $\dfrac a q$ by the GCD of $a$ and $q$.
Let $X = \floor x$ be the integer part of $x$.
Let $\alpha_q = \alpha q - \floor {\alpha q} \in \hointr 0 1$ for $q = 1, \ldots, X$.
Consider the disjoint real intervals:
:$I_k = \hointr {\dfrac{k-1} {X + 1} } {\dfrac k {X + 1} }, \quad k = 1, \ldots, X + 1$
Suppose there exists $q$ such that:
:$\alpha_q \in \hointr 0 {\dfrac 1 {X + 1} }$
Then:
:$0 \le \alpha q - \floor {\alpha q} < \dfrac 1 {X + 1}$
Hence:
:$\size {\alpha - \dfrac {\floor {\alpha q} } q} < \dfrac 1 {q \paren {X + 1} } < \dfrac 1 {q x}$
Taking $a = \floor {\alpha q}$, the construction is complete.
Suppose that not to be the case, but suppose that there exists $q$ such that:
: $\alpha_q \in \hointr {\dfrac X {X + 1} } 1$
Then similarly:
:$\dfrac X {X + 1} < \alpha q - \floor {\alpha q} < 1$
so:
:$-\dfrac 1 {X + 1} < \alpha q - \floor {\alpha q} - 1 < 0$
and:
:$\size {\alpha - \dfrac {\floor {\alpha q} + 1} q} < \dfrac 1 {q \paren {X + 1} } < \dfrac 1 {q x}$
Taking $a = \floor {\alpha q} + 1$, again the construction is complete.
If neither of the above cases holds, then the $X - 1$ remaining intervals $I_k$ contain the $X$ values of $\alpha_q$.
Therefore, by the Pigeonhole Principle, there are $k_0 \in \set {2, \ldots, X}$ and $q_1 < q_2$ such that: :$\alpha_{q_1}, \alpha_{q_2} \in I_{k_0}$
Then for $i = 1, 2$:
:$\dfrac {k_0 - 1} {X + 1} \le \alpha q_i - \floor {\alpha q_i} < \dfrac {k_0} {X + 1}$
Therefore:
:$\size {\alpha q_2 - \alpha q_1 - \floor {\alpha q_2} + \floor {\alpha q_1} } < \dfrac 1 {X + 1}$
and therefore:
:$\size {\alpha - \dfrac{\floor {\alpha q_2} - \floor {\alpha q_1} } {q_2 - q_1} } < \dfrac 1 {\paren {X + 1} \paren {q_2 - q_1} } < \dfrac 1 {x \paren {q_2 - q_1} }$
Taking $a = \floor {\alpha q_2} - \floor {\alpha q_1}$ and $q = q_2 - q_1$ the construction is complete.
Category:Diophantine Equations
Dirichlet's Box Principle

== Theorem ==
Let $S$ be a finite set whose cardinality is $n$.
Let $S_1, S_2, \ldots, S_k$ be a partition of $S$ into $k$ subsets.
Then:
:at least one subset $S_i$ of $S$ contains at least $\ceiling {\dfrac n k}$ elements
where $\ceiling {\, \cdot \,}$ denotes the ceiling function.
=== Corollary ===
== Proof ==
 no subset $S_i$ of $S$ has as many as $\ceiling {\dfrac n k}$ elements.
Then the maximum number of elements of any $S_i$ would be $\ceiling {\dfrac n k} - 1$.
So the total number of elements of $S$ would be no more than $k \paren {\ceiling {\dfrac n k} - 1} = k \ceiling {\dfrac n k} - k$.
There are two cases:
:$n$ is divisible by $k$
:$n$ is not divisible by $k$.
Suppose $k \divides n$.
Then $\ceiling {\dfrac n k} = \dfrac n k$ is an integer and:
:$k \ceiling {\dfrac n k} - k = n - k$
Thus:
:$\ds \card S = \sum_{i \mathop = 1}^k \card {S_i} \le n - k < n$
This contradicts the fact that $\card S = n$.
Hence our assumption that no subset $S_i$ of $S$ has as many as $\ceiling {\dfrac n k}$ elements was false.
Next, suppose that $k \nmid n$.
Then:
:$\card S = k \ceiling {\dfrac n k} - k < \dfrac {k \paren {n + k} } k - k = n$
and again this contradicts the fact that $\card S = n$.
In the same way, our assumption that no subset $S_i$ of $S$ has as many as $\ceiling {\dfrac n k}$ elements was false.
Hence, by Proof by Contradiction, there has to be at least $\ceiling {\dfrac n k}$ elements in at least one $S_i \subseteq S$.
== Also known as ==
== Also see ==
* Infinite Ramsey's Theorem
== Historical Note ==
== Sources ==
* : $\S 10.18$
* : Chapter $2$: Elementary Concepts of Graph Theory: $\S 2.2$: Isomorphic Graphs
* : Henry van Etten: $124$
* 
Category:Dirichlet's Box Principle
Category:Combinatorics
Dirichlet's Box Principle/Also known as

== Dirichlet's Box Principle: Also known as ==
Dirichlet's Box Principle, in particular its corollary, is also commonly known as the Pigeonhole Principle or Pigeon-Hole Principle:
:Suppose you have $n + 1$ pigeons, but have only $n$ holes for them to stay in.
:By the Pigeonhole Principle, at least one of the holes houses $2$ pigeons.
It is also known as Dirichlet's Drawer Principle or Dirichlet's Shelf Principle.
Some sources give it as the Letterbox Principle or Letter-Box Principle.
Some sources call it Dirichlet's Principle, but there is more than one theorem named such.
Some sources give this as the Dirichlet Principle.
== Sources ==
* 
* 
* 
Category:Dirichlet's Box Principle
Dirichlet's Box Principle/Corollary

== Corollary to Dirichlet's Box Principle ==
If a set of $n$ distinct objects is partitioned into $k$ subsets, where $0 < k < n$, then at least one subset must contain at least two elements.
== Proof ==
A direct application of the Dirichlet's Box Principle.
== Also known as ==
== Sources ==
* : $\S 0.6$: Theorem $9$
* : $\S 10.18$
* 
* 
* 
* 
Category:Dirichlet's Box Principle
Dirichlet's Box Principle/Historical Note

== Historical Note on Dirichlet's Box Principle ==
Dirichlet's Box Principle appeared in print as early as $1622$ in by .
It also appears, in greater detail, in the $1624$ work by "", also commonly attributed to .
It is commonly called Dirichlet's Box (or Drawer) Principle, after an $1834$ treatment by , who called it the Schubfachprinzip (drawer principle or shelf principle).
In Russian and some other languages, it is known as the Dirichlet Principle or Dirichlet's Principle, which name ambiguously also refers to the minimum principle for harmonic functions.
It is usually seen in its simplest form: if you have $N + 1$ objects to put into $N$ boxes, at least one box contains $2$ objects.
== Sources ==
* : Henry van Etten: $124$
Category:Historical Notes