 David Hilbert (/ˈhɪlbərt/;German: [ˈdaːvɪt ˈhɪlbɐt]; 23 January 1862 – 14 February 1943) was a German mathematician and one of the most influential mathematicians of the 19th and early 20th centuries. Hilbert discovered and developed a broad range of fundamental ideas in many areas, including invariant theory, the calculus of variations, commutative algebra, algebraic number theory, the foundations of geometry, spectral theory of operators and its application to integral equations, mathematical physics, and the foundations of mathematics (particularly proof theory).

# Understanding these basic definition and statement~

• If $x$ belongs to a class $A$, we write $x \in A$ and read as ” $x$ is an element of $A . “$ Otherwise, we write $x \notin A$.
• If $A$ and $B$ are sets, then $A \subseteq B(” A$ is a subset of $B$ ” or “A is contained in $B “$ ) means that each element of $A$ is also an element of $B$. Sometimes we write $B \supseteq A$ (“B contains A”) instead of $A \subseteq B$.
• We say two sets $A$ and $B$ are equal, written $A=B$, if $A \subseteq B$ and $B \subseteq A$.
• Any statement $S$ has a negation $\sim S($ “not $S$ “) defined by
$\sim S$ is true if $S$ is false and $\sim S$ is false if $S$ is true.
• Let $P(x)$ denote a property $P$ of the object $x$. We write $\exists$ for the quantifier “there exists.” The expression
$$\exists x \in X: P(x)$$
means that “there exists (at least) one object $x$ in the class $X$ which has the property $P . “$ The symbol $\exists$ is called the existential quantifier.
• We use the symbol $\forall$ for the quantifier “for all.” The expression
$$\forall x \in X: P(x)$$
has the meaning “for each object $x$ in the class $X, x$ has property $P . “$ The symbol $\forall$ is called the universal quantifier (or sometimes the general quantifier).
• We use the symbol := to mean “is defined by.” We take $x:=y$ to mean that the object or symbol $x$ is defined by the expression $y$.
• Note that for negation of a statement we have:
(i) $\sim \sim A:=\sim(\sim A)=A$
(ii) $\sim(A$ and $B)=(\sim A)$ or $(\sim B)$
(iii) $\sim(A$ or $B)=(\sim A)$ and $(\sim B)$
(iv) $\sim(\forall x \in X: P(x))=(\exists x \in X: \sim P(x))$
(v) $\sim(\exists x \in X: P(x))=(\forall x \in X: \sim P(x))$.
• Let $A$ and $B$ be statements. $A$ implies $B$ will be denoted by $A \Rightarrow B$. If $A$ implies $B$, we take this to mean that if we wish to prove $B$, it suffices to prove $A(A$ is a sufficient condition for
B).
• The equivalence $A \Leftrightarrow B$ (“A and $B$ are equivalent” or ” $A$ if and only if $B$,” often written $A$ iff $B$ ) of the statements $A$ and $B$ is defined by
$$(A \Leftrightarrow B):=(A \Rightarrow B) \text { and }(B \Rightarrow A)$$
$A$ is a necessary and sufficient condition for $B$, or vice versa.
• The statement $\sim B \Rightarrow \sim A$ is called the contrapositive of the statement $A \Rightarrow B$. In standard logic practices, any statement is considered equivalent to its contrapositive. It is often easier to prove a statement’s contrapositive instead of directly proving the statement itself.
• To prove $A \Rightarrow B$ by contradiction, one supposes $B$ is false (that $\sim B$ is true). Then, also assuming that $A$ is true, one reaches a conclusion $C$ which is already known to be false. This contradiction shows that if $A$ is true $\sim B$ cannot be true, and hence $B$ is true if $A$ is true.
• Given two sets $A$ and $B$, we define $A \cup B$ (“the union of $A$ with $B$ “) as the set
$$A \cup B:={x: x \in A \text { or } x \in B \text { or both }}$$
When speaking about unions, if we say $x \in A$ or $x \in B$ it also includes the possibility that $x$ is in both $A$ and $B$.
• We define $A \cap B$ (“the intersection of $A$ with $B$ “) as the set
$$A \cap B:={x: x \in A \text { and } x \in B} \text {. }$$
• Let $A$ and $B$ be subsets of $X .$ Then
$$A \backslash B:={x \in X: x \in A \text { and } x \notin B}$$
is the relative complement of $B$ in $A$. When the set $X$ is clear from the context we write also
$$A^{c}:=X \backslash A$$
and call $A^{c}$ the complement of $A$.
• If $X$ is a set, then so is its power set $\mathcal{P}(X)$. The elements of $\mathcal{P}(X)$ are the subsets of $X$. Sometimes the power set is written $2^{X}$ for a reason which is made clear in Problem $2.8$.
• Let $f: X \rightarrow Y$ be a function, then
$$i m(f):={y \in Y ; \exists x \in X: y=f(x)}$$
is called the image of $f$. We say $f$ is surjective (or onto) if $i m(f)=Y$, injective (or one-to-one) if $f(x)=f(y)$ implies $x=y$ for all $x, y \in X$, and $f$ is bijective if $f$ is both injective and surjective.
• If $X$ and $Y$ are sets, the Cartesian product $X \times Y$ of $X$ and $Y$ is the set of all ordered pairs $(x, y)$ with $x \in X$ and $y \in Y$.
• Let $X$ be a set and $\mathcal{A}=\left{A_{i}: i \in I\right}$ be a family of sets and $I$ is an index set. Intersection and union of this family are given by
$$\bigcap_{i \in I} A_{i}=\left{x \in X ; \forall i \in I: x \in A_{i}\right}$$
and
$$\bigcup_{i \in I} A_{i}=\left{x \in X ; \exists i \in I: x \in A_{i}\right}$$
• Inverse image of $B$ under $f$ (or pre-image of $B$ ), $f^{-1}(B)$ defined as
$$f^{-1}(B)={x \in X: f(x) \in B} .$$
Note that we can form $f^{-1}(B)$ for a set $B \subset Y$ even though $f$ might not be one-to-one or onto.
• We will use standard notation, $\mathbb{N}$ for the set natural numbers, $\mathbb{Z}$ for the set of integers, $\mathbb{Q}$ for the set rational numbers, and $\mathbb{R}$ for the set real numbers. We have the natural containments:
$$\mathbb{N} \subset \mathbb{Z} \subset \mathbb{Q} \subset \mathbb{R}$$
• Two sets $A$ and $B$ have the same cardinality if there is a bijection from $A$ to $B$. In this case we write $A \sim B$. We say $A$ is countable if $\mathbb{N} \sim A$. An infinite set that is not countable is called an uncountable set.

# Try the following problem to test yourself！

Problem 1.

Problem 1.1 Consider the four statements
$$\begin{array}{ll} \text { (a) } & \exists x \in \mathbb{R} \forall y \in \mathbb{R} & x+y>0 ; \ \text { (b) } & \forall x \in \mathbb{R} \exists y \in \mathbb{R} & x+y>0 ; \end{array}$$
(c) $\forall x \in \mathbb{R} \forall y \in \mathbb{R} \quad x+y>0$
(d) $\quad \exists x \in \mathbb{R} \forall y \in \mathbb{R} \quad y^{2}>x$.

1. Are the statements $a, b, c, d$ true or false?
2. Find their negations.

Proof .

faf

1. (a) is false. Since its negation $\forall x \in \mathbb{R} \exists y \in \mathbb{R} \quad x+y \leq 0$ is true. Because if $x \in \mathbb{R}$, there exists $y \in \mathbb{R}$ such that $x+y \leq 0$. For example, we may take $y=-(x+1)$ which gives $x+y=x-x-1=-1 \leq 0 .$
2. (b) is true. Indeed for $x \in \mathbb{R}$, one can take $y=-x+1$ which gives $x+y=1>0$. The negation of $(\mathrm{b})$ is $\exists x \in \mathbb{R} \forall y \in \mathbb{R} \quad x+y \leq 0$.
3. $(\mathrm{c}): \forall x \in \mathbb{R} \forall y \in \mathbb{R} \quad x+y>0$ is false. Indeed one may take $x=-1, y=0$. The negation of (c) is $\exists x \in \mathbb{R} \exists y \in \mathbb{R} x+y \leq 0$.
4. (d) is true. Indeed one may take $x=-1$. The negation is: $\forall x \in \mathbb{R} \exists y \in \mathbb{R} \quad y^{2} \leq x$.

Problem 2.

Problem $1.2$ Let $f: \mathbb{R} \rightarrow \mathbb{R}$. Find the negations of the following statements:

1. For any $x \in \mathbb{R} f(x) \leq 1$.
2. The function $f$ is increasing.
3. The function $f$ is increasing and positive.
4. There exists $x \in \mathbb{R}^{+}$such that $f(x) \leq 0$.
5. There exists $x \in \mathbb{R}$ such that for any $y \in \mathbb{R}$, if $xf(y)$.

Proof .

faf

1. This statement may be rewritten as: (For every $x \in \mathbb{R})(f(x) \leq 1)$. The negation of “( For every $x \in \mathbb{R})$ ” is “There exists $x \in \mathbb{R}$ ” and the negation of ” $(f(x) \leq 1)$ ” is ” $f(x)>1 . “$ Hence the negation of the statement is: “There exists $x \in \mathbb{R}, f(x)>1 . “$
2. First let us rewrite the statement “The function $f$ is increasing”: “for any real numbers $\left(x_{1}, x_{2}\right)$, if $x_{1} \leq x_{2}$ then $f\left(x_{1}\right) \leq f\left(x_{2}\right) . “$ This may be rewritten as: “(for any real numbers $x_{1}$ and $\left.x_{2}\right) \quad\left(x_{1} \leq x_{2}\right.$ implies $\left.f\left(x_{1}\right) \leq f\left(x_{2}\right)\right) . ” \quad$ The negation of the first part is: “(there exists a pair of real numbers $\left.\left(x_{1}, x_{2}\right)\right)$ ” and the negation of the second part is: “( $x_{1} \leq x_{2}$ and $\left.f\left(x_{1}\right)>f\left(x_{2}\right)\right)$ “. Hence the negation of the complete statement is: “There exist $x_{1} \in \mathbb{R}$ and $x_{2} \in \mathbb{R}$ such that $x_{1} \leq x_{2}$ and $f\left(x_{1}\right)>f\left(x_{2}\right) .$ ‘
3. The negation is: the function $f$ is not increasing or is not positive. We already did describe the statement “the function $f$ is not increasing.” Let us focus on “the function $f$ is not positive.” We get: “there exists $x \in \mathbb{R}, f(x)<0 . “$ Therefore the negation of the complete statement is: “there exist $x_{1} \in \mathbb{R}$ and $x_{2} \in \mathbb{R}$ such that $x_{1}<x_{2}$ and $f\left(x_{1}\right) \geq f\left(x_{2}\right)$, or there exists $x \in \mathbb{R}, f(x)<0 . “$
4. This statement may be rewritten as follows: “(there exists $\left.x \in \mathbb{R}^{+}\right)(f(x) \leq 0) . “$ The negation of the first part is: “(for any $\left.x \in \mathbb{R}^{+}\right), “$ and for the second part:” $(f(x)>0) . “$ Hence the negation of the complete statement is: “for any $x \in \mathbb{R}^{+}, f(x)>0 . “$
5. This statement may be rewritten as follows: ” $(\exists x \in \mathbb{R})(\forall y \in \mathbb{R})(xf(y)) . “$
The negation of the first part is: ” $(\forall x \in \mathbb{R}), “$ for the second part: ” $(\exists y \in \mathbb{R}), “$ and for the third part: ” $(x<y$ and $f(x) \leq f(y)) . “$ Hence the negation of the complete statement is:
” $\forall x \in \mathbb{R}, \exists y \in \mathbb{R}, x<y$ and $f(x) \leq f(y) . “$