nyuuzyou/wikis huggingface dataset:
Quadrilateral is Cyclic iff Opposite Angles sum to Two Right Angles

== Theorem ==
Given $\Box ABCD$ with $A, B$ and $D$ on a circle.
Let $\angle ABC$ and $\angle ADC$ add to two right angles.
Then $C$ lies on the circle, and $\Box ABCD$ is a cyclic quadrilateral.
== Proof ==
=== Sufficient Condition ===
By Sum of Internal Angles of Polygon, since $\Box ABCD$ is a quadrilateral:
:$\angle ABC + \angle BCD + \angle BAD + \angle ADC = 360$
Therefore $\angle BAD$ and $\angle BCD$ are also supplementary angles.
Suppose $C$ does not lie on the circle, but lies internal. 
Extend $DC$ to meet the circle at $C'$.
By Opposite Angles of Cyclic Quadrilateral sum to Two Right Angles:
:$\angle BC'D$ is supplementary to $\angle BAD$.
It follows that:
:$\angle BC'D = \angle BCD$
By External Angle of Triangle equals Sum of other Internal Angles:
:$\angle BCD = \angle BC'D + \angle C'BC$
Hence $BCD > BC'D$. 
But this is a contradiction.
Suppose $C$ lies outside the circle. 
Draw $DC$ and find the point $C'$ where $DC$ meets the circle.
By External Angle of Triangle equals Sum of other Internal Angles:
:$\angle BC'D = \angle BCD + \angle C'BC$
Hence $BC'D > BCD$. 
But this is a contradiction.
Since $C$ is neither internal to the circle nor external to it, it must lie on the circle.
=== Necessary Condition ===
This follows by Opposite Angles of Cyclic Quadrilateral sum to Two Right Angles.
Category:Cyclic Quadrilaterals
Quadrilateral is Parallelogram iff Both Pairs of Opposite Angles are Equal

== Theorem ==
Let $ABCD$ be a quadrilateral.
Then:
:$ABCD$ is a parallelogram
:
:$\angle ABC = \angle ADC$ and $\angle BAD = \angle BCD$.
== Proof ==
=== Sufficient Condition ===
Let $ABCD$ be a parallelogram.
Then by Opposite Sides and Angles of Parallelogram are Equal:
:$\angle ABC = \angle ADC$ and $\angle BAD = \angle BCD$.
=== Necessary Condition ===
Let $ABCD$ be such that:
:$\angle ABC = \angle ADC$ and $\angle BAD = \angle BCD$.
== Sources ==
* : Chapter $1$: Triangles and Polygons: Theorems and Corollaries $1.23 \ \text{(iii)}$
Category:Parallelograms
Quadrilateral is Parallelogram iff Both Pairs of Opposite Sides are Equal or Parallel

== Theorem ==
Let $ABCD$ be a quadrilateral.
Then:
:$ABCD$ is a parallelogram
:
:either $AB = CD$ and $AD = BC$
:or $AB \parallel CD$ and $AD \parallel BC$
where $AB \parallel CD$ denotes that $AB$ is parallel to $CD$.
== Proof ==
=== Sufficient Condition ===
Let $ABCD$ be a parallelogram.
Then by definition:
:$AB \parallel CD$ and $AD \parallel BC$
and from Opposite Sides and Angles of Parallelogram are Equal:
:$AB = CD$ and $AD = BC$
From Conjunction implies Disjunction, it follows that:
:either $AB = CD$ and $AD = BC$
:or $AB \parallel CD$ and $AD \parallel BC$.
=== Necessary Condition ===
Let $ABCD$ be such that:
:either $AB = CD$ and $AD = BC$
:or $AB \parallel CD$ and $AD \parallel BC$.
First suppose that $AB = CD$ and $AD = BC$.
Then from Opposite Sides Equal implies Parallelogram, $ABCD$ is a parallelogram.
Now suppose that $AB \parallel CD$ and $AD \parallel BC$.
Then $ABCD$ is a parallelogram by definition.
Hence the result by Proof by Cases.
== Sources ==
* : Chapter $1$: Triangles and Polygons: Theorems and Corollaries $1.23 \ \text{(ii)}$
Category:Parallelograms
Quadrilateral is Parallelogram iff Diagonals Bisect each other

== Theorem ==
Let $ABCD$ be a quadrilateral.
Then:
: $ABCD$ is a parallelogram
:
:both:
:: $AD$ is a bisector of $BC$
:and:
:: $BC$ is a bisector of $AD$.
== Proof ==
=== Sufficient Condition ===
Let $ABCD$ be a parallelogram.
Then by Diameters of Parallelogram Bisect each other:
: $AD$ is a bisector of $BC$
and
: $BC$ is a bisector of $AD$.
=== Necessary Condition ===
Let $ABCD$ be such that:
: $AD$ is a bisector of $BC$
and
: $BC$ is a bisector of $AD$.
Then from Quadrilateral with Bisecting Diagonals is Parallelogram, $ABCD$ is a parallelogram.
== Sources ==
* : Chapter $1$: Triangles and Polygons: Theorems and Corollaries $1.23 \ \text{(iv)}$
Category:Parallelograms
Quadrilateral is Parallelogram iff One Pair of Opposite Sides is Equal and Parallel

== Theorem ==
Let $ABCD$ be a quadrilateral.
Then:
:$ABCD$ is a parallelogram
:
:$AB = CD$ and $AB \parallel CD$
where $AB \parallel CD$ denotes that $AB$ is parallel to $CD$.
== Proof ==
=== Sufficient Condition ===
Let $ABCD$ be a parallelogram.
Then $AB \parallel CD$ by definition.
From Opposite Sides and Angles of Parallelogram are Equal it follows that $AB = CD$.
=== Necessary Condition ===
Let $AB = CD$ and $AB \parallel CD$.
Then from Lines Joining Equal and Parallel Straight Lines are Parallel, $AD \parallel BC$.
Thus we have $AB \parallel CD$ and $AD \parallel BC$, and so by definition $ABCD$ is a parallelogram.
== Sources ==
* : Chapter $1$: Triangles and Polygons: Theorems and Corollaries $1.23 \ \text{(i)}$
Category:Parallelograms
Quadrilateral with Bisecting Diagonals is Parallelogram

== Theorem ==
Let $ABCD$ be a quadrilateral.
Let the diagonals of $ABCD$ bisect each other.
Then $ABCD$ is a parallelogram.
== Proof ==
The diagonals of $ABCD$ bisect each other if the position vectors of the midpoints of the diagonals are the same point.
Let $z_1, z_2, z_3, z_4$ be the position vectors of the vertices of $ABCD$.
Thus:
The result follows from Condition for Points in Complex Plane to form Parallelogram.
== Also see ==
* Diameters of Parallelogram Bisect each other
== Sources ==
* : $1$: Complex Numbers: Supplementary Problems: Graphical Representation of Complex Numbers. Vectors: $66$
Category:Quadrilaterals
Category:Parallelograms
Quadruple Angle Formulas

== Theorem ==
=== Quadruple Angle Formula for Sine ===
=== Quadruple Angle Formula for Cosine ===
=== Quadruple Angle Formula for Tangent ===
where $\sin, \cos, \tan$ denote sine, cosine and tangent respectively.
=== Quadruple Angle Formula for Hyperbolic Sine ===
=== Quadruple Angle Formula for Hyperbolic Cosine ===
=== Quadruple Angle Formula for Hyperbolic Tangent ===
where $\sinh, \cosh, \tanh$ denote hyperbolic sine, hyperbolic cosine and hyperbolic tangent respectively.
== Also see ==
* Triple Angle Formulas
* Quintuple Angle Formulas
Category:Quadruple Angle Formulas
Category:Multiple Angle Formulas
Category:Trigonometric Identities
Category:Hyperbolic Functions
Quadruple Angle Formulas/Cosine

== Theorem ==
:$\cos 4 \theta = 8 \cos^4 \theta - 8 \cos^2 \theta + 1$
where $\cos$ denotes cosine.
=== Corollary ===
=== Factor Form ===
== Proof 1 ==
== Proof 2 ==
== Sources ==
* : $\text V$. Trigonometry: Exercises $\text {XXXII}$: $16$.
* : $\S 5$: Trigonometric Functions: $5.48$
* 
* 
Category:Quadruple Angle Formula for Cosine
Category:Cosine Function
Category:Quadruple Angle Formulas
Quadruple Angle Formulas/Cosine/Corollary

== Corollary to Quadruple Angle Formula for Cosine ==
: $\cos 4 \theta = 8 \sin^4 \theta - 8 \sin^2 \theta + 1$
where $\cos$ denotes cosine.
== Proof ==
== Sources ==
* : $1$: Complex Numbers: Supplementary Problems: De Moivre's Theorem: $93 \ \text{(b)}$
Category:Quadruple Angle Formula for Cosine
Quadruple Angle Formulas/Cosine/Factor Form

== Theorem ==
:$\cos 4 \theta = \paren {\cos \theta - \cos \dfrac \pi 8} \paren {\cos \theta - \cos \dfrac {3 \pi} 8} \paren {\cos \theta - \cos \dfrac {5 \pi} 8} \paren {\cos \theta - \cos \dfrac {7 \pi} 8}$
== Proof ==
Setting $z = e^{i \theta}$:
== Sources ==
* : $\S 3$. Roots of Unity: Exercise $8$
Category:Quadruple Angle Formula for Cosine
Category:Cosine Function
Quadruple Angle Formulas/Hyperbolic Cosine

== Theorem ==
:$\cosh 4 x = 8 \cosh^4 x - 8 \cosh^2 x + 1$
where $\cosh$ denotes hyperbolic cosine.
== Proof ==
== Also see ==
* Quadruple Angle Formula for Hyperbolic Sine
* Quadruple Angle Formula for Hyperbolic Tangent
== Sources ==
* : $\S 8$: Hyperbolic Functions: $8.34$: Multiple Angle Formulas
Category:Hyperbolic Cosine Function
Category:Quadruple Angle Formulas
Quadruple Angle Formulas/Hyperbolic Sine

== Theorem ==
:$\sinh 4 x = 8 \sinh^3 x \cosh x + 4 \sinh x \cosh x$
where $\sinh$ and $\cosh$ denote hyperbolic sine and hyperbolic cosine respectively.
== Proof ==
== Also see ==
* Quadruple Angle Formula for Hyperbolic Cosine
* Quadruple Angle Formula for Hyperbolic Tangent
== Sources ==
* : $\S 8$: Hyperbolic Functions: $8.33$: Multiple Angle Formulas
Category:Hyperbolic Sine Function
Category:Quadruple Angle Formulas
Quadruple Angle Formulas/Hyperbolic Tangent

== Theorem ==
:$\tanh 4 x = \dfrac {4 \tanh x + 4 \tanh^3 x} {1 + 6 \tanh^2 x + \tanh^4 x}$
where $\tanh$ denotes hyperbolic tangent.
== Proof ==
== Also see ==
* Quadruple Angle Formula for Hyperbolic Sine
* Quadruple Angle Formula for Hyperbolic Cosine
== Sources ==
* : $\S 8$: Hyperbolic Functions: $8.35$: Multiple Angle Formulas
Category:Hyperbolic Tangent Function
Category:Quadruple Angle Formulas
Quadruple Angle Formulas/Sine

== Theorem ==
:$\sin 4 \theta = 4 \sin \theta \cos \theta - 8 \sin^3 \theta \cos \theta$
where $\sin$ and $\cos$ denote sine and cosine respectively.
=== Corollary 1 ===
=== Corollary 2 ===
== Proof 1 ==
== Proof 2 ==
== Proof 3 ==
== Sources ==
* : $\S 5$: Trigonometric Functions: $5.47$
Category:Sine Function
Category:Quadruple Angle Formula for Sine
Quadruple Angle Formulas/Sine/Corollary 1

== Corollary to Quadruple Angle Formula for Sine ==
For all $\theta$ such that $\theta \ne 0, \pm \pi, \pm 2 \pi \ldots$
:$\dfrac {\sin 4 \theta} {\sin \theta} = 8 \cos^3 \theta - 4 \cos \theta$
where $\sin$ denotes sine and $\cos$ denotes cosine.
== Proof ==
First note that when $\theta = 0, \pm \pi, \pm 2 \pi \ldots$:
:$\sin \theta = 0$
so $\dfrac {\sin 4 \theta} {\sin \theta}$ is undefined.
Therefore for the rest of the proof it is assumed that $\theta \ne 0, \pm \pi, \pm 2 \pi \ldots$
== Sources ==
* : $1$: Complex Numbers: Supplementary Problems: De Moivre's Theorem: $93 \ \text{(a)}$
::(although see Quadruple Angle Formulas/Sine/Mistake for analysis of an error in that work)
Category:Quadruple Angle Formula for Sine
Quadruple Angle Formulas/Sine/Corollary 2

== Corollary to Quadruple Angle Formula for Sine ==
For all $\theta$ such that $\theta \ne 0, \pm \pi, \pm 2 \pi \ldots$
:$\dfrac {\sin 4 \theta} {\sin \theta} = 2 \cos 3 \theta + 2 \cos \theta$
where $\sin$ denotes sine and $\cos$ denotes cosine.
== Proof ==
First note that when $\theta = 0, \pm \pi, \pm 2 \pi \ldots$:
:$\sin \theta = 0$
so $\dfrac {\sin 4 \theta} {\sin \theta}$ is undefined.
Therefore for the rest of the proof it is assumed that $\theta \ne 0, \pm \pi, \pm 2 \pi \ldots$
== Sources ==
* : $1$: Complex Numbers: Supplementary Problems: De Moivre's Theorem: $93 \ \text{(a)}$
::(although see Quadruple Angle Formulas/Sine/Mistake for analysis of an error in that work)
Category:Quadruple Angle Formula for Sine
Quadruple Angle Formulas/Sine/Mistake

== Source Work ==
: Chapter $1$: Complex Numbers
:: Supplementary Problems: De Moivre's Theorem: $93 \ \text{(a)}$
This mistake can be seen in the 1981 printing of the second edition (1974) as published by Schaum: ISBN 0-070-84382-1
== Mistake ==
:Prove that:
::$\dfrac {\sin 4 \theta} {\sin \theta} = 8 \cos^3 \theta - 4 = 2 \cos 3 \theta + 6 \cos \theta - 4$
== Correction ==
The correct expression is:
:$\dfrac {\sin 4 \theta} {\sin \theta} = 8 \cos^3 \theta - 4 \cos \theta = 2 \cos 3 \theta + 2 \cos \theta$
as demonstrated in Quadruple Angle Formulas for Sine: Corollary 1 and Quadruple Angle Formulas for Sine: Corollary 2
The mistake in the second expression probably arose from taking the incorrect result of the first expression:
:$\dfrac {\sin 4 \theta} {\sin \theta} = 8 \cos^3 \theta - 4$
and substituting for $\cos^3 \theta$ from Power Reduction Formulas/Cosine Cubed.
== Sources ==
* : $1$: Complex Numbers: Supplementary Problems: De Moivre's Theorem: $93 \ \text{(a)}$
Category:Mistakes/Theory and Problems of Complex Variables
Quadruple Angle Formulas/Tangent

== Theorem ==
:$\tan 4 \theta = \dfrac {4 \tan \theta - 4 \tan^3 \theta} {1 - 6 \tan^2 \theta + \tan^4 \theta}$
where $\tan$ denotes tangent.
== Proof ==
== Sources ==
* : $\S 5$: Trigonometric Functions: $5.49$
Category:Tangent Function
Quadruply Perfect Number/Examples/30,240

== Example of Quadruply Perfect Number ==
$30 \, 240$ is quadruply perfect:
:$\map {\sigma_1} {30 \, 240} = 120 \, 960 = 4 \times 30 \, 240$
== Proof ==
From :
Hence the result.
== Sources ==
* : $30,240$
Category:Quadruply Perfect Numbers
Category:30,240
Quantifier-Free Formula of Arithmetic is Provable

== Theorem ==
Let $\phi$ be a sentence in the language of arithmetic.
Suppose $\phi$ contains no quantifiers.
Suppose also that $\N \models \phi$.
:That is, the natural numbers model $\phi$.
Then $\phi$ is a theorem of minimal arithmetic.
=== Corollary ===
== Proof ==
By Existence of Negation Normal Form of Statement, $\phi$ is logically equivalent to a WFF $\psi$ such that:
:The only logical connectives are $\set {\neg, \land, \lor}$.
:The connective $\neg$ only appears in front of a predicate symbol.
Proceed by induction on the structure of WFFs in the language of arithmetic.
=== Predicate Symbol ===
Let $\alpha, \beta$ be terms.
Let $a, b \in \N$ be:
:$a = \map {\operatorname{val}_\N} \alpha$
:$b = \map {\operatorname{val}_\N} \beta$
where $\map {\operatorname{val}_\AA} \tau$ is the value of $\tau$.
Suppose $\psi$ is $\alpha = \beta$.
The result follows from Equality of Terms of Natural Numbers is Provable.
Suppose $\psi$ is $\alpha < \beta$.
Then $a < b$.
By Equality of Terms of Natural Numbers is Provable:\
:$\alpha = \sqbrk a$
:$\beta = \sqbrk b$
are theorems, where $\sqbrk x$ is the unary representation of $x$.
The result follows from Substitution Property of Equality and Ordering of Natural Numbers is Provable.
By definition of language of arithmetic, these are the only predicate symbols.
=== Negation ===
By definition of negation normal form, $\neg$ is only applied to predicate symbols.
That is, only in the form:
:$\neg \map P {\tau_1, \dotsc, \tau_n}$
Let $\alpha, \beta, a, b$ be defined as above.
Suppose $\psi$ is $\neg {\alpha = \beta}$.
Then $a \ne b$.
The result follows from Substitution Property of Equality and Inequality of Natural Numbers is Provable.
Suppose $\psi$ is $\neg {\alpha < \beta}$.
Then $a \ge b$.
The result follows from Substitution Property of Equality and Negation of Ordering of Natural Numbers is Provable.
=== Connectives ===
Let $A, B$ be WFFs.
By definition of negation normal form, the only other connectives are $\land$ and $\lor$.
Suppose $\psi$ is:
:$A \land B$
Then $\N \models A$ and $\N \models B$ by definition of value of formula.
By the inductive hypothesis, $A$ and $B$ are theorems.
The result follows from Rule of Conjunction.
Suppose $\psi$ is:
:$A \lor B$
Then $\N \models A$ or $\N \models B$.
Suppose that $\N \models A$.
Then, by the inductive hypothesis, $A$ is a theorem.
The result follows from Rule of Addition.
Likewise, if $\N \models B$, the result follows from Rule of Addition.
By the Principle of Structural Induction, every $\psi$ in this form has this property.
But by the definition of logical equivalence, $\phi$ can be derived from $\psi$.
Hence the result.
Category:Natural Numbers
Category:Proof Theory
Quantifier-Free Formula of Arithmetic is Provable/Corollary

== Theorem ==
Let $\phi$ be a sentence in the language of arithmetic.
Suppose $\phi$ contains no quantifiers.
Then exactly one of:
:$\phi$
:$\neg \phi$
is a theorem of minimal arithmetic.
== Proof ==
By Law of Excluded Middle, either $\N \models \phi$, or $\N \models \neg \phi$.
By Quantifier-Free Formula of Arithmetic is Provable, whichever one holds is a theorem of minimal arithmetic.
Now, suppose that $\N \models \phi$.
Then, $\N \not\models \phi$ by definition of value of formula.
Thus, by the definition of sound proof system, $\neg \phi$ is not a theorem.
Therefore, $\phi$ and $\neg \phi$ cannot both be theorems.
Quantifier/Examples

== Examples of Use of Quantifiers ==
=== Existence for All of Element Greater Than ===
=== $\epsilon$-$\delta$ Condition ===
=== Uniqueness of Additive Identity ===
=== Square of Sum ===
=== Equation involving Square ===
In the following, $x$, $y$ and $z$ are assumed to be in the domain of the natural numbers.
=== Existence for All of Twice Element ===
=== Definition of Greater Than or Equal To ===
=== Existence of $x, y \in \N$ such that $x^y = y^x$ ===
=== Existence of Multiplicative Identity ===
Category:Examples of Use of Quantifiers
Quantifier/Examples/Definition of Greater Than or Equal To

== Example of Use of Quantifiers ==
Let $x$ and $y$ be in the natural numbers.
:$\forall x: \forall y: \exists z: y \ge x \implies y = x + z$
means:
:If a natural number $y$ is not less than a natural number $x$, then $y - x$ is a natural number.
== Sources ==
* : Chapter $1$: Sets and mappings: $\S 1.1$: The need for logic: Exercise $(7) \ \text{(ii)}$
Category:Examples of Use of Quantifiers
Quantifier/Examples/Epsilon-Delta Condition

== Example of Use of Quantifiers ==
:$\forall \epsilon: \exists \delta: \forall y: \size {x - y} < \delta \implies \size {\map f x - \map f y} < \epsilon$
means:
:For every $\epsilon$ there exists a $\delta$ such that for every $y$:
::If $\size {x - y} < \delta$ then $\size {\map f x - \map f y} < \epsilon$.
== Sources ==
* : $\S 1.2$ Logic and Notation: $(2)$
Category:Examples of Use of Quantifiers
Quantifier/Examples/Equation involving Square

== Example of Use of Existential Quantifier ==
:$\exists x: x \in \Z: x^2 + 2 = 11$
means:
:There exists an integer $x$ which satisfies the equation $x^2 + 2 = 11$.
== Sources ==
* : $\S 1$: Some mathematical language: Variables and quantifiers
Category:Examples of Use of Quantifiers
Quantifier/Examples/Existence for All of Element Greater Than

== Example of Use of Quantifiers ==
:$\forall x: \exists y: x < y$
means:
:For every $x$ there exists a $y$ such that $x < y$
or (assuming the domain is that of numbers):
:For every number there exists a number greater than it.
== Sources ==
* : $\S 1.2$ Logic and Notation: $(1)$
Category:Examples of Use of Quantifiers
Quantifier/Examples/Existence for All of Twice Element

== Example of Use of Quantifiers ==
Let $x$ and $y$ be in the natural numbers.
:$\forall x: \exists y: x = y + y$
means:
:Every natural number is twice a natural number.
This is false.
Thus:
:$\exists x: \forall y: x \ne y + y$
== Sources ==
* : Chapter $1$: Sets and mappings: $\S 1.1$: The need for logic: Exercise $(7) \ \text{(i)}$
Category:Examples of Use of Quantifiers
Quantifier/Examples/Existence of Multiplicative Identity

== Example of Use of Quantifiers ==
Let $x$ and $y$ be in the natural numbers.
:$\exists x: \forall y: \exists z: \paren {y > z} \implies y = x z$
means:
:There exists a natural number $x$ such that every natural number $y$ equals the product of $x$ with a natural number $z$.
This is shown to be true by setting $x = 1$.
== Sources ==
* : Chapter $1$: Sets and mappings: $\S 1.1$: The need for logic: Exercise $(7) \ \text{(iv)}$
Category:Examples of Use of Quantifiers
Quantifier/Examples/Existence of x^y = y^x

== Example of Use of Quantifiers ==
Let $x$ and $y$ be in the natural numbers.
:$\exists x: \exists y: \paren {x \ne y} \land x^y = y^z$
means:
:There exist distinct natural numbers $x$ and $y$ such that $x^y$ equals $y^x$.
This is true:
:$2^4 = 16 = 4^2$
== Sources ==
* : Chapter $1$: Sets and mappings: $\S 1.1$: The need for logic: Exercise $(7) \ \text{(iii)}$
Category:Examples of Use of Quantifiers
Quantifier/Examples/Square of Sum

== Example of Use of Universal Quantifier ==
:$\forall x: x \in \R \implies \paren {x + 2}^2 = x^2 + 4 x + 4$
means:
:Every real number $x$ satisfies the equation $\paren {x + 2}^2 = x^2 + 4 x + 4$.
== Sources ==
* : $\S 1$: Some mathematical language: Variables and quantifiers
Category:Examples of Use of Quantifiers
Quantifier Free Formula is Preserved by Superstructure

== Theorem ==
Let $\MM, \NN$ be $\LL$-structures such that $\MM$ is a substructure of $\NN$.
Let $\map \phi {\bar x}$ be a quantifier-free $\LL$-formula, and let $\bar a \in\MM$.
Then $\MM \models \map \phi {\bar a}$ $\NN \models \map \phi {\bar a}$.
== Proof ==
The proof is done by induction on complexity of formulas.
Note that since interpretations of terms with parameters from $\MM$ are preserved when passing to superstructures, we have that $\map {t^\MM} {\bar a} = \map {t^\NN} {\bar a}$ whenever $t$ is an $\LL$-term and $\bar a$ is in $\MM$.
First, we verify the theorem for atomic formulas. This is the base for the inductive proof.
Suppose $\phi$ is $t_1 = t_2$ for terms $t_1$ and $t_2$:
We have $\MM \models \map \phi {\bar a}$ $\MM \models \map {t_1} {\bar a} = \map {t_2} {\bar a}$.
The of this holds $\map {t_1^\MM} {\bar a} = \map {t_2^\MM} {\bar a}$.
By the note above, this in turn holds $\map {t_1^\NN} {\bar a} = \map {t_2^\NN} {\bar a}$, which is equivalent to $\NN \models \map \phi {\bar a}$.
Suppose $\phi$ is $R(t_1, \dots, t_n)$ where $R$ is a relation symbol and each $t_i$ is a term:
We have:
:$\MM \models \map \phi {\bar a}$ iff $\paren {\map {t_1^\NN} {\bar a}, \dots, \map {t_n^\NN} {\bar a} } \in R^\MM$
Since $\MM$ is a substructure of $\NN$, the interpretation of $R$ in $\NN$ must extend $R^\MM$, so the right side of this statement is equiavlent to:
:$\paren {\map {t_1^\NN} {\bar a}, \dots, \map {t_n^\NN} {\bar a} } \in R^\NN$
By the note above, this in turn is equivalent to:
:$\paren {\map {t_1^\NN} {\bar a}, \dots, \map {t_n^\NN} {\bar a} } \in R^\NN$
which is the same as:
:$\NN \models \map \phi {\bar a}$
Having verified the theorem for the atomic formulas, we proceed with the inductive step of the proof.
Suppose the result holds for $\psi$, and consider $\neg \psi$:
We have $\MM \models \neg \map \psi {\bar a}$ $\MM \not \models \map \psi {\bar a}$.
By the inductive hypothesis, the right side of this statement is equivalent to $\NN \not\models \map \psi {\bar a}$, and so the result follows.
Suppose the result holds for $\psi_1$ and $\psi_2$.#
Consider $\psi_1 \wedge \psi_2$:
We have $\MM \models \map {\psi_1} {\bar a} \wedge \map {\psi_2} {\bar a}$ $\MM \models \map {\psi_1} {\bar a}$ and $\MM \models \map {\psi_2} {\bar a}$.
By the inductive hypothesis, the of this is equivalent to $\NN \models \map {\psi_1} {\bar a}$ and $\NN \models \map {\psi_2} {\bar a}$.
The result follows, completing the proof.
Category:Model Theory for Predicate Logic
Quantifier has Unique Scope

== Theorem ==
Let $\mathbf A$ be a WFF of predicate logic.
Let $Q$ be an occurrence of a quantifier in $\mathbf A$.
Then there exists a unique well-formed part of $\mathbf A$ which (omitting outermost parentheses) begins with that occurrence $Q$.
This unique well-formed part of $\mathbf A$ is called the scope of the occurrence of $Q$.
== Proof ==
=== Existence ===
First, from the rules of formation of predicate logic, we have that whenever a quantifier is included in a WFF, it appears in the form:
:$\paren {Q x: \mathbf B }$
where $\mathbf B$ is itself a WFF.
Hence it is clear that $\paren {Q x: \mathbf B}$ is a well-formed part of $\mathbf A$ which begins with $Q$.
=== Uniqueness ===
Now we prove that this well-formed part is unique.
Suppose $\mathbf B$ and $\mathbf C$ are both well-formed parts of $\mathbf A$ which begin with the given occurrence of $Q$.
Since $\mathbf B$ and $\mathbf C$ both begin with the same $Q$, neither one can be the prefix of the other, by Prefix of WFF of Predicate Logic is not WFF.
Therefore, $\mathbf B$ and $\mathbf C$ are necessarily the same.
Hence the result.
== Sources ==
* : $\S 2.3$: Theorem $2.3.1$
Category:Predicate Logic
Quantity of Positive Integers Divisible by Particular Integer

== Theorem ==
Let $d$ be a positive integer. 
Let $x \ge 1$ be a real number.
Then: 
:$\ds \sum_{n \le x, \, d \divides n} 1 = \floor {\frac x d}$
That is: 
:there are $\floor {\dfrac x d}$ natural numbers less than or equal to $x$ that are divisible by $d$. 
== Proof ==
Consider the sum: 
:$\ds \sum_{n \le x, \, d \divides n} 1$
Note that a natural number $n \le x$ is divisible by $d$ :
:there exists a natural number $k$ such that $n = d k$.
So we are counting the natural numbers $k$ such that $d k \le x$. 
That is, the natural numbers $k$ such that: 
:$k \le \dfrac x d$ 
So:
Category:Analytic Number Theory