AC and the subset axiom

AC may be incorporated into the subset axiom.

The subset axiom says that, assuming the use of "vacuous truth," any set X has a subset.

AC would say that every pure set except those of cardinality less than 2 (as in {0,1}) has a nonempty proper subset.

But such a formulation requires an axiom of foundation, or the equivalent, in order to outlaw sets of "cardinality" less than 0. (That is, to forbid infinite descent definitions of not-so-primitive elements.)

A snapshot of undecidability

---

Notation: The logical product, or conjunction, of two declarations P and Q is expressed PQ (P and Q) or P.Q.

---

A logic language uses a finite set of symbols. A declaration is a legal arrangement of symbols in a string of finite length. It doesn't matter whether the declaration "makes sense."

A theory T contains a denumerable (finite or not) set of axioms and a denumerable set of declarations. That that set is infinite is shown by the simple P --> P --> P --> ad infinitum.

In any case, we need worry about nothing but the axiom subset of T. That is, if a declaration is regarded as provable, then it must be derived from axioms via modus ponens, as in A_xA_y --> Q, where Q is a theorem.

Note that though the axiom set may be infinite, proofs demand that a finite subset be used since an infinite chain of conjunctions means that a deduction is never realized. So then any provable or derivable theorem has a finite chain of declarations linking the theorem to some finite subset of axioms. This last statement expresses the deduction theorem. Hence, we can simply cite the axioms that yield the theorem. The intervening chain is built and checked by mechanical procedure, of course.

So we may express any provable theorem of T thus:

Π A_i --> P, in which case P is customarily taken as an element of T, though not always.

Now suppose we write Π A_i --> P. This may be rewritten ~(Π A_i) v P. Then, ~~[~(Π A_i) v P]. Then ~[(Π A_i).~P].

We denote that last declaration by R (some would call this a meta-declaration). R denies that the axiom subset can be true while P is false. But suppose P says, "This declaration cannot be derived from axioms" (or "This declaration is not provable in T")? Yet R assures P cannot be false. So, intuitively, we are inclined to accept it as true. Yet P cannot be proved. So, if P is true then T is incomplete. If P is false, then it can be derived from axioms, which tells us that R expresses an inconsistency, which is to be found in the axioms.

This is a snapshot because it does matter what the declaration means. A proof requires the use of logic symbols only. We must be able to use symbols to justify a declaration like "This declaration is not provable in T." By the use of a Goedel-type method, to include Goedel numbers, this snapshot can be made rigorous. That is, it is possible to encode the string represented by P as an element of Number Theory. That, in turn, shows that not all theorems -- or posed problems -- of Number Theory are decidable. (Goedel and others base their results on a subset of Peano's axioms.) Because the logic L of symbol strings can represent Axiomatic Set Theory, we then have that even that theory (usually ZFC) cannot be fully provable. Any system sufficient to be encoded by Goedel's tool will not be fully provable or decidable.

It has been shown that when Number Theory is limited to addition (and multiplication), that system is complete and consistent. So any system that cannot be encoded only at that level must be inconsistent or incomplete.

Monty Hall II

A peculiar scenario
Behind three doors are two booby prizes and a luxury car.

You are asked to select a door and, after reflection, you choose one.

Monty says, "Have you chosen a door?"

"Yes."

"Are you very certain?"

"Yes."

"Before I open that door, would you like to change your choice?"

Now you must decide whether it would help you to change your choice even though Monty hasn't opened a door.

On your first choice, you had a 1/3 probability of being right.

So, your probability of being wrong is 2/3.

Thus, it makes sense to change your choice, even though nothing else has changed.

You now have a 2/3 probability of being right.

Similarly, Monty could hear you answer, "I pick door A."

Monty asks, "Are you very certain? Would you like to change your choice?"

The same reasoning applies as above -- even though there is no new information. That is, so-called Baysean reasoning does not appear to be terribly relevant here. The probabilities have not been updated by new information. The probabilities change based only on a person's firm mental act.

Weird, but not contradictory in the context of the usual logic of probability.

But a Bayesian solution to Monty Hall I DOES require a door to open. Yes, we can see that the Bayesian solution makes sense. But that does not answer the puzzle of why the non-Bayesian solution works for Monty Hall I and II. That is, the non-Bayesian solution seems to be the more general of the two.

Some would argue that this poser proves that one cannot use the simple solution given above. Yet, the logic itself is not flawed, though one may question any potential application. But perhaps we have an insight here into the interpretation problem of quantum physics.

You say, hold up! What we have here is two independent cases. Wrong. If that were so, we would be told -- before Monty asks "Are you sure?" -- that a reshuffle of prizes may have taken place.

Bayesian solution to Monty I
I found a very good Bayesian analysis online at Geek Data Guy
https://towardsdatascience.com/solving-the-monty-hall-problem-with-bayes-theorem-893289953e16

which I reproduce below:

Solving the Monty Hall Problem with Bayes Theorem

How your intuition can lose you money on gameshows

GreekDataGuy

Apr 20, 2020·3 min read

Photo by vaun0815 on Unsplash

You’re on a gameshow called “Let’s Make a Deal”. There are 3 closed doors in front of you.

Behind each door is a prize. One door has a car, one door has breath mints, and one door has a bar of soap. You’ll get the prize behind the door you pick, but you don’t know which prize is behind which door. Obviously you want the car!

So you pick door A.

Before opening door A, the host of the show, Monty Hall, now opens door B, revealing a bar of soap. He then asks you if you’d like to change your guess. Should you?

My gut told me it doesn’t matter if I change my guess or not. There are 2 doors so the odds of winning the car with each is 50%. Unfortunately for me, that’s 100% wrong.

This is the famous Monty Hall problem.

By working through Bayes Theorem, we can calculate the actual odds of winning the car if we stick with door A, or switch to door C.

Bayes Theorem

Bayes Theorem describes probabilities related to an event, given another event occurs.

Bayes Theorem

A = An event.

B = Another event.

P(A|B) = posterior = The probability of an event occurring, given another event occurs.

P(B|A)= likelihood = The probability event B occurs, if event A occurs.

P(A) = prior = The probability an event occurs, before you know if the other event occurs.

P(B) = The normalizing constant.

Bayes Theorem + Monty Hall

Note: A, B and C in calculations here are the names of doors, not A and B in Bayes Theorem.

Now let’s calculate the components of Bayes Theorem in the context of the Monty Hall problem.

Let’s assume we pick door A, then Monty opens door B.

Monty wouldn’t open C if the car was behind C so we only need to calculate 2 posteriors:

1. P(door=A|opens=B), the probability A is correct if Monty opened B,
2. P(door=C|opens=B), the probability C is correct if Monty opened B.

Prior: P(A)

The probability of any door being correct before we pick a door is 1/3. Prizes are randomly arranged behind doors and we have no other information. So the prior, P(A), of any door being correct is 1/3.

1. P(door=A), the prior probability that door A contains the car = 1/3
2. P(door=C), the prior probability that door C contains the car = 1/3

Likelihood: P(B|A)

If the car is actually behind door A, then Monty can open door B or C. So the probability of opening either is 50%.

If the car is actually behind door C then monty can only open door B. He cannot open A, the door we picked. He also cannot open door C because it has the car behind it.

1. P(opens=B|door=A), the likelihood Monty opened door B if door A is correct = 1/2
2. P(opens=B|door=C), the likelihood Monty opened door B if door C is correct = 1

Numerator: P(A) x P(B|A)

1. P(door=A) x P(opens=B|door=A) = 1/3 x 1/2 = 1/6
2. P(door=C) x P(opens=B|door=C) = 1/3 x 1 = 1/3

Normalizing Constant: P(B)

In cases where analyzed events cover all possible options and don’t overlap, we can take the sum of the numerators.

P(B) = 1/6 + 1/3 = 3/6 = 1/2

Posterior: P(A|B)

Now we just need to do the remaining math.

1. P(door=A|opens=B) = (1/6) / (1/2) = 1/3
2. P(door=C|opens=B) = (1/3) / (1/2) = 2/3

This leaves us with a with a higher probability of winning if we change doors after Monty opens a door.

If this is super counter-intuitive, I think it’s important to remember 2 pieces of information:

• Monty NEEDS to open a door
• He can’t open the door with the car behind it

Conclusion

I found this to be a super interesting case where intuition is at odds with probability.

Try asking people (especially smart people) what they would do if playing the Monty Hall problem. Sometimes it’s fun to see how they answer :)

GreekDataGuy

Just a developer. Contact: greek.data.guy “at” gmail.com

Follow

GREEKDATAGUY FOLLOWS

• 

  Shefali O'Hara

• 

  Patrick Cryptozoa

• 

  Felicia C. Sullivan

• 

  Ann Adaya

• 

  Niharikaa Kaur Sodhi

See all (315)

Related

Union of Probabilistic Event Groups

How to calculate the union of probabilistic events into groups

Why Bootstrapping Actually Works

A simple layman explanation of why this popular technique in data science makes sense

Bayes’ Theorem, Simply Explained

If ignorance is bliss, knowing how to deal with incomplete knowledge is the key. Bayes’ Theorem formalizes all of that.

Assumptions of Logistic Regression, Clearly Explained

Footnote HPX.23: On Hilbert's Sixth Problem

HPX.23 A consistent ToE would be a model of some logic (logic system). As this system must incorporate number theory, we have immediately that this system would be either inconsistent or incomplete, thus contradicting the claim that we have a ToE.

Goedel, and others, extended Goedel's initial incompleteness result to show that a great many diophantine equations are undecidable in terms of axioms. These expressions are encoded forms of statements in the ToE system which are undecidable: they may be true, but not provably so.

So then, any supposed ToE contains a vast number of irresolvable problems.

Note that this result cannot be voided by appeal to some topology for the cosmos.

One may object that a countable infinity of trivial axioms should take care of this technicality to the satisfaction of most physicists. This may not be the case. If we call a system that has been extended by an additional axiom L', we have the potential that L' itself contains an infinity of irresolvable problems (that are encoded as diophantine equations). Hence we face the potential that the set of all Ls would require an uncountable infinity of axioms. Most physicists are unlikely to regard that eventuality as satisfactory.

If one is a mechanist, materialist or conventional physicalist, then the proofs of Goedel and Turing strongly support some form of Cartesian dualism. To reject Cartesian dualism means to reject the former philosophical approaches.

That is, the cosmos, and in particular, the human cognitive function (AKA "mind") cannot be reduced to Boolean logic circuits. This is shown by their proofs that mathematics cannot be reduced to logic alone -- unless one posits an infinite nested class of logics.

Thus, we draw the conclusion that not all mathematical insight and activity can be algorithmic; it cannot be reduced to a Boolean, or any other, logic system.

Goedel dealt with this fact by tending toward the divine. Turing, an atheist, tried to deal with it by mechanizing his logic system that was based on Oracles, which are not subject to the limits found by himself and Goedel. Yet, though Turing may have succeeded to some extent, one cannot void the fact that his Oracle remains unanalyzable, and hence as non-scientific as many a theological notion.

Where are the non-computables in the binary tree picture of the reals?

---

NOTE. Occasionally, over the years, I have published discussions of the binary tree picture of the reals. This post continues in that vein.

---

We accept the idea that the set of decimal extensions is bijective with the reals. For convenience, we convert to the base-2 number system, such that the reals are comprhended by the set of binary extensions.

To help us in our intuition, we employ a binary tree with a denumerable infinity of stages/levels. That is, at each level is a set of 2ⁿ nodes, or branching points. At level 1, there are 2 nodes...at level 10, 1024 nodes... Every left branch is designated 1 and every right branch 0.

Example: At level 3, we have,

  
  L R L R L R L R
  
  which is equivalent to
  
  1 0 1 0 1 0 1 0
  
  

The complete set of stages corresponds to the set of natural numbers N. The number of nodes in the "final" stage is taken to be 2^ℵ_o.

Hence, we see that every path is well-ordered. (But AC is needed to tell us those distinct paths reach the "bottom" stage.) Now we know from the Goedel and Turing theorems that the cardinality of the computables is ℵ_o, which is that of N.

It is also evident that every rational is represented as a finite digit string that recurs infinitely often. That is a set of all 0's means 0; a set of all 1's means 1; a finite string of 0's and 1's that is either followed by all 0's or that recurs infinitely often means some rational.

In addition, we have the set of computable irrationals. This means there exists at least one procedure that converts a numerical input into some 1's and-or 0's without ever doing so periodically and that this procedure is infinitely (or indefinitely) recursive, as in f(x) = x_next.

Now each path, up to any finite level, we must construe as a proto-number. All one can prove about any such path one follows is that if we know the algorithm, we can say whether the number is rational or irrational. And, if one does not know the algorithm, all one can say is that -- thus far -- the number is computable, as it can be defined stage by stage. In fact, at any finite level, the path has thus far been computed. So there is really no way to discern a noncomputable from the ordinary perspective.

But if we accept that the power set of N exists, in that case it must be that the "bottom line" point set of 2^ℵ_o "originates" the non-computables.

That could only mean, I suggest, that there must be many digit strings (from the "top" or "our" perspective) followed by an infinity of 0's that are then followed by a "finite" (from "bottom" perspective) string of 0's and 1's.

Such numbers are said to be undefined because their paths vanish as they climb skyward. Their paths all converge to the number 2. But they have vanished "before" coming into our finite range.

I concede such talk is inexact. Our language is unsuited for such conceptualization. Yet, I suggest, that intuitively we can discern that the "bottom up" paths must contain the non-computables, but that we cannot, from "top down" obtain them.

This picture does not suggest much beyond what is already known: that the continuum hypothesis is independent of the axioms of standard set theory.

A way to think about that is to note that the set of the computables K and its complement K^c comprise the reals. And R\K is equinumerous to R.

But we must use AC to "pick out" an arbitrary x ∈ K^c because there is no method in our posession for specifying any x. That is, if we define K^c by its elements, we say K^c is defined such that x is not definable. This is almost an abuse of the usual set notation {x|x ... }, which means that "any element x is defined..." So for K^c we have {x|x is undefinable}. That expression, to me, makes clear why CH is such an elusive beast.

Historical note on quantifiers

I have read in a few places that C.S. Peirce was the first to introduce quantifiers into logic.

Hence, I draw attention to the words of Augustus de Morgan in an appendix to his Formal Logic, or, The Calculus of Inference, necessary and probable published in 1847, before Peirce's time.

In 1842, there was published anonymously 'Outline of the Laws of Thought'; London and Oxford (Pickering, and Graham) octavo in twos (small). The author is the Rev. Wm. Thomson, tutor of Queen's College, Oxford. It is a very acute work, and learned. The system of propositions is extended by the introduction of both the common quantifications of the predicate into the affirmatives only, which introduces the propositions U and Y, as the author calls them, or "all Xs are all Ys" or "some Xs are all Ys."

Caution: Tractatus commentaryis in very, very rough form

It is nowhere near ready for dissemination. But, I believe in permitting anyone who likes to look over my shoulder and see what I am doing while my work is progressing, if it is.

That commentary is distinct from the essay An objection to proposition 1 of 'Tractatus,' which is complete, though flawed in its organization and presentation.

Right now the commentary is very clumpy, scattershot and not very good. At some future point -- who knows when? -- I hope to have put it into proper form. But, please peek if you are so inclined.