In what sense is propositional logic "zeroth-order logic?"

This gets weird as it pertains to logical connectives, though. In propositional logic, the objects really are thought to be "constant functions" in that they are considered to have a true or false value, and we can apply logical connectives to them. But if we are considering these to be the things that first-order predicates take as arguments, how does this sense? In first-order $PA$, for instance, the zeroth-order predicates are basically just numbers. What meaning does $(12 \vee 13)\wedge(14\vee \neg 15)$ have?

The emphasized part is very misleading. We don't generally take our constants to be "zeroth-order" predicates, but rather $0$-ary functions (and even that is not forced). An $n$-ary predicate takes an $n$-tuple and returns a truth-value, whereas an $n$-ary function takes $n$-tuples and returns an object of the domain, so it's natural to identify $0$-ary functions with constants. But then the constants will not be "zeroth-order" predicates!

EDIT: You also seem confused by the definition of "zeroth-order" logic, first-order logic, etc. Basically, a logic is of the $n$th-order if no variable of order $n+1$ is quantified, where the order of the variables can be defined recursively by setting a (relational) type hierarchy as follows:

  • $o, i$ are types of order $0$ and $1$, respectively (they are, respectively, the types of the truth-values and of the individuals);
  • if $\tau_1, \dots, \tau_n (n \geq 1)$ are of any type except $o$, then $\langle \tau_1, \dots, \tau_n\rangle$ is a type of order $1 + max\{ord(\tau_1), \dots, ord(\tau_n)\}$. Intuitively, $\langle \tau_1, \dots, \tau_n\rangle$ is the type of $n$-ary relations with arguments from $\tau_1, \dots, \tau_n$. So, for instance, first-order $n$-ary relations are variables of type $\langle i, \dots, i\rangle$ (that's $n$ $i$'s) and order $2$.

So first-order logic is so-called because no variable of the second order is quantified. Similarly, a zeroth-order logic is so-called because no variable of order $1$ is quantified (i.e. we don't quantify over indviduals). Note further that relation variables take individuals, not truth-values, as inputs.


The idea is that the propositions of propositional logic can be thought of as predicates of "zeroth order." They take in no input and can be thought of basically as "constant $\{0,1\}$-valued functions." First-order predicates take these as input. Second-order predicates take in either first-order predicates or zero-order predicates as input. And so on.

No.

A "constant $\{0,1\}$-valued function" is (equivalent to) one of the numbers $\{0, 1\}$. So if this were true, first order logic would be quantifying over the set $\{0, 1\}$. That is, a statement like $\forall x P(x)$ would immediately reduce to $P(0)\wedge P(1)$, which is not generally valid (though it would be valid if your domain of discourse happens to be $\{0, 1\}$, for example in boolean algebra).

The propositions of propositional logic quantify over nothing at all; they are nullary boolean variables, as you have described. First-order predicates quantify over some objects, but not necessarily booleans. For example, under PA, they quantify over natural numbers, whereas under ZFC they quantify over sets (but this is just a semantic convention; syntactically this domain is left unspecified). Second-order predicates do quantify over these first-order predicates, in a sense, but the domain of these predicates is again specific to the problem space. For example, a second-order restatement of the axiom schema of separation would allow replacing the bound predicate $\phi(x)$ with something like $x \in S$, for some previously described free variable $S$. The symbol $\in$ belongs not to first-order logic but to set theory. Syntactically this is valid because the symbol acts like a "funny looking" first-order predicate. In other words, we could just as easily write $\mathrm{In}(x, S)$, but that would be unconventional. Nevertheless, $\in$ or $\mathrm{In}$ has a semantic, set-theoretic meaning which is specific to ZFC; this is not just some arbitrary symbol which we plucked out of nowhere (in much the same way as the 2 is not a meaningless symbol under PA).

So to tie it all together:

  • Propositions are syntactically boolean variables and semantically represent specific true or false statements about our semantic domain
  • First-order predicates are syntactically functions of unspecified domain and a boolean codomain (that is, they produce rather than consume booleans), and semantically they are statements with "a bit missing," specifically some bound variable which may be filled in from our domain.
  • Second-order predicates are syntactically higher-order functions of unspecified domain with a "first-order predicates" codomain, and semantically they are statements with "a whole formula missing," which may again be filled in from our domain.
  • This process may be carried on for as many layers as you like. Each layer allows for quantifying over the previous layer, which is syntactically like a function that produces the previous layer's predicates, and semantically like introducing another layer of indirection.

Tags:

Logic

Predicate Logic

First Order Logic

Propositional Calculus

Related

Find the height of a bar, given the lengths of shadows cast by it and another bar Find all $f : \mathbb{N} \to \mathbb{N}$ such that $f(a) + f(b) \mid a+b, \ \forall \ a, b \in \mathbb{N}$ I think I have discovered a proof for the irrationality of $\sqrt{2}$, but I'm not sure Prove that if fifteen bishops were placed on a chessboard, then at least two of them attack each other. Showing that $\lvert H K\rvert = \frac{| H\| K|}{ |H\cap K|}$ $a_n$ is the smallest positive integer number such that $\sqrt{a_n+\sqrt{a_{n-1}+...+\sqrt{a_1}}}$ is positive integer Prove that $\lim\limits_{x\to 0^+}\sum\limits_{n=1}^\infty\frac{(-1)^n}{n^x}=-\frac12$ Is the set of rational number discrete or continuous? How does calculus without Euler's number (e) look? Prove the existence of an analytic function Is the algebraic number theory in Ireland and Rosen enough to study Washington's Cyclotomic Fields? Why do I get a converging result when pressing cosine multiple times on a calculator?

Recent Posts