most recent 30 from http://mathoverflow.net 2013-05-24T05:23:50Z http://mathoverflow.net/feeds/user/8246 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/37086/models-for-the-given-fol-statement Akshar Prabhu Desai 2010-08-29T21:26:12Z 2010-08-29T22:12:42Z

<p>Consider the following FOL sentence:</p> <p>$\phi = \exists x \forall y \exists z ((x=y) \lor (P(x,y,z) \land \lnot P(y,x,z) ) $</p> <p>It can be proven that for any natural number n > 0 there exits a model of size n for the above sentence. (Please correct me here if I am wrong. This should be provable using induction.). </p> <p>Now imagine a FOL sentence that <b>does not use = (and similar) predicate</b>. And if such a sentence has a model of size n can I claim that the sentence will essentially have a model of size n+1 ? </p>

http://mathoverflow.net/questions/37084/graph-properties-and-infinite-fol-sentences Akshar Prabhu Desai 2010-08-29T20:53:37Z 2010-08-29T21:50:03Z

<p>This question is related to this <a href="http://mathoverflow.net/questions/36956/graph-properties-and-fol" rel="nofollow">Question</a>. </p> <p>Above questions revealed that even though FOL is not expressive enough to describe properties such as Connectivity, Bipartite etc. It is possible to express these properties as infinite FOL sentences.</p> <p>Now the question I got in my mind is: is it possible to express ALL properties of graph using such infinite families of FOL sentences? </p> <p>An example showing that it is not is what I want. </p>

http://mathoverflow.net/questions/36956/graph-properties-and-fol Akshar Prabhu Desai 2010-08-28T07:30:18Z 2010-08-29T09:22:13Z

<p>If a certain property of graphs cant not be expressed by a first order logic sentence $\phi$ over $\Sigma$ then can we say with confidence that such as property can not be expressed even by a an infinite family of FOL sentences $\eta$ over $\Sigma$ ?</p> <p>$\Sigma$ is the vocabulary {E,=} used to represent graph where E is a binary predicate and = has the usual meaning. </p> <p>EDIT: What if the graph is directed? </p>

http://mathoverflow.net/questions/36552/how-to-tackle-this-puzzle Akshar Prabhu Desai 2010-08-24T13:50:34Z 2010-08-24T14:44:10Z

<p>Disclaimer: This is not a homework problem. I stumbled on this puzzle on internet and I also have the answer. However I am not able to figure out whats the method to be used to arrive at the answer.</p> <p>The puzzle is as below:</p> <p>The product of the ages of David's children is the square of the sum of their ages. David has less than eight children. None of his children have the same age. None of his children is more than 14 years old. All of his children is at least two years old. How many children does David have, and what are their ages?</p> <p>The answer happens to be 2,4,6,12. </p> <p>Please suggest ways to solve this problem systematically. </p>

http://mathoverflow.net/questions/36263/porbability-of-selecting-balls-from-boxes Akshar Prabhu Desai 2010-08-21T06:28:31Z 2010-08-21T06:46:10Z

<p>There are three boxes. B1, B2, B3 The probability of selecting them is 0.2, 0.2 , 0.6 respectively. </p> <p>B1 contains 3 red balls and 7 green balls. B2 contains 5 red balls and 5 green balls. B3 contains 2 red balls and 8 green balls.</p> <p>If we select a box and then a ball from the box what is the probability that the ball is of red color. </p> <p>If we select the a ball and it turns out to be of green color what is the probability that it comes from B3 ?</p>

http://mathoverflow.net/questions/35393/natural-number-properties-as-uniterpreted-functions-in-first-order-logic Akshar Prabhu Desai 2010-08-12T20:36:04Z 2010-08-12T20:48:28Z

<p>Can we express the following property of natural numbers as FOL. The property given below is only indicative, I am more interested in know how the concepts such as "infinitly many X exists for so and so" be expressed in FOL. Also these need to be expressed as uninterpreted functions.</p> <p>"For Every natural number n, there are infinitly many other natural numbers such that the greatest common divisor of n and each of these other numbers is 1" </p> <p>As I said if you cant express this sentence in FOL at least suggest links/material where I can get leads.</p>

http://mathoverflow.net/questions/35203/exponent-function-as-uninterpreted-function-in-first-order-logic Akshar Prabhu Desai 2010-08-11T09:16:09Z 2010-08-11T09:22:35Z

<p>I want to express the following sentence in first order logic. </p> <p>There are naturals numbers that can not be expressed as one natural number raised to the power of another natural number other than one. </p> <p>Under normal circumstances this is very simple. I am wondering if the the exponent function involved here can be expressed as uninterpreted function. Can we use some combination of *,+ as interpreted functions to express exponent function as uninterpreted one ? </p>

http://mathoverflow.net/questions/34989/horn-clauses-and-satisfiability Akshar Prabhu Desai 2010-08-09T10:52:53Z 2010-08-09T15:29:49Z

<p>It is well known that satisfiability of Horn formulae can be checked in polynomial time using unit propagation.</p> <p>But suppose we relax the condition for horn clauses from at most one un-negated literals to two un-negated literals. Then is it possible to prove that satisfiability of such a formula can be checked in time polynomial in the size of the formula? </p>

http://mathoverflow.net/questions/37086/models-for-the-given-fol-statement/37090#37090 Akshar Prabhu Desai 2010-08-29T22:11:56Z 2010-08-29T22:11:56Z

By syaing b has all properties of a you are trying to say add &quot;another a&quot; and since our FOL cant use &quot;=&quot; we will get away with it. But I feel you have ignored the fact that : size of a model means the cardinality of it's universe. Universe is a set and hence each member of universe has to be distinct isnt it ?

http://mathoverflow.net/questions/36956/graph-properties-and-fol Akshar Prabhu Desai 2010-08-29T20:30:03Z 2010-08-29T20:30:03Z

@Asaf Karagila And more precisely: &quot;Are there SOL (or higher) theories about graphs that cannot be expressed in FOL but can be expressed as infinite families of FOL sentences?&quot;

http://mathoverflow.net/questions/36956/graph-properties-and-fol Akshar Prabhu Desai 2010-08-28T22:34:57Z 2010-08-28T22:34:57Z

What if the Graph is directed ?

http://mathoverflow.net/questions/36552/how-to-tackle-this-puzzle/36558#36558 Akshar Prabhu Desai 2010-08-24T15:24:20Z 2010-08-24T15:24:20Z

Thanks. I wanted to know if there is any way other than casework.

http://mathoverflow.net/questions/36552/how-to-tackle-this-puzzle Akshar Prabhu Desai 2010-08-24T15:22:21Z 2010-08-24T15:22:21Z

@Jose Why shouldn't it be of interest for Researchers? Just because I have used the word puzzle it need not mean it's an casual problem. For example above problem can possibly have a geometric interpretation that might yield the answer very easily Or can be framed as an optimization problem based on constraint?

http://mathoverflow.net/questions/36263/porbability-of-selecting-balls-from-boxes/36265#36265 Akshar Prabhu Desai 2010-08-21T06:50:09Z 2010-08-21T06:50:09Z

Oh no the problem I am solving is entirely different. Just wanted to check that my line of thinking is correct.

http://mathoverflow.net/questions/35393/natural-number-properties-as-uniterpreted-functions-in-first-order-logic/35394#35394 Akshar Prabhu Desai 2010-08-13T05:58:08Z 2010-08-13T05:58:08Z

Okay. I was a bit confused as per who the &quot;infinitely many..&quot; is represented.

http://mathoverflow.net/questions/35203/exponent-function-as-uninterpreted-function-in-first-order-logic Akshar Prabhu Desai 2010-08-11T11:29:34Z 2010-08-11T11:29:34Z

What I mean here is that we are allowed to use + with it's usual interpretation but not allowed to use ^ with it's normal interpretation. The question here is &quot;how to express ^ as uninterpreted function?&quot;