#separator:tab
#html:false
#notetype:Basic
#deck:Math::Sets::The algebra of sets
#tags:sets math
#columns:Front	Back	Tags
#tags column:3
Which logical connective is ∪? Complete: x ∈ A ∪ B when …	'or' (inclusive): x ∈ A ∪ B when x ∈ A or x ∈ B, or both.	logic
Which logical connective is ∩?	'and': x ∈ A ∩ B when x ∈ A and x ∈ B.	logic
Which logical connective is the complement A′?	'not': x ∈ A′ when x ∉ A (and x is in the universe U).	logic
Rewrite A ⊆ B as a logical statement about members.	For every x: if x ∈ A then x ∈ B. Subset is if-then applied to every member at once.	logic
Rewrite A ∖ B in logic, and as an intersection.	x ∈ A and x ∉ B; equivalently A ∖ B = A ∩ B′.	logic
Why does a complement only make sense relative to a universal set U?	'Everything not in A' needs an everything, and there is no set of everything (Russell). So A′ = U ∖ A for a U fixed in advance.	definition
What is a universal set?	The set U, fixed before the problem starts, of everything under discussion: every set in the problem is a subset of it, and complements are taken out of it. Not a set of everything; there is none.	definition
Three notations for the complement of A?	A′, Ā (a bar over A) and Aᶜ. Sullivan's Precalculus writes Ā and notes the other two in a footnote; this library writes A′.	definition
Same A, different universal set U: does the complement change?	Yes. A = {1, 2} has complement {3, 4} in U = {1, 2, 3, 4}, {3, 4, 5, 6} in U = {1, …, 6} and ∅ in U = {1, 2}. A complement quoted without its U is an unfinished sentence.	trap
Python has |, &, - and ^ for sets. Why is there no complement operator?	A complement needs a universe and Python cannot guess it. Name U yourself and write U - a.	python
State De Morgan's laws for sets.	(A ∪ B)′ = A′ ∩ B′ and (A ∩ B)′ = A′ ∪ B′. Taking the complement swaps ∪ and ∩.	law
De Morgan's laws in plain words: what is 'not either', and what is 'not both'?	Not either = neither: not in A and not in B. Not both = at least one is missing: not in A or not in B.	law
Rewrite not (a or b) without the outer not.	not a and not b. Likewise not (a and b) is not a or not b. In SQL, NOT (x = 1 OR y = 2) is x <> 1 AND y <> 2.	law
Expand A ∩ (B ∪ C), and its dual A ∪ (B ∩ C).	A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C), and A ∪ (B ∩ C) = (A ∪ B) ∩ (A ∪ C). Unlike + and × on numbers, each operation distributes over the other.	law
Simplify A ∪ (A ∩ B) and A ∩ (A ∪ B).	Both are A (absorption). A ∩ B already lies inside A, so the union adds nothing; A ∪ B already contains A, so the intersection removes nothing.	law
Simplify A ∪ ∅, A ∩ U, A ∪ U and A ∩ ∅.	A, A, U, ∅. ∅ is the identity for ∪ and U is the identity for ∩; U swallows any union and ∅ swallows any intersection (domination).	law
What are A ∪ A′, A ∩ A′ and (A′)′?	U, ∅ and A. Every x is in A or out of it; none is both; not-not brings you back.	law
Why does checking a law on every subset of a 4-element universe count as a proof, not a sample?	Whether x is on the left or the right side depends only on which of A, B, C contain x. The subsets of a small universe realise every combination of memberships, so the check is the law's complete truth table.	principle
What single structure do the algebra of sets and the logic of and, or, not both form?	A Boolean algebra: the same laws, with ∪, ∩, ′, ∅, U matching or, and, not, false, true.	definition
Is (A ∪ B) ∖ B = A? Give a counterexample if not.	No. A = {1}, B = {1}: (A ∪ B) ∖ B = ∅ ≠ A. Removing B also removes the part of A that overlapped it; difference does not undo union.	trap
From A ∪ B = A ∪ C, can you cancel A and conclude B = C?	No. A = {1}, B = ∅, C = {1}: both unions are {1}. A absorbs whatever B and C differ by, so union has no cancellation law.	trap
Is set difference associative? Commutative?	Neither. With A = B = C = {1}: (A ∖ B) ∖ C = ∅ but A ∖ (B ∖ C) = {1}. And A ∖ B ≠ B ∖ A unless A = B.	trap
How many regions does a Venn diagram of n sets have, and what does each stand for?	2^n, one for each pattern of in-or-out across the n sets. Three sets give 8, counting the region outside all the circles.	venn
In a three-set Venn diagram, which set is the region outside all three circles?	(A ∪ B ∪ C)′, the complement of the union: everything in U that is in none of them.	venn
What does the rectangle in a Venn diagram stand for, and the part of it outside a circle?	The rectangle is the universal set U, and the circles are sets inside it. The part of the rectangle outside a circle is that set's complement.	venn
How does a Venn diagram show A ⊆ B, and A and B disjoint?	A ⊆ B: the circle A drawn inside the circle B. Disjoint (A ∩ B = ∅, no member in common): two circles drawn apart. The usual overlapping circles claim nothing; a region may be empty.	venn
Which three properties make ⊆ an order relation?	Reflexive (A ⊆ A); antisymmetric (A ⊆ B and B ⊆ A give A = B, which is extensionality again); transitive (A ⊆ B and B ⊆ C give A ⊆ C).	order
Why is ⊆ a partial order and not a total one?	Some pairs are incomparable: neither {1} ⊆ {2} nor {2} ⊆ {1}. A total order, like ≤ on numbers, compares every pair.	order
What is a poset, and what is the standard example?	A partially ordered set: a set with a reflexive, antisymmetric, transitive relation that need not compare every pair. The subsets of a set under ⊆ are the standard example.	order
Why does sorted([{3}, {1, 2}, {1}]) give a meaningless order in Python, and what is the fix?	sorted() compares with <, which for sets is proper subset, a partial order; {3} is neither below nor above the others, so the result depends on the input order. Sort by a total key, e.g. key=lambda s: (len(s), sorted(s)).	python
How many subsets does a set with n members have, and why?	2^n: each member is independently in or out. {1, 2, 3, 4} has 16 subsets.	definition
Define the symmetric difference A △ B, two ways.	The members of exactly one of A and B: (A ∖ B) ∪ (B ∖ A), equivalently (A ∪ B) ∖ (A ∩ B). In logic it is exclusive or.	definition
{1, 2, 3, 4} △ {1, 4, 5} = ?	{2, 3, 5}. 1 and 4 are in both and drop out; 2, 3 and 5 are each in exactly one.	example
What notations exist for symmetric difference, and which does MathWorld recommend?	A △ B, A ⊖ B, A ∇ B and A + B. MathWorld recommends ⊖, because each of the others already means something else in mathematics.	definition
Why is symmetric difference sometimes written A + B?	The subsets of U form a group under △: associative, commutative, identity ∅, and A △ A = ∅, so every set is its own inverse. With ∩ as multiplication they form a ring, like bits under XOR and AND.	law
What does a chain A △ B △ C △ … contain?	The elements that occur in an ODD number of the sets, not those in exactly one. Each pair of occurrences cancels because A △ A = ∅. E.g. {0,1,2,3,4} △ {2,3,4} △ {2,5} = {0, 1, 2, 5}: 2 is in all three and survives.	law
When is A △ B = ∅?	Exactly when A = B. So an empty symmetric difference is a test of set equality.	law
How do ∀ and ∃ split over a union A ∪ B?	∀x∈A∪B p ⇔ (∀x∈A p) ∧ (∀x∈B p), and ∃x∈A∪B p ⇔ (∃x∈A p) ∨ (∃x∈B p). 'For all' over a union becomes 'and'; 'there exists' over a union becomes 'or'.	law
If some x in A satisfies p and some x in B satisfies p, must some x in A ∩ B satisfy p?	No. A = {1}, B = {2}, p true on both: the witnesses differ and A ∩ B is empty. Only the converse holds: ∃x∈A∩B p implies ∃x∈A p and ∃x∈B p.	trap
If every x in A satisfies p, or every x in B does, must every x in A ∪ B?	No. A = ∅ makes 'every x in A' true vacuously while p can fail on B. The valid direction is the other way: ∀ over the union implies ∀ over each part.	trap
What are the truth values of ∀x∈∅ p(x) and ∃x∈∅ p(x)?	True and false, for every p: no member can fail the test, and no member can pass it. This vacuous truth is the whole proof that ∅ ⊆ A.	law
How is A = B proved in practice?	Show both inclusions, A ⊆ B and B ⊆ A. Each one is a 'take any x ∈ A and show x ∈ B' argument.	law