Set cardinality, Turing encoding, and inductive proofs

[andrewr]

I'm going to construct an ordered set, and I'd like to ask some questions about it; and in particular consider coding problems about this set and sets in general (Turing tape encoding).

Start with:
A={ }

And, allow a mutable temporary set, initialized with:
T={ }
and an iterator: set n=0

For reference, "x", is a character;

Now to construct the set:
1) T = T $\bigcup$ "x"
2) A = A $\bigcup$ T
3) n = n+1
4) Test if |T| ?= |A| and T ?$\in$ A
5) Goto 1.

The Algorithm at each iteration (step 4), will yield a pattern:
n=1, A = { {x} } , T ={ x }, Test=True
n=2, A = { {x}, {x,x} }, T= {x.x}, Test=True
n=3, A = { {x}, {x,x}, {x,x,x} }, T={x,x,x}, Test=True
n=4, A = { {x}, {x,x}, {x,x,x}, {x,x,x,x} }, T={x,x,x,x}, Test = True
... etc

The ordering of the set A is the order in which the elements were added algorithmically.
Now, using strong induction; I can say:

Base case: for n=1, $\exists$ y $\in$ A : |y| = |A|
For case n+1, exactly one element is added to T, and one element added to A, hence:
$\exists$ y $\in$ A : |y| = |A| BY 1:1 correspondence (it is not needed to count n items.)
This is inductively true, because of algorithmic step #4.

∴ For all steps, n, even an infinite number of steps (n+1...) -- $\exists$ y $\in$ A : |y| = |A|

Now, does anyone see a problem with what I have done? If so, what?

 

[Stephen Tashi]

1) T = T $\bigcup$ "x"
2) A = A $\bigcup$ T

The Algorithm at each iteration (step 4), will yield a pattern:
n=1, A = { {x} } , T ={ x }, Test=True
n=2, A = { {x}, {x,x} }, T= {x.x}, Test=True

Are you using $\cup$ to mean the ordinary operation of set union ? If so, I don't see why T becoming {x,x} is any different that T becoming {x} since we nee only list each member of a set once. Likewise, since {x} is the same set as {x,x,...,x) there is no need to list {x} and {x,x} twice when listing the elements of A. Your example would make sense if you were doing a concatenation of characters onto strings rather than a union of sets.

 

[andrewr]

Are you using $\cup$ to mean the ordinary operation of set union ? If so, I don't see why T becoming {x,x} is any different that T becoming {x} since we nee only list each member of a set once. Likewise, since {x} is the same set as {x,x,...,x) there is no need to list {x} and {x,x} twice when listing the elements of A. Your example would make sense if you were doing a concatenation of characters onto strings rather than a union of sets.

Hi Stephen!
Yes, I mean a simple union operator. Although, I'm not used to it coming out so large... ;)

Take each 'x's inserted into set T as a *distinct* constant, with a subscript not written down but implied; (This happens in many areas of mathematics -- eg: one C is not the same as another C... sigh... My inexperience of set theory conventions is the issue here...),

I apologize for not being clear; I wasn't sure how to phrase it better at the time without writing pages of stuff...

In agreement with your observation, string concatenation is an acceptable interpretation of what is in each subset, but I don't want the whole string counted as '1' element.
Rather, count the string as a subset; and the cells of the string as *distinct* sub-elements of that subset.

I put "x" in quotes in the opening post thinking the idea of a character string would help, but I see that was a bad choice.

I don't wish to define a particular way that each x must be distinct; but it's sufficient to say that each x is at least distinct in where it appears in the string/stream. eg: the x immediately next to the "{" is at an earlier position than the second "x" after the "{".
It's an ordered set encoding, with the least element of any subset being leftmost in the text written in the post.

"x" can be replaced with many different things once the discussion progresses (assuming a flaw doesn't derail me!), and I am using a character for now simply because *encoding* sets on a Turing tape is intrinsically a string concatenation problem.

If there is better notation, I'd be happy to follow it. The Latex symbols available on PF, however, do appear to be limited; eg: assignment vs. equality isn't clear cut as to which symbol I ought to use.

Do you see any problem with the inductive proof, given the clarification of what "x" is?

 

[SteveL27]

∴ For all steps, n, even an infinite number of steps (n+1...) -- $\exists$ y $\in$ A : |y| = |A|

Now, does anyone see a problem with what I have done? If so, what?

I didn't try to follow this in detail, but what do you mean an infinite number of steps? You haven't defined what happens after an infinite number of steps.

Can you say in words what you're trying to do?

I'm already disinclined to spend time on this because Stephen Tashi's questions already brought out the fact that you are unclear what a union is and you are attempting to use one symbol 'x' to mean many different things. So there's some underlying confusion. If you say what you're trying to do or prove, it would help me to get started following the symbology.

Also you seem to be combining set theory and programming concepts in a confusing way. '=' is an equality operator, not an assignment statement. And again when you write {x,x} you are simply confusing the issue tremendously. Nothing sensible can arise.

Are you trying to construct the von Neumann ordinals?

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

 

[andrewr]

I didn't try to follow this in detail, but what do you mean an infinite number of steps? You haven't defined what happens after an infinite number of steps.

There is no "after" an infinite number of steps. I am just saying that for any finite N the pattern holds, and it holds for N+1; and hence, it must hold for any cardinality of set in 1:1 correspondence with counting numbers.

Here's a weak ANALOGY; Consider the counting numbers ... 1 is a counting number, (base case), 1+1 is a counting number; and for every n generated by adding 1 to a previous number, there is still an n+1 which is also a counting number.

The statement "n+1 is a counting number" holds true regardless of how many 'n' exist in a set; Again, I mean -- Even if the set has infinite cardinality (Aleph naught) there will be *no element* in that set, which fails to produce another counting number if 1 is added to the element's value.

Can you say in words what you're trying to do?

No, that will cause more confusion. It's best to just get the notation correct and say what I mean using the notation that everyone agrees to -- or at least will be mocked for not accepting by the general community...

I'm already disinclined to spend time on this because Stephen Tashi's questions already brought out the fact that you are unclear what a union is and you are attempting to use one symbol 'x' to mean many different things. So there's some underlying confusion. If you say what you're trying to do or prove, it would help me to get started following the symbology.

I am totally clear about what a union is; and although I understand why "x" is confusing, I explained to Stephen what I meant. Do I need to re-write the OP with x_a, x_b, x_c, x_d, ..., x_z, x_aa, x_ab, x_ac, ... ? etc.?

If so, I don't want to use enumerated subscripts because those will be hazardous later in the discussion; so what notation ought I use ?

Also you seem to be combining set theory and programming concepts in a confusing way. '=' is an equality operator, not an assignment statement. And again when you write {x,x} you are simply confusing the issue tremendously. Nothing sensible can arise.

That's a fair complaint, so will you help me fix the problem?

I know '=' is routinely used as an assignment operator where algorithms and Turing machines are concerned. But, I looked for alternatives in the Latex symbols here on the PF before writing that post, and didn't see a non ambiguous assignment operator available.

For that reason, I simply used the typical programming symbol for assignment;
and used "?=" to test equality.

I could add the word,"Let" to the assignments, I suppose; would that help? or do you have a suggestion, perhaps?

I'd happily restart the thread with better notation if the moderators permit, and there is some kind of consensus about how the O.P. ought to have been written.

Are you trying to construct the von Neumann ordinals?

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

Not at this time, no.

The construction I have made is arbitrary, and very simple, and has both finite and infinite aspects that I want to consider. In particular, I am interested in studying the possibility of character encoding various infinite sets, and proofs of what has or hasn't been encoded in such a set.

For example: If it helps you,

A specific instance where "x" is replaced by useful characters might be,
{ {1}, {1 2}, {1 2 3}, {1 2 3 4}, ...

The character sequence on your screen, would be the start of a Turing tape or "infinite stream".

With that particular *set* and it's encoding defined, I might ask something like "Could a Turing machine ever get a final closing '}' "? ( but that's not my goal, a set theory question is... )

There are several questions I'd like to be able to ask about -- but, until I have help with the basics; new questions are out of reach.

 

[andrewr]

I'll attempt the OP again, and see if this is better, if you see a mistake in notation -- please supply a link with a way which is better.

--------------------------------------------------------------

I'm going to construct a set (initially a set ordered by cardinality of subsets, but you may treat it as a sequence), and I'd like to ask some questions about the construction; and in particular consider some computer/stream encoding problems about this set and sets in general (a Turing tape type idea.).

For the purposes of discussion, the | | operator means cardinality, since P.F. does not support the more explicit symbols available in the AMS Tex package.

Start with:
Let A := { }
and
Let T := { }
and
Let n := 0

The set being constructed is called "A", "T" is a temporary used to construct set A, and n is an iterator counter for doing strong inductive proofs with, later.

Now to construct the set:

1. Let T := T ⋃ x_{unique_index}
2. Let A := A ⋃ T
3. Let n := n+1
4. Test := True if ( |T| = |A| ) and if ( T ∈ A ) else Test:= False
5. Goto 1.

The Algorithm at each iteration (step 4), will yield a pattern:
n=1, A = { {x_a} } , T ={ x_a }, Test=True
n=2, A = { {x_a}, {x_a,x_b} }, T= {x_a,x_b}, Test=True
n=3, A = { {x_a}, {x_a,x_b}, {x_a,x_b,x_c} }, T={x_a,x_b,x_c}, Test=True
n=4, A = { {x_a}, {x_a,x_b}, {x_a,x_b,x_c}, {x_a,x_b,x_c,x_d} }, T={x_a,x_b,x_c,x_d}, Test = True
... etcThe ordering of the set A is the order in which the elements were added algorithmically, eg: by cardinality of the subsets. The first subset inserted has the smallest cardinality.

Now, I am going to do a strong inductive proof that I think can be seen by inspection; but I am wanting to verify how one is done formally.

The base case is: for n=1, ∃ y ∈ A : |y| = |A|
For case n+1, exactly one element is added to T, and one element added to A, hence
There is a 1:1 correspondence between what was added to T and to A.
∴ for every iteration: ∃ y ∈ A : |y| = |A|

Which means, for all sets constructable by iteratively adding one element in this fashion, that there always will exist at least one element with the same cardinality as the set it was added to. The value of n plays no role in the construction of the set, but only serves to demark step n and n+1 in the inductive proof. The actual proof is based only on 1:1 correspondence of elements.

Now, does anyone see a problem with what I have done using strong induction?
Eg: is the proof *written* validly or not? (The result is not what I am asking about, just the construction of the proof.)

 

[Stephen Tashi]

The Algorithm at each iteration (step 4), will yield a pattern:
n=1, A = { {x_a} } , T ={ x_a }, Test=True
n=2, A = { {x_a}, {x_a,x_b} }, T= {x_a,x_b}, Test=True

That doesn't make sense as an operation of set union.
if $A = \{x_a\}$ and $T = \{x_a, x_b\}$ then $A \cup T = \{x_a, x_b\}$.

You aren't taking the union of the two sets. You are using A as a set whose members are other sets and you are adding T to the list of the members of set A. I see nothing wrong with performing such an operation, but you shouldn't use the notation $\cup$ to symbolize it.

Some people might find the notation $A:= A \cup \{\{ T \}\}$ acceptable for that operation, but it would be clearer if you just said it in words.

Likewise $T = T \cup \{x_a\}$ is the operation that adds $x_a$ to the list of the members of $T$.

 

[SteveL27]

There is no "after" an infinite number of steps. I am just saying that for any finite N the pattern holds, and it holds for N+1; and hence, it must hold for any cardinality of set in 1:1 correspondence with counting numbers.

That is false.

1 is a finite number. And if n is a finite number, n + 1 is a finite number. Therefore every element of the natural numbers is a finite number. (You can define finite any way you like, doesn't matter for this example).

But no set in 1:1 correspondence with the counting numbers is a finite number.

You can make up your own examples. Every natural number is either prime, composite, or 1, But no number in 1:1 correspondence with the natural numbers is prime, composite, or 1.

When you take limits, you often lose properties. In general that's a common pattern for math errors in proofs. Every element of the sequence 1/2, 1/3, 1/4, 1/5, ... is greater than zero. But if you take the limit, the limit is zero, which is not greater than zero.

No, that will cause more confusion. It's best to just get the notation correct and say what I mean using the notation that everyone agrees to -- or at least will be mocked for not accepting by the general community...

I was just asking for a statement of where you're going. If I just start writing down a proof without saying even what general subject I'm in, I'm going to confuse people. I get the idea that you're trying to construct the von Neumann ordinals. They are a model of the Peano Axioms built out of the empty set, the set containing the empty set, the set containing the empty set and the set containing the empty set, and so forth. We get a nested sequence of sets such that the n-th set has cardinality n, and we can use the sets the same we we use the natural numbers. And the construction can even be extended to transfinite ordinals by carefully defining the limit of an upward chain of existing ordinals. What you're doing seems very similar to that.

I could add the word,"Let" to the assignments, I suppose; would that help? or do you have a suggestion, perhaps?

If I had the big picture of what you're trying to do, I could make suggestions. Typically when doing an inductive construction we define A_n+1 as some operation on A_n.

In programming we always say x := x + 1 but typically in math we typically introduce new (usually subscripted) variables.

Can't you just give me the big picture description of what you're trying to build?

 

[andrewr]

That doesn't make sense as an operation of set union.
if $A = \{x_a\}$ and $T = \{x_a, x_b\}$ then $A \cup T = \{x_a, x_b\}$.

You aren't taking the union of the two sets. You are using A as a set whose members are other sets and you are adding T to the list of the members of set A. I see nothing wrong with performing such an operation, but you shouldn't use the notation $\cup$ to symbolize it.

Some people might find the notation $A:= A \cup \{\{ T \}\}$ acceptable for that operation, but it would be clearer if you just said it in words.

I see, yes I missed the outer brackets. You're exactly right, and that's what I thought I was writing, and didn't. Thank you for the correction.

Likewise $T = T \cup \{x_a\}$ is the operation that adds $x_a$ to the list of the members of $T$.

Yes, it's the same issue.
I'm not trying to be a pain -- but your corrections are exactly what I am seeking. They are more important, in many ways, than the particular problem I am laying out.

I won't miss the braces again!

There are two+ reasons I am not saying it in words; And I am, of course, open to suggestions about how to work around these issues.

The first is that I have had several conversations where people seem totally unable to transform the words back into logical statements; Secondly, I wouldn't know the *precise* words myself to describe what I see pictorially in my mind.

Perhaps, I might try to explain in words and notation side by side; if that would help ?

Take for example the following question;
Can I subtract 1.0 from $0.999\bar{9}$ algorithmically and show the two are the same?

Consider: In decimal subtraction, the same result can be gotten by subtracting the MSDigit first (big endian style), so long as borrows are propagated correctly.

Now, I have said exactly what I am going to do -- but most people seem to not get what I said, or they will immediately trip over the concept of a finite unbounded computation, vs. an infinite one; (eg; at every step there is a borrow...and a remainder) or they will try to say -- that can't be done because of the halting problem -- or, since the idea is unusual, they will simply reject it as my being crazy, etc.

It ends up being a very long discussion... and typically fails.
People don't seem to notice that the halting problem doesn't apply to a fixed algorithm with a known input!
eg:

while True:

pass​

halt
​

And that it is necessary when comparing an infinite stream to another one (by subtraction as computers generally do) that the program Never halt if the streams are identical.
A string compare only halts when the subtraction produces a non-zero result.

I can demonstrate a few iterations of the algorithm for proving decimal 1.0 equal to the all 9's version -- and it will be very short compared to the previous paragraph.

$1.0 - 0.9999\bar{9} = 0.1 - 0.0999\bar{9} = 0.01 - 0.0099\bar{9}$ ...

The answer being computed in place would be the left hand side of each subtraction.
And I can easily make an algorithm for generating all future steps.

Considered in one way, there is a residual '1' digit at every step of the calculation, however looked at in another way (which I think is more proper) that '1' is a temporary that will be zeroed in the next step.

I don't know what to call the algorithmic necessity of a temporary or a register in computations which deal with sets of cardinality Aleph Naught. In English, I might try an analogy -- eg: the event horizon, but I have no vocabulary to describe it otherwise;
Things beyond the event horizon can't be accessed without fantasy errors creeping in...

Anyhow, that's what I am dealing with -- and the problem will get more interesting as I develop a vocabulary and become more rigorous. That's also why I want to do a formal strong inductive proof on sets of cardinality Aleph Naught. The strong inductive proof is a major tool for conveying the ideas I have to others. (And getting them correct in my own mind.)

I appreciate your help.

 

[andrewr]

That is false.

1 is a finite number. And if n is a finite number, n + 1 is a finite number. Therefore every element of the natural numbers is a finite number. (You can define finite any way you like, doesn't matter for this example).

But no set in 1:1 correspondence with the counting numbers is a finite number.

I don't think I said a set in 1:1 correspondence with the counting numbers is a finite number.
Construct the set of counting numbers by adding an element that is 1 greater than the greatest element already in the set; each set so constructed is *always* finite at every iteration of the algorithm.

Let A := { 1 }
Let N:= 1

1. Let N:= N+1
2. Let A:= A $\bigcup$ { N }
3. Goto 1

However, when the algorithm is allowed to run without end -- it is inductively the entire set of counting numbers which has cardinality Aleph Naught. Counting numbers CAN be constructed by *counting*.

I am not taking a limit, I am defining an ordered set algorithmically; or a sequence if you prefer.

I was just asking for a statement of where you're going. If I just start writing down a proof without saying even what general subject I'm in, I'm going to confuse people. I get the idea that you're trying to construct the von Neumann ordinals. They are a model of the Peano Axioms built out of the empty set, the set containing the empty set, the set containing the empty set and the set containing the empty set, and so forth. We get a nested sequence of sets such that the n-th set has cardinality n, and we can use the sets the same we we use the natural numbers. And the construction can even be extended to transfinite ordinals by carefully defining the limit of an upward chain of existing ordinals. What you're doing seems very similar to that.

Yes, it's similar -- but it's not the purpose of the exercise. The sets aren't empty as you'll notice. Also, I am using 1:1 correspondence and strong induction. There must *always* be one element in the set which has the same cardinality as the set.

IF this is so, then 1:1 correspondence confounds the idea of open and closed sets.
I can ask: Is Aleph Naught truly *infinte* or is it merely finite, unbounded?
How do you prove something is infinite?, is it not by 1:1 correspondence ?

If I had the big picture of what you're trying to do, I could make suggestions. Typically when doing an inductive construction we define A_n+1 as some operation on A_n.

Which I did, it's the adding of an element to the list which is 1 larger than the last one added. Since each list adds 1 element, the lists must be in 1:1 correspondence.

In programming we always say x := x + 1 but typically in math we typically introduce new (usually subscripted) variables.

I am unfortunately, a 20 year vetran programmer, boolean logic electrical engineer, and well -- I use different methods of computer solutions to the kinds of problems I typically solve. The tools you typically use aren't the ones available to me in everyday use.
I do solve the same problems, but my methods are typically graphical and algorithmic.

It's hard to shift paradigms without some intermediate practice -- which I hope to gain some of here. Feel free to take what I wrote, and give a different mathematical description of it -- I'll examine it, and if I can follow it -- I'll emulate it.

Can't you just give me the big picture description of what you're trying to build?

I'll have to think about it for a while before I can put it into words; The proof is merely of the existence of an element of a given cardinality. If the proof is wrong, I want to know which step and precisely why; and whether this is a mistake is trivial (like the braces I omitted) or fundamental (the induction does not follow the formal requirements of an inductive proof.)

The proof is merely an exhibit to examine; that's why I am not really interested in explaining what I am trying to prove -- for I am interested in the proof itself, not really the result which I think will never be agreeable to anyone here.

 

[Stephen Tashi]

the result which I think will never be agreeable to anyone here.

The average unusal thing is usually disagreeable to many people, here and elsewhere. Don't let that bother you - after all, this is just the internet.

I think your presentation will be more palatable if you make it clear that it relates to the theory of computation or a theory about manipulating infinite strings. The average reader will look at your steps and assume you want to say something about sets of numbers. I don't know the lingo of computability theory that well, but I'm sure it has one.

 

[andrewr]

O.K, I think, Thanks to Stephen Tashi ! That I finally at least have an OP which generates the set I wanted to generate.. So, here it is one last time (hopefully the last time); and perhaps the moderators will allow an edit of post #1, to include a link down to the more sensible O.P.

--------------------------------------------------------------

I am trying to grasp what is computable, and not computable, in an algorithmic sense when dealing with sets of cardinality Aleph Naught. I will be (for the most part) dealing either with place holders for numbers (unknowns like x) to see how a set can be organized on a Turing tape (or modern infinite stream) -- or decimal representations of numbers.

Hence, there are two things I will be dealing with -- infinite strings of characters on tape (decimal representations), and set theory.

The first example set is intended only to decide on how to approach inductive proofs, and what will be acceptable as a properly formed strong induction proof, and what is not. I am out of practice, and need some assistance in getting the steps of a strong inductive proof correctly written.

To begin with: I'm going to construct an example set -- and I will over-specify the set as an ordered set; The ordering is not necessary to the questions I wish to answer, but it is convenient to my way of thinking; you may discard the ordered nature of the set and treat it unordered if you wish to be an advanced auditor of the thread...

For the purposes of discussion, the | | operator means cardinality, since the P.F. does not support the more explicit symbols available in the AMS Tex package.

Start with:
Let A := { }
and
Let T := { }
and
Let n := 0

The set being constructed is called "A", "T" is a temporary used to construct set A, and n is an iterator counter for doing strong inductive proofs with, later.

Now to construct the set:

1. Let T := T ⋃ { x_{unique_index} }
2. Let A := A ⋃ { T }
3. Let n := n+1
4. Test := True if ( |T| = |A| ) and if ( T ∈ A ) else Test:= False
5. Goto 1.

The Algorithm at each iteration (step 4), will yield a pattern:
n=1, A = { {x_a} } , T ={ x_a }, Test=True
n=2, A = { {x_a}, {x_a,x_b} }, T= {x_a,x_b}, Test=True
n=3, A = { {x_a}, {x_a,x_b}, {x_a,x_b,x_c} }, T={x_a,x_b,x_c}, Test=True
n=4, A = { {x_a}, {x_a,x_b}, {x_a,x_b,x_c}, {x_a,x_b,x_c,x_d} }, T={x_a,x_b,x_c,x_d}, Test = True
... etcThe ordering of the set A is the order in which the elements were added algorithmically, eg: by cardinality of the subsets. The first subset inserted has the smallest cardinality.

Now, I am going to do an arbitrary strong inductive proof that I think can be seen by inspection; but I am wanting to verify how such a proof is done.

The base case is: for n=1, ∃ y ∈ A : |y| = |A|
For case n+1, exactly one element is added to T, and one element added to A, hence
There is a 1:1 correspondence between what was added to T and to A. (1 element each).
∴ for every iteration: ∃ y ∈ A : |y| = |A|

Which means, for all sets constructable by iteratively adding one element in this fashion, that there always will exist at least one element with the same cardinality as the set it was added to. The value of n plays no role in the construction of the set, but only serves to demark step n and n+1 in the inductive proof. The actual proof is based only on 1:1 correspondence of elements.

Now, does anyone see a problem with what I have done using strong induction?
Eg: is the proof *written* validly or not? (The result is not what I am asking about, just the construction of the proof.)

 

[SteveL27]

Test := True if ( |T| = |A| ) and if ( T ∈ A ) else Test:= False

Just a quibble here, not sure if it's relevant to what you're doing. How do you determine if |T| = |A|?

In the infinite case, in order to determine if two infinite sets have the same cardinality you have to examine every possible function between them to see if it's a bijection. Is that computable? There are uncountably many functions between two infinite sets. Is this a concern?

 

[Stephen Tashi]

Now, I am going to do an arbitrary strong inductive proof that I think can be seen by inspection; but I am wanting to verify how such a proof is done.

The way to begin a proof is with a statement of what you intend to prove. That statement is missing.

The base case is: for n=1, ∃ y ∈ A : |y| = |A|

That's OK if the reader understands that 'A' changes as 'n' changes. Computer programmers would understand it by referring to the initialization step in your algorithm. I think mathematicians would disapprove of the ambiguity in notation. They would prefer each different 'A' to have a distinct symbol, such as A[1], A[2],...

For case n+1, exactly one element is added to T, and one element added to A, hence
There is a 1:1 correspondence between what was added to T and to A. (1 element each).
∴ for every iteration: ∃ y ∈ A : |y| = |A|

To use (weak) induction, case n+1 should refer to situation of case n and use the fact that whatever is to be proven is true at case n. I don't see that you mentioned case n.

To use strong induction, case n+1 refers to the fact that whatever to be proven is true for all the cases 1,2,.. n. I don't think you need strong induction.

 

[andrewr]

Just a quibble here, not sure if it's relevant to what you're doing. How do you determine if |T| = |A|?

In the infinite case, in order to determine if two infinite sets have the same cardinality you have to examine every possible function between them to see if it's a bijection. Is that computable? There are uncountably many functions between two infinite sets. Is this a concern?

I've never heard that every possible mapping function had to be examined, before.
My understanding is that listing a single 1:1 mapping between the two sets is sufficient to show they have the same cardinality (I'm presuming no redundant elements); So I am implicitly taking as an axiom, that any 1:1 correspondence may be re-ordered (mapped) into any other 1:1 correspondence that can be constructed.

If this is wrong, do you have a concrete example of a set that is a counter-example ?

I can't examine entire swaths of set theory at my level, and without tracing out all steps of a proof inductively constructed; I'm not going to be certain the idea applies -- so, if you want assent from me, keep it simple. ;) or perhaps wait until I have developed the ideas here enough to point out an analogy of some kind.

Regarding the un-countability of all possible mappings; that will become important, I think, later in the discussion. That seems, intuitively, an issue of constructing permutations of a list/ordered set;and can't be tackled without discussing character encoding of simultaneous infinite lists on a Turing tape/stream.

 

[andrewr]

Just a quibble here, not sure if it's relevant to what you're doing. How do you determine if |T| = |A|?

In the infinite case, in order to determine if two infinite sets have the same cardinality you have to examine every possible function between them to see if it's a bijection. Is that computable? There are uncountably many functions between two infinite sets. Is this a concern?

There is a second way that I can answer your question.
Georg Cantor is the one who claims 1:1 correspondence means two sets are the same size.
He does not restrict, as far I as I can tell -- and I have asked others -- this axiom to infinite sets. He claims that it works for finite sets as well -- and his method is an extension of this basic trait of finite sets to "infinite" sets.

Sets, by their nature (as Stephen Tashi mentioned) do not allow redundant elements.

In any example, where the two sets have finite elements -- cardinality can be found by counting the number of elements in each and comparing the number; AKA, indexing them with an integer subscript and comparing the highest valued subscript in each set and seeing if they are the same.

If it were possible for two sets having the same cardinality by counting to NOT be in 1:1 correspondence, then there must be a 1 to many, or many to 1 relationship within those two sets. Such a relationship is unaffected by adding more elements; and therefore such a statement would disprove that 1:1 correspondence correctly identifies sets of known finite cardinality; and since infinite cardinality is made up of subsets of finite cardinality -- infinite sets could never be guaranteed to be in 1:1 correspondence either.

This violates Georg Cantors axiom for infinite sets; and hence, your potential disagreement would be with an axiom implied by my using the cardinality "Aleph Naught" at all.

-------------------------------
Now: A direct answer to your question in terms of what I did.

My (attempted) proof, at every finite subset constructed of the final set -- is *also* countable; and hence, you may *also* verify the cardinality of every finite set by counting.

However, Since a counting number is finite but unbounded, it can't be used to state the cardinality of a set which has the property that for every finite cardinality subset, there is another subset of larger finite cardinality; for no finite counting number is the largest possible finite counting number (by definition).

That's why I chose to use 1:1 correspondence in the proof.

 

[andrewr]

The way to begin a proof is with a statement of what you intend to prove. That statement is missing.

Yes and No.
I didn't just say QED at the end -- but gave a statement of what was proven.
Hence, I can copy that statement to the start of the proof to show what I'm going to prove -- it's sort of redundant; but OK, I can do that.

Regarding the mutability of A, which is being constructed, you said:

That's OK if the reader understands that 'A' changes as 'n' changes. Computer programmers would understand it by referring to the initialization step in your algorithm. I think mathematicians would disapprove of the ambiguity in notation. They would prefer each different 'A' to have a distinct symbol, such as A[1], A[2],...

I'm sure that's the case also; but that indexing is also a problem -- for there is no infinite index -- but I am constructing an infinite list of A's. When I show the examples of iterations of 'A' mutations, I decided to make the sub-elements have letter indexes for the same reason.

If it is more proper to say A_a ... A_$\aleph$, I suppose I could do that -- but, I'm not sure how the mathematician would understand why the sequence ended in aleph naught; I simply don't know how to subscript them un-ambiguously.

That brings up another problem...
If there is no legitimate way to subscript them but there is a way to compute such a set -- that seems to say Mathematical notation is deficient. And if Georg Cantor used Mathematical notation -- that would suggest there are some things he couldn't have proved that are computable... I don't like that idea/fantasy/nighmare.

To use (weak) induction, case n+1 should refer to situation of case n and use the fact that whatever is to be proven is true at case n. I don't see that you mentioned case n.

To use strong induction, case n+1 refers to the fact that whatever to be proven is true for all the cases 1,2,.. n. I don't think you need strong induction.

I'm not quite sure I follow the distinction you are making.
There appear to be two different ideas about what weak/strong induction is in the literature, and I may have picked the wrong word to use in a mathematical context.
There is the idea used to differentiate an informal induction (eg: typically used outside mathematics -- philosophy, perhaps?) which is called weak induction; and the words "strong induction" in that sphere of discourse refers to a mathematical kind of proof.

Within mathematics there appears to be a subtlety that you have mentioned; and I'm not quite sure what the distinction is.

It would seem to me that weak induction, given a base case, and the relationship for n-->n+1, would show that what is proven is true for all cases for it has to be true for n=1, and n+1, and n+1+1, etc.

eg: in mine, it is true at every step that an element exists within A that has the same cardinality as A; So it is true for all A.

Did I miss something? or do you mean that I could downgrade to weak induction, although strong induction would still hold?

-----------------------------------

The missing n may be just a wording/notation issue.
I'm looking here:
Mathematical induction weak and strong

weak induction:

Weak induction is used to show that a given property holds for all members of a countable inductive set, this usually is used for the set of natural numbers.

Weak induction for proving a statement P(n) (that depends on n) relies on two steps:

• P(n) is true for a certain base step. Usually the base case is n=1 or n=0
  
• P(k)$\Rightarrow$ P(k+1). That is, given that P(k) is true, P(k+1) is also true.

If these two properties hold, one may induce that the property holds for all elements in the set in question

I gave a base case. A_a := { {x_a} }
And in that case, the statement is true that: ∃ y ∈ A_a : |y| = |A_a|

Then I gave an operation to perform, eg: add 1 element to T_last, and add T_present as another element to A_last.

This operation maintains the relationship: ∃ y ∈ A_present : |y| = |A_present| because a set in 1:1 correspondence with another set, when 1 new unique element is added to each set, then the newly created sets must still be in 1:1 correspondence for the new elements are in 1:1 correspondence -- and this is true regardless of how many elements (n) were in each set originally.

But given the inability of an integer index to reach all the way to cardinality Aleph Naught, I don't see how it is appropriate to mention n explicitly for anything but a finitely countable set. So, how would you overcome this notational problem ?