I highly recommend "A First Look at Rigorous Probability Theory" by Jeffrey Rosenthal.
This book is an introduction to probability with measure theory. The writing is very clear. When it comes to formality, the book carefully explains notational changes. It's also very good about providing intuitive imagery, while reinforcing the mathematical results with plenty of examples and counterexamples. I've never had a single book answer so many of my pre-existing questions during a casual 30-minute read.
Thanks to Jon Fintzi for the recommendation.
I have a rant about formal Probability, and Analysis in general, being deeply frustrating subjects. For example, if you use a more advanced result to prove a more basic one, you're "cheating". I suppose that's how foundational subjects are supposed to go, and "mathematical maturity" consists in inhibiting your intuitions; whereas my natural tendency is a coherentist one and has lots of room for "reckless" intuitions*. Symbol-crunching is best left to my computers, except when it can teach me something useful. I suppose this kind of mental weight-lifting is good exercise, though.
* - falsities will eventually lead to contradictions, as long as you do frequent tests; this is analogous to the way we find bugs in software. Some mathematicians feel superior about their epistemic modality, because proofs are infallible, don't you know?? I say, more power to them! But just as mathematicians are unsatisfied with results that have only been verified empirically, I am likewise distrustful of proofs that haven't been formalized and checked by computers.
mirror of this post