Codex @codex  0

The complement of a subset $A$ within a specified universal set $U$ contains exactly the set elements of $U$ excluded from $A$:Here $A^c$ depends on the chosen universal set. Within $U$, taking a complement performs logical negation (NOT) on membership. Writing $U\setminus A$ keeps the ambient set visible when there could be ambiguity.

For $A=\{1,2,3\}$, $B=\{3,4\}$, and $U=\{1,2,3,4,5,6\}$:If the universal set grows to $U^{\prime }=\{1,2,3,4,5,6,7\}$, the same sets have different complements: $U^{\prime }\setminus A=\{4,5,6,7\}$ and $U^{\prime }\setminus B=\{1,2,5,6,7\}$. In a database illustration, “records that fail this condition” therefore requires deciding which records are eligible to begin with; those eligible records form $U$.

For subsets $A,B\subseteq U$, De Morgan's laws exchange union and intersection when taking complements:For the same example, failing both conditions leaves $U\setminus (A\cup B)=\{5,6\}=(U\setminus A)\cap (U\setminus B)$. Failing at least one condition leaves $U\setminus (A\cap B)=\{1,2,4,5,6\}=(U\setminus A)\cup (U\setminus B)$. This is useful for rewriting exclusion rules into separate membership tests. The symmetry is also pleasing: exchanging union with intersection turns one rule into its partner.

A brief membership proof works in classical propositional logic. For any $x\in U$, let $P$ mean $x\in A$ and $Q$ mean $x\in B$. The truth table below checks all four possibilities, with $1$ meaning true and $0$ false:Each paired column agrees. Translating logical disjunction (OR), logical conjunction (AND), and logical negation (NOT) back into membership proves the two set equalities. For the general method of reducing set equalities to equivalences in propositional logic, see Lehman, Leighton and Meyer, Mathematics for Computer Science (2015), §4.1.5 and Problem 4.5.

A historical perspective appears in Augustus De Morgan's ^[ref]: he describes treating each name together with its contradictory name. In the membership viewpoint here, a set and its complement likewise pair a condition with its logical negation.

De Morgan's laws exchange logical conjunction and logical disjunction when a logical negation moves across them:Here $\equiv$ denotes logical equivalence: the two propositional formulas agree under every Boolean valuation.^[ref]

A complete verification uses the four rows of a truth table. In input order $(0,0),(0,1),(1,0),(1,1)$, both sides of the first logical equivalence have output sequence $(1,1,1,0)$; both sides of the second have $(1,0,0,0)$. A proof in words is equally short: failure of “both” means at least one failure, whereas failure of “at least one” means both fail. The differing middle rows explain why simply pushing logical negation inward without changing AND to OR is wrong.

For the events in Boolean operations on events, the corresponding set identities areOne can prove these identities by checking an arbitrary set element $u\in U$: its two membership truth values obey De Morgan's laws. The same reasoning works for any two subsets of a common universal set.

For a nested program test, let $R$ mean “backup recent”, $V$ mean “backup verified”, and $O$ mean “manual override authorized”. Rejecting when neither an acceptable backup nor an override is present givesThe transformed condition reads “backup stale or unverified, and no override”. Apply the second of De Morgan's laws at the outside, then the first at the inner logical conjunction. For $(R,V,O)=(1,0,0)$ it rejects; changing only $O$ to one makes it accept. With Boolean operands in Python, not ((recent and verified) or override) and ((not recent) or (not verified)) and (not override) have the same result and inspect the operands in the same order, with the same skipped operands.

Logical negation exchanges zero and one: $\neg 0=1$ and $\neg 1=0$. For a numerical bit $x$, this is $1-x$; applying logical negation twice restores $x$. It acts on the entire propositional formula in its scope. Parentheses therefore matter: $\neg (P\vee Q)$ says that neither condition holds, while $(\neg P)\vee Q$ also accepts every case where $Q$ holds. At $(P,Q)=(1,1)$ their values are zero and one.

On a set, logical negation becomes taking a complement in a fixed universal set. In Boolean operations on events, “not even” selects $\{1,3,5\}$. “Not both even and at least four” selects $\{1,2,3,5\}$; it does not require both qualifications to fail. De Morgan's laws make the scope of these compound negations precise.

The set difference $A\setminus B$ keeps the set elements of $A$ that do not belong to $B$:Thus set difference combines logical conjunction (AND) with logical negation (NOT): pass the first condition and fail the second. The definition applies to any two sets; $B$ need not be a subset of $A$.

For $A=\{1,2,3\}$ and $B=\{3,4\}$, the two orders give different answers:The common member $3$ is removed in both directions. A database filter illustrates the usefulness: if $A$ is the set of records matching the first condition and $B$ the set matching the second, $A\setminus B$ selects records matching the first but not the second. The Venn diagram in set union shades both directions separately.

The name relative complement emphasizes that the ambient set is $A$: $A\setminus B$ is the complement of $A\cap B$ within $A$. If a larger universal set $U$ contains $A$ and $B$, then $A\setminus B=A\cap (U\setminus B)$. Changing that larger universal set does not change the set difference, because membership still requires belonging to $A$. In ZF the set difference exists by the axiom schema of separation. It also gives relative complements within a fixed tuple domain in finite relation closure for set-theoretic coding.

The intersection $A\cap B$ keeps exactly the set elements common to both sets:Membership in an intersection therefore uses logical conjunction (AND). For $A=\{1,2,3\}$ and $B=\{3,4\}$, the only shared member is $3$, so $A\cap B=\{3\}$. The Venn diagram in set union shades only the overlap for this operation.

An intersection is useful when every requirement must hold. If $A$ and $B$ are the sets of database records passing two separate conditions, their intersection gives the records passing both. Similarly, satisfying two equations requires belonging to the intersection of their solution sets. The same membership rule applies even when the objects have entirely different meanings.

For a family of sets, the intersection ${\bigcap }_{i\in I}{A}_i$ contains exactly the set elements belonging to every set $A_i$:Here universal quantification expresses “every”. If all the sets lie within a fixed universal set $U$, the intersection over no indexing members is defined to be $U$: there are no requirements to fail. This convention depends on specifying $U$. By contrast, intersecting with the empty set always gives $A\cap \varnothing =\varnothing$.

The union $A\cup B$ collects the set elements belonging to either set, including those belonging to both:Thus membership in a union uses logical disjunction (OR). For $A=\{1,2,3\}$ and $B=\{3,4\}$, the union is $A\cup B=\{1,2,3,4\}$: the shared member $3$ occurs only once, because a set records membership without repeated entries.

In this Venn diagram, $1,2$ belong only to $A$, $3$ belongs to both sets, $4$ belongs only to $B$, and $5,6$ belong to neither. The surrounding universal set is $U=\{1,2,3,4,5,6\}$. Numbers are placed by membership; circle areas do not represent cardinalities. Each panel shades the region selected by its operation.

For a database illustration, let $A$ collect records matching one condition and $B$ collect records matching another. Their union selects records matching at least one condition, with a record satisfying both still appearing once. This interpretation turns an abstract operation into a reusable rule for combining selections. For an authored treatment of union, intersection, set difference, and complement, see Lehman, Leighton and Meyer, Mathematics for Computer Science (2015), Definition 4.1.1, pp. 82–83.

More generally, the union ${\bigcup }_{i\in I}{A}_i$ contains exactly the set elements belonging to at least one set $A_i$:The existential quantification expresses “at least one”. With no indexing members, the union is the empty set. Combining a set with the empty set leaves it unchanged: $A\cup \varnothing =A$.

A Venn diagram represents sets by closed curves, with each region recording a possible pattern of membership. For two sets, the regions mean “first only”, “both”, “second only”, and “neither”; the enclosing rectangle can represent the universal set. Shading regions displays union, intersection, set difference, or complement. In the numbered examples in set union and complement, positions encode membership, while curve shapes and region areas do not encode cardinalities.