Proving the Truth: The Relationship Between Formal Systems C, K, and O

[honestrosewater]

[Just as an example, P can be "My name is Rachel" and Q can be "I know my name is Rachel." Use your own name if the use of "I" bothers you. I am using P and Q generally in what follows.]
P, Q, X are statements. C, K, O, are systems. Use different variables if it helps.

Q: I know P.
P is a true statement in consistent, formal system C.
Can I prove Q is a true statement in C? (I am assuming this excludes Q from being an axiom of C.)
If I construct C and prove P is true in C, I know P. That is, by proving P is true in C, I am proving Q is true.
Q is a true statement in formal system K. K is then consistent, right? (K is only tied to one C, there is one K for each C.)
What is the relationship between C and K?
If I a) prove X is a true statement in a consistent, formal system or b) directly observe X, I know X is true.
Let all X be axioms of formal system O.
What is the relationship between C, K, and O? If Q is an axiom of O, how can Q be a theorem of C? Or, how can Q not be an axiom of C?

BTW I'm not assuming O is consistent. In fact I think O is inconsistent. I think my question has something to do with self-reference, but I'm not sure how. Sorry, it's difficult for me to ask this intelligently.
Perhaps this would be better suited to the Logic forum, but since I am talking about knowledge, I put it here.
Edit: I used C for Consistent, K for Known, O for Observed, in case it helps you keep them straight.

 

[honestrosewater]

Okay, I'll try something else.
I know P iff I prove P is true in a consistent, formal system.
Can I know I know P?
This seems like a pretty simple question, but something about it makes me loopy.

 

[quantumdude]

A question and a comment.

[Just as an example, P can be "My name is Rachel" and Q can be "I know my name is Rachel." Use your own name if the use of "I" bothers you. I am using P and Q generally in what follows.]
P, Q, X are statements. C, K, O, are systems. Use different variables if it helps.

Q: I know P.
P is a true statement in consistent, formal system C.
Can I prove Q is a true statement in C? (I am assuming this excludes Q from being an axiom of C.)

That depends. Is C weak enough to slip under the antecedent conditions of Goedel's theorem? Remember that there are formal systems that are both consistent and complete.

If I construct C and prove P is true in C, I know P. That is, by proving P is true in C, I am proving Q is true.

Not necessarily. All you've proved is that your name is Rachel. That demonstrates both the truth of P and the justification of P. But it doesn't prove Q, because Q is a claim to knowledge. And it is (almost?) universally acccepted that knowledge is jointly predicated on truth, justification, and belief.

Proving P gives you the first 2. It doesn't give you the last one.

I'll pause for your response.

 

[honestrosewater]

Is C weak enough to slip under the antecedent conditions of Goedel's theorem? Remember that there are formal systems that are both consistent and complete.

I am just beginning to read Gödel -for myself- for the first time (instead of relying on other's interpretations) but... C can be any consistent, formal system- so I was assuming both cases would have to be considered. Even if $C_a$ cannot prove its own consistency, can't another system in O prove $C_a$'s consistency? O contains all Cs.

Not necessarily. All you've proved is that your name is Rachel. That demonstrates both the truth of P and the justification of P. But it doesn't prove Q, because Q is a claim to knowledge. And it is (almost?) universally acccepted that knowledge is jointly predicated on truth, justification, and belief.

Yes, I was assuming belief. (x)[Prove(x) -> Believe(x) -> Know(x)]. Or however I would say that- I am just learning PC properly from the beginning, so it may not be the best time to be asking this question. But the question has been bothering and distracting me.

It seems Q would be equivalent to "This statement is true" but I can't say exactly how.
___
Actually, I should add that x needs to be true to (x)[Prove(x) -> Believe(x) -> Know(x)] I can't help but jump ahead of myself.

 

[quantumdude]

C can be any consistent, formal system- so I was assuming both cases would have to be considered. Even if $C_a$ cannot prove its own consistency, can't another system in O prove $C_a$'s consistency? O contains all Cs.

OK, it's possible that even if C is subject to Goedel that you can prove that P is true in C. It's just that if C is incomplete that it doesn't necessarily follow that you can prove an arbitrary statement in C. So let's take P to be decidable by either C or one of its supersets.

Yes, I was assuming belief.

OK, so all 3 elements are there.

It seems Q would be equivalent to "This statement is true" but I can't say exactly how.

I don't think so. The statement, "Rachel knows that P" is a comment on the truth value of P made by an external sentient agent, Rachel. That's not self-reference. Loosely speaking, self-reference occurs when a statement fixes its gaze on its own truth value. It can't make up its mind.

OK, back to your opening post.

If I construct C and prove P is true in C, I know P. That is, by proving P is true in C, I am proving Q is true.

...assuming you believe P, then OK.

Q is a true statement in formal system K. K is then consistent, right? (K is only tied to one C, there is one K for each C.)

I think that's right. If a system is inconsistent, then I believe it is possible to prove any decidable statement true (or false!) in the system, IIRC.

What is the relationship between C and K?

If this were an exam, I'd plead "not enough information".

more later...

 

[honestrosewater]

The statement, "Rachel knows that P" is a comment on the truth value of P made by an external sentient agent, Rachel. That's not self-reference. Loosely speaking, self-reference occurs when a statement fixes its gaze on its own truth value. It can't make up its mind.

But I am Rachel I is used in defining O. How is I external to O? The "I" is the whole loopy thing.
How can I prove Q if proving Q is equivalent to knowing Q? (Q: I know P) That's the limited part in my second post.
In my first post, I added that I can also know P if I observe P. So I will extend it. How can I (prove or observe) Q if (proving or observing) Q is equivalent to knowing Q?

The whole problem is that all Qs are axioms of O and all Cs are subsystems of O. Right? So how can Q not be an axiom of C? I know that's not an argument but I don't know exactly what "subsystem" means so I will go look it up.

I think that's right. If a system is inconsistent, then I believe it is possible to prove any decidable statement true (or false!) in the system, IIRC.

If O is inconsistent, and I can't prove Q in C, what does Q mean? Perhaps vacuous isn't the right word, but...

If this were an exam, I'd plead "not enough information".

Ah, but can you prove you know so to yourself?!

Edit: Okay, after an unsuccessful search, I see you said superset, not supersystem. How do you treat systems as sets? (How) Do you distinguish axioms from theorems? Or do you just lump them together as statements?

 

[quantumdude]

Before I respond (which probably won't be today), could you answer a question about this bit?

But I am Rachel I is used in defining O. How is I external to O? The "I" is the whole loopy thing.

Yes, I know that you are Rachel. I still don't see why you believe self-reference enters into your propositions within this reasoning process, unless your answer to the following question is "yes":

Is it your position that the proposition "I know that my name is Rachel" is self-referential because you are referring to your own name?

 

[honestrosewater]

Is it your position that the proposition "I know that my name is Rachel" is self-referential because you are referring to your own name?

No. I used P: "My name is Rachel" because I already know P is true by definition in O. And I can't go "outside" of O. The "I prove" and "I know" parts confuse me.

 

[honestrosewater]

If you think it would be better for me to just wait until I can better formulate the question, I would certainly understand.

 

[Canute]

Honestrosewater

I'm no mathematician so be wary of what I say here, but this is how I see it.

Your question makes a whole bundle of assumptions which are difficult to unpick, so I'll generalise.

First, it is dangerous to use the term 'know' in respect of true and false statements. It is possible to prove that a statement is true or false within some formal system of symbols, but this is in no sense equivalent to 'knowing' that the statement is true of false. This is why scientific theories are taken to be about prediction and utility, not about what is true. Unless one is using a formal system so simple that it evades the incompleteness theorem then it is not possible to know whether the truths and falsities provable within the system are really true and false.

'Consistent' is also tricky. In your illustration you said that formal system C is consistent. If it is consistent then it is incomplete. If it is incomplete you cannot know that it is consistent. You can only know that it is consistent so far. In fact, assuming that system C is subject to the incompleteness theorem, then we know for certain that the only way to complete it is to accept at least one contradiction in it, one statement that cannot be decided because both its truth and falsity entail a contradiction. So a formal system is either provably inconsistent now, or predictably inconsistent later.

Looking at it another way the problem is that a statement that is provable within one formal system is falsifiable in another differently axiomatised system. So how do we know which is the best set of axioms from which to derive our proof (say, of 'I am called Rachel')? What the incompleteness theorem says is that it is not possible to know if any given set of axioms is self-consistent, and therefore it is not possible to construct a formal and demonstrable proof of any statement at all. (Unless it is 'meta-systematic', like Godel's theorem).

This means that all bets are off when it comes to 'knowing' the truth or falsity of any meaningful statement by formal reasoning or calculation. It just cannot be done. Ones axioms may always be faulty.

In a strong sense G showed that certain knowledge is unnattainable by means of any system of proofs and disproofs. Meta-mathematically speaking all questions are undecidable, not just those that are undecidable within some particular system. Another way of putting it is that all formally proved truths and falsities are only relatively true or false (relative to the axioms, which may be inconsistent).

Thus true knowledge is not the sort of knowledge that can be gained by manipulation of symbols according to the usual rules of logic (excluded middle, non-contradiction and so on) within a formal and consistent system of theorems or statements.

'My name is Rachel', although it seems to be something you can prove to be true, is in fact falsifiable given a different set of axioms from which to derive its truth-value. For instance, a person in a mental institution might claim to be able to prove 'My name is Napoleon', and perhaps, given their axioms, they can. Perhaps you are delusional, and your name is actually Doris.

Worse than this, you'll find that you cannot even prove that you think your name is not Doris, and in the end you cannot even prove that you think. In an absolute sense it is impossible to prove anything at all. The thing is, when we 'prove' a statement within a formal system we are not really proving anything, we are demonstrating that the truth or falsity of the statement can be derived from the axioms of the system.

Because all formally demonstrable truths and falsities can be quite easily refuted within some differently axiomatised system, and because we cannot know which is the most 'true' set of axioms, we know that any statement that we can prove to be true might be false, and that the only absolutely true statetements we might make will be those that are tautologies, those for which we cannot demonstrate their truth or falsity, or those that are predicated on a contradiction.

As Lao-Tsu said, true words are paradoxical. Or in Aristotle's words 'True knowledge is identical with its object', i.e. cannot be systematically derived from axioms within some formal systems of symbols and rules.

Aristotle's argument was that any attempt to prove ones axioms leads to an infinite regress of axioms. This can only be terminated by taking some number of axioms as self-evident'. Thinking of the title you gave your question, what is self-evident is precisely and exactly what can never be formally proved.

I'm hoping Tom will go along with this, but it's terrifyingly easy to make mistakes on this topic.

 

[honestrosewater]

First, it is dangerous to use the term 'know' in respect of true and false statements. It is possible to prove that a statement is true or false within some formal system of symbols, but this is in no sense equivalent to 'knowing' that the statement is true of false.

Yes, I know, er, I agree. That's why Q: I know P is true in consistent, formal system C. I am explicitly referencing the system in which P is true.
I'm defining knowledge as justified true belief. P is true in C (true) + I proved P is true in C (justification) + If I prove P, I believe P (belief) = I know P. That isn't a formal formulatiion, but just call it my knowledge axiom; It's an axiom of O.

'Consistent' is also tricky. In your illustration you said that formal system C is consistent. If it is consistent then it is incomplete. If it is incomplete you cannot know that it is consistent.

https://www.physicsforums.com/showpost.php?p=385658&postcount=19 IIRC, Gödel's second incompleteness theorem says something similar what Canute said. I'm less familiar with this one, and always have a hard time digging up references on this one, but I think it says that, given the same assumptions used for the first incompleteness theorem, the theory cannot both be consistent and prove itself consistent.

Of course, this says nothing about relative consistency: it's simple enough, for instance, to use ZFC to prove number theory consistent.

I should be able to prove at least some C in O are (relatively) consistent by using other C in O. No?

In fact, assuming that system C is subject to the incompleteness theorem, then we know for certain that the only way to complete it is to accept at least one contradiction in it, one statement that cannot be decided because both its truth and falsity entail a contradiction.

I've never heard that before. A system can be made complete by an undecidabe statement? Is that what you said? Can you explain?

Looking at it another way the problem is that a statement that is provable within one formal system is falsifiable in another differently axiomatised system. So how do we know which is the best set of axioms from which to derive our proof (say, of 'I am called Rachel')? What the incompleteness theorem says is that it is not possible to know if any given set of axioms is self-consistent, and therefore it is not possible to construct a formal and demonstrable proof of any statement at all. (Unless it is 'meta-systematic', like Godel's theorem).

And Q is true in every C. No? I'm speaking of P generally- forgetting the my name is Rachel example. P is just a theorem of C- that's all. Now, my knowledge axiom is in O, and O contains all Cs. Perhaps it's confusing becuase I'm speaking of Ps, Qs, and Cs individually and collectively. Fine. If I prove $P_a$ is a theorem of $C_a$ then $Q_a$ is also true in $C_a$. But is $Q_a$ a theorem or an axiom of $C_a$? Remembering that my knowledge axiom is in O and $C_a$ is a subset of O. My knowledge axiom makes Q true in all Cs. No? Ugh. I may not be making any sense to you.

Another way of putting it is that all formally proved truths and falsities are only relatively true or false (relative to the axioms, which may be inconsistent).

Fine, I just want to know if $Q_a$ can be a theorem of $C_a$. In other words, can I prove I know something if my knowledge of that thing is justified solely by my proving it is true in a consistent, formal system? Or must I just take that knowledge as necessarily self-evident (i.e. unprovable)?

Thus true knowledge is not the sort of knowledge that can be gained by manipulation of symbols according to the usual rules of logic (excluded middle, non-contradiction and so on) within a formal and consistent system of theorems or statements.

In other words, the answer to my last question is yes?

'My name is Rachel', although it seems to be something you can prove to be true, is in fact falsifiable given a different set of axioms from which to derive its truth-value.

Right, that's not what I'm asking. (I think.) I just want to know if I can use $C_a$ to prove $Q_a$.

As Lao-Tsu said, true words are paradoxical. Or in Aristotle's words 'True knowledge is identical with its object', i.e. cannot be systematically derived from axioms within some formal systems of symbols and rules.

This is exactly the motivation for my question. I cannot use my knowledge to formally prove my knowledge- that is where the self-referencing comes in. But I only have a weak grasp on this concept so far. I'm trying to strengthen that grasp by asking these questions.

Aristotle's argument was that any attempt to prove ones axioms leads to an infinite regress of axioms. This can only be terminated by taking some number of axioms as self-evident'. Thinking of the title you gave your question, what is self-evident is precisely and exactly what can never be formally proved.

Yes, and how does that apply to my knowledge? That's exactly what I want to know. I cannot formally prove I know anything. Right? The only "form" of proof is observation, experience, whatever you want to call "being"! Right? / I'm so close to and so far from understanding this. I don't know what I'm missing.

I'm hoping Tom will go along with this, but it's terrifyingly easy to make mistakes on this topic.

Yeah, tell me about it.

 

[honestrosewater]

Just to clarify- I'm saying that I can know P, but I cannot formally prove I know P. I know P by virtue of my knowledge axiom. And if I want my knowledge axiom to be fundamental (i.e. I want it to be in O) then I cannot prove my knowledge axiom is true- it's a fundamental axiom. Of course, I cannot prove it is false either. My knowledge axiom is formally unprovable. Similar to cogito, ergo sum.

 

[Canute]

Just to clarify- I'm saying that I can know P, but I cannot formally prove I know P. I know P by virtue of my knowledge axiom. And if I want my knowledge axiom to be fundamental (i.e. I want it to be in O) then I cannot prove my knowledge axiom is true- it's a fundamental axiom. Of course, I cannot prove it is false either. My knowledge axiom is formally unprovable. Similar to cogito, ergo sum.

I feel that you're making the question harder than it really is. But this could be me, I still can't quite grasp what you are asking. Perhaps the reason is that you are using the term 'prove' to mean 'demonstrate'. It is perfectly possibly to prove cogito, it couldn't be easier. But you cannot demonstrate a proof of it. If you could then cogito ergo sum wouldn't be an axiom, it would a true or false statement derived from an axiom. Ironically, if we could derive the truth of cogito from some other axiom then we would not be able to know for certain that it is true.

'I know P by virtue of my knowledge axiom' seems something of a contradiction. It is possible to derive relative proofs from axioms, but it is not possible to know whether that proof is certain. This is because an axiom is by definition uncertain. An axiom is an assumption. If it were not an assumption then it would have to be derivable from an axiom, and therefore would not be an axiom. So you cannot know anything at all with certainty by deriving theorems from axioms, for if knowledge is uncertain then philosophically speaking it would be incorrect to say that you know it.

If an axiom is self-evident like cogito, (well, without getting picky), then it is not true or false within the system. It is just what is self-evidently the case, with or without the system. Formal systems arise from their axioms, they do not exist prior to the formulation of their axioms, and so axioms are not really in the system at all. This is why it is impossible to demonstrate the truth of a system's axioms from within the system. To do that, you need another system, and so on ad infinitum.

Sorry, I'm losing the plot. Could you restate your question more simply, without elaborating it so much? The problem is that the question as you present it embodies a number of assumptions that make it very difficult to address.

One more go - if a statement can be proved true or false by demonstration then it cannot be known to be true or false with certainty. If a statement is known to be true or false with certainty then its truth or falsity cannot be demonstrated systematically. This is because certain knowledge is that which is self-evident, and if it is self-evident all we can do is take it as axiomatic, and then we cannot derive its truth or falsity from our axiom, because it is our axiom. Argh... Perhaps I should shut up and let someone who can do clarity have a go.

To come at it from another angle. If something is the case then it is the case regardless of what human beings do or how they think, or how they prove and disprove things. If a statement is demonstrably true within a formal system then we know that it is demonstrably falsifiable within a different system. But it makes no sense to say that what is the case is the case in some systems but not in others.

So statements (what those statements assert) that can be proved to be true or false may or may not be the case, and we cannot ever demonstate completely which they are. However, if we can, through direct experience, reach a point where what is the case is self-evident to us, then we can know it, even though we can never systematically prove it.

One thing I do know for certain, self-reference is a nightmare to discuss.

 

[Hurkyl]

Frankly, I'm confused, so I'll just say something and hope it's useful!


From any consistent, incomplete system, one can, in principle, extend it (in many different ways) to a consistent, complete system. The general method is:

Start with the original axioms.

For every possible logical statement:
- If the statement is undecidable WRT your current set of axioms, add this statement to your set.


(exercise: prove that the resulting set of axioms is both complete and consistent)


It is often overlooked that a theory can be too strong for Gödel's arguments to work -- he assumes it has finitely many axioms.

 

[honestrosewater]

What does WRT mean? Edit: With Regard/Respect To?

Do the following mean the same thing?
The statement "the statement S is true in formal system F" is true in formal system F.
$S \wedge S$.

 

[Hurkyl]

The statement "the statement S is true in formal system F" is true in formal system F.

Generally speaking, a formal system cannot speak of "truth" within itself -- you run into the Liar's paradox fairly quickly.

 

[honestrosewater]

Generally speaking, a formal system cannot speak of "truth" within itself -- you run into the Liar's paradox fairly quickly.

How do the following statements strike you, even just the general meaning of them?
I know the statement "I know the statement S is true in formal system F" is true in formal system F.
I know "I know my name is Hurkyl".
I know "I know my name is Hurkyl is true" is true.
"'Hurkyl is my name' is known" is known.
"'Hurkyl is my name' is known by me" is known by me.

Does it seem like I'm just adding "and S and S and S..." or is something else going on?

 

[honestrosewater]

I happened to stumble across this article (http://psyche.cs.monash.edu.au/v2/psyche-2-04-mccullough.html) while looking for something else. I have only read it once and don't quite yet understand some terms, but it sounds similar to what I have been trying to ask. Here's another article on the same topic and a little excerpt:

http://jamaica.u.arizona.edu/~chalmers/papers/penrose.html
(1) Assume my reasoning powers are captured by some formal system F (to put this more briefly, "I am F"). Consider the class of statements I can know to be true, given this assumption.

(2) Given that I know that I am F, I know that F is sound (as I know that I am sound). Indeed, I know that the larger system F' is sound, where F' is F supplemented by the further assumption "I am F". (Supplementing a sound system with a true statement yields a sound system.)

(3) So I know that G(F') is true, where this is the Gödel sentence of the system F'.

(4) But F' could not see that G(F') is true (by Gödel's theorem).

(5) By assumption, however, I am now effectively equivalent to F'. After all, I am F supplemented by the knowledge that I am F.

(6) This is a contradiction, so the initial assumption must be false, and F must not have captured my powers of reasoning after all.

(7) The conclusion generalizes: my reasoning powers cannot be captured by any formal system.

Both of these and more can be found at http://jamaica.u.arizona.edu/~chalmers/online2.html#godel , under the heading "Gödel's theorem and AI". I'm still reading and absorbing- and cautiously optimistic.
BTW How can I put html links (anchors) in my posts so I don't have to clutter them up with urls?

Edit: Yes! See Penrose's Second Argument in Chalmer's article (the one quoted). This is exactly what I'm saying. Hallelujah! How does he make it so clear? Sorry, I'm just so happy and tired I can't even think.
See, O was my larger system, C was the smaller, and I was trying to say that C was referencing O in proving Q- but I couldn't figure out how because I was going at it backwards and my knowledge axiom I think was soundness. Well, whatever, whether anyone believes me or not, I'm just glad it's finally clear.
And thanks loseyourname!

 

[Philocrat]

A theory is incomplete only when the means by which it is devised is also incomplete, both in structure and in function. The most reliable means of completing a theory is to first complete the means by which it is derived. So, when a theory fails to complete, look at the means!

 

[loseyourname]

BTW How can I put html links (anchors) in my posts so I don't have to clutter them up with urls?

I'm not sure you can use HTML in a post (it depends on if the admin enables it or not for vbulletin), but you can use the URL tags. Like this. Just quote my post to see how it looks.

 

[phoenixthoth]

I think you'd be interested in "Strange Loops".

http://en.wikipedia.org/wiki/Strange_loop

http://mathworld.wolfram.com/StrangeLoop.html

Maybe someone can produce more meaty links?

If a mathematician will accept this as a proof/statement:

since x^2 >= 0 for all real x, the intersection of the domain of sqrt(x) and R is {x:x>=0},

then why won't a mathematician accept this as a proof/statement:

This statement is false?

In other words, why the need to go to formal machine-like language to come up with a self-referential statement which is also, I believe, known as a strange loop?

 

[honestrosewater]

I think you'd be interested in "Strange Loops".

Yes, I'm reading GEB now.