A cardinal tweak
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: 0א 0. I then tried another command behind the alef and got this absurdity: 0א 00 .
I propose a minor modification of the foundations of transfinite and finite arithmetic.
ω - 1 = א 0. 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 א 0 is Cantor's first transfinite cardinal number.
For notation consistency, I write N as a name for ω and N as a name for א 0 . 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 א 0. 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 א 0, which I write as N.
Alternatively, I propose that we define א 0 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 א 0 + א 1 (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 N2 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 N2 when we should, to be exact, write N2.
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.
Wednesday, May 1, 2019
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.
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.
Alternate proof
of the Schroeder-Bernstein theorem
Draft 2The 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
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 2n+2.
At limn->inf. 2n+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 n2n+2.
But limn->inf. n/2n = 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 kn has a cellular diagonal at the tiling algorithm's infinite limit.
On the other hand, a tiling defined by nk 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 card2n, which corresponds to step n of our algorithm, in which we have a set of 2n+2 pre-reals.
Additional remark:
Lemma: Any set with limn->inf kn 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 limn->inf 2n elements. Hence the cardinality of each set is identical. Similarly, the algorithm above can be rewritten as ckn, with c a nonzero integer constant, meaning that all real digit strings are established at limn->inf ckn.
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 an of cauchy sequence {an}, then {an} is a choice sequence if f(n) --> aon+1 or a1n+1 or . . . or amn+1.
Note i.Since a choice sequence is cauchy |am - an| <= 1/k for all m and n after some no. However, the rule for determining step n+1 means that more than one choice sequence is possible for every n after some no. That is, a choice sequence's limiting value must fall within an upper and lower bound.
Note ii: It may be that axn+1 is non-randomly determined. Yet, there exists an infinity of choice sequences such that the limiting value of {an} 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
When algorithms collide: An infinite sum that isn't (or is it?)
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.
Most Hamiltonian circuit families grow polynomially
DraftStatement (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)2n. (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 mFor 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 F1 U F2 will not cross at p because of the option mpq linking F1 and F2 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 cThe 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 F2 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 F2'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 dHow 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 2n/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(2n/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 2n 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)2m 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 n2(n-1), which gives 3n2 - 2n, or 0n2, 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
