I have attached a fix to this issue (and implicitly issue1062277).

This patch allows pickling self-referential sets by implementing a set.__reduce__ which uses states as opposed to ctor parameters.

Before:
>>> s=set([1,2,3])
>>> s.__reduce__()
(<class 'set'>, ([1, 2, 3],), None)
>>> len(pickle.dumps(s,1))
38

After:
>>> s=set([1,2,3])
>>> s.__reduce__()
(<class 'set'>, (), [1, 2, 3])
>>> len(pickle.dumps(s,1))
36

Basically what this does is: instead of unpickling the set by doing set([1,2,3]) it does s=set(); s.__setstate__([1,2,3]).
States are supported in all versions of pickle so this shouldn't break anything.
Creating empty data structures and then filling them is the way pickle does it for all mutable containers in order to allow self-references (with the exception of sets, of course).

Since memoization is performed after the object is created but before its state is set, pickling an object's state can contain references to oneself.

    class A:
        pass

    a=A()
    s=set([a])
    a.s=s

    s_=loads(dumps(s,1))
    next(iter(s_)).s is s_ # True

Note that this fix only applies for sets, not frozensets. Frozensets are a different matter, because their immutability makes it impossible to set their state. Self-referential frozensets are currently supported in my implementation of pickle4 using a trick similar to what tuples use. But the trick works more easily there because frozensets have their own opcodes, like tuples.

Also note that applying this patch makes Lib/test/pickletester.py:test_pickle_to_2x fail (DATA3 and DATA6 there contain pickled data of sets, which naturally have changed).
I'll upload a patch fixing this as well as adding one or more test for sets soon.