2

Let $A_1,A_2$ be sentence symbols. Could anyone advise me how to prove $(A_1\rightarrow\wedge A_2)$ is not a well-formed formula? Thank you.

Alexy Vincenzo
  • 5,400

5 Answers5

6

Somewhere you have a definition of WFF that says something like:

  1. Atoms are wffs.
  2. If $\Phi$ and $\Psi$ are wffs, then the formula $⌜( \Phi \land \Psi )⌝$ is a wff.
  3. If $\Phi$ and $\Psi$ are wffs, then the formula $⌜( \Phi \lor \Psi )⌝$ is a wff.
  4. If $\Phi$ and $\Psi$ are wffs, then the formula $⌜( \Phi \to \Psi )⌝$ is a wff.
  5. Nothing else is a wff.

(I am using Quine's quasiquoting convention here, so that for example the expression “$⌜ (\Phi \to \Psi) ⌝$” means the result of concatenating “(”, $\Phi$, “$\to$”, $\Psi$, and “)”.)

If we can show that your string $“(A_1\to\land A_2)”$ is not covered by any of clauses 1–4, then by clause 5, it is not a wff. It is not an atom, so clause 1 does not apply. (You need to invoke the definition of ‘atom’ here.) If it were a wff under clause 3 it would contain a $\lor$ symbol, which it does not, so clause 3 does not apply.

If it were a wff under clause 2, then we would have to have $\phi = “A_1\to”$ and $\psi = “A_2”$. However, we can show that $“A_1\to”$ is not a wff, because it is not an atom, and is not covered under clauses 2–4 because it has no parentheses; therefore under clause 5, $“A_1\to”$ is not a wff, and so clause 3 does not apply to $“(A_1\to\land A_2)”$. Similarly we can show that clause 4 does not apply, and then we are done.

MJD
  • 65,394
  • 39
  • 298
  • 580
3

See by Stephen Simpson Mathematical Logic in Ch.1 [page 4]: Definition 1.1.11. for the definition of formation tree and the way to check if a formula is well formed.

You must start form the sentence symbols that are the leaf of the tree, going up step by step applying the rules for formula generation.

In your case, you can start from $A_1$ or $A_2$, but in both case you will find a dyadic connective; in case of $A_1 \rightarrow$ you need as RHS another sentence symbol and not the connective $\land$.

If you start from $\land A_2$, again in the LHS you are expecting to find a sentence symbols and not the connective $\rightarrow$.

Mauro ALLEGRANZA
  • 94,169
2

The usual way to prove this uses the fact that the set of formulas is the smallest set that (i) contains the atoms and (ii) is closed under the usual connectives.

The result immediately follows from the following fact:

(+) For every set $\Sigma$ that contains $(A_1 \rightarrow \wedge A_2)$ and that satisfies (i) and (ii) there is some smaller set (namely $\Sigma \setminus \lbrace (A_1 \rightarrow \wedge A_2) \rbrace$) that satisfies (i) and (ii).

So, no set containing the string is the smallest set satisfying (i) and (ii). So, the string is no formula.

To complete this prove you simply have to verify the fact (+). For this it suffices to show that $\Sigma \setminus \lbrace (A_1 \rightarrow \wedge A_2) \rbrace$ satisfies (i) and (ii).

Jon
  • 456
  • I think we can prove, by induction, that any well formed formula has equal number of left parentheses and connective symbols? – Alexy Vincenzo Feb 06 '14 at 13:53
  • Right, that's another way to show that the string under consideration is no formula. But I think my way is simpler, since it doesn't require any inductive arguments. Furthermore my way is more general than yours, because the non-well- formedness of $pq$ ($p$ concatenated to $q$) for any propositional variables $p, q$ can be proved by appeal to my way, but not by appeal to your way. – Jon Feb 07 '14 at 17:28
1

$\wedge$ only can appear between sentence symbols: $A\wedge B$.

Martín-Blas Pérez Pinilla
  • 41,546
  • 4
  • 46
  • 89
  • This is the general method. We can prove by induction on formulas that every formula has some property, then check that the formula in question does not have that property. The easiest such property in this case is that $\to$ and $\land$ are never adjacent. – Carl Mummert Feb 08 '14 at 13:11
  • "∧ only can appear between sentence symbols: A∧B."

    Huh? $\land$ appears between parentheses and sentence symbols. E. G. (A $\land$ (B $\lor$ C)) or (A) $\land$ (B) in another infix scheme. That said, if you ignore improper symbols, then maybe $\land$ can only appear between sentence symbols.

     – Doug Spoonwood Jul 06 '15 at 13:51
  • @CarlMummert I don't know how to prove that binary operators are never adjacent. I do think I could fairly easy prove that the sum of the number of sentence variables and constants has to equal one more than the number of binary connectives (given that no connectives with arity greater than 2 exist in the formula). The property that binary operators are never adjacent is local to infix schemes. The property that (#(connectives) + 1) = #(sentence variable and constants) holds for prefix, infix, and postfix schemes. – Doug Spoonwood Jul 06 '15 at 13:58
0

→ and ∧ are both binary connectives.

A simple lemma goes that if a wff doesn't have any three_up-ary operators, such that

three_up >= 3, then the number of sentence letters in a wff, #(sentences), is one more than #(binary_connectives). That is,

"#(sentences) = (#(binary_connectives) + 1)"

Your string has the same number of binary_connectives as it does sentence letters. Thus, it is not a wff.

Doug Spoonwood
  • 11,211