3
$\begingroup$

I am aware of existence of the "generalized quantifiers" as seen here: https://en.wikipedia.org/wiki/Generalized_quantifier to mean "sets of sets". Universal quantifier is a set containing the universe and existential one is a family of all the subsets of the universe but the empty set. You can create more quantifiers by inventing new sets of sets. I got it, more or less.

What I'd like to know is whether anyone pursued other way to generalize the quantifiers - as infinite logical connectives. You can think of universal quantifier as inifite and operaton (can't you?):

$\forall_{x\in X}: p(x) \approx \bigwedge_{x\in X} p(x) \approx p(x_1) \wedge p(x_2)\wedge\dots\wedge p(x_i)\wedge\dots$

Similarly for existential quantifier as inifite or:

$\exists_{x\in X}: p(x) \approx \bigvee_{x\in X} p(x) \approx p(x_1) \vee p(x_2)\vee\dots\vee p(x_i)\vee\dots$

Has anyone found a way to do the same with other logical connectives?

I know that all other connectives can be constructed from these two, so perhaps there is nothing to discover/invent here, but still... I find it interesting to try to evaluate the logical value for

$?_{x\in X}: p(x) \approx \Leftrightarrow_{x\in X} p(x) \approx p(x_1) \leftrightarrow p(x_2)\leftrightarrow\dots\leftrightarrow p(x_i)\leftrightarrow\dots$

which seems to depend on the (possibly infite) parity of the domain $X$ (whatever that means, if anything, as pointed out in the comments).

$\endgroup$
5
  • $\begingroup$ But what is the "parity" of an infinite domain ? Is $1+1+1\ldots$ even or odd ? $\endgroup$ – Mauro ALLEGRANZA Jun 18 '20 at 8:49
  • $\begingroup$ I don't know. It's just something that I stumbled upon when considering infinite $\leftrightarrow$. $\endgroup$ – AdHoc Jun 18 '20 at 8:51
  • 1
    $\begingroup$ It's not true that the universal quantifier can be thought of as an infinite AND operation, under Tarskian semantics. You could be working in a language where there are infinitely many objects, but finitely many names for these objects. This makes it impossible to list them all in a conjunction. $\endgroup$ – user400188 Jun 18 '20 at 13:51
  • $\begingroup$ @user400188 While the possible existence of undefinable elements is definitely important, the broader point about $\forall$ isn't really true. When we set up the definition of $\models$ in a structure $\mathcal{A}$, we first pass to an expansion $\hat{\mathcal{A}}$ of $\mathcal{A}$ gotten by adding new constant symbols naming each of the elements of $\mathcal{A}$. Once we've made this change in language, "$\forall$" can indeed be represented as an infinite conjunction. $\endgroup$ – Noah Schweber Jun 27 '20 at 17:14
  • $\begingroup$ @NoahSchweber I did not have a broader point about the universal quantifier other than what I said. In Tarskian semantics it cannot be thought of as a conjunction of AND operations. You can of course, construct other semantics where the universal quantifier can be thought of as such a conjunction. $\endgroup$ – user400188 Jun 28 '20 at 2:49
0
$\begingroup$

What I'd like to know is whether anyone pursued other way to generalize the quantifiers - as infinite logical connectives.

Yes. In fact, this is of primary importance to the study of infinitary logics. In some theories, the infinite conjunction and disjunction are exactly the universal and existential quantifiers, respectively.

Has anyone found a way to do the same with other logical connectives?

Incidentally, I dealt with this exact problem a few months ago. Here's what I came up with:

Let $U$ be a domain and $C:\mathcal{P}(U)\not\to U$ the choice function on $U$ such that $C(E)\in E$ for all $E$ in the domain of $C$. For each predicate $\phi:U\to\Bbb{B}$, define the operator $\Pi^\phi_C$ according to the following:

  1. for any set $E\subseteq U$,

$$\Pi^\phi_C(E)\equiv\bigg{(}\phi(C(E))\iff\Pi^\phi_C(E\setminus \{C(E)\})\bigg{)}$$

  1. for any expression $P$,

$$P\iff\Pi^\phi_C(\emptyset)\equiv P$$

Suppose now that $U=\{x_n:n\in\Bbb{N}\}$ and for any $E\subseteq U$,

$$C(E)=x_i\quad \text{iff}\quad i=\min\{j\in\Bbb{N}:x_j\in E\}$$

Then:

$$\begin{align} \Pi^\phi_C(U)&\equiv\phi(x_0)\iff\Pi^\phi_C(U\setminus\{x_0\})\\ &\equiv\phi(x_0)\iff\phi(x_1)\iff\Pi^\phi_C(U\setminus\{x_0,x_1\})\\ &\cdots\\ &\equiv\phi(x_0)\iff\phi(x_1)\iff\phi(x_2)\iff\cdots \end{align}$$

This provides a finite means of expressing the new quantifier in terms of the logical connective $\iff$ - independently of "parity" of the set, as you put it.

That being said, I would be extremely cautious using this technique. The existence of the choice function is not provable in every theory. Even then, the evaluation of $\Pi^\phi_C(X)$ is another matter entirely. It is not always possible to evaluate $\Pi^\phi_C(E)$ for all $\phi$, $C$, and $E$.

In particular, if $E$ is uncountable, then there is no finite procedure to determine $\Pi^\phi_C(E)$ for arbitrary $C$.

Addendum

For each predicate $\phi$, let $\mathcal{U}_\phi$ be an ultrafilter over the powerset of the domain $U$ such that the ultrapower $\Bbb{B}^U/\mathcal{U}\cong\Bbb{B}$, then define one of the equivalence classes to be the set of infinite bi-implications whose valuation is "true."

This can be done with or without choice, but the selection of the "correct" ultrafilter can be difficult when the order on $U$ is not apparent. In most cases, it can be shown, informally, that some ultrafilter exists; but this information is not necessarily helpful for evaluating specific infinite statements.

$\endgroup$
5
  • $\begingroup$ I think the abstraction is getting in the way a bit, and in particular bringing $C$ into the picture muddies things. The following seems clearer to me: given a structure $U$ and a formula $\varphi$, you're interested in the existence of a map $B:\mathcal{P}(U)\rightarrow \{\top,\perp\}$ such that $B(\emptyset)=\top$ (to get us off the ground, so to speak) and for each set $M$ and each $x\in M$ we have $$B(M)\equiv\varphi(x)\leftrightarrow B(M\setminus\{x\}),$$ correct? (Really we should talk about multisets since $\leftrightarrow$ isn't idempotent, but whatever.) $\endgroup$ – Noah Schweber Jun 27 '20 at 3:13
  • $\begingroup$ I figured that multisets would be unnecessary, since the goal is to define the infinite connectives over a set. Besides, you can always define a non-injective function $f$ and use $\Pi^\phi_C(f,M)\equiv \phi(f(C(M))\iff\Pi^\phi_C(f,M\setminus\{C(M)\})$ to account for repeat terms. $\endgroup$ – R. Burton Jun 27 '20 at 16:30
  • $\begingroup$ @NoahSchweber The choice function is necessary for quantification over arbitrary sets. The expression you provide only works for finite sets. As a counterexample, consider $B^{2\mid n}(\Bbb{N})$. If you have $B^{2\mid n}(N)\equiv 2\mid1\iff2\mid2\iff\cdots$ then the subformulae evaluate as the sequence $\bot,\bot,\top,\top,\bot,\bot,\top,\top,\ldots$. On the other hand, if you have $B^{2\mid n}(N)\equiv 2\mid 2\iff2\mid4\iff\cdots2\mid 1\iff2\mid3\iff\cdots$, then the evaluation of the subformulae yields the sequence $\top,\top,\top,\top,\ldots\bot,\top,\bot,\top,\ldots$. $\endgroup$ – R. Burton Jun 27 '20 at 16:51
  • $\begingroup$ Choice is only relevant if you're trying to whip up a "canonical" example of such a function. That's why I phrased the question in my comment the way I did: that phrasing doesn't rely on choice at all. As you've observed, that question has a negative answer (whether or not choice holds); the point is that this rules out any natural "infinite bi-implication" operation. Of course you can construct such a thing if you want, but by the above we know it will be pretty artificial and not satisfy many nice properties. $\endgroup$ – Noah Schweber Jun 27 '20 at 17:08
  • $\begingroup$ @NoahSchweber I wouldn't expect their to be a "nice" infinite bi-implication operation in the first place - dealing with infinite-length formulas is generally a messy business. The point of this construction is solely to explain how it can be done, regardless of whether or not it should be done. Personally, I would not use this technique at all - but if the OP is interested in infinite connectives, I figure it's better to share what I have than answer with a straightforward "No." If nothing else, maybe someone else can improve upon this technique? $\endgroup$ – R. Burton Jun 27 '20 at 18:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.