I want to prove some various but closely-related things about a language, so if I need help later on, I'll just add it here. Definitions are in indigo. The primitive symbols of formal language L fall into two disjoint sets: a countably infinite set of propositional symbols and a non-empty finite set of connective symbols. The set S of primitive symbols is then countably infinite. A string of length n is a map from {1, 2, 3, ..., n} to S. The empty string has length 0. Conjecture: The set G of strings is countably infinite. I got this idea from seeing Cantor's diagonal process. Let G_{n} denote the set of strings of length n. Then G is countable if each G_{n} is at most countable. G_{0} has one member. G_{1} = S, so is countable. For G_{2}, consider the infinite array, where p_{n} is a primitive symbol: p_{1}p_{1}, p_{1}p_{2}, p_{1}p_{3}, ... p_{2}p_{1}, p_{2}p_{2}, p_{2}p_{3}, ... p_{3}p_{1}, p_{3}p_{2}, p_{3}p_{3}, ... ... Then the members of G_{2} can be arranged in the sequence: (p_{1}p_{1}; p_{2}p_{1}, p_{1}p_{2}; p_{3}p_{1}, p_{2}p_{2}, p_{1}p_{3}; ...). So G_{2} is countable. I can't think of a way to visualize the process for higher G_{n}s, but here's the idea, with G_{3} as an example. Arrange the members of G_{3} into a sequence by groups. Let group 1 contain all arrangements of p_{1}: p_{1}p_{1}p_{1}. Let group 2 contain all arrangements of p_{1} and p_{2} not in group 1 (I'll just write the subscripts): 112, 121, 122, 211, 212, 221, 222. Let group M contain all arrangements of p_{1}, p_{2}, ..., p_{M} not in previous groups. Put the members of each group into the sequence. Then the sequence contains all members of G_{3} and is countable. Do the same for each remaining G_{n}. Then every G_{n} is at most countable. Does that work? Make sense?
I think your scheme can be used to prove that each of your G_{n}s is countable, and that the union of any finite set of those G_{n}s is countable, but not that G is countable. If I recall correctly, a language is countable iff it is recursively enumerable. I don't see how you can use your technique to define a Turing machine (or any algorithm) that would eventually (i.e. in some finite amount of time) list every member of your language. Depending on how you structure it, wouldn't it either: a) run on forever listing strings of length 1 (G_{1} in your scheme), never getting to any longer strings or, trying a slightly different approach, b) run on forever listing strings consisting only of p_{1}, never getting to any strings containing other primitives?
You could extend honestrosewater's scheme. Let g(a, b) denote the group in honestrosewaters scheme of length a and counted as the bth group within that length (e.g. g(2, 2) = p2p1, g(3, 2) = p1p1p2). Now at each step, step number n, count the groups g(a, b) such that a + b = n. These groups are a finite set, so they are countable, and every g(x, y) will be reached. (This idea is similar to what honestrosewater was already doing, namely counting "diagonals")
There's a simpler approach: prove there's an injection from G to N^{2}, and use the fact someone already proved N^{2} countable!
Thanks, I love the creativity. They may mean the same thing, I don't know, but I only need sets to be countable, not languages. I actually already had a proof that the union of a countable set of countable sets was countable. Of course, G_{0} is finite, so I said at most countable, which obviously also holds. I also found a proof (on the same page as the one above!) that the set of all n-tuples of a coutable set is countable. And strings are just n-tuples. It goes: Assume G_{n-1} (n = 2, 3, ...) is countable. The elements of G_{n} are of the form (g, s) with g in G_{n-1} and s in S. For every fixed g, the set of pairs (g, s) is equivalent to S (recall S is countable). Thus B_{n} is the union of a countable set of countable sets, thus by the last theorem is countable. The basis is just G_{1} = S. Well, G_{0} is a pain, but it's just a tweek. His is much shorter than mine ;) The next part is easy. The set R of formulas is a subset of G. A valuation is a map from R to {T, F}. Let V denote the set of all valuations. Conjecture 1: If R is finite, then V is finite. If there are n elements in R, think of a valuation as an n-tuple whose terms are T and F. Then there are 2^{n} elements in V, so V is finite. Conjecture 2: If R is countable, then V is uncountable. I'm adapting this from the same book. So think of a valuation as a sequence whose terms are T and F. Let W be a countable subset of V, and let W consist of the sequences s_{1}, s_{2}, s_{3}, .... Construct a sequence s as follows. If the nth term of s_{n} is T, let the nth term of s be F, and vice versa. Then s is in V, and s differs from every member of W in at least one place, so s is not in W, so W is a proper subset of V. Thus V is uncountable, since every countable subset of V is a proper subset of V (and V cannot be a proper subset of itself ;). I'm trying to be as general as possible, but do I need to make R non-empty? Empty R doesn't make sense to me- do I just choose one- T or F? Is it an open for interpretation kind of thing? Hurkyl, what does N^{2} mean- I can't seem to keep it straight- the set of all 2-tuples in N?
Yep. Also means the set of all functions from 2 (= {0, 1}) to N. So, if you take a string and convert it into a 2-tuple by saying the first coordinate is the length and second coordinate is m, where your string is the m-th string of that length, then you get an injection into N^{2} Actually, I can do even better, an injection into N! You have countably many symbols in your language. So, you can just write each symbol as a binary number. Then, any string can be written as a ternary number by rewriting each symbol as its binary representation, and inserting a `2' between each symbol. Voila, injection into the naturals! There is exactly one function whose domain is the empty set: the empty function.
Ah, that's clever. So now it starts getting complicated because I add that a set H of theorems is a subset of R. If r is a formula and v a valuation, v(r) denotes the value assigned to r by v. I want to prove that for every H, there is a subset of V such that r is in H iff v(r) = T. And vice versa (for every subset of V...). This may be easy since I've left things general and simple, but I want to start adding specifics and it gets rather overwhelming. I'll work on it a bit later.