"To apply the same reasoning the other way, if you aren't a Christian, what would be a situation which would convince you of the truth of Christianity?"
-And Jesus said unto them, Because of your unbelief: for verily I say unto you, If ye have faith as a grain of mustard seed, ye shall say unto this mountain, Remove hence to yonder place; and it shall remove; and nothing shall be impossible unto you. - Matthew 17:20
If mountains moved when Christians told them to, every time, and no one else could effectively command mountains to move, I think most of us non-believers would start going to church.
Alternatively, if the world looked like it was designed and regulated by a loving being, it would help. That might not promote Christianity specifically, but it would be a much better start than what we actually see.
2+2=4 is a truth about mathematics. It is not a truth about the world.
Truths in the world have no bearing on mathematical truths. While we learn mathematics from observations about the world, it is not from observation that mathematics derive truth. Mathematicians do not test theories empirically; such theories would become the domain of physics or biology or the like. Thus, the only evidence one could infer 2+2=3 from would be misleading mathematical evidence.
Since 2+2=4 is so simple, there are not too many people who could be effectively mislead in this way, and Eliezer is most likely not one of them. One could probably convince someone to believe a false mathematical formula if it were sufficiently complicated for the individual to have trouble understanding it, and it had a sufficiently crafty explanation.
Basically, believing 2+2=3 to be true would require the evidence necessary to believe in married bachelors: evidence that confuses the hell out of you effectively.
Some people are arguing that mathematics is not a priori. If so, then the situation with putting two pairs of apples together and getting 3 apples would be the appropriate type of evidence. If mathematics is a posteriori, the answer is thus quite simple.
Sorry if this is overly redundant with previous posts.