Location



The seminar is held online. Join Zoom Meeting:

https://us02web.zoom.us/j/889933315?pwd=Q3U3V3VQdXpXckhJYWRrcWRiMUhhQT09


19 February (Friday) 4:15 PM  ONLINE
Amitayu Banerjee
Logic and Philosophy of Science PhD Program, Eötvös University, Budapest
 
Combinatorial properties and Dependent Choice
in models where the Axiom of Choice fails
(PhD Pre-Defense Presentation)
We work with models of set theory where the Axiom of choice (AC) can consistently fail. We use the following theories.
  • ZF (Zermelo–Fraenkel set theory without AC).
  • ZFA (ZF with the axiom of extensionality weakened to allow the existence of atoms).
A weak choice principle W is a statement which satisfies the following properties: W is true in ZFC, W is not true in ZF (similarly ZFA), and ZF+W (similarly ZFA+W) does not imply AC. (I enclose a link of Ioanna Dimitriou's `Choiceless Grapher Project': A diagram creator for the hierarchy of weak choice principles connected to Howard–Rubin's `Consequences of the Axiom of Choice' book, https://cgraph.inters.co/).

Firstly, we study new relations of different combinatorial statements with weak choice principles in ZF and ZFA.

  1. Variants of Chain/Antichain principle. A famous application of the infinite Ramsey's theorem (a weak choice principle) is the Chain/Antichain principle (abbreviated here as CAC), which states that `Any infinite partially ordered set contains either an infinite chain or an infinite antichain'. In 2016, Tachtsis investigated the possible placement of CAC in the hierarchy of weak choice principles.1 Komjath–Totik (https://2n6pw521j10.blob.core.windows.net/2n6pw521j10/MTQ0MTkyMTQwMA==.pdf) proved the following variants of CAC, applying Zorn's lemma (which is equivalent to AC in ZF):
    • `If in a partially ordered set all antichains are finite and all chains are countable, then the set is countable'.
    • `If in a partially ordered set all chains are finite and all antichains are countable, then the set is countable'.
    We study the relations of weak choice principles and the above variants of CAC in ZF and ZFA (https://arxiv.org/abs/2009.05368.pdf, https://arxiv.org/pdf/1911.00434.pdf).

  2. Chromatic number of the product of graphs. In 1985, Andras Hajnal applied the Compactness theorem for propositional logic (equivalent to the Ultrafilter lemma (UL) in ZF, a weak choice principle) to prove the statement `If the chromatic number of a graph $G_{1}$ is finite (say a natural number $k$), and the chromatic number of another graph $G_{2}$ is infinite, then the chromatic number of the product of $G_{1}$ and $G_{2}$ is $k$'.2 The author and Zalan Gyenis observed that if $k=3$, then the above statement does not imply the axiom of choice restricted to 3 element sets in ZFA (and consequently does not imply UL in ZFA) (https://arxiv.org/pdf/1911.00434.pdf). We will see two open problems in this area.

  3. Maximal Independent sets. In 2011, Harvey M. Friedman sketched a proof of the fact that AC is equivalent to the statement `Every graph has a maximal independent set' in ZF. We study new relations of weak choice principles and weaker versions of the above statement in ZF (https://arxiv.org/abs/2009.05368.pdf).

  4. Cofinal subsets of posets. It is well known that AC implies the following statements.
    • `Every partially ordered set has a cofinal well-founded subset' (we abbreviate by CWF).
    • `Every partially ordered set without a maximal element has two disjoint cofinal subsets' (we abbreviate by CS).
    In 2016, Howard, Saveliev, and Tachtsis investigated the possible placement of CS in the hierarchy of weak choice principles. In 2017, Tachtsis investigated the possible placement of CWF in the hierarchy of weak choice principles. We study the new relations of CWF and CS with weak choice principles (https://arxiv.org/abs/2009.05368.pdf). We will also see some open problems in this area.

  5. Dilworth's theorem. In 1950, Dilworth proved the statement `If $\mathbb{P}$ is an arbitrary poset, and $k$ is a natural number such that $\mathbb{P}$ has no antichains of size $k + 1$ while at least one $k$-element subset of $\mathbb{P}$ is an antichain, then $\mathbb{P}$ can be partitioned into $k$ chains' (we abbreviate by DT) using Teichmüller–Tukey Lemma (which is equivalent to AC in ZF). It is well-known that a proof of DT can be achieved by the $n$-coloring Theorem due to De Bruijn and Erdős (we note that the $n$-coloring theorem is a weak choice principle) for any integer $n$ greater than or equal to 3. In 2019, Tachtsis investigated the possible placement of DT in the hierarchy of weak choice principles. We study new relations of DT with weak choice principles (https://arxiv.org/pdf/1911.00434.pdf). We will see some open problems in this area.

  6. A weaker form of Łoś's lemma. We recall the following weaker form of Łoś's lemma: `If $\mathcal{A}=\langle A, \mathcal{R}^{\mathcal{A}}\rangle$ is a non-trivial relational $\mathcal{L}$-structure over some language $\mathcal{L}$, and $\mathcal{U}$ be an ultrafilter on a non-empty set $I$, then the ultrapower $\mathcal{A}^{I}/\mathcal{U}$ and $\mathcal{A}$ are elementarily equivalent' (we abbreviate by LT). In 1975, Howard proved that LT + UL implies AC in ZF. In 2019, Tachtsis investigated the possible placement of LT in the hierarchy of weak choice principles. We study new relations of LT with weak choice principles (https://arxiv.org/pdf/1911.00434.pdf).

  7. A graph homomorphism problem. Komjáth sketched a proof of the following generalization of the $n$-coloring Theorem due to De Bruijn and Erdős: `For any infinite graph $G=(V_{G}, E_{G})$ and any finite graph $H=(V_{H}, E_{H})$, if every finite subgraph of $G$ has a homomorphism into $H$, then so has $G$' abbreviated here as $\mathcal{P}_{G,H}$. We study new relations of $\mathcal{P}_{G,H}$ with weak choice principles.

2. Secondly, we study the status of Dependent Choice (a weak choice principle, abbreviated here as DC) and combinatorial properties in different symmetric extensions. We recall that symmetric extensions of the ground model $V$ are symmetric submodels of the forcing extension $V[G]$ (with respect to a generic filter $G$) containing the ground model $V$, where AC can consistently fail. We also recall that a symmetric extension of $V$ (denoted by $V(G)$) can be built up with respect to a forcing notion $\mathbb{P}$, a group of permutations $\mathcal{G}$ of $\mathbb{P}$, and a normal filter $\mathcal{F}$ of subgroups over $\mathcal{G}$. In such cases, we say that the symmetric extension is defined with respect to the tuple $\langle \mathbb{P},\mathcal{G},\mathcal{F}\rangle$ (we say symmetric system).

  1. Preserving Dependent Choice. DC is equivalent to the Baire Category Theorem (which is a fundamental theorem in functional analysis), and other important theorems like the countable version of the Downward Löweinheim–Skolem theorem in ZF. On the other hand, AC has controversial applications like the existence of a non-Lebesgue measurable set of real numbers, Banach–Tarski Paradox, and the existence of a well-ordering of real numbers whereas DC does not have such counterintuitive consequences. In particular, DC is consistent with assumptions such as `All sets of reals are regular' for different versions of regularity (for example Lesbegue measurability). Thus it is often desirable to preserve DC in symmetric extensions.

    $DC_{\kappa}$ for an infinite well-ordered cardinal $\kappa$: Let $\kappa$ be an infinite well-ordered cardinal (i.e., $\kappa$ is an aleph). Let $S$ be a non-empty set and let $R$ be a binary relation such that for e$V$ery $\alpha<\kappa$ and every $\alpha$-sequence $s =(s_{\epsilon})_{\epsilon<\alpha}$ of elements of $S$ there exists $y \in S$ such that $s R y$. Then there is a function $f : \kappa \rightarrow S$ such that for every $\alpha<\kappa$, $(f\restriction \alpha) R f(\alpha)$.

    We note that $DC_{\aleph_{0}}$ is a reformulation of DC. We denote by % latex2html id marker 823 $ DC_{<\lambda}$ the assertion % latex2html id marker 825 $ (\forall\eta < \lambda)DC_{\eta}$. Moreover, % latex2html id marker 827 $ DC_{\lambda}$ implies $DC_{\kappa}$ if % latex2html id marker 831 $ \lambda>\kappa$ in ZF.

    In 2014, Asaf Karagila proved that if $V$ is a model of ZFC, $\mathbb{P}$ is a $\kappa$-closed notion of forcing, and $\mathcal{F}$ is $\kappa$-complete then $DC_{<\kappa}$ is preserved in the symmetric extension of $V$ in terms of symmetric system $\langle \mathbb{P},\mathcal{G},\mathcal{F}\rangle$. Let $V$ be a model of ZFC. Karagila wrote that if $\mathbb{P}$ is $\kappa$-c.c. and $\mathcal{F}$ is $\kappa$-complete, then $DC_{<\kappa}$ is preserved in the symmetric extension of $V$ in terms of symmetric system $\langle \mathbb{P},\mathcal{G},\mathcal{F}\rangle$.3 Moreover, the author and Karagila used the later result to answer a question of Apter (see https://www.impan.pl/pl/wydawnictwa/czasopisma-i-serie-wydawnicze/bulletin-polish-acad-sci-math/all/67/1/112842/preserving-dependent-choice). We observe the following inspired by the first result of Karagila.

    1. Let $V$ be a model of ZFC. If $\mathbb{P}$ is $\kappa$-distributive and $\mathcal{F}$ is $\kappa$-complete, then $DC_{<\kappa}$ is preserved in the symmetric extension of $V$ in terms of symmetric system $\langle \mathbb{P},\mathcal{G},\mathcal{F}\rangle$ (https://arxiv.org/abs/1903.05945v3).

    2. We also study that even if we start with a model $V$, which is a model of ZF + $DC_{\kappa}$ where AC can consistently fail, then we can still preserve $DC_{<\kappa}$ in a symmetric extension of $V$ in certain cases (https://arxiv.org/abs/1903.05945v3).

  2. Proving Dimitriou's Conjecture. In 2011, Ioanna Dimitriou constructed a symmetric extension in her Ph.D. thesis. She conjectured that DC might fail in that model. We prove the conjecture (https://arxiv.org/abs/1903.05945v3).

  3. Extending some results of Apter, Dimitriou, and Koepke. We carry forward a few research works of Apter, Dimitriou, and Koepke based on the behaviour of large cardinals in ZF (https://onlinelibrary.wiley.com/doi/abs/10.1002/malq.201800018). In particular, we observe that the first supercompact cardinal can be the first uncountable regular cardinal in Gitik's symmetric extension. This extends the result of Apter, Dimitriou, and Koepke (see https://onlinelibrary.wiley.com/doi/abs/10.1002/malq.201110007) from 2014. We will see an open problem in this area. In 1985, Apter proved the consistency of the fact that all successor of regular cardinals can be weakly compact in presence of DC. We recall that in the hierarchy of large cardinals, a measurable cardinal is strictly stronger than a Ramsey cardinal, and a Ramsey cardinal is strictly stronger than a weakly compact cardinal. We observe that the statement `All successors of regular cardinals can be Ramsey (and not measurable)' does not imply countable choice (CC) in ZF. We also observe the existence of an infinitary Chang conjecture in two different symmetric extensions constructed by Apter–Koepke (from 2006) inspired by the methods of Dimitriou from her Ph.D. thesis (2011).

  4. Reducing the large cardinal assumption of some results. In 2013, Apter–Cody worked on symmetric extensions based on supercompact Prikry Forcing to prove some consistency results on consecutive singular cardinals and continuum functions assuming a supercompact cardinal (https://projecteuclid.org/euclid.ndjfl/1361454970). We reduce the large cardinal assumption from a supercompact cardinal to a strongly compact cardinal (https://arxiv.org/abs/1903.05945v3) by working on a symmetric extension based on strongly compact Prikry Forcing and applying a recent result due to Usuba from 2019 (again we recall that in the hierarchy of large cardinals, a supercompact cardinal is strictly stronger than a strongly compact cardinal).

In this presentation, I shall discuss the new results (with more historical details, but without the technical details). We shall also discuss some open problems, and a direction for further studies in this area.

PDF version of the abstract


26 February (Friday) 4:15 PM  ONLINE
Erik Nelson
Department of Philosophy,  Dalhousie University, Canada
 
The Grammar of Bird Cognition:
Nonlinguistic Concepts, Holism, and Internal Relations
While it would be too soon to claim that a scientific consensus has been reached, many researchers in the fields of comparative psychology, behavioural ecology, and cognitive science are willing to attribute conceptual capabilities to nonlinguistic animals (Shettleworth, 2009, pp. 167–209). In contrast, a group of conceptual holists, inspired by (and including) the work of Wilfrid Sellars, have argued that scientists who attribute conceptual capabilities to nonlinguistic animals have failed to understand what it actually takes to grasp a concept. Sellarsian holists argue that grasping any one concept depends upon the ability to grasp the inferential connections between it and other concepts. These inferential connections are supposedly only available through linguistic practices. It is the alleged failure to recognize this requirement that has led Robert Brandom to claim that “analytic philosophy has failed cognitive science” (2009, 197). In this paper, I will assess the claim that grasping a concept is only possible through the medium of language by comparing the claims of Sellarsian holists to recent empirical work on same/different transfer tasks with Clark’s nutcrackers and black-billed magpies (Magnotti et al. 2015, Magnotti et al. 2017, Wright et al. 2017). I argue that success at same/different transfer tasks is only possible for subjects that can grasp (what the later-Wittgenstein called) the internal relation between the concepts of same and different. Two concepts are internally related if it is only possible to understand one by also understanding the other. The success of Clark’s nutcrackers and black-billed magpies at these tasks demonstrates that grasping the inferential connections between (at least some) concepts is not dependent upon linguistic capabilities.
References:

Brandom, R. (2009). How Analytic Philosophy Has Failed Cognitive Science. In Reason in Philosopy: Animating Ideas (pp. 197–224). Harvard University Press.

Magnotti, J. F., Katz, J. S., Wright, A. A., & Kelly, D. M. (2015). Superior abstract-concept learning by Clark’s nutcrackers (Nucifraga columbiana). Biology Letters, 11(5), 20150148. https://doi.org/10.1098/rsbl.2015.0148

Magnotti, J. F., Wright, A. A., Leonard, K., Katz, J. S., & Kelly, D. M. (2017). Abstract-concept learning in Black-billed magpies (Pica hudsonia). Psychonomic Bulletin & Review, 24(2), 431–435. https://doi.org/10.3758/s13423-016-1132-4

Shettleworth, S. J. (2009). Cognition, Evolution, and Behavior. Oxford University Press.

Wright, A. A., Magnotti, J. F., Katz, J. S., Leonard, K., Vernouillet, A., & Kelly, D. M. (2017). Corvids Outperform Pigeons and Primates in Learning a Basic Concept. Psychological Science, 28(4), 437–444. https://doi.org/10.1177/0956797616685871