Write a formula that defines the set of all interpretations

Assignment Help Mathematics

Reference no: EM132409827

Questions -

1. First Order Formulas and Interpretations

We fix a signature

S = (f₁(·), f₂(· , ·), f₃(· , ·), R₁(· , ·), R₂(· , ·))

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:

φ₁ = (∀y(∀x(∃z(R₂(x, f₃(y, z))))))

φ₂ = (∃y(∀x(∀z(R₂(x, f₃(y, z))))))

φ₃ = (∃y(∀x(∃z(R₂(x, f₂(y, z))))))

φ₄ = (∀x(R₁(f₁(x), f₂(x, y))))

φ₅ = ((R₁(f₁(y), x)) → (R₁(f₂(y, y), f₂(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.

- 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 = 3² + 4²).

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: EM132409827

Questions Cloud

Identifying the purpose of the study : Writing Research Reports: Each report (worth 1 unit of research credit) will be based on a scientific article in a psychology journal that is pre-approved.

Calculate the purity of the sample expressed as percent : Calculate the purity of the sample expressed as percent K2O.

Calculating the chemical formula : Analysis shows that it contains 1.4462 g of sulfur and1.4435 g of oxygen. Find its chemical formula.

Common glassware and laboratory equipment : Concisely explain how you should prepare 250. mL of a 10 mF pH 4.5 acetate buffer. Available reagents: sodium acetate (NaOAc, 82.03 g/mol

Write a formula that defines the set of all interpretations : 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

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.

User Account

All Pages