Andreas van Cranenburgh, 0440949
	Basic Logic, predicate logic homework 3

Exercise 1

Only true in N:
∃x ~∃y: Ryx
because N has a least element, 0 (or 1, depending on definition).

Only true in Q:
~∃x ∀y: R0x ^ (Ry0 v Rxy) ^ ~∃x ~∃y: Ryx

Only true in R
∃x ∀y: R0x ^ (Ry0 v Rxy)

ie., there exists an infinitesimal? Actually I thought it was shown in the last
lecture that R is not characterizable in the language of partial orders...

Exercise 2

i)
Base case: 
- if phi is atomic then phi* = phi

Inductive step:
- if phi = ~psi, then phi* = ~(psi*)
- if phi = psi ^ chi, then phi* = psi* v chi*
- if phi = psi v chi, then phi* = psi* ^ chi*
- if phi = ∃x psi, then phi* = ∀x psi*
- if phi = ∀x psi, then phi* = ∃x psi*

ii)
Claim: M |= phi iff M* |= ~(phi*)
Base case:
 - if phi is atomic and M |= phi, then M* |= ~(phi*) because M* is specified
to contain the complement of predicates true in M.
 - likewise, if M |/= phi, then M* |/= ~(phi*)

Inductive step:
Assume property holds for psi and chi.
- M |= psi ^ phi iff M* |= ~(psi* v chi*)
  We know by de Morgan that p ^ q is equivalent to ~(~p v ~q).
  By IH, M |- psi iff M* |= ~psi* and M |- chi iff M* |= ~chi*
  Ergo taking the conjunction of psi and phi is the same as
  negating the disjunction of psi* and chi*.

- M |= psi v phi iff M* |= ~(psi* ^ chi*)
  We know by de Morgan that p v q is equivalent to ~(~p ^ ~q)
  By IH, M |- psi iff M* |= ~psi* and M |- chi iff M* |= ~chi*
  Ergo taking the disjunction of psi and phi is the same as
  negating the conjunction of psi* and chi*.
- M |= ∃x psi iff M* |= ~(∀x psi*)
  ∃x psi is equivalent with ~∀x ~psi, because if there is an x for which psi
  holds, then it is not the case that for all x psi does not hold.
  By IH, M |- psi iff M* |= ~psi*
  So if ∃x psi holds, then ~(∀x psi*) will hold and vice versa.
- M |= ∀x psi iff M* |= ~(∃x psi*)
  Similar to above.

Exercise 3

The third sentence characterizes a model with only two objects. From the first
two sentences we gather that P holds of the one and not of the other. Since
P is the only predicate we know everything there is to know about the two
objects.

Exercise 4

i)

Claim: for every formula chi in which P occurs, there is a formula chi'
such that Sigma |= chi <-> chi' and Sigma' |= chi <-> chi'
Proof:
Base case: chi is an atomic formula, so chi is P(...). Then chi' is the phi 
from the explicit definition of P, it follows from Sigma and Sigma' from
definition and inclusion, respectively.

Inductive step:
Assume property holds for theta and psi (ie., we have theta' and psi').
- Unary operators:
  by IH, Sigma |= theta <-> theta' and Sigma' |= theta <-> theta',
  so if chi = ~theta / ∃x theta / ∀x theta,
  then chi' = ~theta' / ∃x theta' / ∀x theta' and the property still holds.
- Binary operators:
  by IH, Sigma |= theta <-> theta' and Sigma |= psi <-> psi'
  and similarly for Sigma'.
  so if chi = theta ^ psi / theta v psi / theta -> psi,
  then chi' = theta' ^ psi' / theta' v psi' / theta' -> psi', 
  and the property still holds.


Now we can claim that for every formula psi, Sigma |= psi iff Sigma' |= psi:

=>
if Sigma |= psi then Sigma' |= psi.
Suppose P does not occur in psi, then Sigma' |= psi follows from the definition
of Sigma': it contains all formulas without P which are entailed by Sigma.

Suppose P does occur in psi.
By our previous proof we have shown that for every formula there is an
equivalent formula without P. We substitute psi for chi, then we have 
Sigma |= psi <-> psi' and Sigma' |= psi <-> psi' where psi' does not contain P.
Since psi' does not contain P, the claim holds for psi' by the definition of
Sigma'. And since an equivalence is expressed, the claim must also hold for
psi as well.

<=
if Sigma' |= psi then Sigma |= psi.
Suppose P does not occur in psi, then Sigma |= psi follows from the definition
of Sigma': it contains all formulas without P which are entailed by Sigma
plus epsilon, which is also entailed by Sigma.

Suppose P does occur in psi.
By our previous proof we have shown that for every formula there is an
equivalent formula without P. We substitute psi for chi, then we have 
Sigma |= psi <-> psi' and Sigma' |= psi <-> psi' where psi' does not contain P.
Since psi' does not contain P, the claim holds for psi' by the definition
Sigma'. And since an equivalence is expressed, the claim must also hold for
psi as well.


ii)
a)  The explicity definition of Exy is: ∀x∀y Exy <-> ~Rxy ^ ~Ryx
b)