Well-formed Formulas Set in Formal Theory

[Calculuser]

There is a statement on page 26 in Elliott Mendelson's book of "Introduction to Mathematical Logic" as shown:

What I got from the statement above, which is obvious, I guess, is that in the sequence of $\mathcal{B}_1,\mathcal{B}_2,...\mathcal{B}_k$ there are "SOME" well-formed formulas (wfs) that elements of $\Gamma$ set of wfs, or axioms that are NOT elements of $\Gamma$, or direct consequences by some rule of inference of some the preceding wfs in the sequence. To me, It also seem to be possible that "ALL" of those $\mathcal{B}_k$ wfs can by definition be one of the three possibilities mentioned above. Hence, we cannot say $\Gamma=\{\mathcal{B}_1,\mathcal{B}_2,...\mathcal{B}_k\}$.

My questions in regard to these are:

1) Does $\mathcal{L}(\mathcal{B}_k=\mathcal{L})$ has to be in the set of $\Gamma$ or not?
2) What exactly does $\Gamma$ represent?

 

[fresh_42]

There is a statement on page 26 in Elliott Mendelson's book of "Introduction to Mathematical Logic" as shown:

View attachment 242202

What I got from the statement above, which is obvious, I guess, is that in the sequence of $\mathcal{B}_1,\mathcal{B}_2,...\mathcal{B}_k$ there are "SOME" well-formed formulas (wfs) that elements of $\Gamma$ set of wfs, or axioms that are NOT elements of $\Gamma$, or direct consequences by some rule of inference of some the preceding wfs in the sequence. To me, It also seem to be possible that "ALL" of those $\mathcal{B}_k$ wfs can by definition be one of the three possibilities mentioned above. Hence, we cannot say $\Gamma=\{\mathcal{B}_1,\mathcal{B}_2,...\mathcal{B}_k\}$.

... which wasn't said.

My questions in regard to these are:

1) Does $\mathcal{L}(\mathcal{B}_k=\mathcal{L})$ has to be in the set of $\Gamma$ or not?

No. $\mathscr C \in \{\, \mathscr B_k\,\}$.

2) What exactly does $\Gamma$ represent?

$\Gamma$ represents given conditions. E.g. for any linear map $\varphi$ we have $\varphi(0)=0$ means '$\varphi$ is linear' $\in \Gamma$. It also means that impossible statements can be part of $\Gamma$. E.g. if any pink unicorn is part of equidae, then it has four hooves, means that 'pink unicorns are part of equidae' is an element of $\Gamma .$

 

[Calculuser]

... which wasn't said.

Did you mean the entire text or just $\Gamma=\{\mathcal{B}_1,\mathcal{B}_2,...\mathcal{B}_k\}$? Could you clarify a bit?

$\Gamma$ represents given conditions. E.g. for any linear map $\varphi$ we have $\varphi(0)=0$ means '$\varphi$ is linear' $\in\Gamma$. It also means that impossible statements can be part of $\Gamma$. E.g. if any pink unicorn is part of equidae, then it has four hooves, means that 'pink unicorns are part of equidae' is an element of $\Gamma$.

Then $\Gamma$ is like a universal set of any statements that are either true or false.

No. $\mathscr C \in \{\mathscr B_k\}$.

In light of what I understood in the comment on your explanation of $\Gamma$ above, that seemed absurd to me. Why can $\mathscr C$ not be an element of $\Gamma$, as it is a universal set of statements?

 

[stevendaryl]

Then $\Gamma$ is like a universal set of any statements that are either true or false.

What does "universal set" mean?

$\Gamma$ is a set of assumptions or axioms, and you're trying to figure out what can be derived from those assumptions.

So, for example, if I tell you:

1. Sam is a dog.
2. If Sam is a dog, then Sam is a mammal.
3. If Sam is a mammal, then Sam is a vertebrate.
4. If Sam is a vertebrate, then Sam has bones.

Then let $\Gamma$ be the collection of statements 1-4.

A consequence of this is: $\mathcal{C}:$ "Sam has bones". To prove this, let

$B_1 =$ "Sam is a dog"
$B_2 =$ "If Sam is a dog, then Sam is a mammal"
$B_3 =$ "Sam is a mammal".
$B_4 =$ "If Sam is a mammal, then Sam is a vertebrate."
$B_5 =$ "Sam is a vertebrate."
$B_6 =$ "If Sam is a vertebrate, then Sam has bones."
$B_7 =$ "Sam has bones"

Then the sequence $B_1 ... B_7$ is a proof of $\mathcal{C}$ provided that:

• $\mathcal{C} = B_7$
• Every statement $B_i$ is either in $\Gamma$, or follows from previous statements.

We can check:

1. $B_1$ is in $\Gamma$ (check)
2. $B_2$ is in $\Gamma$ (check)
3. $B_3$ follows from $B_1$ and $B_2$ (check)
4. $B_4$ is in $\Gamma$ (check)
5. $B_5$ follows from $B_3$ and $B_4$ (check)
6. $B_6$ is in $\Gamma$ (check)
7. $B_7$ follows from $B_5$ and $B_6$ (check)
8. $B_7 = \mathcal{C}$ (check)

So we've shown that $\mathcal{C}$ is a consequence of $\Gamma$.

 

[Calculuser]

What does "universal set" mean?

What I mean by that is a set of anything related to the real of propositions, e.g. atomic formulas, statement forms, etc. from which we deduce a consequence with some propositions within. Because in the screenshot I posted above it does NOT say that ALL $\mathcal{B}_1,\mathcal{B}_2,...\mathcal{B}_k$ belong to $\Gamma$, yet uses "for each $i$, $\mathcal{B}_i$ is EITHER an axiom OR $\mathcal{B}_i$ in $\Gamma$, OR $\mathcal{B}_i$ is a direct consequence..." phrase. Then I tend to think that there is a possibility of $\mathcal{B}_i$ as an axiom, but not an element of $\Gamma$. I do not know whether or not this is possible, if it can, then how.

We can check:

1. $B_1$ is in $\Gamma$ (check)
2. $B_2$ is in $\Gamma$ (check)
3. $B_3$ follows from $B_1$ and $B_2$ (check)
4. $B_4$ is in $\Gamma$ (check)
5. $B_5$ follows from $B_3$ and $B_4$ (check)
6. $B_6$ is in $\Gamma$ (check)
7. $B_7$ follows from $B_5$ and $B_6$ (check)
8. $B_7= \mathcal{C}$ (check)

Where do these $B_3,B_5,B_7$ belong, then, if not to $\Gamma$?

 

[stevendaryl]

Because in the screenshot I posted above it does NOT say that ALL $\mathcal{B}_1,\mathcal{B}_2,...\mathcal{B}_k$ belong to $\Gamma$, yet uses "for each $i$, $\mathcal{B}_i$ is EITHER an axiom OR $\mathcal{B}_i$ in $\Gamma$, OR $\mathcal{B}_i$ is a direct consequence..." phrase. Then I tend to think that there is a possibility of $\mathcal{B}_i$ as an axiom, but not an element of $\Gamma$.

No, the rules explicitly say that each $B$ must either be an element of $\Gamma$, or derivable from previous sentences by the rules of inference. For the sake of the definition of "consequence", $\Gamma$ is the only set of axioms you have.

Where do these $B_3,B_5,B_7$ belong, then, if not to $\Gamma$?

$\Gamma$ in my example is the set $\{ B_1, B_2, B_4, B_6 \}$. So $B_3, B_5, B_7$ are NOT in $\Gamma$, but they are derivable from other $B$'s.

 

[Calculuser]

No, the rules explicitly say that each $B$ must either be an element of $\Gamma$, or derivable from previous sentences by the rules of inference. For the sake of the definition of "consequence", $\Gamma$ is the only set of axioms you have.
$\Gamma$ in my example is the set $\{ B_1, B_2, B_4, B_6 \}$. So $B_3, B_5, B_7$ are NOT in $\Gamma$, but they are derivable from other $B$'s.

I agree on that part! However, I do not get why it was extra(?) stated that $\mathcal{B}_i$ can also be an axiom in the original text of the author as said "...either $\mathcal{B}_i$ is an axiom..." in addition to the things you said. Wouldn't it be sufficient to say that $\mathcal{B}_i$ is either a well-formed formula from $\Gamma$ or a direct consequence by some rule of inference as you stated?

 

[stevendaryl]

I agree on that part! However, I do not get why it was extra(?) stated that $\mathcal{B}_i$ can also be an axiom in the original text of the author as said "...either $\mathcal{B}_i$ is an axiom..." in addition to the things you said. Wouldn't it be sufficient to say that $\mathcal{B}_i$ is either a well-formed formula from $\Gamma$ or a direct consequence by some rule of inference as you stated?

Wow. I'm sorry. I read it over too quickly. It does say that $B_i$ can be an axiom. In that case, I'm not sure about the motivation for introducing $\Gamma$. Why not let $\Gamma$ include all the axioms?

The author may be distinguish "logical" from "nonlogical" axioms, where a logical axiom defines when something is true for every possible theory.

 

[Periwinkle]

One theory described in the Proposition Calculus can be accurately illustrated by chess
​

• The language is the sequence of symbols that can be used to describe a chess game position.
• Well-formed formulas correspond to real, possible positions. So there is only one white and one black king on the board, not five of white and black.
• Axioms: A series of chess game positions.
• Hypothesis: specific chess game positions.
• Conclusion rules: rules for chess steps.
• Proof: To derive a particular chess game position from axioms and hypotheses based on rules for chess play. (So how chess pieces can move.)

Perhaps I am not even mistaken that Hilbert was motivated by the analogy with chess when he created the Hilbert program.

 

[sysprog]

... which wasn't said.

No. $\mathscr C \in \{\, \mathscr B_k\,\}$.

$\Gamma$ represents given conditions. E.g. for any linear map $\varphi$ we have $\varphi(0)=0$ means '$\varphi$ is linear' $\in \Gamma$. It also means that impossible statements can be part of $\Gamma$. E.g. if any pink unicorn is part of equidae, then it has four hooves, means that 'pink unicorns are part of equidae' is an element of $\Gamma .$

If a white horse is not a horse, then a pink unicorn is not a unicorn, and an Easter egg is not an egg.

$(\forall x)[(Wx\land Hx) \Rightarrow \neg Hx]\Rightarrow ((\forall x)[(Px\land Ux) \Rightarrow \neg Ux] \land (\forall x)[(\mathcal E x\land Ex) \Rightarrow \neg Ex])$

 

[fresh_42]

Wow. I'm sorry. I read it over too quickly. It does say that $B_i$ can be an axiom. In that case, I'm not sure about the motivation for introducing $\Gamma$. Why not let $\Gamma$ include all the axioms?

Loosely speaking, a proof consists of a framework given by axioms, assumptions as basis for conclusions under these assumptions, here $\Gamma$, and previous or intermediate results $\mathscr{B}_i$ including the last conclusion $\mathscr{B}_k$.

Neither $\Gamma$ nor the $\mathscr{B}_i$ include axioms, as they are of a different kind. Axioms build the framework, or calculus, or setup of what follows. They have to be minimal in number and without contradictions. This is not true for $\Gamma\,.$ If $\text{ False } \in \Gamma$, then we still can get a valid proof. Indeed it happens regularly in mathematics, that a conclusion is drawn without bothering existence! This is often part of a second consideration afterwards. E.g. in the theory of simple Lie algebras, all possible root systems are classified before one proves, that each of them actually represents a specific Lie algebra. The $\mathscr{B}_i$ are results which already have been concluded from axioms and $\Gamma$.

 

[Periwinkle]

Neither ΓΓ nor the BiBi include axioms, as they are of a different kind. Axioms build the framework, or calculus, or setup of what follows. They have to be minimal in number and without contradictions. This is not true for Γ.Γ. If False ∈Γ False ∈Γ, then we still can get a valid proof. Indeed it happens regularly in mathematics, that a conclusion is drawn without bothering existence!

For someone to give guidance to the person asking the question, they need to know Mendelson's book, the book must be on the table before. The detail shown is not enough. I have the book, not the English edition, and the symbols used are slightly different. I checked what it was about.

Development of the formal theory of Proposition calculus, so when deciding the correctness of a statement is not based on the truth table, but the valid statements are purely linguistic means proven from the axioms.

I wrote this only because the hypotheses as mentioned earlier included "False" as an example. But whoever sees the context of the question will know that this is not appropriate here because the book speaks of a purely syntax-based formal language system, where truth, falsehood does not exist. This is the question of interpretation. But obviously, without the book, you can't see the context.

 

[stevendaryl]

Neither $\Gamma$ nor the $\mathscr{B}_i$ include axioms, as they are of a different kind.

The quote from the first post said that $\mathscr{B}_i$ is either an axiom, or an element of $\Gamma$ or follows from previous statements by the rules of inference.

 

[fresh_42]

The quote from the first post said that $\mathscr{B}_i$ is either an axiom, or an element of $\Gamma$ or follows from previous statements by the rules of inference.

Right. This means that the $\mathscr{B}_i$ can be any intermediate step, but $\Gamma$ is still the set which lists the conditions given for a proof. We don't write proofs like: Given ZFC then Zorn's Lemma and AC are equivalent. or even list ZFC in the list of conditions. We separate it into our general framework and only say: Zorn's Lemma and AC are equivalent.