Mathematical Logic Questions

Assignment Help Mathematics
Reference no: EM132409822

Mathematical Logic Questions -

1. First Order Formulas and Interpretations

We fix a signature

S = (f1(·), f2(· , ·), f3(· , ·), R1(· , ·), R2(· , ·))

and consider the interpretation

I = (Z, x |→ x + 1, (x, y) |→ x · y, (x, y) |→ x + y, ≤, =).

(a) Translate the following formulas to English/Math:

φ1 = (∀y(∀x(∃z(R2(x, f3(y, z))))))

φ2 = (∃y(∀x(∀z(R2(x, f3(y, z))))))

φ3 = (∃y(∀x(∃z(R2(x, f2(y, z))))))

φ4 = (∀x(R1(f1(x), f2(x, y))))

φ5 = ((R1(f1(y), x)) → (R1(f2(y, y), f2(x, x))))

(b) For each of the above formulas, state whether or not they are satisfied in interpretation I. For formulas that are not sentences (that is, have free variables) provide a valuation v such that I, v together satisfy the formula or argue that no such valuation exists.

(c) For each of the following sets of numbers, provide a formula that defines this set in interpretation I:

- The set that contains only the number 0.

- The set of integers that are the sum of two squares (an example is 25, since 25 = 32 + 42).

2. Definability (and the Compactness Theorem)

We consider the signature

S = (f(·), P(·), EQ(· , ·))

where f is a function symbol, P is a one-place predicate and EQ a two place predicate. We will consider only interpretations where the predicate EQ is interpreted as equality.

Write a formula that defines the set of all interpretations of this signature, where the property P holds for all elements in the range of f. Give an example of such an interpretation.

Describe a set of formulas that defines the set of all interpretations of this signature where infinitely many elements have the property P. Give an example of such an interpretation.

Show that the set of all interpretations, where the property P holds only for finitely many elements of universe is not definable. Give an example of such an interpretation.

3. Halting Problem

Show that there is no algorithm H that takes the code of some program P and determines whether P halts and outputs "I will pass MATH1090!". That is, H should say

- loop, if P loops forever or doesn't output "I will pass MATH1090!"

- halt, if P halts and outputs "I will pass MATH1090!"

Reduce the original halting problem to this and explain your reduction!

Reference no: EM132409822

Questions Cloud

What is the degree of dissociation : At 25°C, ?G for the reaction : is 1380 cal. What is the degree of dissociation at 25°C when the total pressure is 10 atm?
How simplicity can benefit problem solving : Watch the video, Rory Sutherland: Sweat the Small Stuff, on how simplicity can benefit problem solving. Select one of the following topics: Laypersons.
Unit 3 Science and Materials Assignment Problem : Unit 3 Science and Materials Assignment Help and Solution - Higher National Diploma in Construction and the Built Environment Assessment Writing Service
Compute cl in the sample : The new weight of the dried crucible is 23.9622 g. Compute % Cl in the sample.
Mathematical Logic Questions : Mathematical Logic Questions - First Order Formulas and Interpretations: provide a formula that defines this set in interpretation I
Describe the critical characteristics of both participants : Describe the critical characteristics of both the participants and the procedures used. Summarize the main findings. How do these findings answer the question.
Describe the importance of critical thinking : Provide an explanation of the importance of critical thinking and the implications of not questioning information, both in general and as they relate.
Calculate the molar concentration of the naoh solution : A 0.429 g sample of KHC 8H 4O 4 (molar mass =204.44g/mol) requires 23 ml of a NaOH solution to reach the phenolphthalein endpoint.
Calculate the ph of the resulting solution : Calculate the pH of the resulting solution given that the pKa of benzoic acid is 4.19.

Reviews

Write a Review

Mathematics Questions & Answers

  Questions on ferris wheel

Prepare a Flexible Budget Gator Divers is a company that provides diving services such as underwater ship repairs to clients in the Tampa Bay area.

  Logistic map

This assignment has two question related to maths. Questions are related to bifurcation cascade and logistic map.

  Finding the probability of cards

This assignment has questions related to probabiltiy.

  Systems of ode

Find all the xed points, and study their stability and Draw the phase portrait of the system, as well as the graphs of the solutions in all relevant cases.

  Derive the boolean expression

Derive the Boolean Expression and construct the switching circuit for the truth table stated

  System of equations

Evaluate which equations are under-identified, just-identified, and over-identified.

  Linear programming problem

Linear programming problem consisting of only two constraints with one objective function.

  Find the natural domain

Find the natural domain of the given functions.

  Introduction to numerical methods

Compute the coecients of the polynomials using the term recurrence relation.

  Chart of the topological manifold

De?nition of smoothness of functions on a smooth manifold is chart independent and hence geometric.

  Mathematics in computing

Questions related on mathematics in computing.

  Complex problems

Complex problems

Free Assignment Quote

Assured A++ Grade

Get guaranteed satisfaction & time on delivery in every assignment order you paid with us! We ensure premium quality solution document along with free turntin report!

All rights reserved! Copyrights ©2019-2020 ExpertsMind IT Educational Pvt Ltd