The very first thing one usually does in a logic course is to defines a formal language for the propositional logic.
I don't want to bother what a "logic" is and why we need a "language" which we define know for a "logic".
A language consists of an ALPHABET and a GRAMMAR.
An alphabet $\mathcal{A}$ is a union of three different sets, we will call the element of an alphabet symbols. The first set are the symbols for the propositional variables like $A,B,C....$, the second set is the set of logical symbols $T,F,\wedge,\vee,\implies,\iff$ and the thirs set are non-logical symbols like $(,)$
Now here comes the first thing I don't understand yet we say a propositional formula is a sequence of symbols that satisfies certain rules. What I don't understand is how exactly I can write the set I take an element from when I say: Assume $\phi$ is a propositional formula. Maybe somebody can help me.
The condition that has to be satisfied if $\phi$ wants to be an element of the set of all statements (that I don't know how to define in logical notation) are: $\phi$ is a propositional variable($\iff \phi$ is a function with domain $\{1\}$ and range $\mathcal{A}$ and $\phi(1)$ is a propositional variable) or $\phi$ is $F$( $\iff \phi$ is a function with domain $\{1\}$ and range $\mathcal{A}$ and $\phi(1)=F$) or $\phi$ is $T$ ( $\iff \phi$ is a function with domain $\{1\}$ and range $\mathcal{A}$ and $\phi(1)=T$) or there is a $ n\in\mathbb{N}$ such that $n\geq 2$ and $\phi$ is a function with domain $\{1,...,n\}$ and range $\mathcal{A}$ and $\phi(1)=\neg$ and $\psi:\{1,...,n-1\}\rightarrow \mathcal{A}$ with $\forall k\in\{1,...,n-1\}\psi(k)=\phi(k+1)$ is a propositional formula or there is a $n\in\mathbb{N}$ and a $k\in\mathbb{N}$ such that $n\geq 5$ and $k\in\{2,...,n-1\}$ and $\phi$ is a function with domain $\{1,...,n\}$ and range $\mathcal{A}$ and $\phi(1)=($ and $\phi(n)=)$ and $\phi(k)=\wedge\backslash\vee\backslash\implies\backslash\iff$ and $\psi_1:\{1,....,k-2\}\rightarrow \mathcal\{A\}$ with $\forall j\in{1,...,k-2}\psi_1(j)=\phi(j+1)$ and $\psi_2:\{1,...,(n-1)-k\}$ with $\forall z\in \{1,...,(n-1)-k\}\psi_2(z)=\phi(z+k)$ are propositional formulas.
My question to you how can I prove this claim:
If a property holds for every constant (propositional variable,T,F) and the implications ( $a$ is a propositional formula and $a$ has property $\Rightarrow \neg a$ has property,$a$ and $b$ are propostioanl formulas and $a$ and $b$ have property then $a\wedge b$ has property (and so on for the other logical operationsyymbols)) are true then every propositional formula has the property.
I am trying to find a way to prove this by induction over the natural numbers $n\in\mathbb{N}$, however I didn't succeed in building this bridge. I was reading a book (H.-D Ebbinghaus,J.Flum,W.Thomas) and they have proposed to define the notion of a derivation with a lenght $n\in\mathbb{N}$ and then show that the claim above implies that every derivation fullfils the property. Which then in turn means every element fullfills the property because every element has (or is) a derivation.
An example of what a derivation is
$((A\wedge B)\vee C) $ is a propositional formula because there exists a derivation, namely
$C$ is a propositional constant
$A$ is a propositional constant
$B$ is a propositional constant
$(A\wedge B)$ is a propositional formula because of $3.$ and $2.$
$((A\wedge B)\vee C)$ is a propositional formula because of $4.$ and $1.$ This derivation has a length of $5$
I have tried to define what a derivation is and to prove that every propositional formula has (or is[because it depends on how we define derivation]) a derivation.
I came to an unsatisfying result. Because I didn't see another way to prove that every propositional formula has a derivation other than changing the definition of what a propositional formula itself is. Thus I have first defined what a derivation is and then said what a propositional formula is, namely objects that we get from certain derivations (the derivation itself depends on "rules" thats why I said certain here). This however prompted a new problem. Namely that if I go the other way around and already have an element I cannot use the prior convenient definition anymore and because the definition that I came up with didn't match the definition which the author intended, I couldn't understand the following proofs in the book anymore. I hope somebody can help me to find a a way to define what a derivation is and then to prove that every propositional has a derivation and eventually to prove the claim above by using this definition of a derivation. My only goal is to find a proof for the claim which preserves the definition of a propositional formula. The above paragraph was just a proposal and described my efforts and thinking-process so far.
If you want to know more details about the work I have done so far please tell me I will edit then, and thank you for reading this long text.