On this page explaining godel numbers (https://plato.stanford.edu/entries/goedel-incompleteness/sup1.html) it says "for simplicity, let us assume that ¬,→ and ∀ are the only primitive logical symbols, and that ∧,∨,↔ and ∃ are defined with the help of them". But I cant find how symbols like the existential quantifier can be defined from the symbols given?

# Can ∃ be defined using ∀

logic

#### Related Solutions

(2) If you're reading Gödel's original paper, he's certainly defining the primitive recursive functions as *semantic* objects at first -- it's only much later in the paper that he shows they can be expressed in a particular formal system.

(1) The point of defining primitive recursive functions is not to give you a new way of making functions. It is to *name a certain subset* of all the functions you already have, namely the functions that happen to be definable using the rules for p.r. functions and nothing else. These particular functions are going to have some nice properties ...

(3) ... in particular they are all representable in the formal system we're reasoning about, in the sense that for each p.r. function there's a fixed logical formula that you can plug numerals into, and the result will be a provable or disprovable according to whether the numerals you plug in represent a correct set of inputs and corresponding output to your p.r. function.

You're right in observing that it is not very exciting that the representable functions are closed under function composition -- that is not particular to PA, and can be proved for about any reasonable first-order theory. But it *is* interesting and nontrivial that the *primitive recursion rule* does not take us outside the space of Peano-Arithmetic representible functions. You cannot prove that for first-order theories in general -- for example it is not true for Presburger Arithmetic (which has addition but not multiplication as a primitive notion).

What this is used for is to connect "correct proof" at the metalevel with a property in the formal system. Gödel proves that "$x$ is (the Gödel number of) a valid proof of formula $y$" is a primitive recursive property, and *therefore* there is a formula in the system itself that is provable exactly when you plug in numerals for Gödel numbers of valid proofs. This is the core of the construction of an undecidable sentence.

An important convention that, unfortunately, often goes un-stated is that when an operation that ordinarily only applies to objects of a certain sort is applied to a *set* of objects of that sort, the result is the set obtained by applying that operation to the elements of that set. For example, multiplication by $2$ is an operation usually applied only to numbers. $\mathbb{Z}$ is the set of all integers, so in particular is not a number but a set of numbers. The expression $2\mathbb{Z}$, therefore, doesn't really make sense - we don't know what it means to multiply a set by a number. Instead, what we mean by "$2\mathbb{Z}$" is $\{2x \mid x \in \mathbb{Z}\}$ - in this case, the set of all even integers.

Likewise, you're right that the Godel-numbering operation typically applies only to sentences. $\Sigma$ is a set of sentences; therefore, $\ulcorner\Sigma\urcorner$ refers to the set $\{\ulcorner\varphi\urcorner\mid\varphi\in\Sigma\}$. In other words, $\ulcorner\Sigma\urcorner$ is the set of Godel numbers of sentences in $\Sigma$.

Now, you say you know what it means for a Godel number to be computable. If that's the case, either you're misunderstanding something or you're mis-stating something - a single Godel number is always computable, because it's just an integer. Any integer can be computed (by a program which just outputs that number). What you almost certainly mean is that you know what it means for a *set* of Godel numbers to be computable - that is, there is an algorithm which, given a Godel number, will determine whether or not that number is in the set. If I'm correct in thinking that, then this notion of "computable" is specifically for things like $\ulcorner\Sigma\urcorner$ (sets of Godel numbers).

## Best Answer

$\exists$ is equivalent to $\neg \forall \neg$ (there exists a true instance if it is not the case that the statement always fails).

Equivalently, one can define $\forall$ as $\neg \exists \neg$.

Also, $a \vee b$ is equivalent to $\neg a \to b$. And, $a \wedge b$ is equivalent to $\neg(a \to \neg b)$. Finally, $a \leftrightarrow b$ is equivalent to $(a \to b) \wedge (b \to a)$ which merely abbreviates $\neg((a \to b) \to \neg(b \to a))$.