In electromagnetism, how do we know that either $F^{\mu\nu}$ or $A^\mu$ is a tensor? In special relativity the partial derivative $\partial_\mu$ is a tensor. Now if some function $A^\mu$ was a tensor, then also the quantitiy $F^{\mu\nu}=\partial^\mu A^\nu - \partial^\nu A^\mu$ would be a tensor simply by composition.
Maxwell's equations can be broken down to a scalar potential $\phi$ and a vector potential $\vec{A}$. Now of course I can randomly construct a four potential $A^\mu=\left(\phi,\vec{A}\right)$ from these coincidentally 4 quantities which fits nicely in the 4-dimensional space-time formulation. But how do I know that $A^\mu$ is actually a tensor?! Is it just a phenomenological premise which cannot be proven? Given $A^\mu$ is a tensor and the relation of $F^{\mu\nu}$ to the electric and magnetic fields $\vec{E}$ and $\vec{B}$, I can obtain these fields in any inertial system by a simple Lorentz transformation of the entire thing $F^{\mu\nu}$.
But I need to start somewhere and know a priori that either $F^{\mu\nu}$ or $A^\mu$ is a tensor.
I hope that what I am asking is clear. So can it be proven, or is it just given by experiment?
 A: First, note that if $A^\mu$ transforms like the components of a vector, then so does $A'^\mu = A^\mu + \partial^\mu \chi$ for any scalar field $\chi$ - therefore, the tensorial nature of the 4-potential is gauge-invariant.
Second, note that in the Lorenz gauge, we have
$$\partial_\alpha \partial^\alpha A^\beta\equiv \square A^\beta  = \mu_0 J^\beta$$
Since $\square \equiv \partial_\alpha\partial^\alpha$ transforms like a scalar operator under Lorentz transformations, it follows that $A^\beta$ shares the same transformation properties as $J^\beta$.  
Lastly, we know $J^\beta$ transforms like a four-vector because the continuity equation $\partial_\beta J^\beta = 0$ holds in all reference frames.  Letting primes denote transformed quantities, 
$$\partial_\beta J^\beta- \partial'_\alpha J'^\alpha = \partial_\beta J^\beta - \left(\Lambda^{-1}\right)_\alpha^{\ \ \beta} \partial_\beta J'^\alpha = \partial_\beta \left(J^\beta - \left(\Lambda^{-1}\right)_\alpha^{\ \ \beta} J'^\alpha\right) = 0 $$
which implies that
$$ J'^\alpha = \Lambda^\alpha_{\ \ \beta} J^\beta + C^\alpha$$
for some divergence-free field $C^\alpha$.  On physical grounds we can demand that if the 4-current vanishes in one frame then in vanishes in every frame (a Lorentz boost can't create charge or current density out of nowhere), implying that $C^\alpha = 0$ and that $J^\beta$ transforms like a 4-vector.
Therefore, $A^\beta$ transforms like a vector in the Lorenz gauge, and by extension, in every gauge.
A: Well... $A^\mu$ is not really a tensor. The tensor form of that 4-potential is 
$$
A = A^\mu \partial_\mu,\ A^\mu \in \mathbb{R}
$$
So since you know that $\partial_\mu$ transform as a tensor, then $A$ is a tensor and you say that its components transform as a tensor. Let me explain this a little bit more:
Let's say I want to change coordinates $x \rightarrow y$, then
$$
\partial_\mu = \frac{\partial}{\partial x^\mu} \rightarrow \partial_\mu^{\ '} = \frac{\partial y^\nu}{\partial x^\mu}\frac{\partial}{\partial y^\nu}
$$
Therefore, since $A^\mu$ is just a function, under this change
$$
A(x) = A^\mu(x)\partial_\mu \rightarrow A^{'}(y) = A^{'\ \mu}(y)\frac{\partial y^\nu}{\partial x^\mu}\frac{\partial}{\partial y^\nu}, \quad A^{' \mu}(y) = A^\mu(x(y))
$$
And now you can make an abuse of language and say that $A^\mu$ is a tensor because it transforms as
$$
A^\mu(x) \rightarrow A^{'\ \mu}(y)\frac{\partial y^\nu}{\partial x^\mu}
$$
Now, how do you know that $A^\mu = (\phi , \vec{A})$ gives you the correct theory? As far as I know, that is due to a special relativity extension of classical lagrangian mechanincs. Classically you have that the interaction is given as
$$
S_{int} = \int dt\ L_{int} = -\int dt\ \phi
$$
Since $S$, the action, must be invariant under Lorentz tranformation you suggest that $\phi$ is the zero-th component of some 4-vector $A^\mu = (\phi, \vec{0})$ so now you can write
$$
S_{int} = -\int dt\ A^0 = -\int dx_0\ A^0 
$$
But this is not a Lorentz scalar, so you extend $A^\mu = (\phi, \vec{A})$ but without assuming that $\vec{A}$ is the usual magnetic vector potential. Therefore, 
$$
S_{int} = -\int dt\ A^0 \xrightarrow{extension} -\int dx_\mu\ A^\mu = -\int dt\ \frac{dx_\mu}{dt}A^\mu  
\tag1$$
This is now a Lorent scalar (so invariant) since the index $\mu$ is dummy now. Let's see what $\vec{A}$ is by developing Eq. (1) (recall $x_0 = dt$):
$$
S_{int} = -\int dt\ \phi(dt/dt) - \vec{A}(d\vec{x}/dt)
$$
The part on $\vec{A}$ is the usual interaction of the form current times magnetic potential if consider $\vec{A}$ like that and goes to lagrangian density formulation. By construction $A^\mu$ must be a 4-vector (tensor of rank 1) because if it wasn't that, $A^\mu dx_\mu$ wouldn't be a Lorentz scalar
A: One way to prove it could be finding how the fields transform. Another way to prove that $A^{\mu}$ is a tensor is by trying to construct the theory of a massless spin-1 particle by using the Lagrangian formalism, since the Lagrangian should be lorentz invariant and gauge invariant you would eventually find that you need the same form of the Maxwell tensor $F_{\mu\nu}$ that you gave before and that it has to transform as a Lorentz tensor.
A pretty good derivation of the above is given in M.Schwartz Quantum field theory and the standard model, at the end electromagnetism is also a field theory (A classical one). 
