Q:

Let $A$ be a matrix, how to show that the left null space of $A$ is the orthogonal complement of the column space of $A$?

Let $N(A^\top)$ be the left null space of $A$
$N(A^\top) = \{x| A^\top x = 0\}$
Let $C(A)^\perp$ be the orthogonal complement of the column space of $A$.
$C(A)^\perp = \{y| y^\top x = 0 \text{ for all } x \text{ in the column space of A}\}$
I want to show that they are equal.
In particular, I want to show that
$C(A)^\perp \subseteq N(A^\top)$

Proof attempt:
Let $y \in C(A)^\perp$, then $y^\top x = 0$. 
Since $x$ is in the column space of $A$, there exists some vector $v$ such that $x = Av$, hence $y^\top (Av) = 0$. 
This is the same as writing $(y^\top A) v = 0$ or $(A^\top y)^\top v = 0$.

I want to conclude that this implies $A^\top y = 0$ and hence $y \in N(A^\top)$. But this doesn't necessarily have to be the case.
First, $v$ could be zero. 
Second, even if $v$ is not zero, you can have the case $(A^\top y)^\top = [-1, 1]$ and $v = [1, -1]^\top$, so $(A^\top y)^\top v = 0$ even though $A^\top y \neq 0$
Can someone please help?

A:

For $y\in C(A)^\perp$, we have $y^Tx=0$ for all $x\in C(A)$. As you say, each $x\in C(A)$ is of the form $x=Av$ for some $v$. Thus, $y^T(Av)=0$ for all $v$, and as you do we get $(A^Ty)^Tv=0$ for all $v$. 
Can you take it from here?

