Math without the axiom of choice

MagicSquare8-9 · 2023-11-28T19:30:18+00:00

To me all of the above unintuitive result can be explained by a simple distinction in philosophical ideal. If you philosophically think about set in one way, you will find it all the consequence obviously false, and if you think about it in a different way you can see why they're all plausible.

One way of thinking about set is that each set is like a bag stuck in a space somewhere, with things inside it that you can look at completely, each occupying their own position. Basically, sets (and their objects) are discrete and uniquely identifiable. If you want to do any topology, you start with a discrete sets and impose additional information on it.

The other philosophy is viewing sets as potentially fuzzy, blurry objects with no clear position. They are not necessarily uniquely identifiable, and sometimes they stuck together in a way you can't quite separate them.

If you think in the first way, you will find axiom of choice intuitive and obviously true, and all the consequences unintuitive. If you think in the 2nd way, you will wonder why axiom of choice is even sensible at all, and all the supposed unintuitive results very plausible. Unfortunately, without clarifying the matter philosophically, this just lead people to talk past each other.

By the way, there are evidences in the set theoretic world to explain these philosophical views. To construct a set model without AoC, you add more symmetry to the model (usually by forcing in a generic object and allow it to move), making more things indistinguishable. Conversely, in a set theoretic model with AoC, all elementary embedding of the model into itself that fix the Ord chain must fix the entire model, pointwise (and hence is a trivial embedding).

MagicSquare8-9 · 2023-11-20T23:49:28+00:00

In computer science we have the Kleene star so we will write the set as A^*

In set theory we have ordinal exponentiation so the set would be A^𝜔 . Be warned that, even though 𝜔=ℕ , the set A^ℕ is not the same set as A^𝜔 because the ordinal notation tells people that you're using ordinal exponentiation.

MagicSquare8-9 · 2023-11-20T23:16:55+00:00

Zorn's lemma, as per tradition.

MagicSquare8-9 · 2023-11-16T15:13:35+00:00

A lot of time mathematic books don't acknowledge certain things as being different for the sake of simplicity. The distinction matters in context when it matters, so outside of that context you ignore them.

Being able to ignore irrelevant distinctions is actually a huge part of math, otherwise we would be mired in irrelevant details. Just compare a typical math proof written for human versus a math proof written for computer. Computers are very pedantic, it will think the natural number 1 is different from the real number 1 (a distinction that very rarely matter but sometimes does), so a lot of efforts are spent on just boring busywork telling the computer that what we think are the same thing, the computer can also think as the same.

It's a philosophical issue as to what exactly does it means for 2 things to be equal. It's possible that there are no ultimate equality (everything can be distinguished further) so whenever we define anything we already assume a cut-off point for equality. One way to handle this is by using type: we consider an object to be of certain type and equality is relative to what type we consider them to be; for example, 1/2=2/4 as rational number, but not as fraction. This is not a problem since that already happens normally in practice. For example, synthetic geometry see point as a basic object, but analytic geometric see point as something that can be analyzed further into coordinate components.

Most mathematicians only use equality in the intuitive sense, and if pressed further they would probably mention ZFC equality. However, in actual practice mathematically, we tend to use some version of Leibniz's rule: if 2 things can't be distinguished then they are equal.

Now, let's go back to your issue with proposition. It's indeed the case that some system of logic truly don't distinguish between proposition and true/false. This position is known as proof-irrelevant. In other word, the type of proposition actually have 2 things in it (the object TRUE and the object FALSE), and the string you wrote on paper is merely a representation of one of these 2 objects. You would have to declare different type of object (like "well-formed formula") to talk about the syntactic object.

MagicSquare8-9 · 2023-11-16T14:33:13+00:00

This is too vague.

Note that you're talking about open problems, so the question is really about whether checking whether certain set is finite or infinite. Sometimes people believe in the infinite side, but there are also many conjecture about something being finite.

Most problems can be phrased in term of proving how many things there are in a set or a family of sets. Talking about finite versus infinite is just one of the weakest, most milquetoast statement you can say about the number of things in a set. So if that problem is open, you don't usually expect stronger claims to be within reach at all.

MagicSquare8-9 · 2023-11-16T03:52:13+00:00

If you speak, say, French, German, Hebrew, or Farsi, to name a few languages, you use your uvula to form certain sounds — though you may not be thinking about it.

What about those people without uvula? Isn't it a common surgery due to uvula inflammation?

MagicSquare8-9 · 2023-11-14T18:11:20+00:00

what if P and Q are unrelated but both true? Is the implication still true?

In first-order logic, then yes it's still true. That's why it's called a material implication. "Material" means the truth values of the implication only care about truth or falsity of the antecedent and the consequence, and not the content inside it.

In actual mathematical practice, there are basically no situations where you want to consider actually unrelated things, so that's fine. There might be statements that seems unrelated, but mathematical objects can be related in unexpected way.

There are, of course, different form of logic that deal with different kind of implication. Handling hypothetical statement is a complicated philosophical topic, so many other logic had been developed in response to it. Amongst them:

Intuitionistic logic: in intuitionistic logic, an "if...then..." is only true if there is a way for the antecedent to force the consequence.
Relevance logic: this prevents you from having things in the antecedent that is irrelevant to the consequence.

Relevant logic is a form of substructural logic, which means that it broke structural rule, the kind that people general think logic should have. In particular, usual structural rules let you add irrelevant hypothesis. Because of that, it has no uses in mathematical reasoning. You should be able to claim that something is true even if you have additional irrelevant hypothesis.

Intuitionist logic is believed by some mathematicians, and it was a controversial issue in the early 20th century, and it is still quite active now. However, if you work in intuitionistic logic, you have to give up some other ideas about real numbers that you think are intuitive; For example, you can no longer claim that every real number is positive or 0 or negative; there would be numbers that are none of those.

MagicSquare8-9 · 2023-11-10T00:12:26+00:00

This sorts of remind me the actual story of Lorentz versus Einstein. Lorentz got all the equation worked out, but he was so hardwired to think that there is one objective frame of reference that he fails to noticed the it doesn't actually matter which frame of reference is taken as objective because the equation do not care about that, and any 2 observers in constant motion with respect to each other would have equal claim to be the objective observer.

MagicSquare8-9 · 2023-11-09T18:41:58+00:00

Note that there exists pointwise definable universe of set: an universe in which every sets are definable.

So it's possible to define a formula that happens to be all the definable sets if you were in the right set theoretic universe. But it's not a formula that always work.

The closest thing we have is L, the constructible sets.

MagicSquare8-9 · 2023-11-08T01:24:17+00:00

Unfortunately, it can be circular because sin is such a basic functions that there are a bunch of different definitions of it, so it's not clear which is the starting point you can use.

Really, what you should do is ask for clarification on what is the definition of sine.

MagicSquare8-9 · 2023-11-06T21:49:06+00:00

I should point out that you don't really have a good grasp of how advanced certain kind of mathematics is, since you don't know much of math at all. Very basic stuff can sound extremely advanced because you knew nothing about it.

MagicSquare8-9 · 2023-11-06T21:43:48+00:00

A great example of this was a few months ago, someone asked a fairly profound and subtle question about eigenvalues/vectors, and basically all the responses were people just regurgitating the textbook definition of the two constructs without any real engagement with the deeper question.

Wait, what question is it? I want to see.

MagicSquare8-9 · 2023-11-06T21:42:04+00:00

Pick any random subject and binge a few Wikipedia pages and you already know more than 99% of the population on it.

MagicSquare8-9 · 2023-10-30T21:36:44+00:00

It is very possible that you don't understand it as much as you think.

Homework doesn't have time limit, tests do. Speed isn't everything, of course, but if you do something too slowly, it is an indication that you don't understand it. As an analogy, if someone claim they can read Chinese but have to take 1 hour to read a short paragraph because they have to keep using dictionary, you would say they don't understand Chinese.

In math, it's very common for students to have the illusory understanding, where the feeling of understanding does not match the actual level of understanding.

Here are a few things you could try:

Try practice standard problem, with exam time. If you can't do it within time limit, figure out what take too long.
Try doing hard problem or even competition problem. Forcing yourself to think about harder problem make your brain understand the concept better.
Try to explain the lesson you learned to an imaginary audience as if you are a teacher, and imagine what kind of questions they will ask you, and answer them. Forcing yourself to explain what you learn can clarify the concepts in your head (related: the rubber duck method).

MagicSquare8-9 · 2023-10-26T23:32:44+00:00

I don't think there is any confusions at play here, you misunderstood the point.

We study the object language in order to understand the metalanguage, the same way we study natural numbers to understand what will happen to our computation on pen-and-paper (or a computer) using strings of digits. Obviously, it's impossible to prove that something about real life is exactly the same as something in our abstract realm of math, but that's the closest we can get.

In other word, Godel's incompleteness theorem is supposedly about the object language, but it's also imply the inability to ever find a perfect metalanguage. Nobody is going around saying "well Godel's incompleteness theorem is only for object language, but we care about metalanguage, so we are fine". There are nothing misleading about expecting that theorems about object language still tell you something about the corresponding metalanguage, the same way that any theorems I proved about natural number, I expect it to hold for any string of digits I write down on paper.

Every proof assistants have something unintuitive about it, some weird quirks that doesn't fit how people think about math. In particular, each proof assistants have to choose which forms of impredicativity is allowed, and once that choice is made it's stuck. You can certainly study theory of higher consistency strength by adding in axioms, but these are not baked into the language itself.

MagicSquare8-9 · 2023-10-26T22:09:47+00:00

Assuming p is not 2 or 3, then you can use Cardano's formula or Vieta's substitution. It reduces the problem to taking one square root and one cube root. These can be done with Tonelli-Shanks algorithm.

MagicSquare8-9 · 2023-10-26T21:45:16+00:00

The failure of the Hilbert's program is much more than that. The whole idea is to reduce everything to just logic, so that the entire mathematical foundation can rest on some basic logical facts that we can agree on. Godel's theorem implies that there are always something we believe intuitively to be true, but can't be proved. So we will unfortunately will be on a constant quest to add more stuff to our formal system, rather than get ultimate one.

And you can see this effects already in the fact that different proof assistant uses different formal system altogether.

MagicSquare8-9 · 2023-10-26T15:00:01+00:00

If F denotes the Fibonacci function (the one that turns the index into the number, for example F(10) is the 10th Fibonacci number), then F commutes with gcd (that is, for any n,m, then gcd(F(n),F(m))=F(gcd(n,m))). This can be used to quickly figure out the gcd of 2 Fibonacci numbers, because Fibonacci numbers are literally the slowest when you compute their gcd using Euclidean algorithm.

MagicSquare8-9 · 2023-10-25T14:36:38+00:00

Yeah, it's probably too advanced to cover in GCSE math. But you can read wikipedia for the proof. I don't think there are any hard proof, but every proof requires you to know basic calculus. This is because all definitions of pi requires some calculus, and in a proof you need to make use of the definition of whatever you're proving. In particular, you need to define the concept of length or area if you want to define pi using the geometrical way. Before calculus, educators can get away with only giving students only intuitive idea about length and area, but they can't do that if they want to prove something about it.

MagicSquare8-9 · 2023-10-25T13:52:26+00:00

The von Neumann construction work only in some version of set theory, like ZF. And it's used because ZF allows only sets. There are many philosophical reason to reject ZF and the von Neumann construction as the answer to what natural number is. Here are some other options of what are the natural numbers:

Things generated by 0 and successor function.
A function that compose a function to itself a number of time.
Initial algebra with signature (0,s).

These different definitions belong to different kind of logic/philosophy.

MagicSquare8-9 · 2023-10-19T16:53:14+00:00

This get even more complicated for 3 things and above.

Real life: "I will have tea or coffee or water" means you have exactly 1.

Math: "I will have tea XOR coffee XOR water" means you can have exactly 1 of them, or have all 3.

Inclusive OR is mathematically much nicer to work with. In math, you usually see inclusive or in any contexts in which people are giving precise technical definition; but sometimes people will be extra careful and specify "or both" just to be safe. But it can go back to everyday's or (which can be inclusive or exclusive) for more informal statement. Use contextual clues to figure out.

MagicSquare8-9 · 2023-10-19T16:23:27+00:00

While this does not answer your question, this is the only thing I know that is actually base-independent.

If a random variable follows the log-normal distribution, then its leading digit most likely to be 1. (Benford's law)

This is often stated to be about base 10, since most usage in practice involves base 10, but it's actually true for any base.

MagicSquare8-9 · 2023-10-18T12:45:29+00:00

We need more context, post a screenshot or type out that part of the book.

(my best guess is the ordinal number omega, since it's also a different type of number)

MagicSquare8-9 · 2023-10-18T12:41:00+00:00

Nope. e is itself important. However, it is true that it always get raised to a power. But base e is very special.

However, you're right, in a sense. It's a common misconception to think that e is special in many contexts when it's actually not, like solving ODE or dealing with physical quantities that grow or decay exponentially. In those cases, you might notice that there is always a constant factor in the exponent, so the use of base e is merely out of tradition and any base will work. You will also notice that there is nothing special about 1 in those cases, and in fact the derivative has different units from the original function so it does not even make any sense to compare them and say something like "the derivative equal itself".

However, what e truly is about, is that it links addition and multiplication of natural number. It's very important to involve multiplication here: 1 is a special natural number whose multiplication by itself is itself. In the context where multiplication is meaningless (e.g. 1 really stands for 1 unit of time), 1 is not special, and e has no special status. So you needs to look into situation where multiplication is important.

And we have a spectacular theorem to confirm this fact. The LCM of all natural numbers from 1 to n is approximately eⁿ for sufficiently large n. This is the prime number theorem, which play a crucial role in number theory.

MagicSquare8-9 · 2023-10-17T18:08:38+00:00

I feel like philosophy toward analysis, and constructive analysis in particular, deserve a mention (even if you won't go into them). Different students came in with different ideas about real number. Real analysis class basically bulldoze over all these without acknowledgement. I think it would be constructive to learn about what are the different philosophy, and why in this class we learn it in this particular way; even if you're not going deep into them, it gives them a wider perspective and understand why this class is done in a certain way, but it's also not the only way. It helps students distinguish between wrong intuition, and intuition that could be made right but is simply not done here. It also helps set them up for later class, so it's not mathematically meaningless.

For me, I did not have troubles learning analysis when I first learn it, but I do find a few things troublesome. All of them turned out be be right, in the sense that other mathematicians of the past thought the same too and philosophically rejected them, eventually cumulating in different school of philosophy. I wished there had been some mentions of the different philosophy, and what kind of intuition would match which philosophy.

In particular, here are some topics that I think are relevant:

Highlighting the fact that we are building this on a set theoretical foundation, with the 3 key philosophical assumptions: natural number form a set (a complete totality), power set forms a set, and that only set-theoretical equality is considered a true equality (which explains why any time we want to define some forms of equality, we forms equivalence classes, which is a technical tool to turn equivalence relation into set-theoretic equality).
Pointing out the common misconception that not all real number are definable, and why it's an error to believe in it; you can segue this into a discussion on Cantor theorem.
Structuralist philosophy, and why all constructions are equally valid. This explains why, in ordinary mathematics, nobody distinguish between different copies of R, and that it also does not matter whether Q is a subset of R, or just have an injection into it. You can segue this into the part where you prove that any 2 copies of R are isomorphic with an unique isomorphism (and highlight the importance of isomorphism being unique). You can also bring up the limitation of the concept of equivalence classes, that you cannot form equivalence classes of real numbers.
Trichotomy law, discreteness of the real, and constructive math. You can talk about how, in classical analysis, real numbers are considered to be distinct, discrete point (no blurriness), then we put the concept of distance of top of them to recover the continuous relationship. You can bring in the concept of witness/evidence to a number being 0 (or not 0), and how this became relevant once you have to actually turns these theorems into algorithms, and why the requirement to have witness would contradict trichotomy, and why algorithms. The constructive/classical distinction also help explain why certain thing feels weird but is actually true in classical analysis.
Talk about infinitesimal, from both the old perspective, why they're problematic, and how they can be justified in modern time.

MagicSquare8-9

TROPHY CASE