# Various stuff, mostly about sets

1. ### honestrosewater

2,329
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 Gn denote the set of strings of length n. Then G is countable if each Gn is at most countable. G0 has one member. G1 = S, so is countable. For G2, consider the infinite array, where pn is a primitive symbol:
p1p1, p1p2, p1p3, ...
p2p1, p2p2, p2p3, ...
p3p1, p3p2, p3p3, ...
...
Then the members of G2 can be arranged in the sequence:
(p1p1; p2p1, p1p2; p3p1, p2p2, p1p3; ...). So G2 is countable.
I can't think of a way to visualize the process for higher Gns, but here's the idea, with G3 as an example. Arrange the members of G3 into a sequence by groups. Let group 1 contain all arrangements of p1: p1p1p1. Let group 2 contain all arrangements of p1 and p2 not in group 1 (I'll just write the subscripts): 112, 121, 122, 211, 212, 221, 222. Let group M contain all arrangements of p1, p2, ..., pM not in previous groups. Put the members of each group into the sequence. Then the sequence contains all members of G3 and is countable.
Do the same for each remaining Gn. Then every Gn is at most countable.
Does that work? Make sense?

Last edited: Apr 21, 2005
2. ### gnome

I think your scheme can be used to prove that each of your Gns is countable, and that the union of any finite set of those Gns 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 (G1 in your scheme), never getting to any longer strings
or, trying a slightly different approach,
b) run on forever listing strings consisting only of p1, never getting to any strings containing other primitives?

3. ### BicycleTree

552
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")

Last edited: Apr 25, 2005
4. ### gnome

Yes. Looks like that'll do it.

5. ### Hurkyl

16,090
Staff Emeritus
There's a simpler approach: prove there's an injection from G to N2, and use the fact someone already proved N2 countable!

Last edited: Apr 25, 2005
6. ### honestrosewater

2,329
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, G0 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 Gn-1 (n = 2, 3, ...) is countable. The elements of Gn are of the form (g, s) with g in Gn-1 and s in S. For every fixed g, the set of pairs (g, s) is equivalent to S (recall S is countable). Thus Bn is the union of a countable set of countable sets, thus by the last theorem is countable. The basis is just G1 = S. Well, G0 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 2n 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 s1, s2, s3, .... Construct a sequence s as follows. If the nth term of sn 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 N2 mean- I can't seem to keep it straight- the set of all 2-tuples in N?

7. ### Hurkyl

16,090
Staff Emeritus
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 N2

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.

8. ### honestrosewater

2,329
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.