Sets and Propositions in Discrete Mathematics

Learning Objectives

• Define a set, describe how sets are written, and test membership using ∈ and ∉.
• Perform union, intersection, difference, and complement operations on sets and compute a power set.
• State and apply the laws of set algebra (commutative, associative, distributive, De Morgan's).
• Define a proposition and combine propositions using conjunction, disjunction, and negation.
• Build a truth table for a compound proposition and use it to check logical equivalence.
• Explain why sets and propositions underpin databases, digital logic, and program correctness.

Quick Answer

A set is a well-defined collection of distinct objects — the numbers {1, 2, 3} or the vowels {a, e, i, o, u}, for instance. A proposition is a declarative sentence that is either true or false, never both — "7 is prime" is a proposition, but "close the door" is not. Together, sets and propositions give computer science its two most basic building blocks: sets let us group and compare data (the backbone of databases, type systems, and collections), while propositional logic lets us reason precisely about conditions (the backbone of if statements, circuit design, and program verification). Nearly every later topic in discrete math — relations, functions, graphs, automata — is defined in terms of sets, and every conditional statement in code is a proposition in disguise.

What Are Sets?

A set is a collection of distinct, unordered elements. We write sets with curly braces and usually name them with capital letters:

$$A = \{1, 2, 3, 4\} B = \{\text{apple}, \text{banana}, \text{cherry}\}$$

Two properties define a set, and both trip students up if ignored:

• No duplicates. {1, 1, 2} and {1, 2} are the same set — writing an element twice doesn't create a second copy.
• No order. {1, 2, 3} and {3, 1, 2} are the same set — order of listing is irrelevant.

Membership is the fundamental question a set answers: does this object belong here or not? We write 3 ∈ A ("3 is an element of A") and orange ∉ B ("orange is not an element of B"). There is no partial or "maybe" membership — this all-or-nothing rule is exactly what makes a set a clean model for a WHERE clause in SQL or a Python in check.

Real-world example: Think of a set as a guest list at a party. Someone is either on the list or they aren't — you don't list the same person twice, and the order you typed the names in doesn't change who's invited. A database table's set of valid user IDs works the same way: each ID is either present or absent, never duplicated.

Common misunderstanding: Students often think {1, 2} and (1, 2) mean the same thing. They don't — the first is a set (unordered, {2, 1} is identical), the second is an ordered pair or tuple (order matters, (2, 1) is different). Confusing these leads to errors later when defining relations, which are built from ordered pairs of set elements.

Special Sets

Notation	Meaning
∅ or {}	The empty set — contains no elements
U	The universal set — everything under discussion in a given problem
ℕ, ℤ, ℚ, ℝ	Natural numbers, integers, rationals, reals
|A|	Cardinality of A — the number of elements in A

Set Operations

Set operations build new sets from existing ones — the set-theoretic equivalent of arithmetic.

Union (A ∪ B)

All elements that are in A, in B, or both.

$$A = \{1, 2, 3\}, \quad B = \{3, 4, 5\} A \cup B = \{1, 2, 3, 4, 5\}$$

Intersection (A ∩ B)

Only the elements shared by both sets.

$$A \cap B = \{3\}$$

Difference (A − B)

Elements in A that are not in B.

$$A - B = \{1, 2\}$$

Complement (A′)

Everything in the universal set U that is not in A.

$$U = \{1, 2, 3, 4, 5\}, \quad A = \{1, 2, 3\} A' = \{4, 5\}$$

Worked example — a database use case: Suppose Active = {101, 102, 103, 105} (active user IDs) and Premium = {102, 105, 108} (premium subscribers).

• Active ∩ Premium = {102, 105} — active and premium users, exactly the query SELECT id FROM users WHERE active AND premium.
• Active − Premium = {101, 103} — active but not paying, a natural upsell target list.
• Active ∪ Premium = {101, 102, 103, 105, 108} — anyone who is either active or a subscriber, useful for a "send this announcement to everyone who matters" query.

This is exactly why relational databases speak the language of sets: JOIN, UNION, and EXCEPT are just union, intersection, and difference wearing SQL clothing.

Why it matters: Every time you filter, merge, or de-duplicate data, you're doing set algebra. Understanding these operations abstractly means you can reason about a SELECT DISTINCT query, a spreadsheet filter, or a search-engine result set with the same four tools.

Common misunderstanding: Students sometimes think A − B is the same as B − A. It isn't — difference is not commutative. {1,2,3} − {3,4,5} = {1,2} but {3,4,5} − {1,2,3} = {4,5}. Always ask "elements of which set are we removing from?"

Power Set

The power set of A, written P(A), is the set of all subsets of A, including the empty set and A itself. If |A| = n, then |P(A)| = 2^n.

$$A = \{1, 2\} P(A) = \{ \emptyset, \{1\}, \{2\}, \{1, 2\} \}$$

This 2^n fact is not a coincidence — it's the same counting principle behind why n bits can represent 2^n distinct values, since each element is independently "in" or "out," exactly like each bit is independently 0 or 1.

Laws of Set Algebra

Law	Statement
Commutative	A ∪ B = B ∪ A, A ∩ B = B ∩ A
Associative	(A ∪ B) ∪ C = A ∪ (B ∪ C)
Distributive	A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C)
De Morgan's	(A ∪ B)' = A' ∩ B', (A ∩ B)' = A' ∪ B'
Identity	A ∪ ∅ = A, A ∩ U = A

Worked proof — De Morgan's law for sets: Show (A ∪ B)' = A' ∩ B'.

Take any element x.

• x ∈ (A ∪ B)' means x ∉ (A ∪ B), i.e., x is in neither A nor B.
• That means x ∉ A and x ∉ B, i.e., x ∈ A' and x ∈ B'.
• So x ∈ A' ∩ B'.

Since every element of (A ∪ B)' is in A' ∩ B' and the argument reverses step for step, the two sets contain exactly the same elements, so they're equal. ∎

Propositions and Logic

A proposition is a declarative statement that is definitively true or definitively false — never both, never neither. "2 + 2 = 4" is a proposition (true). "The sky is green" is a proposition (false, but still a proposition — truth value doesn't have to be true). "What time is it?" is not a proposition, because a question can't be true or false.

Logical Operators

Operator	Symbol	Meaning	True when...
Conjunction	P ∧ Q	P and Q	both P and Q are true
Disjunction	P ∨ Q	P or Q	at least one of P, Q is true
Negation	¬P	not P	P is false
Implication	P → Q	if P then Q	P is false, or Q is true

Worked example:

$$P: 2 + 2 = 4 \quad \text{(true)} Q: 3 > 5 \quad \text{(false)} P \land Q: \text{false — Q fails} P \lor Q: \text{true — P succeeds} \neg P: \text{false — P was already true}$$

Real-world example: An if statement in code is a proposition-testing machine. if (age >= 18 and hasID): is exactly the proposition P ∧ Q, and the program branches based on whether that compound proposition evaluates to true.

Why it matters: Compilers, database query planners, and digital circuits all reduce decisions to evaluating propositions. Boolean algebra (covered separately) is the algebra of these truth values, and every logic gate in a CPU implements one of these operators in silicon.

Common misunderstanding: Students often read P → Q as "P causes Q" or assume it's false whenever P is false. Actually P → Q is defined as true whenever P is false, regardless of Q — "if pigs fly, then 2+2=5" is considered true in logic, because the premise never holds. This "vacuous truth" feels unnatural until you see it modeled as ¬P ∨ Q.

Building a Truth Table

A truth table lists every possible combination of truth values for the input propositions and shows the result. For P ∧ Q and P ∨ Q:

P	Q	P ∧ Q	P ∨ Q	¬P
T	T	T	T	F
T	F	F	T	F
F	T	F	T	T
F	F	F	F	T

With n propositions, a truth table needs 2^n rows — the same power-of-two counting we saw with power sets, because each proposition is independently true or false.

Logical Equivalences

Two propositions are logically equivalent if they have identical truth tables — they're always true or false together, no matter the input values.

• De Morgan's Laws: ¬(P ∧ Q) ≡ ¬P ∨ ¬Q and ¬(P ∨ Q) ≡ ¬P ∧ ¬Q
• Double Negation: ¬(¬P) ≡ P
• Commutative: P ∧ Q ≡ Q ∧ P, P ∨ Q ≡ Q ∨ P

Worked proof — De Morgan's law for propositions: Show ¬(P ∧ Q) ≡ ¬P ∨ ¬Q by truth table.

P	Q	P ∧ Q	¬(P ∧ Q)	¬P	¬Q	¬P ∨ ¬Q
T	T	T	F	F	F	F
T	F	F	T	F	T	T
F	T	F	T	T	F	T
F	F	F	T	T	T	T

Columns 4 and 7 match on every row, so the two expressions are logically equivalent. ∎ Notice this is the exact propositional mirror of the set-theory De Morgan's law proved above — sets and propositions share the same algebraic skeleton, which is why they're taught together.

Diagram: How Sets and Propositions Connect

Key Terms

Term	Definition
Set	A well-defined, unordered collection of distinct elements.
Element	A member of a set, tested with ∈ (belongs) or ∉ (does not belong).
Cardinality	The number of elements in a set, written |A|.
Power set	The set of all subsets of a set A, with 2^n members when |A| = n.
Universal set	The set U of all objects under discussion in a given context.
Proposition	A declarative sentence with a definite truth value (true or false).
Conjunction / Disjunction	The logical AND (∧) and OR (∨) of two propositions.
Negation	The logical NOT (¬), which flips a proposition's truth value.
Logical equivalence	Two propositions that share identical truth tables for all inputs.
De Morgan's Laws	Rules relating negation to conjunction/disjunction (and complement to union/intersection).

Common Mistakes

Misconception 1: "Sets can have repeated elements if you write them twice." Why it's wrong: A set is defined by which elements it contains, not how many times you list them. {1, 1, 2} has exactly the same members as {1, 2}. Correct explanation: Writing an element more than once has no effect — always simplify a set listing to its distinct elements before reasoning about size or operations.

Misconception 2: "P → Q is false whenever P is false." Why it's wrong: This confuses implication with causation. By definition, P → Q is only false in the single case where P is true and Q is false; if P is false, the implication is true by default (vacuously). Correct explanation: Build the truth table before trusting intuition — P → Q ≡ ¬P ∨ Q, so any row with P false immediately makes the whole implication true.

Misconception 3: "A − B and B − A are the same set." Why it's wrong: Set difference is directional — it asks "what's left in the first set once you remove anything shared with the second." Correct explanation: Compute both separately with a concrete example, e.g., {1,2,3} − {2,3,4} = {1} while {2,3,4} − {1,2,3} = {4} — they only coincide when A and B are disjoint or identical.

Comparison and Connections

Concept	Sets	Propositions
Basic object	Elements	Truth values (T/F)
Combining rule	∪, ∩, complement	∨, ∧, ¬
"AND"-like operation	Intersection (∩)	Conjunction (∧)
"OR"-like operation	Union (∪)	Disjunction (∨)
Structural law family	Laws of set algebra	Logical equivalences
Counting rule	|P(A)| = 2^n	2^n rows in a truth table with n variables
Used heavily in	Databases, data structures, type theory	Digital logic, program verification, AI reasoning

Sets and propositions are two faces of the same underlying algebra (formally, both form a Boolean algebra): union mirrors disjunction, intersection mirrors conjunction, and complement mirrors negation. Recognizing this parallel means you only have to memorize De Morgan's law once — it works for both.

Practice Questions

Recall 1. What two properties must a collection of objects have to qualify as a set? Answer guidance: Elements must be distinct (no duplicates) and the collection is unordered (no positional meaning).

Recall 2. Define a proposition and give one example of a sentence that is not a proposition. Answer guidance: A proposition is a declarative statement with a definite truth value. "Please close the door" or "What time is it?" are not propositions — commands and questions have no truth value.

Understanding 1. Explain why A ∪ B corresponds to ∨ and A ∩ B corresponds to ∧. Answer guidance: An element belongs to A ∪ B if it's in A or B (disjunction-like condition); it belongs to A ∩ B only if it's in A and B (conjunction-like condition). Set membership behaves like a Boolean test, so the operations line up structurally.

Understanding 2. Why is P → Q considered true when P is false, even if Q is also false? Answer guidance: Implication only makes a promise about what happens if P holds. If P never holds, the promise is never tested, so it can't be broken — hence vacuously true. Formally P → Q ≡ ¬P ∨ Q, and ¬P is true whenever P is false.

Application 1. A school database has Enrolled = {S1, S2, S3, S4} and Scholarship = {S2, S4, S5}. Find the set of enrolled students who do not have a scholarship. Answer guidance: Enrolled − Scholarship = {S1, S3}.

Application 2. Write the propositional condition for "a user can checkout" if the rule is "the cart is non-empty AND (the user is logged in OR the cart is a guest cart)." Build a mini truth table with 2 of the 3 boolean inputs fixed to check one edge case. Answer guidance: NonEmpty ∧ (LoggedIn ∨ GuestCart). Edge case: if NonEmpty = F, the whole expression is false regardless of the other two, since ∧ needs both sides true.

Analysis 1. A set A has 5 elements. How many elements are in P(A), and how many of those subsets contain at least one element? Answer guidance: \|P(A)\| = 2^5 = 32. Exactly one of those (the empty set) has zero elements, so 32 − 1 = 31 subsets contain at least one element.

Analysis 2. Prove or disprove: A − (B ∪ C) = (A − B) ∩ (A − C). Answer guidance: This is true — it's De Morgan's law applied through set difference. Take x ∈ A − (B ∪ C): then x ∈ A and x ∉ (B ∪ C), meaning x ∉ B and x ∉ C. So x ∈ A − B and x ∈ A − C, hence x ∈ (A−B) ∩ (A−C). The steps reverse, proving equality.

FAQ

Is the empty set a subset of every set? Yes. Vacuously, every element of ∅ (there are none) satisfies "is in A," so ∅ ⊆ A for any set A, including ∅ itself.

What's the difference between ⊆ and ∈? ∈ relates an element to a set (3 ∈ {1,2,3}); ⊆ relates two sets ({1,2} ⊆ {1,2,3}). Mixing these up is one of the most common early errors — always check whether the left side is a single object or a collection.

Can a proposition's truth value change over time or context? The statement's form stays the same, but its truth value can depend on unstated context — "it is raining" is only a genuine proposition once you fix a time and place. In pure logic we usually treat propositional variables as fixed T/F values for the scope of a problem.

Why do we care about logical equivalence instead of just computing both sides? Equivalence rules let you simplify a complex logical expression (or a set expression) into a smaller one without checking every case by hand — this is exactly how digital circuit designers reduce gate counts and how compilers optimize boolean conditions in code.

How many rows does a truth table need for 4 propositions? 2^4 = 16 rows, since each of the 4 propositions is independently true or false.

Quick Revision

• A set is an unordered collection of distinct elements; duplicates and order don't matter.
• ∈ tests element membership; ⊆ compares whether one set is contained in another.
• Union (∪) = "or," intersection (∩) = "and," complement (′) = "not," difference (−) = "in this one but not that one."
• Power set of an n-element set has 2^n subsets, including ∅ and the set itself.
• De Morgan's laws swap ∪/∩ (or ∨/∧) with negation applied to each part: (A ∪ B)' = A' ∩ B'.
• A proposition is a statement with a definite, single truth value — true or false, never both.
• P → Q is false only when P is true and Q is false; it is vacuously true whenever P is false.
• A truth table with n propositional variables needs 2^n rows to cover all cases.
• Two propositions are logically equivalent if their truth tables match on every row.
• Sets and propositions share the same algebraic structure: ∪↔∨, ∩↔∧, complement↔negation.
• Set difference A − B is not commutative — order matters.
• These ideas are the foundation for relations, functions, Boolean algebra, and digital logic design.

Related Topics

Prerequisites: Basic algebraic notation, elementary logic (true/false reasoning from arithmetic), familiarity with reading mathematical symbols.

Related Topics: Boolean Algebra (this unit), Mathematical Logic and Predicate Logic (this unit), Relations and Functions, Venn diagrams.

Next Topics: Graph Theory (which builds structures out of sets of vertices and edges), Automata Theory (which defines languages as sets of strings accepted by logical rules).