- #1
andrewr
- 263
- 0
I am interested in a little fun...
It has been some time since I have done any set theory, and I am forgetting the symbols and ideas... So, I wanted to construct a strong inductive proof, and get a bit of help with how to concisely write the proof, and how to get TEX here at the forums to correctly display it! -- and receive input as to whether or not the conclusion of this proof is valid.
I want to start with an empty set S={}
Then I want to add to the set a new subset, and the new subset must contain *arbitrary* elements equal in cardinality to the cardinality of elements (eg:subsets) in S *after* adding the new subset.
There could be multiple ways of arriving at this result, and constructing this set S; eg: one of which is just that each subset added must have exactly one more element than the last subset added to S. etc.
But I want to be general in the final proof... perhaps including other ways this could happen.
For simplicity, I'll just assume an "infinite" alphabet can be used in the subsets in order to represent arbitrary "elements" of the subsets (or a finite unbounded alphabet ... whichever is really appropriate, and I don't really know. ).
So, for example, the first time I do this -- S is { {a} }
And then, when I do it again, S is { {a}, {a b} } or perhaps S is { {a}, {b b} }
(The reason for a particular symbol is TBD later, I just want to be *very* general at this time)
Now, I can continue to add subsets one at a time, so that one might suspect there is an order of successors -- but I am not *depending* on the order at this time. The order could be scrambled at every addition of a subset as far as I am concerned right now.
I'm just showing a list in order because, well, this is a computer screen and Turing machine equivalent -- and I have to print the characters in *some* order (indexing) so that I may demonstrate it to you; otherwise it's a bit of a non-falsifiable idea... I can't see how else to *demonstrate* the construction.
But I wish to ignore that as *much* as possible, as many set theorists seem to do...!
So, at the next addition to the set, I have:
S is { {a}, {a,b}, {a,b,c} }
and then
S is { {a}, {a,b}, {a,b,c}, {a,b,c,d} }
And so on...
This may seem trivial, but what I want to inductively show is that there *IS* an element in S (one or more subsets), that has exactly the *SAME* cardinality as S itself, regardless of how many other ways S could have been constructed that is equivalent to my one example: And I'd like to know how to write the proof concisely using the symbols of set notation; and I'd like it to be a robust and *general* proof without any *major* flaws... (A bit of a fun challenge... eh?)
I expect there will be a conclusion something like:
[tex] \exists x \in S | |x| = |S| [/tex]
[tex] \exists x \in S : \# x = \# S [/tex]
Whatever is more proper...
So, how would I show the steps I have given by example and without any precise symbols, BUT generalize these examples, and do so in concise mathematical format;
Can anyone give a strong inductive proof of my idea that an element of the same cardinality as S *always* exists in the constructed set, S ? Regardless of how many times I *add* to S? (Even if I never stop?)
After that, I have some detailed questions to ask... but I'd like to start here, it's simple.
Thanks!
It has been some time since I have done any set theory, and I am forgetting the symbols and ideas... So, I wanted to construct a strong inductive proof, and get a bit of help with how to concisely write the proof, and how to get TEX here at the forums to correctly display it! -- and receive input as to whether or not the conclusion of this proof is valid.
I want to start with an empty set S={}
Then I want to add to the set a new subset, and the new subset must contain *arbitrary* elements equal in cardinality to the cardinality of elements (eg:subsets) in S *after* adding the new subset.
There could be multiple ways of arriving at this result, and constructing this set S; eg: one of which is just that each subset added must have exactly one more element than the last subset added to S. etc.
But I want to be general in the final proof... perhaps including other ways this could happen.
For simplicity, I'll just assume an "infinite" alphabet can be used in the subsets in order to represent arbitrary "elements" of the subsets (or a finite unbounded alphabet ... whichever is really appropriate, and I don't really know. ).
So, for example, the first time I do this -- S is { {a} }
And then, when I do it again, S is { {a}, {a b} } or perhaps S is { {a}, {b b} }
(The reason for a particular symbol is TBD later, I just want to be *very* general at this time)
Now, I can continue to add subsets one at a time, so that one might suspect there is an order of successors -- but I am not *depending* on the order at this time. The order could be scrambled at every addition of a subset as far as I am concerned right now.
I'm just showing a list in order because, well, this is a computer screen and Turing machine equivalent -- and I have to print the characters in *some* order (indexing) so that I may demonstrate it to you; otherwise it's a bit of a non-falsifiable idea... I can't see how else to *demonstrate* the construction.
But I wish to ignore that as *much* as possible, as many set theorists seem to do...!
So, at the next addition to the set, I have:
S is { {a}, {a,b}, {a,b,c} }
and then
S is { {a}, {a,b}, {a,b,c}, {a,b,c,d} }
And so on...
This may seem trivial, but what I want to inductively show is that there *IS* an element in S (one or more subsets), that has exactly the *SAME* cardinality as S itself, regardless of how many other ways S could have been constructed that is equivalent to my one example: And I'd like to know how to write the proof concisely using the symbols of set notation; and I'd like it to be a robust and *general* proof without any *major* flaws... (A bit of a fun challenge... eh?)
I expect there will be a conclusion something like:
[tex] \exists x \in S | |x| = |S| [/tex]
[tex] \exists x \in S : \# x = \# S [/tex]
Whatever is more proper...
So, how would I show the steps I have given by example and without any precise symbols, BUT generalize these examples, and do so in concise mathematical format;
Can anyone give a strong inductive proof of my idea that an element of the same cardinality as S *always* exists in the constructed set, S ? Regardless of how many times I *add* to S? (Even if I never stop?)
After that, I have some detailed questions to ask... but I'd like to start here, it's simple.
Thanks!
Last edited: