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

Maximum size of a poset chain

Let m,n ≥ 2. Consider the poset ({1,...,m}×{1,...,n}, ρ) where ρ is defined by (i,j)ρ(k,l) if and only if i ≤ k and j ≤ l. What is the maximum size of a chain in this poset? What is the maximum size ...
0
votes
0answers
23 views

Math challenge(Infinite sets): Bottles of Beer

Imagine a counter with stools that stretch across the room(infinite). All the stools are occupied. Two drunks come in and want to squeeze in to sit down. Drunk #1 walks in and tells the person on the ...
1
vote
1answer
19 views

Lexicographic product of chains is a chain

Let $A_i$ be a partially ordered set and $C_i$ a chain of $A_i$. Order $A_1\times A_2$ lexicographically. Prove that $C_1\times C_2$ is a chain of $A_1\times A_2$. This is a set theory proof ...
0
votes
2answers
25 views

Having trouble showing the cardinality of two infinite sets is the same

We just learned about Aleph-naught today and I read about it on wikipedia but I do not know how to go about solving this problem in my homework: Prove that N(natural numbers) has the same ...
0
votes
0answers
24 views

Beginner proof of image of functions and functions of sets

This is the third time I got my proofs handed back from my teacher. She won't tell me what's wrong except I have to redo it. I am running out of luck and I need help towards the right direction! The ...
0
votes
0answers
29 views

The limit of sequence of set.

When dealing with sequence of numbers, if $a_n\rightarrow a$, and for each $a_n$, we have $a_{n,j}\rightarrow a_n$, I think there exists a subsequence $a_{n,n_j}\rightarrow a$. What if we replace ...
1
vote
1answer
35 views

The set consisting of all surjective functions from R to R [on hold]

I'm trying to answer a question about elementary set theory. The question is: Find out if the set B of all surjective functions from R to R is equivalent to R or to R^R and prove your answer. Does ...
-3
votes
1answer
27 views

number of pairwise distinct subsequences [on hold]

Let be $(a_n)_{n \in \omega}$ be a sequence of real number such that $|\{a_n \colon n \in \omega \}|$ is infinite. How many pairwise distinct subsequences does $(a_n)_{n \in \omega}$ have? Can I ...
0
votes
1answer
33 views

Why the class of all inductive sets is not a set?

Page 66, Set Theory of - Herbert B. Enderton, Elements of Set Theory. It says "but the class of all inductive sets is not a set."
1
vote
3answers
14 views

Intersection of two sets that contain other sets as elements

How would the intersection of $A=\{a, b, e, \{a, b, c, d\}, \{d, e\}\}$ and $B=\{a, b, c, f, \{a, d\}, \{d, e\}\}$ be defined? I've searched quite a few books but no luck so far.
0
votes
2answers
36 views

Is there a straight-forward, “magic bullet” style way of showing $(\overline{X^\mathsf{c}})^\mathsf{c} = X^{\circ}$?

I would like to rigorously show that $(\overline{X^\mathsf{c}})^\mathsf{c} = X^{\circ}$, that is, the complement of the closure of the complement of X equals the interior of X. I am TAing a class ...
1
vote
2answers
37 views

What is the cardinality of $\bigcup_{n=1}^\infty\Bbb R^n$? [on hold]

What is the cardinality of the infinite union of R^n, that is n=1 to infinity? Also is there a generalization for arbitrary sets?
1
vote
2answers
28 views

Proving that $S_k = \{A \subset \mathbb{N} : |A| = k\}$ for $k\in\mathbb{N}$ is denumerable. [duplicate]

I am having trouble with this problem for quite some time. I posted this question before but I still can not figure out this problem. So far,from the suggestion of user134824, I have tried to define ...
0
votes
1answer
50 views

Proving that these two sets are denumerable.

(a) $S_k=\{A\subset\mathbb{N}: |A|=k\}$ for $k\in\mathbb{N}$ (b) $S = \bigcup_{k=1}^\infty S_k$ Work: For (a), I am not too sure about what approach I should use. I think finding a bijective ...
0
votes
1answer
27 views

Let S be the set of all reals where every other decimal place, starting with the first one, contains a 1.

(so, for instance, S contains 23.101816191... but not 0.123419...) (a) Show that the cardinality of positive integers is less than or equal to the cardinality of the set S (b) Is the cardinality of ...
0
votes
4answers
44 views

“$((A\times B) \to C)$” denotes what?

I'm having some trouble understanding notation. The question is For any three sets $A,B,C$ , $((A\times B) \to C) =_c (A \to (B\to C))$ Exactly what does "$((A\times B) \to C)$" denote? Is ...
2
votes
2answers
60 views

What does this set look like? [on hold]

Consider the set of points $A \subset \mathbb{Q}^2$ in the unit square with both coordinates rational: $$A=\{(x,y) \in \mathbb{Q^2} \mid \, 0 \leq x \leq 1,\,\, 0 \leq y \leq 1 \} $$ If we color the ...
0
votes
3answers
59 views

Prove that a set is not countable

Please note I'm new to all this - so can you explain it simply please. Really appreciate it I'm trying to prove that the set of all finite and countably infinite sequences over {0,1} is not ...
0
votes
1answer
27 views

Prove a statement for the infinite matrix

We are given infinite two dimensional matrix $\{a_{i,j}\}_{i,j=1}^\infty$. And we know that matrix contain only natural values and each number appears in the matrix exactly 8 times. Task is to prove ...
0
votes
3answers
33 views

What does $f: 2^{\mathcal{S}}\rightarrow\,\mathbb{R}$ mean?

A function $f: \mathcal{S}^n\rightarrow\,\mathbb{R}$ This is I understand. $x\in\mathrm{dom}\,f$ means that $x$ is a vector of size $n$ where its elements are taken from the set $\mathcal{S}$. ...
2
votes
1answer
37 views

Question about $\aleph = 2^{\aleph_0}$ proof.

I'm reading this proof from my course's book for the identity: $\aleph = 2^{\aleph_0}$ The proof starts with the claim: $2^{\aleph_0} \le \aleph \le 10^{\aleph_0}$. Then, since $2^{\aleph_0} = ...
2
votes
1answer
152 views

Why are the Animals in a Field a Set ? Why is a Group a Set ? What does Qualify as a Set?

A classroom conversation goes along the lines: Teacher: A is a set of animals in a field. S is a subset of A, the sheep in the field. B is a subset of A, the black animals in the field. The ...
0
votes
1answer
36 views

Reflexive for belonging ($\in$)

This question is related to the previous one I asked. @Brad proves in that answer that $A \notin A$ by considering the set $A = \{0,1\}$. What I don't understand in his proof that he takes a single ...
0
votes
2answers
36 views

Determining the cardinality of these sets.

I am having trouble with determining the cardinality(finite, denumerable, uncountable) of these two sets: The set of all circles in $\mathbb{R}^2$ in form $(x-a)^2+(y-b)^2=R^2$ with ...
4
votes
0answers
28 views

Prove that for every 2 elements in the set F of all functions from N to N, there's an element in F that's bigger than both

let there be $\ F$ the set of all functions from $\ N \rightarrow N$. K is a relation on F, for every f,g$\in$F , (f,g)$\in$K $\leftrightarrow$ for all $\ n\in N$, $\ f(n)\leq g(n)$ Prove that for ...
0
votes
1answer
36 views

How to simplify the expression $(E \cup F)\cap(E \cup F^{c})$?

$(E \cup F)(E \cup F^{c})$ Is the operator between the 2 parentheses implied to be an intersection, i.e, $(E \cup F)\cap(E \cup F^{c})$? In this case: $(E \cup F)\cap(E \cup F^{c})$=$(E\cap E\cup ...
1
vote
1answer
28 views

Show that $\mathfrak c +{\aleph_0}=\mathfrak c$ using “presenters”

I need to prove that $\mathfrak c +{\aleph_0}=\mathfrak c$ using "presenters". For example, in order to prove that $\mathfrak c +\mathfrak c=\mathfrak c$ We can show that: $$\mathfrak c =\left| ...
3
votes
2answers
31 views

Cardinality of the set of at most countable subsets of the real line?

I'm exploring an unrelated question about power series with complex coefficients. While exploring this question, I wondered: What is the cardinality of the set of all such power series? Or with ...
0
votes
1answer
24 views

How to show a quasi-order ~ on a set S with relation // induces a partially ordered relation?

Let ~ be the quasi-order relation. and let // be defined as the relation s~t and t~s(s,t elements of S). Show that ~ induces a partially ordered relation on the set of equivalence classes relation //, ...
2
votes
3answers
41 views

Cardinality of the set of all involutions from $\mathbb N$ to itself

The following is a section in my homework, I couldnt solve it so I'm asking for some help. I have the following set : $\{f:\mathbb N \to \mathbb N | f(f(a)) = a \text{ for all } a\in \mathbb N\}$. I ...
1
vote
1answer
51 views

Why $A\in A$ not reflexive

I have been reading Naive Set theory book by Holmes and it is stated that $A\in A$ is not true of any reasonable set and hence it isn't reflexive. Why isn't belonging ($\in$) reflexive ? I cannot ...
2
votes
1answer
48 views

Zorich's misinterpretation of “Axiom of Choice”?

I'm reading Zorich'es "Mathematical Analysis I", Ed 4, 2004, and wonder if this is a trifle misinterpretation of "Axiom of Choice". Ch 1.4 "Supplementary Material" says: 8°. (A x i o m o f c h o i ...
7
votes
1answer
88 views

First usage of the symbol ∈

Concerning a book [1] I am reading the symbol $\in$ was first used by Giuseppe Peano and is the first letter $\epsilon$ (epsilon) of the word ἐστί (means "is"). Does anyone know in which work of Peano ...
0
votes
1answer
17 views

Set Theory: Symmetric Relation

If relation S1 is symmetric, prove that S1 circle S1^(-1) is also a symmetric relation. (x,y)inS and (y,x)inS. Thank you for help!
0
votes
0answers
26 views

Axioms for Set Theory [duplicate]

I'm reading Zorich's "Mathematical Analysis I", Ed 4, 2004. Ch "1 .4 . 1 The Cardinality of a Set (Cardinal Numbers)" says: 3° $\forall X \forall Y (\text{card} X \le \text{card} Y) \vee ...
1
vote
1answer
37 views

Proving Limits of f(x) and f(a+h) are equal

The question asks me to prove that the equality of these two expressions $\lim_{x\to a} f(x)$ and $\lim_{h \to 0}f(a+h)$ provided their limits exist. My answer: Let $x=a+h$ so this $\lim_{h \to ...
-1
votes
1answer
20 views

denumerables: prove or disprove the following

Prove or disprove: a. if $A \subseteq B$ and A is denumerable, then B is denumerable. b. $J \cup K$ isdenumerable, where J is the set of all linear functions with slope 1 and retional y intercept, ...
1
vote
1answer
43 views

Proof identity for any function: $F(A) \cap B = F(A \cap F^{-1}(B))$

Let any number $y\in(f(A))\cap B$. We want to show that $y \in f(A \cap f^{-1}(B))$. Then $X \in A$ and $y \in B$. What should I do next?
1
vote
1answer
22 views

Question on Cardinality ..Help

a) Let $n$ be a positive integer. Define a relation on $\mathbb{Z} $, which yields a partition of $\mathbb{Z}$ with $n$ elements; and give the partition. b) Deduce that $n\omega = \omega$ where ...
0
votes
2answers
44 views

Proof : $A \subseteq B\Rightarrow C\setminus B\subseteq C\setminus A$

I have several of these types of problems, and it would be great if I can get some help.
1
vote
1answer
33 views

Proof strategy for $(<=)$: If $g \circ f = id_A$, then f onto $\iff$ g 1-1. [Chartrand 3Ed P239 9.72]

For nonempty sets A and B and functions f : A → B and g : B → A, suppose that $g \circ f =$ the identity function on A. $(♦)$ (e) $(<=)$ Assume that $g$ is one-to-one. Because $g$ is a ...
0
votes
1answer
33 views

Set notation of $S^1 \times S^1$

This is a simple question, but should this be written as: $\hspace{120pt}S^1 \times S^1 = \{(z_1,z_2)\in\mathbb{C}\times\mathbb{C}:|z_1|=|z_2|=1\}$
0
votes
1answer
17 views

Building an antichain in a finite poset

Given some finite poset $P$ we would like to find an antichain $A$ which intersects each maximal chain. How to do that? Note that each chain $C$ and each antichain $A$ intersects at one element as ...
1
vote
1answer
29 views

the depth of a set

The depth of a set X is the maximal number of nestings it contains. The definition runs as follows: if X contains no set, depth(X) = 0 otherwise ...
0
votes
1answer
41 views

Union of functions

Let $F=\{f(n)\ |\ f:\mathbb N\to\mathbb N\}$ I want to prove that for any $f,g\in F$, there is always an $h\in F$ that is different from $f$ and $g$, and is larger than both of them. I believe that ...
0
votes
4answers
29 views

operations on sets

Assume that the universe U is the set of all lower case letters alphabetically up to k, i.e. ...
2
votes
1answer
43 views

element or subset

My task is consider the set V = {b, d, f , g, {f , g}, {d, e, f} , {{d}, e} } R = {c, d, e, f , g} S = {f , g} T = {d} Classify each of the following statements as true or false. ...
0
votes
1answer
71 views

Are all uncountable infinities greater than all countable infinities? Are some uncountable infinities greater than other uncountable infinities? [duplicate]

I recently finished a discrete mathematics class, and near the end of the semester, the prof (very superficially) touched on countable and uncountable infinities. His explanation of countable ...
1
vote
2answers
31 views

Set difference of real numbers and rational numbers

If $\mathbb{R}$ is the set of real numbers and $\mathbb{Q}$ is the set of rational numbers,then what is $\mathbb{R}\setminus \mathbb{Q}$? The answer is irrational numbers. My question is the reason ...
2
votes
1answer
33 views

Commutative property in one object set

I have a question, If we have $A=\{1\}$, Can I say it's commutative? it demands at least two different objects? I think you can look at $(1,1)$ and say that $1+1$ is equal to $1+1$. Thanks!