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

3
votes
1answer
52 views

What are the bounds (upper and lower) for $|A+A|$?

Let $A$ be a finite set of real (or complex) numbers. If I consider sets with small sizes, we have that: If $A$ is the empty set, then $A+A$ is also empty. If $A$ is a singleton, then $A+A$ is ...
1
vote
0answers
30 views

What is meaning of big U in sets? [duplicate]

What does big U below signify? And what is number written above and below it?
3
votes
2answers
21 views

Computing the union and intersection of family of sets

Suppose we are given for all $n \in \mathbb{N} $ $$ X_n = \{ (x,y) \in \mathbb{R} \times \mathbb{R} : n^2 \leq x^2 + y^2 \leq (n+1)^2 \} $$ I am trying to compute $\bigcup_{n \in \mathbb{N} } X_n $ ...
1
vote
1answer
29 views

Inverse Function in terms of Surjective and Injective Functions

Here is my intuition of the proof listed after The mapping of A to A is an inverse function. The mapping of A to B is injective and the mapping from B to A is surjective. I'm confused as to where ...
2
votes
1answer
30 views

Find the number of times K appears in any 4 item subset of T

Given the set T of all K {1, 2, 3, 4, 5, 6, 7, 8, 9} Let N be 4. There can be produced 126 combinations of N items, as subsets S. Every K has an equal ...
0
votes
2answers
17 views

Trying to prove a set equality

Suppose $f:X \to Y $ is a map and let $A \subseteq X $ And $T \subseteq Y $. I want to show that $f^{-1} ( f(A)) \supseteq A $. Also, I want to show that $T = f( f^{-1} (T)) \iff T \subseteq Im f $. ...
1
vote
1answer
48 views

A question on the generalization of Cartesian Product

In Halmos’s Book, it is written that, The notation of families is the one normally used in generalizing the concept of Cartesian product. The Cartesian product of two sets $X$ and $Y$ was defined ...
0
votes
1answer
32 views

Set operations on $A$ and $B$

I am a bit confused right now, in one of the practice questions for my book it says $$A,B \subset X$$ $$B = A \cup ((X \setminus A) \cap B)$$ However, when I simplify it, I get that it equals $$A ...
1
vote
1answer
23 views

Question about methods of proof (Elementary Set Theory)

I have a question in regard to some questions I am working on in beginner set theory. I will give an example to illustrate by question better, For example, say we were wanting to prove $$A \cup(B ...
1
vote
1answer
21 views

$S(\Omega \sqcap A)=S(\Omega)\sqcap A$ Halmos Measure Theory

I'm having trouble grasping the proof of theorem E, section 5, chapter 1 in Halmos' Measure Theory. Let $X$ be a nonempty set, and $\Omega$ a family of subsets of of $X$. Given $A\subset X$, denote ...
2
votes
1answer
18 views

Proving or Disproving a function that is onto itself is one to one.

I'm having some trouble formulating a proof for this following problem: A is a finite set and f a function with f : X → X. Suppose that f is onto. Now Prove or Disprove: f is one to one. ...
0
votes
2answers
33 views

Set theory basics exam

I have a question about this, we had this on our exam. Let be $f:A \to B$ a function. Prove next statements or give an example against it. (i): if $A$ is countable, then $f(A)$ is also ...
1
vote
2answers
42 views

Examples of non-transitive sets.

What are some examples of non-transitive sets? I have conducted several searches on Google and also searched the math.stackexchange website. I have encountered intransitive sets before but cannot ...
0
votes
1answer
125 views

Set theory identity, can't derive it

I see the following step in a textbook, and I can't follow it, $A\cup(B\cup(C-D)-E)$ $=$ $(A\cup(B-E))\cup(C-(D\cup E)$ My progress from the LHS get stuck like this, $$A\cup(B\cup(C-D)-E)$$ ...
2
votes
0answers
35 views

Proof of a lemma needed for proving a second result

So i have a question that i have to prove, but in order to prove it i need to prove the following lemma. It is a typical set theory sort of lemma, so i feel the proofs are almost complete, but ...
1
vote
1answer
38 views

Preimage of a closed set is a closed implies f is continuous. Some concerns about the proof

Ok. I have managed thru: If f is continuous then the preimage of open set is a open set If the preimage of the open set is a open set then f is continuous If f is continuous then the preimage of a ...
7
votes
1answer
41 views

Continuity $\iff$ Preimage is closed whenever set is closed

I'm trying to do the following: Prove that a function $f : S\rightarrow T$ between two topological spaces is continuous iff $f^{-1}(C)$ is closed whenever $C\subset T$ is closed. To show that ...
0
votes
2answers
37 views

simplify an expression to include only union and intersection

simplify:$$ (A\cup B)\cap (B\cup C\cup D)\cap(B\cup C\cup D') $$ the end result should only have one $\cup$ and one $\cap$ symbol. a bit confused on how to start. I think we can use the ...
2
votes
3answers
40 views

Cardinality of the set of automorphisms of $(\mathbb{N},+)$

I wonder if the set of bijections $\sigma\,:\mathbb{N}\to\mathbb{N}$ that satisfy $$ \sigma(a+b) = \sigma(a)+\sigma(b)\qquad \forall a,b\in\mathbb{N} $$ is countable or uncountable. What if we also ...
0
votes
1answer
31 views

what does the set $0 < x_{1} < x_{2} < 1 $ mean?

How do I interpret the set $ S = \{ (x_{1}, x_{2}) \space \big| \space 0 < x_{1} < x_{2} < 1 \} $ ? How do I plot the set on a $2$ dimensional graph?
3
votes
2answers
45 views

Representing rational numbers on a number line

Though the cardinality of the set of natural numbers is the same as the cardinality of the set of rational numbers, when one looks at a number line this fact seems counterintuitive, since between ...
0
votes
3answers
72 views

Union of countably many sets is uncountable implies at least one of them is uncountable

Suppose that we have an unountable set. If it is written as the union of countably many sets, this should mean that at least one of these sets is uncountable. I think that this intuitive statement ...
0
votes
0answers
18 views

Question about the sums of the entries in an infinite array

Imagine you have an infinite array of numbers. You can divide this array in columns with labels of opposite signs that go to infinity and negative infinity starting from the center of the array. Each ...
26
votes
8answers
2k views

Is symmetric group on natural numbers countable?

I guess it is too difficult a question to ask about the cardinality of $S_{\mathbb{N}}$ so I would like to ask whether it is countable or not. I tried to prove it is uncountable somewhat mimicking ...
-2
votes
3answers
29 views

Composition of an injective and surjective function [closed]

Is the composition of injective and surjective function bijective? Why?
0
votes
1answer
38 views

Provide a counter example to the claim that "for every set S, if ∅∈P(S) , then ∅∈S

Provide a counter example to the claim that "for every set S, if $\emptyset\in P(S)$ , then $\emptyset\in S$ This is a false statement but I don't know the counter example of it. What could be the ...
1
vote
0answers
31 views

Subsets, bijections

Let $A, B, C$ be sets with $A \subset B \subset C$. Also, let $f : C \to A$ be a bijection. Prove that $\# A=\# B$. I know that I have to find a bijection $g : B \to A$, but I don't have a clue how ...
1
vote
0answers
25 views

Why Is This Step Needed in Proving Bernstein-Schroeder?

Link to Original Text My question is in the lemma: If $f: A \rightarrow B$ is injective, where $B \subset A$, then there is a bijection between $A$ and $B$. The author commented that, with $Y = ...
0
votes
1answer
22 views

Does $f(X \setminus A)\subseteq Y\setminus f(A), \forall A\subseteq X$ imply $f$ is injective ?

I know that if $f:X\to Y$ is injective then $f(X \setminus A)\subseteq Y\setminus f(A), \forall A\subseteq X$ . Is the converse true i.e. if $f:X \to Y$ is a function such that $f(X \setminus ...
0
votes
2answers
50 views

What is the cofinality of $2^{\aleph_\omega}$

There is a similar question in this site but I am not satisfied with the answer, which is basically the same as the proof in the mentioned textbook. The book(Karel Hrbacek&Thomas Jech, ...
1
vote
1answer
31 views

Listing elements from set-builder notation, and vice versa

I have trouble translating from a set-builder notation to a "dotted set" $$\{\ldots,v_1,v_2,v_3,\ldots\}$$ and vice-versa. Set-builder to dotted set: $$\begin{align*} A &= \{5a+ 2b : a,b \in ...
1
vote
1answer
12 views

Notation to express that set is a relation on certain sets

Is there any specific notation to express that a set R is a relation between X and Y, or a relation on Z? I currently express that as R $\subseteq$ X x Y and R $\subseteq$ Z x Z in terms of subset, ...
3
votes
0answers
31 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 ...
1
vote
3answers
40 views

Prove: $\lbrace A_r : r \in \mathbb{R}\rbrace$ is a partition of $\mathbb{R} \times \mathbb{R}$

Given the following: For each $r \in \mathbb{R}$, let $A_r = \lbrace(x,y) \in \mathbb{R} \times\mathbb{R} : x - y = r\rbrace$ Prove: $\lbrace A_r : r \in \mathbb{R}\rbrace$ is a partition of ...
1
vote
2answers
49 views

Axiom of choice confusion: what does it mean an element to have no distinguishing features?

I'm trying to understand the axiom of choice, but am stuck on this point: How can an element of a set ever have no distinguishing features? Two things which are identical are the same thing - surely? ...
0
votes
1answer
18 views

What is the established algebraic form for interleaving or zipping a pair of equal length sets?

I am interleaving elements from two sets, A and B, of equal length. What is the most well established way of presenting this, algebraically? This is what I have: $$ (x,y) \forall x,y \in A,B $$ I ...
2
votes
1answer
37 views

Categorical sum of maps

I was reading that the product and the sum of two open maps are again open (and the sum of closed maps is closed too). Since the product of ${\rm id} : \Bbb R \to \Bbb R$ with itself is not open, I ...
12
votes
3answers
196 views

Generalization of $f(\overline{S}) \subset \overline{f(S)} \iff f$ continuous

A common characterization of a continuous function $f: X \to Y$ is that for any $S \subset X$, $f(\overline{S}) \subset \overline{f(S)}$. Similarly, closed maps are such that $f(\overline{S}) \supset ...
0
votes
1answer
27 views

L is countable set on a number line, then K=R\L is

L is countable set on a number line, then K=R\L is: a) K has interior point b) K has exterior point c) K has isolated point d) K has boundary point e) all statements are false A good approach is to ...
1
vote
1answer
38 views

A different approach to prove Distributive Properties

Is there any wrong with proving it like this (instead of proving it with logic arrows). Q: Prove that $(A \cup (B \cap C)=(A \cup B) \cap (A \cup C)$. Ans: If $\ x \in A \cup (B \cap C)$ is true. ...
0
votes
2answers
62 views

why is $(0,1) \subseteq$ $\mathbb{R}$ \ $\mathbb{N}$

why is $(0,1) \subseteq$ $\mathbb{R}$ \ $\mathbb{N}$ Sorry it seems very simple but can't get my mind to understand why, I feel like $\mathbb{R}$ \ $\mathbb{N}$ = {all negative numbers and ...
2
votes
1answer
43 views

Prob. 6 (c), Sec. 10 in Munkres' TOPOLOGY, 2nd ed: Set of elements having no immediate predecessors in the minimal uncountable well-ordered set

Let $S_{\Omega}$ be the minimal uncountable well-ordered set. Let $X_O$ be the subset of $S_{\Omega}$ consisting of all elements $x$ such that $x$ has no immediate predecessor. Then how to show that ...
0
votes
2answers
58 views

Proof that $|\mathbb{R}|=|\mathbb{R}^2|$

Theorem 3 of the chapter "Sets, functions, and the continuum, hypothesis" in the book "Proofs from the book", says that the set $\mathbb{R}^2$ has the same size of the set $\mathbb{R}$ and as a proof ...
0
votes
1answer
45 views

Operations on sets, parenthesis difference?

![enter image description here][1]I pretty much know how operations on sets work and I do have idea how to mark them on an axis but i find this a little different so if somebody could explain that to ...
1
vote
2answers
24 views

unclear why subset of a lexicographic ordered set of strings is said NOT to have a least element.

I am watching an excellent series on Discrete Mathematical Structures from IIT At the 47:33 mark of the video the instructor constructs a set of strings as ...
2
votes
1answer
45 views

Some basic set theory proofs.

Are these proofs correct? I felt really bad because I felt that I have only written a bunch of garbage just to restate the obvious rather than proving anything. (I am not very used to the mentality in ...
0
votes
3answers
30 views

If I use an element chasing proof, can I prove the identity of two sets false by proving the negation of that identity?

For example, if A=(B∖C) is true, the following are true: ∀x(x∈A→x∈B∧~x∈C) ∀x(x∈B∧~x∈C→x∈A) (A=(B∖C) is just an arbitrary example; I don't really know its truth value) But this sounds really just ...
0
votes
2answers
60 views

Proof of a exercise problem from basic set theory

Can someone have a quick check of my answer. The textbook solution is very conversational, and it would help me out a lot to get a second opinion. Thank you! Q: Suppose $A \subset B$. Show that $B^c ...
0
votes
1answer
26 views

Prove that sets being equipotent is an equivalence relation

Let $X$ and $Y$ two subsets of $E$. We know that $X$ and $Y$ are equipotent, $X\sim Y$, if there exists a bijective function so that $f:X\rightarrow Y$. Proof that $\sim$ defines an equivalence ...
0
votes
1answer
32 views

Ordering relations smallest/minimal elements definitions

In How to Prove It: A Structured Approach, 2nd Edition, page 192, the author introduces the following definitions of smallest and minimal elements of partial orders: Definition 4.4.4. Suppose R is ...