04-BS-16 · May 2013

Question 4 of 12: Power Sets, Partitions, and Set-Builder Families

Nivaar worked solution (AI-drafted; not reviewed by a licensed engineer)

Notes on this paper

National Examination, 04-BS-16 Discrete Mathematics, May 2013. Closed book, no aids, 3 hours, 12 questions of 10 marks each (100 marks); the exam instructs "answer 10 of 12" but every question is solved below as a complete study resource.

Reference texts: Rosen, Discrete Mathematics and Its Applications, 7th ed. (logic Ch.1, induction & recursion Ch.5, counting Ch.6, discrete probability Ch.7, relations Ch.9, graphs Ch.10-11); Epp, Discrete Mathematics with Applications.

Question 4: Power Sets, Partitions, and Set-Builder Families (10 marks)

Question text not reproduced: the examination questions are © Engineers and Geoscientists BC. Open the official past paper (linked at the top of this page) to read the question, then follow the worked solution below.

Given. The set $\{a,b,c\}$ (3 elements) for part (a); the family $S(\alpha,\beta)=\{(x,y): -\alpha\le x\le\alpha,\,-\beta\le y\le\beta\}$ for every pair of positive reals $\alpha,\beta$, for part (b).

Check: the paper prints the defining inequalities as $-\alpha\ge x\ge\alpha,\ -\beta\ge y\ge\beta$. Read literally, $-\alpha\ge x\ge\alpha$ forces $-\alpha\ge\alpha$, i.e. $\alpha\le0$, which contradicts "$\alpha,\beta$ positive" — every $S(\alpha,\beta)$ would be the empty set, and the union and intersection in (b) and (c) would both be $\varnothing$. That reading makes the question trivial and the request to "describe the set in plain English" pointless, so the inequality signs are taken as a typesetting slip for $-\alpha\le x\le\alpha,\ -\beta\le y\le\beta$ (the standard centred-rectangle family), which is what is solved below. If you meet this question in the exam, state that assumption in one line, as the cover page instructs ("In case of doubt... clearly state any assumptions made").

Find. (a) The power set and every partition of $\{a,b,c\}$. (b) A plain-English description of $S(\alpha,\beta)$, plus its union and intersection over all positive $\alpha,\beta$.

(a) Power set. Every subset of $\{a,b,c\}$, $2^3=8$ elements: $$\mathcal{P}(\{a,b,c\}) = \boxed{\{\varnothing,\{a\},\{b\},\{c\},\{a,b\},\{a,c\},\{b,c\},\{a,b,c\}\}}.$$
(a) Partitions. A partition splits $\{a,b,c\}$ into non-empty, pairwise-disjoint blocks whose union is the whole set. Enumerating by number of blocks (1, 2, or 3): $\boxed{5}$ partitions total (the Bell number $B_3=5$): $$\{\{a,b,c\}\},\ \{\{a\},\{b,c\}\},\ \{\{b\},\{a,c\}\},\ \{\{c\},\{a,b\}\},\ \{\{a\},\{b\},\{c\}\}.$$
(b-a) Describe $S(\alpha,\beta)$. $S(\alpha,\beta)$ is the closed, axis-aligned rectangular region in the plane centred at the origin, with horizontal half-width $\alpha$ and vertical half-height $\beta$ — i.e. a $2\alpha\times2\beta$ filled rectangle (including its boundary) centred at $(0,0)$.
(b-b) Union over all $\alpha,\beta>0$. For any point $(x,y)\in\mathbb{R}^2$, choosing $\alpha=|x|+1$ and $\beta=|y|+1$ places $(x,y)$ inside $S(\alpha,\beta)$. Since $\alpha,\beta$ range over ALL positive reals (unboundedly), every point of the plane is covered by some member of the family: $$\bigcup_{\alpha>0,\beta>0}S(\alpha,\beta) = \boxed{\mathbb{R}^2}.$$
(b-c) Intersection over all $\alpha,\beta>0$. The origin $(0,0)$ satisfies $-\alpha\le0\le\alpha$ and $-\beta\le0\le\beta$ for every $\alpha,\beta>0$, so it belongs to every $S(\alpha,\beta)$. Any other point $(x,y)\ne(0,0)$ fails to be in $S(\alpha,\beta)$ once $\alpha<|x|$ or $\beta<|y|$ (which is always achievable for some positive $\alpha,\beta$ since they range arbitrarily close to $0$). Hence $$\bigcap_{\alpha>0,\beta>0}S(\alpha,\beta) = \boxed{\{(0,0)\}}.$$

Final results — Question 4
Part	Result
(a) Power set	8 subsets — see boxed list
(a) Partitions	5 partitions (Bell number $B_3=5$)
(b-a) Description	Closed axis-aligned rectangle, $2\alpha\times2\beta$, centred at origin
(b-b) Union	$\mathbb{R}^2$ (the whole plane)
(b-c) Intersection	$\{(0,0)\}$ (just the origin)

Topic: Power sets, set partitions (Bell numbers), and indexed unions/intersections of a growing/shrinking set family.

Key relations: $|\mathcal{P}(A)|=2^{|A|}$; number of partitions of an $n$-set is the Bell number $B_n$ ($B_3=5$); for a monotone-in-parameter family, $\bigcup$ tends to the limiting largest member and $\bigcap$ to the limiting smallest member.

Why this works: $S(\alpha,\beta)$ grows as $\alpha,\beta$ increase and shrinks toward the origin as they decrease — since the index set ranges over ALL positive reals (no fixed bound), the union sweeps out arbitrarily large rectangles (covering the plane) while the intersection sweeps toward arbitrarily small rectangles (collapsing to the single point that is common to every one of them, the origin).

Common pitfall: Confusing this indexed union/intersection (over a continuum of $\alpha,\beta$) with a union/intersection of only two or three explicit sets; forgetting the origin is the ONLY point guaranteed to survive every arbitrarily-small rectangle.

Source: Rosen, Discrete Mathematics and Its Applications, §2.1-2.2 (sets, power sets), §2.5 (indexed unions/intersections); Epp, Discrete Mathematics with Applications, Ch.5 (set partitions).

← Question 3 Next: Question 5 →