1
$\begingroup$

Definitions for the syntax of formal languages frequently make use of clauses such as

If $t_1, ..., t_n$ are terms in $\mathcal{L}$ and $P$ is an $n$-ary predicate in the vocabulary of $\mathcal{L}$, then $P(t_1, ..., t_n)$ is a formula in $\mathcal{L}$.

Isn't this actually imprecise in that it makes use of a unidirectional implication instead of a bidirectional one?
Logically seen, the above formulation would allow for a complex expression to be a valid formula of the language even if $t_1, ..., t_n$ weren't terms or $P$ wasn't a predicate, since the mathemaical "if" stays true if the antecedent ("$t_1, ..., t_n$ are terms and $P$ is an $n$-ary predicate") is false and the consequent ("$P(t_1, ..., t_n)$ is a formula") is true.
When interpreting the implication in this way, this would mean that something like $\exists (P, R \forall)$ can be a formula, which is clearly not what is intended.

Shouldn't it rather be

If and only if $t_1, ..., t_n$ are terms in $\mathcal{L}$ and $P$ is an $n$-ary predicate in the vocabulary of $\mathcal{L}$, then $P(t_1, ..., t_n)$ is a formula in $\mathcal{L}$.

thereby ensuring that the constituents must actually be syntactically correct in order for the more complex statement to be too?

I would also think that appending a final "Nothing else is a formula in $\mathcal{L}$" doesn't save the problem: This only ensures that nothing apart from what is defined by these clauses is a formula, but given the wording of the clauses, the implicational clauses themselves would already permit $\exists (P, R \forall)$ as a formula.

However, I've almost never seen a biimplicational "iff" in such definitory statements and am now confused as to whether my reasoning is correct.

$\endgroup$
1
  • $\begingroup$ Comments are not for extended discussion; this conversation has been moved to chat. $\endgroup$ Mar 31 '17 at 21:02
3
$\begingroup$

We of course have to define what a formula is.

For a propositional language $P$ with atoms $p_i$ and connectives: $\lnot, \to$, we may define the set of propositional formulas $\text {Sent}$ as follows:

An expression $\varphi \in \text {Sent}$ iff there is a finite sequence $\langle \psi_0, \ldots, \psi_n \rangle$ of expressions (i.e. finite strings of symbols) of $P$ such that $\varphi = \psi_n$ and for each $i \le n$ one of the following holds:

(i) $\psi_i=p_k$, for some $p_k \in P$;

(ii) $\psi_i=\lnot \psi_j$, for some $j < i$;

(iii) $\psi_i = \psi_j \to \psi_k$, for some $j,k < i$.

Or we can simply mimicks the costruction licensed by the Axiom of Induction [see Ax.5, page 2]:

Let $S$ a set of expressions of the language $\mathcal L$ such that:

1) every sentential letter $p_i$ belongs to $S$,

2) if $\varphi$ belongs to $S$, then $\lnot \varphi, \varphi \lor \psi, \ldots$ belong to $S$.

Then $S$ contains all the formulas.


But this as little to do with your comment:

"the above formulation would allow for a complex expression to be a valid formula of the language even if $\phi$ wasn't, since the mathemaical "if" stays true if the antecedent ("$\phi$ is a formula") is false and the consequent ("$¬ϕ$ is a formula") is true."

The fact that the conditional expressing the definition can be vacuously true does not license you to conclude with wrong results.

In order to use modus ponens to "detach" the consequent of the true conditional:

if $x∃P$ is a formula, then $¬x∃P$ is a formula,

you have to assert the antecedent, i.e. you have to assert that $x∃P$ is a formula, which is not.


On definition in general, you can compare two different "authoritative" points of view: Definitions, arguing that:

the similarity in the logical behavior of [definitions in terms of $=_{df}$] and [definitions in terms of $\leftrightarrow$] should not obscure the great differences between the biconditional (‘$\leftrightarrow$’) and definitional equivalence (‘$=_{df}$’),

and Tarski's introduction on the use of iff in definitions.

$\endgroup$
1
  • $\begingroup$ +1: in the interests of fairness as there is no right answer! $\endgroup$
    – Rob Arthan
    Mar 30 '17 at 14:54
2
$\begingroup$

No, because the second 'f' in iff assumes the thing you want to define. So strictly speaking, a definition with 'iff' is circular, hence undefined.

$\endgroup$
3
  • 1
    $\begingroup$ I don't get it. Could you expand on your answer? $\endgroup$ Mar 30 '17 at 14:17
  • 1
    $\begingroup$ We can use it both ways: to replace the long expression with the shorter abbreviaition, but also in a proof to replace the condition $A \subseteq B$ with its definition. $\endgroup$ Mar 30 '17 at 14:23
  • $\begingroup$ I wrote about this at math.stackexchange.com/questions/566565/… $\endgroup$ Mar 31 '17 at 11:28
1
$\begingroup$

Let's consider a somewhat less confusing context for the question. Let's inductively define the set $\mathbb S$ of all natural numbers that are multiples of 3.

So we might start out (borrowing the concept of 0 and 3 from natural numbers):

  • $0 \in \mathbb S$
  • $3 + n \in \mathbb S \text{ if } n \in \mathbb S$

So we've used a unidirectional implication as your question is addressing. And as you've pointed out in your question, from the two above axioms we can't prove that $7 \not \in \mathbb S$. So we need to augment the above two axioms with something so we can prove $7 \not \in \mathbb S$. Let's try your suggestion of using $\text{iff}$:

  • $0 \in \mathbb S$
  • $3 + n \in \mathbb S \text{ iff } n \in \mathbb S$

Now can we prove that $7 \not \in \mathbb S$ ? No. If we could establish $4 \not \in \mathbb S$ or $10 \not \in \mathbb S$, then sure; but that is no easier than establishing $7 \not \in \mathbb S$. It is in a way "begging the question" (this is what @uniquesolution is getting at in his answer).

What is done is to add an inductive axiom of some sort (the exact language depends on the underlying logic):

  • $0 \in \mathbb S$
  • $3 + n \in \mathbb S \text{ if } n \in \mathbb S$
  • $\bigg(\forall n \in \mathbb S ~:~ P(n) \implies P(3 + n)\bigg) \implies \bigg(P(0) \implies \forall m \in \mathbb S ~:~ P(m)\bigg)$

Now we can establish $7 \not \in \mathbb S$. Instantiate the 3rd axiom with $P(n) = \exists y \in \mathbb N ~:~ n = 3y$ to establish that every member of $\mathbb S$ is a multiple of $3$. Then you use whatever your underlying theory of natural numbers is to establish that $\lnot \exists y \in \mathbb N ~:~ 7 = 3y$.

The point is that

  • yes, using only 'if' is wrong
  • no, using 'iff' isn't right either
  • you have to have somewhere made the claim that your set is inductively defined

There are some alternatives to the 3rd axiom. A kind author will simply say in plain english that the defintion is inductive, so that you can infer the 3rd axiom yourself. Also, as @MauroALLEGRANZA suggested, some authors use "the smallest set satisfying ..." (I have seen this in formal logic papers as well). I don't like that because it is fake formality, it isn't as clear as just saying straightforwardly that you are invoking the concept of induction and it isn't as algebraic as an explicit induction axiom.

Most commonly however, since so many inductive sets already exist, authors will avoid inductive definitions and just provide a mapping from some already defined inductive set (like natural numbers) to the set you with to create:

$$n \in \mathbb N \text{ iff } 3n \in \mathbb S$$

is sufficient.

$\endgroup$
1
  • $\begingroup$ (To any who noticed, my apologies, I avoided the issue of the impredictive nature of induction because it is way too complicated for the scope of the question and I don't fully understand it yet, I would concede it may be just another example of "begging the question"). $\endgroup$
    – DanielV
    Mar 30 '17 at 15:59

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.