Cardinality of Theorems vs True Sentences in a Theory

[WWGD]

TL;DR Summary

Given a Structure , is the Set of True Sentences (which I think is called the full theory generated by the Structure) with, say, countable symbols. Is there always a bijection between the true sentences (Semantic ) vs the Theorems (Syntactic)?

Given a Structure , is the Set of True Sentences (which I think is called the full theory generated by the Structure) with, say, countable symbols. Is there always a bijection between the true sentences (Semantic ) vs the Theorems (Syntactic)? I believe this depends on the existence of a model, which itself depends on the consistency of the theory. Sorry, I am a bit rusty with these concepts I last saw some 10 years back . Is it reasonable to assume/define the theory as the maximally-consistent set of wffs? If so, by one of Godel's theorems, a model will exist. If there are finitely-many symbols in our language, there are countably-infinitely many wffs. Then these will be mapped into truths in the/a model. Am I on the right track here? Just need a little push before getting into re-reading the definitions more carefully.

 

[SSequence]

Note: My understanding isn't quite incomplete since either (i) Formally I haven't learned a lot of this stuff (e.g. including any kind of meta-logic theorems or model theory). (ii) Even if I have, I don't have enough (technical) facility with it [or understanding of the nuances ... and in set and model theory there just seem too many of them]. Nevertheless, I have seen some of these things [mostly while skimming to make some sense of it] so many times that I have "some" intuition about it.

Is there always a bijection between the true sentences (Semantic ) vs the Theorems (Syntactic)?

I don't quite get it. Why would there be? For example, for an incomplete theory (where first incompleteness theorem applies) won't the "theorems" be a strict subset of "true sentences" (assuming PA I am thinking of N as a model)?

Also, I guess the "Godel's theorem" you are referring to is completeness theorem? I haven't really studied/encountered it formally, but what it seems to say (based on what I have read) is:
"For a consistent theory, a theorem (statements derived via logical inference) is true in every model"

Here is how I make some sense of it. The theorems [the statements "proved" via logical inference] of set-theory would be true in every model of it [a similar remark, I think, should hold for both standard and non-standard model of PA]. But because, for example, CH and GCH aren't theorems (actually, even their negations) of set-theory [assuming con(set-theory)] we can't assume that they would be true in every model. But that also doesn't mean that there can't be a model where they aren't true. For example, famously, Godel constructed a model where both CH and GCH are true (which wouldn't be possible if ~CH and ~GCH were set-theory theorems).P.S.
Also, the "meta-theory" (which I take to mean roughly as "background assumptions") for "model theory" is ZFC. So much of theorems of model theory can be proved in ZFC. At least, that's what I have read. I don't know this well myself. And that's sort of why ZFC doesn't prove it has a model [and because every consistent theory has a model, such a proof would violate second incompleteness theorem].

 

[Klystron]

{snip...} [or understanding of the nuisances ... and in set and model theory there just seem too many of them]. {...snip. Bold added.}

Interesting reply. Did you mean to type 'nuances'; meaning subtle distinctions?

The term 'nuisances'; i.e., minor problems; certainly applies to set theory. Thanks.

 

[SSequence]

Interesting reply. Did you mean to type 'nuances'; meaning subtle distinctions?

Yes, I used the wrong word. I will edit accordingly.

 

[yossell]

Given a Structure , is the Set of True Sentences (which I think is called the full theory generated by the Structure) with, say, countable symbols. Is there always a bijection between the true sentences (Semantic ) vs the Theorems (Syntactic)?

For a theory with countably many symbols, the set of sentences true in a model has a countable cardinality. For all reasonable axiom systems, there will be countably many theorems. In that sense, there will be a bijection between the truths and the theorems.

However, you might have meant to ask whether, for any Set of True sentences (of a countable language ), there is an axiom system which has precisely those sentences as theorems. As Ssequence says, the answer is no, by Godel's incompleteness theorem.

One point where I diverge with Ssequence -- Godel's completeness theorem (as opposed to his incompleteness theorem) tells us that our underlying logic is complete -- if A is a semantic consequence of T, then our underlying logic is such that A can be proved from T.

I believe this depends on the existence of a model, which itself depends on the consistency of the theory.

Unsure what you mean -- I'm assuming that, by 'structure' you meant 'model.' And I had understood 'the set of true sentences' to be the set of truths in a given structure. In this sense, the existence of 'the set of true sentences' assumes the existence of a model.

Sorry, I am a bit rusty with these concepts I last saw some 10 years back . Is it reasonable to assume/define the theory as the maximally-consistent set of wffs?

Which theory? You would need to say more about *which* set of maximally consistent set of wffs before you could be said to have defined a theory. But, say, the set of sentences true in the standard model of Peano Arithemetic is regarded as a reasonable way of presenting a theory. And the set of sentences true in a model will be maximal and consistent. But there are other ways of presenting a maximally consistent set which do not refer to a model.

If so, by one of Godel's theorems, a model will exist.

Correct -- it's the completeness theorem again. But if you're defining your maximally consistent set by reference to a model in the first place, then there's no need for the theorem.

If there are finitely-many symbols in our language, there are countably-infinitely many wffs.

Yes.

Then these will be mapped into truths in the/a model.

I don't understand this. What do you take to be Mapped onto what? Truths onto theorems? I find it odd to put it this way: the sentences are the same in the two cases; insofar as there's a mapping, it's just the identity mapping. The question is really whether the set of truths is identical to the set of theorems -- not whether there are mappings between them.

 

[SSequence]

The question is really whether the set of truths is identical to the set of theorems -- not whether there are mappings between them.

I agree that this is a fundamental question. One thing that I might highlight briefly is that even before this question one can ask a question which could be a considered a precursor to it: "what counts as a 'meaningful' question?"

For example, (nearly) everyone would agree that the questions of PA count as "meaningful questions". Set-theorists would say that something like CH is a meaningful question (same can be said for many other questions that can be posed within it). Some one who isn't willing to fully commit might disagree.

But anyway, this isn't quite relevant to OP.

Coming back to:

The question is really whether the set of truths is identical to the set of theorems -- not whether there are mappings between them.

Another way I see it is to see things in terms of being able to generate more and more sets (especially ones that are subset of $\mathbb{N}$). Even if some theory isn't sound (but consistent nevertheless), what if it helps to generate us more such sets? This becomes even more compelling if there is no known concrete instance against soundness (where at least most people would agree). It seems a tricky issue to me.

==================

Informally, to the extent that I have been able to understand there are two kinds of 'ambiguities' (if one wants to call it that) in set theory:
(i) How far can you go?
(ii) How many sets are produced (as you proceed).

To some extent constructibility (it seems to me) helps to give a clearer picture of of (ii) by restricting the universe somewhat (relevant picture that I find helpful: https://www.iep.utm.edu/wp-content/media/SetTheory4.png).

Anyway, since the thread was bumped, here is quite a nice picture which helped me to understand how the notion of uncountable isn't absolute. This is also closely related to theorem point(i) above [and I think(?) also to lowenheim-skolem]. [the function $f$ which generates the well-order for $\omega^M_1$ isn't part of $M$ ... that's why $M$ can satisfy all the axioms without creating a paradox]:
https://usamo.files.wordpress.com/2015/12/countable-transitive-model.png

 

[yossell]

I agree that this is a fundamental question. One thing that I might highlight briefly is that even before this question one can ask a question which could be a considered a precursor to it: "what counts as a 'meaningful' question?"

In the context of the original proof, I was taking 'the set of truths' to be a reasonably well defined mathematical question. E.g., 'the set of all the truths in the standard model of Peano Arithmetic'; 'the set of truths across all models of Peano Arithmetic.' I hesitate to use the phrase without some such implicit clauses in play because I'm not sure what 'the set of all truths' simpliciter is supposed to ref to.

Another way I see it is to see things in terms of being able to generate more and more sets (especially ones that are subset of $\mathbb{N}$. Even if some theory isn't sound (but consistent nevertheless), what if it helps to generate us more such sets? This becomes even more compelling if there is no known concrete instance against soundness (where at least most people would agree). It seems a tricky issue to me.

This is interesting -- I comment just because this could confuse the OP. I think it helps in logic to think of theories as sets of sentences, and then to treat certain logical questions as questions about the properties of certain sets of sentences. The program you've got in mind sounds something like the large cardinal program -- where, by adding large cardinal axioms to ZFC, we generate a theory which (first order) implies the existence of subsets of of N that are not (first order) implied by ZFC alone.

I suppose I could imagine someone rejecting the truth of set-theory plus large cardinals, while believing that the extra subsets of N extensions of set-theory imply to exist are genuine subsets of N. For instance, you might accept peano arithmetic formulated in second order terms -- so that the induction axiom ranges genuinely over ALL the subsets of N -- while thinking set-theory and all its infinities is beyond the pale.

 

[SSequence]

The program you've got in mind sounds something like the large cardinal program -- where, by adding large cardinal axioms to ZFC, we generate a theory which (first order) implies the existence of subsets of of N that are not (first order) implied by ZFC alone.

I suppose I could imagine someone rejecting the truth of set-theory plus large cardinals, while believing that the extra subsets of N extensions of set-theory imply to exist are genuine subsets of N. For instance, you might accept peano arithmetic formulated in second order terms -- so that the induction axiom ranges genuinely over ALL the subsets of N -- while thinking set-theory and all its infinities is beyond the pale.

About the second paragraph, I don't have nearly enough of background to comment on this.

Let me try to explain this view by using number of (idealized/simplified) examples so that the main point is across:
(1) "Suppose" (just for sake of argument) that set-theory proves some goldbach-type statement to be false when it is "actually true". If one actually finds that out then what do we do about all the subsets of N that it says exist? At some level at least, we can still say we have a relation to many of those sets in a concrete way, since can we concretely enumerate infinitely many elements of these sets [without appealing to a platonic realm or anything of that sort etc.], and not only that we can continue to do so.

(2) At some level this phenomenon doesn't even require set-theory specifically. The set of all truths of number-theory, we can enumerate infinitely many elements from this set [and continue to do so] without making any commitment about truth of PA theorems. Probably PA is a bad example [what I mean is some theory which poses the same questions that PA does and is clearly unsound+consistent].

EDIT: I have thought about it some more and it seems there is at least one quite basic observation one can make in case of (2). Purely for the sake of supposition, if one believes that there is a false theorem then when enumerating the set above one certainly wouldn't want to trust the theorems as (incompletely) enumerating the set correctly.

The situation seems to be much more complicated in (1) though. I don't have any clear picture of it. Though, a similar observation about the same set would hold.

My feeling [def. quite unclear] about it is that this is related to differences between two things: (a) Agreeing that a certain subcollection of N is well-posed (b) Disagreement over what would be the "correct" method to (incompletely) enumerate the elements. END

EDIT2: My understanding is that (generally) mathematicians tend to go for maximalist position [that would be the default unless, presumably, a clearly unsound conclusion emerges at some point (if it does in the first place)]. END

=============================

An analogue of above:

As I understand (based on what I have read/seen people say), the existence of large cardinals implies
results that are falsifiable (via trivial computation) ... meaning that assuming that they are inconsistent, they can be refuted just by trivial computation. I don't have enough knowledge to know whether this is true in all cases.

Taking what you said about these cardinals implying more subsets of N (that wouldn't just exist in normal set-theory) as existing [I don't know nearly enough to know whether that is true or not] an interesting hypothetical scenario would be existence of such a cardinal implying a simple number-theory statement that is "clearly false" (for example) but the falsity doesn't necessarily mean that its inconsistent. So then one question would be what that subset of N it implies exists "really means"?

Sorry I have been fairly incoherent in the last two paragraphs I think (but hopefully it makes some kind of sense as to what I am trying to say). Anyway, what I wrote before that should probably be clearer.

=============================

P.S.
At any rate, I think I should add that the specific point in this post is related to discussion of a (difficult to put it lightly) philosophical question on which there is significant disagreement (even among experts).

Technically understanding the logic related topics doesn't seem to be related to it. I find the technical understanding much harder to obtain than just identifying these kind of points.