#!/usr/bin/env python3 """Set katas: Cunningham's first exercises, checked on every subset of {1, 2, 3}. Run: python3 set_katas.py The exercises of section 1.1 of Cunningham's Set Theory: A First Course are of three kinds: statements about arbitrary sets A, B, C, which the program checks on all 512 choices of subsets of {1, 2, 3}; truth sets, which it computes; and intervals of real numbers, which it computes exactly with rational endpoints, or checks on a grid of sample points where the exercise asks for an algebraic solution. A check is not a proof, and the page says which move each proof needs. """ import ast from fractions import Fraction from itertools import combinations, product from operator import and_, or_, sub, xor BASE = (1, 2, 3) SUBSETS = [frozenset(c) for r in range(4) for c in combinations(BASE, r)] INF = float("inf") def braces(s) -> str: return "{" + ", ".join(str(x) for x in sorted(s)) + "}" if s else "∅" # --------------------------------------------------------------------------- # Intervals with rational endpoints: just enough for the exercises # --------------------------------------------------------------------------- class Interval: def __init__(self, lo, lo_closed, hi, hi_closed): self.lo, self.lo_closed, self.hi, self.hi_closed = lo, lo_closed, hi, hi_closed def contains(self, x) -> bool: above = x > self.lo or (self.lo_closed and x == self.lo) below = x < self.hi or (self.hi_closed and x == self.hi) return above and below def empty(self) -> bool: return self.lo > self.hi or (self.lo == self.hi and not (self.lo_closed and self.hi_closed)) def __str__(self) -> str: def end(v): return "∞" if v == INF else ("−∞" if v == -INF else str(v)) return ("[" if self.lo_closed else "(") + f"{end(self.lo)}, {end(self.hi)}" + ("]" if self.hi_closed else ")") def intersect(a, b): if a.lo > b.lo or (a.lo == b.lo and not a.lo_closed): lo, lo_c = a.lo, a.lo_closed else: lo, lo_c = b.lo, b.lo_closed if a.hi < b.hi or (a.hi == b.hi and not a.hi_closed): hi, hi_c = a.hi, a.hi_closed else: hi, hi_c = b.hi, b.hi_closed return Interval(lo, lo_c, hi, hi_c) def union(a, b): """The union when it is one interval (the two overlap or touch).""" if intersect(a, b).empty() and not (a.hi == b.lo and (a.hi_closed or b.lo_closed)) \ and not (b.hi == a.lo and (b.hi_closed or a.lo_closed)): return None lo, lo_c = (a.lo, a.lo_closed) if a.lo < b.lo else (b.lo, b.lo_closed) if b.lo < a.lo else (a.lo, a.lo_closed or b.lo_closed) hi, hi_c = (a.hi, a.hi_closed) if a.hi > b.hi else (b.hi, b.hi_closed) if b.hi > a.hi else (a.hi, a.hi_closed or b.hi_closed) return Interval(lo, lo_c, hi, hi_c) def difference(a, b): """a ∖ b as the list of pieces: a ∩ (left of b) and a ∩ (right of b).""" left = Interval(-INF, False, b.lo, not b.lo_closed) right = Interval(b.hi, not b.hi_closed, INF, False) return [p for p in (intersect(a, left), intersect(a, right)) if not p.empty()] # --------------------------------------------------------------------------- # Section 9: an unbracketed expression under every full bracketing # --------------------------------------------------------------------------- OPS = {"|": or_, "&": and_, "^": xor, "-": sub} def bracketings(operands, ops): """Every full bracketing of operands joined by ops, as (text, value) pairs.""" if not ops: return [operands[0]] out = [] for k in range(len(ops)): for left in bracketings(operands[: k + 1], ops[:k]): for right in bracketings(operands[k + 1 :], ops[k + 1 :]): out.append((f"({left[0]} {ops[k]} {right[0]})", OPS[ops[k]](left[1], right[1]))) return out def as_python_reads(expr: str) -> str: """The bracketing Python's own parser gives expr, written out in full.""" symbols = {ast.BitOr: "|", ast.BitAnd: "&", ast.BitXor: "^", ast.Sub: "-", ast.LtE: "<=", ast.Eq: "=="} def show(node): if isinstance(node, ast.BinOp): return f"({show(node.left)} {symbols[type(node.op)]} {show(node.right)})" if isinstance(node, ast.Compare): return f"({show(node.left)} {symbols[type(node.ops[0])]} {show(node.comparators[0])})" return node.id return show(ast.parse(expr, mode="eval").body) def precedence_kata(label, expr, expected, env, show_all): """Evaluate expr under every bracketing and count how many give the expected set.""" tokens = expr.split() operands = [(t, frozenset(env[t])) for t in tokens if t.isalpha()] ops = [t for t in tokens if t in OPS] python = eval(expr, {}, {k: frozenset(v) for k, v in env.items()}) trees = bracketings(operands, ops) same = sum(1 for _, v in trees if v == python) print(f" {label} {expr} with " + ", ".join(f"{n} = {braces(s)}" for n, s in env.items())) verdict = "right" if python == expected else "WRONG" print(f" Python reads {as_python_reads(expr)} = {braces(python)}; the kata expects {braces(expected)}: {verdict}") if show_all: for text, value in trees: note = "Python's" if text == as_python_reads(expr) else ("also" if value == python else "") print(f" {text:<28} {braces(value):<16} {note}") print(f" {same} of {len(trees)} bracketings give the expected set" + (": only Python's" if same == 1 else "")) def main() -> None: print("1. STATEMENTS ABOUT SETS: EXERCISES 1.1, 1 TO 7, ON EVERY A, B, C ⊆ {1, 2, 3}") katas = [ ("1", "if a ∉ A ∖ B and a ∈ A, then a ∈ B", lambda A, B, C, a: a not in (A - B) and a in A, lambda A, B, C, a: a in B), ("2", "if A ⊆ B, then C ∖ B ⊆ C ∖ A", lambda A, B, C, a: A <= B, lambda A, B, C, a: (C - B) <= (C - A)), ("3", "if A ∖ B ⊆ C, then A ∖ C ⊆ B", lambda A, B, C, a: (A - B) <= C, lambda A, B, C, a: (A - C) <= B), ("4", "if A ⊆ B and A ⊆ C, then A ⊆ B ∩ C", lambda A, B, C, a: A <= B and A <= C, lambda A, B, C, a: A <= (B & C)), ("5", "if A ⊆ B and B ∩ C = ∅, then A ⊆ B ∖ C", lambda A, B, C, a: A <= B and not (B & C), lambda A, B, C, a: A <= (B - C)), ("6", "A ∖ (B ∖ C) ⊆ (A ∖ B) ∪ C", lambda A, B, C, a: True, lambda A, B, C, a: (A - (B - C)) <= ((A - B) | C)), ("7", "if A ∖ B ⊆ C and A ⊄ C, then A ∩ B ≠ ∅", lambda A, B, C, a: (A - B) <= C and not (A <= C), lambda A, B, C, a: bool(A & B)), ("1.2, problem 5", "x ∉ A ∖ B iff x ∉ A or x ∈ B", lambda A, B, C, a: True, lambda A, B, C, a: (a not in (A - B)) == (a not in A or a in B)), ] cases = [(A, B, C, a) for A in SUBSETS for B in SUBSETS for C in SUBSETS for a in BASE] for num, text, hyp, concl in katas: applicable = [c for c in cases if hyp(*c)] ok = all(concl(*c) for c in applicable) print(f" {num:<15} {text}") print(f" {'':<15} holds in all {len(applicable)} cases where the hypothesis holds (of {len(cases)}): {ok}") print(" Every one is proved by taking an arbitrary x and unpacking the") print(" definitions of ∖, ∩, ∪ and ⊆; the page names the move for each.") print() print("2. TRUTH SETS: PROBLEM 1 AND EXERCISES 8, 10, 12") print(f" {{x ∈ ℕ : 3 < x < 11}} = {braces(x for x in range(0, 30) if 3 < x < 11)}") print(f" {{y ∈ ℤ : y² = 4}} = {braces(y for y in range(-30, 30) if y * y == 4)}") print(f" {{z ∈ ℕ : z is a multiple of 3}} = {braces(z for z in range(0, 16) if z % 3 == 0)[:-1]}, ...}} (Cunningham's ℕ starts at 0)") P = lambda x: x > 1 / x print(" exercise 8, P(x): x > 1/x: " + " ".join(f"P({x}) {P(Fraction(x))}" for x in ("2", "-2", "1/2", "-1/2"))) print(" exercise 10: {1, 4, 9, 16, 25, ...} = {x ∈ ℕ : x = n² for some n ≥ 1};") print(" {..., -10, -5, 0, 5, 10, ...} = {y ∈ ℤ : 5 divides y}") print(f" exercise 12(a) {{x ∈ ℕ : 0 < x² < 24}} = {braces(x for x in range(0, 30) if 0 < x * x < 24)}") print(f" exercise 12(b) {{y ∈ ℤ : y divides 12}} = {braces(y for y in range(-13, 14) if y and 12 % y == 0)}") print(f" exercise 12(c) {{z ∈ ℕ : 4 divides z}} = {braces(z for z in range(0, 17) if z % 4 == 0)[:-1]}, ...}}") print() print("3. INTERVALS: EXERCISE 9 EXACTLY, EXERCISES 11 AND 12(d) ON A GRID") a9 = intersect(Interval(-3, False, 2, False), Interval(1, False, 3, False)) b9 = union(Interval(-3, False, 4, False), Interval(0, False, INF, False)) c9 = difference(Interval(-3, False, 2, False), Interval(1, True, 3, False)) print(f" 9(a) (−3, 2) ∩ (1, 3) = {a9}") print(f" 9(b) (−3, 4) ∪ (0, ∞) = {b9}") print(f" 9(c) (−3, 2) ∖ [1, 3) = {' ∪ '.join(str(p) for p in c9)}") grid = [Fraction(k, 8) for k in range(-40, 41)] checks = [ ("11(a)", "{x ∈ ℝ : x² − 1 ≤ 3}", lambda x: x * x - 1 <= 3, Interval(-2, True, 2, True)), ("11(b)", "{x ∈ ℝ : x > 0 and (x − 1)² < 1}", lambda x: x > 0 and (x - 1) ** 2 < 1, Interval(0, False, 2, False)), ("12(d)", "{y ∈ ℝ⁻ : 1 ≤ y² ≤ 4}", lambda y: y < 0 and 1 <= y * y <= 4, Interval(-2, True, -1, True)), ] for num, text, pred, claim in checks: agree = all(pred(x) == claim.contains(x) for x in grid) print(f" {num} {text:<34} = {str(claim):<10} agrees on {len(grid)} sample points in [−5, 5]: {agree}") print(" The grid check is evidence, not proof: solving x² − 1 ≤ 3 is the kata.") print() print("4. QUIZ KATAS: SEVEN MULTIPLE-CHOICE QUESTIONS, COMPUTED") N = range(1, 200) mult = lambda k: frozenset(n for n in N if n % k == 0) fac = lambda n: frozenset(d for d in range(1, n + 1) if n % d == 0) is_prime = lambda n: n > 1 and all(n % d for d in range(2, n)) X, Y, Z = mult(3), mult(6), mult(9) print(" Q1 X = multiples of 3, Y of 6, Z of 9 (within 1..199):") for name, claim in [("A X ⊂ Y", X < Y), ("B X ⊂ Z", X < Z), ("C Z ⊂ Y", Z < Y), ("D Z ⊂ X", Z < X)]: print(f" {name}: {claim}") print(" every multiple of 9 is a multiple of 3, because 3 | 9; and Y ⊂ X too, since 3 | 6.") A, B = fac(6), frozenset(d for d in fac(6) if is_prime(d)) C_strict, C_loose, D = fac(6) - {1, 6}, fac(6) - {6}, fac(3) print(f" Q2 A = factors of 6 = {sorted(A)}, B = prime factors = {sorted(B)}, D = factors of 3 = {sorted(D)}") print(f" C = proper factors of 6: {sorted(C_strict)} if 1 is excluded (Math is Fun), {sorted(C_loose)} if only 6 is") print(f" A = B {A == B} A = C {A == C_strict} B = C {B == C_strict} C = D {C_strict == D} -> C, on the convention that excludes 1") print(" Q3 which is the null set?") cands = [("A subsets of ∅", {frozenset()}), ("B even primes", {n for n in range(2, 100) if is_prime(n) and n % 2 == 0}), ("C factors of 7", set(fac(7))), ("D rational expressions for π", set())] for name, s in cands: print(f" {name}: {sorted(s, key=str) if s else '∅'} empty: {not s}") print(" {∅} has one member, ∅ itself; π is irrational, so D.") print(f" Q4 subsets of {{a, b, c, d}}: 2^4 = {2 ** 4} (each of 4 members in or out)") print(f" Q5 proper subsets of {{a, b, c, d, e}}: 2^5 − 1 = {2 ** 5 - 1} (all subsets but the set itself)") subsets3 = [frozenset(c) for r in range(4) for c in combinations((1, 2, 3), r)] trans = all((not (a <= b and b <= c)) or a <= c for a in subsets3 for b in subsets3 for c in subsets3) print(f" Q6 A ⊆ B and B ⊆ C imply A ⊆ C, on all triples of subsets of {{1, 2, 3}}: {trans} -> D; the other three fail e.g. A = ∅, B = C = {{1}}") P5, Q25, R125 = fac(5), fac(25), fac(125) print(f" Q7 factors of 5, 25, 125: {sorted(P5)}, {sorted(Q25)}, {sorted(R125)}") print(f" P ⊂ Q {P5 < Q25} Q ⊂ R {Q25 < R125} R ⊂ P {R125 < P5} P ⊂ R {P5 < R125} -> C is the false one") A8 = frozenset(n for n in range(10) if is_prime(n)); B8 = frozenset(n for n in range(10) if n % 2); C8 = frozenset(n for n in range(10) if n % 2 == 0) print(f" Q8 A = primes < 10 = {sorted(A8)}, B = odd < 10 = {sorted(B8)}, C = even < 10 = {sorted(C8)}") claims = [("A ⊂ B", A8 < B8), ("B ⊂ A", B8 < A8), ("A ⊂ C", A8 < C8), ("C ⊂ A", C8 < A8), ("B ⊂ C", B8 < C8), ("C ⊂ B", C8 < B8)] print(" " + " ".join(f"{n} {v}" for n, v in claims) + f" -> {sum(v for _, v in claims)} true: D, None; 2 is the prime that is not odd") print(" Q9 which is infinite? whole numbers < 10: 10 of them; primes < 10: 4; factors of 10: 4;") print(" integers < 10: 9, 8, 7, ..., 0, −1, −2, ... with no end -> C") print(f" Q10 factors of 12 = {sorted(fac(12))}; not a member: {[n for n in (3, 4, 5, 6) if n not in fac(12)]} -> C") print(" Behind Q1, Q2, Q7 and Q10 is one fact of number theory read as sets:") print(" a | b iff factors(a) ⊆ factors(b) iff multiples(b) ⊆ multiples(a)") ok = all((b % a == 0) == (fac(a) <= fac(b)) == (mult(b) <= mult(a)) for a in range(1, 13) for b in range(1, 13)) print(f" checked for all a, b in 1..12: {ok}") print() print("5. FROM ASHLOCK'S PROBLEM SET: WHICH ARE SETS, PRECEDENCE, FOUR CIRCLES, COUNTING") print(" 2.1 'the weights of all people in Canada' repeats values: a multiset, not a set;") print(" 'all weights at least one person had' drops repeats: a set. In Python:") weights = [70, 82, 70, 65, 82, 82] print(f" list {weights} -> set {sorted(set(weights))}; 'the first names in a phone book, in order' is a list,") print(" the set behind it forgets the order. {√x : x < 0} is ∅ in ℝ and a set of imaginaries in ℂ: it depends on U.") A, B_, C = frozenset({1, 2}), frozenset({2, 3}), frozenset({3, 4}) U4 = frozenset({1, 2, 3, 4}) print(" 2.7 precedence (Ashlock: complement, then ∩, then ∪; ∖ and △ always bracketed):") print(f" A ∪ B ∩ C ∪ D reads A ∪ (B ∩ C) ∪ D; Aᶜ ∩ Bᶜ ∪ C reads (Aᶜ ∩ Bᶜ) ∪ C; A ∪ B = A ∩ C is a truth value") print(f" with A = {sorted(A)}, B = {sorted(B_)}, C = {sorted(C)}: A ∪ (B ∩ C) = {sorted(A | (B_ & C))} but (A ∪ B) ∩ C = {sorted((A | B_) & C)}") print(" 2.9/2.10 a Venn diagram of n sets needs 2^n regions; n circles in general position") print(" make at most n² − n + 2 regions, so circles stop working at four sets (Venn used ellipses):") print(" n: " + "".join(f"{n:>5}" for n in range(1, 7))) print(" 2^n: " + "".join(f"{2 ** n:>5}" for n in range(1, 7))) print(" n²−n+2: " + "".join(f"{n * n - n + 2:>5}" for n in range(1, 7))) from math import comb print(" 2.19/2.20 k-element subsets of an n-set: C(n, k) = n! / (k!(n−k)!)") for n in (4,): items = tuple(range(1, n + 1)) counts = [sum(1 for _ in combinations(items, k)) for k in range(n + 1)] print(f" n = {n}: counted {counts}, formula {[comb(n, k) for k in range(n + 1)]}, sum {sum(counts)} = 2^{n}") ie = all(len(S | T) == len(S) + len(T) - len(S & T) for S in SUBSETS for T in SUBSETS) print(f" 2.21 |S ∪ T| = |S| + |T| − |S ∩ T| on all pairs of subsets of {{1, 2, 3}}: {ie} (inclusion–exclusion)") print() print("6. FROM A SCHOOL TEXTBOOK: ∈ VERSUS ⊆, NESTED SETS, AND COUNTING BY VENN REGIONS") E, S1, S2 = frozenset(), frozenset({frozenset()}), frozenset({frozenset(), frozenset({frozenset()})}) print(" 1.2.2 true or false: 1 ∈ {1}: " + str(1 in {1}) + " {2} ∈ {2}: " + str(frozenset({2}) in {2}) + " {2} ∈ {{2}}: " + str(frozenset({2}) in {frozenset({2})}) + " ∅ ∈ {1, 2, 3}: " + str(E in {1, 2, 3}) + " ∅ ⊆ {1, 2, 3}: " + str(E <= {1, 2, 3})) print(" ∈ asks 'is it a member'; ⊆ asks 'is every member of it a member'. ∅ is a subset of everything and a member of almost nothing.") nested = [("{a}", frozenset({"a"})), ("{a, {a}}", frozenset({"a", frozenset({"a"})})), ("{∅, 1, 2, {1, 2}}", frozenset({E, 1, 2, frozenset({1, 2})})), ("{1, {1}, {1, {1}}}", frozenset({1, frozenset({1}), frozenset({1, frozenset({1})})})), ("{∅, {∅}, {∅, {∅}}}", frozenset({E, S1, S2}))] print(" 1.2.4 cardinality of nested sets: " + " ".join(f"{name} -> {len(s)}" for name, s in nested)) print(" a member that is itself a set still counts once; braces inside braces do not open.") def power(s): items = list(s) return frozenset(frozenset(c) for r in range(len(items) + 1) for c in combinations(items, r)) print(f" 1.2.3 P(∅) has {len(power(E))} member; P({{∅}}) has {len(power(S1))}; P({{∅, {{∅}}}}) has {len(power(S2))}; n(A) = 10 gives 2^10 = {2 ** 10}, n(A) = 100 gives 2^100 = {2 ** 100}") print(f" BANANA: the set of its letters is {sorted(set('BANANA'))}, {len(set('BANANA'))} members, not 6") # inclusion–exclusion word problems, solved by building the sets def regions(only_a, only_b, both, neither): A = set(range(0, only_a + both)); B = set(range(only_a, only_a + both + only_b)) U = set(range(0, only_a + both + only_b + neither)) return A, B, U B_, T, U = regions(11, 2, 11, 16) print(f" Ex.20 40 students, 22 badminton, 11 both, 16 neither -> table tennis only: build the sets and count: {len(T - B_)}") print(f" check: n(U) = {len(U)}, n(B) = {len(B_)}, n(B ∩ T) = {len(B_ & T)}, n(neither) = {len(U - (B_ | T))}; formula n(T) = n(U) − n(neither) − n(B) + n(B ∩ T) = {40 - 16 - 22 + 11}") L, M, U = regions(74, 28, 18, 0) print(f" Ex.21 120 students, 92 language, 46 maths, all teach something -> both: {len(L & M)} = 92 + 46 − 120; exactly one: {len(L ^ M)} = 92 + 46 − 2·18") print(" Ex.22 100 students, 70 physics, 60 chemistry: n(P ∪ C) = 130 − n(P ∩ C) and n(P ∪ C) ≤ 100,") print(f" so n(P ∩ C) ≥ 30 (least both) and, with C ⊆ P, n(P ∪ C) = 70 so neither ≤ {100 - 70} (most neither)") # three sets: languages problem, exercise 1.3.10 reg = {"EGS": 25, "EG": 15, "GS": 5, "ES": 0, "E": 20, "G": 5, "S": 5, "none": 25} people, E3, G3, S3 = [], set(), set(), set() k = 0 for name, n in reg.items(): for _ in range(n): if "E" in name: E3.add(k) if "G" in name: G3.add(k) if "S" in name and name != "none": S3.add(k) k += 1 U3 = set(range(k)) at_least_two = sum(1 for p in U3 if (p in E3) + (p in G3) + (p in S3) >= 2) print(f" 1.3.10 100 students: E 60, G 50, S 35, EG 40, GS 30, ES 25, all three 25. Build 8 regions, then count:") print(f" sizes rebuilt: n(E) = {len(E3)}, n(G) = {len(G3)}, n(S) = {len(S3)}, n(E ∩ G) = {len(E3 & G3)}, n(G ∩ S) = {len(G3 & S3)}, n(E ∩ S) = {len(E3 & S3)}, all three {len(E3 & G3 & S3)}") print(f" at least two: {at_least_two} at most one: {len(U3) - at_least_two} none: {len(U3 - (E3 | G3 | S3))}") formula = 60 + 50 + 35 - (40 + 30 + 25) + 25 print(f" n(E ∪ G ∪ S) by inclusion–exclusion = 60 + 50 + 35 − (40 + 30 + 25) + 25 = {formula}; counted: {len(E3 | G3 | S3)}") print(" 1.3.9 56 certificates, 17 + 28 + 25 = 70 awards, 4 students with all three: pairs sum to 70 + 4 − 56 = 18,") print(f" exactly two = 18 − 3·4 = {18 - 12} (each triple student sits in three of the pair counts)") print() print("7. SOLUTION SETS: SULLIVAN 3.5, PROBLEMS 39 TO 43, ON A GRID OF RATIONALS") grid = [Fraction(k, 4) for k in range(-40, 41)] claims = [ ("39 (x − 4)² ≤ 0 has exactly one solution", lambda x: (x - 4) ** 2 <= 0), ("40 (x − 2)² > 0 misses exactly one real", lambda x: (x - 2) ** 2 > 0), ("41 x² + x + 1 > 0 for every real", lambda x: x * x + x + 1 > 0), ("42 x² − x + 1 < 0 has empty solution set", lambda x: x * x - x + 1 < 0), ] for name, test in claims: sols = [x for x in grid if test(x)] non = [x for x in grid if not test(x)] small = sols if len(sols) <= 3 else non word = "solutions" if small is sols else "non-solutions" shown = ", ".join(str(x) for x in small) if small else "none" print(f" {name:<46} on {len(grid)} points: {len(sols)} solutions; {word}: {shown}") print(" 43 x-intercepts of y = (x − 1)(x − 3) in the solution set? (x − 1)(x − 3) ≤ 0: " f"{all((x - 1) * (x - 3) <= 0 for x in (1, 3))} (x − 1)(x − 3) < 0: {all((x - 1) * (x - 3) < 0 for x in (1, 3))}") print(" A grid refutes 'empty' or 'all' with one point and never proves them; the") print(" proofs are one line each: a square is never negative, and the discriminant") print(" of x² ± x + 1 is 1 − 4 < 0, so the parabola, opening up, never meets the axis.") print() print("8. A SYMBOL TABLE SAYS 'A ⊆ B: THE SUBSET HAS FEWER ELEMENTS OR EQUAL'. TEST IT.") subs = [frozenset(c) for r in range(4) for c in combinations((1, 2, 3), r)] pairs = [(a, b) for a in subs for b in subs] fewer_or_equal = sum(1 for a, b in pairs if len(a) <= len(b)) subset = sum(1 for a, b in pairs if a <= b) both = sum(1 for a, b in pairs if a <= b and len(a) <= len(b)) print(f" pairs (A, B) of subsets of {{1, 2, 3}}: {len(pairs)}; |A| ≤ |B|: {fewer_or_equal}; A ⊆ B: {subset}; A ⊆ B and |A| ≤ |B|: {both}") a, b = frozenset({1}), frozenset({2, 3}) print(f" A = {set(a)}, B = {set(b)}: |A| ≤ |B| is {len(a) <= len(b)}, A ⊆ B is {a <= b}") print(" Every subset has no more elements, but having no more elements is not being a") print(" subset. ⊆ is about membership: every member of A is a member of B.") print() print("9. FOUR PASTED PRECEDENCE KATAS, TRIED UNDER EVERY BRACKETING") print(" Python's ladder, tightest first: - then & then ^ then |, and comparisons") print(" below all four (the language reference's precedence table). An assert on") print(" the final set passes whenever any reading gives that set, so each kata is") print(" evaluated under every full bracketing, and tests a step only if the rival") print(" readings give a different set.") katas = [ ("kata 1", "A | B & C", {1, 2, 3, 5}, dict(A={1, 2, 3}, B={3, 4, 5}, C={5, 6, 7})), ("kata 2", "A - B & C", set(), dict(A={1, 2, 3, 4}, B={3, 4, 5}, C={4, 5, 6})), ("kata 3", "A | B ^ A & C", {1, 2, 3}, dict(A={1, 2}, B={2, 3}, C={3, 4})), ("kata 4", "A | B ^ C - A & D", {1, 2, 3, 4}, dict(A={1, 2}, B={2, 3}, C={3, 4}, D={2, 4})), ] for label, expr, expected, env in katas: precedence_kata(label, expr, expected, env, show_all=True) print(" Kata 3 tests nothing about ^: A ∩ C = ∅ and B △ ∅ = B, so the ^ step changes") print(" nothing, and the two readings it claims to rule out, ^ above & and ^ below |,") print(" give the expected set too. Kata 4 tests - before & before ^, not ^ before |:") sub16 = [frozenset(c) for r in range(5) for c in combinations((1, 2, 3, 4), r)] differ = sum(1 for A, B, C, D in product(sub16, repeat=4) if (A | (B ^ ((C - A) & D))) != ((A | B) ^ ((C - A) & D))) print(f" A | (B ^ ((C - A) & D)) = (A | B) ^ ((C - A) & D) on all {len(sub16) ** 4} quadruples of subsets") print(f" of {{1, 2, 3, 4}} ({differ} differ): (C ∖ A) ∩ D is disjoint from A, and (A ∪ B) △ X = A ∪ (B △ X)") print(" whenever A ∩ X = ∅. No choice of sets mends it while the second operand of - is A.") print(" Repaired:") precedence_kata("kata 3", "A | B ^ A & C", {1, 2, 3}, dict(A={1, 2}, B={2, 3}, C={2, 4}), show_all=True) precedence_kata("kata 4", "A | B ^ C - D & E", {1, 2, 3}, dict(A={1, 2}, B={2, 3}, C={1, 3}, D={3, 4}, E={1, 4}), show_all=False) print(" What else the ladder says, checked:") print(f" comparisons come last: A - B <= C reads {as_python_reads('A - B <= C')}; A ^ B == C reads {as_python_reads('A ^ B == C')}") triples = list(product(sub16, repeat=3)) minus = sum(1 for A, B, C in triples if (A - B) - C != A - (B - C)) xor_ = sum(1 for A, B, C in triples if (A ^ B) ^ C != A ^ (B ^ C)) print(f" within one level, left to right: (A - B) - C ≠ A - (B - C) on {minus} of {len(triples)} triples of subsets of {{1, 2, 3, 4}};") print(f" (A ^ B) ^ C ≠ A ^ (B ^ C) on {xor_}: only - needs its brackets, since △, ∩ and ∪ are associative") try: {1, 2} - [1] mixed = "no error" except TypeError as e: mixed = f"TypeError: {e}" try: -{1, 2} unary = "no error" except TypeError as e: unary = f"TypeError: {e}" print(f" sets on both sides: {{1, 2}} - [1] -> {mixed}; -{{1, 2}} -> {unary};") print(f" the methods take any iterable and have no precedence to know: {{1, 2}}.difference([1]) = {braces({1, 2}.difference([1]))}") if __name__ == "__main__": main()