711 reputation
410
bio website
location
age
visits member for 3 years, 3 months
seen 1 hour ago

Jul
9
answered Is there an easy way to see associativity or non-associativity from an operation's table?
Jul
6
comment Where can I find (download) a book about basics of discrete mathematics?
Try courses.csail.mit.edu/6.042/spring12/mcs.pdf
Jun
8
awarded  Caucus
May
22
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?
May
12
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)$.
May
12
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?
May
12
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)$.
May
11
accepted Mutual Uniqueness of Operations in PA models
May
11
comment Mutual Uniqueness of Operations in PA models
Great. This paper is exactly what I was looking for.
May
11
revised Mutual Uniqueness of Operations in PA models
added 5 characters in body
May
11
asked Mutual Uniqueness of Operations in PA models
May
3
comment Is there a branch of mathematics that requires the existence of sets that contain themselves?
Since your question considers paradoxes, let me point out the book "The Liar: An Essay on Truth and Circularity" where the authors use non-well founded set theory (i.e. Aczel's one in Mark Dominus' answer) to discuss this paradox (which is obviously a non set-theoretic paradox)
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