Bijections and Finite Sets: Proof by If And Only If

Here's a proof that requires a bit of subtlety...

Prove that a nonempty set $T_{1}$ is finite if and only if there is a bijection from  $T_{1}$ onto a finite set  $T_{2}$.

We can use the following:

• Definition     (a)  The empty set is said to have zero elements.
• (b)  If $n\in \mathbb{N}$,  a set S is said to have n elements if there exists a bijection from the set         $\mathbb{N}_{n}$ := {1, 2, ..., n} onto S.
• (c)  A set S is said to be finite if it is either empty or has n elements for some $n\in \mathbb{N}$.
• (d) A set S is said to be infinite if it is not finite.

Step 1: If
Assume there is a bijection from $T_{1}$ onto $T_{2}$. We're given that $T_{2}$ is finite. We know that by definition, every element of one set is paired with exactly one element of the other set, and every element of the other set is paired with exactly one element of the first set ($T_{1}$). Since $T_{2}$ is finite, $T_{1}$ is finite.

Step 2: Only If
Assume $T_{1}$ is finite set, which is nonempty as described in the original problem statement. This means that by the definition above, $T_{1}$ has n elements for some $n\in \mathbb{N}$ and there exists a bijection from the set $\mathbb{N}_{n}$ := {1, 2, ..., n} onto $T_{1}$. Let's call that bijection f.

We also are given that $T_{2}$ is a finite set. Assuming that $T_{2}$ is not empty, we know by the definition above that there exists a bijection from the set $\mathbb{N}_{n}$ := {1, 2, ..., n} onto $T_{2}$. Let's call that bijection g.

The composition $g\circ f$ would map $T_{1}$ into $T_{2}$, and since the composition of two bijections is a bijection, $g\circ f$ is a bijection from $T_{1}$ onto $T_{2}$.

QED 

Exponents and Factorials: Mathematical Induction Proof

Easy one here...

Prove that $2^{n}< n!$ for all $n\geq 4$, $n\in \mathbb{N}$.

Step 1: Show P(4) is true.
Our base case is k = 4. $2^{4}<4!$ $\Rightarrow 16 < 24$. OK.

Step 2: Show that (if we assume P(k) is true), P(k+1) is true. (Induction hypothesis). This means we should have $2^{k+1}<(k+1)!$.

$$2^{k+1}<(k+1)!$$
can be rewritten as
$$2\cdot2^{k}<(k+1) k!$$

For $k\geq 4$, 2 < k + 1, and by the induction hypothesis, we assume $2^{k}< k!$, so we can see that
$$2^{n}< n!$$
for all $n\geq 4$, $n\in \mathbb{N}$

QED

Composition Of Two Bijections Is a Bijection: Proof

A common exercise from an "Introduction To Real Analysis" course is to show that

1. if $f: A\rightarrow B$ is a bijection, and
2. if $g: B\rightarrow C$ is a bijection

then the composite $g\circ f$ is a bijective map of A onto C.

We just need to show that $g\circ f: A\rightarrow C$ is one to one and onto.

$$g\circ f = g(f(x))$$
$$f(x)=y     (y\in B)$$
$$g(y)=z    (z\in C)$$

First, show the composite is injective (one to one):
by 1, we know that $f(x_{1})=f(x_{2})$ means $x_{1}=x_{2}$ (f is one to one - injective).
by 2, we know that $g(f(x_{1}))=g(f(x_{2}))$ means $f(x_{1})=f(x_{2})$ (g is one to one - injective).

a) So, we see that $g(f(x_{1}))=g(f(x_{2}))$ means that  $x_{1}=x_{2}$, which means that $g\circ f$ is       an injective (one to one) map of A onto C.

Second, show the composite is surjective (onto):
by 1, we know that for any $b\in B$ there exists at least one $x\in A$ such that $f(x)=b$.
by 2, we know that for any $c\in C$ there exists at least one $b\in B$ such that $g(b)=c$.

b) So, we see that for any$c\in C$ there exists at least one  $x\in A$ such that $g(f(x))=c$, which means that    $g\circ f$ is a surjective (onto) map of A onto C.

With the results a) and b) we see that the composite $g\circ f$ is indeed a bijective map of A onto C.

QED

Momentum-Space Wavefunction - Expectation Values: Quantum Mechanics (Griffiths)

In D. J. Griffiths' "Introduction to Quantum Mechanics: 1st Edition," Problem 3.51 on page 117 is a 3-star problem. In the second edition, it's problem 3.12 on page 109, and is not a starred problem at all. I attribute this to being given more information about $\Psi_{x,t}$ in terms of $\Phi_{p,t}$ in the second edition. In the first edition, we are working from knowledge of the form of $\Phi$ alone. Since one is a Fourier transform of the other and vice versa, we can convert the integral used to evaluate $< x>$  from one with an integrand function containing $\Psi$ and x to one containing $\Phi$ and the x operator.

$$< x> = \int \Phi^{*}\left ( -\frac{\hbar}{i}\frac{\partial }{\partial p} \right )\Phi dp$$

In the first edition, we're given

$$\Phi(p,t)=\frac{1}{\sqrt{2\pi \hbar}}\int_{-\infty}^{\infty}e^{-ipx/\hbar}\Psi(x,t)dx        (1)$$

We know $<x>=\int_{-\infty}^{\infty}x|\Psi(x,t)|^{2}dx$, so we just need to show that

$$\int \Phi^{*}\left ( -\frac{\hbar}{i}\frac{\partial }{\partial p} \right )\Phi dp=\int x|\Psi(x,t)|^{2}dx$$

Easier said than done, but here we go. It's not too bad, actually...

$$\int \Phi^{*}\left ( -\frac{\hbar}{i}\frac{\partial }{\partial p} \right )\Phi dp$$

Using (1) gives

$$ \int \left [ \frac{1}{\sqrt{2\pi \hbar}}\int e^{ipx^{'}/\hbar}\Psi^{*}dx^{'} \right ]\left ( -\frac{\hbar}{i} \frac{\partial }{\partial p}\right )\left [ \frac{1}{\sqrt{2\pi \hbar}}\int e^{-ipx/\hbar}\Psi dx \right ]dp$$

Simplifying a little...

$$\int \left [ \frac{1}{\sqrt{2\pi \hbar}}\int e^{ipx^{'}/\hbar}\Psi^{*}dx^{'} \right ]\left [ \frac{1}{\sqrt{2\pi \hbar}}\int i\hbar\frac{\partial }{\partial p} e^{-ipx/\hbar}\Psi dx \right ]dp        (2)$$

Consider the integrand function in the second set of brackets. In particular,  $i\hbar\frac{\partial }{\partial p} e^{-ipx/\hbar}$.

Using the fact that $\frac{\mathrm{d} }{\mathrm{d} p}\left ( e^{-ipx/\hbar} \right )= -\frac{ix}{\hbar} e^{-ipx/\hbar}$ we can rewrite (2) using $x e^{-ipx/\hbar}$ in place of $i\hbar \frac{\partial }{\partial p}\left ( e^{-ipx/\hbar} \right )$ ...

$$\int \left [ \frac{1}{\sqrt{2\pi \hbar}}\int e^{ipx^{'}/\hbar}\Psi^{*}dx^{'} \right ]\left [ \frac{1}{\sqrt{2\pi \hbar}}\int x e^{-ipx/\hbar} \Psi dx \right ]dp$$

Simplifying further and using Fubini's Theorem gives

$$\frac{1}{2\pi \hbar}\int \int \int \left [ e^{ipx^{'}/\hbar}\Psi^{*} x e^{-ipx/\hbar}\Psi \right ]dx^{'}dxdp     (3)$$

Letting $y = \frac{p}{\hbar}$ and simplifying the integrand further gives

$$\frac{1}{2\pi }\int \int \int \left [ e^{-i(x-x^{'})/y} \Psi^{*} x \Psi \right ]dx^{'}dxdy     (4)$$

Evaluating the y-integral first...

$$\frac{1}{2\pi }\int e^{-i(x-x^{'})/y}dy = \delta (x-x^{'})$$

If you're not comfortable with this, check it for yourself by using Plancherel's Theorem to determine the Fourier transform of $\delta(x)$.

Now we have

$$\int \int \delta(x-x^{'})  \Psi^{*}(x^{'},t) x \Psi (x,t) dx^{'}dx     (5)$$

But $ \int \delta(x-x^{'}) \Psi^{*}(x^{'},t) = \Psi^{*} (x,t)$  (see Eq. 3.129 in the first edition and Eq. 3.52 in the second edition), so we have

$$\int \Psi^{*}x \Psi dx = \int x |\Psi (x,t)|^{2}dx$$

QED

Two Linear Algebra Proofs - Hermitian and Transpose: Quantum Mechanics (Griffiths)

Problem A.11 from D.J. Griffiths' "Introduction to Quantum Mechanics: 2nd Edition" asks the student to prove a few properties from linear algebra. The properties aren't all that difficult to prove, but give some students trouble because these properties are generally used by students to prove other relationships in linear algebra.

The first property: The transpose of a product is the product of the transposes in reverse order...

$$\widetilde{\mathbf{ST}}=\widetilde{\mathbf{T}}\widetilde{\mathbf{S}}$$

$$\widetilde{\mathbf{ST}}$$

$$=(ST)_{ji}$$

$$=\sum_{k=1}^{n}S_{jk}T_{ki}$$

$$=\sum_{k=1}^{n}\widetilde{S}_{kj}\widetilde{T}_{ik}$$

$$=\sum_{k=1}^{n}\widetilde{T}_{ik}\widetilde{S}_{kj}$$

$$=\mathbf{\widetilde{T}}\mathbf{\widetilde{S}}$$

QED

The second property: The Hermitian conjugate of a product is the product of the Hermitian conjugates in reverse order...

$$(\mathbf{ST})^{\dagger }=\mathbf{T}^{\dagger }\mathbf{S}^{\dagger }$$

$$(\mathbf{ST})^{\dagger }$$

$$=(\widetilde{\mathbf{ST}})^{*}$$

$$=(\mathbf{\widetilde{T}}\mathbf{\widetilde{S}})^{*}$$

$$=\mathbf{\widetilde{T}}^{*}\mathbf{\widetilde{S}}^{*}$$

$$=\mathbf{T}^{\dagger }\mathbf{S}^{\dagger }$$

QED

Proof of Plancherel's Theorem: Quantum Mechanics (Griffiths)

Problem 2.20 from chapter two of David J. Griffiths' "Introduction to Quantum Mechanics: 2nd Edition" takes the student through a step-by-step proof of Plancherel's Theorem:

$$f(x)=\frac{1}{\sqrt{2\pi }}\int_{-\infty}^{\infty}F(k)e^{ikx}dk \Leftrightarrow F(k)=\frac{1}{\sqrt{2\pi }}\int_{-\infty}^{\infty}f(x)e^{-ikx}dx$$

where F(k) is the Fourier transform of f(x), and f(x) is the inverse Fourier transform of F(k).

Step 1
First, Griffiths asks us to show that a function f(x) on the interval [-a, a] expanded as a Fourier series

$$f(x)=\sum_{n=0}^{\infty}[a_{n}sin(n\pi x/a)+b_{n}cos(n\pi x/a)]               [1]$$     

          

can be written equivalently as

$$f(x)=\sum_{n=-\infty}^{\infty}c_{n}e^{in\pi x/a}      [2]$$

and to write $c_{n}$ in terms of $a_{n}$ and $b_{n}$. 

If we look at n = 0, [1] --> $f(x) = b_{0}$

Now, use Euler's identity $e^{i\phi }=cos(\phi)+isin(\phi)$ to rewrite [1] as

$$f(x)=b_{0}+\sum_{n=1}^{\infty}\frac{a_{n}}{2i}(e^{in\pi x/a}-e^{-in\pi x/a})+\sum_{n=1}^{\infty}\frac{b_{n}}{2}(e^{in\pi x/a}+e^{-in\pi x/a})$$

And, rearranging this a little...

$$f(x)=b_{0}+\sum_{n=1}^{\infty}\left \{ \frac{a_{n}}{2i}+\frac{b_{n}}{2} \right \}e^{in\pi x/a}+\sum_{n=1}^{\infty}\left \{ \frac{-a_{n}}{2i} +\frac{b_{n}}{2}\right \}e^{-in\pi x/a}           [3]$$

Evaluating [3] with n = 1 gives

$$f(x)=\frac{1}{2}\left ( -ia_{1} +b_{1}\right )e^{i\pi x/a}+\frac{1}{2}\left ( ia_{1} +b_{1}\right )e^{-i\pi x/a}         [4]$$

Now, let's evaluate [2] with both n = -1 and n = 1

n = 1:   

$$f(x)=c_{1}e^{i\pi x/a}$$

n = -1: 

$$f(x)=c_{-1}e^{-i\pi x/a}$$

These two terms look like the two terms in [4] if $c_{1}$ = $\frac{1}{2}\left ( -ia_{1} +b_{1}\right )$ and  $c_{-1}$ = $\frac{1}{2}\left ( ia_{1} +b_{1}\right )$ (Remember, [3] sums on n from 1 to infinity, but [2] sums on n from negative infinity to positive infinity, so including the -n terms and the +n terms in [2] will give you the same two terms you get when evaluating [3] with only the +n terms.)

So, in general, $f(x)=\sum_{n=0}^{\infty}[a_{n}sin(n\pi x/a)+b_{n}cos(n\pi x/a)]$ can be written equivalently as

$$f(x)=\sum_{n=-\infty}^{\infty}c_{n}e^{in\pi x/a}$$
with $c_{n}$ = $\frac{1}{2}\left ( -ia_{n} +b_{n}\right )$, $c_{-n}$ = $\frac{1}{2}\left ( ia_{n} +b_{n}\right )$, and $c_{0}$ = $b_{0}$ 

QED

Step 2
Next, we are asked to show that

$$c_{n}=\frac{1}{2a}\int_{-a}^{+a}f(x)e^{-in\pi x/a}dx                [5]$$  

by using what Griffiths refers to as 'Fourier's Trick', which exploits the orthonormality of wavefunctions of different excited states.

The 'trick' is to multiply both sides of [2] by $\psi _{m}^{*}$ and integrate. Of course, in this case $\psi _{n}=e^{in\pi x/a}$.

$$f(x)=\sum_{n=-\infty}^{\infty}c_{n}e^{in\pi x/a}$$

$$\int_{-a}^{+a}\psi _{m}(x)^{*}f(x)dx = \sum_{n=-\infty}^{\infty}c_{n}\int_{-a}^{+a}\psi _{m}^{*}(x)\psi _{n}(x)dx=\sum_{n=-\infty}^{\infty}2ac_{n}\delta _{mn}=2ac_{m}$$

The orthonormality of $\psi_{m}^{*}$ and $\psi_{m}$ knocks out all the terms except for the n = m one, thus the appearance of the Kronecker delta.

So now we have

$$\int_{-a}^{+a}\psi_m^{*}(x)f(x)dx=2ac_{m}$$

Swapping indices (m for n) gives

$$\int_{-a}^{+a}\psi_n^{*}(x)f(x)dx=2ac_{n}$$

Finally, solving for $c_{n}$ and remembering that $\psi _{n}=e^{in\pi x/a}$ gives us

$$\frac{1}{2a}\int_{-a}^{+a}f(x)e^{-in\pi x/a}dx=c_{n}$$
QED

Step 3
Next, we are told to eliminate n and $c_{n}$ and use the new variables $k = (n\pi /a)$ and $F(k) = \sqrt{\frac{2}{\pi }}ac_{n}$ and show that [2] becomes

$$f(x)=\frac{1}{\sqrt{2\pi} }\sum_{n=-\infty}^{\infty}F(k)e^{ikx}\Delta k$$

and [5] (Step 2) becomes

$$F(k)=\frac{1}{\sqrt{2\pi} }\int_{-a}^{+a}f(x)e^{-ikx}dx$$

$F(k) = \sqrt{\frac{2}{\pi }}ac_{n}$ solved for $c_{n}$ gives $c_{n} = \frac{1}{a}F(k)\sqrt{\frac{\pi }{2}}$. Also, we know that $\Delta k=\frac{\Delta n\pi}{a}$ $\Delta n = 1$ so $\frac{\Delta k}{\pi }= \frac{1}{a}$

Substituting these results into [2] gives

$$f(x)=\frac{\Delta k}{\pi }\sqrt{\frac{\pi }{2}}\sum_{n=-\infty}^{\infty}F(k)e^{ikx}=\frac{1}{\sqrt{2\pi }}\sum_{n=-\infty}^{\infty}F(k)e^{ikx}\Delta k     QED$$

That takes care of f(x); Now for F(k)...

$$c_{n}=\frac{1}{2a}\int_{-a}^{+a}f(x)e^{-in\pi x/a}dx                [5]$$

But $c_{n} = \frac{1}{a}F(k)\sqrt{\frac{\pi }{2}}$, so [5] becomes

$$ \frac{1}{a}F(k)\sqrt{\frac{\pi }{2}}= \frac{1}{2a}\int_{-a}^{+a}f(x)e^{-in\pi x/a}dx$$

A little algebra and an appropriate substitution gives

$$ F(k) = \frac{1}{\sqrt{2\pi}}\int_{-a}^{+a}f(x)e^{-ikx}dx       QED$$


Final Step
To complete the proof of Plancherel's Theorem, we are asked to take the limit a $\rightarrow\infty$ for the two results from Step 3

1st, f(x)...

$$\lim_{\Delta k\rightarrow 0}f(x)=\lim_{\Delta k\rightarrow 0}\frac{1}{\sqrt{2\pi }}\sum_{n=-\infty}^{\infty}F(k)e^{ikx}\Delta k = \frac{1}{\sqrt{2\pi }}\int_{-\infty}^{\infty}F(k)e^{ikx}dk $$

Now, F(k)...

$$\lim_{a\rightarrow \infty}F(k) = \lim_{a\rightarrow \infty}\frac{1}{\sqrt{2\pi}}\int_{-a}^{+a}f(x)e^{-ikx}dx = \frac{1}{\sqrt{2\pi}}\int_{-\infty}^{\infty}f(x)e^{-ikx}dx$$

So, finally we have Plancherel's Theorem as our result

$$f(x) = \frac{1}{\sqrt{2\pi }}\int_{-\infty}^{\infty}F(k)e^{ikx}dk \Leftrightarrow F(k) = \frac{1}{\sqrt{2\pi}}\int_{-\infty}^{\infty}f(x)e^{-ikx}dx$$

QED