Game of Life rules in 14 lines of Python
For docstrings, if you're following the Sphinx documentation format (which it looks like you are), you can specify an explicit :return: field to document what exactly it is your function is returning. PEP-0257 has various other conventions for docstrings like leaving a blank line between the summary line and the rest of the docstring, if you're really interested.

In terms of functional programming, you could use some of Python's functional programming functions, e.g the builtins filter and map and also any functions from the functools module. Also, since you are already not mutating any of the variables in your program (as you wouldn't do when programming in a functional manner), you can use frozenset()s in place of where you're currently using sets, as frozen sets are explicitly immutable.

Here is an attempt at "functionifying" the step function. Since Python 3, you can put type hints in the signature of functions, and since Python 3.5 you can also use the typing module to define types in a formal way, which can allow for better static type-checking if you're using a typing-aware IDE. Since you're wanting to program in a functional way, I'm guessing this would be of more interest than usual.

from functools import reduce
from typing import Tuple, Set

Cell = Tuple[int, int]
Universe = Set[Cell]  # or even FrozenSet[Cell]

...

def step(universe: Universe) -&gt; Universe:
    """ Evaluate the next step in the Game of Life.

    :param universe: set of live cells in the universe. A live cell is the tuple (x,y)
    :return: the new universe after a single step in the game of life.
    """
    survivors = filter(lambda cell: is_survivor(universe, *cell), universe)
    neighbours = reduce(set.union, map(lambda cell: get_neighbours(*cell), universe))
    dead_neighbours = filter(lambda cell: cell not in universe, neighbours)
    births = filter(lambda cell: is_born(universe, *cell), dead_neighbours)
    return frozenset(survivors) | frozenset(births)


To be honest though, functional programming does not seem idiomatic in Python, even though it can be done; I would say your current code is pretty clear and idiomatic as is, using set comprehensions and such.