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

0
votes
0answers
9 views

Notation for mimimal sum when choosing elements from two sets

I'd be grateful for any pointers on the following I am wondering if there is any standard notation (or neat suggestions) for the following. I have two sets $\{t_1, t_2, \ldots , t_k\}$ and $\{s_1, ...
2
votes
1answer
29 views

Intensional Set Defintions like $\{ x | A(y) \}$

Let $x = 1$. Is it valid to define sets like $Y = \{ x | 1 = 1 \} = \{ 1 \}$ and $Z = \{ x | 1 \neq 1 \} = \emptyset$? What I want to know: Are we allowed to define sets like $\{ y | A(z) \}$ where ...
1
vote
1answer
27 views

If each uncountable set $T$ has a countable subset, can we form $T$ by a union of countable subsets?

I was working my way through the set theory chapter in my Analysis textbook when I stumbled across these two theorems: Every infinite set has a countable subset A union of countable subsets ...
1
vote
1answer
28 views

Noetherian toplogical space exercise

Let $X$ be a noetherian topological space. Prove the following statements: (a) If $F \subset X$ is closed, then there exist $n \in \mathbb N$ and irreducible closed subsets $F_1,\ldots,F_n \subset ...
1
vote
1answer
24 views

Cardinal Arithmetic and a permutation function.

I am working on the following problem and am having difficulties getting started: We define a permutation of $K$ to be any one-to-one function from $K$ onto $K$. We can then define the factorial ...
1
vote
0answers
16 views

Noetherian topological space problem

Problem Show that the following statements are equivalent: (a) $X$ is a noetherian topological space (b) Every family of non empty closed subsets of $X$ has a minimal element. (c) If $$U_1 \subset ...
2
votes
1answer
33 views

Existence of a Set Function Axiom of Choice

I have the following problem. Let $A$ be a set and $B\neq\emptyset$ be a proper subset. Prove the existence of a function $f:A\to A$ such that $f\circ f=f$ and $\text{im}~f=B$. In the case where $A$ ...
5
votes
0answers
72 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 ...
1
vote
2answers
43 views

Construction of a small but fat set? [duplicate]

Is it possible to find a subset $A$ of the real line $\mathbb R$ such that the Lebesgue measure of $A$ minus its interior is positive ?
2
votes
4answers
40 views

Subsets $S$ such that $7 \notin S $ or $2 \notin S $

How many subsets $S \subseteq\{1,2...10\}$ are there such that $7 \notin S $ or $2 \notin S $? I can't find the right way to write a formal response. I think that we should consider at least ...
0
votes
1answer
20 views

Define the given set

Let $S_1$ and $S_2$ denote spheres of radii $1$ and $100$,respectively. Prove that the points on the surface of $S_1$ and those on the surface of $S_2$ are sets with the same cardinality. I don't ...
0
votes
2answers
36 views

How to show the surjectivity of $f(x)=x^5$ on $\mathbb R$?

Sasy $f:\mathbb R\to\mathbb R$ define by $f(x)=x^5$ This is definitely injective as $x_1^5=x_2^5 \implies x_1=x_2$ I say it is surjective because for all really $x$ there is all real $y$, $x \in ...
0
votes
1answer
46 views

Bridging the Gap Between Implicit Understanding and Formal Math

I use set theory on an implicit basis as a programmer; however, it's recently become necessary for me to expand into the formal world to explain my intent to decision makers that don't operate at a ...
0
votes
0answers
27 views

Intersection of Images of a function

I'm trying to understand intuitively why the image ( under some function ) of the intersection of subsets of the domain of that function is only contained ( and not equal ) to the intersection of the ...
0
votes
2answers
51 views

Cardinality problem: if $|A-B|=|B-A|$ then $|A| = |B|$

I was trying to prove the following question: 1. we need to prove that if $|A-B|=|B-A|$ then $|A| = |B|$. this is my answer so far: Case 1: $$A \cap B = \varnothing$$ In this case: $|A-B|= |A| ...
1
vote
0answers
25 views

Proof Verification: For $f: A \to B$ and $T \subset B$ show that $f^{-1}(T') = (f^{-1}(T))'$.

I want to know if my proof is correct and if the strategy I use should be used for all questions of this form. Compliments are taken with respect to the set $B$. My method of proof would be to first ...
-1
votes
0answers
22 views

Cartesian Product and Identity Function

Ok, I have this question: Why do you have the id,id repeated twice? Does it define function on a function of an element in the set 2 like id(id(a E 2))?
6
votes
2answers
394 views

Meaning of a set in the exponent

Let $ D = 2^\mathbb{N} $, i.e., D is the set of all sets of natural numbers. What's the meaning of this definition? Intuitively, I would suggest that $ D = \{1,2,4,...\} $ but the explanation ...
-2
votes
0answers
28 views

Let A = {0,1,2,3,4} and let B = P(A) (the power set of A). Which of the following are true and which are false? [on hold]

(a) 1∈A (c) {1}∈A (e) {1}⊆A (g) A∈B (b) 1∈B (d) {1}∈B (f) {1}⊆B (h) B⊆B My Attempt: (a) True (c) True (e) False (g) True (b) True (d) False (f) True (h) True
-2
votes
0answers
15 views

Let (A,≼A) and (B,≼B) be partially ordered sets. Define C = A×B and define the relation ≼ on C by (a,b)≼(a′,b′) ⇐⇒ (a≼A a′)∧(b≼B b′). [on hold]

Let (A,≼A) and (B,≼B) be partially ordered sets. Define C = A×B and define the relation ≼' on C by (a,b)≼'(a′,b′) ⇐⇒ (a≼A a′)∧(b≼B b′). (a) Prove that ≼' is a partial order on C. (b) Prove that if a ...
-2
votes
3answers
67 views

Proving $A \cap (B \cup C) = (A \cap B) \cup (A \cup C)$ [on hold]

Let $A, B, C$ be three sets. Prove that $A \cap (B \cup C) = (A \cap B) \cup (A \cap C)$.
2
votes
2answers
38 views

Following the Von Neumann definition of ordinal, why $V$ is not a set?

According to wikipedia (http://en.wikipedia.org/wiki/Ordinal_number#Closed_unbounded_sets_and_classes) (section "Von Neumann definition of ordinals"): "... every set of ordinals has a supremum, the ...
0
votes
2answers
59 views

Does the Cartesian product of an infinite family have all the elements we expect?

Given the axiom of choice, we know that the Cartesian product of an infinite family of non-empty sets is non-empty. However, this doesn't tell us whether the Cartesian product contains every element ...
0
votes
1answer
14 views

Is the function $|V_{\alpha}|$ normal?

Is the function $|V_{\alpha}|$, that is, the function that assigns to $\alpha$ the cardinality of $V_{\alpha}$, a normal function? I think it is but I am not really sure, please help. Thanks!
0
votes
0answers
46 views

Elementary Pigeonhole Principle Question

Is my reasoning here correct? If not, advice would be appreciated. Thank you for your time! We assume that $A$ is finite and $f: A \rightarrow A$. We show that $f$ is one-to-one iff $ran \ f = A$. ...
1
vote
1answer
50 views

Can one find uncountably many $T_x \subseteq \mathbb N$, any two of which have an empty intersection.

My question is this : Can one find uncountably many $T_x \subseteq \mathbb N$, any two of which have an empty intersection. I am currently reading an introductory text in Set Theory (Stillwell; The ...
1
vote
3answers
75 views

Number of images from $\mathbb{N}$ to {0, 1}.

Are the number of images from $\mathbb{N}$ to {0, 1} countably infinite or uncountably infinite? I was thinking of counting in base 2 to make a bijection between $\mathbb{N}$ and {0, 1}. So, a ...
0
votes
1answer
17 views

Report Comparing two Subsets against Aggregate

I have a report I'm writing which represents some customer 'worth' data. This subset (let's call it T) is broken down into two sub-categories ('A', and 'B'). The issue I'm having is my limited ...
2
votes
1answer
25 views

If $R$ and $R^{-1}$ are well orderings on some set S, then S is finite

I have been studying set theory of Herbert Enderton as I came about this problem in exercise section in chapter about ordinals. I have tried proving this using least upper bounds, pigeonhole ...
0
votes
0answers
20 views

Are sets evenly distributed under $\subset$? [duplicate]

I'm sure that this question is not meaningful at all, but i'm just curious whether there is a theorem about this. The question is: Let $X,Y$ be sets Let $f:X\rightarrow Y$ be an injection. ...
2
votes
1answer
63 views

Equivalence between “mathematical induction” and “transfinite induction” for natural numbers?

The "principle of mathematical induction" says that for a subset $S$ of $\omega$ (where $\omega$ is the set of all natural numbers), if $0 \in S$ and $n \in S \implies n^+ \in S$, then $S = \omega$. ...
1
vote
2answers
29 views

How does cf(cf $\alpha$) = cf $\alpha$?

Assume $\alpha > 0$ is a limit ordinal, and cf $\alpha=$ the least ordinal $\beta$ such that there is an increasing $\beta$-sequence $\langle \alpha_\xi \, \colon\, \, \xi < \beta\rangle$ that ...
3
votes
2answers
29 views

Set operations performed on functions

There's something I don't find intuitive about using set operations like 'union' and 'intersection' on functions. A function $f: X \rightarrow Y$ just pairs every element in the domain with a ...
3
votes
2answers
34 views

On the size of a non-empty family of non-empty sets such that every set in the family has a proper subset also in the family

Let $ F$ be a non-empty family of non-empty sets such that for every set $A \in F$ , $\exists $ a proper subset $B \subset A$ such that $B \in F$ . I can prove that every set in such a family $F$ is ...
2
votes
1answer
36 views

Is this a proper subset?

Let $A \cap C = \{1\}$ and $C = \{1,5\}$. Is it true that: $A \cap C = C$? For this to be true I know that they $A \cap C$ must be a subset of $C$ and $C$ must be a subset of $A \cap C$. So I found ...
1
vote
1answer
41 views

The operation $\langle a, b\rangle = \{\{∅, a\}, \{\{∅\}, b\}\}$ creates distinct sets from distinct pairs $(a,b)$

I understand the variant where $\langle a, b\rangle = \{\{a\}, \{a, b\}\}$, but I'm having trouble with the title problem. My strategy was to prove that $a = b = c = d$, however I ran into a problem ...
1
vote
1answer
23 views

Necessary that $A \cap M = \emptyset $ in $A\cup M \sim M$?

I have some notes that say $A \cap M = \emptyset $, $M$ infinite, $A$ countable implies $A\cup M \sim M$. Why is the intersection necessarily empty?
4
votes
2answers
84 views

Is the Least Integer Principle an axiom?

I'm really sorry if this question has been asked before, I looked but couldn't find anything. I'm going through an elementary number theory book and in the first chapter it introduces the least ...
1
vote
1answer
47 views

Bijection from $\mathbb{R}$ to the set of all infinite subsets of $\mathbb{R}$? [closed]

How to show that exists a bijection from $\mathbb{R}$ to set of all infinite subsets of $\mathbb{R}$ ?
2
votes
1answer
26 views

Is this relation symmetric

$R = \{(X, Y) \in \mathscr{P}(A)^2| X \subset Y \text{ and }X \neq Y \}$ I know that $(X,Y) \in R$ holds true since $X \subset Y$. However I'm unsure if $(Y,X) \in R$ since if $Y \subset X$ then ...
0
votes
3answers
39 views

Infinite set of natural numbers and the set difference

If we were to take $M \subseteq \mathbb{N}$, and $M$ has infinitely many elements, can the complement $\mathbb{N} \backslash M$ still be infinite? I'm guessing no, since the cardinalities of $M$ and ...
0
votes
2answers
26 views

Smallest member in a non-empty set of integers [closed]

I would like to prove that given a non-empty set of positive integers, it definitely contains a smallest member. Apparently, this is the well-ordering principle.
2
votes
3answers
36 views

What is the set with characteristic function $\chi_A(x) + \chi_B(x)-\chi_A(x)\chi_B(x)$?

Suppose that $A$ and $B$ are subsets of $X$ Find the subset $C$ whose characteristic function is given by: $\chi_C(x)=\chi_A(x) + \chi_B(x)-\chi_A(x)\chi_B(x)$ The answer given is ...
0
votes
3answers
33 views

Cardinality of cartesian product

I'm having issues getting my head around cartesian products and their cardinalities. $A = \{0, 1, \{2, 3, 4\}\}$ $B = \{1,5\}$ $D = B \times N$ (where $N$ is the set of natural numbers) The first ...
3
votes
4answers
104 views

Is there a bijection from a bounded open interval of $\mathbb{Q}$ onto $\mathbb{Q}$?

It is easy to create a bijection between two bounded open intervals of $\mathbb{R}$, such as: $$ \begin{align} f : (a,b) &\to (\alpha,\beta) \\ x &\mapsto \alpha+(x-a)(\beta-\alpha). ...
1
vote
1answer
33 views

Closure operator and topology problem

Statement If $c:\mathcal P(X) \to \mathcal P(X)$ is a closure operator on $X$, then the set $\tau=\{U \in \mathcal P(X) : c(X \setminus U)=X \setminus U\}$ is a topology on $X$. First let me write ...
0
votes
1answer
26 views

Is there a name for sum over one set divided by the cardinality of another set?

What is the summation of one set real numbers divided by the cardinality of another set called? $$A \subset\mathbb R$$ $$\frac{\sum A}{|B|}$$ I will try and be specific to my problem because I lack ...
1
vote
1answer
45 views

Is the subset relation on the powerset of a set, with qualification, reflexive?

I was wondering if the subset relation is reflexive? $R = \{(X, Y ) \in P(A)^2\mid X\subseteq Y \text{ and } X \neq Y \}$ I assumed they it was reflexive since for all $X \in P(A), X \subseteq X$ is ...
0
votes
1answer
38 views

is the probability of selecting a completely even family $\frac1{2^ n}$?

let $A$ be a set with $N$ elements, and for $0 \le M_{\mathfrak{B}} \le 2^n$ let $\mathfrak{B} =\{B_j\}_{j=0 \cdots M_{\mathfrak{B}}}$ be a a random variable whose value is a family of subsets of $A$, ...
-1
votes
2answers
33 views

Finding Domaing and Range

Can you please tell me how i am going to solve these? $R=\{(x,y)\in \mathbb R^2 | x^2=y^2\}$ $R^{-1}=?$ $R\circ R^{-1}=?$ $\text{dom} (R)=?$ $\text{range}(R)=?$ Thanks..