The double complement law: (A′)′ = A¶

Level: 101 · one law of the algebra of sets, on its own page

One line: Not not in A is in A: two complements cancel, so a chain of primes can be cut to its parity.

The law¶

Sets	Logic	Python
(A′)′ = A	¬¬p = p	`U - (U - a) == a`

Why it is true¶

x ∈ (A′)′ means x ∉ A′, which means it is not the case that x ∉ A, which means x ∈ A. Each step is one use of the definition of the complement, and "not not p" is p in classical logic. A law of sets is decided one member at a time, so checking it on every subset of a four-element universe, every pattern of membership there is, proves it; the program does that and prints the matching truth table.

Where it is used, and the trap¶

In code, not not x is bool(x), and two negations in a condition are a sign to rewrite it. In De Morgan's laws the double complement is what lets you go back: from (A′ ∩ B′)′ to A ∪ B. The one logic that refuses this law is intuitionistic logic, where "not not p" is weaker than p, because a proof that p cannot be refuted is not a proof of p.

What the program prints¶

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

1. THE LAW: (A′)′ = A
   checked on all 16 choices of 1 subset(s) of U = {1, 2, 3, 4}: True

2. ONE INSTANCE, WORKED
   A = {1, 2}, B = {2, 3}, C = {3, 4}, A' = {3, 4}, B' = {1, 4}
   (A')' = ({3, 4})' = {1, 2} = A

3. THE SAME LAW IN LOGIC: ¬¬p = p
   every row of the truth table agrees, which is why the member-by-member check is a proof:
   p   left  right
   T   T     T
   F   F     F

Po polsku, w skrócie¶

Prawo podwójnego dopełnienia: dopełnienie dopełnienia to wyjściowy zbiór, bo „nie nie p" to p. W kodzie not not x to bool(x); w logice intuicjonistycznej to jedyne prawo, które nie zachodzi.

Auf Deutsch: Stichwörter¶

Doppeltes Komplement: (A′)′ = A.

Stichwörter: doppeltes Komplement, Involution, doppelte Negation.