8 ms·

The mileage of others may vary, but it has been my experience that there is no cogent solid proof of uncountability that can withstand concerted critique.[0] B

• myWindoonn 5y ago
  Hi, Lawvere pummelled your position into the ground a while ago: http://tac.mta.ca/tac/reprints/articles/15/tr15.pdf http://tac.mta.ca/tac/reprints/articles/15/tr15.pdf Your critique involves repeatedly crossing the boundary between the inside and outside of the system in question; Lawvere works entirely inside the system, and shows that the paradoxes of self-reference arise from our interpretations. https://arxiv.org/abs/math/0305282v1 https://arxiv.org/abs/math/0305282v1 explains with many examples. Hi downvoters: Use your words when somebody is wrong. Your downvotes aren't helpful here for finding the truth.
  • sharpener 5y ago
    I'm not seeing this yet. Perhaps you could explain it to me in plain terms.
    • myWindoonn 5y ago
      Pick any Cartesian closed category. Says Lawvere: If there exists t : Y -> Y such that t;y != y for all y : 1 -> Y then for no A does there exist a surjection A -> (A -> Y). (He actually says something much stronger.) Note that the first half of this is saying "if there exists t such that t has no fixed points..." Let our category be Set, the category of sets and functions; it is well-known to be Cartesian closed. Let A be the set of natural numbers and let Y be the Booleans. Then Lawvere is saying that there is no surjection N -> (N -> 2), and thus definitely no bijection, because there is a function 2 -> 2 with no fixed points: the negation function which swaps true and false has no fixed point. It does not get much plainer without actually reading Lawvere and/or Yanofsky directly, sorry. I hope that this helps explain how inescapable this sort of theorem is.
  • sharpener 5y ago
    Lawvere's paper appears to suggest that if I refute one diagonal argument then I refute them all. Would you consider that to be an accurate description?
  • ProfHewitt 5y ago
    Lawvere's work is elegant! However, Lawvere missed the crucial importance of Russell's orders on propositions in blocking the construction of monster propositions using recursive definitions. Orders on propositions block construction of I'mFalse, I'mNotSelfapplicable, I'mUnprovable, and MyTheoremsAreEnumerable. See the following video for more information: https://www.youtube.com/watch?v=AJP1VL7shiI https://www.youtube.com/watch?v=AJP1VL7shiI for the following article: https://papers.ssrn.com/abstract=3603021 https://papers.ssrn.com/abstract=3603021
• curtisf 5y ago
  This presents a confused understanding of Cantor's diagonalization argument. You are shrouding in complexity something that is straightforward. The complete proof of distinct infinite cardinalities can be stated succinctly and clearly in only a few lines, without referencing the reals at all. You don't need to vaguely refer to "four steps", you should precisely elaborate the steps of the proof you view as problematic. First, forget the reals. Let's establish that there are sets that are infinite yet uncountable. ---- "Uncountable" means that there is no bijection with (a subset of) the natural numbers. An "infinite sequence of A's" means a function ℕ → A. For convenience, I'll denote the set of infinite sequences of A's with `A**` -- this is not standard notation. Theorem: There is no bijection between ℕ and {0, 1}**. Proof: Suppose for contradiction that there is a bijection f: ℕ → {0,1}**. Define a function z(n) = 1 - f(n)(n). z is clearly well defined and is clearly a member of {0,1}**. Since f is a bijection and z is in the codomain of f, there is an element k of ℕ such that f(k) = z. However, z(k) = 1 - f(k)(k). Yet f(k) = z, so z(k) = 1 - z(k). This is a contradiction. So, the assumption (that there exists a bijection f: ℕ ↔ {0,1}**) must be false. Q.E.D.: There does not exist a bijection between ℕ and {0, 1}**. ---- The linked paper claims that the above proof would work on a bijection of the form ℕ ↔ [ℕ] or ℕ ↔ [ℚ] (where the [] indicate some suitable representation of the set as sequences of bits; again, not standard notation), but that is mistaken: crucially, the constructed function `z` must be a member of the codomain of `f`. The construction 1 - f(n)(n) does not necessarily lie in that set when the set only permits _certain_ bit-sequences! For example, consider an encoding [ℕ] which is "one-hot"; the natural n is encoded as a function y(n) = 1 and otherwise y(k) = 0. Then there is an obvious bijection `f`: f(a, b) = 1 when a=b and otherwise 0. What is `z` for such an `f`? z(k) = 1 - f(k, k) = 1. So, `z` is not a member of [ℕ]. For a more involved example, consider an encoding of [ℕℕ] that is a unary-encoding of the first natural, followed by a single zero, followed by a unary encoding of the second natural, and followed by only 0s. (The rationals correspond to a subset of these). A standard bijection has the pairs appear in the order of their sum: (0, 0), (0, 1), (1, 0), (2, 0), (1, 1), (0, 2), ... It's an exercise left for the reader that z constructed on this set does not encode to a unary number, followed by a single zero, followed by a unary number, followed by only zeros. ---- If you have an issue with cardinalities, I expect it can be found in the above proof and does not actually lie with the reals. But, for completion, to tie in the real numbers, it's necessary to show that {0,1}** is bijective with ℝ, or with (0, 1). This falls out from the Cauchy-sequence definition of ℝ. For a sequence y : {0,1}** the sequence z(k) = y(0) + 1/2·y(1) + 1/4·y(2) + 1/8·y(3) + ... + 1/2^k·y(k) is clearly a Cauchy sequence with a limit in the interval [0, 1]. It's also straightforward to check that every real number in the interval [0, 1] is the limit of one such Cauchy sequence.
• candybar 5y ago
  > Stage 4 of the CDA outline can be critiqued on several grounds. The first is that if we have all the numbers in [0,1] in our table a priori, then using the diagonal process to create a number that is not in the original set does precisely that: It creates a number that is not in [0,1]. So why does the constructed anti-diagonal number seem to have a form that puts it within [0,1]? Could it be that ignoring the zero ahead of the decimal point is a bit sneaky? You wrote all this and you don't seem to understand how proof by contradiction works? > If, instead, we construct the anti-diagonal number by counting down the table by positions before each digit selection we find that any anti-diagonal number constructed (from the rectangle) is now within the set we have counted through, and therefore not outside the counted set. This Stretched Diagonal counterargument remains true as d→ ∞, irrespective of any ordering of number representations in the table. This is not how anything works. You can't take a proof where they create an example that leads to contradictions and say, well, if you choose a different example, it doesn't lead to contradictions, so the proof doesn't work. Your "proof" in Appendix B is also just gibberish from a mathematical perspective. The infinity and cardinalities aren't numbers - this isn't a mathematically rigorous statement: lim(n -> inf) log(n) = inf = aleph_0 - it's nonsense. What you're saying here is that as n increases without bound, 2^n also increases without bound. That doesn't prove anything about the cardinality of infinite sets. Also, since you seem to accept that |R| is equivalent 2^|N|, it's also not hard to prove that 2^|S| > |S| for any S. 2^|S| < |S| is trivially untrue and if |S| = 2^|S], there must be at least one bijection F such that F: S => P(S) and inverse F^-1: P(S) => S Now define S' to be a subset of S such that s is in S if & only if it's in S, but not in F(s). Now, consider F^-1(S') - it must be in S, due to how it's defined. Let's consider whether it's also in S': 1. If F^-1(S') is not in S' (= F(F^-1(S')), by definition, it must be in S' 2. If F^-1(S') is in S', by definition it must not be in S' Since both these lead to contradictions, the assumption that there must be a bijection between P(S) and S mut be false. On the whole, you seem to be generally confused - R is not a real thing - it's a mathematical abstraction.
• sharpener 5y ago
  For the sake of HN archival history... The executive summary of my paper is that provably there are fatal inconsistencies in Cantor's Diagonal Argument (CDA). They take a few forms: (1) Application of basic classical analysis tools reveals that the contradiction sought by CDA does not hold if those tools are used. E.g. Assume we have the table of all unique infinite length binary strings {0,1}* (where * represents the supremum of the natural numbers, e.g. the first ordinal infinity in set theoretic language). Assume that those strings represent the fractional part of binary represetations of real numbers in the continuum interval [0,1]. Assume they start big endian, so for some string s, the value v(k) of some bit at the k-th position of s is v(k) = s(k)/2^k, for k = 1,2,3.... Let f: \N x \N -> {0,1}, be a function that accesses bits in the binary strings viewed as a matrix M(i,j). Create the binary number z as z(k) = 1 - f(k,k). Now deploy basic analysis. Note that k -> \infty implies v(k) -> 0. So no matter what the value of z(k) is, k -> \infty implies |z - f(k)| -> 0, for some suitable k. Let f be the limit of f(k) as k -> \infty. Then in the limit k -> \infty the number z = f, and (for all practical purposes) the diagonal z coincides with a binary number in the table f within a countable limit. This is independent of any ordering of the table rows of M(i,j). So the contradiction of CDA does not hold convincingly when these basic tools of analysis are used. (2) Corollary: Platonists would need to prove that infinite digit existence somehow invalidates basic analysis in order to cling to CDA. Moreover, they would have to prove that "higher" infinite digit existence does not invalidate useful concepts of numbers and limits at all. As far as I know, no one has done that yet. (3) Using the same basic tools of analysis, key arguments about powersets having cardinalities that are "higher" infinities do not go through, and moreover aspects of "higher" cardinal arithmetic, as presently defined, can be shown to be self-inconsistent. Therefore: A) When the tools of basic classical analysis are so useful, why would any pragmatic user of mathematics throw them out at some key point within CDA (and CDA only) to endorse a notion of "uncountability" that creates manifold inconsistencies further on? B) Why should any pragmatic mathematician allow the extra unconvincing machinery of higher infinities into maths? In the absence of decent answers to those questions I am compelled towards the recommendation is that mathematicians should throw CDA out. Edit: formatting.
  • myWindoonn 5y ago
    You're presupposing the topology of the Cantor space; how do you know that Cantor space {0,1}* corresponds to real numbers? You're also supposing that an infinite matrix is actually some sort of infinite-plus-one matrix in a handwaved fashion. Limits don't work in the discrete setting; you must invent and justify them. Pick a k. Note that z(k) is not in rows 0 through k of M, by finite diagonalization. Now, suppose that you try taking k to "infinity" again. z(k) keeps up at every step, by primitive recursion, and M is always missing at least one entry. By what justification do you suppose that M somehow outruns v at "infinity"? I need you to remember how to be a human for just a moment. Reread your words, "the recommendation is that mathematicians should ..." and consider the precise moral justification by which you make this recommendation. Note that your attempt at the passive voice failed to shift the moral burden, because the given proof is unconvincing (and quite unrigorous). Please consider a dram of humility and give Yanofsky's paper a serious read. It's good. Also, if you want a better idea of such an infinite Boolean matrix, consider reading about Chu spaces: http://chu.stanford.edu/ http://chu.stanford.edu/