0.2.1 · Sets: membership, subset, union, intersection, difference, cardinality, power set

0 · Recall Warm-up

Answer from memory first. Answers are in the Answer Vault at the bottom.

What is the difference between a schema and an instance? from Lesson 0.1.3
Which data model is used for conceptual design? from Lesson 0.1.4
Name the eight file-processing problems. from Lesson 0.1.1

1 · The Hook

In the relational model (Phase 2), a table is not "a grid of cells"; it is a set. That one fact decides many GATE answers: why a table has no duplicate rows, why the order of rows does not matter, why "students in CS and enrolled in DBMS" is an intersection. Before any database idea, you need sets.

2 · Predict First

A = {1, 2, 3, 4} and B = {3, 4, 5}. How many elements are in "everything in A or B", and how many in "things in A but not in B"? Also: is {1, 1, 2} a different set from {1, 2}?

Make a guess in your head. The answer opens Section 3.

3 · Core Concept

Predict First — the answer

A or B = {1, 2, 3, 4, 5}: 5 elements (3 and 4 are counted once). A but not B = {1, 2}: 2 elements. And {1, 1, 2} is the same set as {1, 2}: a set does not count repeats.

Sets and membership

A set is a collection of distinct objects, called its elements. Order does not matter and repeats are ignored: {1, 2} = {2, 1} = {1, 1, 2}.

x ∈ A means "x is an element of A"; x ∉ A means it is not. 2 ∈ {1, 2, 3}; 5 ∉ {1, 2, 3}.
The empty set ∅ = { } has no elements.
Set-builder notation describes a set by a rule: {x | x is a CS student} reads "the set of all x such that x is a CS student".

Subset

A ⊆ B (A is a subset of B) means every element of A is also in B. {1, 2} ⊆ {1, 2, 3}. Every set is a subset of itself, and ∅ is a subset of every set. A ⊂ B (proper subset) means A ⊆ B and A ≠ B. Two sets are equal exactly when A ⊆ B and B ⊆ A.

Operations

Operation	Symbol	Contains	{1,2,3,4} with {3,4,5}
Union	A ∪ B	elements in A or B (or both)	{1,2,3,4,5}
Intersection	A ∩ B	elements in A and B	{3,4}
Difference	A − B	elements in A but not in B	{1,2}
Difference	B − A	elements in B but not in A	{5}

Note A − B ≠ B − A in general. Useful identities: A ∩ B ⊆ A ⊆ A ∪ B, and A − B = A − (A ∩ B). Union and intersection are commutative (A ∪ B = B ∪ A) and associative.

Cardinality

The cardinality |A| is the number of elements in A. |{1, 2, 3}| = 3, |∅| = 0. For any two finite sets:

|A ∪ B| = |A| + |B| − |A ∩ B| (elements in both would otherwise be counted twice).

Power set

The power set P(A) is the set of all subsets of A, including ∅ and A itself. For A = {a, b}: P(A) = {∅, {a}, {b}, {a, b}}. If |A| = n then |P(A)| = 2ⁿ: each element is either in or out of a subset, two choices per element. This counts, for example, all possible groups of columns of a table (used for superkeys in Lesson 2.2.1).

4 · Visual

A = {1,2,3,4}, B = {3,4,5}. The overlap is A ∩ B; everything shaded is A ∪ B.

5 · Worked Examples

Example 1 Easy

A = {CS, EE, ME}, B = {EE, CE}. Find A ∪ B, A ∩ B, A − B and |A ∪ B|.

Solution

A ∪ B = {CS, EE, ME, CE}; A ∩ B = {EE}; A − B = {CS, ME}; |A ∪ B| = 3 + 2 − 1 = 4.

Example 2 Medium

List the power set of {roll, name, dept}. How many subsets contain roll?

Solution

P = {∅, {roll}, {name}, {dept}, {roll,name}, {roll,dept}, {name,dept}, {roll,name,dept}}: 2³ = 8 subsets. Those containing roll: fix roll as "in", the other two attributes are free: 2² = 4.

Example 3 GATE

A	= 40,	B	= 25 and	A ∪ B	= 55. Find	A ∩ B	and	A − B	.

Solution

A ∩ B	= 40 + 25 − 55 = 10.	A − B	=	A	−	A ∩ B	= 40 − 10 = 30.

6 · GATE Traps

A set has no duplicates and no order: {2, 1, 1} = {1, 2}, cardinality 2.
A − B is not B − A.
∅ ⊆ every set, and ∅ ∈ P(A); |P(A)| = 2ⁿ counts ∅ and A itself.
|A ∪ B| ≠ |A| + |B| when the sets overlap; subtract the overlap.
∈ (element of) is not ⊆ (subset of): 1 ∈ {1, 2} but {1} ⊆ {1, 2}.

7 · Memory Hook

"OR = Union (U-cup holds more), AND = Intersection (the ∩ cap is the overlap), MINUS = remove the other's bite." Power set: every element flips a coin, in or out → 2ⁿ outcomes.

8 · Connect the Dots

Lesson 0.1.4 said the relational model is the language DBMSs implement; this lesson gave the set ideas that model is built on. Next: sets whose elements are ordered tuples, the Cartesian product, which is exactly what a table is.

9 · Self-Test

GATE format. Try every question before opening the vault.

Q1 · NAT · 1 mark(s) — Cardinality

A	= 12,	B	= 9,	A ∩ B	= 4. What is	A ∪ B	?

Numerical answer: ________

Q2 · NAT · 1 mark(s) — Power set

How many subsets does a set of 5 attributes have (including ∅ and the full set)?

Numerical answer: ________

Q3 · MCQ · 1 mark(s) — Operations

A = {1, 2, 3}, B = {2, 3, 4}. A − B is:

(A) {1}
(B) {4}
(C) {1, 4}
(D) {2, 3}

Q4 · MSQ · 2 mark(s) — Subsets

Let A = {1, 2}. Which statements are true?

(A) ∅ ⊆ A
(B) {1} ∈ P(A)
(C) 1 ⊆ A
(D) A ⊆ A

Q5 · NAT · 2 mark(s) — Power set

How many subsets of {A, B, C, D, E} contain both A and B?

Numerical answer: ________

10 · Rule Card

Set = distinct elements, no order; x ∈ A; ∅ has no elements.
A ⊆ B: every element of A is in B. ∅ ⊆ A; A ⊆ A.
∪ or, ∩ and, − in first but not second; A − B ≠ B − A.
|A ∪ B| = |A| + |B| − |A ∩ B|.
|P(A)| = 2ⁿ for |A| = n; subsets containing k fixed elements: 2ⁿ⁻ᵏ.

11 · Concept Ledger

Unlocked in this lesson. From here on, these terms may be used.

setelement (∈)empty set ∅set-builder notationsubset ⊆proper subset ⊂union ∪intersection ∩difference −cardinality |A|power set P(A), 2ⁿ

12 · Answer Vault

Reveal answers when you’re ready

Recall Warm-up

The schema describes the data and rarely changes; the instance is the data stored at a moment.
The ER model.
Redundancy, inconsistency, difficult access, isolation, integrity, atomicity, concurrency, security.