Carl Mummert

Marshall University

science.marshall.edu/mummertc

Age: 35

I work in mathematical logic. My main areas of interest are arithmetic, reverse mathematics, computability, and proof theory.
19h
comment Recursively enumerable language
Could you edit the post to include some additional information: What is your question? What are your own thoughts about it? Where did you encounter it? This will help others answer. In its present form, the post is likely to be put on hold, but only because that sort of information is not included. You can edit your post freely.
1d
answered Definition and decidability of bounded quantifiers
2d
comment Uncomputability of subset relation
@David Toth: that uses the recursion theorem, one of the most powerful of the basic theorems of recursion theory. It says, essentially, that in constructing a program we may assume we already know its index. For details see en.wikipedia.org/wiki/Kleene's_recursion_theorem
Jul
25
comment Is a set $\{ e \in \mathbb{N} | \#\{x \in \mathbb{N} | \phi_e(x) \downarrow \} = \#\mathbb{N}\}$ computable?
You can use the same method as in this answer: math.stackexchange.com/questions/873063/… . Start by proving that there is no computable function $G$ that, given an oracle for an arbitrary function $f\colon \mathbb{N}\to\mathbb{N}$, determines whether the range of $f$ is infinite.
Jul
25
comment Example of first order logic without equality.
@dstathis: it depends on how the set is presented. If you present a set by a definition, it may not be decidable just using that definition, especially if the definition involves quantifiers (e.g. the set for the halting problem). But in this context sets are essentially presented as oracles for their membership relation.
Jul
25
comment Associativity of logical connectives
The most common convention I have seen is that $p \to q \to r$ means $p \to (q \to r)$ which is equivalent to $(p \land q) \to r$. This convention is very common in type theory, because it works well with the Curry-Howard isomorphism. Under this interpretation, $a \to b$ is read as "we have a function from $a$ to $b$" and $p \to q \to r$ means "we have a function that, given $p$, constructs a function from $q$ to $r$.".
Jul
24
comment Example of first order logic without equality.
Aha. Yes, that is another meaning of the word.
Jul
24
comment Example of first order logic without equality.
Indeed; this is exactly why I referred to the "traditional" language of set theory.
Jul
24
revised Example of first order logic without equality.
added 13 characters in body
Jul
24
answered Example of first order logic without equality.
Jul
24
comment How many recursively definable groups are there on $\mathbb{N}$?
The answer seems perfectly clear to me - if you're in a position to ask the question, you can certainly fill in the routine details.
Jul
23
comment People should not hurry to solve a problem when OP has not demonstrated efforts
I tend to downvote and/or vote to close "puzzles" - in my experience this site is intended for mathematical questions that users have encountered, not for mathematical questions that users have intentionally concocted to test others.
Jul
22
reviewed Close prove the countable additive of measure theorem
Jul
22
comment Uncomputability of subset relation
Those theorems sound almost right, but for the index version you need a computable $f$ and the ability to compute, given a finite initial segment of $f$, an index for an extension of that segment that is not in $D$. That extra restriction holds in all the examples I listed. In my mind, the proof of the index version is just an "effectivization" of the proof of the oracle version, vaguely analogous to another common type of "effectivization": taking a boldface result in descriptive set theory and making it into a lightface result. @Henning
Jul
22
reviewed Close complex variable integral using residue theorem
Jul
22
comment Uncomputability of subset relation
The systematic method is that there is a type of strategy to solve the oracle case: you pretend to construct an oracle for one object $\alpha$, which is computable, but as soon as the purported decision procedure says that you are constructing something with the appropriate property of $\alpha$, you switch to constructing an oracle for a different object $\beta$, also computable, whose oracle agrees with a sufficiently long initial segment of the oracle for $\alpha$. This method, which is very common, can almost always be adapted to work with indices exactly as above. @Henning
Jul
22
comment Uncomputability of subset relation
Just one more, which involves fewer prerequisites but is more trivial. (1) it is not computable, given an oracle for a subset of $\mathbb{N}$, to tell whether the set is finite (2) it is not computable, given an index for a subset of $\mathbb{N}$, to tell whether the set is finite
Jul
22
revised Uncomputability of subset relation
added 38 characters in body
Jul
22
comment Uncomputability of subset relation
Similarly: (1) it is not computable, given an oracle for a group operation on $\mathbb{N}$, to tell whether the group determined by the operation is cyclic (2) it is not computable, given an index for a group operation on $\mathbb{N}$, to tell whether the group determined by the operation is cyclic. Again (2) follows immediately from the appropriate strategy to solve (1).
Jul
22
comment Uncomputability of subset relation
I had built $i_1$ into the construction itself to avoid being too general, but now I have edited it to make $i_1$ explicit. To see that this is a general technique, consider these problems: (1) it is not computable, given an oracle for a Cauchy sequence of rationals, to tell whether the sequence converges to $0$. (2) it is not computable, given an index for a Cauchy sequence of rationals, to tell whether the sequence converges to $0$. There is a direct strategy to prove (1), and since that strategy is computable, it can be adapted in exactly the same way as my answer to solve (2). @Henning
1 2 3 4 5