boumol
Reputation
749
Top tag
Next privilege 1,000 Rep.
Create tags
 Nov22 comment Who first explicitly noted that second-order logic is unaxiomatizable? Indeed, Henkin says "This follows from results of Godel concerning systems containing a theory of natural numbers, because a finite categorical set of axioms for the positive integers can be formulated within a second order calculus to which a functional constant has been added." So Henkin does does not give a reference, but he provides a proof (without the details, but it is quite clear this is a proof). Sep25 comment Difference between elementary logic and formal logic @Peter: You are absolutely right that metalogic is in general in a much wider sense. I should have said "elementary logics refers to a part of metalogic" (the easiest part). Sep25 comment Difference between elementary logic and formal logic I suspect that your answer to question 1 (that is, elementary logic refers to metalogic) is what Kelley had in mind. Concerning question 2 I suggest you look at en.wikipedia.org/wiki/Consequence_operator Aug21 comment Is the set of all definable subsets of the natural numbers recursively enumerable? @Thomas: I do not follow your last edition, it has the same troubles. I can understand what you mean by a natural number which is well formed (although I dislike your terminology and proposal), but I do not understand your definition for subsets of natural numbers. Let me do some concrete questions: how do you codify the subset of odd numbers? how do you codify the subset of even numbers? how do you codify the subset of prime numbers? etc. Aug20 comment Is the set of all definable subsets of the natural numbers recursively enumerable? As Carl Mummert says in his answer, your question is ambiguous (I disagree with his interpretation of the question, but what he says is completely fine). Problems about decidability (and recursive enumerability) must be presented in the form of a subset of natural numbers (another option is to consider a subset of the set $\{0,1\}^*$ of finite binary strings). Thus, your question must be rewritten saying which is the subset of natural numbers you are wondering whether is recursively enumerable. Notice for instance that in Carl's answer he has considered the subset $\{ n_{i,j}:i,j\in\omega\}$. Aug20 comment Is the set of all definable subsets of the natural numbers recursively enumerable? Let me remember that the "Turing machine" model is a finitistic one; it only accepts finite inputs and it only produces finite outputs. How do you want to codify in a finitistic way a subset of natural numbers? The more natural way is to use a finitistic formula to describe the set, but then it is obvious which is the answer to your question (YES). If you do not want to use the natural way then you must add to the question what is the finitistic codification (for subsets of natural numbers) you want to use. Aug16 comment Totally ordered set with greater cardinality than the continuum Although no Axiom of Choice [AC] is needed if you use the theory of transfinite ordinals, let me give a "simple" example (simple in the sense that you do not need to know ordinals) using Zorn's Lemma (which is known to be equivalent to [AC]). First consider the partial $( \mathcal{P}(\mathbb{R}), \subseteq )$, and then use Zorn's Lemma to prove that every partial order can be extended to a linear order (look at en.wikipedia.org/wiki/Linear_extension and en.wikipedia.org/wiki/Szpilrajn_extension_theorem ) Aug9 answered Introductory text for lattice theory Jul24 comment Aftermath of the incompletness theorem proof In this context (Peano arithmetic, natural numbers, ...) it is common to use the word "true" to mean "holds in the standard model of natural numbers". In other words, claiming Gödel sentence is true is just claiming that it holds in the standard model. Jul16 comment Where are good resources to study combinatorics? @ Tom Au: a finite number of sets? I suppose you mean finite sets.. Jul9 comment Is there an easy way to see associativity or non-associativity from an operation's table? Paper sent. Right now I am too busy to write down the details of this method. If you go through the paper I suggest you add the details in an answer to your own post. Jul9 answered Is there an easy way to see associativity or non-associativity from an operation's table? Jul6 comment Where can I find (download) a book about basics of discrete mathematics? Jun8 awarded Caucus May22 comment Variety generated by finite fields @Magidin: I have always believed that Birkhoff proved that a class of algebras is a variety iff it is closed under $H$, $S$ and $P$. And, Tarski proved that the variety generated by a class $K$ of algebras is $HSP(K)$. Anybody can confirm this? May12 comment Second-order logic - monadic version and Henkin semantics @Levon: It seems you didn't get my point. Even if you want to use your "parentheses convention", your formula is not well written: it should be written as $\forall x \forall y \exists X X(x,y)$. May12 comment Second-order logic - monadic version and Henkin semantics Maybe I misunderstood the question, but I thought he was asking for an explicit formula which is valid in monadic second order logic and is not valid in full Henkin semantics. Any idea how to write down one of these formulas? May12 comment Second-order logic - monadic version and Henkin semantics Be careful with your example, what you have written down is not a formula; essentially because $(x,y)$ is not an atomic formula. A formula capturing your idea is $\forall x \forall y \exists X (Xxy)$. May11 accepted Mutual Uniqueness of Operations in PA models May11 comment Mutual Uniqueness of Operations in PA models Great. This paper is exactly what I was looking for.