# Minimum number of elements in the domain? (predicate logic)

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. Commented May 21, 2018 at 23:00

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. Commented May 21, 2018 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.. Commented May 21, 2018 at 13:08