Paul Halmos è stato anche autore di noti testi universitari o di introduzione alla ricerca, con i quali ha riscosso un discreto successo editoriale (nell'ambito delle tirature - in genere piuttosto basse - dei libri tecnico-scientifici). Ha scritto monografie sulla teoria degli insiemi, spazi di Hilbert, algebra booleana, teoria spettrale, teoria della misura, spazi vettoriali. Nel 1985 ha pubblicato I want to be a Mathematician, in cui attraverso la propria biografia scientifica analizza il ruolo del matematico nel XX secolo.
L'introduzione della notazione iff in luogo di if and only if (con equivalente italiano sse in luogo di se e solo se), è talvolta erroneamente attribuita ad Halmos (egli stesso ha detto di averla presa altrove).
Gli viene attribuito l'uso del tombstone (il quadratino che si inserisce alla fine di una dimostrazione matematica) a significare Q.E.D., essendo egli stato il primo matematico di rilievo ad utilizzarlo. In effetti, tale simbolo, rappresentato con ∎ (Unicode U+220E), a volte viene chiamato l'halmos.
Opere
Teoria elementare degli insiemi, (Naive set theory), Van Nostrand, 1960 (USA), Feltrinelli, 1974 (IT), ISBN 9788807620072