ProofWiki:Sandbox
Welcome to the Sandbox! Play safe and have fun!
Use Proofwiki:Sandbox/Template for experimental template Warning: The sandbox is not permanent. EXPECT ANYTHING YOU PUT HERE TO BE DELETED! |
Theorem
Let
- $ S = \begin{pmatrix} 0 & - 1 \\ 1 & 0 \end{pmatrix} \text{ and } T = \begin{pmatrix} 1 & 1 \\ 0 & 1 \end{pmatrix}$.
Then $S$ and $T$ generate the special linear group of order 2 over $\Z$.
Proof
Let
- $ g = \begin{pmatrix} a & b \\ c & d \end{pmatrix}$
be an element of $\text{SL}_2(\Z)$. Observe that
- $ T^n = \begin{pmatrix} 1 & n \\ 0 & 1 \end{pmatrix}$
so that
- $ T^n g = \begin{pmatrix} a + nc & b + nd \\ c & d \end{pmatrix}$.
Also note that $S^2 = -I$ and:
- $Sg = \begin{pmatrix} -c & -d \\ a & b \end{pmatrix}$.
We now describe an algorithm to reduce $g$ to the identity matrix only using multiplication by $S$ and $T$.
This will show that $g^{-1}$ can be written as a word in $S$ and $T$.
We can then take the inverse of this expression in $S$ and $T$ and it too will be a word in $S$ and $T$.
Recall $g = \begin{pmatrix} a & b \\ c & d \end{pmatrix}$.
If $c = 0$ then, since $\text{det}(g) = 1$, we must have $ad = 1$.
Thus $a = d = \pm 1$. In this case:
- $g = \pm\begin{pmatrix} 1 & b' \\ 0 & 1 \end{pmatrix} = \pm T^{b'}$
where $b' = \pm b$.
Since $S^2 = -I$ we either have $g = T^{b'}$ or $g = S^2T^{b'}$.
If $c \neq 0$ we proceed as follows.
Without loss of generality we may suppose $|a| \geq |c|$, for if $|a| < |c|$ we could apply $S$ to swap $a$ and $c$.
By the Division Algorithm, we can write $a = cq + r$ where $q,r \in \Z$ and $0 \leq r < |c|$.
Then $T^{-q}g$ has upper left entry $a - qc = r$ which is smaller than $|c|$.
Applying $S$ switches the rows (with a sign change), which then makes our lower left entry $-r$.
We've applied a combination of $S$ and $T$ to turn $g$ into a matrix where the absolute value of the lower left entry is strictly less than the one we started with.
If $r = 0$ then we're in our original case, and we know we can multiply by a multiple of $T$ and $S$ to get to the identity matrix.
Note that this process can have at most $r$ steps, since there are only $r$ natural numbers between $r$ and $0$.
Thus the process terminate in a finite number of steps.
Theorem
Let $\forall$ and $\exists$ denote the universal quantifier and existential quantifier respectively.
Then:
- $\forall x: P \left({x}\right) \dashv \vdash \neg \exists x: \neg P \left({x}\right)$
- everything is if and only if there does not exist anything that is not.
Proof
First, show $\forall x: P(x) \to \neg \exists x: \neg P(x)$ by contradiction.
(1) $\neg\left(\forall x: P(x) \to \neg \exists x: \neg P(x)\right)$ by assumption for RAA
(2) $\forall x: P(x) \wedge \exists x: \neg P(x)$ from 1 by negated implication
(3) $\forall x: P(x)$ from 2 by simplification
(4) $\exists x: \neg P(x)$ from 2 by simplification
(5) $\neg P(c)$ from 4 by existential instantiation
(6) $P(c)$ from 3 by universal instantiation
(7) $\forall x: P(x) \to \neg \exists x: \neg P(x)$ from 1 by RAA on 5 and 6
Therefore, if everything is $P$, then there does not exist anything which is not $P$.
Next, show $\neg \exists x \neg P \left({x}\right) \to \forall x: P(x)$ by magic...?