Lower bound on size of proof that a list of integers is sorted
When talking about proofs, you need to explain three things: (1) formal proof system, (2) what you want to prove, (3) what you want to prove it from.

You seem to imply that item 3 should be $n$ different axioms, listing the contents of the array. In that case, you're right that you will need to invoke all axioms to prove that the list is sorted, in any consistent formal system.

Another reason why the proof will need to be of linear length is that item 2, what you want to prove, might be stated as $A[1] \leq A[2] \land A[2] \leq A[3] \land \cdots \land A[n-1] \leq A[n]$.

However, perhaps it is the case that item 3 is a description of the algorithm, and item 2 is something similar to Gilles's formulation, $\forall i \in [n-1], A[i] \leq A[i+1]$. In that case, if the proof system is strong enough (say ZFC), then you should be able to prove item 2 in $O(\log n)$ by starting with a general correctness proof for your algorithm, and then invoking it for your particular $n$. If your proof system is too weak to prove something like that, you might still be able to prove that the array is sorted in $O(\log^{O(1)})$; the relevant subject is known as bounded arithmetic.