This tag is for elementary questions on set theory - the sort of material covered in "Chapter 0" of graduate texts and in undergraduate set theory texts. Topics include intersections and unions, de Morgan's laws, Venn diagrams, relations, functions, countability and uncountability, power sets, ...

learn more… | top users | synonyms

11
votes
0answers
151 views

What does it take to divide by $2$ (or even $3$)?

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
41 views

There's no cardinal $\kappa$ such that $2^\kappa = \aleph_0$

I am trying to prove that a cardinal $\kappa$ such that $2^\kappa = \aleph_0$ . My attempt: We suppose it exists. Since $\kappa<2^\kappa$, in particular, $\kappa<\aleph_0$. But that implies ...
8
votes
0answers
197 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 ...
8
votes
0answers
106 views

Analogue of the term 'summand' for unions and intersections.

If we have a sum $\sum\limits_{i=1}^na_i$, we call the terms $a_i$ summands. In fact, in the cases of addition, subtraction, multiplication, and division, we have a large vocabulary to describe the ...
7
votes
0answers
96 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 ...
7
votes
0answers
144 views

Follow up on “Proof of $X \times X \hookrightarrow X$ implies $[X]^2 \hookrightarrow X$”

This is a follow up on this earlier question of mine. We have the following statements: (HSO) For every infinite set $X$ there exists an injection $f: X \times X \hookrightarrow X$ (HSU) For every ...
6
votes
0answers
82 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
170 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
118 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
79 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
195 views

Colored Picture for Equivalence Classes, Relations, Partitions, ..

Origin — A Book of Abstract Algebra — Charles Pinter — p120. I'm trying to sketch a colored picture for the ideas from equivalence classes, equivalence relations, partitions, etc... underneath. ...
5
votes
0answers
207 views

Questions on Answer to “The cardinality of the set of all finite subsets of an infinite set”

Would someone please enlarge on Arturo Magidin's original answer ? $1.$ Say the question didn't divulge $|S| = |X|$. Then how can $|S|$ be determined? Any intuition? I recast it below with more ...
5
votes
0answers
110 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
78 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
48 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
240 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
84 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
263 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
18 views

Is the limit of a recursive sequence of recursive ordinals itself a recursive ordinal?

Is the limit of a recursive sequence of recursive ordinals itself a recursive ordinal? If so, is there a nice proof of this?
3
votes
0answers
46 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
35 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
39 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
26 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 \ | \ i \in I \rangle $, where $I = \emptyset$? The family $\langle \mathbf{A}_i \ | \ i \in ...
3
votes
0answers
69 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
45 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
115 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 ...
3
votes
0answers
22 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
54 views

Interpretation of a tail event

I am currently reading about tail events wikipedia. And I was wondering: Where does the interpretation come from that events in this sigma algebra are independent from the behaviour of any finite set ...
3
votes
0answers
78 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
67 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
143 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 ...
3
votes
0answers
73 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
90 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
888 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
81 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
94 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\{ ...
3
votes
0answers
91 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 ...
3
votes
0answers
135 views

Semi-partition or pre-partition

For a given space $X$ the partition is usually defined as a collection of sets $E_i$ such that $E_i\cap E_j = \emptyset$ for $j\neq i$ and $X = \bigcup\limits_i E_i$. Does anybody met the name for a ...
2
votes
0answers
64 views

Counterexample to an implication

Denote $\bar{A}$ a complement of $A$ in a set $\Omega$ and $A \Delta B = A/B \cup B/A$ the symmetric difference of $A, B$. It is claimed that for a map $\phi := \Omega \rightarrow \lbrace 0, 1 ...
2
votes
0answers
50 views

Software to solve basic set equations (in algebra of sets)?

What symbolic math software is able to solve basic set equations? E.g. $X \setminus A = C \setminus X $, for $X$
2
votes
0answers
56 views

How do we know we have all subsets of a set?

The axiom schema of comprehension basically says that every definable subclass of a set is also a set. However, we know there are only countably many formulas in the language of set theory. So, this ...
2
votes
0answers
27 views

How to prove this statement $x \not\in D$ then $x \in B$

I am quite a beginner writing proofs, that's why I am asking such a simple question. I have an exercise: Suppose A\B ⊆ C ∩D and x ∈ A. Prove (by using proof techniques) that if $x \notin D$ ...
2
votes
0answers
82 views

Challenge on Some Definition on Formal Language & Recursive & Automata

We know set A is countable if A is finite or in a one-to-one mapping to natural numbers. Suppose $\Sigma$ be an arbitrary finite alphabet. I summarize my inference: a) Each arbitrary Language on ...
2
votes
0answers
33 views

Powerset of $A\times B$

$A = \{0,1\}$ and $B = \{1,2\}$, find $P(A\times B).$ And I found $A\times B = \{(0,1),(0,2),(1,1),(1,2)\}$ So if I wanted $P(A\times B),\text{would I do this:} \\ P(A\times B) = ...
2
votes
0answers
26 views

If $X$ is inductive, then, the set, $\{ x \in X \mid x $ is transitive and $ x \notin x \}$ is inductive.

Definition. We say that $A$ is an inductive set if $\varnothing\in A$, and whenever $x\in A$ then $x\cup\{x\}\in A$ as well. I am trying to prove the following exercise: If $X$ is inductive, ...
2
votes
0answers
32 views

function over countable union, intersection, etc

is it true that for a give function, or a linear transformation, $L$, in $\mathbb{R}^n$, if $S=\bigcup_{j=1}^\infty T_j$, then $L(S)=L(\bigcup_{j=1}^\infty T_j)=\bigcup_{j=1}^\infty L(T_j)$? What if ...
2
votes
0answers
56 views

Munkres Topology Exercise 2.q

I have another doubt regarding a question from Munkres' Topology (another one on cartesian products, sorry!). I have to determine if the following statement is true: $$(A\times B)-(C\times ...
2
votes
0answers
21 views

Set with relative complement forms partition

Prove that if $S$ is a set and $ \emptyset \subsetneq A \subsetneq S $ then $\Pi = \{A , S-A \}$ is a partition of $S$. Proposed Solution: Since $ A \subsetneq S$ , we have $S - A \neq ...
2
votes
0answers
76 views

Simple Proofs in ZFC Set Theory

So I'll keep this real short and simple. In this document on page 23 there is a list of axioms. On page 24 there is a list of theorems that come from said axioms. I can prove them all except 3 and 5. ...