1. If a relation is transitive and reflexive, must it be symmetric?
2. If a relation is transitive and irreflexive, must it be asymmetric?
3. If a relation is transitive and symmetric, must it be reflexive?
4. If a relation is asymmetric, must it be irreflexive?
5. What's a more familiar name for a symmetric pre-order?
6. What is the difference between a weak and a strict partial order?
7. What is the difference between a pre-order and a partial order?
8. What is the difference between a partial order and a total order?
9. What does it mean for a relation to be trichotomous?
10. What does it mean for a relation to be Euclidean?
11. What does it mean for a relation to be serial?
12. What does it mean for a relation to be dense?
13. What does it mean for $$a$$ and $$b$$ to be comparable wrt some relation?
14. What is the "ancestral" or transitive closure of the relation "is a parent of"?
15. What is the equivalence class of Ben under the relation "has the same height as"?
16. Is the relation "is at least as old as" symmetric, anti-symmetric, or asymmetric?
17. Is the relation "is a brother of" symmetric?
18. What is the difference between a maximal element, a greatest element, and a least upper bound (also called a "supremum") wrt some ordering relation?
19. If an ordered set has any upper bounds, must it have a least upper bound?
2. What does it mean for an ordering relation on some set to be well-founded? Is the relation "is an initial substring of" on the set of strings over some alphabet well-founded? Is the set well-ordered by that relation?

3. Try to explain each of the following in language that's less technical and which you're sure you understand, but is as rigorous as is compatible with the first requirements.

1. some theory is deductively consistent
2. some theory is deductively closed
3. some theory is deductively complete
4. some theory is effectively decidable
5. some theory is effectively enumerable
4. In Sider's proof of completeness (section 2.9, starting p. 62), he uses the notion of a "maximally consistent" set of sentences. Although he defines "maximal" and "consistent" separately, his definitions entail that a set is maximally consistent iff it's deductively consistent, and no further sentences can be consistently added (that is, for any $$\phi\notin \Gamma$$, $$\Gamma\cup \{\, \phi \,\}$$ is deductively inconsistent).

1. Prove that a set is maximally consistent iff it's deductively consistent, deductively closed, and deductively complete.
2. Prove that if a maximally consistent set contains a formula $$\phi\wedge\psi$$, then it also contains $$\phi$$ and contains $$\psi$$.
3. Prove that if a maximally consistent set contains a formula $$\neg(\phi\wedge\psi)$$, then it either contains $$\neg\phi$$ or it contains $$\neg\psi$$.
5. The following is an alternative formulation of one of the important logical facts we've discussed in the past several weeks. What is the short name of that fact?

If $$\Gamma\cup \{\, \neg\phi \,\}$$ is satisfiable, then every finite subset of $$\Gamma\cup \{\, \neg\phi \,\}$$ is deductively consistent.

6. On the webnotes page on Peano arithmetic and non-standard models, I discuss a proof from Compactness for the result that there must be models of true arithmetic that have an additional element in the domain, coming "after" (in the $$<$$-ordering) all the numbers designated by $$0, S0, SS0, \dots$$ The proof begins "Here's how we can persuade ourselves that there are such models." Make sure you understand this proof. (a) In order to understand the proof, did you have to work out or spell out some of the details more explicitly? if so, please tell me what they were, preferably by presenting a fuller version of the proof. (b) Without any further details about such models, we already now know enough about them to prove they are not isomorphic to the intended model of arithmetic. How can we prove this? For all we've said so far, the model with the extra element may have a countable domain, just like the intended model. So why are the models not isomorphic?

Suggestion: begin by spelling out for yourself what it takes for two models to be isomorphic. You should already be able to do this, on the basis of your understanding of what a model for the language of arithmetic will look like, and your understanding from earlier in the term of what it is for two algebraic structures to be isomorphic. Explicit definitions for what it takes for models to be isomorphic are also present in some of the big list of readings for 5 Nov. You can look at those to see if you got it right, or got stuck.

Once you know what it is for two models to be isomorphic, prove that any model with that extra element isn't isomorphic to the intended model of arithmetic.

7. At the end of class on 5 Nov, we discussed an argument from Sider's section 4.5 (p. 105) to the effect that there can't be any sentence in first-order logic which says exactly that there are finitely many objects; so neither can there be its negation, which says exactly that there are infinitely many objects. At the same time, we also discussed a sentence that entails that there are infinitely many objects. Why doesn't an analogue of Sider's argument show that latter sentence to be impossible? We also discussed some sentences that entail that there are finitely many objects: give an example, and explain why an analogue of Sider's argument doesn't show these sentences to be impossible.

8. Fill in the gaps in this proof that the power set of a set $$S$$ always has a higher cardinality than S does.

Assume for reductio that the power set of $$S$$ is no larger than $$S$$ is. By definition of what it is for one set to be no larger than another, there must then be an injection $$f$$ from the power set of $$S$$ to $$S$$. (Spell out what this consequence amounts to.) For each $$X$$ in the power set of $$S$$, $$f(X)$$ is some member of $$S$$, and this will either be a member of $$X$$ or it won't. If $$f(X)\in X$$, call $$X$$ "happy"; else call $$X$$ "unhappy". No member of the power set of $$S$$ will be both happy and unhappy (why?).

Let $$U$$ be the image under $$f$$ of all the unhappy members of the power set of $$S$$; that is, the set $$\{\, u\in S \mid \exists X\in 2^{S}. f(X)=u \wedge f(X) \notin X \,\}$$. $$U$$ is a member of the power set of $$S$$ (why?); so $$U$$ must be happy or unhappy.

Suppose $$U$$ is happy; then $$f(U)\in U$$ (why?). But by definition of $$U$$, it includes only those $$f(X)$$ where $$X$$ is unhappy. So then $$U$$ is unhappy.

Suppose $$U$$ is unhappy; then $$f(U)$$ must be in $$U$$ (why?). But if $$f(U)\in U$$, then by definition of "happy", $$U$$ is happy.

So $$U$$ is happy iff $$U$$ is unhappy; but as we said, no member of the power set of $$S$$ can be both happy and unhappy.

So our assumption that there is an injection $$f\colon 2^{S} \to S$$ fails. So the power set of $$S$$ must be larger than $$S$$ after all.

What step(s) in this argument relied on $$f$$'s being an injection, and would fail if we weren't allowed to assume that? Spell that step in the proof out more explicitly.

9. Fill in the gaps in this proof that if a proof system is semantically sound and (strongly) complete, then Compactness holds.

Soundness for a proof system entails that if some finite subset of a set of sentences $$\Gamma$$ can prove a contradiction, then $$\Gamma$$ has no model (why were we entitled to say "finite" here?). (Strong) completeness entails the converse: that if $$\Gamma$$ has no model, then from some finite subset one can prove a contradiction (why were we entitled to say "finite" here?). Taken together, this gives us that $$\Gamma$$ has no model iff from some finite subset one can prove a contradiction. Equivalently, $$\Gamma$$ has a model iff from every finite subset one cannot prove a contradiction. Any finite subset that has a model will be one that cannot prove a contradiction (why?). So if every finite subset of $$\Gamma$$ has a model, then $$\Gamma$$ has a model (why does this follow from what we've said?) That is Compactness.

1. Fill in the gaps in this proof that if any two at-most-countable models of a deductively closed theory $$T$$ are isomorphic, then $$T$$ is deductively complete.

Assume for reductio that $$T$$ is not deductively complete. Then for some sentence $$\psi$$, both $$T\cup \{\, \psi \,\}$$ and $$T\cup \{\, \neg\psi \,\}$$ are deductively consistent. So these sets are satisfiable (why?). By Loewenheim-Skolem, these sets must have at-most-countable models $$\mathscr{M}_1$$ and $$\mathscr{M}_2$$. These models must be isomorphic (why?). So they must make true all the same sentences (why?). So $$T$$ must be deductively complete after all (why?).