I was studying model theory and that\'s how I came across formal languages. I lo

Question

I was studying model theory and that's how I came across formal languages. I looked around but it seems as though a language (set of strings over some alphabet) is usually treated as being finite or countable. Just wondering if languages of higher cardinality have been investigated. Any references would be nice.

Thank you!

EDIT: I found an answer. Infinitary logic deals with just such a question. See here. It allows formulas of infinite length, so the collection of all such formulas could be uncountable. I guess in the CS world a formula is simply a legally formed word (based on some rules). The set of all such legal formulas could be uncountable.

I'm choosing to leave this question here as it might help another beginner like myself.

EDIT 2: Another way maths allows uncountable languages is to allow uncountably many symbols in the signature (which would be a subset of alphabet in the CS world). So even if formulas (i.e. words) can only be finitely long, there can be uncountably many of them.

I've realized the question isn't so much about formal languages as it is about logic. It was due to my ignorance that I posted the question here. My humble apologies!

Explanation / Answer

The answer by jmite tells you what is being done in computer science.

The point of it is that it is primarily devoted to algorithm and computation, as ways of solving problems. Hence it is also tightly connected with proof theory, and the logical work in the late 19th and early 20th century.

To a large extent, it is a theory of syntax, as all we do in mathematics is to push symbols around according to specific rule. Of course, as you know, there is semantics behind the symbols and their assembly into sentences, but the only way to refer to the semantics is through the symbols.

In a way, it is a physical theory, as much as a mathematical one. It is about what we can express in this physical world, as human being, or using machines. It is about computation, which is also called calculus (not to be confused with differential and integral calculus), which comes from counting stones in Latin. Our first interest is then to develop what seems physically meaningful.

Of course, there are probably many ways to extend it, such as hypothesizing computable solutions to problems even though none actually exists, which is somewhat like adding an axiom that has no physical model. It is a bit like science-fiction: we can talk about the extension, and what it can do , and how that would change the world. But we cannot actually use it and do those things.

So, nearly everything we do in practice is finite, but often cannot be bounded meaningfully. Working up to denumerable infinity turned out to be the most convenient way to address efficiently that situation. We often consider "infinite" structures, but in the end they are only limits of uniformly computable finite approximations, which keeps us in the denumerable world.

The case of computable reals is interesting. They are (isomorphic to) a subset of the usual reals, but defined as computable limits, hence characterized by whatever machine computes the approximations. In the end, each is characterised by a finite definition, which makes them denumerable. The interesting point is that you can do with computable reals practically all you do with the classical ones. See for example "To what extent can the mathematics of Reals be applied to Computable Reals?"

My guess, but it is only a guess, is that the same is probably true of infinitiary logic (of which I know only what you said). If you are careful to consider only computable strings on infinite length, you will stay in the denumerable realm, but you can probably adapt all definitions to get whatever nice properties you expect from infinitiary logic. And, as a bonus, it may have physical sense.

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.