Discrete Mathematics: Sets and Functions

Russel's Paradox

• Illustrates that not all sets can be defined, specifically highlighting the contradiction that arises when considering the set of all sets that do not contain themselves.
• Defining characteristic of S: S is the set of all sets that do not contain themselves as a member.
• If S were to contain itself: It would contradict its own definition – if S contains itself, then by definition it shouldn't be in S.
• Direct implication: The existence of sets that cannot be defined, exposing a flaw in naive set theory.
• Formulation: Bertrand Russell.
• Solution function: f(x) = { x if x ∉ x, 0 if x ∈ x }. This function maps a set to itself if it doesn't contain itself, and to 0 otherwise.
• One-to-one: For unique inputs, the outputs are different. This is because no two sets can map to the same output.
• Onto: It covers the entire range of its outputs, including the sets that don't contain themselves and the set containing 0.
• Range: The set itself (as it contains all sets that don't contain themselves and the set containing 0).
• f(5): 5, as 5 doesn't contain itself.

Sets and Subsets

• Condition for subset: Every element of set A is also an element of set B. Written as A ⊆ B.
• ∅ ⊆ S: The empty set is a subset of every set, as it contains no elements that aren't in S.
• a ∈ S → a ∈ S: This implication is always true, meaning that if an element is in a set, it is also in the same set.
• Subset truth: The union of two sets is a superset of both sets.
• 'a ∈ ∅ is always false': The empty set contains no elements, meaning any element cannot be in the empty set.

Countability and Bijections

• Even integers function: f(n) = 2n.
• Z countable: The set of integers Z is countable, meaning it can be put into a one-to-one correspondence with the set of natural numbers.
• Ordering for countability: 0, 1, -1, 2, -2, 3, -3, ....
• an = an-1 + 2an-2: As n increases, the growth of the sequence is exponential.

Matrices

• 3x4 matrix: A matrix with 3 rows and 4 columns.
• Plural of matrix: Matrices.
• Definition: A rectangular array of numbers, symbols, or expressions arranged in rows and columns.
• 5x2 matrix: This matrix will have 5 rows and only 2 columns.
• 0 columns: The matrix is considered empty or a null matrix.

Arithmetic Progression (AP) and Geometric Progression (GP)

• Common difference: d = r - a = 5 - 2 = 3
• a = 1, r = -1: The first two terms are 1 and -1.
• a = 6, r = 1/3: This represents a geometric progression, where each term is 1/3 of the previous term.
• First term 1, d = -1: The third term would be 1 + (-1) + (-1) = -1.
• a = 6, r = 1/3: This progression is decreasing geometrically, where the terms are getting smaller by a factor of 1/3.