Can Strong Induction Prove an Element in Set S Matches Its Own Cardinality?

[andrewr]

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!

 

[oli4]

Hi andrewr
I'm not sure I really understand what you are after
But it looks like you are after defining an order for sets that grow in cardinality independently of their content (sorry if this is not it)
before trying to guess too much about what you are after
would this construction make any sense to you (I mean not "would you understand it" but is this a a way to express what you are after")
{} (0) is void, that is a set that does not contain anything
{{}} (1) is the set that contains the void set and has 1 element
{{{}}, {}} (2) is the set that contains the previous set (1 (that was the set containing the void set)) and the void set
etc.

Is this the notation you are look for ? or are you after something completely different ?
(I probably am not able to help you anyway, but just in case I try to understand what you are after

Cheers...

Oli4

 

[andrewr]

Hi andrewr
I'm not sure I really understand what you are after
But it looks like you are after defining an order for sets that grow in cardinality independently of their content (sorry if this is not it)
before trying to guess too much about what you are after
would this construction make any sense to you (I mean not "would you understand it" but is this a a way to express what you are after")
{} (0) is void, that is a set that does not contain anything
{{}} (1) is the set that contains the void set and has 1 element
{{{}}, {}} (2) is the set that contains the previous set (1 (that was the set containing the void set)) and the void set
etc.

Is this the notation you are look for ? or are you after something completely different ?
(I probably am not able to help you anyway, but just in case I try to understand what you are after

Cheers...

Oli4

Hi Oli, Yes -- that could express an equivalent idea, or a subset of my idea.
It's not the notation I'm looking for, though.
The set I am showing you is defined recursively, by examples.
In set theory, if you look over at the latex bar by clicking on the Sigma during a post edit -- there are set theory symbols, such as "in", "union", etc; there are also general math symbols like "Such that", "at least one", "exactly one", etc.

What I am wanting to do is express what the set *is* regardless of different ways one might construct it using set theory notation (as you have just done!). Any set having the properties of the one I showed, and which you produced a specific instance of, needs to be defined symbolically -- and then a strong inductive proof in proper mathematical notation (as opposed to only using English words) is desired, to show that there is always an element in such a set that has the same cardinality as the set itself. (This is seemingly trivial, but the process is what I find most important -- not the result.)

There are various ways someone might try to compare the symbols for cardinality, one might "number" them as you are doing -- or someone might do a bijection (1:1) correspondence. ; and perhaps several others I haven't thought of.

Some methods might be generally rejected by the mathematical community (at least for now) because of perceived flaws, or historical definitions that exclude certain possibilities;

Take for example sequence notation, which has an index "i"; The index only index's a finite location -- as there is no such thing as an "infinite" integer. But a set or a subset can be infinite. Hence, what one chooses as notation might affect what is or isn't permissible in a proof.

I am just hoping to see the process people go through to construct the best proof they can, with the *LEAST* amount of writing, and invocation of disciplines which are specialized. I'd like to see this in terms of basic set theory... (Whatever that really means. )

 

[oli4]

Hi andrewr,
I suppose I am getting closer (maybe not ;))
What I was putting as an example, was precisely not numbering, on the contrary, I was showing a very minimal set of symbols to show a set of growing cardinality.
(I was just putting (0) (1) (2) as a note to see how the constructed sets can be interpreted, but (0), (1) and (2) are meaningless in this context
that is, all you have is the notion of set (which contains or not something (and if not is the empty set)))
you can then see {} (the empty set) as 0
and {{}} the set that contains the empty set as 1,
and then {{}, {{}}} the set that contains what was previously called '1' and the empty set and is defined at '2'

but you could also make something different:
{} ->0 (the empty set is 0)
{{}} -> the set that contains just one set (it contains the empty set) is 1
{{{}}} -> the set that contains 1 (which is the set that contains the empty set) is 2 etc.

So anyway, I was not trying to index anything but trying to see if when you were putting a, b, c, ... and (as I understood it) were finding arbitrary limitations due to the limitation of available symbols, you would be satisfied with this notation which does not suffer from symbol limitation.
(if this has nothing to do with your question, well, at least we cleared that up

Cheers...

Oli4

 

[andrewr]

Hi andrewr,
I suppose I am getting closer (maybe not ;))
What I was putting as an example, was precisely not numbering, on the contrary, I was showing a very minimal set of symbols to show a set of growing cardinality.
(I was just putting (0) (1) (2) as a note to see how the constructed sets can be interpreted, but (0), (1) and (2) are meaningless in this context

Yes, I noticed that before.

that is, all you have is the notion of set (which contains or not something (and if not is the empty set)))
you can then see {} (the empty set) as 0
and {{}} the set that contains the empty set as 1,
and then {{}, {{}}} the set that contains what was previously called '1' and the empty set and is defined at '2'

Which is fine. I would extrapolate your example to:
{ {}.{{}},{{},{}},{{},{},{}} }

I would question whether it is proper to say {} contains the empty set, or is an empty set.
If it's the latter, then other's might object that it does not contain the same number of members as the set S = { {} }, but one less -- the cardinality becomes interpretation dependent...

I wonder, do we needto say S = { { ∅ } } to be more formal/clear ?

but you could also make something different:
{} ->0 (the empty set is 0)
{{}} -> the set that contains just one set (it contains the empty set) is 1
{{{}}} -> the set that contains 1 (which is the set that contains the empty set) is 2 etc.

No, that one would not agree with my original example. I'm not sure if what I said allows this idea or not, but it would violate what I had in mind -- so this is a place where notation would be something useful to prevent misunderstanding. I'm not sure how to state it in symbols, that I don't mean multiple sub-nested sets -- but only 1 level of sub-nesting.

So anyway, I was not trying to index anything but trying to see if when you were putting a, b, c, ... and (as I understood it) were finding arbitrary limitations due to the limitation of available symbols, you would be satisfied with this notation which does not suffer from symbol limitation.
(if this has nothing to do with your question, well, at least we cleared that up

Cheers...

Oli4

Well it does, but that's something too subtle for me to explain in any detail until after I have achieved the idea with physical elements in the set, as opposed to empty sets.
Human beings, computers, etc. are considered {assumed} in most mathematical disciplines to be equivalent in a processing sort of way -- that is, we convey output and receive input in a character/symbol oriented format. You had to use brackets, for example, to indicate an empty set. Hence, any computing machine or mathematician that is conveying *information* or an arbitrary set *idea* requires a convention of some type of symbol or character -- to write to an output or input media, whether permanent or ephemeral.

I tend to think certain restrictions in mathematics might not be on account of using symbols, but precisely the opposite; inductive reasoning based on the assumption that there is such a thing a symbol-less idea.

Philosophically, I might argue this way -- (but I will restrict myself to Turing tapes in the future); Someone could say to me: "If a tree falls in the forest and there's nobody around, does it make a sound?" -- to which I can reply, "I saw it in my imagination when you told me about it, and now you are calling me nobody?!" and then we can discuss if an imaginary sound is a sound, etc. But the point is, there is no idea which can communicated that is entirely an empty set; we must communicate "something" and then delete the "box" by convention -- and sometimes forgetting that the box is being deleted by convention may be a *BAD* idea.

Once we proceed past this first definition/inductive proof part, I'll most likely move the conversation forward by extending the idea to different ways one might encode this set "S" we're discussing in various formats on a Turing tape; (but ignoring! the Turing machine...) and how one would still prove the existence of an element in the set with the same cardinality as the set... etc.

P.S. I never intended to accuse you of indexing anything, if you thought I was. If you didn't think I was accusing, I'm glad. Empty conversations and attempted clarifications about nothing -- sometimes lead to hurt feelings. :shy:

 

[oli4]

Hi andrewr
I don't understand what you mean, and I don't feel accused of anything, I just wanted to make sure I was addressing your question.
If I understand you correctly, and I probably don't, you are looking for some 'ultimate way' (one that would be truer, or more fundamental) to express your ideas.
If this is indeed, what you are after, then tough luck, there is no such thing, the two examples I gave you are perfectly equivalent minimalistic ways to represent the integers.

Anyway, it looks like you are interested in formal logic, and to get as deep as possible into it (I'm saying this because you brought in philosophical arguments/pieces).
If it is the case, I would recommend you to have a deep look at this.
whether or not it is the first answer to your original question (which I didn't identify) it will very likely be a good answer to your last question ;) (well, you would have so many others after that but more and more philosophical and less and less mathematical)

 

[andrewr]

Hi andrewr
I don't understand what you mean, and I don't feel accused

ibid -- Good. Just ignore it, then.

you are looking for some 'ultimate way' (one that would be truer, or more fundamental) to express your ideas.

I'm looking for a formal inductive proof, Given the set I've shown a-priori, that an element exists in the set which has the same cardinality as the set. It doesn't need to be ultimate, just formal; with comments on possible defects in the proof -- "a progression" toward the ultimate, but no expectation to achieve it.

Anyway, it looks like you are interested in formal logic, and to get as deep as possible into it (I'm saying this because you brought in philosophical arguments/pieces).
If it is the case, I would recommend you to have a deep look at this.

That URL didn't work, I don't know why. Yes, I think you are correct -- I am interested in formal inductive proof logic; eg: how it is properly stated.

well, you would have so many others after that but more and more philosophical and less and less mathematical)

No, I am going to use a Turing tape (or a pair) to discuss representations of set S. They will be concrete examples -- not philosophical. There are unavoidable constraints when one chooses to represent sets on tape, or internet, or... etc. The philosophical comment was intended to show an overview of the math -- not vice versa.

Thanks for your input. No need to comment further, except perhaps a working link.
I expect there are others who will chime in once I have enough information to at least attempt a formal proof.

 

[SteveL27]

S is { {a}, {a,b}, {a,b,c}, {a,b,c,d} }

It looks like you might be interested in the Von Neumann Ordinals.

http://en.wikipedia.org/wiki/Ordinal_number#Von_Neumann_definition_of_ordinals

 

[oli4]

Ah sorry for the bad link
From your reply though, I suppose it wasn't a useful link anyway, I just wasn't sure where you were heading, but just in case, Gödel's incompleteness theorem

Have fun :)

Cheers...