Gaifman's first result (obtained when he was a mathematics student) was the equivalence of context-free grammars and categorial grammars. He was Rudolf Carnap’s research assistant, working on the foundations of probability theory, and got his Ph. D. under Alfred Tarski (on infinite Boolean algebras). He worked on mathematical logic (mostly set theory, where he invented the technique of iterated ultrapowers, and models of Peano arithmetic), foundations of probability (where he defined probabilities on first-order and on richer languages), in philosophy of language and philosophy of mathematics, as well as in theoretical computer science. He held various permanent and visiting positions in mathematics, philosophy and computer science departments. While he was professor of mathematics at the Hebrew University, he taught courses in philosophy and directed the program in History and Philosophy of Science.
Gaifman's recent interests include foundations of probability, rational choice, philosophy of mathematics, logical systems that formalize aspects of natural reasoning, Frege and theories of naming.