2
$\begingroup$

In Propositional Logic when we define the set of all propositions inductively how we can prove such a set(smallest with such properties) does exists? means that the set (of all sets with these properties) under intersection operation is not empty?

Definition 1.1.2 from Van Dalen book:

The Set $PROP$ of propositions is the smallest set $X$ with the properties:

(i) $p_{i}\in X (i\in \mathbb{N})$, $\bot \in X$

(ii) $A,B \in X$ then $(A\wedge B), (A\vee B), (A\rightarrow B), (\neg A) \in X$

I know in propositional logic we model it mathematically based on ZF(C) as a common accepted foundation for mathematics and I know there is another definition by formation sequences, I think it shows at least one such set exists but I want to know without it, how we can show that $PROP$ is a set in ZFC?

  • 0
    Symbols such as $\land$ and $($ are not sets. So if we want to construct PROP in ZF encoding is necessary. The rest (construction of the set natural numbers, construction of the set of finite sequences from a set, and so on are standard ZF constructions that you will see in any detailed development of ZF. It takes about one chapter.2012-09-20

1 Answers 1

1

First let us show that if only there is some set somewhere that satisfies both of your conditions, there is also a smallest such set.

It is easy to show that for any nonempty set of solutions to (i)+(ii), their intersection is still a solution. Then, under the assumption that some set $A$ is a solution, we can set $\mathit{PROP}$ to be the intersection of all subsets of $A$ that satisfy (i)+(ii), and that is clearly minimal among all solutions that are subsets of $A$. However, this is also a global minimum, because for any solution $B$, it holds that $\mathit{PROP}\subseteq B\cap A \subseteq B$.

Now for the main part. We suppose we have decided on a fixed set $L$ of proposition letters and and some arbitrary mathematical objects not in $L$ to represent the logical symbols. Then $\Sigma = L\cup\{{\land},{\lor},{\to},{\neg},{\bot},{(},{)}\}$ is a set, and then the collection $\Sigma^*$ of all finite sequences of elements of $\Sigma$ is a set. Now $\Sigma^*$ satisfies both of your conditions (i) and (ii), so we can use it as $A$ in the reasoning above. Therefore $\mathit{PROP}$ exists.

(Why is $\Sigma^*$ a set? Each of its elements is a function from some subset of $\mathbb N$ to $\Sigma$, so in particular it is a relation between $\mathbb N$ and $\Sigma$. So every element of $\Sigma^*$ is a subset of $\mathbb N\times \Sigma$, and therefore $\Sigma^*$ itself is a subset of $\mathcal P(\mathbb N \times \Sigma)$ and so $\Sigma^*$ is a set).

  • 0
    I cannot imagine any situation where one would want to choose as $L$ something that is not _plainly and obviously_ a set.2012-09-21