Sets consist of elements. If $X$ is a set, we write $x \in X$ to mean that $x$ is an element of $X$ (or ” $x$ is in $X$ “). Similarly, $x \notin X$ means that $x$ is not an element of $X$ (which only really makes sense if both $x$ and the elements of $X$ are elements of some common larger set so they can be compared.)
b. The set consisting of elements called 1,2, and 3 is denoted ${1,2,3}$, and this notation extends to any finite collection of objects.
c. The set ${1,2,3, \ldots}$ of positive integers is again a set.
d. The real numbers $\mathbb{R}$ form a set.
Any collection of elements of a set $X$ is called a subset of $X$ and is a set itself. We write $Y \subseteq X$ to mean that $Y$ is a subset of $X .$ If $Y$ and $Z$ are different subsets of $X$, then we write $Y \neq Z$ and we say that $Y$ and $Z$ are distinct subsets.
A property $P$ that only some elements of $X$ satisfy allows us to specify a subset of $X$ consisting of elements of $X$ that satisfy $P$, which we denote in set-theoretic notation by
$$
\{x \in X \mid x \text { satisfies } P\},
$$
or just $\{x \mid x$ satisfies $P\}$ if $X$ is understood.
The subset $\{n \in \mathbb{Z} \mid 2$ divides $n\}$ of $\mathbb{Z}$ is the set of even integers.
Let $X$ be a set and $Y$ be a subset of $X$. Then $X-Y$ denotes the complement of $Y$ in $X$, which is defined as
$$
X-Y=\{x \in X \mid x \notin Y\} .
$$
If $Y$ is a subset of $X$ that is not $X$ itself, then it is called a proper subset, and we write $Y \subset X$ (or $Y \subsetneq X$ ). Given two subsets $Y$ and $Z$ of a larger set $X$, we can form their union $Y \cup Z$ and their intersection $Y \cap Z$, which are also subsets of $X$.
Given sets $X$ and $Y$, the direct product $X \times Y$ is the set of pairs $(x, y)$ with $x \in X$ and $y \in Y$.
In set-theoretic notation, we may write this as
$$
X \times Y=\{(x, y) \mid x \in X, y \in Y\} .
$$
We can, of course, compose functions, as in the following definition.
Let $X, Y$, and $Z$ be sets and $f: X \rightarrow Y$ and $g: Y \rightarrow Z$ functions. The composition (or composite function) $g \circ f: X \rightarrow Z$ of $g$ with $f$ is the function such that $(g \circ f)(x)=$ $g(f(x))$ for all $x \in X$.
Let $f: X \rightarrow Y$ be a function.
a. The function $f$ is one-to-one (or injective, or an injection) if for every $x, y \in X$ such that $f(x)=f(y)$, one has $x=y$.
b. The function $f$ is onto (or surjective, or a surjection) if for every $y \in Y$, there exists an $x \in X$ such that $f(x)=y$.
c. The function $f$ a one-to-one correspondence (or bijective, or a bijection) if it is both oneto-one and onto.
In other words, to say a function $f: X \rightarrow Y$ is one-to-one is to say that it sends at most one element of $X$ to any given element of $Y$. To say that it is onto is to say that it sends at least one element of $X$ to any given element of $Y$. So, of course, to say that it is a one-to-one correspondence is to say that it sends exactly one element of $X$ to each element of $Y$.
a. The map $f: \mathbb{Z} \rightarrow \mathbb{Z}$ defined by $f(x)=2 x$ for every $x \in \mathbb{Z}$ is one-to-one, but not onto.
b. The function $f: \mathbb{R} \rightarrow \mathbb{R}$ defined by $f(x)=x^{3}$ is a bijection.
c. The function $f: \mathbb{R} \rightarrow \mathbb{R}$ defined by $f(x)=x \sin (x)$ is onto, but not one-to-one.
a. A set $X$ is finite if $X$ has only a finite number of elements, and it is infinite otherwise.
b. If $X$ is a finite set, then the order $|X|$ of $X$ is the number of elements it has.
Let $n=|X|$, and denote the elements of $X$ by $x_{1}, \ldots, x_{n}$. If $f\left(x_{i}\right)=f\left(x_{j}\right)$ for some $i \neq j$, then the subset $\left{f\left(x_{1}\right), \ldots, f\left(x_{n}\right)\right}$ of $Y$ has fewer than $n$ elements, hence cannot equal $Y$. Conversely, if $\left{f\left(x_{1}\right), \ldots, f\left(x_{n}\right)\right}$ has fewer than $n$ elements, then $f\left(x_{i}\right)=f\left(x_{j}\right)$ for some $i \neq j$. Therefore $f$ is not one-to-one if and only if it is not onto, as desired.
Every bijection has an inverse
If $f: X \rightarrow Y$ is a bijection, then we define the inverse of $f$ to be the function $f^{-1}: Y \rightarrow X$ satsifying $f^{-1}(y)=x$ for the unique $x$ such that $f(x)=y$.
Given a bijection $f: X \rightarrow Y$, note that
$$
f^{-1}(f(x))=x \text { and } f\left(f^{-1}(y)\right)=y
$$
for all $x \in X$ and $y \in Y$. In other words, $f^{-1} \circ f$ (resp., $f \circ f^{-1}$ ) is the function that takes every element of $Y$ (resp., $X$ ) to itself.
The function $f: \mathbb{R} \rightarrow \mathbb{R}$ defined by $f(x)=x^{3}$ has inverse $f^{-1}(x)=x^{-1 / 3} .$
Often, it is useful to use what is called an indexing set $I$ to define a collection, which is just some given set, like the natural numbers. Given objects $x_{i}$ for each $i \in I$, we can use set-theoretic notation to define a set consisting of them
$$
\{x_{i} \mid i \in I\}
$$
that is in one-to-one correspondence with $I$ via the map that takes $i$ to $x_{i}$.
Let $X$ be a set and $\left{Y_{i} \mid i \in I\right}$ be a collection of subsets of $X$ indexed by a set $I$.
a. The intersection and union of the sets $Y_{i}$ are defined as
$$
\bigcap_{i \in I} Y_{i}=\left{x \in X \mid x \in Y_{i} \text { for all } i \in I\right} \text { and } \bigcup_{i \in I} Y_{i}=\left{x \in X \mid x \in Y_{i} \text { for some } i \in I\right},
$$
respectively.
b. If $Y_{i} \cap Y_{j}=\varnothing$ for every $i, j \in I$ with $i \neq j$, we say that the sets $Y_{i}$ are disjoint.
c. If the collection of $Y_{i}$ is disjoint, then their union is called a disjoint union and is often written as
$$
\coprod_{i \in I} Y_{i} .
$$
Let $\left{X_{i} \mid i \in I\right}$ be a collection of sets. The direct product $\prod_{i \in I} X_{i}$ of the $X_{i}$ is the set of tuples
$$
\begin{align}
\prod_{i \in I} X_{i}=\left{\left(x_{i}\right){i \in I} \mid x{i} \in X_{i}\right} .
\end{align}
In other words, an element of $\prod_{i \in I} X_{i}$ is a choice of one element of $X_{i}$ for each $i \in I$.