(And here I thought I already responded to this...)
Of course you can battle each other! That's one of the main advantages that RPs have over Games. You are free to battle anyone. And if you two want to have a rivalry, go right ahead. And despite this, you can still have an NPC rival, if you'd like.