Skip to main content
added 207 characters in body
Source Link
user107952
  • 2k
  • 16
  • 24

I asked this on Math Stack Exchange, but apparently no one paid attention to it. So, I am asking it again, filling in the background necessary to understand it.

Consider a countably infinite set $P$ of propositional atoms, indexed by the positive integers like so: $p_1,p_2,p_3,p_4,...$. We also have the connectives $\land$, $\vee$, and $\neg$ as well as the parentheses $($ and $)$. We define the set $W$ of well-formed formulas from the alphabet $P \cup \{\land,\vee,\neg,(,)\}$ in the standard recursive way given in almost any mathematical logic textbook. Over the set $W$, I define an equivalence relation $E$ by saying that two wffs $A$ and $B$ are related by $E$ iff they are logically equivalent, where logical equivalence is defined in the standard way in any logic textbook. Now, let $B$ be the set of equivalence classes of $W$ under $E$, and consider the Boolean algebra structure $(B;\land,\vee,\neg,0,1)$, where $0$ is the set of contradictions, $1$ is the set of tautologies, and $\land$, $\vee$, and $\neg$ are operations defined by passing to representatives (and it is easy to check that they are well-defined).

I previously asked if the set of propositional atoms, or even any non-empty subset of it, is definable without parameters in the structure $B$. The answer was negative. Now, if we use parameters, certainly any finite subset of the set of propositional atoms is definable. But I believe that is the best possible. So, my current question is, is the set of propositional atoms, or even any infinite subset of it, definable even with parameters? I believe it is not, but how to prove it?

Edit: As a bonus question, can anyone give a complete classification of all the parameter-definable subsets of the structure $B$?

Edit 2: As a matter of fact, I now conjecture that the parameter-definable subsets are finite and cofinite subsets of $B$, that is, $B$ is a minimal structure. Can anyone confirm or deny this conjecture?

I asked this on Math Stack Exchange, but apparently no one paid attention to it. So, I am asking it again, filling in the background necessary to understand it.

Consider a countably infinite set $P$ of propositional atoms, indexed by the positive integers like so: $p_1,p_2,p_3,p_4,...$. We also have the connectives $\land$, $\vee$, and $\neg$ as well as the parentheses $($ and $)$. We define the set $W$ of well-formed formulas from the alphabet $P \cup \{\land,\vee,\neg,(,)\}$ in the standard recursive way given in almost any mathematical logic textbook. Over the set $W$, I define an equivalence relation $E$ by saying that two wffs $A$ and $B$ are related by $E$ iff they are logically equivalent, where logical equivalence is defined in the standard way in any logic textbook. Now, let $B$ be the set of equivalence classes of $W$ under $E$, and consider the Boolean algebra structure $(B;\land,\vee,\neg,0,1)$, where $0$ is the set of contradictions, $1$ is the set of tautologies, and $\land$, $\vee$, and $\neg$ are operations defined by passing to representatives (and it is easy to check that they are well-defined).

I previously asked if the set of propositional atoms, or even any non-empty subset of it, is definable without parameters in the structure $B$. The answer was negative. Now, if we use parameters, certainly any finite subset of the set of propositional atoms is definable. But I believe that is the best possible. So, my current question is, is the set of propositional atoms, or even any infinite subset of it, definable even with parameters? I believe it is not, but how to prove it?

Edit: As a bonus question, can anyone give a complete classification of all the parameter-definable subsets of the structure $B$?

I asked this on Math Stack Exchange, but apparently no one paid attention to it. So, I am asking it again, filling in the background necessary to understand it.

Consider a countably infinite set $P$ of propositional atoms, indexed by the positive integers like so: $p_1,p_2,p_3,p_4,...$. We also have the connectives $\land$, $\vee$, and $\neg$ as well as the parentheses $($ and $)$. We define the set $W$ of well-formed formulas from the alphabet $P \cup \{\land,\vee,\neg,(,)\}$ in the standard recursive way given in almost any mathematical logic textbook. Over the set $W$, I define an equivalence relation $E$ by saying that two wffs $A$ and $B$ are related by $E$ iff they are logically equivalent, where logical equivalence is defined in the standard way in any logic textbook. Now, let $B$ be the set of equivalence classes of $W$ under $E$, and consider the Boolean algebra structure $(B;\land,\vee,\neg,0,1)$, where $0$ is the set of contradictions, $1$ is the set of tautologies, and $\land$, $\vee$, and $\neg$ are operations defined by passing to representatives (and it is easy to check that they are well-defined).

I previously asked if the set of propositional atoms, or even any non-empty subset of it, is definable without parameters in the structure $B$. The answer was negative. Now, if we use parameters, certainly any finite subset of the set of propositional atoms is definable. But I believe that is the best possible. So, my current question is, is the set of propositional atoms, or even any infinite subset of it, definable even with parameters? I believe it is not, but how to prove it?

Edit: As a bonus question, can anyone give a complete classification of all the parameter-definable subsets of the structure $B$?

Edit 2: As a matter of fact, I now conjecture that the parameter-definable subsets are finite and cofinite subsets of $B$, that is, $B$ is a minimal structure. Can anyone confirm or deny this conjecture?

Became Hot Network Question
edited tags
Link
Joel David Hamkins
  • 236.3k
  • 44
  • 777
  • 1.4k
added 133 characters in body
Source Link
user107952
  • 2k
  • 16
  • 24

I asked this on Math Stack Exchange, but apparently no one paid attention to it. So, I am asking it again, filling in the background necessary to understand it.

Consider a countably infinite set $P$ of propositional atoms, indexed by the positive integers like so: $p_1,p_2,p_3,p_4,...$. We also have the connectives $\land$, $\vee$, and $\neg$ as well as the parentheses $($ and $)$. We define the set $W$ of well-formed formulas from the alphabet $P \cup \{\land,\vee,\neg,(,)\}$ in the standard recursive way given in almost any mathematical logic textbook. Over the set $W$, I define an equivalence relation $E$ by saying that two wffs $A$ and $B$ are related by $E$ iff they are logically equivalent, where logical equivalence is defined in the standard way in any logic textbook. Now, let $B$ be the set of equivalence classes of $W$ under $E$, and consider the Boolean algebra structure $(B;\land,\vee,\neg,0,1)$, where $0$ is the set of contradictions, $1$ is the set of tautologies, and $\land$, $\vee$, and $\neg$ are operations defined by passing to representatives (and it is easy to check that they are well-defined).

I previously asked if the set of propositional atoms, or even any non-empty subset of it, is definable without parameters in the structure $B$. The answer was negative. Now, if we use parameters, certainly any finite subset of the set of propositional atoms is definable. But I believe that is the best possible. So, my current question is, is the set of propositional atoms, or even any infinite subset of it, definable even with parameters? I believe it is not, but how to prove it?

Edit: As a bonus question, can anyone give a complete classification of all the parameter-definable subsets of the structure $B$?

I asked this on Math Stack Exchange, but apparently no one paid attention to it. So, I am asking it again, filling in the background necessary to understand it.

Consider a countably infinite set $P$ of propositional atoms, indexed by the positive integers like so: $p_1,p_2,p_3,p_4,...$. We also have the connectives $\land$, $\vee$, and $\neg$ as well as the parentheses $($ and $)$. We define the set $W$ of well-formed formulas from the alphabet $P \cup \{\land,\vee,\neg,(,)\}$ in the standard recursive way given in almost any mathematical logic textbook. Over the set $W$, I define an equivalence relation $E$ by saying that two wffs $A$ and $B$ are related by $E$ iff they are logically equivalent, where logical equivalence is defined in the standard way in any logic textbook. Now, let $B$ be the set of equivalence classes of $W$ under $E$, and consider the Boolean algebra structure $(B;\land,\vee,\neg,0,1)$, where $0$ is the set of contradictions, $1$ is the set of tautologies, and $\land$, $\vee$, and $\neg$ are operations defined by passing to representatives (and it is easy to check that they are well-defined).

I previously asked if the set of propositional atoms, or even any non-empty subset of it, is definable without parameters in the structure $B$. The answer was negative. Now, if we use parameters, certainly any finite subset of the set of propositional atoms is definable. But I believe that is the best possible. So, my current question is, is the set of propositional atoms, or even any infinite subset of it, definable even with parameters? I believe it is not, but how to prove it?

I asked this on Math Stack Exchange, but apparently no one paid attention to it. So, I am asking it again, filling in the background necessary to understand it.

Consider a countably infinite set $P$ of propositional atoms, indexed by the positive integers like so: $p_1,p_2,p_3,p_4,...$. We also have the connectives $\land$, $\vee$, and $\neg$ as well as the parentheses $($ and $)$. We define the set $W$ of well-formed formulas from the alphabet $P \cup \{\land,\vee,\neg,(,)\}$ in the standard recursive way given in almost any mathematical logic textbook. Over the set $W$, I define an equivalence relation $E$ by saying that two wffs $A$ and $B$ are related by $E$ iff they are logically equivalent, where logical equivalence is defined in the standard way in any logic textbook. Now, let $B$ be the set of equivalence classes of $W$ under $E$, and consider the Boolean algebra structure $(B;\land,\vee,\neg,0,1)$, where $0$ is the set of contradictions, $1$ is the set of tautologies, and $\land$, $\vee$, and $\neg$ are operations defined by passing to representatives (and it is easy to check that they are well-defined).

I previously asked if the set of propositional atoms, or even any non-empty subset of it, is definable without parameters in the structure $B$. The answer was negative. Now, if we use parameters, certainly any finite subset of the set of propositional atoms is definable. But I believe that is the best possible. So, my current question is, is the set of propositional atoms, or even any infinite subset of it, definable even with parameters? I believe it is not, but how to prove it?

Edit: As a bonus question, can anyone give a complete classification of all the parameter-definable subsets of the structure $B$?

Source Link
user107952
  • 2k
  • 16
  • 24
Loading