# Appendix A.1 Sets and Functions ## Sets A set is a collection of objects called elements. If $a$ is an element of a set $A$, we write $$ a\in A. $$ If $a$ is not an element of $A$, we write $$ a\notin A. $$ Sets are fundamental throughout mathematics because nearly every mathematical structure can be described in terms of collections and relations between collections. Examples include: $$ \mathbb{N}=\{1,2,3,\ldots\}, $$ $$ \mathbb{Z}=\{\ldots,-2,-1,0,1,2,\ldots\}, $$ and finite sets such as $$ \{2,3,5,7\}. $$ ## Equality of Sets Two sets are equal if they contain exactly the same elements. Thus $$ A=B $$ means: $$ x\in A \iff x\in B $$ for every object $x$. Order does not matter in sets, and repeated elements are ignored. For example, $$ \{1,2,3\} = \{3,2,1\}. $$ Similarly, $$ \{1,1,2,2,3\} = \{1,2,3\}. $$ ## Subsets A set $A$ is a subset of $B$ if every element of $A$ belongs to $B$. We write $$ A\subseteq B. $$ Thus $$ A\subseteq B $$ means: $$ x\in A \implies x\in B. $$ For example, $$ \{2,3\}\subseteq\{1,2,3,4\}. $$ If $$ A\subseteq B \quad\text{and}\quad A\neq B, $$ then $A$ is called a proper subset of $B$. ## Empty Set The empty set is the set containing no elements. It is denoted by $$ \varnothing. $$ The empty set is a subset of every set. Indeed, the statement $$ x\in\varnothing \implies x\in A $$ is automatically true because there are no elements in $\varnothing$. ## Union and Intersection The union of two sets $A$ and $B$ is the set $$ A\cup B = \{x:x\in A \text{ or } x\in B\}. $$ The intersection is $$ A\cap B = \{x:x\in A \text{ and } x\in B\}. $$ For example, if $$ A=\{1,2,3\}, \qquad B=\{3,4,5\}, $$ then $$ A\cup B=\{1,2,3,4,5\}, $$ and $$ A\cap B=\{3\}. $$ ## Set Difference The difference of sets is $$ A\setminus B = \{x:x\in A \text{ and } x\notin B\}. $$ For example, $$ \{1,2,3,4\}\setminus\{2,4\} = \{1,3\}. $$ Set difference removes elements belonging to the second set. ## Cartesian Products Given sets $A$ and $B$, the Cartesian product is $$ A\times B = \{(a,b):a\in A,\ b\in B\}. $$ Its elements are ordered pairs. For example, $$ \{1,2\}\times\{x,y\} = \{ (1,x), (1,y), (2,x), (2,y) \}. $$ Cartesian products are fundamental for defining coordinate systems, relations, and functions of several variables. ## Functions A function from a set $A$ to a set $B$ assigns to every element of $A$ exactly one element of $B$. We write $$ f:A\to B. $$ If $a\in A$, then its image under $f$ is denoted $$ f(a). $$ The set $A$ is the domain of the function, and $B$ is the codomain. ## Image and Preimage The image of a subset $$ S\subseteq A $$ is $$ f(S) = \{f(x):x\in S\}. $$ If $$ T\subseteq B, $$ the preimage of $T$ is $$ f^{-1}(T) = \{x\in A:f(x)\in T\}. $$ Preimages are important because they behave well with unions and intersections. ## Injective Functions A function $f:A\to B$ is injective if distinct inputs produce distinct outputs. Formally, $$ f(a)=f(b) \implies a=b. $$ Equivalently, $$ a\neq b \implies f(a)\neq f(b). $$ An injective function never identifies different elements. For example, $$ f(n)=2n $$ from $\mathbb{Z}$ to $\mathbb{Z}$ is injective. ## Surjective Functions A function $f:A\to B$ is surjective if every element of $B$ occurs as an output. Thus for every $$ b\in B, $$ there exists $$ a\in A $$ such that $$ f(a)=b. $$ For example, $$ f(n)=n^3 $$ from $\mathbb{R}$ to $\mathbb{R}$ is surjective. ## Bijective Functions A function is bijective if it is both injective and surjective. A bijection establishes a perfect correspondence between two sets. If a bijection exists between $A$ and $B$, the sets have the same cardinality. For finite sets, this means they contain the same number of elements. ## Composition of Functions If $$ f:A\to B $$ and $$ g:B\to C, $$ their composition is the function $$ g\circ f:A\to C $$ defined by $$ (g\circ f)(x)=g(f(x)). $$ Function composition is associative: $$ h\circ(g\circ f) = (h\circ g)\circ f. $$ Composition is one of the central operations throughout mathematics. ## Identity Functions For a set $A$, the identity function is $$ \operatorname{id}_A:A\to A $$ defined by $$ \operatorname{id}_A(x)=x. $$ It leaves every element unchanged. Identity functions satisfy $$ f\circ\operatorname{id}_A=f, $$ and $$ \operatorname{id}_B\circ f=f. $$ ## Inverse Functions A function $$ f:A\to B $$ has an inverse if there exists a function $$ g:B\to A $$ such that $$ g(f(a))=a $$ for all $$ a\in A, $$ and $$ f(g(b))=b $$ for all $$ b\in B. $$ A function has an inverse precisely when it is bijective. ## Finite and Infinite Sets A set is finite if its elements can be counted using a natural number. Otherwise it is infinite. The set $$ \mathbb{N} $$ of natural numbers is infinite. Infinite sets exhibit surprising behavior. For example, there exists a bijection between $$ \mathbb{N} $$ and the even integers: $$ n\mapsto2n. $$ Thus an infinite set may have the same size as a proper subset of itself. ## Countable Sets A set is countable if it is finite or has a bijection with $\mathbb{N}$. Examples of countable sets include: - integers, - rational numbers, - algebraic numbers. The rational numbers are countable despite being dense in the real line. ## Uncountable Sets A set is uncountable if it is not countable. The real numbers form an uncountable set. Cantor’s diagonal argument proves that no enumeration of real numbers can include them all. Thus infinities come in different sizes. ## Relations A relation on a set $A$ is a subset of $$ A\times A. $$ Examples include: - equality, - divisibility, - congruence modulo $n$, - order relations. Relations are fundamental for defining algebraic and arithmetic structures. ## Equivalence Relations A relation $\sim$ on $A$ is an equivalence relation if it is: 1. reflexive, 2. symmetric, 3. transitive. Congruence modulo $n$ is a basic example: $$ a\equiv b\pmod n. $$ Equivalence relations partition sets into equivalence classes. These ideas appear constantly in algebra and number theory. ## Conceptual Importance Sets and functions form the language of modern mathematics. Functions describe transformations and structure-preserving maps. Sets organize mathematical objects into collections suitable for rigorous reasoning. Nearly every construction in number theory, algebra, geometry, and analysis depends ultimately on these foundational concepts.