While searching for a way to work around the breakage of the Schwartzian transform in Python 3 (and the resulting awkwardness if you wish to use heapq or bisect, which do not yet have a key argument), I thought of the good old IEEE-754 NaN. Unfortunately, that shouldn't work since lexicographical comparisons shouldn't stop for something comparing False all the time. Nevertheless:

>>> (1, float("nan"), A()) < (1, float("nan"), A())
False
>>> (0, float("nan"), A()) < (1, float("nan"), A())
True

Instead of as in
>>> nan = float("nan")
>>> (1, nan, A()) < (1, nan, A())
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
TypeError: unorderable types: A() < A()

(As a side note, PyPy3 does not have this bug.)

Is the issue that:

  >>> (1, float('nan')) == (1, float('nan'))
  False

but

  >>> nan = float('nan')
  >>> (1, nan) == (1, nan)
  True

?

`nan != nan` therefore it might be expected that `(a, nan) != (a, nan)` [1]:

> The values float('NaN') and Decimal('NaN') are special. The are identical to themselves, x is x but are not equal to themselves, x != x. 

> Tuples and lists are compared lexicographically using comparison of corresponding elements. This means that to compare equal, each element must compare equal and the two sequences must be of the same type and have the same length.
> If not equal, the sequences are ordered the same as their first differing elements.

[1]: https://docs.python.org/3.4/reference/expressions.html#comparisons

btw, pypy3 (986752d005bb) is broken:

  >>>> (1, float('nan')) == (1, float('nan'))
  True

Python containers are allowed to let identity-imply-equality (the reflesive property of equality).  Dicts, lists, tuples, deques, sets, and frozensets all work this way.  So for your purposes,  you need to use distinct NaN values rather than reusing a single instance of a NaN.

The bug is that the comparison should throw a TypeError, but does not (for incomparable A).

Python core containers support the invariant:

    assert all(x in c for x in c)

See also:  http://bertrandmeyer.com/2010/02/06/reflexivity-and-other-pillars-of-civilization/

> Python containers are allowed to let identity-imply-equality (the reflesive property of equality).

Is it documented somewhere?

> Dicts, lists, tuples, deques, sets, and frozensets all work this way. 

Is it CPython specific behaviour?

It's not about equality.

    >>> class A: pass
    ... 
    >>> (float("nan"), A()) < (float("nan"), A())
    False

That < comparison should throw a TypeError, since NaN < NaN is False, in the same way that 0 < 0 is False here:

>>> (0, A()) < (0, A())
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
TypeError: unorderable types: A() < A()

It is about equality. `float('nan') != float('nan')` unlike `0 == 0`.

From msg221603: 

> If not equal, the sequences are ordered the same as their first differing elements.

The result of the expression: `(a, whatever) < (b, whatever)` is defined by 
`a < b` if a and b differs i.e., it is not necessary to compare other elements (though Python language reference doesn't forbid further comparisons. It doesn't specify explicitly the short-circuit behavior for sequence comparisons unlike for `and`, `or` operators that guarantee the lazy (only as much as necessary) evaluation).

FWIW, the logic for tuple ordering is a bit weird due to rich comparisons.   Each pair of elements is first checked for equality (__eq__).  Only if the equality comparison returns False does it call the relevant ordering operations (such as __lt__).   The docs get it right, "If not equal, the sequences are ordered the same as their first differing elements."

In short tuple ordering is different from scalar ordering because it always makes equality tests:
 
   a < b              calls           a.__lt__(b)

in contrast:

   (a, b) < (c, d)    is more like:   if a != c:  return a < c ...

> (a, b) < (c, d) is more like: if a != c: return a < c ...

except CPython behaves (undocumented?) as:

  b < d if a is c or a == c else a < c

the difference is in the presence of `is` operator (identity
comparison instead of `__eq__`). `nan is nan` therefore `b < d` is
called and raises TypeError for `(nan, A()) < (nan, A())` expression
where `a = c = nan`, `b = A()`, and `d = A()`.

But `(float("nan"), A()) < (float("nan"), A())` is False (no
TypeError) because `a is not c` in this case and `a < c` is called
instead where `a = float('nan')`, `b = A()`, `c = float('nan')`, and
`d = A()`. Plus `(a, b) < (c, d)` evaluation is lazy (undocumented?)
i.e., once `a < c` determines the final result `b < d` is not called.