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

1
vote
1answer
16 views

In general, are subsets of recursively enumerable sets recursive sets?

I recently became interested in the solution to Hilbert's tenth problem, in reading about the succession of results that lead up to the proof I came across the notion of recursive sets and ...
1
vote
1answer
16 views

Composition of Ordered Pair

I'm doing math exercises from a Computer Science book and I am confused as to how the following result (from the solutions manual) is obtained: Given the function f={(a,b), (a,c), (c,d), (a,a), ...
2
votes
1answer
35 views

Defining a partial order on $A\times B$, given partial orders on $A$ and on $B$

Let $(A,\preceq_A)$ and $(B,\preceq_B)$ be partially ordered sets. Define $C = A \times B$ and define the relation $\preccurlyeq$ on $C$ to be $(a,b) \preccurlyeq$ $(a',b')$ if and only if ...
0
votes
0answers
21 views

Subset of a finite set is finite: base step

We can prove by induction that any subset of a finite step is finite. But I am confused by the step "Observe first that all subsets of $\emptyset$ and $\mathbf I_1$ are finite", which I think is the ...
8
votes
1answer
60 views

Graphs with uncountably many vertices

Let $ \mathcal{H}$ be the class of all graphs with at most $ 2^{\aleph_0}$ vertices not containing a complete subgraph of size $ \aleph_1$. Show that there is no graph $ H \in \mathcal{H}$ such that ...
2
votes
1answer
58 views

Two Definitions of Infinite Cartesian Product

In my one of lecture notes, there are two definitions of infinite Cartesian product, and it reads that we can construct a unique bijection between them. One way to define an infinite Cartesian ...
-1
votes
2answers
41 views

Question regarding cartesian product

Suppose $\bigl\{(x,y)\mid x^2+y^2<1\bigr\}$ is a subset of $\Bbb R\times\Bbb R$, where $\Bbb R$ is the set of real numbers. Is the given set also the cartesian product of two subsets of ...
2
votes
3answers
261 views

Cardinality of the set of all two-element subsets of $\mathbb{N}$

Consider the set $\mathbb{N}$ of all natural numbers; we can assign each natural number a point on a single axis. Let $A$ be the set of all of these points; $A$ is a countable set (we can assign each ...
0
votes
0answers
12 views

Proof of a variation of Hausdorff maximality principle

Let ($A$, $\le$) be a partially ordered set and let $B$ be a totally ordered subset of $A$. Prove that $A$ has a maximal totally ordered subset $C$ such that $B \subset C$. I'm trying to prove this ...
5
votes
5answers
478 views

Why is that *any* union of open sets is open but only *finitely many* intersections of open sets is open?

I understand that when we talk about union of open sets, we introduce an index set which can be countable or uncountable. But could I not do the same for the intersection of open sets too?
0
votes
3answers
73 views

What is $X^{\omega}$ where $X$ is a set?

I fail to find a duplicate. If it exists, please link me in the comments and I will delete the question. In my recently bought topology book, they use $X^{\omega}$ where $X$ is a set. However, this ...
0
votes
1answer
36 views

What is the name of this property of relation?

What is the name of property of a binary relation $R$ that states that $\lnot(a\mathrel{R} b) \iff \lnot(b \mathrel{R} a)$ for all $a, b$?
0
votes
1answer
48 views

Finding the cardinality of $\{ X \subseteq \mathcal{P}(A) : |X| \leqslant 1 \}$.

Given that $|A| = m$, my task is to find the cardinality of the set $Q = \{ X \subseteq \mathcal{P}(A) : |X| \leqslant 1 \}$. Since this is an even-numbered exercise in the text I'm working through, ...
1
vote
2answers
52 views

Questions regarding Cantors' Theorem

The proof of Cantor's Theorem in the Wikipedia Article goes like this: Two sets are equinumerous (have the same cardinality) if and only if there exists a one-to-one correspondence between them. ...
0
votes
2answers
32 views

If a mapping and it's inverse are both one to one, then must the mapping be bijective?

If $\sigma$: $A$ $\rightarrow$ $B$ was a mapping which was one to one, and had an inverse $\sigma$$^{-1}$: $B$ $\rightarrow$ $A$ which is also one to one, then are they both bijective mappings? I'm ...
4
votes
1answer
41 views

How to prove the following defined collection is a sigma algebra?

Let $\mu$ and $\lambda$ be two measures on a $\sigma$-algbra $\mathfrak{F}$ on $\Omega$, such that $\mu (A)=\lambda(A)$ for any $A\in \mathfrak C$, where $\mathfrak C\subset\mathfrak{F}$ is a ...
0
votes
0answers
16 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
2answers
49 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 ...
2
votes
1answer
33 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
46 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
33 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 ...
2
votes
1answer
38 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
80 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
44 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
41 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
22 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
48 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 ...
1
vote
1answer
40 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
27 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
23 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
396 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? [closed]

(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
17 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′). [closed]

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
72 views

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

Let $A, B, C$ be three sets. Prove that $A \cap (B \cup C) = (A \cap B) \cup (A \cap C)$.
2
votes
2answers
39 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
61 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
50 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
76 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
19 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
21 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 ...
4
votes
3answers
35 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 ...