But to say that arithmetic can be reduced to logic requires showing, for example, the derivation of the axioms of PA from only logical axioms. And that ain't gonna happen. — TonesInDeepFreeze

You don't need the axioms of PA to carry out arithmetic. It will work perfectly fine without. You just won't have a theory about it.

Of course we don't need any axioms to do a whole bunch of arithmetic. But just doing a bunch of arithmetical computations is not, in the context of mathematical logic or philosophy of mathematics, what people ordinarily mean by reducing arithmetic to logic.

Given a particular countable language and meta-theory with a countable alphabet:

This is correct:

Given a countable set of symbols, there are exactly denumerably many finite sequences of symbols, thus exactly denumerably many sentences.

There are uncountably many subsets of the set of sentences. And any set of sentences can be a set of axioms. Therefore, there are uncountably many theories. But there are only countably many ways to state a theory, so there are theories that are not stable. — TonesInDeepFreeze

I considered that argument, that there might be uncountably many theories (interpretations) but I don't think it's correct. An interpretation must have finite length, yes? There are only countably many FINITE subsets of a countable set.

I'm pretty sure this is correct:

There are exactly denumerably many algorithms. And for every formal theory and set of axioms for that theory, there is an algorithm for whether a sentence is an axiom. So there are only countably many formal theories. — TonesInDeepFreeze

That's what I believe is true. Only countably many interpretations of each sentence. So the poster (sorry I didn't look back to find out who) who said natural language could be uncountable, is wrong. IMO anyway.

Given a language for a theory, trivially, there are uncountably many interpretations for the language, since any non-empty set can be the universe for an interpretation, and there are not just countably many sets. But there are only countably many ways to state an interpretation, so there are interpretations that are not statable. — TonesInDeepFreeze

I'd have to give that more thought.

Given any theory, there are uncountably many models of the theory, since there are uncountably many isomorphic models of the theory. But there are only countably many ways to state a model, so there are models that are not statable. — TonesInDeepFreeze

I don't know. Not knowledgeable about model theory.

No disagreement here, and I agree it's a side issue.

Practically speaking, the sum total of all natural language that has ever or will ever be spoken/thought/etc. in the visible universe is finite anyhow. There are in fact, far stricter physical limits on how many truths could ever actually be expressed, which seems more relevant to the OP. If you could make every proton in the visible universe represent an entire sentence that only gets you to 10^80 or so sentences, a very far cry from an infinite number of truths.

there might be uncountably many theories (interpretations) — fishfry

No, theories and interpretations are different things. But, yes, I did give reasoning by which there are uncountably many theories and uncountably many interpretations for even just one language.

I'm pretty sure this is correct:

There are exactly denumerably many algorithms. And for every formal theory and set of axioms for that theory, there is an algorithm for whether a sentence is an axiom. So there are only countably many formal theories.
— TonesInDeepFreeze

That's what I believe is true. Only countably many interpretations of each sentence. — fishfry

I didn't say that there are only countably many interpretations of a given sentence. Indeed, there are uncountably many interpretations, as I explained.

natural language could be uncountable, is wrong — fishfry

There are only countably many expressions. But there are uncountably many interpretations even of just one sentence.

I only give up when it talks about the models of ZFC — Tarskian

Set theory says what is the requirement for being a model for set theory is. But set theory (if it is consistent) does not claim that there is model that meets that requirement. And set theory proves that if set theory is consistent if and only if set theory has model. Also, set theory talks about inner models, which a figure of speech for relativization, which also is not problematic.

At that point, it is no longer capable of cleanly separating provability and truth: "How can a model of ZFC be a set, if we want to use ZFC to study sets?" — Tarskian

ZFC is a set of sentences. Any consistent set of sentences has models, and the universe of a model is a non-empty set. There is no incapability of distinguishing the definitions of 'provable in a theory' from 'true in a model'.

the theory is essentially its own model. — Tarskian

That is nonsense. Theories are not models and models are not theories.

Theories are not models and models are not theories. — TonesInDeepFreeze

The math exchange answer says something quite confusing in that regard:

To study "models", we need to work in a metatheory that already has some concept of set or collection. The "metatheory" here is the theory that we use, as a tool, to study the object theory. There are many options for such a metatheory. One option would be ZFC itself.

A model is not a metatheory, but "we need to work in" one "to study the model". So, as one of the options, we could "work in" ZFC itself to study its models.

I don't say that it is wrong. I just say that it is highly confusing.

I find that quote quite understandable, quite clear and not confusing.

In a meta-theory we define 'is a model' and we talk about models for languages for a theory, and we talk about models of theories.

In a meta-theory we define 'is a model' and we talk about models for languages for a theory, and we talk about models of theories. — TonesInDeepFreeze

Indeed, it looks indeed like it doesn't matter that ZFC is its own model metatheory. For example, with ZFC being PA's model metatheory, Löwenheim–Skolem theorem does not seem to be particularly PA-specific:

It implies that if a countable first-order theory has an infinite model, then for every infinite cardinal number κ it has a model of size κ, and that no first-order theory with an infinite model can have a unique model up to isomorphism.

It does not seem to matter for which object theory the cardinals κ are being considered.

The following math exchange answer suggests that explicitly mentioning the model's metatheory is not even a requirement:

https://math.stackexchange.com/questions/531516/meta-theory-when-studying-set-theory

Meta Theory when studying Set Theory

There are generally two accepted approaches:

(1) You can use some arithmetical theory, e.g. PA, or even a fragment which is sufficient to develop first-order logic and syntactic manipulation of proofs. Then one can define the language of set theory, write the axioms and proofs and so on. In fact Con(ZFC) is in fact a statement about natural numbers rather than a statement about sets and models.

This is even true if one wants to introduce forcing. And I ran into a recent masters thesis in which this (usually folklore, I believe?) result is given in details.

(2) You can use ZFC itself. Then you have some universe of set theory (usually ZFC+Con(ZFC) and even more), but you are in fact working inside a set model of set theory within that universe. In that case you are free to use all sort of fun model theoretical tools, and forcing is done directly and so on.

(3) However in many many instances we in fact omit the meta theory, and we just care about it sufficient to develop first-order logic. We often work within the universe. So there is no real model of set theory, there is a universe and we work with that. We can do forcing using the universe because we can define Boolean-valued models and prove independence results using that, and so on.

No, as I said, Cantor did not make that reductio assumption. Again:

Let g be an arbitrary list of denumerable binary sequences. (We do NOT need to ASSUME that this is a list of ALL the denumerable binary sequences). Then we show that g is not a list of all the denumerable binary sequences. — TonesInDeepFreeze

Well, in my example (which is common), I was referring to reals between 0 an 1, not ALL reals.

I think that we aren't understanding each other here:

If you say " Then we show that g is not a list of all the denumerable binary sequences." Isn't then that g is not in the list of all these sequences exactly constructed by diagonalization? And here the negative self-reference is that g is not on this list, the list of (in your version) all the denumerable binary sequences.

Turing constructed a quite important and remarkable proof for the uncomputability of the Entscheidungsproblem. But is that constructiveness a problem? — ssu

Church is the one who addressed the Entscheidungsproblem. Turing proved the unsolvability of the halting problem. — TonesInDeepFreeze

Not quite, even if it's great that someone remembers Church's role (although he is remembered by us referring to Church-Turing thesis). Alan Turing's paper is called "ON COMPUTABLE NUMBERS, WITH AN APPLICATION TO THE ENTSCHEIDUNGSPROBLEM".

Where Turing states:

Although the class of computable numbers is so great, and in many
ways similar to the class of real numbers, it is nevertheless enumerable.
In §8 I examine certain arguments which would seem to prove the contrary.
By the correct application of one of these arguments, conclusions are
reached which are superficially similar to those of Gödel. These results
have valuable applications. In particular, it is shown (§11) that the
Hilbertian Entscheidungsproblem can have no solution.

It's Turings paper itself where we get "the halting problem" of a Turing Machine (in the paper referred to a machine. The name "Turing Machine" was given by his teacher, Alonzo Church).

OP is another crank (like PL) hiding behind fancy mathematical and logical language to push his nonsense, this time the nonsense being religious proselytising, as can be seen from his other posts.

Arithmetic can be reduced entirely to logic. However, logic can also be entirely reduced to arithmetic — Tarskian

Translation does not mean you did not need to understand logic first to discover math. I don't mean formal annotated logic, I mean 'logical thinking'.

Translation does not mean you did not need to understand logic first to discover math. I don't mean formal annotated logic, I mean 'logical thinking'. — Philosophim

I also believe that a good measure of logical thinking is built into our biological firmware, but so is quite a bit of arithmetic:

https://www.quantamagazine.org/animals-can-count-and-use-zero-how-far-does-their-number-sense-go-20210809/

Now, researchers are uncovering increasingly more complex numerical abilities in their animal subjects. Many species have displayed a capacity for abstraction that extends to performing simple arithmetic, while a select few have even demonstrated a grasp of the quantitative concept of “zero” — an idea so paradoxical that very young children sometimes struggle with it. In fact, experiments have shown that both monkeys and honeybees know how to treat zero as a numerosity, placing it on a mental number line much as they would numerosity one or two. And in a paper published in the Journal of Neuroscience in June, researchers reported that crows can do it, too.

I think that we were born with it and that we can do quite a bit of it out of the box.

I also believe that a good measure of logical thinking is built into our biological firmware, but so is quite a bit of arithmetic: — Tarskian

Oh, no debate there. I'm just noting that to express the formal logic of arithmetic, you have to logically ascertain what '1' is as an abstract. What '+' means as an abstract. What '=' means as an abstract. You can't use math to prove math, because you must first invent the symbols and meanings that math is based off of.

This seems like a side track off of the larger conversation at this point however.

I don't say that it is wrong. I just say that it is highly confusing. — Tarskian

Math is confusing. It's far more closer to philosophy than mathematicians and logicians want to admit.

For example, I've followed Chaitin's story and his efforts with the Omegan number and AIT, on and off for now about 20 years and seen how he has been gotten even ad hominem attacks (actually from my own university, from where I graduated). Only now it seems that Gregory Chaitin is getting respect.

OP is another crank (like PL) hiding behind fancy mathematical and logical language to push his nonsense, this time the nonsense being religious proselytising, as can be seen from his other posts. — Lionino

I wouldn't go for ad hominems, but for me this thread is informative. So hopefully nobody is banned and the tempers don't rise too much.

I myself follow the rule that if two or more PF members saying you are wrong (not just that they oppose you view in some way) with nobody agreeing with you, then you might really look sincerely where this error would lies.

I was referring to reals between 0 an 1, not ALL reals — ssu

It doesn't matter whether we're proving that there is no list of all the reals, or no list of all the reals between 0 and 1, or (as in Cantor's proof) no list of all the denumerable binary sequences.

The point is that we don't need to assume for a reductio (and Cantor did not do that).

If it's about reals between 0 and 1, then let g be any list of reals between 0 and 1 (we don't need to assume for a reductio that it is a list of all reals between 0 and 1). Then we construct a real between 0 and 1 that is not listed.

Isn't then that g is not in the list of all these sequences exactly constructed by diagonalization? — ssu

g is not in the list since g is not a real between 0 and 1. Rather, we construct a real between 0 and 1 that is not in the range of g.

Cantor did it for the denumerable binary sequences: Let g be a list of denumerable binary sequences. We construct a denumerable binary sequence that is not in the range of g.

/

Entscheidungsproblem. My mistake. I overlooked that Turing proved both the unsolvabilty of the halting problem and the unsolvabity of the Entscheidungsproblem. Chuch also independently proved the unsolvability of the Entscheidungsproblem.

Math is confusing. It's far more closer to philosophy than mathematicians and logicians want to admit. — ssu

In this thread I got exposed to a part of model theory that I have always avoided (models of ZFC) because I have always found it highly confusing. (I had always restricted myself to dealing with models of PA.) After having a few exchanges on the subject, the subject has actually become slightly less confusing. That's actually some progress. I hope that I no longer confuse a model with its metatheory (that problem does not really have the opportunity to occur with dealing with models of PA). Maybe I will less actively avoid the subject in the future. I also think that mathematics has its deep philosophical aspects. As far as I am concerned, model theory has never been a goal in itself. I mostly get confronted with it when I read about something else which happens to be connected. I will probably still never read about model theory just for its own sake.

.

Ok, I think I now understood you. By g you referred to the list, while I thought you meant the constructed real that isn't on g.

g is a list of denumerable binary sequences, and we construct a denumerable binary sequence not listed by g.

Or if reals are addressed:

g is a list of reals, and we construct a real not listed by g.

:grin:

And you see now that a reductio argument is not needed; indeed Cantor did not use a reductio argument.

And you see now that a reductio argument is not needed; indeed Cantor did not use a reductio argument. — TonesInDeepFreeze

OK, so let me try get your viewpoint here: having the list g and constructing the real that is not on the list isn't itself using reductio ad absurdum. Yes, this obvious to me also.

However, I still insist that to prove that there's no 1-to-1 correspondence between exist between the natural numbers and the reals is a proof by contradiction, where you use what was done above. So when I talked about diagonalization, being an amateur here, I also referred to consequences and this (the list, anti-diagonal construct which isn't on the list) being used as part of a wider proof. For you diagonalization is just the part with the list g and the construction of the real that isn't in it. I can understand that totally.

Either this is the issue, or then I have to try to spend even more of your precious time.

It's garden variety modus tollens:

If there is a bijection then there is a surjection
There is no surjection.
Therefore, there is no bijection.

No need for a reductio assumption.

It's garden variety modus tollens:

If there is a bijection then there is a surjection
There is no surjection.
Therefore, there is no bijection.

No need for a reductio assumption. — TonesInDeepFreeze

Yes,

But if you start from that there is no bijection, and then prove it by:
If there is a bijection then there is a surjection
There is no surjection.
Therefore, there is no bijection.

Isn't that a proof by contradiction. That was my point.

first is assumed that all reals, lets say on the range, (0 to 1) can be listed — ssu

If that is considered a form of reductio ad absurdum, then every proof of a negation is proof by a form of reductio ad absurdum.

In a natural deduction system, the way to prove a negation ~P is to assume P, derive a contradiction, and infer ~P.

In an ordinary Hilbert system, the way to prove a negation ~P is to prove, for some Q, P -> Q and ~Q, and infer ~P.

Yes, those are like "cousins" of one another. And they can be derived from one another as derived rules in the systems.

But again, if using modus tollens is considered a form of reductio ad absurdum, then any proof of a negation is a form of reductio ad absurdum.

Note that both of those are intuitionistically valid. What are not intutionistically valid are:

Assume ~P, derive a contradiction, and infer P.

~P -> Q and ~Q, and infer P.

/

Also there are different terminologies:

reductio ad absurdum

indirect proof

proof by contradiction

So we need to be clear whether the intuitionistically valid form or the intuitionistically invalid form or both are referenced.

/

You mentioned 'indirect proof' and you said:

first is assumed that all reals, lets say on the range, (0 to 1) can be listed — ssu

My point was that we do not need to assume that all the reals are listed. "All the reals are listed" would be P in the remarks above.

Now you've switched to pointing out that modus tollens is used.

And this has nothing to do with anti-diagonalization.

Thanks for the educative response. But it seems that you went back to my earlier post.

So just to make things clear, I'll ask again:

But if you start from that there is no bijection, and then prove it by:
If there is a bijection then there is a surjection
There is no surjection.
Therefore, there is no bijection.

Isn't that a proof by contradiction? — ssu

Now why I'm ranting so much about negative self-reference or diagonalization, which I acknowledge I haven't accurately defined, is that it crops so easily in many important findings. Yet what is lacking is a general definition.

Here's a video explaining this perhaps better than me:

Could this be put to even more simple terms?

Now why I'm ranting so much about negative self-reference or diagonalization, which I acknowledge I haven't accurately defined, is that it crops so easily in many important findings. Yet what is lacking is a general definition. — ssu

Here's the general theorem in the setting of category theory. It's called Lawvere's fixed point theorem. Not necessary to understand it, just handy to know that all these diagonal-type arguments have a common abstract form.

In mathematics, Lawvere's fixed-point theorem is an important result in category theory. It is a broad abstract generalization of many diagonal arguments in mathematics and logic, such as Cantor's diagonal argument, Russel's paradox, Gödel's first incompleteness theorem and Turing's solution to the Entscheidungsproblem.

I gather the video was about that, but the Wiki page is more to the point and takes far less time to not understand :-)

What I meant that it itself is an indirect proof: first is assumed that all reals, lets say on the range, (0 to 1) can be listed and from this list through diagonalization is a made a real that is cannot be on the list. Hence not all the reals can be listed and hence no 1-to-1 correspondence with natural numbers. Reductio ad absurdum. — ssu

Not necessary to use reductio. Cantor's diagonal argument says that any list of reals is incomplete. We can prove it directly by showing that any list of reals (not an assumed complete list, just any arbitary list) is necessarily missing the antidiagonal. Therefore there is no list of all the reals.

theories (interpretations) — fishfry

We're talking about different things. I'm talking about formal theories and interpretations of their languages as discussed in mathematical logic, and such that theories are not interpretations.