Factory for arbitrarily high-order operations
Since this is tagged "functional-programming" I decided to take the functional approach. However, take note that Python isn't necessarily a "functional language," so it's not going to be as efficient as the iterative approach you were using. However, it looks like you're doing this from a theoretical standpoint, so you may find this interesting.

import functools

def iterate(f, x, n):
    """ Applies f n times to x. """
    if n == 0:
        return x
    else:
        return f(iterate(f, x, n - 1))

def iterate_for(f, x, n):
    """ Applies f n times to x, without recursion. """
    for _ in range(n):
        x = f(x)
    return x

def increase_order(f):
    return lambda x, n: iterate(functools.partial(f, x), x, n - 1)

def op_of_order(f, order):
    return iterate(increase_order, f, order)

def test():
    add = lambda x, y: x + y

    mul = increase_order(add)
    assert mul(3,5) == 15
    assert mul(7,3) == 21

    exp = increase_order(mul)
    assert exp(3,2) == 9
    assert exp(7,2) == 49

    tetract = op_of_order(add, 3)
    assert tetract(5,2) == 3125
    #assert tetract(7,2) == 823543
    #assert tetract(4,3) == 4294967296

if __name__ == "__main__":
    test()


The biggest change here was the abstraction of the loop you have in both increase_order and op_of_order into a function called iterate, inspired by Haskell's iterate function. I've provided both a recursive and non-recursive version for understanding and efficiency (Python has a no tail-call optimization) during testing.

In my opinion, both increase_order and op_of_order are much clearer when written this way, making it easier to see just what both functions actually do.