HTSEFP: Model theory

1Subset defined by a formula¶

Given some structure, find the subset defined by a given formula.

1.1General solution¶

Just check all the different possible combinations and determine if the formula holds true for each one. Pretty straightforward, see examples below for more on the procedure.

1.2Examples¶

• Assignment 6, question 3, part a
• Assignment 7, question 3, part a
• Lecture notes for Monday, October 24

2Models and satisfaction¶

Given some structure, decide if a first-order formula is satisfied (as in, $\mathcal{M} \models \sigma$).

2.1General solution¶

Similar to above - if the formula holds true for each combination of things in the structure, then $\mathcal{M} \models \sigma$. Otherwise, it doesn't. See examples.

2.2Examples¶

• Assignment 6, question 3, part b
• Assignment 7, question 3, part b
• Fall 2009 final exam, question 5
• Fall 2010 final exam, question 5
• Lecture notes for Monday, October 24

3Defining formulas¶

Given a signature, find a formula that defines some set.

3.1General solution¶

This is pretty problem-specific. Some tips:

• To define "divides", just say that there exists a number that, when multiplied with the denominator, produces the numerator.
• To define a remainder, don't forget that the remainder must be less than the denominator.
• With powers, use the property that every integer has a unique prime factorisation. If only numbers that are powers of $n$ are part of this set, then do something like this: $\forall k((\Pi(k) \land (k \mid a)) \to k = n)$ (where $a$ is the number in the set and $(k \mid a)$ is the "divides" relation, which has to be defined beforehand). Similarly, if you know that a number is a power of a prime, then you also know that its prime factors must only be the prime itself.

3.2Examples¶

• Assignment 7, question 4