1,153 views
8 votes
8 votes

Consider the First Order Logic (FOL) with equality and suitable function and relation symbols. Which of the following is FALSE?

  1. Partial orders cannot be axiomatized in FOL
  2. FOL has a complete proof system
  3. Natural numbers cannot be axiomatized in FOL
  4. Real numbers cannot be axiomatized in FOL
  5. Relational numbers cannot be axiomatized in FOL

1 Answer

Best answer
8 votes
8 votes

For the relation operator $\leq$,

  • Transitive: $\forall x \forall y \forall z; x \leq y\wedge y \leq z \implies x \leq z$
  • Reflexive: $\forall x; x \leq x$
  • Antisymmetric: $\forall x \forall y; x \leq y \wedge y \leq x \implies x = y$

Now, the axioms of Partial Order is just $\text{Transitive} \wedge \text{Reflexive} \wedge \text{Antisymmetric}$

So, A is FALSE.

For Option B, quoting from Wikipedia:

In general, logical consequence in first-order logic is only semidecidable: if a sentence A logically implies a sentence B then this can be discovered (for example, by searching for a proof until one is found, using some effective, sound, complete proof system). However, if A does not logically imply B, this does not mean that A logically implies the negation of B. There is no effective procedure that, given formulas A and B, always correctly decides whether A logically implies B.

So, B is TRUE.

Axioms of natural numbers are called Peano Axioms. There are $9$ of them and only one of them (axiom of induction) cannot be represented in FOL (requires second order).

So, C is TRUE.

Options D and E are more theoretical and related to fields. If interested you can read here.

Correct option: A

Reference: https://en.wikipedia.org/wiki/First-order_logic

Answer:

Related questions

19 votes
19 votes
4 answers
2
go_editor asked Dec 21, 2016
4,036 views
How many distinct ways are there to split $50$ identical coins among three people so that each person gets at least $5$ coins?$3^{35}$$3^{50}-2^{50}$$\binom{35}{2}$$\bino...
7 votes
7 votes
1 answer
3
go_editor asked Dec 21, 2016
1,597 views
A suitcase weighs one kilogram plus half of its weight. How much does the suitcase weigh?$1.3333$... kilograms$1.5$ kilograms$1.666$... kilograms$2$ kilogramscannot be de...
15 votes
15 votes
2 answers
4
go_editor asked Dec 21, 2016
2,081 views
How many distinct words can be formed by permuting the letters of the word $\text{ABRACADABRA}?$$\frac{11!}{5! \: 2! \: 2!}$$\frac{11!}{5! \: 4! }$$11! \: 5! \: 2! \: 2!\...