Skip to content

Hints Homework 10

November 9, 2011

Problem 2

As we saw in class, you can define the {\leq} relation using the formula {\varphi(x,y) \equiv \exists z ( x+z =y)}. Furthermore, given any number {n \in {\mathbb N}}, we can represent it as {\underline{n} = S(S \dots S(\underline{0}))}, where we apply {S} {n}-times.

Now show that {\mathsf{PA} \models \forall x ( \underline{0} < x \; \Rightarrow \underline{1} \leq x)}.

Problem 3

For any specific finite number {n}, you can find a formula that says: “There exist exactly {n} distinct elements”.

Problem 4

One direction is trivial. For the other direction, use the completeness theorem. Argue that a theory {T} is consistent if and only if it has a model. Then use the fact that proofs are finite, in particular can use at most finitely many formulas.

Problem 5

Extend the language of arithmetic by a new constant symbol {\underline{c}}. Add sentences of the form {\underline{0} < \underline{c}}, {\underline{1} < \underline{c}}, {\underline{2} < \underline{c}}, … to {T_{\mathbb N}}. Apply the compactness theorem.

Advertisements

From → Homework

Leave a Comment

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: