When defining set, we mentioned that repetition and order are irrelevant for a set in the sense that \{a,b,c\}=\{b,c,a,b,b,c\}. This somewhat tells us the existence of order for the elements of sets. In fact, for many sets we are interested in, one or more orders are assumed in the common sense so that we can compare those elements. For example, for the set \{1,2,3,4\}, there is apparently an order called ‘less than’ (小于) which means we can ‘compare’ two elements in the manner whether one number is less than the other number or not. Similarly ‘less or equal to’ (小于等于), ‘greater than’ (大于), ‘greater or equal to’ (大于等于), and ‘equal to’ (等于) are other four orders for this set.

There is a mathematical way to define an ‘order’ for a set. This founds an important cornerstone for mathematical logic, and it is the main task of this post.

1. Ordered pair (有序对)

An ordered pair is a collection of two elements where order does matter. In other words, one can distinguish the first element from the second one. For example, if the first element is a and the second element is b, then we denote this ordered pair as (a,b). In this case, (a,b) \neq (b,a), \text{if}\ a \neq b. We call the first element the first coordinate (第一坐标) and the second one the second coordinate (第二坐标).

We can easily generalize this concept for cases with dimensions more than two. An ordered n-tuple is a collection of n elements. For example, (a,b,c,d) is a 4-tuple. Again, order does matter here. (There is an more formal definition of n-tuple using ordered pair.)

It should not be hard for us to understand this as we are using the Cartesian Coordinate System (笛卡儿坐标系) all the time. For the x-y planes, (1,2) is an ordered pair (x-y coordinates) for a point, which is different from another point (2,1). The n-tuple corresponds to n axes plane. It is helpful to use it as an example in this section, especially for the Cartesian Product coming next.

2. Cartesian Product (笛卡尔积)

Given two sets A\ \text{and}\ B, we denote the (binary) Cartesian product of A\ \text{and}\ B by A \times B, which is defined as

A \times B=\{(a,b)|a \in A, b \in B\}.

Here (a,b) is an ordered pair. Therefore, it is easy to see that A \times B \neq B \times A\ \text{if}\ A \neq B. Several more properties are as follows.

Proposition 1: 

  • \emptyset \times A=\emptyset; A \times \emptyset=\emptyset.
  • (A \cap B) \times (C \cap D)=(A \times C) \cap (B \times D)=(A \times D) \cap (B \times C).
  • (A \cup B) \times (C \cup D) \neq (A \times C) \cup (B \times D).
  • A \times (B \cap C)=(A \times B) \cap (A \times C).
  • A \times (B \cup C)=(A \times B) \cup (A \times C).
Remark 1: The second and third rules are special. They show that Cartesian Product works well with intersection, but not with union.

Similarly, we can generalize it to high dimensional case. We define n-nary Cartesian Product (n维笛卡儿积) as

A_1 \times \cdots \times A_n=\{(a_1, \ldots, a_n)|a_i\in A_i\ \text{for}\ i=1, \cdots, n\}.

where (a_1, \ldots, a_n) is a n-tuple.

3. Binary Relation

We are going to define the relation using ordered pairs. It is natural to understand a relation as some comparison between two elements. For instance, ‘4 is greater than 3’ is a relation between 3 and 4, and ‘3 is less than 4’ is another relation between them. Notice that these two relations are viewed as absolutely the same in our natural language; but in math, especially in mathematical logic, to avoid further confusion, it is worth to distinguish them in some sense. This gives us the first motivation to develop the conception of relation.

Given two sets, for example A\ \text{and}\ B, a (binary) relation between A and B is a set of ordered pairs, of which the first coordinates are from the first set, and the second coordinates are from the second set. In other words, a relation between A and B is a subset of A \times B. Use the previous example, let A=B=\{3,4\}. Then the relation ‘being greater than’ between A and B is the set \{(4,3)\} \subset A \times B. Another relation ‘being greater or equal to’ is \{(3,3), (4,3), (4,4)\}. One can see the importance of the ordered pair from these two examples, otherwise (4,3)=(3,4), but 3 is not greater or equal to 4.

If we call a relation between two sets as R (from the definition, R is a set), and if (a,b) \in R, we can write it as aRb. Using the same example again, we use '>' to denote the relation ‘being greater than’, then 4>3 means (4,3) is a member of this relation, i.e., 4 is greater than 3.

The main reason for us to bring up relation is to introduce ‘function’. There are more discussions about relation, for example here. We skip them and jump to the next section.

4. Function (or map, mapping) (函数或映射)

We probably have begun to learn about functions from elementary school, and most people know the definition by natural languages. However, from the discussions above, it is simple to give a definition in term of relation.

Given two sets A\ \text{and}\ B, a function from A to B is a relation between A and B such that there are no two members of the relation having the same first coordinate. For example, A=\{1,2\}, B=\{3,4\}. f=\{(1,3), (2,3)\}, then f is a function. g=\{(1,3), (1,4)\}. g is not a function.

In the above definition, the function f is a set essentially (从本质上说). The sets A\ \text{and}\ B are called the domain (定义域) and the codomain (上域) of the function f, respectively. The set of all second coordinates of elements of f is called the image or range (值域) of f, which is a subset of the codomain of f. If (a,b) \in f, then we can write is as f(a)=b. Several notations and special cases are as follows:

  • Domain of f: D(f).
  • Range of f: R(f)=\{f(x)|x \in D(f)\}.
  • f is injective (one-to-one) (单射): f(x) \neq f(y)\ \text{if } x \neq y, x ,y \in D(f).
  • f is surjective (onto) (满射): R(f)=B, where B is the codomain.
  • f is bijective (一一映射或双射): f is both injective and surjective.

In the above examples, we defined functions point by point. However, most functions that we deal with are given in algebraic way. For example, in \mathbb{R}, f(x)=x^2+1, x \in \mathbb{R} is a function from \mathbb{R} to \mathbb{R}. This means (x,y) \in f if x, y \in \mathbb{R} and y=x^2+1.

Given a function f(x) from A to B, we can define the inverse function (反函数或逆函数) of f(x), denoted as f^{-1}(x), to be a new function from R(f) to D(f) such that f^{-1}(x)=y if f(y)=x.

Remark 2: Does any function have an inverse function? If yes, prove it; otherwise give the sufficient condition (充分条件) for a function having an inverse function.
Remark 3: If a function has an inverse function, is the inverse function unique? If yes, prove, it; otherwise give a counterexample.

Another similar but different conception is inverse image (原像或逆像). Given a function f(x) and a set of B \subset R(f), the inverse image of B: f^{-1}(B)=\{x \in D(f)|f(x) \in B\}. Specially, f^{-1}(b)=\{x \in D(f)|f(x)=b\}.

Remark 4: If the answer to remark 2 is no, does a function have to have an inverse function for the existence of the inverse image for some subset of its range?

Consequently, we reach the common notion for functions. One can now talk about some special functions using definitions from high school math, such as odd/even functions, piecewise functions, symmetric functions, periodic functions, and so on. Also, one can understand function operations like composition, sum, difference, product, quotient, etc.

Remark 5: There are more special functions like convex functions, continuous functions, differentiable functions, integrable functions, analytic functions, etc. We will give the definitions when we talk about them.

5. Order

Number is one of the first objects that math studies. Since we already brought up the conception of relation, it is natural to look at different relations between number sets. A simple relation between numbers is order (in the common sense). Everyone agrees that 1 is less than 2, and 5 is greater than -3, as how we define these numbers (check here). Indeed, the common number sets we study, such as \mathbb{N}, \mathbb{Z}, \mathbb{R}, are equipped with orders like <, \leq, >,\ \text{and}\ \geq  automatically. These orders have some properties than normal relations may not have. For example, 1<2, 2<3,\ \text{then}\ 1<3 (transitivity 传递性). On the other hand, consider the relation ‘son’ from a set {Tom, James, John} to itself. The relation has two elements: (Tom, James) and (James, John). In other words, Tom is the son of James who is the son of John. However, (Tom, John) is not a member of the relation. Therefore, the order ‘son’ does not have transitivity. This example, together with other problems, motivates us to look at the special orders between number sets and generalize them.

We call a relation from a set A to itself as an (binary) partial order [(二元)偏序] on A if this relation satisfies (we use R to denote this relation):

  1. Reflexivity (自反性): aRa, \forall\ a \in A.
  2. Antisymmetry (反对称性): If a, b \in A, aRb, and bRa, then a=b.
  3. Transitivity (传递性): If a, b, c \in A, aRb, bRc, then aRc.

We call a set ‘partially ordered set’ (偏序集) if the set is equipped with at least one partial order.

Remark 6: Based on the definition above, < is not a partial order as the reflexivity is not satisfied, but \leq is. We use \leq as the example most of the time to think and explain.

It is worth noticing the word ‘partial’ in the name. It comes from the fact that, in the definition, the existence of the order is not guaranteed between any two elements. For example, on \mathbb{R}, for any two elements, we can compare them by \leq. However, on \mathbb{C}, this is not true. (we cannot compare 1+2i and 2+i.)  A partial order R is called a total (linear) order (全序) if additionally

Totality (完全性): a, b \in A, aRb\ \text{and}\ bRa.

From the previous example, we can see it is important to indicate which set the partial order is on. Also, one shall always keep an eye on whether an order is partial or total.

6. Several special elements

Next we will talk about concepts for partially order sets. These concepts are all related but different from each other. Make sure to understand the relationship and differences. Notice that in most cases, we are talking about infinite sets (sets containing infinite elements. See more here). Two good examples to help you understand are as follows:

Example 1: Consider the set A=\mathbb{R}^2 which corresponds to x-y plane. An element of this set is denoted by an ordered pair (x,y). We define the order `\leq' as 

(x_1, y_1) \leq (x_2, y_2) \Longleftrightarrow x_1 \leq x_2\ \text{and}\ y_1 \leq y_2.

One can verify this is a partial order on A by checking those three conditions. Also, this is not a total order as the totality is not satisfied. ((1,2)\ \text{and}\ (2,1) cannot be compared.) For specific cases, one may consider some subsets of A.

Example 2: Consider the set B=\mathbb{Q}

Given a partial order \leq on X (here ‘\leq‘ denotes an arbitrary partial order, may not be ‘less or equal than’) and E \subset X, we call x \in X the maximal/minimal element (最大元／最小元) of E if

x \leq y\ (\text{respectively}\ y \leq x)\Longleftrightarrow y=x, \forall\ y \in E.

We call z the upper/lower bound (上界／下界) of E if

\forall\ x \in E, x \leq z\ (\text{respectively}\ z \leq x).

Furthermore, we call z the least upper bound (LUB)/greatest lower bound (GLB) (上确界／下确界) of E, if z is an upper/lower bound of E, and \forall\ z' an upper/lower bound of E, z \leq z'\ (\text{respectively}\ z' \leq z).

Remark 7: Does maximal/minimal element always exist? Does the upper/lower bound always exist? Does LUB/GLB always exist? If not, what is a sufficient condition for the existence? How about the uniqueness? Answer the questions by proving them or giving counterexamples.

The least upper bound property is an important property of \mathbb{R}, which is equivalent to other completeness axioms of \mathbb{R}. We will talk about this in some separated section.