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, (un)...

learn more… | top users | synonyms

1
vote
0answers
9 views

Explaining and Integral involving the Divisor Function

In a 1973 paper by Martinet, Deshouilliers and Cohen, $A(x)$ is defined as $$A(x)=\lim_{N\to\infty}\frac{\#\{n\leq N\mid \frac{\sigma(n)}{n}≥x \}}{N}$$ where $\sigma(n)$ is the "sum-of-divisors" ...
0
votes
2answers
29 views

Subtle difference between statemetns invloving negation in set theory.

What is the difference between the statements $x$ is not in an infinite number of sets $E_n$ and ...
0
votes
0answers
17 views

Relations, Ordered Pairs, Naive set theory by Halmos

I quote: "Explicitly: a set R is a relation if each element of R is an ordered pair;" The question is: "what about the converse? is a set of ordered pairs could be considered a relation?"
1
vote
2answers
22 views

which set is including $k$

$A=\{x^2+k \mid x \in \mathbb Z,-3 \leq x<k\}$, where $k$ is a constant. If $\{6,9\}\subseteq A$, then which set below includes $k$? $\{5x+1\mid x \in \mathbb Z\}$ $\{4x+3\...
-2
votes
1answer
42 views

Is ω really the first ordinal transfinity?

The Internet claims that ω is the first ordinal transfinity. But what about ω-1? Isn't that a ordinal transfinity, and isn't it before ω? Kind of like ω/2? I guess I lack an understanding of what ω ...
0
votes
0answers
13 views

Set notation for unordered cartesian product

In the question unordered cartesian product an shorthand notation for the unordered cartesian product was discussed but without any standard notation. So my question is what would be the explicit ...
1
vote
1answer
27 views

Proof-verification: $A\times B \subset C \times D \Rightarrow A\subset C$ and$B \subset D$.

I think I have a proof but Munkres' statement "assuming $A$ and $B$ are nonempty" is making me unsure. [EDIT to clarify: This statement is given twice, once without the "assuming nonempty" and once ...
0
votes
1answer
15 views

Finding equivalent statements with quantifiers

Find equivalent pairs: a. $\forall x(P(x)\land Q(x))$ b. $(\forall x(P(x))\land (\forall xQ(x))$ c. $\exists x(P(x)\land Q(x))$ d. $(\exists x(P(x))\land (\exists x Q(x))$ Are ...
1
vote
1answer
26 views

How do I formalize the topology generated by a subbasis?

The topology generated by a subbasis $\mathcal{S}$ is defined as the colection $\tau$ of all unions of finite intersections of elements of $\mathcal{S}$. I want to formalize $\tau$ as something ...
3
votes
4answers
58 views

Does this thing I'm calling 'the operationalization of $x$' have an accepted name?

Given a set $X$ and an element $x \in X$, we can turn $x$ into a function denoted $\tilde{x}$ as follows: for any set $Y$ and any function $f : X \rightarrow Y$, define $$\tilde{x}(f) = f(x).$$ For ...
2
votes
4answers
59 views

How do you prove that $p → q$ is equivalent to $p \lor q ↔ q$?

I gotta draw $p \lor q ↔ q$ from $p → q$, logically. not by a truth table. While it seems obvious, I cannot find a formal proof. This is how far I came up to: $\quad p \lor q$ $\equiv (p \land T) \...
2
votes
1answer
21 views

Prove that if $R$ is a symmetric, transitive relation on $A$ and the domain of $R$ is $A$, then $R$ is reflexive on $A$.

Assume, $R$ is a symmetric, transitive relation on $A$ and the domain of $R$ is $A$. $Dom(R)=A$ implies $(\forall x \in A)(\exists y \in A)[xRy]$. Since, $xRy$ is true it follows that $yRx$ is ...
3
votes
5answers
77 views

How are sets “detached” from their structure?

This question is best asked with an example. Consider the real numbers. However we construct the real numbers, the "final product" so to speak, is not just a set, but it is a complete ordered field. ...
2
votes
1answer
38 views

Describe the equivalence classes generated by T

Suppose $S = \{(x,y) \in \mathbb{R}^2\mid y = x + 1\text{ and } 0 < x < 2\}$. Question Describe the equivalence relation T on the real line that is the intersection of all equivalence ...
3
votes
1answer
41 views

Intersection of Compact sets Contained in Open Set

Just wanted to see if my proof of the following is valid: Let $\{K_i\}_{i=1}^{\infty}$ be compact sets (in some metric space), and let $V$ be an open set such that $$ \bigcap_{i=1}^{\infty} K_i \...
1
vote
2answers
22 views

Is there a faster way to determine partial orderings of basic finite sets?

For example, consider the set $S = \{ 0, 1, 2, 3 \}$, and the following relation on $S$: $$ R = \{(0,0), (1,1), (1,2), (1,3), (2,0), (2,2), (2,3), (3,0), (3,3) \}. $$ Obviously, I can go through ...
1
vote
2answers
31 views

Find an example such that $X$ with the lexicographic order is not well-ordered.

Let $\{A_n\}_{n\in\Bbb N}$ be a collection of well-ordered sets. $X$ is defined by $X=\prod_{n\in\Bbb N}A_n$. Find an example such that $X$ with the lexicographic order is not well-ordered. I know ...
2
votes
1answer
24 views

Intersection of a nested interval of $A_n=\left[3-{\frac{1}{\sqrt{n}},3+\frac{1}{3^n}}\right]$

$A_n=\left[3-{\frac{1}{\sqrt{n}},3+\frac{1}{3^n}}\right]$ What is $\bigcap_{n=1}^{\infty}A_n$ Since every set becomes a subset of the next set, is it correct to say that the intersection of all ...
0
votes
4answers
44 views

Find a counter example

The interior of the union is the union of the interiors. $\text{int}\left(A\cup B\right) = \text{int}(A) \cup \text{int}(B)$ I'm not too sure about to get started with this one. Any hints so as to ...
0
votes
1answer
24 views

Is $R$ an equivalence relation?

Let $X,Y$ be infinite sets. Define $F$ as $F=\{f:X\rightarrow Y\}$ . We define a binary relation $R$ on $F$: $fRg$ if there is no countable $S\subseteq X$ such that $\forall x\in S \ f(x)\neq g(x)$. ...
6
votes
2answers
200 views

Cardinality of the set of all infinite monotonically decreasing sequences of naturals

Find the cardinality of the set of all infinite monotonically decreasing sequences of naturals. I think it's $\aleph_0$. I marked this set in $A$, and said that $\forall n\in\Bbb N \ (n,n,n,...)\in ...
-2
votes
1answer
38 views

Are $(\mathbb R\times \mathbb Q, \le_h)$ and $(\mathbb Q\times \mathbb R, \le_h)$ isomorphic? [on hold]

Are $(\mathbb R\times \mathbb Q,\leq_h)$ and $(\mathbb Q\times \mathbb R, \leq_h)$ isomorphic? when "$\leq_h$" is the right lexicographic order? Thanks a lot!
4
votes
1answer
46 views

Why is the axiom of choice controversial? [duplicate]

In other words, what are the arguments for ZF over ZFC, and what philosophical issues have people raised against including it as a standard axiom of set theory?
1
vote
0answers
22 views

Formalization of an intuitive idea to construct a surjection

Let $A$ be an arbitrary set and $B$ be any non-empty set. Furthermore, suppose that there is no injection from $A$ to $B$. I want to prove that it follows that there is a surjection from $A$ to $B$. ...
0
votes
1answer
30 views

Set Theory Introduction [on hold]

what does it mean that a set is element of itself if a set is element of itself I must add it one element and then that set is not the old one so contradiction
1
vote
1answer
32 views

Cantor's diagonal argument: Prove that $|A|<|A^{\Bbb N}|$

Let $A_1\subseteq A_2\subseteq A_3\subseteq...$ be a raising series of sets such that $\forall n\in \Bbb N \ |A_n|\lt |A_{n+1}|$. We mark $A$ as $A=\bigcup_{n\in\Bbb N}A_n$. Prove that $|A|<|A^{\...
0
votes
1answer
76 views

Can $\bigcap_{B\in A}B=\emptyset$ Given that all elements of $A$ are inductive sets?

I am reading a course in mathematical analysis vol 1 by J.H. Garling. He defines a successor set as one that (1) contains $\emptyset$, and (2) contains $a^+$ whenever it contains $a$ (where $a^+$ is ...
0
votes
3answers
54 views

vacuous truth -> empty set is both included and not included in every set?

I understand the concept of vacuous truth and its use in showing that the empty set is a subset of every set. Based on my understanding of vacuous truth (for example https://en.wikipedia.org/wiki/...
3
votes
1answer
34 views

Boundary and Interior of set $\{-3,2,5\}$

I'm trying to see if I'm correctly understanding and applying the definition for interior and boundary points. Interior point: A point x in R is an interior point of S if there exists a ...
0
votes
0answers
20 views

How am I to understand this notation with regards to bdS and the int S? $S=\bigcap_{n=1}^{\infty}\left(-\infty,7+\frac{1}{n}\right]$

I'm trying to find the largest $\epsilon$ such that the neighborhood centered at $x$ of radius $\epsilon$ is contained in $S$. That part I think I can do, but I just don't know understand the below ...
2
votes
1answer
57 views

Olympic Problem about Theory of numbers.

Let $Y=\{1,2,\ldots, 2014\} \subset \mathbb{N}$. Find the maximal subset $A\subset Y$ such that, $$\forall x\in A,\quad x\not\mid\sum_{y\in A\setminus\{x\}} y.$$ Example, $A'=\{2,4,6,\ldots,2014\}\...
0
votes
1answer
30 views

How would I calculate the total number of combinations [on hold]

Lets say I have 4 lines or rows lets call them Row 1 .. Row 4 Now the total number of ways to delete the rows are: Row 1 (leaving Row2, Row3, Row4) Row 2 (leaving Row1, Row3, Row4) Row 3 Row 4 ...
0
votes
3answers
17 views

Prove that set of sequence of integers is countable if the sequence have a step of c

How would you prove that the set S of all infinite sequences $a_{1}a_{2}\ldots$ is countable given the condition that $a_{I+1}-a_{1}=c$ For example: ${10, 13, 16, \ldots}$ should be in the set S as $...
0
votes
2answers
35 views

The cardinality of all the infinite binary sequences that don't contain 010

Find the cardinality of all the infinite binary sequences that don't contain 010 I think it's $\aleph_0$. I marked the set all infinite binary sequences that don't contain 010 in A, and the set of ...
2
votes
1answer
34 views

Well-ordering principle and theorem

Could somebody clearly explain the difference between the well-ordering principle and the well-ordering theorem? Is one of these related to the Principle of Mathematical Induction, and the other to ...
1
vote
1answer
49 views

Formulating a problem in terms of set theory

Here is one problem I was trying to solve just by trial-and-error method. However, I was thinking about how to write the clear solution using set theory. Problem: A notebook contains exactly $100$...
1
vote
1answer
31 views

Reasoning informally about $\{x \in B \mid x \notin C\} \in \mathscr P(A)$

Attempting to apply more flexible, informal reasoning to predicate logic as demonstrated helpfully to me by another user in answer to my last question. $\{x \in B \mid x \notin C\} \in \mathscr P(A)$ ...
3
votes
1answer
19 views

Prove that $\text{Dom } (S\circ R) ⊆ \text{Dom }R $

Let $R$ be a relation from $A$ to $B$ and $S$ be a relation from $B$ to $C$. Suppose, $x \in \text{Dom }(S\circ R)$. Then, it follows that there $\exists y \in C$ such that $(x,y) \in S\circ R $. ...
3
votes
2answers
23 views

Rewriting $\mathscr P(\bigcup_{i \in I} A_i)\not\subset\bigcup_{i \in I} \mathscr P(A_i)$ in more fundamental terms.

Working through Velleman's "How to Prove It" and currently having a bit of difficulty with a problem where I'm asked to rewrite this: $$\mathscr P\left(\bigcup_{i\in I} A_i\right)\not\subset\bigcup_{...
3
votes
1answer
29 views

Commonplace sets

I recently started reading about sets of numbers, set builder notation, and operations on sets of numbers. To practice using different symbols (e.g., $\wedge$) and different set "layouts," I decided ...
2
votes
3answers
44 views

Understanding notation for the sequence definition

Looking for assistance in translating this definition into more laymen terms? In other words, can someone explain it to me like I'm a 5 year old? Definition. A sequence ($s_n$) is said to diverge ...
1
vote
2answers
33 views

Cardinality of subsets with finite intersections

Let $\ F_0 $ be a family of disjoint subsets of $ C$. $\ |C|= \aleph_0$. Prove that $\ (*) |F_0|\leq\aleph_0 $. This part was relatively simple, in the presence of choice an injection can be ...
0
votes
0answers
12 views

Chartrand Mathematical Proofs 3e Exercise 1.45

I'm self-studying this book to learn how to do proofs, I have previously studied Calculus 1,2,3 and Linear Algebra in college in the US. I have a problem with the following question: Exercise. 1.45 ...
2
votes
1answer
34 views

Existence of an inverse relation for $R \subseteq A \times A$.

I'm stuck with the following problem: Given the set $A = \{1,2,3,4,5\}$, construct a relation $R \subseteq A \times A$ such $$ R \circ R^{-1} = \triangle_A = \{(a,a) \hspace{5pt} | \hspace{5pt} a \...
1
vote
1answer
28 views

Proving that $A+B - (A \cap B) = A \cup B$ for binary integers

I hope computing questions are fine here. I'm trying to show that for all binary numbers $A$ and $B$, $A+B - (A \cap B) = A \cup B$. It's confusing me firstly because I'm not sure what the "set ...
1
vote
0answers
33 views

For each of the following sets, determine its cardinality (ω, 2ω, or something else) and prove that your answer is correct

(a) A1 = {f ∈ (ω → ω) : ∀n,m ∈ ω (n < m ⇒ f(n) < f(m))}. (b) A2 = {f ∈ (ω → ω) : ∃n ∈ ω∀m ∈ ω f(m) ≤ n}. (c) A3 = {f ∈ (ω → ω) : ∃n ∈ ω∀m ∈ ω (n ≤ m ⇒ f(n) = f(m))}. a) A1 = {f ∈ (ω → ω) : ∀n,...
4
votes
0answers
82 views

Every family $\mathscr{A} $ of sets satisfies $|\mathscr{A} \setminus \mathscr{A}| \geq |\mathscr{A}|$

Let $\mathscr{A} $ be a set of sets. Let's denote $\{A \setminus B : A,B \in \mathscr{A}\}$ by $\mathscr{A} \setminus \mathscr{A} $. The Marica-Schönheim theorem in combinatorics says that $|\...
0
votes
1answer
38 views

Assistance with finding the accumulation points for $(3,6) \cup (6,9]$

I'm having trouble digesting the definition of an accumulation point(s). Can you help me to understand it given the following: $(3,6) \cup (6,9]$ I know this produces the interior set $(3;9]\...
1
vote
1answer
52 views

Proving the Cardinality of a set in R

Let $\ A\subset R $ have the following characteristic: For all $\ a,b \in A$ , $\ \frac{a+b}{2} \notin A$. Prove that there exists a maximal set A. Prove its cardinality is $\ \aleph $. The first ...
2
votes
2answers
53 views

A 'bad' definition for the cardinality of a set

My set theory notes state that the following is a 'bad' definition for the cardinality of a set $x:$ $|x|=\{y:y\approx x\}$ $(y\approx x\ \text{iff} \ \exists\ \text{a bijection}\ f:x\rightarrow y )...