Considering the following:
Constants: $0, 1$
Functional Symbols: $+, .$
Relational Symbols: $<, |$ (| denotes divisibility)
Is it possible to write the following sequences using First Order Logic?
- There are infinite prime numbers (how to represent infinite?)
- Every subset of Natural Numbers has a minimum element (how to represent the subset?)
If it is not possible, what is missing? Could we extend the language in order to represent that?
Yes, it is. $$ \forall x \exists p \forall d \colon x < p \wedge 1 < p \wedge (1 < d \wedge d < p \rightarrow \neg d | p). $$ This sentence states that for all $x$ there is some $p$ that is not divisible by any $d$ such that $1 < d < p$ or even simpler: There are unboundedly (and hence infinitely) many primes.
We can't can't quantify over subsets in first order logic. However, we can do so in second order logic. In the following I reserve capital letters for subsets of our model, while lowercase letters denote elements thereof. Now consider the following sentence in second order logic over the language $\{0,1,+,\cdot, | \}$: $$ \forall X \exists m \forall n \colon \neg X(n) \vee [X(m) \wedge (n < m \rightarrow \neg X(n))]. $$ It states that for every subset $X$, $X$ is empty or there is some $m \in X$ such that there is no $n < m$ that is an element of $X$, i.e. $X$ is empty or there is some minimal $m \in X$.