**Maintainer:**admin

*1*Subset defined by a formula¶

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

*1.1*General 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.2*Examples¶

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

*2*Models and satisfaction¶

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

*2.1*General 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.2*Examples¶

- 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

*3*Defining formulas¶

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

*3.1*General 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.2*Examples¶

- Assignment 7, question 4