Sets in Python¶

Level: 101 · for anyone who has read this chapter and writes Python

One line: Every idea in this chapter is one line of Python: extensionality is ==, Zermelo's separation is a set comprehension, the operations are | & - ^, and the one missing operator, the complement, is missing for the reason the mathematics gives: it needs a universe.

This page is the bridge. The math library owns the idea; the language libraries own the call. How Python's set actually behaves, hashing, True == 1 == 1.0, operators against methods, frozenset, dict views, Counter, and the notes on sets that turned out to be wrong, is the Python library's page A set is a hash table ↗, which this page used to hold. Rust and ABAP have their own pages, linked at the end.

Each idea, found in the language¶

The chapter says	Python says	Why it is the same thing
a set is its members (extensionality)	`{2, 5} == {5, 2}`, `{1, 1, 2} == {1, 2}`	`==` on sets compares membership and nothing else
there is one empty set	`set()`, however it was built	`{}` was already taken by the empty dict
a rule cuts a subset out of a set you have (separation)	`{x for x in source if rule(x)}`	a comprehension always has a source, so Russell's "every x" cannot be written
∪ ∩ ∖ △ are or, and, and-not, exclusive or (the algebra)	`a \\| b`, `a & b`, `a - b`, `a ^ b`	each tests one member at a time
A′ needs a universe	no operator; write `U - a`	"not in A" means nothing until U is named
A ⊆ B, A ⊂ B	`a <= b`, `a < b`	`<` is proper subset, a partial order, which is why `sorted()` on sets fails
chained △ keeps odd counts	`s1 ^ s2 ^ s3`	△ is a group operation in which every set cancels itself
\|A\|, the cardinality	`len(a)`	counting members, with repeats already gone

What the program prints¶

Verified output of python_sets.py — regenerated by tools/run_examples.py, never hand-typed.

1. EXTENSIONALITY IS ==
   {2, 5} == {5, 2}       True   order is not membership
   {1, 1, 2} == {1, 2}    True   neither is repetition
   three empty sets built three ways, all equal: True
   there is one empty set; it is written set(), because {} is a dict

2. SEPARATION IS THE COMPREHENSION
   {n for n in range(1, 21) if n is prime} = {2, 3, 5, 7, 11, 13, 17, 19}
   The rule always draws from an existing source. Python has no syntax
   for 'every x such that ...' with no source, so it cannot state Russell.

3. THE OPERATIONS ARE OPERATORS
   A = {1, 2, 3, 4}, B = {1, 4, 5}, U = {1, 2, 3, 4, 5, 6}
     A ∪ B   A | B    {1, 2, 3, 4, 5}
     A ∩ B   A & B    {1, 4}
     A ∖ B   A - B    {2, 3}
     A △ B   A ^ B    {2, 3, 5}
     A′      U - A    {5, 6}
     A ⊆ B   A <= B   False
     3 ∈ A   3 in A   True
   The complement has no operator: 'not in A' needs a universe, so
   the code must name U and write U - A.

4. CHAINED ^ KEEPS WHAT OCCURS AN ODD NUMBER OF TIMES
   {0, 1, 2, 3, 4} ^ {2, 3, 4} ^ {2, 5} = {0, 1, 2, 5}
   occurrences: 0:1  1:1  2:3  3:2  4:2  5:1   odd ones: {0, 1, 2, 5}
   2 is in all three sets and stays: ^ is exclusive or, and it is a group
   operation in which every set cancels itself (the algebra of sets, section 7).

Flashcards¶

Two decks cover Python sets, and both live here so they can be imported from one place: python_sets.txt is the Python behaviour, from the Python library's page, and the chapter's other decks are on what is a set?, the definition on trial and the algebra of sets. Import with File → Import.

Po polsku, w skrócie¶

Każda idea z tego rozdziału to jedna linijka Pythona. Ekstensjonalność to ==: zbiory o tych samych elementach są równe, bez względu na kolejność i powtórzenia. Aksjomat wyróżniania Zermela to wyrażenie {x for x in źródło if warunek(x)}, które zawsze ma źródło, więc paradoksu Russella nie da się w nim zapisać. Suma, iloczyn, różnica i różnica symetryczna to |, &, - i ^. Dopełnienia brakuje z tego samego powodu co w matematyce: potrzebuje uniwersum, więc piszemy U - a.

Szczegóły zachowania typu set w Pythonie (haszowanie, operatory a metody, frozenset, widoki słowników, Counter) są w bibliotece Pythona, na stronie „A set is a hash table”.

Auf Deutsch: Stichwörter¶

Pythons set ist eine endliche Menge mit den Mengenoperationen als Operatoren; was es kann und wo es von der Mathematik abweicht.

Stichwörter: Menge in Python, set, frozenset, Hashbarkeit, Operatoren | & − ^, Teilmengentest, Mengenbildung (comprehension).

Run it yourself¶

From the root of your clone of this repository:

python3 04_Sets/python_sets/examples/python_sets.py