The book I used in my 'proofs' class was "Doing Mathematics: An Introduction to Proofs and Problem Solving" by Steven Galovich, here on Amazon.
The class was called "Mathematical Structures", which is an apt name since the class wasn't solely about learning to prove things. It was learning to prove things in the context of learning about basic mathematical objects. It starts with basic logic, but after it introduces sets, relations, functions, equivlance relations and the like, it goes onto to develop the ideas of cardinality, including Cantor-Bernstein. It also has a couple other topics, like some basic combinatorics, the constructions of number systems, or looking at consequences of the field axioms.
It was a great introduction to what math is "really about" coming after some mostly computational calculus and linear algebra courses. The price is about $50, so it is a little more than you were looking for. But it is absolutely a book worth having.
