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

6
votes
0answers
107 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 ...
6
votes
0answers
57 views

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

If we have a sum $\sum_{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 various ...
6
votes
0answers
132 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 ...
6
votes
0answers
118 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 ...
5
votes
0answers
123 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
152 views

Help with Cantor Bernstein Theorem proof

Suppose $X,Y$ are sets such that $ \left| X \right| \leq \left| Y \right|, \left| Y \right| \leq \left| X \right|.$ Then $\left| X \right| = \left| Y \right| $ Proof: Let $f:X \to Y, g:Y \to X$ ...
5
votes
0answers
89 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
66 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
46 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
175 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
202 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
228 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
46 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
91 views

My proof of Bolzano's theorem

Before I read the proof of Bolzano's theorem from my Calculus book, I've tried to prove it myself. I will use the following lemma and the least upper bound axiom. [Lemma: Sign-preserving property of ...
3
votes
0answers
66 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
316 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
65 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
80 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 ...
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
89 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
150 views

A question about a passage in Just/Weese's Basic Set Theory

I have a question regarding the following passage in Just/Weese (p 192), $\mathbf{V}$ denoting the cumulative hierarchy: "But consider the following situation: Where in "($\beta$)" does the ...
3
votes
0answers
121 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
67 views

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

I am using the Cantor-Schroder-Beenstein Theorem to prove $f_\infty: A_\infty \rightarrow B_\infty$ is a bijection. The cases of $f_+: A_+ \rightarrow B_+$ and $f_-: A_- \rightarrow B_-$ being ...
2
votes
0answers
28 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
29 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
42 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
25 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
134 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
88 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
44 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
43 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
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
87 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
37 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
111 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
228 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
42 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
53 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 ...
2
votes
0answers
233 views

The recursion principle.

In the book that I read there is a exercise where we need to prove the recursion principle that is written in the next fashion. Proposition: Let $f: \mathbb{N} \times \mathbb{N}\rightarrow ...
2
votes
0answers
48 views

Do these union- and intersection-like operations have a name?

I have two sets of pairs, e.g: $$A = \{ (a, 1), (b, 2), (c, 3) \}$$ $$B = \{ (b, 12), (c, 13), (d, 14) \}$$ I also have two operators which match the first element of pairs and return a pair of ...
2
votes
0answers
81 views

How to denote the set of binary relations of which a particular ordered pair is a member?

Given a universe $U$ and two subsets $S$ and $T$ (also, both members of $U$), what is the name given to denote the set of all binary relations in $U$ where the ordered pair $(S,T)$ is a member? The ...
2
votes
0answers
67 views

“Let A be a set. We are able to quotient all possible well-orders over the set A.” What does this mean?

"Let A be a set. We are able to quotient all possible well-orders over the set A." This was the first line in the set-up of some exercises I have to do (which ask specific questions depending on ...
2
votes
0answers
48 views

Which assignment defines a bijection here? And what is its inverse? And why?

In order to make an argument given in A First Course in Modular Forms by Diamond-Shurman to count the cusps of $Γ_0 (N)$ in the context of modular curves more rigorous, I want to prove that there is a ...
2
votes
0answers
19 views

Semilattice of functions with meet as “common restriction”

Is there an established name for the operator $\bigwedge$ which takes a nonempty family $F$ of functions and returns their "common restriction": $$ \bigwedge F = f|_{\bigcap_{f_0, f_1 \in ...
2
votes
0answers
89 views

Images and preimages over a superstructure.

Consider a function $f : X \rightarrow Y$. We can define a sequence of functions $g_n : \mathcal{P}^n(X) \rightarrow \mathcal{P}^n(Y)$ by asserting that $g_0=f$ and that $$\forall A \in ...
1
vote
0answers
47 views

Power Set, Bijection Function, Equivalence Relation

Let $S$ be a set and $P(S)$ the power set of $S$. For sets $A,B⊆P(S)$, we say that $A \sim B$ if there exists a bijective function $f: A \rightarrow B$. Show that $\sim $ is an equivalence relation.
1
vote
0answers
23 views

The product of two rational Dedekind cuts

If $a,b\in \mathbb{Q}$ and $C_a$ and $C_b$ are both positive rational Dedekind cuts then $C_a\cdot C_b=C_{a\cdot b}$. First of all this is my definition of product: Let $r,s$ Dedekind cuts such ...
1
vote
0answers
29 views

Name of the “left” set on which a partial function $f\colon \mathbb N \times \mathbb N \to\mathbb N$ is defined

Given a partial function $f \colon \mathbb{N} \times \mathbb{N} \to \mathbb{N}$ Does the set: $$A = \{ x \in \mathbb{N} \mid \exists y \in \mathbb{N} \text{ such that } f(x,y) \text { is ...
1
vote
0answers
26 views

What does $^{(L)}K$ mean?

Let $K$ and $L$ be two sets. What does $^{(L)}K$ mean? Is it $\underbrace{K\times K\times\dots}_{\text{card L times}}$? I came across this notation somewhere and couldn't quite figure it out. Thank ...
1
vote
0answers
19 views

Under what conditions is there a common transversal?

Let $S = \{S_1,\dots,S_n\}$ and $T = \{T_1,\dots,T_n\}$ be two collections of finite subsets of $\{1,2,\dots\}$. A transversal for $S$ is a list of elements $s_1,\dots,s_n$, one coming from each ...