I'm going to go with some examples of decidable problems, since I've seen more than a few of these in introductions to the Halting problem. Basically these are about whether or not an algorithm exists that can find a pattern, or find some exception to a known "existing" pattern. Here I'm using "pattern" in a quite general sense. For instance, a problem posted on mathforum: show that a function f(n) exists which can look for sequences of \( 0 \) characters of length n in some string, returning 1 if \( 0^n \) is found in the string, and 0 if not. The problem isn't to construct such a function for any input string but to show that one exists by using a specific input, the decimal expansion of \( \pi \). We can exclude rationals with a "constant pattern" like 0.333... or 0.1258..., but all irrational numbers are candidates for this algorithm. Another example is Goldbach's conjecture: every even number greater than 2 is the sum of two odd primes. Finding a counterexample is the problem, so the algorithm is searching for an even number that doesn't have this property and halts when it does. Does such a function exist? Part of it is the proof of existence, but the first example with the decimal expansion of \( \pi \) as the input there are two possible algorithms, only one is "correct" (we don't know which) and both exist. One returns a 1 for every n, the input is assumed to contain sequences of zeros of length n for all n; the other assumes there is a maximum length sequence, say N, so the function returns 1 only for n less or equal to N. We can't know what N is, but if the second is the correct algorithm it must exist (!) The Halting problem is also a decidability problem: does an algorithm exist that can tell us which algorithm of the two possible is the "correct" one?
Sorry, noticed a mistake , the above should say "every even number greater than 4", or it could have said "every even number greater than two is the sum of two primes". Goldbach's conjecture seems to be straightforward to implement as an algorithm, which would need to be able to test if a pair of numbers are both prime, just input every even number greater than 4, find any sum of two primes equal to each number and we're done. Maybe have an addition table of prime numbers and check the input number is in the table . . . But if you suppose there is an even positive number N which is not the sum of two primes, it won't be in an addition table of primes, but will be in the input if such a number exists.
rpenner #18 rpenner wiki I'm paraphrasing the article, and Cantor displays a portion of a partial list, assumed to be true for the sake of argument. If asked to prove it exists, his idea would fail at the beginning. rpenner The sequence s0 is under construction at each step/position, thus the comparisons can only relate to ps0. He can't know what the final sequence s0 will be in agreement with your 2nd statement. Any permutation of the randomly ordered list will generate a different ps0. The partial sequence ps0 has the same number of positions as sequences checked. If a partial sequence has k positions, there are 2^k possible arrangements, independent of the orientation, horizontal, vertical, or diagonal, therefore ps0 cannot have an arrangement that is different from all s. rpenner Cantor states: "since s0 will differ at the intersection of the diagonal with each si in the list L by construction, the list L is incomplete, i.e. a new sequence has been formed." Again, paraphrasing from Wiki, (adding quotes for clarity). My intent is not to prove L incomplete, but s0 always incomplete, therefore, there is no infinite sequence, therefore there is no list. If Cantor or anyone could produce one infinite sequence, then they could produce them all. The method of dividing an ordered L into subsets at each step, is simple and clearly shows if in fact/reality there was a complete L, his claim is a contradiction of terms. The Wiki article also notes there are a few other forms of set theory and Cantor's work isn't accepted by all. philosophical comments The concept of "infinity" is not one of mathematics, (you can't measure it) but one of knowledge in general. Even if humanity were granted immortality, each member will always have a beginning, i.e. a finite lifespan, and still no cognitive ability to form such an idea as continuing forever. If the statement "you can't think of a number great enough to represent infinity" is true, then, infinity is not a number and you can't think/conceive it.
http://en.wikipedia.org/wiki/Cantor's_diagonal_argument#Uncountable_set But, \(T = \left\{ 0, 1 \right\}^{\mathbb{N}}\) which is all possible sequences of 0 and 1. L is just one attempt to enumerate all the elements of T indexed by \(\mathbb{N}\), thus \(L \in \left( \left\{ 0, 1 \right\}^{\mathbb{N}} \right) ^{\mathbb{N}}\), so it follows if \(t \in T\) that \(\textrm{card}(t) = \textrm{card}(L) = \textrm{card}(\mathbb{N})\). Let's step back and use a cartoon version of this, where \(\mathbb{N} = \left\{ 1, 2, 3 \right\}\). Then t might be \(\left\{ 1 \rightarrow 0, \; 2 \rightarrow 1, \; 3 \rightarrow 0, \right\}\) or in shorthand \("010"\). Then T would be \(\left\{ { \left\{ 1 \rightarrow 0, \; 2 \rightarrow 0, \; 3 \rightarrow 0, \right\}, \left\{ 1 \rightarrow 0, \; 2 \rightarrow 0, \; 3 \rightarrow 1, \right\}, \left\{ 1 \rightarrow 0, \; 2 \rightarrow 1, \; 3 \rightarrow 0, \right\}, \left\{ 1 \rightarrow 0, \; 2 \rightarrow 1, \; 3 \rightarrow 1, \right\}, \\ \left\{ 1 \rightarrow 1, \; 2 \rightarrow 0, \; 3 \rightarrow 0, \right\}, \left\{ 1 \rightarrow 1, \; 2 \rightarrow 0, \; 3 \rightarrow 1, \right\}, \left\{ 1 \rightarrow 1, \; 2 \rightarrow 1, \; 3 \rightarrow 0, \right\}, \left\{ 1 \rightarrow 1, \; 2 \rightarrow 1, \; 3 \rightarrow 1, \right\} } \right\}\) or in shorthand \(\left\{ "000", "001", "010", "011", "100", "101", "110", "111" \right\}\). This only looks like a list, because a set has no intrinsic order. The extensibility axiom says the only thing that makes one set different from another would it it's contents. Same contents, identical set. Unlike a list, order doesn't play a part. Then L might be \(\left\{ 1 \rightarrow "100", \; 2 \rightarrow "010", \; 3 \rightarrow "001", \right\}\) but could not hold all the elements of T unless T and \(\mathbb{N} \) were the same size. So while T may have every possible sequence of 0's and 1's, no matter how many there are, L can only point to as many elements of T as there are counting numbers. Thus it has not been proven either that "L is complete" or "it contains all possible sequences of 0 and 1". Indeed, Cantor will assume it would be possible for L to be complete to show that assumption leads to contradiction, so it cannot be true. If you understood this, then you didn't understand the need to clearly communicate which statements you hold to be true and which statement you are only assuming to be true to explore the logical consequences. ---- Math is not subject to the limitations of finite computers. z, or s0 as you insist on calling it, is a function of L and its identity is established as soon as you pick L. Given any L in \(\left( \left\{ 0, 1 \right\}^{\mathbb{N}} \right) ^{\mathbb{N}}\), for all n in \(\mathbb{N}\), we define z(n, L) = 1 - L(n)(n). Thus crippling yourself by building z only from a never-ending process defeats your ability to apply Cantor's theorem to infinite sets larger than \(\mathbb{N}\). I hate your use of s0 over Wikipedia's choice of s and my choice of z, because 0, by definition, is not part of the set \(\mathbb{N}\) being contemplated, so its not natural to the discussion nor does it have a natural position in the existing listing, L. Permutations of L would change L, because L is a specific function from \(\mathbb{N}\) into T.
It's a "new sequence" in that it is not contained in L, not a sequence not a part of T. You are using a crippled version of non-standard mathematics. That's fine, but it means you can never use Wikipedia as a reference to support your point of view. You have to do all the heavy lifting yourself. If you require explicit enumeration of infinite sequences, then you would deny any infinite sequence exists, therefore your non-standard mathematics is denies T has any content at all. And since T is an empty set, then L, purportedly an onto relation between all counting numbers and the empty set, cannot exist. But you didn't argue against Cantor's diagonal argument, only the existence of infinite sequences, which is a noncontroversial part of standard set theory. Even for you, the diagonal argument works fine for finite sets or for sets without an accepted lexicographic order, because it doesn't depend on any assumptions of size or order. You are arguing against a cartoon of the diagonal argument. What is a helpful (an necessarily finite) visual aid for others has become a stumbling block for you. I disagree with simple. I also disagree that you are allowed to reorder L arbitrarily. You have a lot of work before you have communicated the soundness of this idea. Those people are those people with their beliefs and their fringe presence in mathematics. You haven't equated your viewpoint with any of theirs. Like I said, if you want to embrace non-standard mathematics, Wikipedia glosses are going to be less than useless. Your philosophy is weak tea. The concept of infinity certainly exists both inside and outside of mathematics. An infinite set is a set which is not finite. Now there are different definitions of finite set in ZF set theory, with subsequent different definitions of infinite sets: I: A set is strongly finite iff it is equinumerous with a natural ordinal number. ⊢ Fin = {x ∣ ∃y ∈ ω x ≈ y} Ia: A set if finite iff it is not the disjoint union of two I-infinite sets. ⊢ FinIa = {x ∣ ¬ ∃y∃z((x = (y ∪ z) ∧ (y ∩ z) = ∅) ∧ (¬ y ∈ Fin ∧ ¬ z ∈ Fin))} II: A set is Tarski finite iff every nonempty chain of subsets contains a maximum element. ⊢ FinII = {x ∣ ∀y ∈ ℘ ℘x((y ≠ ∅ ∧ [⊂] Or y) → ∃z ∈ y ∀w ∈ y ¬ z ⊂ w)} III: A set is weakly Dedekind finite iff its power set has no equinumerous proper subset. ⊢ FinIII = {x ∣ ℘x ∈ FinIV} IV: A set is Dedekind finite iff it has no equinumerous proper subset. ⊢ FinIV = {x ∣ ¬ ∃y(y ⊂ x ∧ y ≈ x)} V: A set is V-finite iff it behaves finitely under cardinal addition. ⊢ FinV = {x ∣ (x ≈ ∅ ∨ x ≺ (x +c x))} VI: A set is VI-finite iff it behaves finitely under Cartesian product. ⊢ FinVI = {x ∣ (x ≈ ∅ ∨ x ≈ 1o ∨ x ≺ (x × x))} VII: A set is VII-finite iff it cannot be infinitely well ordered. ⊢ FinVII = {x ∣ ¬ ∃y ∈ (On ∖ ω)x ≈ y} Without the axiom of choice, we can prove in ZF theory: ⊢ Fin ⊆ FinIa ⊆ FinII ⊆ FinIII ⊆ FinIV ⊆ FinV ⊆ FinVI ⊆ FinVII However with the axiom of choice, we can prove: ⊢ FinVII ⊆ Fin Thus: ⊢ Fin = FinIa = FinII = FinIII = FinIV = FinV = FinVI = FinVII and eight notions turn out to amount to the same thing in ZFC. On, the class of "all" ordinal numbers is a concept that makes the extended number line concept of +∞ seem petty. Lévy, A., "The independence of various definitions of finiteness," Fundamenta Mathematicae, 46:1-13 (1958) I would strongly urge you to become familiar with much more of standard mathematics before you seek to embrace a fringe theory which is barely covered by Wikipedia.
rpenner #24 wiki rpenner It's a horizontal list, and you put it in order. These 8 combinations would have 8! = 40,320 different possible random listings/arrangements, one of which would be ordered as you present it above. They all qualify for the comparison process. Cantor may truthfully claim his s of 3 positions is different, by construction, from those compared, but he can't extrapolate concerning the ones not compared. The comparison is always between finite sequences. Assuming the shorthand list, at step 3, s=111, which matches the 8th sequence at that stage of construction, which contradicts his claim. The shorthand set can be determined using standard math, without a correspondence principle. Having done that, the 3 character s must be in one of the 8 subsets of T, one for each prefix. If there is a 9th pattern different from the above list of 8, what is it? For his purpose, s only needs to differ by at least one character from any sequence. In step 1, he eliminates all sequences beginning with 0, step 2, all that begin with 00, step 3...000. etc. Comparing s to patterns 4 thru 7 isn't necessary since they are already different from s, thus gives no more support to his claim. size of an infinite set: A length measurement of a discrete object requires a comparison to a standard (object). An object with infinite extent has only one end, which prevents any such measurement. A finite/discrete sequence of characters can be counted (a form of measurement). An infinite sequence of characters, by definition is non discrete and can't be counted, i.e. has no length/magnitude. Length is a property of finite/discrete entities. The term "size" for an infinite set is as meaningless as "approaching infinity", and where is the "rigor" in that. In summation: For each step of his "diagonal argument", he is forming s by choosing the next element from T. Excluding one of two choices is equivalent to selecting the other. His construction is equivalent to an attempt to show how to form an infinite sequence using methods that apply to finite sequences. He makes conclusions about an infinite subset based on manipulation of one finite sequence, then makes the leap to the end (?), declaring (in his own mind) he has made a sequence that should be in T but wasn't. Unlike the tv program "the millionaire", for Cantor there is no "final answer", i.e. the final comparison is always out of reach. This generates another question. How would you know an infinite set is complete? And what if: Cantor succeeds in forming a sequence not in his list. He adds it at the end, and assigns it the next natural number, since the set N is never empty! rpenner Then you would not have approved of Wiki's use of it in the previous edition of Feb 2013! I used it, knowing its meaning from the context. As I occasionally note, Wiki articles can morph, since anyone can be "editor for a day", so "come on down!". I was not aware that there are sacred symbols reserved for specific purposes.
The diagonal argument is opaque to you until you understand the difference between a list (or "indexed set") and a set, which is the difference between L and T.
I represented the set as a list in a 1-dimensional medium so it has an arbitrary order -- but, as I already pointed out, that order plays no part of the definition or structure of a set. Thus {0,1} = {1,0} = {x : x is a binary digit} = {x: x is a natural number less than 2} Thus {3, 2, 1} = {3,1,2} = {1,2,3} = { x: x is a counting numbers less than 4}. Thus { "a", "e", "i", "o", "u" } = { "a", "i", "u", "e", "o" } = { x : x is a string lower-case ASCII letter of length 1 corresponding to a letter which is always an English vowel }. The axiom of extensionality says the identity of a set is determined solely by its contents, not it's color, not it's font and not it's order. http://mathworld.wolfram.com/Zermelo-FraenkelAxioms.html That's because the motivating concept of a set is generalization of a bag which holds things. But while the philosophically naive concept of a set ran into logical paradoxes, axiomatic set theory exists to discuss sets which lack any of the known logical paradoxes. No, because T was a set of all functions from {1,2,3} into {0,1}. Any comparison would be with L, which is a particular function from {1,2,3} into T. This sentence cannot be reconciled with the assumption you understood the diagonal argument. I went back to my convention in post #3 to use R for the base set, not \(\mathbb{N}\) or N because there is no concept of any order on of R being used. \(\mathbb{N}\) and {1,2,3} both have an intuitive order to them which is unfortunate to phyti's education about sets. In the cartoon: R = {1,2,3}, B = {0,1}, T = \(B^R\) = {x : x is a function from R into B}, P = \({B^R}^R = T^R\) = { x: x is a function from R into T}. L ∈ P which is another way to say L is a function from R into T. For all y in R, define \(z_L(y) = 1 - L(y)(y)\), thus z is a function from R into B, thus \(z_L \in T\). But there is no y such that \(\color{red} {L(y) = z_L}\). There was no process, no stepwise construction and no dependence on a particular order of R, B, T, or even L. When we prove for all L in P that no L points to all elements of T, then we prove \(B^R\) has a larger cardinality than R. Since that proof didn't depend on either order or the finiteness of R, then it applies to all sets. By imposing order and finiteness of processes you add to the cartoon unsound properties that don't exist in sets or in Cantor's diagonal argument. Your focus on stepwise processes is not part of standard mathematics which has no problems with π or the sole real root of \(x^5 - x - 1 = 0\) * even though there is no finite construction process for representations of these numbers with rational arithmetic or geometric constructions. (* Imagine my embarrassment if I had written \(x^5 + x + 1 = (x^3-x^2+1)(x^2+x+1) = 0\) or \(x^5 + x - 1 = (x^3 + x^2 - 1)(x^2 - x + 1) = 0\).) Cantor's argument gives \(R \prec \left\{ 0,1 \right\}^R\) for any set R. ("≺" is the "strictly less than" sign for cardinality of sets. It is pronounced "strictly precedes". Both "A strictly precedes B" or "B strictly dominate A" are correct ways to read "A≺B" which is a statement of cardinality, not the content of the sets.) For any finite set of size n, it proves \(n < 2^n\), but it shows that if one infinite set exists then there is an never-ending sequence of progressively larger infinities and it gives a prescription on how to construct (at least some of)** them. (** If the Generalized Continuum Hypothesis is accepted, then this is all of them.) Standard mathematics does, in fact, postulate that at least one such infinite set does exist, the set of all natural numbers, ω. Wrong. You have confused T and L again, and thus demonstrate you have never understood the topic. Four times incorrect. Once because you have imposed order on sets. Second because you mix ordinal and cardinal concepts of number. Thrice because you ignore the definitions of equinumerosity and cardinality. Four times, because you may compare an infinite object with a finite object and say the finite one is lessor, a comparison which is a measurement. In standard mathematics, there is more rigor than your conflation of "discrete" and "finite". Ordinal sets and Cardinal numbers are two different generalizations of number, the first generalizes the stepwise process of counting, the second generalizes pairing off items from two bags. They are good generalizations of number, in that they give identical results for all finite numbers. But you ignore all that rigor to misstate standard mathematics which has many results on the topic of infinite sets, infinite cardinal numbers and transfinite ordinals. Wrong. There is no concept of "step". The set T has no concept of "order" and thus no "next element". What is at issue is L, a particular function from R into T. But L is never a function from R onto every element of T. Thus R ≺ T ≝ {0,1}^R . If R is an infinite set, then {0,1}^R is also an infinite set -- no need to "complete" anything.
