Chapter2 - Sets

Set

An unordered collection of objects called elements or members.

Element

An object contained within a set; denoted by a ∈ A when a is in set A, or a ∉ A when not.

Roster Method

A way to describe a set by listing its members, where order is not important and duplicates do not change the set.

Set-Builder Notation

Describes a set by specifying the property or properties satisfied by its members, often using predicates.

Interval Notation

Represents sets of real numbers within intervals, using [a,b], (a,b), [a,b), or (a,b] to show open or closed endpoints.

Universal Set

The set U containing all objects currently under consideration for the given context.

Empty Set

The set with no elements, denoted by ∅ or {}.

Set Equality

Two sets are equal if and only if they have exactly the same elements.

Subset

A set A is a subset of B if every element of A is also an element of B; denoted A ⊆ B.

Proper Subset

A set A is a proper subset of B, denoted A ⊂ B, if A ⊆ B but A ≠ B.

Set Cardinality

The number of distinct elements in set A; denoted

Power Set

The set P(A) consisting of all subsets of set A; if A has n elements, P(A) has 2ⁿ elements.

Tuple

An ordered collection of elements; an n-tuple (a₁, a₂, …, aₙ) lists elements in a sequence.

Ordered Pair

A 2-tuple (a,b) which is equal to (c,d) only if a=c and b=d.

Cartesian Product

For sets A and B, the set A × B is the set of all ordered pairs (a,b) with a ∈ A and b ∈ B.

Relation

A subset R of A × B that defines a correspondence from elements of A to elements of B.

Union

For sets A and B, the union A ∪ B is the set of elements that are in A or B or both.

Intersection

For sets A and B, the intersection A ∩ B is the set of elements common to both A and B; A and B are disjoint if their intersection is empty.

Complement

For a set A in universal set U, the complement Ā is all elements in U that are not in A.

Difference

For sets A and B, the difference A − B is the set of elements in A that are not in B; also called the complement of B with respect to A.

Symmetric Difference

The set of elements in either A or B but not both.

Inclusion-Exclusion Principle

For sets A and B,

Identity Laws

A ∪ ∅ = A and A ∩ U = A are always true for any set A.

Domination Laws

A ∪ U = U and A ∩ ∅ = ∅ hold true for any set A.

Idempotent Laws

A ∪ A = A and A ∩ A = A for any set A.

Complementation Law

A ∪ Ā = U and A ∩ Ā = ∅ are always true for any set A in U.

Commutative Laws

For sets A and B, A ∪ B = B ∪ A and A ∩ B = B ∩ A always hold true.

Associative Laws

(A ∪ B) ∪ C = A ∪ (B ∪ C) and (A ∩ B) ∩ C = A ∩ (B ∩ C) are always true.

Distributive Laws

A ∪ (B ∩ C) = (A ∪ B) ∩ (A ∪ C) and A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C) hold true.

De Morgan’s Laws

The complement of A ∪ B is the intersection of their complements, and vice versa; both laws state the equivalence in true/false membership.

Absorption Laws

A ∪ (A ∩ B) = A and A ∩ (A ∪ B) = A are always true for any sets.

Generalized Union

The union over indexed sets A₁, A₂, …, Aₙ is the set containing all elements from any set within the collection.

Generalized Intersection

The intersection over indexed sets A₁, A₂, …, Aₙ is the set containing elements common to all sets in the collection.

Function

A mapping f from set A (domain) to set B (codomain) assigning each a ∈ A to exactly one b ∈ B; truth of assignment is shown by f(a) = b.

Mapping

Alternate term for a function, indicating correspondence from domain to codomain.

Image

In function f, the image of a is b if f(a) = b; b is true for a under f.

Preimage

Given function f, the preimage of b is a if f(a) = b; a is true for b under f.

Range

Set of all images of elements in domain A under function f, denoted f(A); shows all truth assignments for function outputs.

Injection

A function is injective or one-to-one if, for all a, b ∈ A, f(a) = f(b) implies a = b; every output is assigned by at most one input, and truth is unique.

Surjection

A function from A to B is surjective or onto if every element of codomain B is the image of at least one input in A; truth of coverage over B.

Bijection

A function is bijective or a one-to-one correspondence if it is both injective and surjective; every input and output pair is true exactly once.

Inverse Function

For bijection f, its inverse f⁻¹ assigns each b in codomain B back to a in A, reversing the original mapping; exists only if true bijection.

Composition of Functions

Given f: B→C and g: A→B, the composition f∘g maps each a in A to f(g(a)) in C; truth of mapping passes through both functions.

Floor Function

The function ⌊x⌋ returns the largest integer less than or equal to x; always true for real input x.

Ceiling Function

The function ⌈x⌉ returns the smallest integer greater than or equal to x; always true for real input x.

Factorial Function

Denoted n!, equals the product of all positive integers up to n; for n ≥ 0, 0! = 1 and truth of result is integer.

Sequence

A function from subset of integers (usually {0,1,…} or {1,2,…}) to another set S; notation aₙ shows the term's true value.

Geometric Progression

A sequence with initial term a and common ratio r, where each term is truthfully determined by multiplying previous term with r.

Arithmetic Progression

A sequence with initial term a and common difference d, where each term is truthfully determined by adding d to previous term.

String

A finite sequence of characters from a specified alphabet; truth of sequence length and content determined by elements.

Recurrence Relation

An equation expressing term aₙ of sequence in terms of previous terms; solution is a sequence whose terms are all true for the relation.

Initial Conditions

Specified terms of a sequence that precede application of recurrence relation; ensure the truth of sequence generation.

Fibonacci Sequence

Defined by f₀ = 0, f₁ = 1 and recurrence relation fₙ = fₙ₋₁ + fₙ₋₂; all terms generated are true for the relation.

Summation

Notation Σ expresses sum of sequence terms; the truth value of sum is determined by accumulated terms from lower to upper index.

Matrix

A rectangular array of numbers with m rows and n columns; entries are truthfully indexed by position.

Matrix Addition

For matrices A and B of same size, sum A+B is a matrix whose entries are the sum of corresponding entries; operation is true only for same-size matrices.

Matrix Multiplication

Given appropriate matrices A and B, product AB has entries that are sum of products of entries in rows and columns; not commutative, truth depends on order and dimension.

Identity Matrix

Matrix of order n with entries 1 on diagonal and 0 elsewhere; multiplication by identity matrix leaves matrix unchanged, always true.

Transpose

Matrix operation switching rows and columns; Aᵗ is true for square matrices that are symmetric.

Symmetric Matrix

A square matrix where aᵢⱼ = aⱼᵢ for all i, j; truth of entry equivalence holds under transposition.

Cardinality

Number of elements in a set; for countable or finite sets, truth is integer, for infinite sets, shows relative size.

Countable Set

A set that is finite or has the same cardinality as positive integers; elements can be listed and matched one-to-one, and truth is countability.

Uncountable Set

A set that cannot be matched one-to-one with positive integers; truth of existence proven by contradiction, e.g. Cantor diagonalization.

Hilbert’s Hotel

A thought experiment illustrating properties of countable infinity; truth of accommodation relies on bijective mappings.

Cantor Diagonalization

A proof technique for showing that certain sets are uncountable by constructing elements not in assumed lists; establishes truth of uncountability.