This tag is for elementary questions on set theory, spanning topics usually found in introductory courses in set theory, in addition to review sections of graduate textbooks in the same field. Topics include intersections and unions, de Morgan's laws, Venn diagrams, relations, functions, ...

learn more… | top users | synonyms

39
votes
0answers
1k views

What does it take to divide by $2$?

Theorem 1 [ZFC, classical logic]: If $A,B$ are sets such that $\textbf{2}\times A\cong \textbf{2}\times B$, then $A\cong B$. That's because the axiom of choice allows for the definition of ...
8
votes
0answers
283 views

Is there an elementary introduction to higher order functions?

I am teaching a pre-calculus course (using the textbook by Michael Sullivan if it helps), and I realized that higher order functions seem to show up in with some frequency in pre-calculus and ...
7
votes
0answers
166 views

Cardinality of set of groups

After analyzing this question I started wondering. Thoughts. Everyone can give a simple example of a countable group $G, |G| = \aleph_0$ which has uncountable number $2^{\aleph_0}$ subgroups, for ...
7
votes
0answers
125 views

Name of a certain set

I want to know if there is any already-standard way to refer to the sets described as follows. For a set $X$, let $-X = \{-x: x \in X \}$; call it the negative of $X$. Take the set of all primes in ...
6
votes
0answers
175 views

Is there really anything wrong with Bourbaki's Set Theory?

Recently I have started reading Bourbaki's Theory of Sets on my own. Regarding one of the explanations of a concept when I went to a Professor of our college, he asked me why I was wasting my time ...
6
votes
0answers
189 views

Validity of my proof for a Cartesian Product in Tao's book

Before all, I'm apologize if my question is too common here. I'm only want to know if my proof is correct or need some adjustments. I'm reading the Terence Tao's Analysis book as I mentioned in my ...
5
votes
0answers
144 views

Show that it is an algebra.

This excercise is a little struggling for me. The part I need help with is showing that $D$ is closed under complements. Let $C$ denote the collection of all intervals on $\mathbb{R}$, including ...
5
votes
0answers
111 views

Tool that draws Venn diagram from subset relation

Is there a tool (LaTeX, JavaScript, Mathematica..) that allows one to draw Venn diagram automatically from subsets relations, e.g. $$A\subset A+B$$ $$A\subset C$$ $$C\subset C+D$$ $$B \not\subset ...
5
votes
0answers
126 views

The counted is to the countable as the ??? is to the (order)-isomorphic.

We sometimes need to distinguish the counted from the countable. A counted set is a set equipped with a particular bijection into (some of) the natural numbers; a set is countable if there exists such ...
4
votes
0answers
71 views

How to Prove It, Exercise 6.5.9

Suppose $R$ is a relation on $A$ and $S$ is the transitive closure of $R$. If $(a, b) \in S$, then there is some positive integer $n$ such that $(a, b) \in R^n$, and therefore by the well-ordering ...
4
votes
0answers
56 views

finding a bijective function from the real plane to the real line

As part of a HW assignment in the course elementary set theory, I was given the following question: Prove explicitly (don't use any theorems or known facts, but find a bijective function) that ...
4
votes
0answers
105 views

Axioms as recreational mathematics

Before modern group theory, mathematicians studied concrete permutation groups: algebraically closed subsets of the set of all bijections on a set $X$ in which all inverses was included. This was the ...
4
votes
0answers
196 views

Existence and uniqueness up to isomorphism of the real numbers from axioms

Pretty much what the title says: how does one prove the existence and uniqueness of the real number system from the ordered field axioms together with the least-upper-bound property (or maybe some ...
4
votes
0answers
156 views

Prove $f_\infty: A_\infty \rightarrow B_\infty$ is a bijection

Update: I was given some hints at how to approach this problem $A_\infty $ and $B_\infty$ are sets, not maps. (which is strange because there are function definitions coming into play here) The ...
4
votes
0answers
85 views

Linear dimension of banach spaces

Let $X$ be some vector space (over $\mathbb{C}$). Note that if $X$ is of finite dimension we can identify $X$ with $\mathbb{C}^n$ for some natural $n$ and endow it with a norm $||x||=|x_1|+...+|x_n|$. ...
4
votes
0answers
51 views

Metric-like families of relations

Let $X$ be an arbitrary set and to start with, let us consider a relation $\leq$ on $X$ (that is $\leq$ is a subset of $X^2$) which is reflexive and transitive. such a relation is called a preorder. ...
4
votes
0answers
297 views

Crititism of the set-theoretic definition of natural numbers

A while ago I read in a book (or a paper?) that a very well-known mathematician (Saunders Maclane?) in his lectures used to mock the classical set-theoretical definition of natural numbers: 0 = {}, 1 ...
4
votes
0answers
87 views

The Theory of Probabilistic Sets

${P}_m := \{ \Phi_{1m}, \Phi_{2m}, \ldots , \Phi_{nm} \}$ where $$|\Phi_{im} \rangle = \wp_{1m} | \phi_1 \rangle + \wp_{2m} | \phi_{2m} \rangle + \cdots + \wp_{km} | \phi_{km} \rangle$$ such that ...
4
votes
0answers
97 views

$\left(0,1\right]\neq\biguplus_{k=1}^{n}\bigcap_{j=1}^{k}G_{j},$ Proving elegantly

How can I show (without making many distinctions by cases) that the equality $$ \left(0,1\right]=\biguplus_{k=1}^{n}\bigcap_{j=1}^{k}G_{j}, $$ can't hold, if $G_{j}\in\mathcal{A}\cup\left\{ ...
4
votes
0answers
308 views

Sum of bijective functions

Can anyone please help me with this? Let $f,g_{1}, g_{2},\ldots,g_{k} \in \mathbb{Q}^{\mathbb{N}}$. $f$ is a sum of $g_{1},g_{2},\ldots,g_{k}$ if for every natural number $n$ $$f(n) = g_{1}(n) ...
3
votes
0answers
61 views

How can functions be written as ordered triples?

In a function $ \langle f,A,B \rangle $, I know that the domain $ A $ and the co-domain $ B $ are not restricted to being sets. They can be proper classes. In that case, how can we write functions as ...
3
votes
0answers
62 views

Proof check:$ \left | \mathbb{R} \right |= 2^{\left|\mathbb{N} \right |}$

This is my first time to post here. Sorry if this post is too simple or naive. Here I would like to prove that $\left | \mathbb{R} \right |= 2^{\left |\mathbb{N} \right |}$ I would first ...
3
votes
0answers
103 views

Is this a way to construct mathematics?(logic vs. set theory)

I recently asked a question about the fact that logic and set theory seems circular. link I got a lot of good and thoughtful answers, that probably explains everything, but I must admit I did not ...
3
votes
0answers
57 views

Why is this not a proof of Schroeder-Bernstein?

We can show that if $f: A \rightarrow B$ is injective then $|A| \leq |B|$ and if $g: B \rightarrow A$ is injective then $|B| \leq |A|$ so $|A| = |B|$. By the definition of having equal cardinality, ...
3
votes
0answers
37 views

How to generate families of sets without replacement symmetry?

I need to generate a family of sets with as few symmetries as possible. If convenient, let the size of each elements of the family be a fixed $s$ and the number of elements in the family be a fixed ...
3
votes
0answers
40 views

Writing some basic sentences in the language of set theory.

I am having some trouble proving that some basic sentences in the language $L_\in$ of first order set theory are $\Sigma_1$ or $\Pi_1$, the reason being that I do not know how exactly to write them. ...
3
votes
0answers
39 views

A reflexive relation?

Suppose I have a set $\mathrm{A}=\{1,2,3,4,5\}$ and a reflexive relation $\mathrm R$ defined on $\mathrm A$, i.e., $$R\colon A\mapsto A\quad\textrm{and}\quad \mathrm R\textrm{ is reflexive.}$$ Is ...
3
votes
0answers
35 views

Proving Equivalence Relation $xPy$ iff $ y = x + n\pi$ on The Reals

I am trying to prove that the relation P on $\mathbb{R}$ by the rule $\forall x, y \in \mathbb{R}, xPy \text{ if and only if } \exists n \in \mathbb{Z} \text{ such that }y = x+ n\pi$ From what I can ...
3
votes
0answers
51 views

Initial and final topologies

Suppose that $X_i$ are topological spaces, and $X_i \xrightarrow{f_i} Y$ are a family of maps into the set $Y$. The final topology on $Y$ is defined to be the finest topology on $Y$ such that each ...
3
votes
0answers
57 views

Looking for info on power set functor

I was reading here about the various functors which take a set $S$ to its power set. In particular, there is the normal contravariant one, and two covariant ones, which the article calls $\exists$ and ...
3
votes
0answers
53 views

Why is this not a poset after adding zero?

The problem    Consider the following set for divisibility. {1, 2, 3, 4, 6, 8, 12, 16, 24, 32, 96}. If 0 is added, the divisibility relation set will no longer be a poset. Please ...
3
votes
0answers
108 views

What are some examples of isotrophic sets?

What are some examples of isotrophic sets? and is there a "good" way to describe them? Isotrophic meaning that a random vector X uniformly distributed in the set has the isotrophic property for all ...
3
votes
0answers
74 views

Is it possible to create division via Set Theory?

I've been reading a book on Set Theory (Charles C. Pinter), and it says, ...set theory is recognized to be the cornerstone of the "new" mathematics... [emph. added] and that ...we can still ...
3
votes
0answers
58 views

an introduction to axiomatic set theory that is not enderton

So I've been reading Endertons Elements of set theory which is easy to understand when it comes to the essential axioms, but there are a number of topics which seem to gloss over important ...
3
votes
0answers
48 views

Topological proof for this set theory statement

Let $\mathcal{A}$ be an algebra of set (in a space $X$), such that any subcollection of disjoint sets in $\mathcal{A}$ is finite. Prove that $\mathcal{A}$ is finite. I already found a boring brute ...
3
votes
0answers
32 views

What is the product of an empty family of similiar algebras, that is $\prod\langle \mathbf{A}_i \ | \ i \in I \rangle $, where $I = \emptyset$?

What is the product of an empty family of similiar algebras, that is $\prod\langle \mathbf{A}_i \mid i \in I \rangle $, where $I = \emptyset$? The family $\langle \mathbf{A}_i \mid i \in \emptyset ...
3
votes
0answers
81 views

Can $\mathbb A=\{f(x)\mid x\in\mathbb R\}$ be shortened as $\mathbb A=f(\mathbb R)$?

Can $\mathbb A=\{f(x)\mid x\in\mathbb R\}$ be shortened as $\mathbb A=f(\mathbb R)$? I saw this notation in the IMO olympiad training materials (the solution to the Problem 16 (IMO 1999 Problem ...
3
votes
0answers
65 views

Cantor's theorem via non-injectivity.

The usual proof of Cantor's theorem proceeds as follows. Let $X$ denote a set and consider a function $F : X \rightarrow \mathcal{P}(X)$. Then we define $D \in \mathcal{P}(X)$ by writing $D = \{x \in ...
3
votes
0answers
33 views

Prove that $\operatorname{ran} f \subseteq \operatorname{dom} g \implies\operatorname{dom} (g \circ f)=\operatorname{dom} f$

Some preliminaries: A function $f$ is a binary relation such that $(x,y_1) \in f$ and $(x, y_2) \in f$ implies $y_1 = y_2$. $\operatorname{ran} f = \{y: \exists x$ such that $(x,y) \in f\}$ ...
3
votes
0answers
99 views

Countably infinite set and uncountable collection of subsets

How can I Prove or disprove that every uncountable collection of subsets of a countably infinite set must have two members whose intersection has at least 2010 elements?
3
votes
0answers
74 views

When can we have $(A+B)\cap C=A\cap C+B\cap C$?

With $A+B=\{a+b:a\in A, b\in B\}$ and any non-empty sets A,B,C. When can we have $(A+B)\cap C=A\cap C+B\cap C$? I am looking for the most general conditions (if any) such that the equality stands. ...
3
votes
0answers
41 views

Prove that for every 2 elements in the set F of all functions from N to N, there's an element in F that's bigger than both

let there be $\ F$ the set of all functions from $\ N \rightarrow N$. K is a relation on F, for every f,g$\in$F , (f,g)$\in$K $\leftrightarrow$ for all $\ n\in N$, $\ f(n)\leq g(n)$ Prove that for ...
3
votes
0answers
84 views

Proving the inclusion exclusion principle from the definition of the cardinality

I want to prove the inclusion exclusion principle: $|A\cup B| = |A| + |B| - |A\cap B|$ where $A$ and $B$ are finite sets. I proved the addition rule by contructing a bijection to a subset of ...
3
votes
0answers
110 views

Product of Summations for All Subsets

We have a set $X$ of $n$ integers $\{$$x_1$, $x_2$, .. , $x_n$$\}$, for which there are $2^n$ total subsets. The summation $s$ of a subset $X'$ is simply the sum of all integers present in $X'$, ...
3
votes
0answers
52 views

Prove that $f: \mathbb{N} \rightarrow \mathbb{N}-\left \{ 1 \right \}$ given by $f(x) = x+1$ is $1$-$1$ and onto

$f: \mathbb{N} \rightarrow \mathbb{N}-\{1\}$ given by $f(x) = x+1$ is $1$-$1$ and onto. Proof: ($1$-$1$) Suppose $f(x_{1}) = f(x_{2})$ for $x_{1}, x_{2} \in \mathbb{N}$. Then $x_{1} + 1 = x_{2} + ...
3
votes
0answers
2k views

Left inverse iff injective; right inverse iff surjective

For a function $f:A\to B$, the function $g:B\to A$ is called: a left inverse for $f$ if $g\circ f$ is the identity on $A$ (i.e., $g\circ f = {\rm id}_A$); and a right inverse for $f$ if ...
3
votes
0answers
100 views

Smallest ring containing collection of subsets

Given any collection $C$ of subsets of a set $X$, show that there is a smallest ring of sets $R$ containing $C$. (That is, $R$ has the property that it contains $C$, and any ring that contains $C$ ...
3
votes
0answers
95 views

How are algebras and rings of subsets generated in this paragraph?

From ncatlab What is missing is a simple description of the σ-algebra generated by ℬ. For a mere algebra, this is easy; any ℬ can be taken as a subbase of an algebra, the symmetric unions ...
2
votes
0answers
55 views

What's wrong with this proof of Schröder-Bernstein theorem?

In V. A. Zorich's Mathematical Analysis I there is an exercise to Analyze the following proof of the Schröder-Bernstein theorem: $(\operatorname{card} X \leq \operatorname{card} Y) \land ...
2
votes
0answers
38 views

Which are partitions are for $\mathbb{Z}$? Which are covers for $\mathbb{Z}$? Which are both or neither?

(a) {{x : x is an even integer}, {x : x is an odd integer}} (b) {{x : x is an even integer}, {x : x is divisible by 3}} Note - divisible by 3 includes negative integers, yes? -3, -6, -9, ... and ...