{{short description|On integer partitions from monotonic functions}}
In [[combinatorial number theory]], theThe '''Lambek–Moser theorem''' describesis a mathematical description of partitions of the [[natural number]]s into two [[Complement (set theory)|complementary sets]]. For instance, it applies to the partition of numbers into [[even number|even]] and [[odd number|odd]], or into [[prime number|prime]] and non-prime (one and the [[composite number]]s). There are two parts to the Lambek–Moser theorem. One part states that any two [[monotonic function|non-decreasing]] integer functions that are inverse, in a certain sense, can be used to split the natural numbers into two complementary subsets, and the other part states that every complementary partition can be constructed in this way. When a formula is known for the {{nowrap|<math>n</math>th}} natural number in a set, the Lambek–Moser theorem can be used to obtain a formula for the {{nowrap|<math>n</math>th}} number not in the set.
The Lambek–Moser theorem belongs to [[combinatorial number theory]]. It is named for [[Joachim Lambek]] and [[Leo Moser]], who published it in 1954,{{sfn|Lambek|Moser|1954}} and should be distinguished from an unrelated theorem of Lambek and Moser, later strengthened by Wild, on the number of [[primitive Pythagorean triple]]s.{{sfn|Wild|1955}} It extends Rayleigh's theorem, which describes complementary pairs of [[Beatty sequence]]s, the sequences of rounded multiples of irrational numbers.
