2

I happened to come across the compactness theorem for propositional logic.. It struck me as odd that we needed to prove that a property such as a model existing for the set exists iff there exists a model for each finite subset.

I feel like such a thing is trivial to claim and could probably have an encompassing proof such as "a set has a property iff every finite subset of the set has the same property"

I'd like if anyone can think of some counter example... where each finite subset has a certain property but the entire set does not.

crommy
  • 131

3 Answers3

3

The trivial example of such a property is finiteness: if $A$ is any infinite set, then all the finite subsets of $A$ are finite but $A$ itself isn't finite.

A slightly more interesting example is boundedness (in the context of metric spaces): every finite subset of a metric space is bounded, but there are metric spaces of unbounded diameter.


However, to appreciate the compactness theorem I believe it's most helpful to think about an example coming from logic - but not first-order logic! In second-order logic (working in the language of arithmetic) we can write the sentence "Every nonempty set has a least element;" when we add a couple more axioms of basic arithmetic, we get second-order Peano arithmetic, which is categorical in the sense that it has a unique (up to isomorphism) model, namely $\mathbb{N}$.

But this means compactness fails for second-order logic! Consider the language consisting of the usual language of arithmetic together with a new constant symbol $c$, and let $T$ be the theory in this language consisting of second-order Peano arithmetic together with, for each $k\in\mathbb{N}$, the sentence $$c\not=1+1+...+1\quad\mbox{($k$ times)}.$$ Then $T$ cannot have a model, even though every finite subset of $T$ does have a model (this is a good exercise).

Noah Schweber
  • 245,398
1

If get the set $ A=\{1/n\} $ (n is natural) so for a limited subset of $A$ it is compact because is closed and limited in reals, but the entire set is not.

user740332
  • 67
  • 5
1

The question is very general.

"think of some counter example... where each finite subset has a certain property but the entire set does not."

This is case-dependent. We could probably list 100 properties of an infinite set that are shared by all it's finite subsets. But we can probably also list 100 other properties of the same infinite set that are not preserved by it's finite subsets.

Adam Rubinson
  • 20,052