5
$\begingroup$

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!

$\endgroup$
  • $\begingroup$ You have a non-sequitur there. A collection of infinite strings is not necessarily uncountable. It may depends on whether these strings are computable or not. Computable reals may be seen as a set of infinite strings, but are denumerable. Actually, but this is just a guess, I would expect that there is a computable version of infinitiary logic,making it denumerable, while keeping most of its interesting properties (as is the case for computable reals). $\endgroup$ – babou Dec 19 '14 at 14:51
  • $\begingroup$ Well, my previous remark may have been a misreading. It depend on whether "all such string" refers to all strings that are allowed (which is what I read, or to all strings of infinite length. $\endgroup$ – babou Dec 19 '14 at 16:14
  • $\begingroup$ @babou No you are right. I've edited the question. I must confess my ignorance of the CS side of things (I'm a math student, and an inexperienced one at that). Actually I've realized what I was looking for isn't so much about formal languages as it is about the formation rules of logic. But thanks for the answer - it's sparked an interest into the CS side of things. $\endgroup$ – Stranger Dec 20 '14 at 1:38
  • $\begingroup$ Actually this is a good question, imho. Since you are in model theory, I should mention that historically, the view of denumerable stuctures and concepts as limits of countable approximation came in pretty late, in the 1970s, precisely in order to construct mathematical models of computation. This was mainly the contribution of a logician, Dana Scott. A fairly simple account of his early work is in Outline of a Mathematical Theory of Computation. Models of computation have considerably evolved since then. $\endgroup$ – babou Dec 20 '14 at 11:18
5
$\begingroup$

In traditional Formal Language theory, all languages are countable. This is because they're defined as a subset of $\Sigma^*$, so they always contain strings of finite length, meaning we can map them to integers.

We rarely deal with finite languages, since all finite languages are regular, and therefore trivially decidable.

There has been research into the computability of functions on real numbers. The difficulty here is that in practice, there's no single way to represent arbitrary real numbers. A common method is looking at, given a real-valued function $f$, inputs $\vec{x} $ and an integer $n$, can we use a Turing Machine to compute a representation $f(\vec{x})$ to $n$ digits of precision?

You could view a real number as justing being a function taking $0$ arguments, so a real number $r$ is can be seen as a function from $n$ to the first $n$ binary digits of $r$.

Interestingly, since Turing Machines are finite, the set of all Turing Machines is countable, so the set of all computable real numbers is countable, meaning there are many more uncomputable reals than computable ones.

For more info, see http://en.wikipedia.org/wiki/Computable_number.

Note that there's also a concept of automata on infinite words, used in formal language theory and program verification. These languages can be uncountable: an infinite sequence of $0$s and $1$s is equivalent to a subset of $\mathbb{N}$ so an automaton that accepts all such words accepts an uncountable language.

$\endgroup$
  • 1
    $\begingroup$ I must confess my ignorance of the CS side of things (I'm a math student, and an inexperienced one at that). Actually I've realized what I was looking for isn't so much about formal languages as it is about the formation rules of logic. But thanks for the answer - it's sparked an interest into the CS side of things. I don't even have enough cred to upvote this answer :( $\endgroup$ – Stranger Dec 20 '14 at 1:39
5
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Great answer. I don't even have enough cred to upvote this answer :( $\endgroup$ – Stranger Dec 20 '14 at 1:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.