nForum - Search Results Feed (Tag: set) 2021-09-23T19:11:04-04:00 https://nforum.ncatlab.org/ Lussumo Vanilla & Feed Publisher small cardinality selection axiom https://nforum.ncatlab.org/discussion/2899/ 2011-07-15T08:56:04-04:00 2021-05-24T03:43:18-04:00 Mike Shulman https://nforum.ncatlab.org/account/3/ New page small cardinality selection axiom.

New page small cardinality selection axiom.

]]>
Type theory language with set theoretic objects? https://nforum.ncatlab.org/discussion/12088/ 2020-12-25T17:32:55-05:00 2020-12-26T02:39:09-05:00 justin https://nforum.ncatlab.org/account/2569/ Hello, I’m starting to learn about type theory (in HoTT or articles on the net) after having been “passively” using it for years in programming languages. My question may certainly be a bit ...

Hello,

I’m starting to learn about type theory (in HoTT or articles on the net) after having been “passively” using it for years in programming languages. My question may certainly be a bit simple but I couldn’t find a resource on the net, so better ask it!

Let’s say I take as granted usual set-theory (ZFC let’say), with its standard notion of set, function and real numbers. Then I would like to “inject” those objects in type theory formalism. My goal is to exploit the type theory expression system for constructive proofs without having “constructively-obtained objects”. In other words, I don’t really care about constructive sets, reals, measures, or anything. I’m more interested in expression theorems and structures in type theory, and using this language for object manipulation.

So I started an easy example or semi-ring of parts (from measure theory). So far, it goes at follows: (1) I use “set” to talk abut ZFC sets, “function” for function in the usual ZFC sense, and “program” for arrows from type theory (2) for any set E, I abuse notation by writing x:E when an object (set) x belongs to E, in the usual sense (judgment)

Fix two sets $A\subseteq E$. For all $n:\mathbb{N}$, I define $I_n$ the set $\{1,\dots,n\}$ and $Assoc(n) \equiv proj_1\bigg(\sum_{a:I_n\to A}(i:I_n,j:I_n)\to (i=j) + (a|_i \cap a|_j = \emptyset) \bigg)$ So if I don’t mistake, this consists of programs from $I_n$ to $A$ that where constructed from programs with an additional specification that either it is proved that $i=j$, or it is proved that the valued of the program are disjoint sets.

Next I define the type $F \equiv \sum_{c: E}\sum_{a:Assoc(n)} (c = a|_1 \cup \dots \cup a|_n) .$ If I don’t mistake, this type consists of (dependent) programs that provide a proof that c (in E) may be written as a disjoint finite union of elements in A.

Next I define the type $D \equiv \prod_{x,y:A}\sum_{f:F}(x\setminus y = proj_1(f))$ If I don’t mistake, this consists of programs that prove that for all x,y: A, there is a writing of the difference $x\setminus y$.

Now I assume the judgment $d: D$ is true (think of A as being a semi-ring in E, but that won’t be important for the remaining part), and I’m interested in constructing a program for $(a:A) \to \sum_{x:A}(x = \emptyset)$, that is: as soon as there exists an element in A, the empty set belongs to A. First, is that indeed equivalent to $(a:A)\to (\emptyset\in A)$ ? For this, I’m going to use the element $d$ assumed to exist. I define the program as $f(a:A) \equiv proj_1(proj_2(proj_2(d(a,a))))$, that is: I evaluate the program $d$ at $(a,a)$, yielding some $e: \sum_{f:F}(a\setminus a = proj_1(f))$. Now I project this $e$ to extract the proof $(a\setminus a = a|_1\cup\dots\cup a|_n)$ as above.

To me, this formally defines a program $(a:A) \to \sum_{a:Assoc(n)}(a\setminus a = a|_1\cup\dots\cup a|_n)$. In my eyes, this is enough to conclude, because the type $(a\setminus a = a|_1\cup\dots\cup a|_n)$ is the same as $(\emptyset=a|_1)$. But here I’m not sure how I should justify the argument. I’m ok to “inject” standard set-theoretic logic, so to me, it is sufficient to have a lemma proving this somewhere, which is kind of trivial. In the same spirit, is it ok to “assume” that $(a:A) \to \sum_{x:A}(x = \emptyset)$ and $(a:A)\to (\emptyset\in A)$ are equivalent programs?

Could someone, somehow validate my approach here?

I emphasize on the idea that I would like to exploit the formalism of type theory without committing to constructive analysis. I like my usual non-constructive analysis objects and I wouldn’t be happy in facing hard and touchy constructivist problems.

Regards,

Justin

]]>
Do non-monotonicity / higher-order / probabilistics / modalities / connectives exhaust all possible https://nforum.ncatlab.org/discussion/10446/ 2019-10-23T12:56:30-04:00 2019-10-25T07:08:42-04:00 tomr https://nforum.ncatlab.org/account/909/ I am searching for all the possible features of reasoning (all of them can be expressed in logic), so far I have found the following features: non-monotonicity, defeasible reasoning (expressed by ...

I am searching for all the possible features of reasoning (all of them can be expressed in logic), so far I have found the following features:

• non-monotonicity, defeasible reasoning (expressed by special features of consequence relation)
• probabilistic reasoning (expressed by assignment of probabilities to the predicates and by the operations on the probabilities to the connectives and modal operators)
• higher order logic (expressed by allowing the predicated to take other predicates and formulas as arguments)
• modal operators (expressed by the unary operators acting on the predicates and formules)
• special connectives (expressed by special connectives that can arise in linear/substructural setting)

My question is this - are there any other features beside those 5, features that can improve the expresiveness of the logic.

I am trying to combine all those features in one logic and initially I would be happy to know that the set of those 5 features is exhaustive and so - when I come up with the language that can express all those 5 features then there is no more general language than that. Of course, I am thinking about templates, i.e., I will leave open the final set of modal operators and connectives (and the interactions among them), because different concrete logics can arise in each concrete choice of those. My aim is to create reasoner (forward chaining engine) that could be used for such templates and that works modulo concrete set of modal operators and connectives.

Of course, I will have to find common proofs for each of the logic but I plan to automate this task by formalizing each concrete logic in Coq or Isabelle/HOL as it has already be done by linear logics. Then (semi)automatic proof search can lead to the proofs of rejections of soundness and completeness theorems and other theorems for each logic. I am even thinking about combination of genetic search (for the operators/connectives/their sequence rules) with automatic theorem proving (for the theorems about concrete logic) (possibly - with deep learning inspired) for (semi)automatic discovery and development of logics. But to guide all this process, to predict the most general grammar for the possible logics, I should be sure that there is nothing beyond those 5 features. (Neural methods have stuck in deadlock, as can be seen from delayed introduction of autonomous vehicles, that is why strong boost of symbolic methods is necessary and automation of the discovery and research of the logics is the key process for the adoption of symbolic methods in industrial setting).

After that I will have to find semantics, but I am sure that set semantics (with probability distributions and set operations and relations (for modalities and substructural connectives)) is sufficient for all those 5 features, because everything in math can be expressed by (ZFC) set theory and that is why any other possible (sophisticated) semantics can be expressed via sets anyway.

Of course, I am aware of the efforts by Logica Universalis community, but the Florian Rabe, but the community of categorical logics and institution theory. But I am having hard time to find the logic that already encompass those 5 features and also I can not find definite answer that those 5 features are exhaustive or am I missing something?

I would like to add that it is very important that everyone at this time come up with some advice or suggestion, idea. Now the economic crisis is starting again and it is very important to finalize the achievement of artificial intelligence and streamline them into industry exactly now. Only the increase of the supply side productivity (by the artificial intelligence) can save the us from the coming crisis.

]]>
Using relations to describe functions https://nforum.ncatlab.org/discussion/7526/ 2016-12-02T13:33:04-05:00 2016-12-07T08:02:47-05:00 PaoloPerrone https://nforum.ncatlab.org/account/1536/ Consider sets and functions. A relation between two sets can then be expressed as a subset of a Cartesian product, in other words, we can define it and describe it using functions. Viceversa, can we ...

Consider sets and functions. A relation between two sets can then be expressed as a subset of a Cartesian product, in other words, we can define it and describe it using functions.

Viceversa, can we describe functions using relations as the “fundamental” arrows? That is, can we define and describe functions without using other functions, only relations?

]]>
Determinacy https://nforum.ncatlab.org/discussion/7203/ 2016-07-22T12:11:27-04:00 2016-07-22T15:01:41-04:00 spitters https://nforum.ncatlab.org/account/936/ Urs is doing a demo on the nlab. He is elaborating the axiom of determinacy. Set theorist, please elaborate.

Urs is doing a demo on the nlab. He is elaborating the axiom of determinacy. Set theorist, please elaborate.

]]>
partial and (total) functions https://nforum.ncatlab.org/discussion/6697/ 2015-07-30T01:49:04-04:00 2015-08-27T08:29:05-04:00 matc https://nforum.ncatlab.org/account/1420/ if "a partial function is the same as a functional relation seen from a different point of view." then why it is considered that partial functions are generalizations of functions, (at ... if "a partial function is the same as a functional relation seen from a different point of view." then why it is considered that partial functions are generalizations of functions, (at least that says Wikipedia in partial function entry) (if a function is "precisely a relation that is both functional and entire.")? ]]> What is precisely the definition of the term homomorphism in the definition of function? https://nforum.ncatlab.org/discussion/6029/ 2014-06-11T00:33:13-04:00 2014-06-11T02:35:25-04:00 MateoC https://nforum.ncatlab.org/account/1234/ In the outstanding definition of function, nLab says: "In a strict sense of the term, a function is a homomorphism f:S→T of sets..." 1. What is exactly the definition of homomorphism in ... In the outstanding definition of function, nLab says: "In a strict sense of the term, a function is a homomorphism f:S→T of sets..."
1. What is exactly the definition of homomorphism in this context?

In the definition of homomorphism, nLab says: "More generally, a homomorphism between sets equipped with any algebraic structure is a map preserving this structure."
2. Then All the sets have an algebraic structure, or a set is an algebraic structure itself? ]]>
Constructive mathematical analysis of recent "Quantum States are Real" publications https://nforum.ncatlab.org/discussion/3797/ 2012-05-10T14:44:26-04:00 2012-05-20T07:36:20-04:00 Ben_Sprott https://nforum.ncatlab.org/account/304/ Hi, If you haven’t looked at these yet, please have a look. They are calling it the biggest discovery in quantum mechanics for decades. Nature article Nature Physics Lucien Hardy, my old ...

Hi,

If you haven’t looked at these yet, please have a look. They are calling it the biggest discovery in quantum mechanics for decades.

Nature article

Nature Physics

The reason I am posting this is that I would like to begin a discussion focusing on classical versus constructive (lack of excluded middle) mathematics as a means of dissecting the issue of realism in quantum mechanics. The articles listed are probing a very deep problem of realism in quantum mechanics. Does the wavefunction reflect our knowledge of a system or does it reflect reality itself. They use the language of ontic versus epistemic states and I will explain those.

Ontic states are variables which we think of as concerning an underlying reality and epistemic states are like probability distributions which reflect the information we have about a system. Were I to flip a coin and cover it and ask you to tell me about this coin, you would say it is 50 % heads and 50% tails. In my case, I peaked at the coin and the state that I would use to describe the coin is 100% heads, so the probability distribution just reflects the information we have been given and does not reflect reality. I could also have told you that the coin has landed on its side and is in the “Quails” state. You would then update your probability distribution to include a third state and this process begins again when I reflip the coin and ask you again what you think the state is.

The reason I am posting this here, is that this community seems familiar with the following research in the foundations of mathematics. In it I discovered the following interesting point:

Bifurcation of notions

On the other hand, differences in axiomatization or definition that make no difference classically can result in actual differences in behavior constructively. Therefore, classically equivalent notions often “bifurcate” (or “trifurcate” or worse) into multiple inequivalent constructive ones. This tends to happen whenever a concept involves negation and, to a lesser degree, disjunction and existential quantification.

I would like to offer for discussion the notion that the ontic states (bases and classical states, states of reality) and the epistemic states (quantum states, wavefunctions, states of knowledge) have been consistently treated to different axiomatizations in physics, perhaps even in the same paper/textbook without the author realizing it. Furthermore, I am offering that the multiple overlaping epistemic states which one can have for the same ontic state in quantum mechanics derives from the bifurcation between the classical mathematics one uses on the ontic states and the constructive mathematics on the epistemic states. It comes from the use of the existential quantification which one passes up from the ontic realm up to the epistemic realm when one talks about the elements of the Hilbert space or the space of quantum states. Further, we should find in the articles listed above that they represent an attempt to eliminate the constructive mathematics at the epistemic level. In particular, we see in Hardy’s paper the central axiom is of “Ontic Indifference” and here it is stated:

“Ontic indiﬀerence. Any quantum transformation on a system which leaves unchanged any given pure state, $| \psi \rangle$, can be performed in such a way that it does not aﬀect the underlying ontic states, $\lambda \in \Lambda_{| \psi \rangle}$ in the ontic support of that pure state.”

What we should note is the presence of the existential quantifier being passed up from the ontic states to the epistemic states. It is here where we can begin with dissecting this recent work in terms of foundations. Below, we the definition of “ontic support”:

“By the ontic support of a given state, $|\psi \rangle$, we mean the set, $\Lambda_{|\psi \rangle}$, of ontic states, $\lambda$ which might be prepared when the given pure state is prepared (i.e. those ontic states that have a non-zero probability of being prepared when the given pure state is prepared)”

]]>
Simplicial group structure on simpl. morphism sets https://nforum.ncatlab.org/discussion/3608/ 2012-02-28T23:48:11-05:00 2012-03-14T23:22:44-04:00 Mirco Richter https://nforum.ncatlab.org/account/378/ Is the set of natural transformations between two simplicial (abelian) groups a simplicial group or a chain complex?

Is the set of natural transformations between two simplicial (abelian) groups a simplicial group or a chain complex?

]]>
Internal Hom Cosimplicial objects https://nforum.ncatlab.org/discussion/3634/ 2012-03-03T20:28:21-05:00 2012-03-05T22:22:22-05:00 Mirco Richter https://nforum.ncatlab.org/account/378/ Is there a well defined internal hom for cosimplicial objects? (sets, algebras, rings)

Is there a well defined internal hom for cosimplicial objects? (sets, algebras, rings)

]]>
Number of morphisms in the Simplex Category https://nforum.ncatlab.org/discussion/3636/ 2012-03-04T19:30:18-05:00 2012-03-05T20:42:59-05:00 Mirco Richter https://nforum.ncatlab.org/account/378/ Simple Question: 1.) How many morphisms f:[n]&rightarrow;[m]f: [n] \rightarrow [m] are there in &Delta;\Delta ? ( Or equivalent: What is $|\Delta [m]_n |$ ? ) 2.) Is there a research ...

Simple Question:

1.) How many morphisms $f: [n] \rightarrow [m]$ are there in $\Delta$ ?

( Or equivalent: What is $|\Delta [m]_n |$ ? )


2.) Is there a research field in combinatorics that is concerned with monotonic integer maps from $[n]$ to $[m]$ (Just in case I have another ’combinatorical’ question concerning $\Delta$)

]]>
Alexander-Whitney and Eilenberg-Zilber in augmented grading notation https://nforum.ncatlab.org/discussion/3572/ 2012-02-17T07:18:57-05:00 2012-02-17T16:22:27-05:00 Mirco Richter https://nforum.ncatlab.org/account/378/ The definition of the Eilenberg-Zilber and the Alexander-Whitney map in the nLab entries(http://ncatlab.org/nlab/show/Eilenberg-Zilber+map) (http://ncatlab.org/nlab/show/Alexander-Whitney+map)are ... The definition of the Eilenberg-Zilber and the Alexander-Whitney map in the nLab entries

(http://ncatlab.org/nlab/show/Eilenberg-Zilber+map)

(http://ncatlab.org/nlab/show/Alexander-Whitney+map)

are given in the "standard simplicial dimension notation". However in the setting of abelian simplicial groups
and chain complexes we have frequently the situation where we work with augmented simplicial sets
and in that scenario there is the 'upshifted dimension counting' where we define the dimension of the augmented
simplex as zero instead of $(-1)$. (Explained for example in

http://ncatlab.org/nlab/show/simplex+category

My question is now how this affects the definition of the above maps and since I can't find anything on the web
I suggest to add such a augmented definition to the nLab entries on those topics.

If someone can post a link or something where this is worked out, I will change the entry if you people agree. ]]>
Kan simplicial Structure https://nforum.ncatlab.org/discussion/3512/ 2012-01-31T00:20:14-05:00 2012-01-31T13:38:25-05:00 Mirco Richter https://nforum.ncatlab.org/account/378/ Suppose we have the sequence of sets &Ropf;\mathbb{R}, &Ropf; 2\mathbb{R}^2, &Ropf; 3\mathbb{R}^3, … Is there a Kan simplicial structure on this sequence of sets, that is not ...

Suppose we have the sequence of sets $\mathbb{R}$, $\mathbb{R}^2$, $\mathbb{R}^3$, … Is there a Kan simplicial structure on this sequence of sets, that is not $n$-coskeletal for some $n \in \mathbb{N}$?

To be more precise, is there a simplicial set (functor) $R$ with $R([n]) = \mathbb{R}^{n+1}$ that is not $n$-coskeletal for some $n \in \mathbb{N}$?

And very closely related: is there a simplicial set (functor) $R$ with $R([n]) = \mathbb{R}^{n}$ (with $R())=\{0\}$), that is not $n$-coskeletal for some $n \in \mathbb{N}$ ?

]]>
Inductive Construction of Simplicial morphism sets https://nforum.ncatlab.org/discussion/3276/ 2011-11-07T02:08:42-05:00 2011-11-10T11:57:55-05:00 Mirco Richter https://nforum.ncatlab.org/account/378/ Suppose we have a simplicial set X and a m-truncated Kan simplicial set Y. Then how is it possible to construct Hom Simpl(X,Y)Hom_{Simpl}(X,Y) as a subset H&subset;Hom Set(X m,Y m)H \subset ...

Suppose we have a simplicial set X and a m-truncated Kan simplicial set Y. Then how is it possible to construct $Hom_{Simpl}(X,Y)$ as a subset $H \subset Hom_{Set}(X_m,Y_m)$?

Since Severa used this in his work on the n-jet functor (for X the nerve of the pair groupoid over an arbitrary set), it should be possible. Nevertheless I can’t find an explicit construction including a proof that what he constructed is indeed $Hom_{Simpl}(X,Y)$.

By an explicit construction I mean something like: Let $f \in H$ be given, then the appropriate simplicial morphism $F$ is given by $F[n]= X_n \rightarrow Y_n$ as follows : ??? where the commutation with the face and degeneracy maps is seen as follows ??? … On the other side we that any simplicial morphism is given that way, because ???

….

So if someone could give me a proof (I think it will be an induction on something like $Hom_{Simpl}(Sk^n X,Y) \subset Hom_{Set}(X_n,Y_n)$ or $Hom_{Simpl}(Horn_j^n X,Y) \subset Hom_{Set}(X_n,Y_n)$ ) it would be great.

Likely this doesn’t work for arbitrary simplicial sets X, so another topic is to find the appropriate conditions on X .

Moreover this should be put into the nLab, too…

If nobody knows a proof it would be nice, if we could work it out together. At the end I will take the time to put in the nLab. Unfortunately my skills on simplicial sets are not good enough, to do it by myself.

]]>
constructible https://nforum.ncatlab.org/discussion/2348/ 2011-01-04T20:33:28-05:00 2011-08-23T05:11:43-04:00 zskoda https://nforum.ncatlab.org/account/10/ I have created a stub for constructible universe. I did not go through the version of the definition via definability. Now constructible sets are sets in the constructible universe. The notion of ...

I have created a stub for constructible universe. I did not go through the version of the definition via definability. Now constructible sets are sets in the constructible universe. The notion of course, intentionally reminds the constructible sets in topology and algebaric geometry as exposed e.g. in the books on stratified spaces, on perverse sheaves (MacPherson e.g.) and in Lurie’s Higher Topos Theory. Now I wanted to create constructible set but I was hoping that there is a common definition for all these cases or at least logically defendable unique point of view, rather than partial similarity of definitions. I mean one always have some business of unions, complements etc. starting with some primitive family, say with open sets, or algebraic sets, or open sets relative strata etc. and inductively constructs more. Now, all the operations mentioned seem to have sense in some class of lattices. Maybe in Heyting lattices or at least in Boolean lattices. On the other hand, google spits out several references on constructible lattices *one of the authors is certain Janowitz), but the definition there is disappointing. I mean I would like that one has some sort of constructible completion of certain kind of a lattice and talk about the constructible elements as the elements of constructible completion. I am sure that the nLab community could nail the wanted common generalization down or to give a reference if the literature has it already.

]]>
Skolem https://nforum.ncatlab.org/discussion/2347/ 2011-01-04T16:29:20-05:00 2011-01-04T18:17:37-05:00 zskoda https://nforum.ncatlab.org/account/10/ I plan to write few foundations/set theory stubs including Skolem paradox. It will wait for a bit as the nnLab seems to be down at the moment. The entry forcing has phrase downward Löwenheim-Skolem ...

I plan to write few foundations/set theory stubs including Skolem paradox. It will wait for a bit as the $n$Lab seems to be down at the moment.

The entry forcing has phrase downward Löwenheim-Skolem theorem. What does it mean downward in this phrase ? Is it a modifier at all ?

]]>
Set* (pointed sets) and Set non-equivalence https://nforum.ncatlab.org/discussion/2189/ 2010-11-26T05:56:20-05:00 2010-12-01T02:13:00-05:00 xelxebar https://nforum.ncatlab.org/account/182/ Hello, This is my first post here at nForum, and I’m a bit unsure whether my question is appropriate here, so please let me know if it should be moved or deleted. However, I’m just beginning to ...

Hello,

This is my first post here at nForum, and I’m a bit unsure whether my question is appropriate here, so please let me know if it should be moved or deleted. However, I’m just beginning to study Category Theory on my own, using Adamek, Herrlich and Strecker’s “Abstract and Concrete Categories”. I’m having a bit of a stumbling block with one of the exercises and would like to discuss it with someone.

The exercise just asks to show that $Set \ncong Set_*$ where $Set_*$ is the category of pointed sets and $\cong$ is equivalence of categories. Could somebody provide me with a little direction? I’d rather work from a hint than receive an answer, but I know that’s sometimes difficult for these elementary problems.

]]>