Set Theory and Induction

These flashcards cover key concepts related to set theory and mathematical induction, defining important terms and outlining essential proofs and examples.

What does x ∈ A mean?

x is an element of set A.

What does x ∉ A mean?

x is not an element of set A.

What is the empty set?

The empty set ∅ contains no elements.

Is {∅} = ∅?

No, {∅} has one element (the empty set), while ∅ has zero elements.

What does A ⊆ B mean?

Every element of A is also in B.

How do you prove A ⊆ B?

Assume x ∈ A, show x ∈ B.

When are two sets equal?

A = B iff A ⊆ B and B ⊆ A.

What is the union of two sets A and B?

A ∪ B = {x : x ∈ A or x ∈ B}.

What is the intersection of two sets A and B?

A ∩ B = {x : x ∈ A and x ∈ B}.

When are two sets disjoint?

When A ∩ B = ∅.

What is the set difference of A and B?

A \ B = {x : x ∈ A and x ∉ B}.

What is the complement of set A?

Aᶜ = U \ A, where U is the universe.

What are De Morgan’s Laws?

(A ∪ B)ᶜ = Aᶜ ∩ Bᶜ and (A ∩ B)ᶜ = Aᶜ ∪ Bᶜ.

What is the power set of X?

𝒫(X) = the set of all subsets of X.

How many elements are in 𝒫(X) if |X| = n?

2ⁿ.

What is the Cartesian product of A and B?

A × B = {(a,b) : a ∈ A and b ∈ B}.

What happens if A or B is empty in a Cartesian product?

A × B = ∅.

What is the base case in induction?

The first value of n where P(n) is proven true.

What is the inductive hypothesis?

The assumption that P(k) is true for an arbitrary k.

What is the inductive step?

Show P(k) → P(k+1) using the inductive hypothesis.

What is the final sentence of induction?

Thus, by induction, P(n) holds for all n ≥ n₀.

What is strong induction?

Assume P(n₀),…,P(k) to prove P(k+1).

When do we use strong induction?

When the proof depends on multiple previous values, not only k−1.

What must ALWAYS be proved first in induction?

The base case.

How do you show where the inductive hypothesis is used?

Explicitly cite it: 'By the inductive hypothesis, …'.

What is an example of induction?

Sum of first n integers: 1+2+…+n = n(n+1)/2.

Another induction example?

2ⁿ ≥ n+1 for n ≥ 0.

What is the proof of (A ∩ B)ᶜ = Aᶜ ∪ Bᶜ?

Element chase using 'not (P and Q)'.

What is the proof template for A = B?

Show A ⊆ B and B ⊆ A.

What is the subset proof template?

Let x ∈ A. Show x ∈ B. Conclude A ⊆ B.