Week1 Notes

Study Notes

A set is a collection of distinct objects, also known as elements or members.
An element is either in a set or not, it cannot be both. This is known as the Law of Non-Contradiction.
Example: The set of prime numbers (P): P = {p | p is a natural number and p is prime}.
The set of all sets that do not contain themselves (R) is a paradoxical concept that leads to Russell's Paradox.

Natural numbers (N): 0, 1, 2, 3,...
Integers (Z): ... -3, -2, -1, 0, 1, 2, 3...
Rational numbers (Q): All numbers that can be expressed as a ratio of two integers (a/b, where b is not zero).
Real numbers (R): All rational and irrational numbers.
Complex numbers (C): All numbers in the form a + bi, where a and b are real numbers and i is the imaginary unit (i² = -1).

Subset (⊆): Set A is a subset of set B if and only if every element of A is also in B.
Equal sets (=): Sets A and B are equal if and only if they have the same elements.
Union (∪): The union of sets A and B is the set of all elements that are in either A or B.
Intersection (∩): The intersection of sets A and B is the set of all elements that are in both A and B.
Complement (Aᶜ): The complement of set A with respect to set B (B \ A) is the set of all elements in B but not in A.
Cartesian product (×): The Cartesian product of sets A and B is the set of all possible ordered pairs (a, b) where a is an element of A and b is an element of B.

A binary operation on a set A is a rule for assigning to each pair of elements x and y in A exactly one element z in A. Examples include addition, subtraction, multiplication.
Commutative: A binary operation is commutative if the order of the operands does not affect the result (a * b = b * a).
Associative: A binary operation is associative if the grouping of operands does not affect the result (a * (b * c) = (a * b) * c).
Identity: A binary operation has an identity element 'e' if a * e = e * a = a for all elements 'a' in the set.
Inverse: An element 'a' has an inverse 'a⁻¹' if a * a⁻¹ = a⁻¹ * a = e, where 'e' is the identity element.

The set of real numbers (R) under addition is commutative, associative, and has an identity element (0).
The set of integers (Z) under multiplication is commutative, associative, and has an identity element (1).
The set of integers modulo 2 (Z₂ = {0, 1}) under addition is commutative, associative, and has an identity element (0).
The set of all possible permutations of a set under composition is associative and has an identity element (the identity permutation).

A set is a collection of elements.
An element is either in a set or not in a set, but not both.
Example: The set of prime numbers (p ∈ P) is contained within the set of natural numbers (P ⊂ N).
Example: The set R of all sets that do not contain themselves is a paradoxical set.

Subset: A is a subset of B (A ⊆ B) if and only if every element of A is in B.
Equality: A is equal to B (A = B) if and only if the elements of A and B are the same.
Union: The union of two sets A and B (A ∪ B) is the set of elements that are in either A or B.
Intersection: The intersection of two sets A and B (A ∩ B) is the set of elements that are in both A and B.
Complement: The complement of a set A with respect to a set B (Aᶜ) is the set of elements in B that are not in A.
Cartesian Product: The cartesian product of two sets A and B (A x B) is the set of all possible ordered pairs (a, b) where a is an element of A and b is an element of B.

A binary operation on a set A is a rule for assigning to each pair of elements (a, b) in A exactly one element a ∘ b in A.
Examples include:
- Addition (+) in the set of natural numbers.
- Multiplication (*) in the set of real numbers.
- min(a, b) in the set of real numbers.
- max(a, b) in the set of real numbers.
Operations can be represented using operation tables.

Commutative: a ∘ b = b ∘ a for all a, b in A.
Associative: (a ∘ b) ∘ c = a ∘ (b ∘ c) for all a, b, c in A.
Identity Element: There exists e in A such that a ∘ e = a and e ∘ a = a for all a in A.
Inverse Element: For every a in A, there exists an inverse element a⁻¹ in A such that a ∘ a⁻¹ = e and a⁻¹ ∘ a = e.

Set of Real Numbers (R) with addition (+) is commutative, associative, has an identity element (0), and has inverses for all elements except 0.
Set of People with their Height with the operation "shortest" is not commutative, not associative, and has no identity element.
Set of Natural Numbers with addition (+) is commutative, associative, and has an identity element (0), but does not have inverses for every element.
Set of the Integers with multiplication (*) is commutative and associative.
Set of the Integers with the operation defined by x ⊕ y = x + y + 1 is commutative, associative, and has an identity element (-1), and has inverses for all elements.

Lemma 1: Let A and B be sets, A is a subset of B (A ⊆ B) if and only if A is a subset of B (A ⊆ B) and B is a subset of A (B ⊆ A).
Lemma 2: Let A, B, and C be sets. If A is a subset of B (A ⊆ B) and B is a subset of C (B ⊆ C) then A is a subset of C (A ⊆ C).