Introduction to Proof via Linear Algebra
Linear Algebra - As an Introduction to Abstract Mathematics (direct link to pdf here) seems like a good shout. I haven't looked through it thoroughly, but the following bold claim is made in the intro:
In the setting of Linear Algebra, you will be introduced to abstraction. As the theory of Linear Algebra is developed, you will learn how to make and use definitions and how to write proofs.
Indeed, at the end of each chapter are special "Proof-Writing Exercises".
Cherry-pick what you need from multiple books, if you need to. But here are some books that satisfy your requirements.
If you want a thorough, from the roots, introduction to higher mathematics, read
- Basic Concepts of Mathematics, by E. Zakon, which is freely available in pdf. (Consider donating.)
It covers logic, naive set theory, the real numbers and linear algebra. It is a great book, but unfortunately it is a bit less well-known. From the author:
This book helps the student complete the transition from purely manipulative to rigorous mathematics.
For a more standard course in linear algebra, consider
- Linear Algebra as an Introduction to Abstract Mathematics.
I would complement this book with Basic Concepts of Mathematics for the logic and set theory basics.
Not about linear algebra, but you should take a look at the
- Book of proofs, by R. Hammack.
It is sort of a cookbook. For instance, one section is entitled 'How to prove $A \subseteq B$?'