Sets and Logic Basics — Mathematics Knowledge System

Overview

Sets and propositional logic are the bedrock of modern mathematics. A set is a collection of distinct objects; logic provides the language for making precise mathematical statements. Together they underpin every branch of mathematics, from algebra to analysis.

Intuition

A set is like a bag: you list what's in it, and order or repetition don't matter. Logic connectives are like switches: AND requires both to be true, OR requires at least one, NOT flips the truth value. De Morgan's laws say that negating 'A and B' is the same as 'not A or not B' -- like saying 'not (raining and cold)' means 'either it's not raining or it's not cold.'

Formal Definition

Definition

A set A is a collection of distinct elements. We write x in A if x is an element of A, and x not in A otherwise. The empty set is {}. A is a subset of B (written A subset B) if every element of A is in B. The union, intersection, and complement are the basic operations.

A \cup B = \{x : x \in A \text{ or } x \in B\}

Union

A \cap B = \{x : x \in A \text{ and } x \in B\}

Intersection

A^c = \{x \in U : x \notin A\}

Complement (relative to universe U)

\overline{A \cup B} = \overline{A} \cap \overline{B}

De Morgan's first law

\overline{A \cap B} = \overline{A} \cup \overline{B}

De Morgan's second law

Notation

Notation	Meaning
$\in$	Element of
$\subseteq$	Subset of (subset or equal)
$\cup$	Union
$\cap$	Intersection
$A^c \text{ or } \overline{A}$	Complement of A
$\emptyset$	The empty set (no elements)
$P \Rightarrow Q$	P implies Q (if P then Q)
$P \Leftrightarrow Q$	P if and only if Q

Theorems

Theorem 1: De Morgan's Laws (Sets)

For any sets A and B in a universe U: (A union B)^c = A^c intersection B^c, and (A intersection B)^c = A^c union B^c.

Theorem 2: De Morgan's Laws (Logic)

NOT(P AND Q) is equivalent to (NOT P) OR (NOT Q). NOT(P OR Q) is equivalent to (NOT P) AND (NOT Q).

Theorem 3: Contrapositive

The implication P => Q is logically equivalent to its contrapositive (NOT Q) => (NOT P). Both have the same truth table.

Theorem 4: Distributive Laws

A intersection (B union C) = (A intersection B) union (A intersection C). A union (B intersection C) = (A union B) intersection (A union C).

Worked Examples

1
A union B contains all elements in A or B (or both):
$A \cup B = \{1,2,3,4,5,6\}$
2
A intersection B contains elements in both A and B:
$A \cap B = \{3,4\}$

✓ Answer

A union B = {1,2,3,4,5,6}; A intersection B = {3,4}.

Practice Problems

Easyapplication

Let U = {1,...,10}, A = {2,4,6,8,10}, B = {1,2,3,4,5}. Find A^c, B^c, and A intersection B^c.

Easyproof writing

Prove De Morgan's law: (A union B)^c = A^c intersection B^c.

EasyMultiple choice

Which truth table rows make the implication P => Q FALSE?

Easyapplication

State the contrapositive of: 'If n^2 is even, then n is even.'

Common Mistakes

Common Mistake

A union B and A intersection B are the same thing.

Union (A cup B) includes everything in A or B; intersection (A cap B) includes only what is in both. They are equal only if A = B.

Common Mistake

P => Q is false when P is false.

An implication is vacuously true when P is false, regardless of Q. Only P=true, Q=false makes it false.

Common Mistake

NOT(A AND B) = (NOT A) AND (NOT B).

By De Morgan's law, NOT(A AND B) = (NOT A) OR (NOT B). The AND becomes an OR under negation.

Quiz

Historical Background

Georg Cantor developed set theory in the 1870s-1880s, revolutionizing mathematics by providing a unified foundation. Gottlob Frege formalized propositional logic in 1879. Bertrand Russell's paradox (1901) forced a more careful axiomatic approach, leading to Zermelo-Fraenkel set theory (ZF), the standard foundation today. Augustus De Morgan stated his famous laws in 1847, simplifying reasoning about complements.

1847
De Morgan states his laws of set/logic complementation
Augustus De Morgan
1879
Frege's Begriffsschrift formalizes propositional and predicate logic
Gottlob Frege
1874
Cantor publishes his first paper on set theory and countability
Georg Cantor
1901
Russell discovers the paradox of the set of all sets that do not contain themselves
Bertrand Russell
1908
Zermelo proposes axiomatic set theory to avoid paradoxes
Ernst Zermelo

Summary

Sets are collections of distinct elements; the main operations are union, intersection, and complement.
Propositional logic uses AND, OR, NOT, and implication to build and evaluate mathematical statements.
De Morgan's laws: NOT(A AND B) = (NOT A) OR (NOT B), and NOT(A OR B) = (NOT A) AND (NOT B).
An implication P => Q is equivalent to its contrapositive (NOT Q) => (NOT P); both have the same truth table.

References

BookHalmos, P. R. (1960). Naive Set Theory. Van Nostrand.
BookVelleman, D. J. (2006). How to Prove It: A Structured Approach (2nd ed.). Cambridge University Press.
WebsiteWeisstein, E. W. Set. MathWorld.