A cardinal tweak

This is a very rough draft that I may withdraw.

---

Hello. I tried to print "alef null" properly, but the system refuses to permit it. Hence the naught subscript appears in front of the alef, rather than behind it, as normally happens when one places the HTML subscript code after the symbol. I experimented by placing the subscript command in front of the alef character and got two subscripts to the front, as you (maybe) see here: ₀א ₀. I then tried another command behind the alef and got this absurdity: ₀א ₀₀ .

---

I propose a minor modification of the foundations of transfinite and finite arithmetic.

ω - 1 = א ₀. That is, ω is the set containing every natural number, so that it is not one of the naturals on ground that no set can be a member of itself. ω is an ordinal because any member of ω is regarded as less than ω and because there are infinite sets that are "larger" than ω. So א ₀ is Cantor's first transfinite cardinal number.

For notation consistency, I write N as a name for ω and N as a name for א ₀ . We have N < R, which is a name for the cardinal number of the reals.

It has become a convention to write that 1 + ω = ω , but ω + 1 =/= ω . The justification is that, as an ordinal which has lower cardinality than other infinite sets, there must logically exist such an entity.

My suggestion is that we drop N (aka ω) as the standard reference set for א ₀. Instead I recommend N X ∅ such that x =   < k, ∅ >  ∈ N X ∅ . So one can say that N has the cardinality of N X ∅ , which then defines א ₀, which I write as N.

Alternatively, I propose that we define א ₀ as N X N so that the ordered pairs are simply two identical integers. This way, using the von Neumann definition of N, every element will be contained by a successor.

We then define the addition of cardinal numbers, finite or infinite, according to their reference sets.

Obviously if N + 1 means N ∪ { ∅ }, then N + 1 = N.

Well, we may however observe that N ∪ 1', where 1' is not an element of N but of, say, N X ∅ , then we may define the addition of a finite element/set (as in the ordering of numbers which are sets of lower numbers) that is in one-one correspondence with the ordinal { ∅ }. That is, 1', being defined as < { ∅ }, ∅ > is in the same ordinal position as 1.

Now 1' could as well represent some irrational, as no irrational is a member of N.

From this, we see that addition of cardinal numbers requires that we assure that X ∩ Y = ∅ .

So N ∪ 1' = N + 1' = 1' + N. Conversely, N + 1 = 1 + N.

This idea is quite minor, as the use of such a ruse to ensure that X ∩ Y = ∅ is standard. But I feel that this tweak is an improvement of the current practice.

So if we wish to express א ₀ + א ₁ (whatever set that might be), the addition operation requires that

א 0 ∩ א 1 = ∅ .

This idea might (I'm hazy on this) interfere with the ordinal structure of the set universe as spelled out so well in NBG.

Because the continuum hypothesis (is there an "actual infinity" that warrants being tagged with an infinite cardinal number between N and P(N) ?) is independent of axiomatic set theory, I suppose we could risk the above described process.

So N + N' = 2N, where the underline expresses that the last is to be considered a cardinal number. N + R' does not permit multiplication, of course. But N x N', written N² is bijective with N X N' or N X N. Notionally, it would be better form to write 2'N.

Note that the cardinal numbers follow arithmetical rules, not per se the sets with which they are bijective. That is, we commonly write N² when we should, to be exact, write N².

One more point: The null set contains nothing, and so has no cardinality. We don't wish to have ∅ because, say, N ∪ < ∅ , ∅ > is bijective with N + 1', which we may wish to avoid.

On Schroeder-Bernstein

This offering is quite old, and I have since attempted what may be a better line of attack. Might be on the Footnotes to Plato blog.

Alternate proof

of the Schroeder-Bernstein theorem

Draft 2

The following proof of the Schroeder-Bernstein theorem is, as far as I know, new as of April 2006. Notation: "cardA" denotes the cardinal number of a set A. "<=" means "less than or equal to." "~" means "equinumerous to." 

Schroeder-Bernstein theorem: If, and only if, A and B are sets such that card A <= cardB and card B <= card A, then cardA = cardB.Proof:
Remark: We grant that the transitivity of subsets is established from axioms. That is, A Í B Í C implies A Í C. Further, for nonempty sets, we accept that if A Ì B, then B Ì A is false. This follows from the definition of subset: for all x, x element of X implies x element of Y. But, if A is a proper subset of A, then, for some b, b element of B implies b is not an element of A. Hence B does not fit the definition of subset of A.
We rewrite cardA <= cardB and card B <= card A, thus:
A ~ C Í B and B ~ D Í A
If
Suppose A ~ C = B. Then we are done. Likewise for B ~ D = A. So we test the situation for nonempty sets with: A ~ C Ì B and B ~ D Ì A. (We note that if C ~ D, then A ~ B, spoiling our interim hypothesis. So we assume C is not equinumerous to D.)
We now form the sets A U C and B U D, permitting us to write (A U C) Ì (A U B) and (B U D) Ì (A U B).
We now have two options:
i) (A U C) Ì (A U B) Ì (B U D) Ì (A U B)
This is a contradiction since A U B cannot be a proper subset of itself.
ii) (A U C) Ì (A U B) É (B U D) Ì (A U B)
Also a contradiction, since B U D cannot be a proper subset of A U B and also properly contain A U B.
Only if
We let B = C and D = A.

---

This proof, like the standard modern proof, does not rely on the Axiom of Choice.

---

An algorithm to imply the set of reals

There should be a superior version of this paper somewhere on one of my blogs, possibly on Footnotes to Plato.

---

I have reconsidered my initial idea that the algorithm I give proves non-denumerability of the reals, an idea which I based on the fact that there is no n for which a cellular diagonal exists that intercepts every row of cells. However, despite intuition, it does not immediately follow that no such diagonal exists for the infinite set.

---

An algorithm to imply the set of realsWe present an algorithm for "constructing" the entire set of reals and find that our intuition suggests that no diagonal can exist, which accords with Cantor's proof.
Cantor's diagonalization proof says that if it were possible that all reals were listed, then one could create an anti-diagonal number from the diagonal that intersects all the listed numbers. Hence, no such diagonal exists and the set of reals is not 1-to-1 with the set of naturals.
However, we are assuming that there is a set N containing all naturals. We are also assuming that because a finite n x n square always has a (non-Pythagorean diagonal of n cells) that intersects every row, then the same holds for the tiled quarter-plane.
However, the infinity axiom says that N exists, in which case we may say that the set of X axis integers is 1-to-1 with the set of Y axis integers, and further that the cellular diagonal with a cell vertex at (0,0) has cardN and intersects every horizontal string of cells bounded by y and y+1. In that case, we may use Cantor's argument to say that the reals can't be mapped 1-to-1 onto this tiling.
Interestingly, our algorithm for constructing all the reals intuitively says that such a set has no diagonal. But, that intuition is simply an intuition until we apply Cantor's proof and the infinity axiom.
We write an algorithm for determining the set of reals, thus:
We have the set of 1x1 square cells in a quadrant of the Cartesian grid. Each square is eligible to contain a digit. We consider only the horizontal strings of cells.
Suppose we use a base 2 system. We begin at step 0 using 2 consecutive spaces and obtaining 4 possible combinations, to wit: 00, 11, 10, 01. For step 1 (3 spaces), the number of combinations is 2*4 and for step n the number of combinations is 2ⁿ⁺².
At lim_n->inf. 2ⁿ⁺², we have established all base 2 infinite digit strings, expressing the entire set of reals greater than an arbitrary j e Z and less than or equal to j+1.
Remark: Our algorithm does not compute reals sequentially. It only computes 'pre-reals,' since a real is defined here as an infinite digit string. No element "materializes" prior to the entire set's establishment at (denumerable) infinity.
The algorithm above requires that for any step n, the set of digit strings is a rectangle n2ⁿ⁺².
But lim_n->inf. n/2ⁿ = 0, meaning the rectangle elongates and narrows toward a limiting form of a half-line.
For an integer diagonal to include an element of all horizontal digit strings, we must have a square of n columns and n rows. But such a square of the reals is never attainable. It would then seem safe to say that the set of reals, expressed as infinite digit strings, has no diagonal, which is equivalent to saying the set of reals is non-denumerable.
However, our intuition that the set of reals so constructed should have no diagonal is provable by agreement to the infinity axiom, which permits the cardN diagonal, and by Cantor's anti-diagonal result.
It also follows that no exponentially defined set of tiles n x kⁿ has a cellular diagonal at the tiling algorithm's infinite limit.
On the other hand, a tiling defined by n^k can be said to have k cellular diagonals, such that collectively the k diagonals intersect every horizontal cellular string. It then can be shown that such a tiling is one-to-one with N.
Interestingly, the power set of any n e N has card2ⁿ, which corresponds to step n of our algorithm, in which we have a set of 2ⁿ⁺² pre-reals.
Additional remark:
Lemma: Any set with lim_n->inf kⁿ elements has the cardinality of the reals, with k =/= 0, -1, 1 and k e Z.
Proof:
The set of reals is 1-to-1 with a set that has lim_n->inf 2ⁿ elements. Hence the cardinality of each set is identical. Similarly, the algorithm above can be rewritten as ckⁿ, with c a nonzero integer constant, meaning that all real digit strings are established at lim_n->inf ckⁿ.
Theorem: Some non-enumerable reals can be approximated with explicit rationals to any degree of accuracy in a finite number of steps.
Proof:
Construct n Turing machines consecutively, truncating the initial integer, and compute each one's output as a digit string n digits long. Use some formula to change each diagonal digit.
The infinite diagonal cannot be encoded as a Turing machine number, so it is not enumerable. Yet a computer can compute its approximation as a rational up to n. (The accuracy of this approximation is the same as the accuracy obtainable, in principle, for an enumerable irrational.)
Comment: The denumerable set of computables implies an extension of the concept of denumerability.
Justification:
We give these instructions for diagonalizing Turing computables:
Up to and including the nth diagonal space, follow this rule: if a digit is not 0, replace it with 0; if 0, replace it with 1. After the nth diagonal space, follow this rule: if a digit is not 2, replace it with 2; if it is 2, replace it with 3.
None of these diagonals is enumerable with respect to the Turing numbers. Yet we have a countably infinite set of diagonals. Hence, non-denumerability implies the existence of two denumerable sets of reals which are not denumerable with respect to each other.
If we diagonalize the diagonals, it is not apparent to me that this real is not a member of the computables.
Definition of choice sequence:
If f(n) gives a_n of cauchy sequence {a_n}, then {a_n} is a choice sequence if f(n) --> a_on+1 or a_1n+1 or . . . or a_mn+1.
Note i.Since a choice sequence is cauchy |a_m - a_n| <= 1/k for all m and n after some n_o. However, the rule for determining step n+1 means that more than one choice sequence is possible for every n after some n_o. That is, a choice sequence's limiting value must fall within an upper and lower bound.
Note ii: It may be that a_xn+1 is non-randomly determined. Yet, there exists an infinity of choice sequences such that the limiting value of {a_n} is an effectively random element of some infinite subset of reals (known as a 'spread') bounded by a least upper bound and a greatest lower bound.
Remark: Though choice sequences are primarily of interest to intuitionists, here we require that they be governed by ZFC.
Theorem: The question of whether the set of choice sequences contains an element with a non-enumerable limiting value is not decidable.
Proof:
We first prove (Lemma i) that within a spread (x,y), with x the GLB and y the LUB, a non-enumerable exists.
Use a diagonalization formula on the digit string outputs from the set of Turing machines, obtaining one non-enumerable real. Prefix, in turn, every rational digit string to this real and then move the decimal point to the front of each new string. Lemma i is proved.
So then suppose x and y are irrational enumerables. Rationals arbitrarily close to x from above and to y from below can be found.
Let x < p and q < y. So calling the choice sequence limit L, we have
Case i: (x < p < L < q < y).
Case ii: The possibility x < L < p exists, but then a smaller rational can be found between x and L.
Case iii: Likewise for the possibility q < L < y.
It is now straightforward that if L is a choice function limit, there is an effectively random possibility that L is enumerable or non-enumerable. This possibility is in principle undecidable.
Though probability laws suggest that the set of choice sequences includes a sequence with a non-enumerable limit, this suggestion is undecidable.

---

A geometric note on Russell's paradox

---

A lengthier discussion of Russell's paradox was found on my web page on vacuous truth before it vanished into the vacuum left by the demise of Geocities. It is there that I discuss banishing 'actual infinity' and replacing it with construction algorithms. However, such an approach, though countering other paradoxes, does not rid us of Russell's, which is summed up with the question: If sets are sorted into two types: those that are elements of themselves ('S is the name of a set that contains sets named for letters of the alphabet' is an example) and those that are not, then what type of set is the set that contains sets that are elements of themselves?

---

Insert: May 1, 2019: You may find more recent discussion of Russell's paradox either on this blog or on Footnotes to Plato. Also the 'vacuous truth' page has been found and is probably on Footnotes to Plato. But that kindergarten paper has also been superseded by more recent discussion.

---

Here we regard the null set as the initial set and build sets from there, as in:Step 0: { }
Step 1: { { { } },{ } }
Using an axiom of infinity, we can continue this process indefinitely, leading directly to a procedure for building an abstraction of all countable sets; indirectly, noncountable sets can also be justified.
In Russell's conundrum, some sets are elements of themselves.
So let us regard a plane as pre-existent (null space or some such) and regard Set sub 0, the empty set, as a circle surrounding nothing. Set sub 1 we picture as a concentric circle around set 0. Now those two circles express the element represented as {{ }}.
We might also say the two circles express the set that contains the element { }.
In that case, we may wish to say that the set {{ }} = the element {{ }}.
Suppose we establish two construction algorithms for sets of concentric circles. In algorithm A, the outer circle is a solid line, so that the null space container is not construed to be part of the set. In algorithm B, the outer circle is a dashed line, so that the null space container is construed to be part of the set.
At each step we add a new enclosing circle and require that it be either solid or dashed.
So as step n is taken to infinity, we find that the null space container vanishes. That is, the circles fill the plane.
In that case, the container is non-existent or undefined, so that the rule that requires that it be either part of the set or not part of the set is not applicable.
We have assumed that the initial circle surrounds something that is not an element -- as with { }. But we really must give a rule that says the inmost area is not an element. We could have a rule that permits not only the outmost but the inmost circle to be dashed. In that case the inner void would be considered a part (element) of the set. Though the void in a null set is, for sound reasons, not permitted to be construed as an element, it is still useful to see the relationship of admitting the inner void to Russell's paradox.

---

Russell's paradox is usually disposed of by resort to an axiom prohibiting a set from being an element of itself. But we can see that sets and elements can be identical except for the rule prohibiting a set belonging to itself.For example, element {{ }} in a set-building algorithm X is identical to the set containing the element { } in set-building algorithm Y.
It seems that the axiom while necessary remains questionable from the standpoint of logical consistency.

---

First published ca. 2000

Disjoint nondenumerable sets of irrationals

I was in kindergarten here. I've since been sent back a grade.

---

[This page went online Feb. 28, 2002.]
I wish to thank Amherst logician Dan Velleman, author of 'How to Prove It,' for not permitting any slack or insecure arguments. He has not vouched for the final version of this theorem and proof. The theorem itself is nothing special. But the proof is amusing in that it gives an inkling of how vast is the sea of irrationals with respect to the rationals.
Theorem: There exists a denumerable infinite family of sets such that each family member is a nondenumerable set of irrationals that is disjoint from every other member.
Proof:
We establish a monotonically climbing differentiable real function h(x), where x is continuous, and where the first derivative exists and is neither a constant nor a periodic (as in cos(ax)). We use only the integer values h(n) in our proof.
We denote a rational q's infinite decimal digit string by S_0 and its recurring finite substring by s. We see that the first digit of s, which has k digit places, recurs every (nk)th digit place. We denote the initial digit place of s by p. We pair p with d_2, which symbolizes a specific numeral digit. Initially, we are assuming a base 10 system.
We then establish the erase-and-replace function f by locating the h(n)th (p, d_2) and replacing d_2 with d_3.
The altered string, S_x, is forever aperiodic.
Example:
s = (01), k = 2, h = n^2
S_0 = 0.010101010101010101...
S_x = 0.210101210101010121...
We know the set of h functions is infinite and we presume that that set, and hence the set of f functions, is denumerable. So we form the indexed set U f_i.
However, this permits us to form a 'diagonal' function g, such that g is formed by the sequence f_1(1), f_2(2), f_3(3) ... ad infinitum. We then alter the g(n)th (p,d_1) by use of a third digit symbol, writing (p,d_3).
Since g is aperiodic and cannot be indexed, we have established a nondenumerable set of irrationals, which we denote R.
In general, we will write R_a to mean the set R derived from the rational q_a.
Indexing the denumerable set of rationals by j, we question whether R_1 intersection R_2 is nonempty. If empty, we proceed consecutively until we find -- if ever -- R_1 intersection R_j is nonempty.
In that event, we form a new function t_i and require use of (p, d_4) on the subset of R_j strings, denoted R'_j, that are identical to R_1 strings. R_j U R'_j we call T_j (which still holds if R_j U R'_j = R_j). We then proceed to the next instance where R_j intersection R_(j+n) is nonempty. Again, we insert digit d_5, obtaining T_(j+n).
Obviously, with a base 10 system, this procedure can be repeated 9 times.
As the number of digit places in s is irrelevant, we can increase our set of available digits with a higher base number system. In that case, we apply induction: If a base m system yields m-1 replacement digits, then a base m+1 system, yields m replacement digits.
With m e M = N, and N denumerable, we find that the family U( T_j) exists, where J = N, requiring that U( T) is denumerable and that for all j e J, n e N(T_j is disjoint from T_(j+n).
Proof concluded.
Remark: It is curious that the set of writable functions is considered denumerable because each expression is composed of a finite string of symbols. For example, 2 + log x, contains 9 symbols, including spaces. Hence, each such expression can be counted, and the entire set of such expressions must also be countable. Since our diagonal function is writable as g(n) = f_n(n), we have shown a nondenumerable subset of writable functions.

---

When algorithms collide

Nothing much to see here.

---

When algorithms collide: An infinite sum that isn't (or is it?)

This page went online Dec. 26, 2001

Peano, Hilbert and others devised space-filling curves about a century ago, helping to initiate the field of topology. So, from a topological standpoint, the result below is unremarkable.
Yet, philosophically it seems curious that the same structure can yield two different values.

---

It seems quite reasonable that an area under a curve is ever better approximated by summing areas defined by rectangular strips that fit the area ever more closely. At the limit of width w = 0, the area is defined as the infinite sum of vertical heights f(x) between x=a and x=b. This calculus approximation algorithm is standard.Yet it is possible to devise an algorithm which seems to yield a sum of y heights that clashes with the area algorithm.
We create a sawtooth path between some curve f(x) and a finite x axis interval by this means: Divide the interval by h, keeping h a positive odd integer. Then trace the path a to f(a) to f(a+1/h) to f(a+2/h) to a+2/h to a+3/h to f(a+3/h) ... to f(a+n/h) to a+n/h = b. The length of this path is always longer than the path connecting the discrete points of f(x). [There are more than two points between f(a) and f(a+1/h) for the sawtooth path but only two points for the other path.]
As h approaches infinity, the number of sawteeth approaches infinity. At the limit of h=infinity, the sawteeth have narrowed to the infinitesimal area f(x), where the route is presumably twice f(x). But the infinite sum of f(x) cannot be infinite if the area is finite (fits inside a finite square). Quite often, the infinite sum (the integral) is less than the continuous arc length for f(x).
So this would seem to indicate that the sawtooth function must be considered undefined at h = infinity.
The special case of the unit square makes this plain:
Use the unit square lying on the positive x axis between origin and x=1. Divide 1 by the odd (for convenience) positive integer h. Trace a sawtooth path from 0,0 to 0,1 to 1/h,1 to 1/h,0 to 2/h,0 to 2/h,1 and so on to 1,0. The sawtooth path length is h+2. As h approaches infinity, the sawtooth path length also nears infinity.
It would seem that at the limit, the 'infinitesimal entity' is twice the height f(x). The sum is the integral of f(x), which, by the fundamental theorem of calculus, is the area quantified as 1.
So that at infinity, if the sawtooth function exists, the sawtooth route length collapses to distance 1.
But would a long-lived or very speedy salesman traveling through all the points of a sawtooth curve find that the sawtooth route is optimal at infinity?
The area is rarely directly proportional to some x interval or radius. For example, take any finite radius circle and define its radius as 1. Then the area is less than the circumference. But take exactly the same circle and define its radius as 3, and now the area is greater than the circumference. Now make a sawtooth path through half of the same circle.
The salesman will find, as h increases, that his path length exceeds the area quantity for every h after some h=k. If the sawtooth algorithm is completable (an 'actual infinity' is agreed), then he would appear to find that the optimal route is the sawtooth route.
But, there is an infinity of areas that can be assigned to the semicircle. For every area quantity there exists a k after which h means that the sawtooth path length is longer.
This observation can be generalized.
So we conclude that the sawtooth function is either unbounded or undefined at h's infinite limit.
If we say it is unbounded, however, we would need to explain why we are forbidden to sum the f(x) heights.
As my son Jim, a Cornell topologist, points out, sawtooth functions are well-known for producing curves with infinite perimeters that contain a finite area, the Koch snowflake being a famous example.
Of course the issue here is not that such functions occur but that the logical conclusion of this particular sawtooth algorithm yields an anomolous result.

I haven't reviewed this particular post in a while. About a year ago I did update a version of this paper. It should be on one of my blogs. In fact there's a chance that the paper below is the updated version -- but "don't quote me on that."

Most Hamiltonian circuit families grow polynomially

Draft    

Statement (i) A method exists for obtaining a set of optimal 'traveling salesman' routes that is a member of a family that grows no faster than 0(In2)2ⁿ. (ii) However, even for large n, the method yields a polynomial rate for most sets of fields of nodes.Remark 1
We operate on a euclidean plane using nodes (cities) that can be specified with cartesian coordinates. We ignore graphs where all points lie on a line.
We adopt the convention that a route begins and ends at an origin city.
Remark 2
We assume that every road linking two cities is straight. This assumption is justified by the fact that a graph composed of curvilinear roads can be deformed into another one that preserves distances -- provided the roads don't cross outside the cities. This proviso is one of the criteria adopted below.
Proof
(i) Our aim is to show that a pretzel circuit can always be replaced by a shorter simple loop (Hamiltonian circuit).
We begin by showing that route backtrackings and crossings are unnecessary.
It is straightforward that if a route covers the same link twice, a shorter route can be drawn.
Suppose a node p is inside a field of nodes and the route enters p from the left, proceeds to x and then backtracks to p exiting toward the right.

                     x                                         n                  p                  m 

For non-trivial cases, there must exist some node m to the immediate right of p and some node n to the immediate left. Since mpx is not straight, it is longer than mx. Hence mxpn is shorter than mpxpn.Similar reasoning holds if p is outside a field.
We show that a route that intersects at a city can be replaced by a shorter route.
Consider any two two-dimensional fields of n nodes and have them intersect at point p.

       [F  I  E  L  D  1]          m          n                p         q         r        [F  I  E  L  D  2] 

The optimal route for the new field F₁ U F₂ will not cross at p because of the option mpq linking F₁ and F₂ and nr linking the fields, with nr < npr; or because of the option npr and mq.So then no route drawn on a graph need cross at a city.
We now show that a route that intersects outside a city can be replaced by a shorter route.
We have some field of four nodes.

        a                        d    b      x                  c 

The route acdba crosses at a non-nodal point we call x. Because bxc is not straight, bxc is longer than bc and hence abxcdxa is longer than abcda.Now we take another four-node field F₂ and attach it to the graph above. But we consider only two-point attachments, as we already know that one-point attachments are not optimal. So it is evident that if F₂'s route does not intersect x, the composite graph's route is shorter than if the alternative holds. An induction proof can be used for any number of fields, of course.
Now suppose we have a ray segment that holds more than two nodes (ignoring origin) adjacent to another ray with at least two.

                     a                       b                                           c                                               O       f       d   

How might we link these rays with an un-loop? Suppose cfdba. We will find that more than one link between two adjacent rays is wasteful. The proof is left for the reader.Also, we know that backtracking is wasteful and so we would not enter the vertical ray at b. In fact our route enters a ray at top or bottom node and leaves at bottom or top. Intermediate nodes can be ignored.
We will not always require that our rays have more than one non-origin node.
(ii)
Our aim is to show a means of obtaining the set of simple loops on any (non-trivial) field of nodes.
We take a field of n nodes and select any node as origin of a set of rays, with each ray drawn through one or more nodes in the field such that all nodes are intersected by rays.
Now our route must begin at origin and link every ray before returning to origin. At origin, we pick any ray to begin and (b = bottom node, t = top node) our path on that ray is determined: 0bt. However, after that there exists a choice. For ray 2 our path may be bt or tb and likewise for subsequent rays. Now if there are 2 nodes per ray, there are n/2 rays and there are about 2^n/2 acceptable paths.
Repeating this procedure for every node in the field, it will be seen that we have established the set of all n-gons, regular or irregular, that can be drawn on the field. Since any route that is not an n-gon is not a simple loop, such a route intersects itself at least once, which we know can be replaced by a shorter circuit.
The set of simple loops would then have an upper limit of n(2^n/2), though it is evident that n is much too high since changes of reference frame will slide nodes out of ray alignment and there is no reason to expect that an equal number of new alignments will occur.
Now suppose we have a field with all rays intersecting two nodes. If we add a point to that field but place it on a ray, the ray's interior point drops out and there is no significant change.
This tends to show that though a set of 0 2ⁿ may occur, it is very unlikely to occur on the next step. But, at this point, we do not rule out the possibility of a set of fields corresponding to an exponential growth rate 0(In2)2^m for m < n.
However, in most cases, a field's upper limit of acceptable routes is given by the number of rays per origin times the number of nodes in the field, or n²(n-1), which gives 3n² - 2n, or 0n², as the rate of change.
Remark 3
It seems apparent that a computer program needs to identify the nodes that form edges of the regular or irregular polygons associated with each node as origin and then to measure only edge distances. Hence we can expect that, for a random field of n nodes, the program will very likely, but perhaps not certainly, run efficiently.
Remark 4
It may be that, for some families of loops, a hard rate continues from n through infinity; or that a hard rate alternates with an efficient rate over infinity; or that the hard rate always zeroes out. The third statement would prove that NP=P.

---

Assuming that for most sets of fields P-time computer programs can be derived from our method, it may be that encypherment experts may wish to consider their options.

---

Primes up to 50,000

---

Freaky facts about 9 and 11

First published Monday, June 14, 2010

It's easy to come up with strange coincidences regarding the numbers 9 and 11. See, for example,

http://www.unexplained-mysteries.com/forum/index.php?showtopic=56447

How seriously you take such pecularities depends on your philosophical point of view. A typical scientist would respond that such coincidences are fairly likely by the fact that one can, with p/q the probability of an event, write (1-p/q)ⁿ, meaning that if n is large enough the probability is fairly high of "bizarre" classically independent coincidences.

But you might also think about Schroedinger's notorious cat, whose live-dead iffy state has yet to be accounted for by Einsteinian classical thinking, as I argue in this longish article:

http://www.angelfire.com/ult/znewz1/qball.html


Elsewhere I give a mathematical explanation of why any integer can be quickly tested to determine whether 9 or 11 is an aliquot divisor.

http://www.angelfire.com/az3/nfold/iJk.html

Here are some fun facts about divisibility by 9 or 11.

# If integers k and j both divide by 9, then the integer formed by stringing k and j together also divides by 9. One can string together as many integers divisible by 9 as one wishes to obtain that result.

Example:

27, 36, 45, 81 all divide by 9

In that case, 27364581 divides by 9 (and equals 3040509)

# If k divides by 9, then all the permutations of k's digit string form integers that divide by 9.

Example:

819/9 = 91

891/9 = 99

198/9 = 22

189/9 =21

918/9 = 102

981/9 = 109

# If an integer does not divide by 9, it is easy to form a new integer that does so by a simple addition of a digit.

This follows from the method of checking for factorability by 9. To wit, we add all the numerals, to see if they add to 9. If the sum exceeds 9, then those numerals are again added and this process is repeated as many times as necessary to obtain a single digit.

Example a.:

72936. 7 + 2 + 9 + 3 + 6 = 27. 2 + 7 = 9

Example b.:

Number chosen by random number generator:

37969. 3 + 7 + 9 + 6 + 9 = 34. 3 + 4 = 7

Hence, all we need do is include a 2 somewhere in the digit string.

372969/9 = 4144

Mystify your friends. Have them pick any string of digits (say 4) and then you silently calculate (it looks better if you don't use a calculator) to see whether the number divides by 9. If so, announce, "This number divides by 9." If not, announce the digit needed to make an integer divisible by 9 (2 in the case above) and then have your friend place that digit anywhere in the integer. Then announce, "This number divides by 9."

In the case of 11, doing tricks isn't quite so easy, but possible.

We check if a number divides by 11 by adding alternate digits as positive and negative. If the sum is zero, the number divides by 11. If the sum exceeds 9, we add the numerals with alternating signs, so that a sum 11 or 77 or the like, will zero out.

Let's check 5863.

We sum 5 - 8 + 6 - 3 = 0


So we can't scramble 5863 any way and have it divide by 11.

However, we can scramble the positively signed numbers or the negatively signed numbers how we please and find that the number divides by 11.

6358 = 11*578

We can also string numbers divisible by 11 together and the resulting integer is also divisible by 11.

253 = 11*23, 143 = 11*13

143253 = 11*13023

Now let's test this pseudorandom number:

70517. The sum of digits is 18 (making it divisible by 9).

We need to get a -18. So any digit string that sums to -18 will do. The easiest way to do that in this case is to replicate the integer and append it since each positive numeral is paired to its negative.

7051770517/11 = 641070047

Now let's do a pseudorandom 4-digit number:

4556. 4 - 5 + 5 - 6 = - 2. Hence 45562 must divide by 11 (obtaining 4142).

Sometimes another trick works.

5894. 5 - 8 + 9 - 4 = 2. So we need a -2, which, in this case can be had by appending 02, ensuring that 2 is found in the negative sum.

Check: 589402/11 = 53582

Let's play with 157311.

Positive digits are 1,7,1
Negative digits are 5, 3, 1

Positive permutations are

117, 711, 171

Negative permutations are

531, 513, 315, 351, 153, 135

So integers divisible by 11 are, for example:

137115 = 11*12465

711315 = 11*64665

Sizzlin' symmetry
There's just something about symmetry...

To form a number divisible by both 9 and 11, we play around thus:

Take a number, say 18279, divisible by 9. Note that it has an odd number of digits, meaning that its copy can be appended such that the resulting number 1827918279 yields a pattern pairing each positive digit with its negative, meaning we'll obtain a 0. Hence 1827918279/11 = 166174389 and that integer divided by 9 equals 20312031. Note that 18279/9 = 2031,

We can also write 1827997281/11 = 166181571 and that number divided by 9 equals 203110809.

Suppose the string contains an even number of digits. In that case, we can write say 18271827 and find it divisible by 9 (equaling 2030203). But it won't divide by 11 in that the positives pair with positive clones and so for negatives. This is resolved by using a 0 for the midpoint.

Thence 182701827/11 = 16609257. And, by the rules given above, 182701827 is divisible by 9, that number being 20300203.

Ah, wonderful symmetry.

A bit of trivia

Tests for divisibility by 9 and 11

If one adds the digits of a number and the sum is divisible by 9, then the number is divisible by 9. Similarly, if one alternates the signs of a multi-digit number's digits and the sum is divisible by 11, then the number is divisible by 11.Example
The sum of the digits of 99 is 18, which is divisible by 9. Likewise, the sum 1+8 is also divisible by 9.
The sum of the alternately signed digits of 99 is 9 + (-9) = 0, and 0 is divisible by 9.
And, of course, 99 = 9(11).
How do these tests of divisibility work?
This description is for people with no background in number theory.

Proposition I

A number is divisible by 9 (with a remainder of 0) if and only if the sum of its digits, in base-10 notation, is divisible by 9.
That is, if n is divisible by 9, the sum of its digits is divisible by 9 and if the sum of its digits is divisible by 9, n is divisible by 9.
So our method of proof can either begin with the assumption that n is divisible by 9 or with the assumption that the sum of n's digits is divisble by 9. Below we have chosen to assume n is divisible by 9. But, first some background.

What is base 10?

It is customary to use a place system for numbers of any base. The base-10 system, with its 10 digits, uses digit position to tell us what multiple of 10 we have.
When we write, say 231, this tells us that we are to add 200 + 30 + 1. Each place represents a power of 10. That is, 200 + 30 + 1 = 2 · 10² + 3 · 10¹ + 1 · 10⁰ (where any number with exponent 0 is defined as equal to 1).
If we wish to write 23 in binary, or base-2, notation, we first write:
1 · 2⁴ + 0 · 2³ + 1 · 2² + 1 · 2¹ + 1 · 2⁰.
Then, limiting ourselves to the digit set {0,1}, we write 10111, knowing that the place signifies a power of 2.

Sets of numbers differing by multiples of q

Now we want to think about some sets of numbers, each of which is divisible by some number n.For example, let's consider the series
{...-17, -10, -3, 4, 11...} where any two members differ by some multiple of 7.
As we see,
(-17) - (-10) = -7
(-17) - 11 = -28
Another such series is
{...-15, -8, -1, 6, 13, 20...}
where subtraction of any two numbers in the series also yields a number divisible by 7.
Once we know one member of such a set, we know them all. That is, the set is writable:
{-3 + 7k|k e K}, with K the set of integers.
It is customary to express such a set thus:
[-3]₇. We can also express this set as [-10]₇. In fact, in this notation,
[-3]₇ = [-10]₇
In general, a series denoted [n]_q is identical to the series denoted [n + qk]_q, where k is any integer.
The set [n]_q is known as congruence class n modulo q.
Note that
[0]_q = [0 + qk]. Every member of this series is divisible by q for all k. That is, every element of this series, when divided by q, equals an integer k.
[q]_q = [q + qk]. Every member of this series is divisible by q. That is, every member, when divided by q, equals k+1.
What happens if we add elements of [m]_q and [n]_q?
We have m + qk + n + qj = m+n + q(k+j), letting j be an integer.
If we set k+j to 0, this gives m+n, which we use to establish the series [m+n]_q = [m+n + qk]_q.
For example, we have [-3]₇ + [-1]₇ = [-4]₇,
which means,
{...-17,-10,-3,4,11...} + {...-15,-8,-1,6,13,20...} = {...-18,-11,-4,3,10,17...}
We see that -18 - 3 = -21, which is indeed divisible by 7.
By kindred reasoning we can show that it is possible to multiply an element from each of two similar series to obtain a third series similar to the other two. By 'similar' is meant a series in which elements differ by an integer multiple of q.

That is, [p]_q · [r]_q = [pr]_q.

Proof of Proposition I

Let d_n, d_n-1 ... d₁, d₀ represent the decimal expansion of some number N.Then, by definition, we have N = d_n · 10ⁿ + d_n-1 · 10^n-1+...+d₀ · 10⁰
[See explanation above.]
Since both sides of the expression are equal, each must belong to the same congruence class.
That is, putting N as a member of the series [N]_q means that the right side of the equation is also a member of [N]_q.
That is, [N]_q = [d_n · 10ⁿ + d_n-1 · 10^n-1 +...+ d₀ · 10⁰]_q.
Now our condition is that N be divisible by 9. In that case N is a member of the congruence class [0]₉. That is, [N]₉ = [0]₉. Likewise, the decimal expansion is also a member of [0]₉.
That is, [N]₉ = [0]₉ = [N's decimal expansion]₉.
Because [p+r]_q = [p]_q+[r]_q and [pr]_q = [p]_q · [r]_q, we may write:
[N]₉ = [0]₉ = [d_n]₉ · [10]₉ⁿ + [d_n-1] · [10]₉^n-1 + ... + [d₁]₉ · [10]₉⁰
Now we know that [10]₉ = [1]₉, since 10-9 = 1.
Hence we can substitute the number 1 for the number 10, obtaining
[0]₉ = [d_n]₉ · [1]₉ⁿ + [d_n-1]₉ · [1]₉^n-1+...+ [d₀]₉ · [1]₉⁰ ...
Obviously 1^m = 1. So we may write
[N]₉ = [d_n]₉ + [d_n-1]₉+...+[d₀]₉
which equals
[d_n+d_n-1+...+d₀]₉, which equals [N]₉, which equals [0]₉.
Since the sum of the digits is equal to congruence class [0]₉, it must be divisible by 9.
QED

Proposition II

A number is divisible by 11 only if the alternating sum of its digits is divisible by 0.That is, d_n - d_n-1 + d_n-2 etc. must equal a sum divisible by 11.
The proof for 9 can be used for 11, noting that [10]₁₁ = [-1]₁₁, since 10 - (-1) = 11. And it should be remembered that (-1)²ⁿ is positive, while (-1)^{2n ± 1}
is negative.
First published ca. 2002