1
$\begingroup$

I'm reading Cohen's 'Set theory and Continuum Hypothesis'. In the book, propositional function is defined as follows:

  1. If $A$ is a variable letter then $A$ is a propositional function.

  2. If $A$ and $B$ both are propositional functions then so are $(A) \& (B)$ , $\neg(A)$ etc.

Now first thing what is meant by saying variable letter? It is only mentioned in the book that it's not to be confused with variable in the formal system.

However,I have granted (intuitively) a variable letter to be some statement. Now, I faced another problem related to the 'rule of Inference' (as referred in that book) in predicate calculus,which says :

If $A$ and $A \implies$B are valid statements then $B$ is as well.

Now, the problem is that the rule seems to be provable from the truth table but that's certainly not possible. So, where am I making the mistake?

Proof follows here: $A$ being valid statement the corresponding function always assumes value 1, so is true for $A\implies$B. Now from the truth table of implication it follows that the function corresponding to $B$ must always assume value 1 making $B$ a valid statement.

$\endgroup$
  • $\begingroup$ Rules of inference aren't "provable" or not, they're sound or not. They should preserve truth. Yes it's true that $(p \& (p\to q)) \to q$ is a tautology, but that's a formula, or "propositional function" in Cohen's parlance. Here, $p, q$ are "variable letters". The formula is not to be confused with the rule of inference you cite, which is (still) called by its Latin name modus ponens. $\endgroup$ – BrianO Feb 2 '16 at 14:49
  • $\begingroup$ I cannot find the relevant passage in the book. Are you referring to books.google.si/… ? There it talks about wff's (well-formed formulas, not about "variable letters"). Please be more specific. $\endgroup$ – Andrej Bauer Feb 4 '16 at 7:48
  • $\begingroup$ @Andrej Bauer yes I'm referring to that book. The book talks about wff , yes; but in the definition of propositional function it talks about variable letters and it was also mentioned that variable letters will be replaced by wff eventually. Look at page 8. And also please help me about the second question. $\endgroup$ – Neel Feb 4 '16 at 8:05
2
$\begingroup$

For reference, the relevant passage is on page 8, section I.3.

This passage is about propositional calculus (as opposed to predicate calculus). The term "variable letter" is a termporary notion, used only in this section, to explain the notion of a propostional function. You can think of a "variable letter" as a thing whose value can be $0$ or $1$.

Perhaps it would help to show the difference between propositional functions and predicate calculus. A propositional function, such as, $$\lnot (A_1 \land \lnot A_2) \lor A_2$$ can be thought of as a function $\{0,1\} \times \{0,1\} \to \{0,1\}$. In more modern notation it would be written as $$(A_1, A_2) \mapsto \lnot (A_1 \land \lnot A_2) \lor A_2$$ so as to indicate that we are thinking of a function of two arguments (here written as $A_1$ and $A_2$). This would be different from $$(A_1, A_2, A_3) \mapsto \lnot (A_1 \land \lnot A_2) \lor A_2$$ which is a function of three arguments so it maps from $\{0,1\} \times \{0,1\} \times \{0,1\}$ to $\{0,1\}$.

A formula such as $x^2 + y^2 = 1 \Rightarrow x > 0$ is a slightly different thing. Assuming that $x$ and $y$ range over real numbers, it represents a function $\mathbb{R} \times \mathbb{R} \to \{0, 1\}$. For each value of $x$ and $y$ we get either $0$ and $1$. This may still be called "propostional function" but Cohen does not do that (I would).

If we have a propositional function, say $A_1 \lor \lnot A_2$ and two formulas, say $x^2 + y^2 = 1$ and $y < x$, then we can plug in the formulas for $A_1$ and $A_2$ to get $$(x^2 + y^2 = 1) \lor \lnot (y < x).$$ This corresponds to composition of functions:

  • $A_1 \lor \lnot A_2$ represents a function $f : \{0,1\}^2 \to \{0,1\}$ (exercise: write down the truth table for $f$)
  • $x^2 + y^2 = 1$ represents a function $g_1 : \mathbb{R}^2 \to \{0,1\}$ (exercise: draw a picture of this function)
  • $y < x$ represents a fucntion $g_2 : \mathbb{R}^2 \to \{0,1\}$ (exercise: draw another picture)

Then $(x^2 + y^2 = 1) \lor \lnot (y < x)$ represents a function $h : \mathbb{R}^2 \to \{0,1\}$, namely the composition of $f$, $g_1$ and $g_2$, $$h(x,y) = f(g_1(x,y), g_2(x,y))$$

Now we can explain what Rule 1 says for this example, namely: if $f$ is always $1$ then $h$ is always $1$.

Rule 2 is a different kind of animal. Let me try to explain by analogy and a story.

A story about a teacher and a student:

  • teacher "Last time we defined the derivative $f'(x)$ of a function $f$ at $x$ as a limit. Today I will give you useful rules for calculating derivatives. The first one is $(f+g)'(x) = f'(x) + g'(x)$."
  • student: "I object. This rule follows from the definition of the derivative."
  • teacher: "Yes, precisely, I was going to prove that it follows, but why are you objecting?"
  • student: "Because the rule is not needed. I can just compute the limits instead."
  • teacher: "Technically, that is true. But it is useful to have these rules, so we do not have to keep calculating limits, don't you think? And also, mathematicians have discovered that these rules apply in other situations, where no limits are present. For instance, there are important applications of derivatives in algebra."
  • student: "I hate algebra."

A story about a logician and a mathematician:

  • logician: "Last time we talked about logical formulas and how they say things about mathematical objects. A formula was said to be true if it said something that was in fact the case. Today I will give you useful rules for discovering true formulas. Such rules are called rules of inference and the formulas we can get using the rules are called provable [the Cohen book calls them "valid" which is strange]. The first one is: if $A$ and $A \Rightarrow B$ then $B$."
  • mathematician: "I object. This rule follows from the truth tables."
  • logician: "Yes, precisely, I was going to point out that this is indeed the case. A logician would say that the rule is sound. But why are you objecting?"
  • mathematician: "Because the rule is not needed. I can just refer to truth tables instead."
  • logician: "Technically, that is true. But it is useful to have these rules, so we do not have to keep looking at the truth tables, don't you think? And also, logicians have discovered that these rules apply in many other situations, where truth tables are not available. For instance, Curry and Howard realized that the rules are formally the same as the rules governing the types in a programming language."
  • mathematician: "I hate computers."
$\endgroup$
  • $\begingroup$ Thank you for detailed answer and the nice story. Actually I assumed the rules should not be derivable(kind of act like axioms). So, you meant to say that some of the listed rules in the book can be derived from the truth table, right? $\endgroup$ – Neel Feb 4 '16 at 9:53
  • $\begingroup$ Well, it depends on how you organize things. You could start with the idea of truth tables and get rules from that (like in my story), or you could start with the rules and then observe that truth tables model the rules. $\endgroup$ – Andrej Bauer Feb 4 '16 at 12:19

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.