Degree of Sentence in Smith's Godel Book: Explained

  • Context: MHB 
  • Thread starter Thread starter agapito
  • Start date Start date
  • Tags Tags
    Degree
Click For Summary

Discussion Overview

The discussion revolves around the concept of "degree" of a sentence in the context of formal languages as presented in Smith's Godel book. Participants explore the implications of Godel numbering and the construction of sentences through induction proofs, focusing on the definitions and examples related to degrees of sentences.

Discussion Character

  • Technical explanation
  • Conceptual clarification
  • Homework-related

Main Points Raised

  • One participant asks for clarification on what the property of "degree" means in the context of formal languages.
  • Another participant suggests that "degree" refers to the unique positive integer assigned to statements or proofs through Godel numbering.
  • A participant cites a definition from the book, stating that a $\Delta_0$ sentence has degree $k$ if it is constructed from specific well-formed formulas (wffs) using a certain number of connectives and bounded quantifiers.
  • There is a question regarding the interpretation of an example from the book, specifically whether a sentence with 1 connective and 1 bounded quantifier corresponds to degree 2, and what an example of degree 3 would look like.
  • Another participant confirms that the previous example indeed corresponds to degree 2 and provides information about a formula that has degree 3.

Areas of Agreement / Disagreement

Participants generally agree on the definitions and interpretations of the degree of sentences, but there are ongoing inquiries about specific examples and their corresponding degrees, indicating some uncertainty in application.

Contextual Notes

The discussion references specific examples and definitions from the book, which may depend on the reader's familiarity with the material and the context of Godel's work. There are unresolved questions about the application of these definitions to specific examples.

Who May Find This Useful

This discussion may be useful for those studying formal languages, Godel's work, or mathematical logic, particularly in understanding the concept of degrees of sentences and their implications in formal proofs.

agapito
Messages
46
Reaction score
0
In Smith's Godel book he presents induction proofs that deal with the degree of a sentence of a formal language. So the base case corresponds to degree 0. The assumption is for sentence of degree k. Then finally proving that sentence of degree k+1 holds. What exactly does the property of "degree" mean in this context? Thanks for any clarification.
 
Technology news on Phys.org
Using "Godel numbering" every statement or proof can be assigned a unique positive integer. I believe that is the "degree" you are referring to.
 
HallsofIvy said:
Using "Godel numbering" every statement or proof can be assigned a unique positive integer. I believe that is the "degree" you are referring to.

OK many thanks for your input. am
 
agapito said:
What exactly does the property of "degree" mean in this context?
Page 75 says, "So let us say that a $\Delta_0$ sentence has degree $k$ iff it is built up from wffs of the form $\sigma=\tau$ or $\sigma\le\tau$ by $k$ applications of connectives and/or bounded quantifiers."
 
Evgeny.Makarov said:
Page 75 says, "So let us say that a $\Delta_0$ sentence has degree $k$ iff it is built up from wffs of the form $\sigma=\tau$ or $\sigma\le\tau$ by $k$ applications of connectives and/or bounded quantifiers."

Thanks for replying. To check for my understanding, if you look at example vii on previous page:

Sentence has 1 connective and 1 bounded quantifier. Would this mean that k in this case is 2? If correct, what might an example of k = 3 look like?

As always, your help is greatly appreciated. am
 
agapito said:
To check for my understanding, if you look at example vii on previous page:

Sentence has 1 connective and 1 bounded quantifier. Would this mean that k in this case is 2?

Yes.

agapito said:
If correct, what might an example of k = 3 look like?
The degree of formula (vi) right before that is 3.
 
Evgeny.Makarov said:
Yes.

The degree of formula (vi) right before that is 3.

Understood, many thanks, Evgeny. agapito
 

Similar threads

Non Computable Functions And Godel's Theorem
  • · Replies 32 ·
2
Replies
32
Views
5K
MHB Proof of Euler Tour in Graphs: In-degree($v$)=Out-Degree($v$)
  • · Replies 1 ·
Replies
1
Views
2K
Undergrad Explaining Enumerable: Understanding the Concept in Godel, Escher, Bach
  • · Replies 6 ·
Replies
6
Views
2K
Von Neumann replicator vehicle model
  • · Replies 23 ·
Replies
23
Views
3K
Graduate Gödel’s theorem: larger than proof?
  • · Replies 8 ·
Replies
8
Views
2K
Proving uniqueness of almost irregular graphs with equal degrees for n=2k
  • · Replies 3 ·
Replies
3
Views
3K
Is Alan Turing given too much credit when it comes to computers?
  • · Replies 29 ·
Replies
29
Views
5K
Is There a Flaw in this Turing Test Reasoning?
  • · Replies 9 ·
Replies
9
Views
2K
Graduate Q.E.D.Undecidability of Q: Proving Godel's First Incompleteness Theorem
  • · Replies 0 ·
Replies
0
Views
1K
Perspectives with an almost-completed BSc. Physics
  • · Replies 4 ·
Replies
4
Views
2K