1

I had asked this earlier but perhaps I could not put it precisely enough.

Consider the atomic formulae $\forall xPx$ and $Pa$, and the logical axiom $\forall xPx \rightarrow Pa$.

Can we define a function $T$, per an interpretation, from the set of sentences to $\{0,1\}$, depending on whether the sentence is true in that interpretation?

Further, if we let $T(\forall xPx)=u$ and $T(Pa) = v$, $u$ and $v$ being Boolean variables, taking values 0 or 1, depending on the interpretation, then do they always satisfy the equation, $$ T(\forall xPx \rightarrow Pa)=[1-{u\cdot (1-v)}]=1? $$

@Mauro:with this analysis, if our language has constants $a_1, a_2, \dots$ and we let $T(Pa_1)=v_1, \space T(Pa_2)=v_2, \dots$ then we should have, $u=c_1.v_1, \space u=c_2.v_2, \dots$ for all independent variables $v_1,v_2, \dots$ ($u$ being a Boolean function of $v1,v2, \dots$).

But the only Boolean function that can satisfy all these equations is the function that always takes only the value $0$.

How does one resolve this?

Alex M.
  • 35,207
Sudhir
  • 115
  • As you have it written, your equality fails any time $\forall xP(x)$ is true, which I'm not sure is what you intend... – Malice Vidrine Dec 11 '13 at 09:22
  • If we have u = 1, then necessarily v = 1 for the equality to hold. – Sudhir Dec 11 '13 at 10:36
  • But $\forall xP(x)\to P(a)$ is a tautology, so it needs to always evaluate to 1. In this case, if $\forall xP(x)$ is false and $P(a)$ is true, the equation in your post gives 0. That is not how you want a conditional to evaluate, much less a logical truth. – Malice Vidrine Dec 11 '13 at 11:29
  • But if ∀xPx is false, then u = 0, and the equation T(∀xPx→Pa)=1-u.(1-v)=1 holds, irrespective of what v is. – Sudhir Dec 11 '13 at 11:47
  • The conditions under which that evaluation comes out to 1 are not the conditions under which a conditional is true, though. The conditions under which your formula comes out true are when $u=0,v=0$ and under no other conditions--that is not a conditional, that's a Quine dagger, a "nor" operator. – Malice Vidrine Dec 11 '13 at 12:23
  • I think my notation may not be strictly as per standard operator precedence,hence the ambiguity.It is 1 -{u.(1-v)}. I will edit the question accordingly – Sudhir Dec 11 '13 at 13:04
  • The edit did not work as have no access to LaTex. – Sudhir Dec 11 '13 at 13:14
  • Aaaah, sorry! The way you wrote it is probably standard, and I'm not used to arithmetic groupings because I'm a dork. Sorry again! – Malice Vidrine Dec 11 '13 at 13:34
  • No problem at all! – Sudhir Dec 11 '13 at 14:14

2 Answers2

1

The boolean interpretation of a formula with conditional-sign is :

$|P \rightarrow Q| = 1 - |P| + |P| |Q|$.

So, if $|P| = u$ and $|Q| = v$, we have that: $[1-u+uv] = [1-u(1-v)]$.

But this is NOT always 1.

Mauro ALLEGRANZA
  • 94,169
  • My question is whether by taking ∀xPx→Pa as an axiom,are we insisting that 1-{u.(1-v)} always evaluate to 1,so that u is not independent of v ? – Sudhir Dec 11 '13 at 14:05
  • In fact, taking v as independent, can we solve for u,to give u = c.v,where c is some arbitrary parameter? – Sudhir Dec 11 '13 at 14:17
  • 1
    I'm not sure to understand your point... But, take in account that the FOL axiom ∀xPx→Pa is logically valid but it is not tautologically valid. Interpreting it with a boolean valuation it is simply P→Q, and this is not a tautology, because (1-u+uv) is not identically 1. Only if you interpret it as a FO-language formula (i.e.taking into account his "inner" logical form, and not only the propositional one) it is valid. – Mauro ALLEGRANZA Dec 11 '13 at 14:44
  • If u and v were independent Boolean variables, then 1-u+uv would not identically evaluate to 1. However, in FOL, we are considering only such interpretations where 1-u+uv = 1, are we assuming that u is not independent of v,but dependent on v by the relation u = c.v ,where c is any arbitrary parameter? – Sudhir Dec 11 '13 at 15:08
  • 1
    In a certain sense, yes. When interpreting ∀xPx→Pa, we are not using two independent evaluations (like the P→Q case). The rule for interpreting the universal quantifier says (roughly) that ∀xPx is true iff for each (name of an) object c in the domain of interpretation, P(c) is true; if this is so, it follows that P(a) is also true, because a is (the name of) an object in the domain of interpretation. – Mauro ALLEGRANZA Dec 11 '13 at 15:16
  • So am I correct to say that FOL requires u and v to be related by the equation 1-u+uv =1 and also u = c.v? If ∀xPx→Pa were the only one logical axiom assumed,could we assume that ∀xPx could be be any wff Pa&Q for any arbitrary Q? – Sudhir Dec 11 '13 at 15:27
  • 1
    I don't think so. I agree that ∀xPx and Pa are not independent, but the correct interpretation is that ∀xPx is Pa, and Pb, and Pc, ... where {a, b, c, ...} is the domain of the interpretation. – Mauro ALLEGRANZA Dec 11 '13 at 16:00
  • If ∀xPx→Pa only , (and not ∀xPx→Pb or Pc etc) was the logical axiom assumed, then ∀xPx could be consistently interpreted to be Pa&Q for any Q.Following this, I have a consequential question, which I will edit into my original question. This is what has been bothering me for quite some time and I would appreciate consideration in this forum – Sudhir Dec 11 '13 at 17:10
1

I think again that you are missing the different use of tautological consequence (and tautology) and of logical consequence (and validity) [please, see again Peter Smith's yesterday answer].

In sentential (or propositional) logic we can use boolean valuations and truth-tables; in first-order logic you need the more complicated notion of satisfaction, based on assignment of value to free variables.

Is a basic result of MathLog that a tautology is logically valid , but not vice versa.

If you "downsize" a first-order formula into sentential logic, you treat all the atoms (like $\forall xP(x)$) as single sentential letters. Because $\forall xP(x)$ is different from $P(a)$, when you "downsize" them you must use different sentential letters; say $A$ and $B$.

In sentential logic, your formula becomes : $A \rightarrow B$, and this is not a tautology.

Tha first-order formula $\forall xP(x) \rightarrow P(a)$ is an axiom of first-order logic (and not of sentential logic) because, according to the standard semantic of FOL (that take in account the "more sophisticated" logical form of the formula, and this is not possible in the sentential version) it is logically valid.

Mauro ALLEGRANZA
  • 94,169
  • I would readily agree that ∀xPx→Pa, is not a tautology, but by 'upsizing'it to a validity in FOL,I am restricting the possible interpretations for ∀xPx and Pa, creating a functional relation between u and v. It is as if instead of freedom in two dimensions,the interpretations are now restricted to only a part of the u-v plane.So u is a Boolean function of the independent variable v.So, in a language with infinitely many constants, u must be a function of the infinitely many independent variables. – Sudhir Dec 11 '13 at 19:21
  • 1
    I'm not sure to understand well. You are thinking of a way to produce form a boolean valuation an interpretation usable for the FOL formula ... Boolean valuations makes a semantic interpretation of sentential formulae based on the "coarse-grained" syntactic analysis of sentential logic; i.e. they consider only truth-functional connectives. Moving to FOL, we use a syntax more "fine-grained" that looks inside the sentence using variables, predicates and quantifiers. A boolena valuation don't see this and this is why it treats the atoms (like: ∀xPx) of a FOL formula as sentential letetrs. – Mauro ALLEGRANZA Dec 12 '13 at 07:30
  • 1
    I see your "metaphor" in terms of u-v plane and the functional relation between u and v. I'm not sure that the starting point is correct. When you evaluate a sentential calculus formula A→B, you are using a single valuation such that |A→B| is 1-|A|+|A||B|. – Mauro ALLEGRANZA Dec 12 '13 at 07:34
  • The semantics of FOL is fully 'captured'into a purely syntactical deductive calculus by the logical axioms and rules of inference.My starting point is not the semantics,but just one ( out of infinitely many) logical axioms axiom ∀xPx→Pa.as a propositional formula, it does not necessarily evaluate to 1.As an axiom of FOL deductive calculus (the semantics already accounted for) I require it to evaluate to 1. That requirement means that the valuation u of ∀xPx is a Boolean function of v,the valuation of Pa. – Sudhir Dec 12 '13 at 11:19
  • My point is: Either ∀xPx→Pa does not necessarily evaluate to 1, in which case the valuations u and v of ∀xPx and Pa respectively are independent Boolean variables OR ∀xPx→Pa necessarily evaluates to1, in which case u is a Boolean function of v. It should not be both. – Sudhir Dec 12 '13 at 17:32