Preparing for Logic Final: Union of T_n Satisfiable & Not Finitely Axiomatizable

[moo5003]

I'm studying for my logic final and I can't seem to find an answer for this practice problem:

(Using < as proper subset since I don't have the right type)

T_1 < T_2 < T_3... be a strictly increasing sequence of satisfiable L-Theories.

a) Show that the union of T_n is satisfiable (over all n in the natural numbers).

b) Show that the union of T_n is not finitely axiomatizable.



A) Pretty simple, every finite subset is satisfiable since the largets T_n is satisfiable thus by compactness their entire union is satisfiable.

B) This is were I have some problems. I'm not sure how to go about showing this. I want to show that any finite amount of sentances can only axiomatize up to T_n and then we can simply show that T_n+1 is not axiomatized. Any ideas on this?

EDIT: I posted this in the wrong forum apparently, if anyone could move it to the logic section I would appreciate it.

 

[moo5003]

The midterm is over though I would still like to know how to solve this problem.

 

[tacman]

Hi there,

Preparing for a logic final can be challenging, but let's break down the practice problem to help you find an answer.

First, let's define some terms. A theory is a set of sentences in a formal language that are true under a certain interpretation. A theory is satisfiable if there exists a model that satisfies all the sentences in the theory. A theory is finitely axiomatizable if there exists a finite set of axioms that can generate all the sentences in the theory.

Now, let's look at the problem. We have a sequence of theories, T_1 < T_2 < T_3..., where each theory is a proper subset of the next. This means that T_1 is a proper subset of T_2, T_2 is a proper subset of T_3, and so on. We also know that each theory in this sequence is satisfiable.

a) To show that the union of T_n is satisfiable, we need to show that there exists a model that satisfies all the sentences in the union. Since each theory in the sequence is satisfiable, we know that there exists a model for each theory. By the compactness theorem, we know that if every finite subset of a theory is satisfiable, then the entire theory is satisfiable. In this case, every finite subset of the union of T_n is satisfiable since it is a proper subset of one of the theories in the sequence. Therefore, the entire union of T_n is satisfiable.

b) To show that the union of T_n is not finitely axiomatizable, we need to show that there does not exist a finite set of axioms that can generate all the sentences in the union. One way to do this is through a proof by contradiction. Assume that the union of T_n is finitely axiomatizable. This means that there exists a finite set of axioms that can generate all the sentences in the union. However, since each theory in the sequence is a proper subset of the next, this finite set of axioms can only generate sentences up to T_n. This means that T_n+1 cannot be generated by this finite set of axioms, which contradicts our assumption. Therefore, the union of T_n is not finitely axiomatizable.

I hope this helps with your preparation for the logic final. Good luck!