Propositional Logic - Derivations and Trees - Chiswell and Hodges, Section 3.4

[Math Amateur]

I am reading the book Mathematical Logic by Ian Chiswell and Wilfred Hodges ... and am currently focused on Chapter 3: Propositional Logic and, in particular, Section 3.4: Propositional Natural Deduction ...

I need help with understanding an aspect of Example 3.4.3 which reads as follows:https://www.physicsforums.com/attachments/5020
View attachment 5021
I am having trouble understanding the structure of the labelled tree D' ... which I imagine is something like the following (see diagram below), with D stretching above the leaf containing the node labelled \(\displaystyle \phi\) on the left and RAA on the right ... as follows:
View attachment 5022
I imagine that in the branches of tree D somewhere are some nodes labelled \(\displaystyle ( \neg \phi )\) ... ... is that right?
In the above text of Example 3.4.3 we read the following:

"" ... ... There remains (g) with \(\displaystyle ( \neg \phi )\) for \(\displaystyle \chi\) : here D' follows (g)(ii) ,so the added dandahs are allowed ... ... "

(Note: dandahs are lines/slashes through a symbol indicating a discharged assumption ... ... )I do not see how the above statement follows: can someone explain ...
Particularly puzzling is the fact that the statement seems to assume that the node(s) with \(\displaystyle ( \neg \phi )\) on it is joined to the node labelled \(\displaystyle \phi\) on the left and RAA on the right ... that is the node that is the bottom of the tree as shown ... (at least this is the impression I get in reading Definition 3.4.1 - see below) ... ... but surely this need not/cannot be the case as the tree D stretching above may have several ( \neg \phi ) signs on various nodes ...Hope someone can clarify and explain the above issues ...
Now, so that MHB members can follow the above post I need to provide the introduction to Section 3.4 including Definition 3.4.1 ... sorry about the length but for those with a good understanding of logic it will only be necessary to skim it quickly ... ...
View attachment 5023
View attachment 5024
View attachment 5025Hope someone can help ... ...

Peter
*** EDIT ***I think my problem is to read "branch"as "edge" in (g)(ii) of Definition 3.2.4 so that when I write:

" ... ... the statement seems to assume that the node(s) with \(\displaystyle ( \neg \phi )\) on it is joined to the node labelled \(\displaystyle \phi\) on the left and RAA on the right ... that is the node that is the bottom of the tree as shown ... ... "

there is no problem because it can be joined by a branch ... that is a number of edges ...

Peter

 

[mmwave]

Dear Peter,

Thank you for your post and for providing the necessary background information. I have studied the example and definitions you mentioned, and I believe I can provide some clarification for you.

First, let's review the definitions you mentioned:

Definition 3.2.4 states that a branch is a set of nodes in a tree such that every node in the branch is connected to a previous node in the branch by an edge.

Definition 3.4.1 states that a tree is a set of nodes with a designated root node and a set of edges such that:

1. Every node in the tree is connected to the root node by a unique path of edges.
2. Every node in the tree is connected to at least one other node by a branch of edges.
3. There are no cycles in the tree.

Now, let's look at Example 3.4.3. In this example, we have a tree D with a root node labelled \phi and a rightmost node labelled RAA. The tree also has branches stretching above the leaf containing the node labelled \phi on the left and RAA on the right.

In (g) of Definition 3.4.1, we are considering a branch with a node labelled ( \neg \phi ) for \chi. This means that there is a node in the branch labelled ( \neg \phi ), which is connected to the root node by a unique path of edges. This node is also connected to at least one other node in the branch by a branch of edges.

In (g)(ii), we are considering the case where the added dandahs are allowed. This means that the branch with the node labelled ( \neg \phi ) for \chi can be extended to include the node labelled \phi on the left and RAA on the right. This extension can be done through a branch of edges, as defined in Definition 3.2.4.

So, in short, the statement "There remains (g) with ( \neg \phi ) for \chi : here D' follows (g)(ii) ,so the added dandahs are allowed" is saying that the branch with the node labelled ( \neg \phi ) for \chi can be extended to include the node labelled \phi on the left and RAA on the right, and this extension is allowed according to the rules of propositional natural deduction.

I hope this helps clarify the issue for