Infinitely More

Infinitely More

Share this post

Infinitely More
Infinitely More
Expressive completeness of a logical language
Copy link
Facebook
Email
Notes
More
A Panorama of Logic

Expressive completeness of a logical language

Some collections of logical connectives are able to express all the others—they are expressively complete.

Joel David Hamkins's avatar
Joel David Hamkins
Jun 10, 2023
∙ Paid
10

Share this post

Infinitely More
Infinitely More
Expressive completeness of a logical language
Copy link
Facebook
Email
Notes
More
2
3
Share

We say that a collection of logical connectives in propositional logic is expressively complete (also known as expressively adequate), if those connectives are able to express all logical truth functions of any positive arity.

Let us explore various complete and incomplete sets of connectives, and the various reasons a language may be incomplete: it may be T-preserving, F-preserving, monotone, affine, or self-dual. Eventually, we shall organize the various sublanguages of propositional logic into a hierarchy of expressivity.

Keep reading with a 7-day free trial

Subscribe to Infinitely More to keep reading this post and get 7 days of free access to the full post archives.

Already a paid subscriber? Sign in
© 2025 Joel David Hamkins
Privacy ∙ Terms ∙ Collection notice
Start writingGet the app
Substack is the home for great culture

Share

Copy link
Facebook
Email
Notes
More