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
0answers
12 views

Define finite ordered set using nested tuples

My book on set theory has this exercise: Define n-tuples so that 1) $(a_0) = a$ 2) $(a_0, a_1,...,a_n) = ((a_0, a_1,...,a_{n-1}), a_n)$ for all $n \geq 1$ I don't understand what I ...
1
vote
0answers
23 views

how to show a function is bijection

I have taken two numbers $p$ and $r$ where $p,r\in A = \{0,1,\ldots,4i + 1\}$ where $i\geq 1$ and $q\in B = \{0,1,\ldots,n-1\}$. Let $X$ contains all elements obtained by cartesian product of $A$ and ...
1
vote
2answers
23 views

Measures: Sigma-Additivity vs. Continuity

Let $R$ be a ring of sets that contains the empty set and $\mu$ be a positive and finite set function on $R$. If $\mu$ is countable additive, then it is continuous from below and above: $$A_n\uparrow ...
0
votes
1answer
20 views

Notation of list expansion to a tuple

I have a set $S$ that I want to expand to a $|S|$-tuple. How is the notation for that? Currently I have something like that: $$ T = (f(x) : x \in S) $$ An example: $$ S = \{A,B,C\}\\ T = (f(A), f(B), ...
-1
votes
1answer
19 views

Sets and set operations [on hold]

Answer the following with short explanation. We consider a set $X$. Recall that P(X) is the power-set of X. 1) If the size of $X$ is 5, what is the size of $P(X)$? 2) If the size of $P(X)$ is 1024, ...
-4
votes
0answers
12 views

Let (A,≼A) and (B,≼B) be partially ordered sets. [duplicate]

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 ...
1
vote
2answers
20 views

Discussion on Measures: Sigma-Additivity

Disclaimer: Though this thread is written in a Q&A style any new thoughts are really welcome! What reasons are there to restrict measures to countable additivity rather than uncountable ...
0
votes
2answers
17 views

Reflexive relation without mentioning the set it is on

I read from my book something like this: Let $R \subseteq A^2$ be a binary relation. If $R$ is reflexive, then... Saying that some relation is reflexive without mentioning the set it is on ...
1
vote
1answer
788 views

Sets induction problem (complement of intersection equals union of complements)

Let $n\ge 2$ and $A_1,\dots,A_n$ be sets in some universe $S$. In this problem we will give a proof by induction of the identity $$\left(\bigcap_{i=1}^nA_i\right)^c=\bigcup_{i=1}^nA_i^c\;.$$ ...
3
votes
1answer
25 views

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

Can someone confirm my answers? (a) 1∈A (c) {1}∈A (e) {1}⊆A (g) A∈B (b) 1∈B (d) {1}∈B (f) {1}⊆B (h) B⊆B ================================================== (a) is true because 1 is an element ...
0
votes
1answer
26 views

Understanding Index Sets

Definition in Wolfram: "A set whose members index (label) members of another set." I was just trying to figure out what index and label actually mean. Thank You
3
votes
1answer
26 views

Direct proof of principle of transfinite induction

This is a problem from the book Set theory by You-Feng Lin. Principle of Transfinite Induction Let $(A,\le)$ be a well-ordered set. For each $x \in A$, let $p(x)$ be a statement about $x$. If for ...
2
votes
1answer
108 views

Multiple barber paradox

I'm having a little trouble formalizing the proof for this statement Suppose B is the set of barbers in a town who shave ALL those and ONLY those who DO NOT shave themselves I have to prove that the ...
0
votes
5answers
158 views

The set of all finite subsets of the natural numbers is countable

Could someone verify my proofs? Proposition: the set of all finite subsets of $\mathbb{N}$ is countable Proof 1: Define a set $ X=\{A\subseteq\mathbb{N}\mid \text{$A$ is finite} \}$. We can have a ...
16
votes
7answers
4k views

Show that the set of all finite subsets of $\mathbb{N}$ is countable.

Show that the set of all finite subsets of $\mathbb{N}$ is countable. I'm not sure how to do this problem. I keep trying to think of an explicit formula for 1-1 correspondence like adding all the ...
1
vote
1answer
51 views

Countable Set & Formal Grammar

We know set A is countable if A is finite or in a one-to-one mapping to natural numbers. I try to summarize my though. I think the following proposition is true. suppose $\Sigma$ is arbitrary ...
-1
votes
2answers
46 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 ...
3
votes
1answer
58 views

Sum of Neighborhoods of Zero

When do two neighborhoods of zero over a topological vector space add up as: $$aN+bN=(a+b)N\quad a,b\geq 0$$ I could imagine something like balanced might suffice... The problem is that I'd like to ...
-1
votes
1answer
31 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))?
2
votes
1answer
39 views

Equality of cardinality of $\mathbb{N}$ and $\mathbb{N} - \{0\}$

I have the sets $\mathbb{N}$ and $\mathbb{N}-\{0\}$. Clearly, $\mathbb{N}-\{0\}$ is a proper subset of $\mathbb{N}$, yet they have the same cardinality. That means that there exists a bijective map ...
1
vote
2answers
56 views

About well formed formula

Axiom of specification is schema because it talks about definite condition(or wff) which use notion of finite but this again we define from sets. But in logic we defined wff using consept of tuple and ...
0
votes
3answers
120 views

Proof that the set of all functions from $\mathbb N$ to $\mathbb N$ is not enumerable

I'm trying to show that the set of all functions from $\mathbb N$ to $\mathbb N$ is not enumerable. Can someone verify my proof below? Proof: Let $\mathcal{F}(\mathbb{N}; \mathbb{N})$ be the set of ...
1
vote
1answer
41 views

Why is the Kleene star of a null set is an empty string?

The articles and textbooks mention that, $\emptyset^\star = \{\epsilon\}$ The star operation puts together any number of strings from the language to get a string in the result. If the language ...
-3
votes
1answer
140 views

Is there a structure theorem for nonempty, compact, nowhere dense subsets of the real line? [closed]

Let $X$ be the set of all nonempty compact nowhere dense subsets of the real line. Is there a theorem that describes the form of the elements of $X$? Context For open subsets of the line, such a ...
-2
votes
2answers
98 views

How do i construct $C^\infty$?

I'm trying to define $C^\infty$ rigorously and i have a trouble with this. Mathematical Induction should be used, but i dunno where to apply this. I'm going to illustrate what i tried below: Before I ...
2
votes
1answer
24 views

Sum of combinations of the n by consecutive k

In a book, I found that the sum of combinations: $\binom{n}{k} + \binom{n}{k+1} +\cdots+ \binom{n}{n}$, where k starts from 0, equals $2^n$. It is possible to express this statement via sum: $2 + ...
1
vote
2answers
44 views

Prove an addition property of Natural numbers

Prove: For any $x,y \in \mathbb{N}, y \neq x+y$. I'm only suppose to use the Peano axioms as defined here http://aleph0.clarku.edu/~djoyce/numbers/peano.pdf and the properties of addition in ...
3
votes
1answer
51 views

What does $F = 2^W$ mean?

I'm reading the book Reasoning about uncertainty and having some problems with the notation. $F = 2^W$ where $W$ is a set and $F$ an algebra. What this mean?
1
vote
1answer
55 views

Regarding open subsets in topology

(Probably due to my lack of experience with the subject, I see that my question is horribly written. If you are to answer, a beginner-friendly explanation of the basis of a topology and the topology ...
0
votes
1answer
41 views

How to write the union of sets

This is just a question about notation(and I can not write it pretty well in Latex either). Is $X=(0,+\infty)\subset\Bbb{R}$ and $Y=\Bbb{R}$. Then $X\times Y= (0,+\infty)\times \Bbb{R} =$ ? ...
3
votes
4answers
49 views

Show $P\left(A-B\right)=P\left(A\right)-P\left(A \cap B \right)$

I'm trying to show that, given two events $A,B \in \Omega$ ($\Omega$ is a sample space): $$P\left(A-B\right)=P\left(A\right)-P\left(A \cap B \right)$$ I know $A-B = A \cap B^C$, but I don't know how ...
2
votes
3answers
72 views

Is this proof correct? Injective function $ f: A \rightarrow B \iff $ function $ g: B \rightarrow A $ is surjective

I've begun a course in "Real Analysis" recently and I have this trivial exercise. Could someone check if my proof is correct? Proposition: There exists Injective function $ f: A \rightarrow B \iff $ ...
23
votes
2answers
3k views

Cardinality of set of real continuous functions

The set of all $\mathbb{R\to R}$ continuous functions is $\mathfrak c$. How to show that? Is there any bijection between $\mathbb R^n$ and the set of continuous functions?
1
vote
1answer
21 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
21 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
63 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 ...
7
votes
1answer
81 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
59 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 ...
2
votes
3answers
263 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
24 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 ...
5
votes
5answers
490 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
0answers
14 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 ...
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 ...
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 ...
1
vote
1answer
43 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 ...
4
votes
1answer
42 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
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, ...
0
votes
3answers
76 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
38 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$?
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. ...