Introduction to Sets

-

Defining sets

Set theory is the foundation of modern mathematics. Every mathematical notion is built on some set. What is a set? This is a very deep question beyond the scope of this lecture. Instead, we give the following very rough, informal definition.


Definition (very informal)

A set is a collection of distinct objects. Objects of a set are called elements of the set.
To denote a set, we can enumerate its elements, enclosed by curly brackets. For example, \[\{1, 2, 3\}\] denotes a set consisting of three elements that are 1, 2, and 3. We may give a set a name as in \[S = \{1, 2, 3\},\] and say, for example, "the set \(S\) contains the elements 1, 2, and 3. Suppose \(S\) is any set. To denote that an object \(x\) is an element of \(S\), we write \[x \in S\] and say "\(x\) is in \(S\)" and so on. To denote that \(x\) is not in \(S\), we write \[x \not\in S.\]
It is important that the elements of a set are distinct. For example,
\[\{a, a, b, c\}\]
is not a set because there are two \(a\)'s that are not distinguishable from each other. A collection with redundant elements such as this is sometimes called a multiset (they play a central role in database theory). If we force ourselves to interpret the above collection as a set, we interpret it as \[\{a, b, c\}\] by removing the redundant elements. 
In a set, we don't care about the order of elements. For example,
\[\{1, 2, 3\}\]
and
\[\{2, 3, 1\}\]
and
\[\{3, 1, 2\},\]
and so on, are all the same set.

Definition (Cardinality of a set)

If the number of elements of the set \(S\) is finite, say \(n\), then we say the set is of cardinality \(n\), and write \(|S| = n.\) If the set \(S\) does not have a finite number of elements, then we say it is a set of infinite cardinality.

Example. For the set \(S = \{a, b, c, d\}\), its cardinality is \(|S| = 4\). \(|\emptyset| = 0.\) □

Subsets and set equivalence

A set may be contained completely in another set. This is the notion of subsets. But what does it mean, exactly? Here's the definition.

Definition

Let \(A\) and \(B\) be sets. If \(x \in A\) implies \(x \in B\), then we say that \(A\) is a subset of \(B\), and write \[A \subset B.\] In this case, the set \(B\) is said to be a superset of \(A\).

Example:
\[\{1, 2\} \subset \{1, 2, 3\}, ~~ \{2\} \subset \{1, 2, 3\}.\]

"\(\subset\)" may be regarded as a relation between sets. 

Lemma 

The subset relation \(\subset\) is transitive. That is, if \(A\subset B\) and \(B\subset C\), then \(A \subset C\).
Proof
Since \(A \subset B\), \(x \in A\) implies \(x \in B\), which, in turn, implies \(x \in C\) because \(B \subset C\). Hence, \(x\in A\) implies \(x \in C\). ■

Here is what we mean by "two sets are equal":

Definition

If \(A \subset B\) and \(B \subset A\), then we say that the sets \(A\) and \(B\) are equal and write \(A = B\).

That is, two sets are equal if each set is a subset of the other set. You should try to validate that the two sets, say, \(\{1, 2, 3\}\) and \(\{2, 1, 3\}\) are indeed equal according to the above definition.

Remark: Note that \(A \subset B\) may mean the sets \(A\) and \(B\) are actually equal sets (that is, if \(B\subset A\) also holds). For this reason, some people prefer \(A \subseteq B\) to \(A \subset B\) to denote the subset relation. When we want to express that \(A\) is a subset of, but not equal to, \(B\), we specifically write 
\[ A \subsetneq B.\]

Definition

If \(A \subset B\) and \(A \neq B\), we say that \(A\) is a proper subset of \(B\) and write \(A \subsetneq B\).

This definition means that \(A\) is a proper subset of \(B\) if \(A \subset B\) and there exists an element \(x \in B\) such that \(x \not\in A\).

Definition

The set with no elements is called the empty set and is denoted \(\emptyset\). That is, \[\emptyset = \{\}.\] The empty set is a subset of any set.

Note that \(\emptyset\) and \(\{\emptyset\}\) are two different sets. The former is the empty set, and the latter is a non-empty set, the only element of which is the empty set.

An alternative way to specify a set

When a set contains a finite number of elements, we can specify it by enumerating all the elements enclosed in curly brackets. For example, \[S = \{1, 2, 3\}\] is a set of three integers, 1, 2, and 3. When a set contains infinitely many elements, how can we specify it? Let's consider the set \(E\) of even natural numbers. In this case, we can exploit the regularity so we may write \[E = \{2, 4, 6, 8, \cdots\}\] to indicate that the "\(\cdots\)" are the rest of the elements with the same regularity (i.e., even natural numbers). But, what if there are no simple regularities? In such cases, we can use the following notation: \[ S = \{ x \in U | P(x) \}\] where \(U\) is some set that is already defined and \(P(x)\) is a logical proposition that depends on the value of \(x\) (such propositions are called predicates). Sometimes, we may omit the superset \(U\). This expression reads:
\(S\) consists of elements \(x\) of \(U\) such that the predicate \(P(x)\) is true.

That is, we pick each element, say \(x\), of \(U\), and if \(P(x)\) is true, then it is included in \(S\); otherwise, it is not included in \(S\).

 For example, we may specify the set of even natural numbers is the following way: \[E = \{x \in \mathbb{N} | \exists k \in \mathbb{N}, ~ x = 2k \}\] where \(\mathbb{N}\) is the set of natural numbers. This definition says: 
\(E\) is a subset of \(\mathbb{N}\), for each element \(x\) of which, there exists a natural number \(k\) such that \(x = 2k\) holds. The predicate here could be written as \(P(x) = [\exists k \in \mathbb{N}, x = 2k]\) For example, \(P(1)\) is false because we cannot express \(1 = 2k\) for any natural number \(k\); thus, 1 is not an element of \(E\). \(P(56)\) is true because \(56 = 2\times 28\) and \(28 \in \mathbb{N}\); thus, \(56 \in E\). And so on...

See also: If you are interested in a more rigorous treatment of set theory, refer to, for example, Zermelo-Fraenkel set theory (Wikipedia).



Comments

Post a Comment

Popular posts from this blog

Open sets and closed sets in \(\mathbb{R}^n\)

-
Image
Open sets In \(\mathbb{R}\), we have the notion of an open interval such as \((a, b) = \{x \in \mathbb{R} | a < x < b\}\). We want to extend this idea to apply to \(\mathbb{R}^n\). We also introduce the notions of bounded sets and closed sets in \(\mathbb{R}^n\). Recall that the \(\varepsilon\)-neighbor of a point \(x\in\mathbb{R}^n\) is defined as \(N_{\varepsilon}(x) = \{y \in \mathbb{R}^n | d(x, y) < \varepsilon \}\) where \(d(x,y)\) is the distance between \(x\) and \(y\). Definition (Open set) A subset \(U\) of \(\mathbb{R}^n\) is said to be an  open set  if the following holds: \[\forall x \in U ~ \exists \delta > 0 ~ (N_{\delta}(x) \subset U).\tag{Eq:OpenSet}\] That is, for every point in an open set \(U\), we can always find an open ball centered at that point, that is included in \(U\). See the following figure. Perhaps, it is instructive to see what is  not  an open set. Negating (Eq:OpenSet), we have \[\exists x \in U ~ \forall \delta > 0 ~ (N_{\delta}(x) \not
Read more

Euclidean spaces

-
Image
We would like to study multivariate functions (i.e., functions of many variables), continuous multivariate functions in particular. To define continuity, we need a measure of "closeness" between points. One measure of closeness is the Euclidean distance. The set \(\mathbb{R}^n\) (with \(n \in \mathbb{N}\)) with the Euclidean distance function is called a Euclidean space. This is the space where our functions of interest live. The real line is a geometric representation of \(\mathbb{R}\), the set of all real numbers. That is, each \(a \in \mathbb{R}\) is represented as the point \(a\) on the real line. The coordinate plane , or the \(x\)-\(y\) plane , is a geometric representation of \(\mathbb{R}^2\), the set of all pairs of real numbers. Each pair of real numbers \((a, b)\) is visualized as the point \((a, b)\) in the plane. Remark . Recall that \(\mathbb{R}^2 = \mathbb{R}\times\mathbb{R} = \{(x, y) | x, y \in \mathbb{R}\}\) is the Cartesian product of \(\mathbb{R}\) with i
Read more

Newton's method

-
Image
Newton's method (the Newton-Raphson method) is a very powerful numerical method for solving nonlinear equations.  Suppose we'd like to solve a non-linear equation \(f(x) = 0\), where \(f(x)\) is a (twice) differentiable non-linear function. Newton's method generates a sequence of numbers \(c_1, c_2, c_3, \cdots\) that converges to a solution of the equation. That is, if \(\alpha\) is a solution (i.e., \(f(\alpha) = 0\)) then,  \[\lim_{n\to\infty}c_n = \alpha,\] and this sequence \(\{c_n\}\) is generated by a series of linear approximations of the function \(f(x)\). Theorem (Newton's method) Let \(f(x)\) be a function that is twice differentiable on an open interval \(I\) that contains the closed interval \([a, b]\) (i.e., \([a,b]\subset I\)) and satisfy the following conditions: \(f(a) < 0\) and \(f(b) > 0\); For all \(x\in [a, b]\), \(f'(x) > 0\) and \(f''(x) > 0\). Let us define the sequence \(\{c_n\}\) by \[ \begin{eqnarray} c_1 &
Read more