classification
Title: frozenset type breaks ZFC
Type: behavior Stage: resolved
Components: Interpreter Core Versions: Python 3.7
process
Status: closed Resolution: not a bug
Dependencies: Superseder:
Assigned To: Nosy List: george-shuklin, rhettinger, steven.daprano
Priority: normal Keywords:

Created on 2019-04-02 14:57 by george-shuklin, last changed 2019-04-02 15:30 by steven.daprano. This issue is now closed.

Messages (4)
msg339340 - (view) Author: George Shuklin (george-shuklin) Date: 2019-04-02 14:57
ZFC (https://en.wikipedia.org/wiki/Zermelo%E2%80%93Fraenkel_set_theory) defines numbers as nested empty sets.

0 is {}
1 is {{}}
2 is {{{}}}

Sets can not be nested in python (as they are mutable), so next best type is frozen set. Unfortunately, nested sets are equal to each other no matter how deep they are nested. This behavior means that 3==2, and it breaks all set operations for ZFC.

Minimal example:

frozenset({frozenset()})
>>> x=frozenset()
>>> y=frozenset(frozenset())
>>> x is y
True
msg339346 - (view) Author: Raymond Hettinger (rhettinger) * (Python committer) Date: 2019-04-02 15:12
The code in the minimal example isn't creating nested frozensets.  Instead, if is converting one frozenset into another (because frozenset takes an iterable as an argument).  This is no different than list(list(list())) producing a single list rather than a nested list.

Here's how to build nested frozensets:

>>> x = frozenset({})
>>> y = frozenset({x})
>>> z = frozenset({y})
>>> x
frozenset()
>>> y
frozenset({frozenset()})
>>> z
frozenset({frozenset({frozenset()})})
>>> x is y
False
>>> x == y
False
msg339347 - (view) Author: Steven D'Aprano (steven.daprano) * (Python committer) Date: 2019-04-02 15:27
Python is a programming language, and we're probably not going to care too much about compliance with ZFC set theory unless there is good *practical* and not theoretical reason to care. That's not to say that we want to break ZFC, only that if we do so, we won't lose any sleep over it.

And it certainly won't mean that 3 == 2 as you suggest.

But fortunately, we haven't violated ZFC and this is not a bug in Python.

You've made two serious errors in your code. The first is that your second line of code:

    y = frozenset(frozenset())

doesn't do what you think it does. It doesn't create a [frozen]set of a [frozen]set, (a nested set). It creates a simple, non-nested set. Printing the value of y in the interactive interpreter would have shown you that it was a plain old non-nested empty set:

    py> print(y)
    frozenset()

The code you want is something like:

   y = frozenset([frozenset()])

for reasons which I hope will become clear. The code you are actually using is equivalent to:

    temp = set()  # mutable (non-frozen)
    for x in frozenset():  # loop over the contents of the inner frozenset
        temp.add(x)  # since that inner set is empty, nothing gets added
    y = frozenset(temp)  # an empty frozenset


Your second error is using the `is` operator when you are talking about equality. The `is` operator tests for object identity, not equality, and the Python interpreter reserves the right to re-use objects when appropriate. In this case, the interpreter sees that it has two empty frozensets, and since they are indistinguishable and immutable, it saves memory by using the same object for both.

(To put it another way: the interpreter caches certain immutable objects to save memory, and empty frozensets happen to be included.)

Of course had you used `==` rather than `is` you would have got the same result, since two empty sets are equal, but the point still stands that you shouldn't use object identity when you mean equality.

Once we fix the bugs in your code, we see that ZFC is saved:

py> x = frozenset()  # empty set
py> y = frozenset([frozenset()])  # non-empty set
py> print(len(x), len(y))
0 1
py> x == y
False
msg339348 - (view) Author: Steven D'Aprano (steven.daprano) * (Python committer) Date: 2019-04-02 15:30
(Aside: that's interesting, normally if I try to post a comment to an issue, and somebody else edits it in the meantime, the message doesn't get posted and I get a error message saying that the page has been edited. This time I did not.)
History
Date User Action Args
2019-04-02 15:30:59steven.dapranosetmessages: + msg339348
2019-04-02 15:27:34steven.dapranosetnosy: + steven.daprano
messages: + msg339347
2019-04-02 15:12:54rhettingersetstatus: open -> closed
resolution: not a bug
messages: + msg339346

stage: resolved
2019-04-02 14:59:32xtreaksetnosy: + rhettinger
2019-04-02 14:57:33george-shuklincreate