Day 35 — Sets

Day 35 — Sets

Stage IV · concept day
Goal: Use roster and set-builder notation; master \(\in\), \(\subseteq\), \(\subsetneq\); work with the empty set and ambient universes; know Russell’s paradox at awareness level; prove set equality by double inclusion.

Why this matters

Sets are the noun phrases of discrete mathematics: types as collections of values, databases as sets of rows, configs as sets of flags, graphs as vertex/edge sets. Stage IV builds relations and functions on top of sets. Equality by double inclusion is the same muscle as “two specs describe the same states.”

Theory

What is a set? (naive view)

A set is a collection of distinct objects, called elements (or members). We write \(x \in A\) for “\(x\) is an element of \(A\)” and \(x \notin A\) otherwise.

Naive set theory is enough for CS mathematics at this level; avoid unrestricted “set of all sets.”

Roster notation

List elements in braces: \(A = \{1,2,3\}\), \(B = \{\mathrm{red},\mathrm{blue}\}\).
Order does not matter: \(\{1,2\}=\{2,1\}\).
Repetition does not matter: \(\{1,1,2\}=\{1,2\}\).

Set-builder notation

\[\{ x \in U : P(x) \}\]
means the set of all \(x\) in universe \(U\) such that predicate \(P(x)\) holds.
Also written \(\{ x \in U \mid P(x) \}\).

Examples: \(\{ n \in \mathbb{Z} : n > 0 \} = \mathbb{Z}^+\) (or \(\mathbb{N}\) depending on convention); \(\{ n \in \mathbb{Z} : 2\mid n \}\) even integers.

Equality of sets

\[A = B \;\overset{\mathrm{def}}{\Longleftrightarrow}\; \forall x\, (x\in A \leftrightarrow x\in B).\]

Double inclusion theorem. \(A = B\) iff \(A \subseteq B\) and \(B \subseteq A\).

Proof. If \(A=B\), membership agrees so each is subset of the other. Conversely, if both inclusions hold, then \(x\in A \Rightarrow x\in B\) and \(x\in B \Rightarrow x\in A\), so \(x\in A \leftrightarrow x\in B\). \(\square\)

Subset and proper subset

\[A \subseteq B \;\overset{\mathrm{def}}{\Longleftrightarrow}\; \forall x\, (x\in A \rightarrow x\in B).\]

\(A\) is a proper subset of \(B\), written \(A \subsetneq B\) (or \(A \subset B\) in texts that use \(\subset\) for proper), when \(A \subseteq B\) and \(A \neq B\).

Always \(A \subseteq A\). If \(A \subseteq B\) and \(B \subseteq C\) then \(A \subseteq C\) (transitivity—direct element chase).

Empty set

The empty set \(\emptyset = \{\}\) has no elements.
\(\forall x\, (x \notin \emptyset)\).
\(\emptyset \subseteq A\) for every set \(A\) (vacuous implication \(x\in\emptyset \rightarrow x\in A\)).
\(\emptyset \neq \{\emptyset\}\): the latter has one element (the empty set).

Universe of discourse

Often all sets under discussion are subsets of a fixed universe \(U\) (e.g. \(\mathbb{Z}\), all strings, all users). Complements (Day 36) need \(U\).

Standard number sets (notation)

\(\mathbb{N}\) (naturals—confirm if \(0\) included), \(\mathbb{Z}\), \(\mathbb{Q}\), \(\mathbb{R}\), \(\mathbb{C}\).
Finite sets: \(|A|=n\) means \(n\) elements (cardinality; deeper Days 41–43).

Russell’s paradox (awareness, one paragraph)

If unrestricted comprehension allowed \(R = \{ x : x \notin x \}\), then \(R\in R \leftrightarrow R\notin R\), contradiction. Naive “any property defines a set” is inconsistent. Modern foundations restrict set formation (types, ZFC axioms). Practice: only form \(\{x \in U : P(x)\}\) from an already given \(U\), or use known set constructors. You will not need formal ZFC here—just do not form “the set of all sets” or “the set of all sets that do not contain themselves.”

Proving \(A \subseteq B\)

Element chase: Let \(x \in A\) be arbitrary. … show \(x \in B\). Conclude \(A\subseteq B\).

Proving \(A \neq B\)

Exhibit a witness element in one set but not the other.

Singleton and pairing

\(\{a\}\) has one element. \(\{a,b\}\) has two if \(a\neq b\), else one.

Sets of sets

\(\{\emptyset, \{1\}, \{1,2\}\}\) is a set whose elements are sets. Common in power sets (Day 36) and inductively defined structures.

Worked examples

Example 1 — Roster equality

\(\{1,2,3\} = \{3,1,2,1\}\) because same members.

Example 2 — Builder

\(\{ n \in \mathbb{N} : n < 4 \} = \{0,1,2,3\}\) if \(0\in\mathbb{N}\), else \(\{1,2,3\}\).

Example 3 — Subset proof

\(A = \{2,4\}\), \(B = \{n\in\mathbb{Z}: 2\mid n\}\).
Let \(x\in A\). Then \(x=2\) or \(x=4\), both even, so \(x\in B\). Thus \(A\subseteq B\).

Example 4 — Proper subset

\(A \subsetneq B\) because \(6\in B\) but \(6\notin A\).

Example 5 — Double inclusion

Let \(E = \{ n\in\mathbb{Z}: 2\mid n \}\), \(F = \{ n\in\mathbb{Z}: n=2k\text{ for some }k\in\mathbb{Z} \}\).
Same definition essentially—show \(E\subseteq F\) and \(F\subseteq E\) by unpacking \(2\mid n\).

Example 6 — Empty subset

\(\emptyset \subseteq \{1\}\): there is no counterexample element in \(\emptyset\) outside \(\{1\}\).

Example 7 — Inequality

\(\emptyset \neq \{\emptyset\}\) because \(\emptyset \in \{\emptyset\}\) but \(\emptyset \notin \emptyset\).

Example 8 — Not subset

\(\{1,2\} \nsubseteq \{1,3\}\) witness \(2\).

Example 9 — Builder with two variables (preview)

\(\{ (x,y) \in \mathbb{Z}^2 : x+y=0 \}\) is a set of pairs (Day 37 products).

Example 10 — Vacuous

Is \(\{ n\in\mathbb{Z}: n^2 < 0 \} = \emptyset\)? Yes, no integer has negative square.

Example 11 — Transitivity

If \(A\subseteq B\subseteq C\) and \(x\in A\) then \(x\in B\) then \(x\in C\).

Example 12 — Spec as set

Valid ports \(= \{ p\in\mathbb{Z}: 1\le p \le 65535 \}\). Membership tests are predicate checks.

Example 13 — Equality failure one side

\(A\subseteq B\) but not \(B\subseteq A\) ⇒ not equal; still useful (subtype / subset of states).

Example 14 — Set of even primes

\(\{ p : p\text{ prime and }2\mid p \} = \{2\}\) under standard primes.

Exercises

1. Rewrite \(\{2,4,6,8\}\) in set-builder form as a subset of \(\mathbb{Z}\).
   
2. List \(\{ n\in\mathbb{Z}: 0 \le n < 5 \}\) in roster form.
   
3. Prove \(\{1,2\} \subseteq \{1,2,3\}\).
   
4. Prove \(\{1,2,3\} \nsubseteq \{1,2\}\) with a witness.
   
5. Prove \(\emptyset \subseteq A\) for arbitrary \(A\).
   
6. Prove \(A \subseteq A\).
   
7. Determine true/false: \(1 \in \{1\}\), \(\{1\} \in \{1\}\), \(\{1\} \subseteq \{1\}\), \(1 \subseteq \{1\}\).
   
8. True/false: \(\emptyset \in \emptyset\), \(\emptyset \subseteq \emptyset\), \(\emptyset \in \{\emptyset\}\), \(\emptyset \subseteq \{\emptyset\}\).
   
9. Prove by double inclusion: \(\{ n\in\mathbb{Z}: 6\mid n \} = \{ n\in\mathbb{Z}: 2\mid n \text{ and } 3\mid n \}\).
   
10. Show \(\{0,1\} \neq \{0,1,0\}\). Wait—actually equal; explain.
    
11. Let \(A=\{x\in\mathbb{R}: x^2 = 2\}\). Describe \(A\).
    
12. Prove if \(A\subseteq B\) and \(B\subseteq A\) then \(A=B\) (quote theorem).
    
13. Find all subsets of \(\{a,b\}\) (roster of the power set preview).
    
14. Is \(\{ n\in\mathbb{N}: n < 0 \}\) empty? Depends on \(\mathbb{N}\)—state convention.
    
15. Prove transitivity of \(\subseteq\).
    
16. Give three different roster notations for the same set of two elements.
    
17. Translate to builder: “all strings of length \(3\) over \(\{0,1\}\).”
    
18. Witness: show \(\{ n : n^2 = n \} \neq \emptyset\) in \(\mathbb{Z}\).
    
19. Explain in your own words why Russell’s paradox blocks unrestricted comprehension.
    
20. Prove \(\{\emptyset\} \neq \emptyset\).
    
21. If \(A = B\) and \(x\in A\), prove \(x\in B\).
    
22. CS: express “set of all failed test names” in builder notation.
    
23. Decide $ {1,2} { {1,2} } $ — true or false?
    
24. Prove that if \(A\subseteq\emptyset\) then \(A=\emptyset\).
    
25. Double inclusion practice: \(\{ n\in\mathbb{Z}: n\mid 6 \} = \{\pm1,\pm2,\pm3,\pm6\}\)—prove carefully.

CS connection

• Types ≈ sets of values (Day 44).
  
• Database tables ≈ sets/bags of tuples; WHERE is set-builder.
  
• Permissions = sets of actions; inheritance ≈ subsets.
  
• Test coverage: set of covered lines \(\subseteq\) set of lines.
  
• Config feature flags as subsets of a universe of flags.
  
• JSON objects are not pure sets, but key sets are.

Common pitfalls

Pitfall	What to do instead
Confusing \(\in\) and \(\subseteq\)	Element vs set of elements
\(\{a\} = a\)	Rarely; \(a\) may not be a set the same way
Order matters in sets	It does not
Forgetting vacuous \(\emptyset\subseteq A\)	Empty has no counterexample
Proving equality with one inclusion	Need both
Unrestricted comprehension	Always build from a known \(U\)
\(\subset\) ambiguity	Prefer \(\subseteq\) and \(\subsetneq\)

Checkpoint

• Roster and builder fluency
  
• Define \(\in\), \(\subseteq\), \(=\)
  
• Prove equality by double inclusion once
  
• Prove \(\emptyset\subseteq A\)
  
• Distinguish \(\emptyset\) and \(\{\emptyset\}\)
  
• Russell awareness paragraph in own words
  
• Exercises done or logged

Two takeaways:

1. …
   
2. …

Deep dive — comprehension discipline

Safe pattern: \(\{ x \in U : P(x) \}\) with \(U\) already a set.
Unsafe pattern: \(\{ x : P(x) \}\) with \(x\) ranging over “everything,” including sets that might create Russell-like trouble. In discrete math practice, \(U\) is \(\mathbb{Z}\), \(\mathbb{R}\), \(V\), strings, etc.

Element-chase templates

Show \(A\subseteq B\):
Let \(x\in A\). [unpack \(A\)]. … [pack \(B\)]. Thus \(x\in B\). Since \(x\) arbitrary, \(A\subseteq B\).

Show \(A=B\):
Show \(A\subseteq B\) and \(B\subseteq A\), then cite double inclusion.

Show \(A\nsubseteq B\):
Produce concrete \(x\in A\setminus B\).

Sets in specifications

Invariants are often “the set of open handles \(\subseteq\) the set of allocated handles.”
Equality of sets of states is the strongest observational equivalence at that abstraction.

More worked examples

Example 15 — Builder equality
\(\{ n\in\mathbb{Z}: n^2=1 \} = \{-1,1\}\) by solving.

Example 16 — Nested braces
\(\{1\} \in \{\{1\}\}\) true; \(\{1\} \subseteq \{\{1\}\}\) false.

Example 17 — Infinite builder
\(\{ n\in\mathbb{N}: n\text{ even} \}\) cannot list fully—use builder or “\(2\mathbb{N}\).”

Example 18 — Spec
Ports in use \(= \{ p : \exists \text{socket bound to } p \}\) as a set comprehension over port universe.

Additional exercises

26. Prove if \(A\subseteq B\subseteq A\) then \(A=B\).
    
27. How many elements does \(\{\emptyset, \{\emptyset\}, \{\emptyset,\{\emptyset\}\}\}\) have?
    
28. Write \(\{0,1\}^n\) vs \(\mathcal{P}([n])\)—not equal as sets, but equinumerous.
    
29. Prove \(A\subseteq B\) and \(C\subseteq D\) need not imply \(A\cup C \subseteq B\cap D\)—counterexample.
    
30. Formalize “set of failed tests \(\subseteq\) set of run tests.”

Extended practice workshop

Membership true/false battery

For \(A=\{1,\{1\},\emptyset\}\), evaluate:

1. \(1\in A\)
   
2. \(\{1\}\in A\)
   
3. \(\{1\}\subseteq A\)
   
4. \(\emptyset\in A\)
   
5. \(\emptyset\subseteq A\)
   
6. \(\{\emptyset\}\subseteq A\)
   
7. \(\{\emptyset\}\in A\)
   
8. \(A\in A\) (naive—should be false here)

Proof battery

9. \(\emptyset\subseteq A\)
   
10. \(A\subseteq A\)
    
11. Transitivity of \(\subseteq\)
    
12. Double inclusion \(\Rightarrow\) equality
    
13. If \(A\subseteq\emptyset\) then \(A=\emptyset\)
    
14. \(\{n\in\mathbb{Z}:6\mid n\}=\{n:2\mid n\text{ and }3\mid n\}\)

Builder practice

15. Evens as builder.
    
16. Primes as builder (no closed form expected).
    
17. \(\{n: n^2<0\}\) in \(\mathbb{R}\) and in \(\mathbb{Z}\).
    
18. Valid TCP ports builder.

Spec practice

19. “Failed tests \(\subseteq\) run tests” as sets.
    
20. “Admins \(\subseteq\) users.”
    
21. When is equality the right claim vs mere inclusion?

Russell awareness

22. Restate the paradox in your own words.
    
23. Why \(\{x\in\mathbb{Z}: P(x)\}\) is safe if \(\mathbb{Z}\) is given.

Notation card

Symbol	Read as
\(\in\)	element of
\(\subseteq\)	subset of
\(\subsetneq\)	proper subset
\(\emptyset\)	empty set
\(\{x\in U:P(x)\}\)	builder

Synthesis

Sets turn predicates into objects: \(\{x\in U:P(x)\}\) packages a property as a value you can pass around, compare, and later transform with \(\cup,\cap\) (Day 36). The core proof skill is the element chase: to show \(A\subseteq B\), take arbitrary \(x\in A\) and derive \(x\in B\). Equality is two inclusions—never “they look the same.”

Element-chase templates

Subset.
Let \(x\in A\). … reason … Therefore \(x\in B\). Since \(x\) was arbitrary, \(A\subseteq B\).

Equality.
Prove \(A\subseteq B\) and \(B\subseteq A\) separately; conclude \(A=B\).

Inequality.
To show \(A\neq B\), exhibit \(x\) in one but not the other (or show one inclusion fails).

More worked examples

Example — Empty set is subset of every set.
Let \(x\in\emptyset\). The premise is false, so \(x\in\emptyset \rightarrow x\in A\) is vacuously true for every \(x\). Hence \(\emptyset\subseteq A\). (Equivalently: there is no counterexample \(x\in\emptyset\setminus A\).)

Example — Builder equality.
\(\{n\in\mathbb{Z}: n^2=n\}=\{0,1\}\). Prove \(\subseteq\) by solving \(n^2-n=0\); prove \(\supseteq\) by checking \(0,1\).

Example — Proper subset.
\(\{1\}\subsetneq\{1,2\}\) because \(\subseteq\) holds and \(2\) witnesses inequality.

Example — Set vs element confusion.
\(\emptyset\neq\{\emptyset\}\): left has no elements; right has one element, namely \(\emptyset\). Also \(\emptyset\in\{\emptyset\}\) but \(\emptyset\notin\emptyset\).

Example — Spec as inclusion.
“Every admin is a user” is \(\mathrm{Admins}\subseteq\mathrm{Users}\). “Admins are exactly the users with flag \(A\)” is equality of two builders.

Extra exercises (synthesis)

31. Prove: if \(A\subseteq B\) and \(B\subseteq C\) then \(A\subseteq C\) (transitivity) by element chase.
    
32. Prove: \(A\subseteq\emptyset\) implies \(A=\emptyset\).
    
33. Disprove: \(A\in B\) implies \(A\subseteq B\) (give finite counterexample).
    
34. Write \(\{n\in\mathbb{Z}: 6\mid n\}\) as an intersection of two builders (div by \(2\) and by \(3\)).
    
35. Prove \(\{n\in\mathbb{Z}: n>0\} = \{n\in\mathbb{Z}: n\ge 1\}\) under standard integer order.
    
36. Russell awareness: why unrestricted \(\{x: x\notin x\}\) is not admitted as a set in this course’s working foundations.

Common Stage IV carry-forward

Habit	Payoff
Always name ambient \(U\) for builders	Avoids “all sets” paradoxes
Double inclusion for equality	Standard in ops/relations proofs
Distinguish \(\in\) vs \(\subseteq\)	Kills \(\{\emptyset\}\) bugs
Vacuous truth for \(\emptyset\subseteq A\)	Matches quantifier Day 26

Roster for finite sets; builder for infinite or rule-defined sets. Tomorrow adds the algebra of combining sets.

Tomorrow

Day 36 — Set operations. \(\cup,\cap,\setminus,\triangle\), complement; Venn reasoning; identities with proofs; power set; \(|\mathcal{P}(S)|=2^{|S|}\).