- #1

andrewr

- 263

- 0

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 [itex]\bigcup[/itex] "x"

2) A = A [itex]\bigcup[/itex] T

3) n = n+1

4) Test if |T| ?= |A| and T ?[itex]\in[/itex] 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, [itex]\exists[/itex] y [itex]\in[/itex] A : |y| = |A|

For case n+1, exactly one element is added to T, and one element added to A, hence:

[itex]\exists[/itex] y [itex]\in[/itex] 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...) -- [itex]\exists[/itex] y [itex]\in[/itex] A : |y| = |A|

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

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 [itex]\bigcup[/itex] "x"

2) A = A [itex]\bigcup[/itex] T

3) n = n+1

4) Test if |T| ?= |A| and T ?[itex]\in[/itex] 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, [itex]\exists[/itex] y [itex]\in[/itex] A : |y| = |A|

For case n+1, exactly one element is added to T, and one element added to A, hence:

[itex]\exists[/itex] y [itex]\in[/itex] 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...) -- [itex]\exists[/itex] y [itex]\in[/itex] A : |y| = |A|

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

Last edited: