Various stuff, mostly about sets

  • Thread starter honestrosewater
  • Start date
  • Tags
    Sets
In summary, the two conjectures state that (1) if R is finite, then V is finite, and (2) if R is countable, then V is uncountable.
  • #1
honestrosewater
Gold Member
2,142
6
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:
Physics news on Phys.org
  • #2
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
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:
  • #4
Yes. Looks like that'll do it.
 
  • #5
There's a simpler approach: prove there's an injection from G to N2, and use the fact someone already proved N2 countable! :smile:
 
Last edited:
  • #6
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, what does N2 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 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
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.
 

1. What is a set?

A set is a collection of distinct objects or elements that are grouped together based on a specific criteria or property. These elements can be anything, such as numbers, letters, or even other sets.

2. How are sets different from other data structures?

Sets are different from other data structures, such as arrays or lists, because they do not have a specific order or index. This means that the elements in a set cannot be accessed by a specific position, and duplicate elements are not allowed.

3. Can sets contain other sets?

Yes, sets can contain other sets. These are known as nested sets and can be used to represent complex relationships between data.

4. How are sets represented in mathematics?

In mathematics, sets are represented using curly braces { } and listing the elements inside. For example, the set of even numbers can be written as {2, 4, 6, 8, ...}.

5. What operations can be performed on sets?

There are several operations that can be performed on sets, such as union, intersection, and difference. Union combines two sets into one, intersection finds the common elements between two sets, and difference finds the elements that are only in one set but not the other.

Similar threads

  • Calculus and Beyond Homework Help
Replies
5
Views
1K
  • Set Theory, Logic, Probability, Statistics
Replies
4
Views
2K
  • Set Theory, Logic, Probability, Statistics
Replies
15
Views
1K
  • Set Theory, Logic, Probability, Statistics
Replies
2
Views
2K
  • Set Theory, Logic, Probability, Statistics
Replies
11
Views
3K
  • Calculus and Beyond Homework Help
Replies
1
Views
3K
  • Set Theory, Logic, Probability, Statistics
Replies
33
Views
4K
  • Set Theory, Logic, Probability, Statistics
Replies
24
Views
2K
  • Topology and Analysis
Replies
2
Views
3K
  • Math Proof Training and Practice
2
Replies
67
Views
7K
Back
Top