📂Set Theory

Quantifiers over Propositional Functions

Definition ¹

Let’s assume the propositional function $P(x)$ of the universe $U$ is given.

1. Universal Quantifier: It is written as $\forall x$ to mean ‘for all $x \in U$’ and is called the universal sign.
2. Existential Quantifier: It is written as $\exists x$ to mean ’there exists at least one $x \in U$ such that’ and is called the existential sign.

Explanation

For instance, regarding the set of natural numbers $\mathbb{N}$, the logical expression $p(x)$ saying ‘$x$ is a multiple of $3$’ can be abbreviated using the symbols above and the congruence as follows:

• $\forall x \in \mathbb{N} ( x \equiv 0 \pmod{3} ) \iff$ ‘Every natural number $x$ is a multiple of $3$’
• $\exists x \in \mathbb{N} ( x \equiv 0 \pmod{3} ) \iff$ ‘There exists a natural number $x$ that is a multiple of $3$’

The former is false and the latter is true. As you can see, the convenience of symbols and their expression in our language are completely independent. Even when studying from the original text, it’s good to pay attention to how to naturally speak in Korean and practice.

Learning in English

Anyone who has majored in mathematics or a major requiring calculus would have been puzzled at least once by the complex definition of limits. $$ \lim_{n \to \infty} x_{n} = a \iff \forall \varepsilon > 0 , \exists N \in \mathbb{N} : n \ge N \implies | x_{n} - a | < \varepsilon $$ Here, $\displaystyle \lim_{n \to \infty} x_{n} = a$ is defined as

For any positive $\varepsilon$, there exists a natural number $N$ such that $n \ge N$ implies $| x_{n} - a | < \varepsilon$.

Nobody would want to explain it in that way. Although it is correct in order, both the speaker and the listener can get confused, and it’s difficult to convey, making it inadequate as a form of speech before right or wrong.

The same expression in English becomes

For any positive $\varepsilon$, there exists a natural number $N$ such that $n \ge N $ implies $|x_{n} - a| < \varepsilon$.

It reads exactly as its definition because such expressions were originally designed to fit English. The language of science is mathematics, but the language of mathematics books is English.

The point is to internalize the essential concepts rather than trying to match the English translation, so it becomes easy enough to read in our language too.

Negation Rules

$$ \lnot \forall x ( p(x) ) \iff \exists x (\lnot p(x) ) \\ \lnot \exists x ( p(x) ) \iff \forall x ( \lnot p(x) ) $$

Another headache-inducing theorem is the above negation rules. As usual in mathematics, the quicker you get accustomed to it, the better.

Uniqueness

The symbol $\exists !$ typically means that it exists uniquely.