2
votes
1answer
35 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$. ...
0
votes
0answers
67 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 ...
1
vote
1answer
55 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 ...
0
votes
2answers
47 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 ...
0
votes
2answers
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 ...
5
votes
2answers
92 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 ...
1
vote
2answers
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$ ...
4
votes
1answer
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 ...
7
votes
5answers
499 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 ...
14
votes
2answers
293 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, ...
1
vote
1answer
225 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 ...
2
votes
1answer
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 ...
4
votes
1answer
212 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 ...
6
votes
2answers
902 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 ...
2
votes
2answers
202 views

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 ...
37
votes
6answers
1k views

Why is compactness in logic called compactness?

In logic, a semantics is said to be compact iff if every finite subset of a set of sentences has a model, then so to does the entire set. Most logic texts either don't explain the terminology, or ...