# 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