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

7
votes
0answers
140 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
88 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
129 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
46 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 ...
6
votes
0answers
146 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
153 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
98 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
36 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 ...
4
votes
0answers
70 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
47 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
199 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
208 views

Do any authors entertain a distinction between sets and subsets?

I sometimes like to entertain a distinction between sets and subsets, I'm curious as to whether any published books or articles (or even blogs!) advocate this kind of thing. If you know of a piece of ...
4
votes
0answers
240 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
19 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
61 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
50 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
130 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
52 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
74 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
388 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
74 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
93 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
90 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
125 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
42 views

Elementary set-theory question

Very basic problem, just wanted to be sure I did this correctly. The problem is "Show that $X-Y = X \cap \overline{Y} $". There was hint in the problem telling one to let our universe $U=X \cup Y$. ...
2
votes
0answers
44 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
57 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 ...
2
votes
0answers
15 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
58 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. ...
2
votes
0answers
37 views

Velleman's How to prove it. Partial order proof.

Theorem: Suppose that $R$ is a partial order on $A$, $B_1 ⊆ A$, $B_2 ⊆ A$, $x_1$ is the least upper bound of $B_1$, and $x_2$ is the least upper bound of $B_2$. Prove that if $B_1 ⊆ B_2$ then ...
2
votes
0answers
31 views

Stuck on set theory question

Let $E$ be a set, let $A_1,\ldots A_n$ be subsets of $E$. Let $A=\{A_1,\ldots,A_n\}$. Note that $A$ is included in the powerset of $E$. Let $\dot A $ be the smallest subset of ...
2
votes
0answers
26 views

Is it always possible to get from a set to another inside the universe?

With an example: We have $C\cap (A\cup B)$. And we want to get to any other "state" (I don't know the actual term) by using set theory operations. Say we want to get to the blue area of $(A\cap B - ...
2
votes
0answers
33 views

Cardinal inequality: Show that if $\alpha, \beta, \gamma$ are cardinals and $\beta \leq \gamma$ then $\beta^{\alpha} \leq \gamma^{\alpha}$.

Show that if $\alpha, \beta, \gamma$ are cardinals and $\beta \leq \gamma$ then $\beta^{\alpha} \leq \gamma^{\alpha}$. I got it all confused when I tried constructing an injective function... Can you ...
2
votes
0answers
29 views

Did I prove in correct process?

The question is "prove that if g of f is 1-1, then f is 1-1." Did I prove it correctly? If not, what is wrong?
2
votes
0answers
137 views

Maximum and minimum values of intersection of sets

I know how to do this problem, but my question is more on the proving the inequality and the extreme values. So here is the problem: Of the 24 students in a class, 18 like to play basketball and 12 ...
2
votes
0answers
46 views

Is there an isomorphism between $\{\frac{m}{2^n}:m,n \in \mathbb{N} \text{ and } m < n\}$ and $\mathbb{Q}$

The middle thirds removed in the formation of the cantor set have a natural ordering. I'm trying to show that we can find an isomorphism between these and the rational numbers with the usual ordering. ...
2
votes
0answers
26 views

Selecting a unique pair satisfying a condition $\varphi$ with an ordering

Given a finite structure $\mathfrak{A}$ with Universe $|A| < \infty$ and signature $\tau$. We say a pair $(a,a') \in A$ satisfies a $\tau$-formular $\varphi$ iff $$ \mathfrak{A} \models ...
2
votes
0answers
196 views

Elementary Set Theory - Questions from final exam, check my answers

Yesterday I had my final exam in set theory, while I think it went pretty well, I'd like to doublecheck my answers, just so I could sleep at night. Would greatly appreciate any input. Question ...
2
votes
0answers
97 views

Relation between sets on a semi-rings

How can one given rectangles a union of disjoint rectangles in $\Bbb R^{n+1}$(more specifically in $\mathcal J^n $ ): $\bigsqcup_{j \in \Bbb{N}}I^{n+1}_j=\bigsqcup_{j \in \Bbb{N}}(I_j^1 \times I_j^n)$ ...
2
votes
0answers
46 views

Set Theory - Well Order (Lexiographical combination)

Question: Prove constructively that if $(A_{1},\prec_{1})$ and $(A_{2},\prec_{2})$ are two well-ordered sets then their lexicographical combination $(A_{1} \times A_{2},<_{1,2})$ is also well ...
2
votes
0answers
48 views

Given a sequence and find the smallest natural number s.t.

The question itself comes from a daily life problem which I think could take a large wall of text to explain. Unfortunately, I don't have any clue about this question and I'm also not sure how to ...
2
votes
0answers
68 views

Notation for unordered product of sets

Frequently, when referring to the edges of an undirected graph $G=(V,E)$, I want to write that $E \subset V \times V$, which isn't correct since the Cartesian product is ordered and the edges are not. ...
2
votes
0answers
49 views

proving $f^{-1}(C\cup D)=f^{-1}(C)\cup f^{-1}(D)$

I don't understand why I have to prove these: $f^{-1}(C\cup D)\subseteq f^{-1}(C)\cup f^{-1}(D)$ $f^{-1}(C)\cup f^{-1}(D)\subseteq f^{-1}(C\cup D) $ Why can't I do something like that: $x\in ...
2
votes
0answers
100 views

Hall's marriage theorem explanation

I stumbled upon this page in Wikipedia about Hall's marriage theorem: The standard example of an application of the marriage theorem is to imagine two groups; one of n men, and one of n women. For ...
2
votes
0answers
40 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} + ...
2
votes
0answers
158 views

Suppose $R$ is a relation on $A$ and $R^{-1}$ is the inverse. Proof or counterexample

Suppose $R$ is a relation on $A$ and $R^{-1}$ is the inverse. Give a proof or counterexample for each of the following statements. (a) If $R$ is reflexive, then $R^{-1}$ is reflexive. Let $x \in A$; ...
2
votes
0answers
321 views

Is this proof for the definition of the symmetric difference of two sets rigorous enough?

My real analysis text asks me to show that the symmetric difference of two sets $A$ and $B$ is given by $D = (A \backslash B) \cup (B \backslash A)$ In the second part of the question, it then ...
2
votes
0answers
50 views

Bell number with minimum bound on partition size

I know that the Bell number $B_n$ is the number of ways to partition a set of $n$ elements into distinct non-empty subsets. Is there a variant of this number that specifies the minimum number of ...
2
votes
0answers
56 views

Difference between defining a constant and beginning with it in a structure

For example, let's suppose that I have my structure $\langle\mathbb{R},+\rangle$ and that $\exists!x\forall a\in \mathbb{R}(a+x=x+a=a)$ as an axiom. In this case $0:=x$. But what if I consider the ...