4
$\begingroup$

The Wikipedia page on the propositional calculus says that another name for it is "zeroth-order logic." This sort of makes sense to me, but appears to break down in some pretty crucial ways with logical connectives.

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.

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 objects are basically just numbers. But if these are supposed to be "zeroth-order predicates," what meaning does $(12 \lor 13) \land (14 \lor \lnot 15)$ have?

It is kind of strange to think of logical connectives as applying to all predicates of order > 0, unless you're working in "zeroth-order logic," at which point they apply there as well. Is there some neat way to make sense of precisely how things are related here?

$\endgroup$
7
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Clarified the wording there. These are all good points, but I'm still trying to understand - since this is all true, how are we supposed to view propositions as zero-order predicates? First-order predicates do not appear to be quantifying over them! $\endgroup$ – Mike Battaglia Oct 14 '17 at 19:24
  • $\begingroup$ @MikeBattaglia - Indeed, predicates are not quantifiers, so they should not quantify over anything. As for the first-order quantifiers, they quantify over individuals, not over truth-values, so all is in order. $\endgroup$ – Nagase Oct 14 '17 at 19:50
  • $\begingroup$ That was a typo - meant they don't take them as arguments. Quantifiers are a separate thing I didn't mean to bring up here. But with regard to your edit, my understanding is that increasing the "order" of a logic doesn't just refer to adding new quantifiers, but also adding new predicates. If first-order logic only added quantifiers to propositional logic, it would be decidable! This confusion over predicate "orders" is exactly where I am hung up. $\endgroup$ – Mike Battaglia Oct 14 '17 at 21:28
  • $\begingroup$ @MikeBattaglia - I don't understand your confusion. Yes, we add new predicates and new variables. So, in the case of first-order logic, now we also have variables for individuals and new predicate letters, instead of just "zeroth-order" predicates. And we can form sentences such as $S(0) = 0 \vee Q$, where $Q$ is a "zeroth-order" predicate (or just a propositional variable). Notice that the predicates will take as arguments only individual variables, not propositional variables! $\endgroup$ – Nagase Oct 14 '17 at 21:33
  • $\begingroup$ @MikeBattaglia - You seem to be under the misimpression that if a predicate is of order $n$, then it takes as arguments every variable of order $m$ for $m < n$. But that is not the case: what determines the arguments of the predicate is its type, not its order. $\endgroup$ – Nagase Oct 14 '17 at 21:43
3
$\begingroup$

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.
$\endgroup$
  • $\begingroup$ Thanks, good response -- a few points of confusion here. The main one is, I didn't think that first-order logic distinguished between types of objects such as natural numbers, sets, etc. I thought there were just objects in the domain of discourse, that their behavior stems from the sentences that we treat as axioms in whatever theory we want, and that our intuitive interpretation of them as numbers, sets, etc comes from their behavior under those axioms. $\endgroup$ – Mike Battaglia Oct 14 '17 at 19:01
  • $\begingroup$ @MikeBattaglia: Syntactically it doesn't. I think my bullet points may be muddying this a bit and I'm still trying to figure out how to properly phrase them. $\endgroup$ – Kevin Oct 14 '17 at 19:04
  • $\begingroup$ The other thing is, given this interpretation, in what sense is propositional logic zero-order logic? It doesn't really make sense to me. $\endgroup$ – Mike Battaglia Oct 14 '17 at 19:09
  • $\begingroup$ Put another way: how are we supposed to view propositions as zero-order predicates? First-order predicates do not appear to be quantifying over them, as you mention! $\endgroup$ – Mike Battaglia Oct 14 '17 at 19:24
  • $\begingroup$ @MikeBattaglia: First-order predicates spit out propositions. Second-order predicates spit out first-order predicates. And so on... $\endgroup$ – Kevin Oct 14 '17 at 19:27
0
$\begingroup$

A proposition is that a unique thing is either 'True' or 'False'. Since this thing cannot be 'half-true', we can only quantify it as absolutely True, or all-the-way false. Which means that it belongs in the set of either True or False - {0} or {1}.

Set theory tells us that a set element is unique so, again, it cannot have a quantity, above 1, or below 0.

Also, when you ask 'what meaning does (12∨13)∧(14∨¬15) have?', I'm not sure that it has much of any! For one thing, these clauses appear to compare real numbers, which would make them higher-order (third?).

I'm sure that I'll regret writing here but, I don't even think that your last paragraph, regarding logical connectives, is even true. As in, you make a false proposition {0}!

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.