# Tagged Questions

34 views

### Proof of Propositional Compactness Theorem

I am going through the proof for the following form of compactness theorem. Statement: If Φ is an unsatisfiable set of propositional formulas, then some finite subset of Φ is unsatisfiable -- ...
36 views

### Compactness and Arithmetic Confusion

Let $T$ be some theory capable of arithmetic and construct a provability predicate (which we will call $Prb_T$). Let $\mathbb{N} \models T$. Expand our language to include a new constant symbol $c$. ...
70 views

### alternative Compactness theorem proof

I'm attempting a problem which requires me to prove the compactness theorem for propositional logic ![enter image description here][1]in a slightly different way to normal. I'm struggling to ...
57 views

### Using the compactness theorem

I am working through problems which ask you to apply the compactness theorem (from propositional logic) to problems. How would you go about solving this one? Let $\mathbf{L}$ be an arbitrary ...
48 views

### Compactness of Propositional Logic

I little confused on compactness of propositional logic. So propositional logic has the property of being compact, that is to say, given a set of formulas $\mathcal F$, then $\mathcal F$ is ...
114 views

### Compactness Theorem explanation

Compactness Theorem definition: If $T$ is a theory in a first-order language $L$, then $T$ has a model iff every finite subset $S$ of $T$ has a model. A number of questions regarding to this ...
93 views

### Compactness theorem, directed graph

We study a language L and the axioms of directed graphs. A directed graph is connected if there's for every 2 points a finite path. Prove that ther's no theory T such that it contains the axioms of a ...
58 views

### Logic: compactness theorem, an example

Let L be an arbitrary language and $T_1$ and $T_2$ be non-empty L-theories. Suppose that the L-theory $T_1 \cup T_2$ is inconsistent. Proof that there is an L-sentence $\phi$ such that $T_1$ $\vDash$ ...
168 views

### Proving Tychonoff's theorem with the Compactness theorem of logic

It seems to be known that Tychonoff's Theorem for Hausdorff spaces and the Compactness theorem of first order logic are both equivalent over ZF to the ultrafilter lemma. Does anyone know a slick proof ...
525 views

### Most astonishing applications of compactness theorem outside logic

The compactness theorem has a lot of applications to logic and model theory. I'm looking for applications. I'm looking for theorems in other areas of mathematics which seem at first sight to have ...
299 views

### Is there a “tree-like” proof of compactness theorem in the case of uncountably many variables?

I like proofs using trees and König's lemma, since they are very visual. One of the applications of König's lemma you can show to students is proving compactness theorem for propositional calculus, ...
235 views

### SHOW that there are infinitely many equivalence classes of formulas

Let $\mathcal{Q}$ denote the additive group of rational numbers, i.e. the structure $\left<\mathbb{Q}; +; 0\right>$. Let $\mathcal{L}$ be the language of $\mathcal{Q}$ and let $T$ be the ...
104 views

### Models of infinite cardinal and compactness

I'm stuck with this problem: $L$ is first-order language with identity and $L_q$ a language obtained by adding to $L$ the quantifier $Q$. If $P$ is a formula and $x$ a variable, $QxP$ is a formula ...
221 views

### Compactness theorem and Tychonoff theorem

This thread has it compactness theorem can be derived from Tychonoff theorem. I'm interested in how this can be done, but got stuck. Here's how far I understand: Following the version of campactness ...
953 views

### Proof of the Compactness Theorem for Propositional Logic

I have a problem understanding the proof for the compactness theorem for propositional logic in my logic course. The compactness theorem states that there is a model for an infinite set $S$ of ...
### Is the negation of Gödel's completeness theorem consistent with $ZF$ without AC?
The proof of compactness and completeness of $\mathscr{FOL}$ (with Hilbert system) used Zorn's lemma. And Zorn's lemma is equivalent to the Axiom of choice in $ZF$. So my question is can they be ...