Various stuff, mostly about sets

[honestrosewater]

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₀ has one member. G₁ = S, so is countable. For G₂, consider the infinite array, where p_n is a primitive symbol:
p₁p₁, p₁p₂, p₁p₃, ...
p₂p₁, p₂p₂, p₂p₃, ...
p₃p₁, p₃p₂, p₃p₃, ...
...
Then the members of G₂ can be arranged in the sequence:
(p₁p₁; p₂p₁, p₁p₂; p₃p₁, p₂p₂, p₁p₃; ...). So G₂ is countable.
I can't think of a way to visualize the process for higher G_ns, but here's the idea, with G₃ as an example. Arrange the members of G₃ into a sequence by groups. Let group 1 contain all arrangements of p₁: p₁p₁p₁. Let group 2 contain all arrangements of p₁ and p₂ 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₁, p₂, ..., p_M not in previous groups. Put the members of each group into the sequence. Then the sequence contains all members of G₃ and is countable.
Do the same for each remaining G_n. Then every G_n is at most countable.
Does that work? Make sense?

 

[gnome]

I think your scheme can be used to prove that each of your G_ns is countable, and that the union of any finite set of those G_ns 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₁ 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₁, never getting to any strings containing other primitives?

 

[BicycleTree]

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

 

[gnome]

Yes. Looks like that'll do it.

 

[Hurkyl]

There's a simpler approach: prove there's an injection from G to N², and use the fact someone already proved N² countable!

 

[honestrosewater]

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₀ 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₁ = S. Well, G₀ 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ⁿ 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₁, s₂, s₃, ... 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² mean- I can't seem to keep it straight- the set of all 2-tuples in N?

 

[Hurkyl]

Hurkyl, what does N² 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²


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.

 

[honestrosewater]

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.