Proof writing depends more on abstract reasoning than knowledge of arithmetics.
Of course, traditionally, it works that way. I would say, though, it's harmful a bit for the reason that the basic math curriculum is so boring, it puts off many brilliant minds.
Mandatory reference: TED Talk, Wolfram on Math Education. ;-)
I actually think that students could be exposed to proofs at an earlier level. At least, the ability to conceptualize a reasoned argument.
But I think to be able to do actual mathematical proofs, elementary school students may lack many of the tools and mechanisms that are necessary. Those tools being arithmetic and basic operations. By the same token, I think understanding basic CS principles and programming are necessary prior to understanding the theory.
Though it would be interesting for an Intro to CS course that used no actual language but was taught with only psuedocode. Teach basic concepts, hell even data structures, prior to tying the concepts to any one programming language.
