0

I'm not really sure how to think about the following problems, especially (iii):

(i) Provide a sentence that contains no other than unary predicate letters and that is true in some structure with a domain containing at least three elements, but that is not true in any structure with a domain containing less than three elements.

(ii) Provide a sentence containing no constants and predicate letters other than R^2 that is true in some structure with a domain containing at least three objects but that is not true in any structure with a domain containing less than three objects.

(iii) Provide a sentence that is true in some structure with an infinite domain but not in any structure with a finite domain.

I must do this without using =. I realize one strategy would be to use a contradiction to force two elements in the domain, but I can't see how adding another unary predicate letter will force a third element. For example:

∃x∃y(Px ∧ ¬Py)

In this case, I must have two elements for this sentence to be true. However, adding another unary predicate letter doesn't necessarily require three elements.

∃x∃y∃z((Px ∧ ¬Py) → (Ry ∧ ¬Rz))

This formula could be satisfied by the following structure (with only two elements):

D = { 0 , 1 }

P = {1}

R = {0}

I'm just not sure how a sentence could 'require' three elements. Any advice? Thanks in advance!

  • I think this is only part of a solution but, "There does not exist a maximum element" would be an English phrase that can be true for infinite domains but must be false for all finite domains with ordering. – Cort Ammon May 21 '18 at 23:00
1

For :

(i) Provide a sentence that contains no other than unary predicate letters and that is true in some structure with a domain containing at least three elements, but that is not true in any structure with a domain containing less than three elements.

without using identity we must have :

∃x,y,z (Ex ∧ ¬Fx ∧ ¬Gx ∧ ¬Ey ∧ Fy ∧ ¬Gy ∧ ¬Ez ∧ ¬Fz ∧ Gy ).

For :

(ii) Provide a sentence containing no constants and predicate letters other than R^2 that is true in some structure with a domain containing at least three objects but that is not true in any structure with a domain containing less than three objects.

the solution is similar; we must have :

∀x [Rxx ∧ ∃x,y,z (¬Rxy ∧ ¬Rxz ∧ ¬Ryz)].

  • This makes sense, thank you. For (ii), I see how I could provide a sentence containing no predicate letter other than R^2 that is true in some structure with a domain containing at least two objects but that is not true in a structure with one: ∃x∃y(Rxy ∧ ¬Ryx) So I realize the same principle must be used to find a sentence that works only when at least three elements are in the domain. I'm thinking something like: ∃x∃y∃z(Rxy ∧ ¬Rxz ∧ ¬Ryx ∧ Ryz ∧ ¬Rzx ∧ ¬Rzy) This seems wrong, though. – vundabar May 21 '18 at 12:38
  • Oh, wonderful. Yes I see. How did you think this one through? Did you first say you were going to create three reflexive ordered pairs (ie, R = {<x, x>,<y, y>,<z, z>}) and then build the sentence around that? Now that I'm trying to reason through (iii), I don't know if I should start with a conception of the elements within the predicate letters or what.. – vundabar May 21 '18 at 13:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.