'Vacuous truth' step by step

We accept these four rules of standard mathematical logic:

1. If P is true and Q is true, then 'P implies Q' is true (takes a binary value denoted T).

2. If P is true and Q is false, then 'P implies Q' is false (takes the value F).

3. If P is false and Q is true, then 'P implies Q' is true.

4. If P is false and Q is false, then 'P implies Q' is true.

By setting up truth tables for these rules, one can see their reasonableness. For example, if we re-express P --> Q as ~P v Q, we see that the truth table is

    ~P      v        Q
 
1.  F                  T         T
2.  F                  F         F
3.  T                  T         T
4.  T                  F         T

Yet, rule 3 can strike people as odd. The statement may be called "true," but vacuously so.

So x e ∅ --> x e S always holds vacuously (and so is a tautology).

That is, if x e S, then rule 3 applies. But if ~(x e S), then rule 4 applies.

Note that this expression justifies the accepted concept that the null set is a subset of every set.

Observe that x e S --> x e ∅ does not necessarily hold. If x e S is true, then the asserted implication is false, by rule 2.

---

A curious result

In modern set theories, x e x is ruled out in order to avoid Russell's contradiction, which proves naive set theory to be inconsistent (a false theory).

We can use the fact that in modern theory, x e x is false to prove that x = x.

First we note that in a goodly number of modern logic systems, 'P --> P' is either an axiom, or immediately derivable from axioms. So we accept 'P --> P' and let P be the assertion 'x is an element of x' , or 'x e x'.

Thence, x e x --> x e x.

Proof:

-->

1a. x e x --> x e x

(1a) is true by rule 3, such that a falsehood implies a falsehood.

2a. so x ⊆ x

<--

3a. x e x --> x e x

4a. x ⊆ x

In other words, the implication arrow works in both directions. Or

5a. x e x <--> x e x

Well, here x is defined vacuously by its purported elements and so

6a. x = x

Note that x e x --> ~(x e x) is also true since, by rule 4, a falsehood also implies a truth. Still, the proof above holds, by rule 3.

Well, yes, but there is no set x such that x e x.

So are we allowed to say this non-set is defined by its purported elements?

Maybe we can get away with saying that a set that doesn't exist in some system even so exists as a non-entity in a larger sense.

Nonexistence has long been a philosophical puzzler, as one can see from Russell's 'A - B = 0 ' problem in his Theory of Descriptions. For more on the nonexistence issue, please see

Philosophy Professor Thomas C. Ryckman's excellent page
https://www2.lawrence.edu/fast/ryckmant/Russell's%20Theory%20of%20Descriptions.htm

We caution that this proof of 'x = x' would not be accepted in some logic texts before quite a bit of groundwork had been done.

The binary tree representation of the reals

Consider a binary tree that begins with 1 and 0 on the top horizontal line, whereby at every fork, the left node takes a 1 and the right node takes a 0.

Let us vertically list every stage with consecutive n's, in the usual order, so that for every n, we have 2ⁿ 0's and 1's on the nth horizontal.

At lim n -->inf. (that is at cardN or aleph_null, or being finicky, at ordN), we have the set of all real binary extensions, which, of course, is bijective to the set of all reals.

Thus at ordN, which we'll call the last step, there are two connected "actual infinities" on display: cardN for the vertical, and cardP(N), or 2^cardN, for the "bottom" horizontal [1]. So the ordNth horizontal contains 2^cardN 0's and 1's.

We see that there is a path from horizontal line 1 to the ordNth line that expresses any real binary extension, including those that are not finitely expressible (non-computables).

Now we can get a good intuition that, assuming the existence of the bottom line, the reals are well ordered. That is, for any finite path (or proto-real), that path is a member of a finite set where each element may be ordered as x < y or y < x, systematically until the entire finite set has been ordered. We may then apply mathematical induction to show that such ordering holds for any set with n-bit paths, where each such set holds 2ⁿ paths.

To wit, the induction basis:

Given a binary tree with path-length 2 bits, we have that:

Any path is a member of a set of 2² members, which implies that, given a binary tree of 3 bits, any path is a member of a set of 2³ members. This holds by inspection and by the structure of our binary tree.

Induction step:

Given a binary tree of path length n bits, any path is a member of a set with 2ⁿ members, which implies the same for n+1.

At this point, we remark that ordinary induction proves that if f(n) holds for f(n+1), then we know that our claim holds for any arbitrary finite n. Some see ordinary induction as implying "potential infinity," which simply means an unbounded finite recursion. Now if one follows a Cantorian line and argues that some successor operation on the positive integers holds for any natural number, then there is a set N -- of "actual infinite" size (cardN) -- that contains "all" these whole numbers. In that case, N -- or really, ordN -- exists by transfinite induction.

So it is clear of course that N is well-ordered. So R's well-ordering is strongly suggested by transfinite induction that accompanies in this case the ordinary induction for recursive sets 2ⁿ. That is, if R exists, then transfinite induction points from 2ⁿ n-bit paths to 2^cardN cardN-bit paths. (R's well-ordering can be proved definitively by other means.)

An objection might be that we cannot, at the ordNth step come up with an algorithm to do the ordering of the 2^cardN paths, though we can do so for any finite ordinal n. Yet note that the cardN-stage binary tree is a self-similar fractal. So if every finite path (1's to the left, 0's to the right) can be easily well-ordered, one would expect that the same, in principle, holds for the infinite fractal.

Appeal to the fractal nature of the binary tree might not persuade some, who would argue that simply because every finite set of 2ⁿ has a least element, it doesn't necessarily follow that the 2^cardNth set has a least element. But if we say that the sorting and ordering algorithm holds at every stage, then shouldn't it be allowed at the ordNth stage?

The fact that a constructive proof may not exist for the case of ordN --> ord2^cardN is, however, a problem for transfinite quantities in general. Something that seems to follow from a "Platonic" logic is drawn up short by the crowd from Missouri (the intuitionists, among others).

So in order to confirm that all the reals are represented and that a specific order is implied, we can cite transfinite induction to assert the well-ordering of the set of all paths. Of course, some may object to our "abuse" of transfinite induction.

The binary tree also says something about Cantor's continuum problem of whether there exists a cardX such that cardN < cardX < cardP(N) = 2^cardN = cardR. Note that we have the binary tree fractal -- or algorithm -- such that N --> R. So plainly any base number system can be used; i.e. a k-nary fractal where k is any positive integer will for any stage n, yield a set of kⁿ paths. So that k^cardN must equal 2^cardN.

So the cardinality of the reals can be "approached" (as n goes to infinity) by any kⁿ. This tends to suggest that functions that climb faster than such exponentials will not approach cardX. In fact, it's hard to think of a function other than kⁿ approaching the cardinal number of the paths of all the reals.

Because of its fractal nature, if we arbitrarily select any finite node on our k-nary tree and work downward, we get the entire k-nary tree, so that one gets nowhere with (lim n --> inf.) Kⁿ - j, as j vanishes in the limit. So we can't get a lower cardinality that way. If we try K^x such that x is not an integer, we won't successfully represent some fraction of paths.

That is, we get the impression that any such set X can't be approached "from below," which helps reinforce our acceptance of the combined result of Goedel and Cohen that the continuum hypothesis is independent of the axioms of standard set theories.

---

1. Sidelight: note that lim n--> inf. n/2ⁿ = 0, in accord with cardN/cardP(N) = 0.

A note on the continuum hypothesis

We can get a feel for why Cantor's continuum hypothesis is independent of standard set theory, both in the case of ZFC axioms and NBG axioms, by beginning with the fact that Cantor's theory, as modified by ZFC and NBG and other systems, implies the existence of non-specifiable numbers.

Cantor's diagonal proof requires that a real be definable as a denumerable infinite decimal (or n-nary) extension. From this he showed that listing the reals in some consecutive order yields a number that cannot be on that list. Hence, the reals must be non-denumerable, which he saw as a "larger" actual infinity than the actual infinity of the naturals. So a cardinal number is defined by equipollence with some representative set, such as N. CardN is not equipollent to CardR, or in Cantorian notation Aleph_null is equivalent to CardN.

So, for Cantor, the cardinal numbers should represent a discrete set of "infinite integers." He was unable to prove however that CardR = Aleph_1, the second infinite "integer" or cardinal number.

The general continuum hypothesis (GCH) is that only cardinals equipollent to power sets exist after Aleph_null, or cardN. For example, the reals are bijective with the power set of N, which reflects another proof that R is of a higher actual infinity than N. (Any proof or disproof of GCH would follow almost immediately from a proof or disproof of HC, in which R represents the real number line continuum [1a].)

Now consider that the Church-Turing thesis (which is a fundamental intuition or axiom) posits that any computation that can be done (whatever its practicality) may be put in Turing machine form. This certainly makes sense when one considers that we would expect that every mechanical, mindless computation can be encoded as a Boolean logic circuit. And any non-logical circuit would not reliably output a computation that could be used with other computations in coming up with another logical circuit that solves a problem.

So one can say that every Boolean logic circuit, can, following a similar procedure for a Turing machine, have every gate given a unique integer number. We then encode these numbers, perhaps in a Goedelian fashion. So then, every Boolean logic circuit is assigned a unique positive integer (it is irrelevant whether more than 1 circuit yields the same output). For both Turing machines and Boolean circuits, the initial conditions, including input code, are included in the encodement by what may be called a Description Number.

In that case, every computable number is associated with one or more unique integers. We shall call this the set of computables, or K. K is infinite, because, among other things there is some description number k that encodes an algorithm for yielding any integer. So K is an infinite subset of N, meaning that cardK = cardN.

We shall call K's complement W, the set of noncomputables. No w e W can be specified or identified, though the Axiom of Choice can be used to manipulate W in standard set-theoretic ways. And of course K U W = R. (So most of the reals have only a ghostly reality.)

Well, any subset of K is either bijective with N or with n e N. A mixed set, such as K' U Y' -- in which K' and Y' are subsets of K and Y -- is either bijective with N, bijective with R or is equipollent to card(K' U Y') but not to K or R. But how can we determine Y'? Well, at least we know that Y' is bijective with Y/K or K/Y. The latter case is possible but not germane to the argument, which is that the mixed case is equivalent to the case Y being composed of all non-computables.

So to the point: If cardN < cardY < cardR, we must find a subset X of Y that is neither bijective with K nor R. Likewise, to show that no subset of Y is bijective with K, we must exclude all subsets of Y such that one has cardY.

But of course a set is defined by its elements. What to do when each element is individually undefined? We know w e W can express some magnitude on the real line, conventionally between 0 and 1; the trouble is, in principle, no one can hone in on that real point. [1]

From this we can see intuitively that the probability of proving or disproving GCH is virtually nil. So we can see the enormous plausibility of the combined results of Kurt Goedel and Paul Cohen that GCH is independent of the axioms of modern set theory -- without actually examining their rigorous proofs.

Interestingly, the WOT version of AC requires that anything properly defined as a set can be well-ordered, as in a nested sequence of least elements descending to a secure bottom (of the well). So the reals are well-ordered, even though we know of no algorithm to yield an element by element well-ordering. So all the k's are in the well-ordering of R. Because R is bijective with the power set of N, proving GCH requires proving that Y is never bijective with any element of p e P(N). Note that if we exclude all members p that are bijective with either N or P(N), we would still be unsure that the result is the null set without the independence proofs of Goedel and Cohen.

---

1a. The continuum is an ancient concept and so is often taken to mean the mapping of all the positive integers onto a finite line segment. That is, the continuum is often identified with N mapped onto a finite magnitude, rather than the set R being so mapped. So then, the set of reals may be said to be the power of the continuum, or R is bijective with P(N).

1. See Kurt Goedel, 'What is Cantor's continuum problem?' in Philosophy of Mathematics, selected readings, 2d ed., Paul Benacerraf and Hilary Putnma, eds. (Cambridge 1984). In particular, see Page 278.

If A infinite, A X A ≈ A

---

Use my proofs at your own risk. I may be wrong. Please notify me of error.

---

Remarks
u ≈ v says u is equinumerous with v.
The cross product A X A is also written A².
For the sake of completeness, if that is wanted, we note that for A finite, the matrix A X A is rarely equinumerous with A. For A ≈ n e N (the Natural Whole Numbers), A X A ≈ n² in N such that n <= n².
The lower case e is used for the element symbol.

---

0.
If A infinite, whether denumerable or not, A X A ≈ A.

To prove

---

1.

A X A may be represented as a matrix, such as the case of Quad I

of the Complex plane, in which a complex point may be represented by 2 partially ordered reals.

It is the sets that are important;

the matrix picture gives a "false visualization" typical of mathematics,

as in the false visualization of a line in the Euclidean plane.

---

2.
By the Axiom of Choice, any set can be put into a well-ordering.

That is, any subset has a least element. Thence, we have x < y or y < x or x = y.

---

3.

We call R_i a row of the matrix such that i is the i-th well-ordered element of A. Note that every pair in R_a has the coordinates 〈a,y〉 such that a is held constant

and y permitted to vary 1-to-1 with x e A.

In fact, y gives the column coordinate such that y is the y-th member of the well-ordering of A.

---

4.
R_a ≈ A.

Follows from 〈a,y〉as described in 3.

---

5.
R_a ≈ R_b

Follows from 〈b,y〉with b constant, making a straightforward 1-to-1 correspondence.

---

6.
∪R_i = A²

Self-evident.

The subscript i is a well-ordered

member of A, and so denumerability is not implied.

---

7.
Any finite subset of ∪R_i ≈ A.

Follows from 5.

---

8.
∪R_i = ∪X_n, where X is a finite subset of ∪R_i and n e N

Exists by definition.

---

9.
(All n,m e N) (X_n ≈ R_a ≈ X_m).

Follows from 5. and 8.

---

10.
∪R_i ≈ R_a

Follows from 9.

---

11. R_a ≈ A

Substitution.

---

12.
A ≈ A²

Substitution.

---

13.
Aⁿ ≈ A

Follows from induction on A and n.

---

(14.
A^ℕ\0 ≈ A

We can use transfinite induction, not defined here, for 13.)

Schroeder-Bernstein sans usual conditions

Draft. Please notify me of any error.

---

Herewith, the Schroeder-Bernstein theorem without the pigeonhole principle and without explicit cardinal numbers.

We use the dot notation for "and" as well as the logical product of u and v expressed uv or of (u) and (v) expressed (u)(v). The symbol ≺ means "less numerous than," which certainly implies the concept of cardinality. The symbol ≺≈ means "less numerous than or equal to." The symbol ~ means "not."

The notation of statement 0 seems to imply the conclusion. Yet,  sets can be peculiar things. Formal proof that the conditions for x and y imply that they are bijective is required.

---

0.
x ≺≈ y • y ≺≈ x  • --> • x ≈ y

To prove.

---

1.
x ≺ y • x ≈ y

Assumption

---

2.
x ≈ r ⊂ y • ~(r ≈ y)

Same as 1.

(The proper subset r is chosen such that it is not bijective with y,

which could happen for r infinite.)

---

3.
r ⊂ y • ~(r ≈ y) : x ≈ y

Assumption

---

3a.
y ≈ s ⊂ x • ~(s ≈ x)

Assumption

---

4.
x ≈ r • ~(r ≈ y)

2, 3

---

5.
~(x ≈ y)

MP on 4

---

6.
~(x ≺ y • x ≈ y)

Deduction Theorem

on 1 to 5.

---

7.
~(y ≺ x • x ≈ y)

Steps 1-6, substitution of y for x

---

8.
x ≺ y • y ≺ x : ~(x ≈ y )

Assumption

---

9.
x' ≈ x • (x', r, y disjoint)

Condition

(For example let x' = x X 0

if no members of r and y are so constructed.

It is always possible to establish 9.)

---

10.
y' ≈ y • (y', s, x disjoint)

Condition

---

11.
x' ∪ r ≈ y

2, 9

---

12.
y' ∪ s ≈ x

3, 10

---

13.
x' ∪ r • ≈ • y' ∪ s

Substitution

---

14.
y ≈ x

Substitution

---

15.
~[(x ≺≈ y)(y ≺≈ x) ~(y ≈ x)]

Deduction theorem 8-15

(Assumption 8 is inconsistent and hence false.)

---

16.
x ≺≈ y • y ≺≈x --> x ≈ y

Deduction theorem 1-15

(Statement 0 is the only scenario left.

One might ask what about a case in which none of

the scenarios holds. But then one would to argue with one or

more of the axioms of the standard set theories.)

---

In an earlier draft, the step numbered 3a was omitted. Rather than renumber the proof, I chose to use that alphanumeric form. And, as I did not indicate which steps were subsidiary to others, 3a should not be read to indicate a special logical relationship.

A 'Traveling Salesman' algorithm with lemmas

---

July 2017: I wrote the paper below quite a few years ago. By itself, it is not wholly adequate. Some updated comments:

1. The "star" method of drawing every circuit that does not cross itself outside two cities (nodes) nor back up, is clearly more efficient than the n! approach. But, if one encounters a map of, say, 100 nodes, then one can follow the star method and yet at each node be faced with some k number of choices. In general, k is nowhere near n!. Yet, even if we had only 2 choices on average per node we have the exponential 2ⁿ as a close approximation.

2. Lemma 1: If one has a map of 3 nodes, one finds that a fourth node can link to 2 or 3 nodes. In general, for a map of n-1 perimeter nodes, the maximum an nth node placed outside the perimeter can reach is n-1 nodes. So if we keep a record of each member of a set of maps, with a 3-node map the minimum member, formed by adding a perimeter node and keeping the subset such that the nth node links to n-1 nodes, then the work of finding the shortest route increases by n (n distances need be measured).

3. Lemma 2: Similarly, for the set of subsets formed such that an external node links to some (n-k) such that k e [1,n-1], the work goes up linearly, on the order of n.

4. It may be useful that one can arrange subsets of the traveling salesman problem such that the work rises monomially. The problem itself -- Can TSP be in every case be reduced from exponential work increase to polynomial work increase? -- remains open. But even so the "star" method outlined below, reduces it from n! to on the order of some kⁿ. (k is some average determined by the specific map.)

5. It was certainly bad form for me to declare that "most" traveling salesman circuits grow polynomially. The algorithm given below is why I reprint this piece. I certainly don't wish to parade my misstatements.

---

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)2n [questionable]. (ii) However, even for large n, the method yields a polynomial rate for most sets of fields of nodes [questionable; see above].

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 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    
             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 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       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 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.

Fermat frivolity

Mad indeed.

Somewhere online there is joke proof of Fermat's last theorem. It's not serious at all. I would like to take it down because the joke is stale but after Google changed its security protocols I was locked out of my accounts.