Timeline for Can finite sets be non-c.e. depending on how they are presented?
Current License: CC BY-SA 4.0
26 events
when toggle format | what | by | license | comment | |
---|---|---|---|---|---|
Dec 4, 2021 at 21:25 | comment | added | Thomas Benjamin | Given what you wrote in your last comment, would you say that the Diaconescu set {$a$, $b$} is recursively enumerable? | |
Dec 3, 2021 at 0:14 | comment | added | Andreas Blass | Burgin's example $X$ shares with Diaconescu's $D=\{a,b\}$ the property that I can't say what its cardinality is. But the reasons are quite different. We don't know what the members of $X$ are, but we can tell whether two given members are equal (because they're natural numbers). We know what the members of $D$ are ($a$ and $b$) but we can't tell whether they're equal. | |
Dec 2, 2021 at 21:35 | comment | added | Thomas Benjamin | Why would that not be the the case with Burgin's example? | |
Dec 1, 2021 at 22:24 | comment | added | Andreas Blass | @ThomasBenjamin I thought I did answer your question, but, more explicitly, to say that "we cannot say (constructively) that Diaconescu's set is a 1-element set or a 2-element set" means that we cannot say (constructively) that Diaconescu's set is a 1-element set and also we cannot say (constructively) that Diaconescu's set is a 2-element set. This situation occurs because we cannot say that the truth-value (or proposition) used in defining that set is true or false. | |
Dec 1, 2021 at 22:14 | comment | added | Thomas Benjamin | True enough, but that doesn't answer my question. Without LEM, is it possible that neither of the disjuncts can be asserted (I seem to recall that Brouwer asserted that very thing, i.e. that given either $a$ $\lor$ $\neg$$a$, there are circumstances in which neither $a$ nor $\neg$$a$ can be asserted. Is that also the case with Burgin's example?)? | |
Dec 1, 2021 at 0:32 | comment | added | Andreas Blass | @ThomasBenjamin Constructively, to assert a disjunction, one must be able to assert one of the disjuncts. | |
Nov 30, 2021 at 22:25 | comment | added | Thomas Benjamin | What does it mean to say that "we cannot say ( constructively) that Diaconescu's set is a 1-element set or a 2-element set, because we don't know which alternative holds"? | |
Nov 30, 2021 at 22:17 | comment | added | Andreas Blass | @ThomasBenjamin What does "we can recognize finite sets" mean? | |
Nov 30, 2021 at 22:15 | comment | added | Thomas Benjamin | So that means that if one assumes LEM that (by the Diaconescu-Goodman-Myhill Theorem) that every n-element Diaconescu set has decidable equality and that is the reason we can recognize finite sets? | |
Nov 22, 2021 at 22:31 | comment | added | Andreas Blass | @ThomasBenjamin Well if AC holds, then we have the law of the excluded middle, so we do know whether Diaconescu's $\{a,b\}$ has one element or two (and subobjects have honest complements). | |
Nov 22, 2021 at 21:31 | comment | added | Thomas Benjamin | True enough. If the Axiom of Choice holds, under what conditions does Diaconescu's {$a,$ $b$} become a 1-element or 2-element set (according to Diaconescu, in topoi/toposes, "subobjects do not have honest complements-[they have pseudocomplements--my comment taken from his paper, pg.176. How does that relate to not knowing which alternative holds, if at all?])? | |
Nov 19, 2021 at 23:48 | comment | added | Andreas Blass | Once a set lacks decidable equality, so does every superset. But I don't think it makes sense to talk about n-element sets that lack decidable equality, at least if n is supposed to be a natural number. For example, we cannot say (constructively) that Diaconescu's {a,b} is a 1-element set or a 2-element set, because we don't know which alternative holds. | |
Nov 19, 2021 at 21:24 | comment | added | Thomas Benjamin | Interesting, thanks. As regards the crucial set in Diaconescu's proof, {$a$, $b$} "where we're unsure whether $a$ = $b$" (being $K$-finite but not having decidable equality), is that the unique set not having decidable equality, or are there arbitrary n-element sets not having decidable equality as well (and how does one determine that they don't have decidable equality)? | |
Nov 17, 2021 at 0:47 | comment | added | Andreas Blass | In a topos with a natural number object $N$, "K-finite" is equivalent to "surjective image of $\{x\in N:x<k\}$ for some $k\in N$" while "K-finite with decidable equality" is equivalent to "bijective image of $\{x\in N:x<k\}$ for some $k\in N$." The crucial set in Diaconescu's proof, $\{a,b\}$ where we're unsure whether $a=b$, is K-finite but doesn't have decidable equality. Hence the distinction at the end of my previous comment. | |
Nov 16, 2021 at 22:56 | comment | added | Thomas Benjamin | Would the fact that it is provable in $ZF$ that all finite sets are projective be because for $ZF$, the law of excluded middle holds (via the Diaconescu-Goodman-Myhill theorem)? Also, what is the structural distinction between "$K$-finite sets $F$ in which the equality relation holds is decidable" and $K$-finite sets in general (other than for the $K$-finite sets $F$ in which the equality relation is decidable, the diagonal is complemented in $F$ $\times$ $F$ in the internal logic of topoi)? | |
Nov 15, 2021 at 15:07 | comment | added | Andreas Blass | Projectivity is a property of a set, not of how it's given. In ZF, it's provable that all finite sets are projective. In intuitionistic higher order logic (the internal logic of topoi), th same is true for K-finite sets $F$ in which the equality relation is decidable (i.e., the diagonal is complemented in $F\times F$) but not for general K-finite sets. | |
Nov 8, 2021 at 21:57 | comment | added | Thomas Benjamin | Well, Burgin states this as follows: "It is usually assumed that any finite set is recursively computable and even decidable. When a finite set is given by a list [my emphasis], then this is true." Is a finite set given as a list not projective (if not, why not)? | |
Nov 8, 2021 at 17:42 | comment | added | Andreas Blass | in another direction: It may be reasonable to try to define computability of presentations of sets (as opposed to computability of sets), but I don't yet see any natural way to do so. It seems to require an arbitrary decision about how much "work" is allowed on the way from the presentation to the algorithm. (Consider, for example, the set of orders of sporadic simple groups, presented as I've just said.) | |
Nov 8, 2021 at 17:39 | comment | added | Andreas Blass | @ThomasBenjamin Since Burgin's $X$ is a set of natural numbers, it has a standard well-ordering, the usual $<$ relation on natural numbers. This is quite different from being given as a list. So I don't see much connection between this issue and choice sets or projective sets. | |
Nov 8, 2021 at 4:01 | comment | added | Thomas Benjamin | (cont.) of what it means to 'have an algorithm' for generating a given finite set (Burgin grants that for lists, i.e., well-ordered finite sets, what you say is true --see my quote of his in my question). | |
Nov 8, 2021 at 3:47 | comment | added | Thomas Benjamin | I am wondering, though, if having an effective way to produce the table from the given description of $X$ (in Burgin's example or in any other example, for that matter) is implicit in our understanding | |
Nov 7, 2021 at 13:30 | comment | added | Andreas Blass | @ThomasBenjamin Our means of expressing a table (or any other algorithm for that matter) involve writing the steps in some linear order, so they would implicitly involve a linear ordering of the set. Note, though, that the usual notion of a finite set --- existence of a bijection with a proper initial segment of the natural numbers --- also implicitly involves a well-ordering. | |
Nov 7, 2021 at 3:33 | comment | added | Thomas Benjamin | Rather, would the table (if one had it) well-order $A$ making it a list? | |
Nov 7, 2021 at 3:21 | comment | added | Thomas Benjamin | Thank you for the very nice answer--it is very helpful. As regards the table look-up algorithm--would it well-order $A$ making it a list? | |
Nov 7, 2021 at 3:13 | vote | accept | Thomas Benjamin | ||
Nov 6, 2021 at 20:45 | history | answered | Andreas Blass | CC BY-SA 4.0 |