boumol
Reputation
779
Top tag
Next privilege 1,000 Rep.
Create new tags
Badges
4 11
Newest
Impact
~36k people reached

• 0 posts edited
• 0 helpful flags
• 92 votes cast

# 226 Actions

 Apr 25 comment Is there a decision procedure for intuitionistic propositional logic? Let me add that "intutionistic propositional logic with one variable" is decidable in linear time, while "intutionistic propositional logic with two variables" is Pspace-complete. The first result is the classical one by Rieger-Nishimura, and the second one is a recent result by Mikhail Rybakov. Apr 14 revised Software for checking whether there is a monomial ordering satisfying some constraints added 28 characters in body Apr 14 revised Software for checking whether there is a monomial ordering satisfying some constraints added 3 characters in body Apr 14 asked Software for checking whether there is a monomial ordering satisfying some constraints Mar 23 comment Is it possible to prove that a problem $P$ is decidable in $O(\phi)$ without providing an algorithm that decides $P$ in $O(\phi)$? Nice answer, but things can be done even closer to Goldbach's conjecture; I mean that I do not see why using this sophisticated way of presenting Goldbach's conjecture. I refer to the fact that the set of natural numbers $\{ n \in \mathbb{N}: \textrm{ there is some even number which is not the addition of two prime numbers } \}$ is also trivially satisfying the requirements of the question (because this set is either $\mathbb{N}$ or $\emptyset$, and in both cases it is trivially decidable in a constant amount of time). Feb 8 comment Can we represent all algebraic structures in First-Order logic? It is not clear to me whether the question concerns what you call "fuzzy subalgebras", but I am just curious since I do not have any idea what you have in mind: all structures I am familiar related to fuzzy logic (MV-algebras, Post algebras, etc) are indeed algebraic ones. To be more precise: What do you mean by fuzzy subalgebra? Can you give an explicit example of a "fuzzy subalgebra" that is not an algebraic structure in first-order logic (using an adequate signature)? Feb 7 comment Is there anything deep about Fuzzy sets/Fuzzy logic? I would say it is quite common to understand "fuzzy logic" (in the mathematical sense I was talking in my answer) as "multi-valued logic where the values form a linear (i.e. total) order". Feb 7 revised Is there anything deep about Fuzzy sets/Fuzzy logic? deleted 3 characters in body Feb 6 answered Is there anything deep about Fuzzy sets/Fuzzy logic? Feb 2 comment What are some examples of theories stronger than Presburger Arithmetic but weaker than Peano Arithmetic? Do you know any reference to look into the bi-interpretability result? Jan 10 awarded Yearling Jan 9 comment Are ideals in rings and lattices related? My personal perspective is that, in general, what matters are congruences. There are a lot of results in universal algebra where you can get properties for a class of algebras by simply understanding the congruences of these algebras. In the particular cases where ideals correspond to congruences (e.g., rings, Boolean algebras, etc), then for sure ideals are very important (and crucial); but in the cases where ideals do not correspond to congruences (e.g., lattices, distributive ones, chains, etc) then I feel that understanding ideals is not enough (you need to understand congruences). Jan 9 comment Are ideals in rings and lattices related? Be careful. While in Boolean algebras congruences are determined by ideals (i.e., there is an isomorphism between ideals and congruences), this is not the case for arbitrary distributive lattices. In distributive lattices, congruences are much wilder than in Boolean algebras. Dec 30 comment Is there an overview of several logical systems? @snowcake: Take a look at mathoverflow.net/questions/2147/… There you can find one of "the most useful math resources from the web" Dec 20 comment On a topological proof of the infinitude of prime numbers. I am afraid to make this last remark true you have to define the characteristic function of a set as: 0 for elements in the set, and 1 for elements not in the set. In other words, this is the dual of the common way of defining characteristic function. Nov 5 awarded Enthusiast Oct 30 comment What is the probability that some number of the form $10223\cdot 2^n+1$ is prime? @David: There is a misprint in your definiton of "Sierpinski number of the second kind". It says "for all k", and it should be "for all n". Oct 30 comment What is the probability that some number of the form $10223\cdot 2^n+1$ is prime? Which chapters of "Towards a Philosophy of Real Mathematics" you mean are interesting? Oct 29 awarded Tumbleweed Oct 25 comment First-order logic: nested quantifiers for same variables @user18180: I will just give you a hint. Use that in classical logic you can prove the sequent "$\Rightarrow \exists x \neg Px, \forall y Py$".