Jump to content

User talk:Jochen Burghardt: Difference between revisions

Page contents not supported in other languages.
From Wikipedia, the free encyclopedia
Content deleted Content added
Line 224: Line 224:
:Oops, my revert was incomplete, while my edit summary referred to a complete revert; I fixed this meanwhile. Here are some more details of my reasons for the complete revert:
:Oops, my revert was incomplete, while my edit summary referred to a complete revert; I fixed this meanwhile. Here are some more details of my reasons for the complete revert:
:The link "[[sequence]]" is at best unneeded, possibly even misleading, since the target article mainly talks about properties of number sequences. Renaming "N" to "i" is pointless. [[WP:EASTEREGG]]s are strongly discouraged by Wikipedia's policy. Moreover, [[mathematical induction]] is a school-level introductory article, so details like the names of parts of implications needn't be introduced there. Moreover, the inductive step is not just an implication, but a universal quantification of an implication (but this needn't be mentioned in the article, either). The word "implication" is even used in [[Mathematical_induction#A_trigonometric_inequality]]; this should be sufficient. - [[User:Jochen Burghardt|Jochen Burghardt]] ([[User talk:Jochen Burghardt#top|talk]]) 16:07, 30 November 2020 (UTC)
:The link "[[sequence]]" is at best unneeded, possibly even misleading, since the target article mainly talks about properties of number sequences. Renaming "N" to "i" is pointless. [[WP:EASTEREGG]]s are strongly discouraged by Wikipedia's policy. Moreover, [[mathematical induction]] is a school-level introductory article, so details like the names of parts of implications needn't be introduced there. Moreover, the inductive step is not just an implication, but a universal quantification of an implication (but this needn't be mentioned in the article, either). The word "implication" is even used in [[Mathematical_induction#A_trigonometric_inequality]]; this should be sufficient. - [[User:Jochen Burghardt|Jochen Burghardt]] ([[User talk:Jochen Burghardt#top|talk]]) 16:07, 30 November 2020 (UTC)
::I have to disagree re the mentioned details and the presumed status of school-level introductory article. Aren't logical operators acting on propositions and predicates included in this school-level? The article should also mention the interaction between implication(s) and universal quantification, even if this interaction is a bit subtle (or perhaps other attribute to be used instead of ''subtle''?). Secondly, it doesn't seem to me that linked article [[sequence]] is mainly about number sequences. As long as the number n in P(n) is just a number of order of individual sentences (ordered by succesive implications), as I see you already said on the talk page, I don't think the link to sequence is such a bad thing, almost as if a vandalism. Also I do not quite understand why the renaming of "N" to "i" be considered pointless, N mainly being to close to the typeface/simbol of the whole set of natural numbers.

::I see that talk page of the article hasn't been used in connection with the edits in the article. I'll mention there these aspects emerged from here, the school-level introductory article and the need to mention the parts of the implication and the interaction of universal quantification with the implication.--[[Special:Contributions/86.127.34.116|86.127.34.116]] ([[User talk:86.127.34.116|talk]]) 23:02, 30 November 2020 (UTC)
::(Also the need to make a total reversion is not quite OK, it gives the impression that you want to have the last word re the edits in the article.) So please propose a wording/formulation re the mentioned aspects or corrections to my proposed formulation which I'll put on the talk page of the induction article and possible talk pages of other articles like [[universal quantifier]], [[material conditional]], [[consequent]], etc....--[[Special:Contributions/86.127.34.116|86.127.34.116]] ([[User talk:86.127.34.116|talk]]) 23:02, 30 November 2020 (UTC)

Revision as of 23:03, 30 November 2020

Meaning of a German word re mathematical induction - Vollständige Induktion

Hi! I see that the German page on Matematical induction has the name Vollständige Induktion. What is the exact meaning of this German word? What other possible shades of meaning exist beside complete? I see that Google Translate gives as equivalents full, complete, total, entire! Thanks!--109.166.135.99 (talk) 19:15, 4 January 2020 (UTC)[reply]

I'd translate it with "complete" in this context. However, in English "complete (mathematical) induction" means "strong (mathematical) induction" - in contrast to "plain mathematical" induction". In German "vollständige Induktion" just means "plain mathematical induction" - in contrast to "philosophical induction". The latter is what humans do in everyday reasoning, viz. inferring ∀n. P(n) from a few observations like e.g. P(1), P(2), P(3); this is deemed "unvollständig" (Engl.: "incomplete"). - Jochen Burghardt (talk) 19:33, 4 January 2020 (UTC)[reply]
Very interesting quote at WikiQuote from Florian Cajori, also says about vollständige Induktion and its use by Richard Dedekind.--109.166.135.99 (talk) 00:06, 5 January 2020 (UTC)[reply]

Other names for math induction - reasoning by recurrence

Hi again! Re math induction, I see that the French wikiarticle has a title that in translation would be reasoning by recurrence! (I see that also the recurrence wikipage mentions matematical induction at See also.) Have you encountered this name, perhaps even in German sources under a German translation?--109.166.135.99 (talk) 19:24, 4 January 2020 (UTC)[reply]

No, I'm not aware of that name. The closest association is primitive recursion, a way to define a function that is (in some sense) based on mathematical induction. - Jochen Burghardt (talk) 19:37, 4 January 2020 (UTC)[reply]
The name reasoning by recurrence seems to be due to similarity with a recurrence relation involved in the structure of math induction being based on the succesive implication from the i value to the next i+1 (and then from n to n + 1) , this transition from a value to next (+ 1) is like the recurrence relation for terms of a sequence.--109.166.135.99 (talk) 22:36, 4 January 2020 (UTC)[reply]
Very interesting quotes re math induction, presenting also history details at WikiQuotes.--109.166.135.99 (talk) 23:36, 4 January 2020 (UTC)[reply]

Bug in watchlist?

I believe to have found a bug in the algorithm computing the watchlist, and would like the programmers to check this. I'm using the {{help}} template because I don't know better how to reach them.

My observations are these (all times are German local time):

  • In my preferences, I enabled the features "Hide bot edits from the watchlist" and "Hide my edits from the watchlist".
  • At the page "Schröder–Bernstein theorem", the current top of the watchlist looks like this:
   19:03, 14 January 2020‎ AnomieBOT talk contribs‎ m 19,187 bytes +18‎ Dating maintenance tags: <{{Cn}}
   18:43, 14 January 2020‎ Wcherowi talk contribs‎ 19,169 bytes +6‎ →‎Alternate proof: needs citation
   10:57, 14 January 2020‎ Dunloskinbeg talk contribs‎ 19,163 bytes +13‎ →‎Alternate proof
   10:37, 14 January 2020‎ Dunloskinbeg talk contribs‎ 19,150 bytes +1,797‎ →‎History
   20:31, 11 January 2020‎ Jochen Burghardt talk contribs‎ 17,353 bytes -32‎ →‎History: fix another link
  • I got a watchlist notice after the 10:57, 14 January 2020‎ Dunloskinbeg edit; this is ok.
  • However, I didn't get a notice after the 18:43, 14 January 2020‎ Wcherowi edit; I consider this a bug.
  • I didn't get a notice after the 19:03, 14 January 2020‎ AnomieBOT edit; this agrees with my preferences settings.

I suspect that AnomieBOT's edit may have masked out Wcherowi's edit. A later edit by myself masking a former would be ok; and possibly the algorithm computing the watchlist handles a later bot edit in the very same way, although for this case it is not ok. - Jochen Burghardt (talk) 11:46, 15 January 2020 (UTC)[reply]

You are correct, that is a bug: phab:T11790. It's been a known problem since since 2007, but fixing it isn't a current priority for any of the WMF development teams. --AntiCompositeNumber (talk) 17:10, 15 January 2020 (UTC)[reply]
Ok, I see. Thanks for the quick response. - Jochen Burghardt (talk) 20:36, 15 January 2020 (UTC)[reply]

Need small change to Georg Cantor's first set theory article

Hi Jochen, I'm currently working on preparing Cantor's first set theory article for a nomination to featured article. While working on accessibility of information in a diagram, I used a screen reader to read the text and found it read both an and aN as "a n" (I had hoped it would read the latter as "a cap n" or "a sub cap n" but it didn't). So my choice of aN and bN was bad for people who depend on screen readers. I think aL and bL would be better. I'm choosing "L" to stand for "last". I would greatly appreciate it if you could change the 4 places that need changing: 3 of them can be found by searching for "last interval". I could change these 3, but since the changes are in a published article, I think all 4 changes should be done at the same time. The fourth occurrence of aN and bN is within your file "Cantor's first uncountability proof Case 1 svg.svg". Thanks again for the work you have done on the article, my featured article mentor is quite impressed with the article and I believe that your diagrams contribute a lot to the key proof in the article. Thank you, RJGray (talk) 17:44, 18 January 2020 (UTC)[reply]

 Done I also changed the corresponding Pdf file. - Good luck with the review process! Jochen Burghardt (talk) 18:20, 18 January 2020 (UTC)[reply]

Thanks for taking care of it so quickly. On my screen, everything was changed except in the diagram where aN and bN had not changed. I tracked down the problem to my browser: I changed browsers from Chrome to Opera and everything worked fine. Chrome may have cached the old copy of the svg file somewhere. I've never had a problem like this before. Thanks for wishing me good luck on the review process -- the featured article process is much tougher than the good article process. My mentor started me off with 16 items to change or consider. It's a good learning experience and is already making me a better Wikipedia writer. —RJGray (talk) 21:36, 18 January 2020 (UTC)[reply]

I repeatedly had a similar problem when I uploaded a new version of an image to commons and viewed its imported copy at English wikipedia. Usually, doing a few times "refresh (no cache)" helps; in Firefox. it is encoded as "Control-Shift-r". - Jochen Burghardt (talk) 16:57, 19 January 2020 (UTC)[reply]

Thanks, Jochen. The refresh worked fine: Chrome encodes it as "Control-F5, which I've read is also an option used by some other browsers including Firefox and Internet Explorer. However, I noticed a typo on the Case 1 diagram: Above the number line, it has a "c" instead of a "y". This conflicts with the Case 1 text on the left: "every y in this interval ...". RJGray (talk) 13:52, 20 January 2020 (UTC)[reply]

 Done Oops - sorry! Maybe it was called "c" earlier, and I missed the renaming. - Jochen Burghardt (talk) 16:52, 20 January 2020 (UTC)[reply]

The "alternate" proof should be kept

In fact, I found it very clear and convenient for generalizing it from sets to ∞-groupoids (https://homotopytypetheory.org/2020/01/26/the-cantor-schroder-bernstein-theorem-for-%e2%88%9e-groupoids). This reference has a proof in mathematical vernacular, and also a proof formalized in a proof assistant and verified by it. I didn't need to check any reference to make complete sense of it. I would like this proof to be reinstated (with a citation for it, if possible), so that my citation to it still makes sense. No further details for the proof are needed. It may be laconic, but it does have all the necessary information. And I like it very much, much better than the proof that produces three equivalence classes. This proof with two equivalence classes is much better and direct and intuitive. Thank you. — Preceding unsigned comment added by 31.185.241.7 (talk) 19:39, 10 February 2020 (UTC)[reply]

You should copy your above text to Talk:Schröder–Bernstein theorem, so that all editors involved can discuss it. - Jochen Burghardt (talk) 19:49, 10 February 2020 (UTC)[reply]

Fixed-point combinator

Hi Jochen, not sure I understand your objection:

your RHS expr. in the 1st def. of Y, viz. "\lambda f. (\lambda x.f (x x)) (\lambda x.f (x x))", wouldn't be a valid term, its valid prefix, viz. "\lambda f. (\lambda x.f (x x))", would have x as both a bound (1st occ.) and a free (2nd ,3rd occ.) variable; this isn't a fixed point combinator
  1. As stated in Notation »the body of an abstraction extends as far right as possible«, so the outermost level of parentheses to the right of . are actually redundant.
  2. The version that is there now, λf.( λx.(f(xx)) λx.(f(xx)) ), when fully parenthesised actually becomes λf.( λx.( (f(xx)) λx.(f(xx)) ) ) which is definitely not a fixed point operator. Instead, it's important that the two abstractions (λx.f(xx)) have an outer set of parentheses to limit the scope of the bound variable x.
  3. As far as I can see my version made the definition of Y equal to the one in Recursion and fixed points.
  4. I also fixed the »Y demonstration« to be parenthesised identically to the one in Recursion and fixed points and made analogous changes to the demonstration of the Θ computation.

I'm trying to understand where I'm going wrong, so would appreciate if you could point out the errors in more detail.

--Jocki84 (talk) 12:44, 14 February 2020 (UTC)[reply]


Oops, my fault. I matched your term syntax against the rules given in Lambda calculus#Lead, not against Lambda calculus#Notation. The former rules lead to the a context free grammar with rules

E ::= V
E ::= ( E E )
E ::= \lambda V . E
V ::= ((any variable name))

and to the following derivation for the 'valid prefix':

_________________E_________________
\lambda V. ____________E___________
\lambda f. ____________E___________
\lambda f. ( _____E______    E    )   
\lambda f. ( \lambda V. E    E    )    
\lambda f. ( \lambda x. E    E    )   
\lambda f. ( \lambda x. f ___E___ )
\lambda f. ( \lambda x. f ( E E ) ) 
\lambda f. ( \lambda x. f ( V E ) )
\lambda f. ( \lambda x. f ( x E ) )
\lambda f. ( \lambda x. f ( x V ) )
\lambda f. ( \lambda x. f ( x x ) )

The two rightmost occurrences of 'x' are then outside the scope of the '\lambda x'. This should explain my weird-looking edit summary text.

I'll revert my revert, and add a note that the syntax of Lambda calculus#Notation, rather than that of Lambda calculus#Lead is used throughout the article. Sorry for the confusion. - Jochen Burghardt (talk) 08:40, 15 February 2020 (UTC)[reply]

Ah, I had taken your reference to »convenience notation« in your template to refer to Lambda calculus#Notation, so I was confused. Thank you for explanation and re-revert, I'm happy now ;-) --Jocki84 (talk) 08:24, 16 February 2020 (UTC)[reply]

Signature: Predicate and Relation

Hi sir, on the first reason that you reverted my change was that "an n-ary relation is the same as an n-ary boolean-valued function, no matter if written in infix or prefix notation". I disagree with your statement, assuming that you and I both talk about relation and function based on set-theoretic definition. According to Binary Relation, a binary relation R over two sets X and Y is a set of ordered pairs (x, y) consisting of elements x in X and y in Y. That is, it is a subset of the Cartesian product X × Y. Noted, a binary relation is indeed a 2-ary relation. According to Function, a function f from a set X to a set Y is defined by a set G of ordered pairs (x, y) such that x ∈ X, y ∈ Y, and every element of X is the first component of exactly one ordered pair in G. In other words, function f is a binary relation G such that every element of X is the first component of exactly one ordered pair in G. Noted, a unary function f: X → Y or f(x) = y is indeed a 1-ary function, but also by definition, a binary relation. In other words, a 1-ary function is equivalent to a 2-ary relation. According to Arity, a function of arity n thus has arity n+1 considered as a relation.

On the reason for my original change, according to Predicate, a predicate P is a boolean-valued function P: X→ {true, false}. Since the distinction between relation and function is clearly shown above, I believe it is careless to say that predicate is logically equivalent to relation when from the set-theoretic view, it is not so.

Also, on the last reason that you reverted my change was that "the name 'predicate' is standard in textbooks (e.g. Hermes 1973, Introduction to Mathematical Logic)". I completely agree this is the case but with a claim that such usage should only be meant loosely and used sparingly, otherwise risk contradictions.

Noted, there are two notations for a function f:

  1. f: X → Y
  2. f(x) = y

The second notation is very useful in predicate logic because it allows us to define function f using variables x and y. Hence, this allows function f to play well with quantifiers, substitutions, building formulas etc...

However, the most common notation for relation R is: R ⊆ X x Y. If we allow set-builder notation, we also have: R = {(x, y) | x ∈ X and y ∈ Y}. Clearly, both notations are not very handy in predicate logic, such as building formulas. As such, in predicate logic, a predicate R' is written in the functional notation R'(x,y) to describe relation R above. Indeed, predicate R' itself is a boolean-value function that should be explicitly written as R'(x,y) = true if (x,y) ∈ R and R'(x,y) = false if (x,y) ∉ R. Predicate R' can be seen as an indicator function of relation R. In other words, the Cartesian product X x Y, which R is a subset of, is the domain of boolean-value function/predicate R' or R': X x Y -> {true, false}. Thus, we can describe predicate R' as a relation: R' ⊆ X x Y x {true, false}. This is where the real connection between relation R and predicate R' comes from. Also, according to Extension, relation R is indeed the extension of R'.

In conclusion, a relation R is the extension of predicate R' and Cartesian product X x Y such that R ⊆ X x Y is the domain of boolean-value function R'. Both relation and predicate, under consideration of both predicate logic and set theory, are closely related but not logically equivalent. I am looking forward to your opinion on this. Thank you so much for your time sir. Langtutheky (talk) 21:54, 16 April 2020 (UTC)[reply]

These descriptions are isomorphic: every subset of a Cartesian product can be associated a binary boolean function and vice versa. So it is a matter of taste which definition is used. As an analogy, real numbers can be seen as equivalence classes of Cauchy sequences or as Dedekind cuts; when real numbers are defined (e.g.) in a textbook, the exact choice of construction is considered, but later on, when they are used, no one cares about it.
Moreover, a signature is concerned not with functions, relations, or predicates at all, but with symbols for them. The name predicate logic originates from the use of predicate symbols. I'm not aware of any logic book that introduces "relation symbols" and explicitly delimitates this term from "predicate symbols", or vice versa, are you?
Best regards - Jochen Burghardt (talk) 11:28, 17 April 2020 (UTC)[reply]
All boolean-value functions are subset of a Cartesian product but not vice versa, for example, one-to-many relation (multivalued function) does not satisfy the definition of a function in Set Theory. On the other hand, I completely agree that there are isomorphic descriptions such as real numbers as you mentioned. However, in Set Theory, the definitions of function, relation and predicate are distinct and not isomorphic. Of course, a signature is concerned about symbols for functions, relations, or predicates, but at the same time, the underlying assumption is that readers must provide semantics to these terms themselves. You can't really talk about "function symbols" without implying the semantic of "function" under some system; similarly, you can't really talk about "relation symbols" and "predicate symbols" without implying their semantics. To say that "relation symbols" is equivalent to "predicate symbols" is to imply that the underlying semantics for "relation" and "predicate" are equivalent.
On semantics, I am aware that the origins of functions and relations predated Set Theory by centuries. Of course, if one is to choose any isomorphic descriptions of these terms from systems other than Set Theory, or even go as far as to treat them as primitive notions then there is no problem at all. However, Predicate Logic has an intimate relationship with Set Theory as it was found by Gottlob Frege, and later developed by Richard Dedekind and Giuseppe Peano, all of whom are also champions of Set Theory. It is very likely that the definitions of function, relation and predicate are rooted in Set Theory. If this is so then the problem I presented above is still there. As a matter of fact, most of the articles here on Wikipedia regarding Predicate Logics, not just on signature, all points to definitions of function, and relation that are heavily built on Set Theory, thus, all suffer this very problem.
On the traditions that logic books use predicates and relations in place of each other, as I mention above, its understandable why they do so but it does not mean there is no room for improvement to clarify doubts for folks like me who get confused when one treats boolean-value function as logically equivalent (biconditional) to relation under Set Theory. I simply suggest that we should avoid mixing them in the same discussion without the intention to clear the mentioned issue.
Lastly, I accept your revision so that we can just leave things as it stands right now. Thank you for your time.
Best regards, Langtutheky (talk) 16:42, 17 April 2020 (UTC)[reply]

Ordinal number: (Trichotomy)

Greetings Jochen Burghardt. You undid one of the edits to page "ordinal number" with the comment "introduced converse relation symbol without need." I don't agree with your undoing, so I undid it. In trichotomy, the emphasis should be on the relations, not the variables. If the example was about permutations, then switching the variables would be more appropriate. By switching the variables back and forth, row by row, it directs attention away from the relation between them. If you want to keep the equality relation on the middle row, I think that is an acceptable compromise, but changing the variables row by row is distracting and does not make for a clear reading. I hope you understand.

Regards, Jozef Putrycz. Jputrycz (talk) 12:47, 29 April 2020 (UTC)[reply]

@Jputrycz: My point is that the trichotomy law is about one relation and equality. Your edit introdoces the converse relation in addition (tacitly assuming the ">" is the converse of "<"). When the relation is called e.g. R, as in Trichotomy (mathematics)#lead ("... a binary relation R on a set X is trichotomous if for all x and y in X, exactly one of xRy, yRx and x = y holds"), the point is even more obvious: the only way to avoid introducing a new notation like RT is to swap the variables. - Jochen Burghardt (talk) 14:50, 29 April 2020 (UTC)[reply]
@Jochen Burghardt:

Jochen,

Thank you for the detailed reply. It is greatly appreciated because now I have a better idea of where you are coming from. There are a few things I would like to address in your response.

First off, yes, thank you for pointing out that when variables are fixed, the statement "x < y" is in fact not equivalent to "x > y"- that is the exact purpose of fixing the variables in place so as to make clear that the statements are not equivalent. The point here is to demonstrate that only one of the statements is true, and by fixing the variables, and drawing attention to the flipped symbol, it is quite obvious that the statements are different, simply because the relations are different. It is unambiguous, and demonstrates the concept even if it is "just" an instance of a more general form of the concept.

Second, since the focus of this section of the article is on only one of the statements being true, and by simply showing the relations to be different is sufficient, I do not see how focusing on the general form of trichotomous relations is in this particular section of the article appropriate.

Nowhere else in the article is the general form of any of the relations focused upon in the same way you are suggesting for this particular concept. If we are going to focus on the general form of the relation in one section, we must either explain to the reader in a dedicated section of the article why that particular concept was generalized and not others, or we must use the general form in all other sections.

Lastly, the generality of a trichotomous relation isn't what makes the definition of an ordinal number unique. A specific instance of a trichotomous relation allows for comprehension, so while generalities and generalization are of course necessary, they are not necessary in this particular definition for there to be comprehension. Focusing on the abstraction of a trichotomy would draw attention away from the properties of ordinal numbers rather than hone in on them. The general form of a trichotomy is more appropriate for an article on general relations, and of course, trichotomous ones.

Regards, Jozef Putrycz Jputrycz (talk) 15:39, 29 April 2020 (UTC)[reply]

Sets are unordered

Thank you for reviewing my edits to Set (mathematics). When I first read the article, I noticed that the unordered property of sets was not mentioned, so I added it. Then, as I was reading the talk page, I came upon this section, Talk:Set_(mathematics)#Unordered?, where another editor apparently made the same "improvement" as I just did. The objection was that "ordered lists are also sets." I attempted to avoid this objection by the qualification "Unless otherwise qualified."

In any case, I do not think the definition of "set" is complete, unless the unordered property is noted. I feel satisfied with changes you made to the article, but apparently another feels concerned we must allow for special cases of ordered sets.

I hope the unordered property does not get removed again.

I will watch this spot in case you wish to comment.

Thanks again for your work on this article. Comfr (talk) 03:52, 16 May 2020 (UTC)[reply]

Thanks for the hint to Talk:Set_(mathematics)#Unordered?. I don't agree that ordered lists are also sets, although the former can be implemented by the latter. As an analogy, rational numbers can be implemented by (pairs of) integer numbers, yet both aren't the same. I agree with you that the unordered property is essential for sets, and intend to defend that phrase in the article. - Jochen Burghardt (talk) 07:01, 16 May 2020 (UTC)[reply]
Thanks for your support. Comfr (talk) 15:40, 16 May 2020 (UTC)[reply]

Rationale for precisification redlink

I redlinked precisification in the vagueness article, which you reverted, and I've just restored. Here's my rationale. Clearly, its surface definition is simply "making more precise", but I think there's clearly more meaning to it as a philosophical/logical term: see [1], [2] and [3]. I don't know enough about these topics to start writing an article on them, but the term is certainly article-worthy. -- The Anome (talk) 11:47, 7 August 2020 (UTC)[reply]

(I answered at Talk:Vagueness#Rationale_for_precisification_redlink.) - Jochen Burghardt (talk) 12:08, 7 August 2020 (UTC)[reply]

Decidability of grammar's regularity

Hi, I saw you left a note in the LL grammar page saying that whether a grammar G is regular is "and easily decidable problem". I am afraid that that is not the case. For a formal proof consult Theorem 14.6 (page 221) of Hopcroft & Ullman's Formal languages and their relation to automata, available freely through ACM on this link. The notion of regularity is precisely the one of type 3 regularity, and the terms regular set and regular partition are commonplace in literature, though they indeed seem to be missing from Wikipedia, which will need to be sorted out. They are introduced in the aforementioned book on page 15.

It is the case that the problem of whether G is regular is decidable for deterministic languages, but I would still not call the proof "easy"[1], and sadly the context of LLR languages permits nondeterminism. 192.76.8.73 (talk) 20:31, 6 October 2020 (UTC)[reply]

Thanks for your prompt reply to my {{clarify}} request, and for the references. Theorem 14.6 states that it is undecidable whether a given context-free grammar happens to generate a regular language. In contrast, the question whether a given grammar obeys the rules for a regular grammar is quite different, and easily decided by looking at the grammar's rules. I understood your phrase in LL grammar#Regular case to refer to the latter question.
I'd agree that the term "regular language" is commonly used; and I can imagine that "regular set" is a synonym, which is confirmed on p.15. However, I didn't find the string "partition" anywhere in the book. Since you are apparently familiar with this notion, could you add a definition?
Moreover, I think decidibility of regularity for deterministic language is worth mentioning - at regular language, or at deterministic context-free language, or in both places. - Jochen Burghardt (talk) 09:46, 7 October 2020 (UTC)[reply]
Good morning. I am happy to do edit the relevant wiki entries.
You are absolutely right, now reading the page again the statement "this is due to the fact that deciding whether a grammar G is regular ... is undecidable" is indeed incorrect and should be changed to "... whether the language generated by a grammar G is regular ...". Many thanks for the edit. Best, 192.76.8.73 (talk) 10:35, 7 October 2020 (UTC)[reply]
Great! You might consider registering with wikipedia (with your real name or a phantasy name).
BTW: I found a publicly available version of Ginsburg's and Greibach's paper here.[2] There is a section "Decision Problems" starting at p.645, and Theorem 5.1 says it is decidible whether a given deterministic languages equals a given regular language. However, I found no theorem saying that it is decidible whether a given deterministic languages equals any regular language; maybe I overlooked it? - Jochen Burghardt (talk) 10:43, 7 October 2020 (UTC)[reply]

References

  1. ^ Ginsburg, Seymour; Greibach, Sheila (1965). "DETERMINISTIC CONTEXT FREE LANGUAGES". 6th Annual Symposium on Switching Circuit Theory and Logical Design: 203–220.
  2. ^ Ginsburg, Seymour and Greibach, Sheila (1966). "Deterministic Context Free Languages". Information and Control. 9: 620–648. {{cite journal}}: Cite has empty unknown parameter: |month= (help)CS1 maint: multiple names: authors list (link)

Hi, and thanks for all you do for Wikipedia. I ran across the word "redices" in your edit here. I could find no definition for it. Is this a typo? Best regards -- LilHelpa (talk) 13:13, 10 October 2020 (UTC)[reply]

Oops, I believed this word to be the plural form of "redex", isn't that true? Now that you asked, I couldn't find an occurence in the WWW either. Maybe the (English) plural really is "redexes", as used in redex, while "redices" is used in German for the plural? - Jochen Burghardt (talk) 15:13, 10 October 2020 (UTC)[reply]
Ah, thanks for explanation! --LilHelpa (talk) 22:22, 10 October 2020 (UTC)[reply]

Sorry for my remark

There was a misunderstanding on my part about a "typo". I misunderstood what was posted when and why. I am deeply sorry. LMSchmitt 09:13, 8 November 2020 (UTC)[reply]

No problem. - Jochen Burghardt (talk) 14:25, 8 November 2020 (UTC)[reply]

deleted induction pic.

I greatly appreciate your observation of my deletion. I found that pic inappropriate for my article on the illogic of treating a single observation as a universal continuing factor. If, after reading my revision, you find it useful to restore that example and pic of the use rather than the logic of induction, I will be happy to discuss that and any other suggestions you have.TBR-qed (talk) 17:12, 15 November 2020 (UTC)[reply]

ArbCom 2020 Elections voter message

Hello! Voting in the 2020 Arbitration Committee elections is now open until 23:59 (UTC) on Monday, 7 December 2020. All eligible users are allowed to vote. Users with alternate accounts may only vote once.

The Arbitration Committee is the panel of editors responsible for conducting the Wikipedia arbitration process. It has the authority to impose binding solutions to disputes between editors, primarily for serious conduct disputes the community has been unable to resolve. This includes the authority to impose site bans, topic bans, editing restrictions, and other measures needed to maintain our editing environment. The arbitration policy describes the Committee's roles and responsibilities in greater detail.

If you wish to participate in the 2020 election, please review the candidates and submit your choices on the voting page. If you no longer wish to receive these messages, you may add {{NoACEMM}} to your user talk page. MediaWiki message delivery (talk) 02:32, 24 November 2020 (UTC)[reply]

Thank you

Thanks sir for considering my edit everybody was continuously deleting my edit THANK YOU SO MUCH :-) — Preceding unsigned comment added by Prakharblue123 (talkcontribs) 04:09, 28 November 2020 (UTC)[reply]

Unneeded links (at mathematical induction)?

Hello! I see your description of your edit at mathematical induction as unneeded links. Can you explain such a label? Also please see the talk page of the article re the structure of the inductive step as implication.--86.127.33.116 (talk) 12:22, 30 November 2020 (UTC)[reply]

Is the reversion mainly due to WP:EASTEREGGs and less to unneeded links?--86.127.34.116 (talk) 14:41, 30 November 2020 (UTC)[reply]

Oops, my revert was incomplete, while my edit summary referred to a complete revert; I fixed this meanwhile. Here are some more details of my reasons for the complete revert:
The link "sequence" is at best unneeded, possibly even misleading, since the target article mainly talks about properties of number sequences. Renaming "N" to "i" is pointless. WP:EASTEREGGs are strongly discouraged by Wikipedia's policy. Moreover, mathematical induction is a school-level introductory article, so details like the names of parts of implications needn't be introduced there. Moreover, the inductive step is not just an implication, but a universal quantification of an implication (but this needn't be mentioned in the article, either). The word "implication" is even used in Mathematical_induction#A_trigonometric_inequality; this should be sufficient. - Jochen Burghardt (talk) 16:07, 30 November 2020 (UTC)[reply]
I have to disagree re the mentioned details and the presumed status of school-level introductory article. Aren't logical operators acting on propositions and predicates included in this school-level? The article should also mention the interaction between implication(s) and universal quantification, even if this interaction is a bit subtle (or perhaps other attribute to be used instead of subtle?). Secondly, it doesn't seem to me that linked article sequence is mainly about number sequences. As long as the number n in P(n) is just a number of order of individual sentences (ordered by succesive implications), as I see you already said on the talk page, I don't think the link to sequence is such a bad thing, almost as if a vandalism. Also I do not quite understand why the renaming of "N" to "i" be considered pointless, N mainly being to close to the typeface/simbol of the whole set of natural numbers.
I see that talk page of the article hasn't been used in connection with the edits in the article. I'll mention there these aspects emerged from here, the school-level introductory article and the need to mention the parts of the implication and the interaction of universal quantification with the implication.--86.127.34.116 (talk) 23:02, 30 November 2020 (UTC)[reply]
(Also the need to make a total reversion is not quite OK, it gives the impression that you want to have the last word re the edits in the article.) So please propose a wording/formulation re the mentioned aspects or corrections to my proposed formulation which I'll put on the talk page of the induction article and possible talk pages of other articles like universal quantifier, material conditional, consequent, etc....--86.127.34.116 (talk) 23:02, 30 November 2020 (UTC)[reply]