Fundamental concepts of Topology

1 Set theory and Logic

1.1 Fundamental concepts

1.1.1 Basic Notation

1.1.1.1 Sets <- Capital letters

1.1.1.2 Objects (elements) <- lowercase letters

1.1.1.3 Logical Identity <- = (equality symbol)

1.1.1.4 A ⊂ B <- A is a subset of B , inclusion

1.1.1.4.1 Every element of A is also an element of B

1.1.1.5 A \subsetneq B <- A is a proper subset of B, proper inclusion

1.1.1.5.1 A \subset B and A is different from B

1.1.2 The Union of Sets and the meaning of ‘or’

1.1.2.1 Union of A and B ( A \cup B) = { x | x \in A or x \in B}

1.1.2.1.1 P or Q : P or Q or both

1.1.3 The Intersection of Sets, the Empty Set and the Meaning of “if .. Then”

1.1.3.1 Intersection of A and B ( A \cap B) = { x | x \in A and x \in B}

1.1.3.2 Empty set \empty : the set having no elements

1.1.3.2.1 A \cup \empty = A

1.1.3.2.2 A \cap \empty = \empty

1.1.3.3 Disjoint (a set A, a set B) : A \cap B = \empty

1.1.3.4 If (Hypothesis), then (conclusion)

1.1.3.4.1 Vacuously true : no case for which the hypothesis holds

1.1.4 Contrapositive and Converse

1.1.4.1 Contrapositive ( ‘If P, then Q ‘ statement) : If Q is not true, then P is not true

1.1.4.2 Converse ( ‘If P, then Q ‘ statement) : If Q, then P

1.1.4.3 P <-> Q : P holds iff Q holds

1.1.5 Negation ( a statement P ) : not P

1.1.6 The difference of two sets

1.1.6.1 Difference of two sets A, B ( Complement of B relative to A)

1.1.6.1.1 A – B = { x | x \in A and x \notin B}

1.1.7 Rules of set theory

1.1.7.1 Distributive law (sets A, B, C)

1.1.7.1.1 A \cap (B \cup C) = (A \cap B) \cup (A \cap C)

1.1.7.1.2 A \cup (B \cap C) = (A \cup B) \cap (A \cup C)

1.1.7.2 Demorgan’s laws

1.1.7.2.1 A – (B \cup C) = (A – B) \cap (A – C)

1.1.7.2.2 A – (B \cap C) = (A – B) \cup (A – C)

1.1.8 Collection of the sets

1.1.8.1 Power set of A ( \mathcal{P} (A) ): set of all subsets of A

1.1.8.2 Collection of sets : a set whose elements are sets

1.1.9 Arbitrary unions and intersections

1.1.9.1 Given a collection \mathcal{A} of sets,

1.1.9.1.1 Union of the elements of \mathcal{A}

1.1.9.1.1.1 \bigcup_{A \in \mathcal{A}} A = { x | x \in A for at least one A \in \mathcal{A}}

1.1.9.1.2 Intersection of the elements of \mathcal{A}

1.1.9.1.2.1 \bigcap_{A \in \mathcal{A}} A = { x | x \in A for every A \in \mathcal{A}}

1.1.9.1.3 \bigcup_{A \in \mathcal{A}} A = \empty

1.1.9.1.4 \bigcap_{A \in \mathcal{A}} A = (Not defined)

1.1.10 Cartesian Product

1.1.10.1 Ordered pair of objects a , b : a \times b

1.1.10.1.1 All ordered pairs of real numbers is a plane

1.1.10.2 Cartesian product ( sets A , B) : A \times B = {a \times b | a \in A and b \in B}

1.2 Function

1.2.1 A rule of assignment : a subset r of the cartesian product C x D of two sets, having the property that each element of C appears as the first coordinate of at most one ordered pair belonging to r.

1.2.1.1 [c \times d \in r and c \times d’ \in r] -> [d = d’]

1.2.1.2 Domain (a rule of assignment r) : { c | there exists d \in D s.t. c \times d \in r}

1.2.1.3 Image ( a rule of assignment r) : {d | there exists c \in C s.t. c \times d \in r}

1.2.2 Function f : a rule of assignment r, together with a set B that contains the image set of r.

1.2.2.1 Domain (a function f) : Domain of the rule r

1.2.2.2 Image set (a function f) : the image set of r

1.2.2.3 Range ( a function f) : the set B

1.2.2.3.1 f is a function having domain A and range B : f : A -> B

1.2.2.4 value ( function f, element a of Domain (f) ) : unique element of B the rule determining f assigns to a

1.2.3 Restriction of function f | A_{0} : If f : A -> B and if A_{0} is a subset of A, we define the restriction of f to A_{0} to be the function mapping A_{0} into B whose rule is {(a,f(a)) | a \in A_{0}}

1.2.4 Composite g \bullet f : given functions f : A->B and g : B->C, the composite of f and g is the function g \bullet f : A -> C defined by equation (g \bullet f)(a) = g(f(a))

1.2.5 Injective : A function f : A -> B is said to be injective (or one -to- one) if for each pair of distinct points of A, their images under f are distinct.

1.2.6 Surjective : f is said to map A onto B if every element of B is the image of some element of A under the function f.

1.2.7 Bijective : f is said to be one-to-one correspondence if f is both injective and surjective

1.2.7.1 If f is bijective, there exists a function from B to A, called the inverse of f. f^{-1}

1.2.7.2 (Criterion of bijection) : Let f : A->B. if there are functions g : B->A and h:B->A s.t. g(f(a)) = a for every a in A and f(h(b)) = b for every b in B, then f is bijective and g = h = f^{-1}

1.2.8 Image of A_{0} under f : Let f:A->B. if A_{0} is a subset of A, we denote by f(A_{0}) the set of all images of points of A_{0} under the function.

1.2.8.1 Preimage of B_{0} under f : if B_{0} is a subset of B, f^{-1}(B_{0}) is the set of all elements of A whose images under f lie in B_{0}.

1.2.8.2 A_{0} \subseteq f^{-1}(f(A_{0})) (equality if f is injective)

1.2.8.3 F(f^{-1}(B_{0})) \subseteq B_{0} (equality if f is surjective)

1.3 Relations

1.3.1 A relation on a set A : a subset C of the cartesian product A \times A

1.3.2 Equivalence relation on a set A : a relation C on A with

1.3.2.1 (Reflexivity) : xCx for every x in A

1.3.2.2 (Symmetry) if xCy, then yCx

1.3.2.3 (Transitivity) if xCy and yCz, then xCz

1.3.3 Equivalence class determined by x : given an equivalence relation ~ on a set A and an element x of A, we define a certain subset E of A, by the equation E = { y | y ~ x }

1.3.3.1 Two equivalence classes E and E’ are either disjoint or equal.

1.3.4 Partition of a set A : a collection of disjoint nonempty subsets of A whose union is all of A.

1.3.4.1 Given any partition \mathcal{D} of A, there is exactly one equivalence relation on A from which it is derived.

1.3.5 Order relations ( a relation C on a set A)

1.3.5.1 (Comparability) For every x and y in A for which x \neq y, either xCy or yCx.

1.3.5.2 (nonreflexivity) : For no x in A does the relation xCx hold.

1.3.5.3 (Transitivity) If xCy and yCz, then xCz

1.3.6 Open interval in X : if X is a set and < is an order relation on X, and if a < b, we use the notation (a, b) to denote the set {x | a < x < b }

1.3.6.1 a is the immediate predecessor of b, and b is the immediate predecessor of a if (a, b) is empty

1.3.7 Suppose that A and B are two sets with order relations <{A} and <{B} respectively, We say that A and B have the same order type if there is a bijective correspondence between them that preserves order

1.3.7.1 Preserve order : a_{1} <{A} a{2} -> f(a_{1}) <{B} f(a{2})

1.3.8 Dictionary order relation : Suppose A and B are two sets with order relations <{A} and <{B} respectively, define an order relation on A \times B by defining a_{1} \times b_{1} < a_{2} times b_{2} if a_{1}<{A}a{2} or if a_{1} = a_{2} and b_{1} <{B} b{2}.

1.3.9 Largest element of A_{0} (an element b) : Suppose that A is a set ordered by relation <. Let A_{0} be a subset of A. b \in A_{0} and if x \le b for every x \in A_{0}

1.3.10 Smallest element of A_{0} (an element a) : a \in A_{0} and if a \le x for every x \in A_{0}

1.3.11 Bounded above (a subset A_{0} of A) : there is an element b of A s.t. x \le b for every x \in A_{0}.

1.3.11.1 Upper bound for A_{0} : b

1.3.11.2 The least upper bound of A_{0} [supremum of A_{0}, sup A_{0}] : a smallest element of the set of all upper bounds for A_{0}

1.3.11.3 Least upper bound property ( an ordered set A) : every nonempty subset A_{0} of A that is bounded above has a least upper bound

1.3.12 Bounded below (a subset A_{0} of A) : there is an element a of A s.t. a \le x for every x \in A_{0}.

1.3.12.1 Lower bound for A_{0} : a

1.3.12.2 The greatest lower bound of A_{0} [infimum of A_{0}, inf A_{0}] : a largest element of the set of all lower bounds for A_{0}

1.3.12.3 Greatest lower bound property (an ordered set A) : every nonempty subset A_{0} of A that is bounded below has the greatest lower bound property.

1.4 The Integers and the real numbers

1.4.1 Binary operation on a set A : a function f mapping A \times A into A

1.4.2 Assume the existence of the set of real numbers \mathbb{R} with +, \cdot, <

1.4.2.1 Algebraic properties

1.4.2.1.1 (x+y) + z = x + (y+z) , (x \cdot y) \cdot z = x \cdot (y \cdot z) for all x, y, z in \mathbb{R}

1.4.2.1.2 x + y = y + x, x \cdot y = y \cdot x for all x,y in \mathbb{R}

1.4.2.1.3 There exists a unique element of \mathbb{R} called zero, denoted by 0, s.t. x + 0 = x for all x \in \mathbb{R}, There exists a unique element of \mathbb{R} called one, denoted by 1, s.t. x \cdot 1 = x for all x \in \mathbb{R}

1.4.2.1.4 (Negative of x) For each x in \mathbb{R}, there exists a unique y in \mathbb{R} s.t. x + y = 0,

1.4.2.1.5 (Reciprocal of x) For each x in \mathbb{R} different from 0, there exists a unique y in \mathbb{R} s.t. x\cdot y = 1.

1.4.2.1.6 x \cdot (y+z) = (x \cdot y) + (x \cdot z) for all x, y, z \in \mathbb{R}.

1.4.2.2 A Mixed Algebraic and Order Property

1.4.2.2.1 if x > y, then x + z > y + z. If x > y and z > 0, then x \cdot z > y \cdot z

1.4.2.3 Order properties

1.4.2.3.1 The order relation < has the least upper bound property.

1.4.2.3.2 If x < y, there exists an element z s.t. x < z and z < y

1.4.2.4 Subtraction operation : z-x = z + (-x)

1.4.2.5 Quotient z/x = z \cdot (1/x)

1.4.2.6 Laws of inequalities : If x > y and z < 0, then x \cdot z < y \cdot z

1.4.2.7 Field : only algebraic properties of above

1.4.2.8 Ordered field : algebraic property and a mixed algebraic and order property of above

1.4.2.9 Linear continuum : only order properties of above

1.4.3 Inductive ( a subset of \mathbb{R}) : it contains the number 1 and if for every x in A, the number x + 1 is also in A.

1.4.4 Positive Integers Z_{+} = \bigcap_{A \in \mathcal{A}} A

1.4.4.1 Z_{+} is inductive

1.4.4.2 (Principle of Induction) : if A is an inductive set of positive integers, then A = Z_{+}

1.4.5 Integers \mathbb{Z} : a set consisting of Z_{+}, the number 0, the negatives of the elements of Z_{+}

1.4.6 Rational numbers \mathbb{Q} : a set of quotients of integers

1.4.7 Section S_{n} of the positive integers : S_{n+1} = {1,…,n}, S_{1} = \empty

1.4.8 (Well-ordering property) : Every nonempty subset of \mathbb{Z}_{+} has a smallest element.

1.4.9 (Strong induction principle) : Let A be a set of positive integers. Suppose that for each positive integer n, the statement S_{n} \subset A implies the statement n \in A, then A = \mathbb{Z}_{+}.

1.4.10 Proofs using least upper bound axiom

1.4.10.1 Archimedian ordering property of the real line : \mathbb{Z}_{+} of positive integers has no upper bound in \mathbb{R}

1.4.10.2 Greatest lower bound property

1.4.10.3 Existence of a unique positive square root for every positive real number

1.5 Cartesian Products

1.5.1 Let \mathcal{A} be a nonempty collection of sets.

1.5.1.1 Indexing function (\mathcal{A}) : a surjective function f from some set J to \mathcal{A}.

1.5.1.1.1 Index set : J

1.5.1.1.2 Indexed family of sets {A_{\alpha}}_{\alpha \in J} : the collection \mathcal{A} with indexing function f

1.5.1.1.2.1 A_{\alpha} = f(\alpha)

1.5.2 \bigcup_{\alpha \in J} A_{\alpha} = {x | for at least one \alpha \in J, x \in A_{\alpha}}

1.5.3 \bigcap_{\alpha \in J} A_{\alpha} = {x | for every \alpha \in J, x \in A_{\alpha}}

1.5.4 M-tuple of elements of X : Let m be a positive integer. Given a set, a function \mathbf{x} : {1,…,m} -> X

1.5.4.1 (x_{1}, …, x_{m})

1.5.4.2 Ith coordinate of \mathbf{x} : value of \mathbf{x} at I

1.5.4.3 Cartesian product ({A_{1}, …, A_{m}} being a family of sets indexed with the set {1,…,m}) :

1.5.4.3.1 Let X = A_{1} \cup … \cup A_{m}. then \prod_{I = 1}^{m} A_{i} or A_{1} \times … \times A_{m} = set of all m-tuples (x_{1} , …, x_{m}) of elements of X s.t. x_{i} \in A_{i} for each i.

1.5.4.4 X^{m} <- M-tuple of elements of X

1.5.5 \omega -tuple of elements of a set X : \mathbf{x} : \mathbb{Z}_{+} -> X

1.5.5.1 Also called sequence , infinite sequence, (x_{1}, x_{2}, …) , (x_{n}){n \in \mathbb{Z}{+}_

1.5.5.2 Ith coordinate of \mathbf{x} : value of \mathbf{x} at I

1.5.5.3 Cartesian product ({A_{1}, A_{2}, … } being a family of sets indexed with positive integers) :

1.5.5.4 Let X = Union of the sets in this family. then \prod_{I = \mathbb{Z}{+}} A{i} or A_{1} \times A_{2} \times… = set of all \omega -tuples (x_{1} , x_{2}… ) of elements of X s.t. x_{i} \in A_{i} for each i.

1.5.5.5 X^{\omega} <- 1.5.5 \omega -tuple of elements of a set X

1.6 Finite sets

1.6.1 Finite (a set) : there is a bijective correspondence of A with some section of the positive integers.

1.6.1.1 Cardinality 0 : A is empty

1.6.1.2 Cardinality n : there is a bijection f:A->{1,..,n} for some positive integer n

1.6.2 (Thm 6.1) Let A be a set. Suppose that there exists a bijection f:A-> {1,..,n} for some n \in \mathbb{Z}_{+}. Let B be a proper subset of A. then there exists no bijection g : B->{1,…,n}. But provided B \neq \empty, there does exist a bijection h:B->{1,…,m} for some m<n.

1.6.2.1 Let n be a positive integer. Let A be a set. Let a_{0} be an element of A. There exists a bijective correspondence f of the set A with the set {1,…,n+1} iff there exists a bijective correspondence g of the set A-{a_{0}} with the set {1,…,n}.

1.6.2.2 (Cor) If A is finite, there is no bijection of A with a proper subset of itself.

1.6.2.3 (Cor) Z_{+} is not finite.

1.6.2.4 (Cor) The cardinality of a finite set A is uniquely determined by A.

1.6.2.5 (Cor) If B is a subset of the finite set A, then B is finite. If B is a proper subset of A, then the cardinality of B is less than the cardinality of A.

1.6.2.6 (Cor) Let B be a nonempty set. Then the following are equivalent.

1.6.2.6.1 B is finite.

1.6.2.6.2 There is a surjective function from a section of the positive integers onto B.

1.6.2.6.3 There is an injective function from B into a section of the positive integers.

1.6.2.7 (Cor) Finite unions and finite cartesian products of finite sets are finite.

1.6.2.7.1 If A and B are finite, so is A \cup B.

1.7 Countable and Uncountable Sets

1.7.1 Infinite : not finite

1.7.2 Countably infinite : there is a bijective correspondence f : A-> \mathbb{Z}_{+}

1.7.3 Countable (a set) : it is finite or countably finite

1.7.4 Uncountable (a set) : not countable

1.7.5 (Thm 7.1) : Let B be a nonempty set. Then the following are equivalent.

1.7.5.1 B is countable.

1.7.5.2 There is a surjective function f : \mathbb{Z}_{+} -> B

1.7.5.3 There is an injective function g : \B -> \mathbb{Z}_{+}

1.7.5.4 (Lem) If C is an infinite subset of \mathbb{Z}_{+}, then C is countably infinite.

1.7.5.4.1 H(n) = smallest element of [C- H({1,…,n-1})], H(1) = smallest element of C

1.7.6 Principle of recursive definition : Let A be a set. A recursive formula determines a unique function h: \mathbb{Z}_{+} -> A.

1.7.6.1 Recursive formula : a formula that defines h(1) as a unique element of A, and for i>1 defines h(i) uniquely as an element of A in terms of the values of h for positive integers less than I.

1.7.7 (Cor) A subset of a countable set is countable.

1.7.8 (Cor) the set \mathbb{Z}{+} \times \mathbb{Z}{+} is countably infinite.

1.7.9 (Thm 7.5) A countable union of countable sets is countable.

1.7.10 (Thm 7.6) A finite product of countable sets is countable.

1.7.11 (Thm 7.7) Let X be the two element set {0,1}. Then the set X^{\omega} is uncountable.

1.7.12 (Thm 7.8) Let A be a set. There is no injective map f: \mathcal{P} (A) -> A, and there is no surjective map g: A->\mathcal{P}

1.8 The principle of Recursive Definition

1.8.1 (Thm 8.3) There exists a unique function h: \mathbb{Z}{+} -> C satisfying recursive formula for all I \in \mathbb{Z}{+}.

1.8.1.1 (Lem)Given n \in \mathbb{Z}_{+}, there exists a function f:{1,…,n} ->C that satisfies the recursive formula for all I in its domain.

1.8.1.2 (Lem)Suppose that f:{1,…,n} -> C and g : {1,…,m} ->C both satisfy recursive formula for all I in their respective domains. Then f(i) = g(i) for all I in both domains.

1.8.2 (Thm 8.4) (Principle of recursive definition) : let A be a set; let a_{0} be an element of A. Suppose \rho is a function that assigns, to each function f mapping a nonempty section of the positive integers into A, an element of A. Then there exists a unique function h: \mathbb{Z}_{+} -> A s.t. recursion formula for h satisfied.

1.8.2.1 Recursion formula for h :

1.8.2.1.1 H(1) = a_{0}

1.8.2.1.2 H(i) = \rho(h | {1,…,i-1}) for I >1

1.9 Infinite sets and the axiom of choice

1.9.1 (Thm 9.1) Let A be a set. The following statements about A are equivalent.

1.9.1.1 There exists an injective function f : \mathbb{Z}_{+} -> A

1.9.1.2 There exists a bijection of A with a proper subset of itself.

1.9.1.3 A is infinite.

1.9.1.4 Pf) Axiom of choice is needed., recursion formula, c: \mathcal{B} -> \bigcup_{B \in \mathcal{B}} B = A

1.9.2 (Axiom of choice) : Given a collection \mathcal{A} of disjoint nonempty sets, there exists a set C consisting of exactly one element from each element of \mathcal{A}

1.9.2.1 A set C s.t. C is contained in the union of the elements of \mathcal{A}, and for each A \in \mathcal{A}, the set C\cap A contains a single element.

1.9.3 (Existence of a choice function)(Lem)

1.9.3.1 Given a collection \mathcal{B} of nonempty sets not necessarily disjoint, there exists a function c : \mathcal{B} -> \bigcup_{B \in \mathcal{B}} B s.t. c(B) is an element of B, for each B \in \mathcal{B}.

1.9.3.1.1 A function c is called a choice function for the collection \mathcal{B} .

1.9.4 Finite axiom of choice : given a finite collection \mathcal{A} of disjoint nonempty sets, there exists a set \mathcal{C} consisting of exactly one element from each element of \mathcal{A}.

1.9.4.1 Weaker form of axiom of choice.

1.10 Well-Ordered sets

1.10.1 Well-ordered ( a set A with an order relation < ) : every nonempty subset of A has a smallest element.

1.10.1.1 Constructing well-ordered sets

1.10.1.1.1 If A is a well-ordered set, then any subset of A is well-ordered in the restricted order relation.

1.10.1.1.2 If A and B are well-ordered sets, then A \times B is well-ordered in the dictionary order.

1.10.2 (Thm 10.1) Every nonempty finite ordered set has the order type of a section {1,…,n} of \mathbb{Z}_{+}, so it is well-ordered.

1.10.3 (Well-ordering theorem) If A is a set, there exists an order relation on A that is well-ordering.

1.10.3.1 Pf) choice axiom

1.10.4 (Cor) There exists an uncountable well-ordered set.

1.10.5 Section S_{\alpha} of X by \alpha : Let X be a well-ordered set. Given \alpha \in X, S_{\alpha} = {x | x \in X and x < \alpha}

1.10.6 (Thm 10.3) If A is a countable subset of S_{\Omega}, then A has an upper bound in S_{\Omega}.

1.10.6.1 (Lem) There exists a well-ordered set A having a largest element \Omega, s.t. the section S_{\Omega} of A by \Omega is uncountable but every other section of A is countable.

1.11 The Maximum principle

1.11.1 Strict partial order on A (a relation < on A)

1.11.1.1 (Nonreflexivity) The relation a<a never holds

1.11.1.2 (Transitivity) If a<b and b<c, then a<c

1.11.2 (The maximum principle) Let A be a set; let < be a strict partial order on A. Then there exists a maximal simply ordered subset of B.

1.11.2.1 Pf) well-ordering theorem

1.11.3 Let A be a set and let < be a strict partial order on A.

1.11.3.1 Upper bound on B ( B a subset of A) : an element c of A s.t. for every b in B, either b = c or b < c.

1.11.3.2 Maximal element of A : an element m of A s.t. for no element a of A does the relation m < a hold.

1.11.4 (Zorn’s Lemma) : Let A be a set that is strictly partially ordered. If every simply ordered subset of A has an upper bound in A, then A has a maximal element.

1.11.5 Partial order on A : let < be a strict partial order on a set A. Then if we define a \le b either a < b or a = b, then the relation \le is a partial order.