Talk:Ugly duckling theorem

Yes, this is pretty much a copy of the page on Everything2 with the same name. I can do that: I wrote that one. Probably needs some formalizing and formatting. Clsn 18:15, 9 May 2006 (UTC)

wtf?

Blueaster 08:16, 24 October 2006 (UTC)

References and wrong content

Please add some print references to this article, not just a link to another page you have written.

Link added to Watanabe's book, or at least a scan of the relevant part of it, which is what I could find. Maybe my statement of it is original, but the research isn't.

The sentence you added again is clearly wrong; there must be additional assumptions on the theorem that says that the set of attributes representing each object has a 50/50 chance of containing any particular attribute. CMummert 03:51, 9 January 2007 (UTC)

the German version

I find a quite detailed article on this topic in the German wikipedia: de:Ugly-Duckling-Theorem, but I don't understand German. So it would be great if someone could translate that one into English. Took 02:45, 5 March 2007 (UTC)

It would be nice if someone could either translate that one or fix it, as the mathematics is wrong. — Arthur Rubin (talk) 22:19, 3 May 2008 (UTC)

Dead link

http://www.igm.hokudai.ac.jp/crg/download_files/watanabe.pdf —Preceding unsigned comment added by 212.198.66.165 (talk) 20:12, 25 September 2010 (UTC)

"if they are only distinguished by their names"

This statement is blatantly false and ruins the entire purpose of the ugly duckling theorem. It stands to reason, I believe, that this should be changed to "if each can be distinguished by a unique name" or something similar. Regardless of how many extra distinguishing features there are, the total number of possible classes will not change if the names are unique, which is the entire point, if I understand this theorem correctly.

I will let someone with a better understanding of the theorem rephrase that statement. — Preceding unsigned comment added by 213.125.208.5 (talk) 12:48, 28 June 2013 (UTC)

Capitalisation

The article uses "Ugly duckling theorem", "Ugly Duckling theorem", and "Ugly Duckling Theorem". This should be unified. 1234qwer1234qwer4 (talk) 22:49, 9 June 2020 (UTC)

 Done I changed all occurrences to "Ugly duckling theorem", as in the article title. However, the title of Anderson's tale is still capitalized as "The Ugly Duckling"; I hope this is ok. - Jochen Burghardt (talk) 07:11, 10 June 2020 (UTC)

Thanks. Yeah, I thought it would make sense to write "Duckling" with a capital letter, but a web search returned mostly occurrences with all letters capitalised (probably in headings) or with only the first of them (I think). There is still the possibility to write "ugly" with a lower-case u though, as the article title doesn't tell how to capitalise the first word. 1234qwer1234qwer4 (talk) 08:27, 10 June 2020 (UTC)

@Jochen Burghardt: Apparently, you didn't, but I fixed the rest now. 𝟙𝟤𝟯𝟺𝐪𝑤𝒆𝓇𝟷𝟮𝟥𝟜𝓺𝔴𝕖𝖗𝟰 (𝗍𝗮𝘭𝙠) 12:56, 24 December 2020 (UTC)

@1234qwer1234qwer4: I made an attempt (on 10 Jun), but apparently missed some occurrences. Thanks for fixing that! - Jochen Burghardt (talk) 16:16, 24 December 2020 (UTC)

@Jochen Burghardt: The choice to only capitalize "Ugly" does not make any sense. Either the theorem uses "Ugly Duckling" as a proper name or both "ugly" and "duckling" should be lower case. In general, Wikipedia prefers to avoid unnecessary capitalization, per MOS:CAPS and more specifically MOS:SCIMATH. Lester Mobley (talk) 03:34, 28 April 2021 (UTC)

@Lester Mobley: I guess you are aware that the name refers to Anderson's fairy tale "The ugly duckling". I am not sure how this is to be handled per MOS:CAPS. If you are, I won't object to your suggestions. When I reverted Trappist the monk's recent edit, I just wanted to hint at this discussion. In case any of you decides to change the capitalization, please do it consistently throughout the whole article, the I'll be fine with it. - Jochen Burghardt (talk) 12:08, 28 April 2021 (UTC)

For the record, I have edited this article exactly once and at this writing, have not been reverted. My edit had nothing to do with this uppercase-lower-case squabble about which I have no opinion. Please leave me out of it.

—Trappist the monk (talk) 12:46, 28 April 2021 (UTC)

Oops, sorry, the edit I meant was by JayBeeEll. - Jochen Burghardt (talk) 18:06, 28 April 2021 (UTC)

Although I am not that well-versed in the manual of style, I think that in line with WP's general preference for lower case and the naming of theorems on Wikipedia (for example, as JBL mentioned below, "hairy ball"), I would pick "the ugly duckling theorem"; in this capitalization, the theorem can be referring to the ugly duckling from the story, rather than the title of the story. Since you are fine with a consistent change of capitalization and JBL supports lower case, I will go ahead and make it all lower case. Sorry if I created a "squabble". Lester Mobley (talk) 19:41, 28 April 2021 (UTC)

 Done Lester Mobley (talk) 20:07, 28 April 2021 (UTC)

I agree with Lester Mobley: the current situation is very weird, and "the ugly duckling theorem" is consistent with both how other theorems are called on Wikipedia ("the hairy ball theorem" etc.) and with common sense. (Currently capitalization is not standard in the article.) --JBL (talk) 18:15, 28 April 2021 (UTC)

Countable set of objects to which the Ugly duckling theorem applies

This discussion has been closed. Please do not modify it.
The following discussion has been closed. Please do not modify it.
"couldn't find strings "countabl" or "finit" in Watanabe.1986; subtraction is undefined for limit ordinals, let alone binomial coefficients (used on p.7) [of "Epistemological Relativity" by Satosi Watanabe, further ER]". That is true that subtraction is undefined for limit ordinals. It is moreover true that addition and multiplication of ordinals is non-commutative. Therefore why would one introduce ordinals, let alone limit ordinals to the Ugly duckling theorem? The author of this profound theorem clearly considered natural numbers: "We start with a certain number $n$ of predicates" (cf. ER p. 6). The term certain number is clearly non-negative integer. "An object satisfies or negates each starting predicate, therefore it corresponds to an atom [atomic predicate]." (cf. ER p. 6). Then he shows that "the number of predicates of rank $r$ that includes given two atoms (...) is independent of which atoms are (...) given" (cf. ER p. 7), which conclusion is the Theorem of the Ugly Duckling. Derivation of this theorem in terms of predicates and their ranks $r$ allowed Watanabe to additionally consider implicational constraints among the predicates, the existence of which reduces the number of the predicates. But the same conclusion can be reached in a simpler way if (as in this article) one considers all the possible ways of making sets out of the $n$ objects. For three objects it gives the list illustrated below the picture with 2 swans and the duckling which clearly shows that any two birds share 4 classes out of 8 available. That remains true for any $n$ objects. There is a close connection of such an articulation of this theorem with Cantor's diagonal argument, but it nevertheless remains valid for any countably infinite set of $n$ objects in the universe.Guswen (talk) 16:13, 15 April 2021 (UTC) I don't understand your above argument: You first say that n is a natural number (that is, finite). In contrast, in your last paragraph, you choose n to be countably infinite. Do you consider two different versions of the theorem (for finite n, and for countably infinite n)? If Watanabe "clearly considers natural numbers" (I agree with that), do you think there is any reference (if yes, please provide it) about a similar theorem for countably infinite numbers? Or don't you agree that each natural number n is finite? Or what else do I misunderstand in your argument? - Jochen Burghardt (talk) 18:30, 15 April 2021 (UTC) Yes. $n$ is a natural number and that is why it is countably infinite, as the set of natural numbers is countably infinite ($\aleph _{0}$). There is just one version of this theorem, clearly for countably infinite $n$ (any countably finite $n$ is but a subset of the countably infinite $n$). Similar theorems for countably infinite numbers are plenty. Take, for example this paper about Laplacians. Fact, here $n$ is taken to denote the dimensionality of a continuous Euclidean space $\mathbb {R} ^{n}$ but I do not see a reason to exclude that this could not be countably infinite. Take the combinatorial proof of the Boltzmann’s H-theorem. It is not based on tangible physics. Just a mathematical model of absolutely elastic molecules (non-dissipative mathematical points) "colliding" with each other. Take any theorem that employs/uses, at least in part/is based on a concept of "a certain number". "Certain numbers" are simply countably infinite. They do not even remotely resemble a fallen Christmass Tree of ordinals. Guswen (talk) 21:34, 15 April 2021 (UTC) Thanks for your explanation; I see the point of disagreement now. In my understanding, the set ℕ of natural numbers has countably infinitely many members, but each of them is a finite number. I am pretty sure this understanding is shared by almost all mathematicians. The finiteness of each member is easily proven by induction (Peano axiom 9, choose φ to be the property of being finite): 0 is finite, and if some natural number i is finite, then its successor i+1 is finite, too. Hence, by induction, each natural number is finite. For these reasons, I think that in the Ugly Duckling Theorem, "$n$ is a natural number and that is why it is" - countably finite, or just finite, for short. - Jochen Burghardt (talk) 07:42, 16 April 2021 (UTC) The definition of the successor $S(n)=n+1$ establishes countable infiniteness ($\aleph _{0}$) of natural numbers $\mathbb {N} _{0}$. There is no finite limit $n_{max}$ as $S(n_{max})=n_{max}+1>n_{max}$. Therefore, indeed, each natural number is finite but they are, as a set, countably infinite. In my opinion this theorem applies both to any finite $n<n_{max}$, as well as to $n_{max}$ itself, even though the latter is formally undefined (or rather unknown).Guswen (talk) 10:40, 16 April 2021 (UTC) You didn't give a precise construction of your $n_{max}$ (I think this is impossible to do), so you can't use it in an argument. Anyway, a citation would be needed for applicability of the theorem to an infinite n. - Jochen Burghardt (talk) 17:07, 16 April 2021 (UTC) Well, I think the definition of a natural number $n$ (or $n_{max}$) is precisely (rigorously) defined by Peano axioms of arithmetic. Namely it is any number greater than or equal to zero, such that differs from the preceding and/or ("or" applies solely to 0) succeeding number by one (successor of zero). And that is all that is required for the proof of the Ugly duckling theorem. Guswen (talk) 08:22, 18 April 2021 (UTC) I have just found a citation to support countably infinite number of objects in this theorem. Obviously the definition of a natural number $n$ in the context of this theorem should be modified to "any number greater than zero, such that it differs from the preceding and the succeeding number by one". This theorem makes no sense for "zero objects".Guswen (talk) 20:53, 18 April 2021 (UTC) Sorry, for the delay; it took me a while to dive into Woodward.2009 (which is very sloppily written) and its citations Schaffer.1994 and Schumacher.Vose.Whitley.2001 (which explains the framework used by Woodward more properly). None of these papers are concerned directly with the Ugly Duckling Theorem (UDT), let alone with its proof. Instead, they are about learning functions from input/output examples, in particular boolean functions. Apparently Woodward (who is the only author who mentions the UDT) sees a relation between the UDT and a theorem of Schaffer saying that all learning algorithms have the same (poor) generalization performance. I added a suggestion for a paragraph in section "Discussion", although I couldn't figure out the relation Woodward might have in mind. I reverted your most recent 2 edits since Woodward's paper give no indication that the old UDT proof can that simply be generalized to infinite n. His proofs about infinite function domains are given on p.874, Sect.V.B and V.C; they are completely different from the proof at Ugly_duckling_theorem#Mathematical_formula. - Jochen Burghardt (talk) 19:39, 25 April 2021 (UTC) Well, it doesn't matter much if a publication is sloppily written, as long as the information it provides is verifiable. Again, UDT applies to natural numbers that commute under addition ($2+3=3+2$ [objects]), not to ordinals that do not commute under addition. Natural numbers are established by Peano axioms and the axiom of the successor function $S(n)=n+1$ establishes their countable infiniteness ($\aleph _{0}$). The definition of a countable set, the elements of which can always be counted (even if the counting may never finish), pertains to $n$ objects to which the UDT applies. Any set of $n\geq 3$ objects can be classified in $2^{n}$ ways and any $2$ objects from this set share $2^{n-1}$ classes. If $n-1$ makes you uneasy, kindly note that one could define natural numbers using a predecessor (instead of successor) function $P(n)=n-1$ such that $P(0)$ is false (that is, there is no predecessor of 0). Woodward proofs concern "all Boolean functions with $n$ combinations of inputs (...). There are $2^{n}$ possible Boolean functions" (cf. V.A). This is the same as in the proof of the UDT that I have just quoted. If you disagree with these arguments kindly consider putting our dispute under some arbitration.Guswen (talk) 08:21, 27 April 2021 (UTC) You need to distinguish between the set of all natural numbers (which has countably infinitely many members) and any of its members (a.k.a. natural number), which is finite in any case. As far as I know, natural numbers can not be defined via zero and predecessor, since then the axiom of induction cannot be expressed. Even if UDT would apply to an infinite n and Woodward's article would imply that, it would not be clear that the current proof can just be kept for the infinity case - for this reason, I reverted your recent edit. Asking someone else to help settle our dispute is a good idea; I'll post it at Wikipedia talk:WikiProject Mathematics. - Jochen Burghardt (talk) 12:22, 27 April 2021 (UTC)  Done See Wikipedia_talk:WikiProject_Mathematics#Ugly_duckling_theorem. - Jochen Burghardt (talk) 12:29, 27 April 2021 (UTC) References Thank you. I do not see a problem with recursion (cf. e.g. factorial recursive formula) for the predecessor function $P(n)=n-1$. However, natural numbers are not closed under subtraction and that, indeed, can render such a definition problematic or impossible. Guswen (talk) 14:29, 27 April 2021 (UTC) As we received no feedback whatsoever to our dispute at Wikipedia talk:WikiProject Mathematics after two weeks since it has been posted, it stands clear to me that the UDT applies to countable sets (not necessarily infinite) of $n$ objects. Commutativity under addition is a prerequisite to count the objects (2+3=3+2=5 [objects]).Guswen (talk) 07:39, 10 May 2021 (UTC) Probably you have received no feedback because your argument is obscure to the point of incomprehensibility, and the previous state of the article was fine. --JBL (talk) 13:41, 12 May 2021 (UTC) @Guswen and JayBeeEll: I have available both Watanabe's 1969 book, and his 1965 book chapter (in French, cited in the 1969 book). As far as I could see, he didn't explicitly discuss finiteness or infiniteness of m (his variable name for the number of "object types") in any of them. However, in the 1969 book, there are some strong indicators that he tacitly assumed m to be finite: in the preparatory section 7.5. referred to from the proof, he uses a "matrix" (also called "table") of size m×n (p.363 top), a "permutation" of its rows (p.367 mid), and the binary logarithm "log2" of m (p.371 mid). In the proof itself (sect. 7.6), he uses subtraction and binomial coefficients involving m (p.377 mid, cf. the Wikipedia article). None of this makes sense for infinite m. - Jochen Burghardt (talk) 18:16, 24 May 2021 (UTC) Thanks, Jochen Burghardt. This seems utterly conclusive; also Guswen's edits and explanation are completely incomprehensible. Guswen, if you continue to edit against consensus, you will find yourself blocked for edit-warring. --JBL (talk) 18:20, 24 May 2021 (UTC) I reviewed the above conversation, and support Jochen and JBL. From what I can tell, Guswen does not realize that all natural numbers are, by definition, finite, and that $\aleph _{0}$ is not a natural number. Watanabe's proof obviously falls apart in that case, because $2^{n}$ is a finite number when $n$ is a natural number. But $2^{\aleph _{0}}$ is uncountable infinity. You cannot enumerate an uncountable infinity of extensional properties, because you cannot enumerate an uncountable infinity of anything. 67.198.37.16 (talk) 22:09, 26 May 2021 (UTC) But how about $2^{{\aleph _{0}}-1}$? In other words, what if one excludes any sequence $s_{n}$ from the set T of all infinite sequences of binary digits considered by Georg Cantor in his diagonal argument to show that the set T is uncountable? Or what if one excludes this special sequence $s$ that he constructed in his proof? Then the proof by contradiction that he used to establish the notion of uncountable sets fails. Hence $2^{{\aleph _{0}}-1}$ is the cardinality of a countable set, a supremum of an uncountable infinity. Any two objects in the UDT have exactly the same number of classes in common, namely $2^{n-1}$, and that is all one needs to prove this theorem. One does not have to enumerate an uncountable infinity of extensional properties. Guswen (talk) 07:32, 15 June 2021 (UTC) If you are right, you have done some successful original research, and you wouldn't find a reliable source for that ("Cantor" doesn't appear in the index, p.585, of Watanabe.1969). So, discussing it here is waste of time; instead, you should discuss it with a mathematician outside of Wikipedia. - My personal view on your above post is that (1) ${\aleph _{0}}-1$ equals $\aleph _{0}$ in cardinal arithmetic and is undefined in ordinal arithmetic, (2) Cantor doesn't construct a fixed ("special") sequence, but counstructs one sequence for every possible enumeration of all sequences, (3) there are "disproofs" of Cantor's theorem that are based on subsequent treatments of $s$ to remedy the contradiction in Cantor's proof, but they are wrong, (4) I feel that the issue of Cantor's theorem and that of the UDT should be separated. You should also be aware that if Cantor's proof wasn't correct, this would render the whole theory of cardinal arithmetic nonsensical. - Jochen Burghardt (talk) 09:23, 15 June 2021 (UTC) Thank you. But I don't know any mathematician in this field outside of Wikipedia. On the other hand, there are plenty of mathematicians inside of Wikipedia (like yourself) but no one is particularly keen to discuss these issue. Our call for arbitration remained unanswered. Ad. 1. ${\aleph _{0}}-1$ equals $\aleph _{0}$, indeed, and thus $2^{{\aleph _{0}}-1}$ equals $2^{\aleph _{0}}$. But $2^{\aleph _{0}}-1$ does not seem to be equal to $2^{\aleph _{0}}$. Cantor needed the whole set of $2^{\aleph _{0}}$ countably finite binary sequences $s_{k}$ to show that this set is countably infinite. His proof fails for a set containing $2^{\aleph _{0}}-1$ sequences, due to this missing (-1) sequence. Ad. 2. I disagree. Cantor does construct a "special" sequence $s$ having $k_{th}$ bit complementary to $k_{th}$ bit of a sequence $s_{k}$ from the list of all possible countably infinite sequences, to show that this "special" sequence $s$ is not included in this list. I obviously agree that $s$ is not "fixed". But "fixed" (or "constant") is not the same as "special". Ad. 3. Cantor’s argument is brilliant and bulletproof. No wonder that all the “disproofs” that you mention are wrong. It's also clear to me why he was publicly humiliated and criticized for his outstanding works by his contemporaries. Ad. 4. I disagree. The UDT and Cantor's diagonal argument are intertwined along with the notion of the power set, the continuum hypothesis, etc. The ever growing list of veridical paradoxes hints that any naive reductionism is wrong. Guswen (talk) 06:45, 16 June 2021 (UTC) (correction of Ad. 1 Guswen (talk) 23:01, 16 June 2021 (UTC)) Just some thoughts: You might find a mathematics course at a Folk high school where you can discuss your arguments with the teacher, or you may hire a student to help you making them waterproof. You might also work through a mathematics textbook to practise rigorous formal proof, and then apply your gained experience to your own arguments. There is even software that checks your proofs for formal correctness (e.g. Coq, Isabelle (proof assistant)), however all (I guess) of them are difficult to learn and require to make explicit every detail of the proof (no "it is easily seen that"). See Gödel's_ontological_proof#Computer-verified_versions for a couple of research papers(!) about formalizing and checking Gödel's alleged proof of the existence of God; like the UDT, it is located at the boundary of philosophy and mathematics. By the way: I appreciate your recent correction of (1). However, from my point of view, several similar errors are still contained in your arguments. For example, according to Cardinal_number#Cardinal_addition, $2^{\aleph _{0}}+1=2^{\aleph _{0}}$, hence $2^{\aleph _{0}}$ does equal $2^{\aleph _{0}}-1$. I don't have the time to look through all your details and try to fix (or just flag) those that I believe are wrong (or just expressed badly? - this is difficult to judge). I guess JBL actually meant something similar when (s)he called your earlier arguments incomprehensible. A student would do this for the paid money, and you could save money if you made your arguments as formal as you can before passing them on the be checked. - Jochen Burghardt (talk) 12:21, 17 June 2021 (UTC) I find the notions of ordinals, cardinals, transfiniteness, etc. devious. There are only two infinities: 1. countable infinity established by Peano axioms of arithmetic, and 2. uncountable infinity established by Cantor's diagonal argument. All the rest is (inevitably lost) man's struggle to cope with them. Kindly contact me privately if you'd like to carry on our discussion any further. Ps. You can't save money if you're groping for truth.Guswen (talk) 08:50, 18 June 2021 (UTC)