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
7 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
2answers
19 views

Cardinality of the set of all involutive functions

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
36 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
41 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
65 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
16 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
23 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
30 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
19 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
39 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
43 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
29 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
32 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
16 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
25 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
34 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
28 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
41 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
67 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
30 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!
1
vote
2answers
32 views

Conditions on the functions $f,g,h,k$ if $f(x)g(y)=h(x)k(y)$

I was working on this problem, and I thought I'd post my answer so people could see if they have a better one: Spivak Calculus, 4th ed., problem 3-18: Suppose $f,\,g,\,h,\,k$ are functions from ...
0
votes
1answer
14 views

Understanding Indexed Families

I'm having a terrible time trying to understand what indexed families are. I read the wiki here http://en.wikipedia.org/wiki/Indexed_family but I found it so confusing. Here's what I understood so ...
-1
votes
1answer
44 views

Find all relations from {1,2) to {x,y} . How many are functions?

Hi today I came across a question as stated above.I just started learning discrete mathematics though. The question said to find all relations from {1,2} to {x,y} .. Isn't it like ...
-1
votes
1answer
39 views

Cardinalilty of Complex numbers [duplicate]

Anyone can assist me finding the cardinality of Complex Numbers and some of its subsets under ZFC? and if we are to prove that if $\kappa$ is any uncountable cardinals, |$\omega \times ...
1
vote
1answer
45 views

The biggest number of possible sets created by $\setminus,\cup$ [on hold]

How many atmost sets can be created by $n$ sets by operations $\setminus, \cup$ .
2
votes
1answer
33 views

Ordinal addition is associative

We've been asked to teach ourselves a unit on ordinals for our final exam tomorrow, I grasp how to prove that certain ordinals are distinct but I am having trouble figuring out a proof to show ordinal ...
0
votes
1answer
26 views

When proving a partial order relation is a total order do we have assume both elements are distinct?

Consider the "divides" relation on the set $A=\lbrace 1,2,2^2,.\;.\;.,2^n\rbrace$, where $n$ is a non-negative integer. Prove that this relation is a total order on $A$. First we prove $A$ is a ...
0
votes
1answer
24 views

Equivalence Relations and distinct equivalence classes

$A=\lbrace(1,3),(2,4),(-4,-8),(3,9),(1,5),(3,6)\rbrace$. $R$ is defined on $A$ as follows: For all $(a, b)\;(c, d) \in A$, $(a, b) R (c, d) \iff ad=bc$ I know what they are asking but I cannot see ...
1
vote
2answers
35 views

How would I express the statement “Let H be a subspace of V” in mathematical notation?

How would I express the statement "Let H be a subspace of V" in mathematical notation? Does something like this work? $$ ( \ \ H(\mathbb{R})\subset V(\mathbb{R}) \ ) $$
0
votes
1answer
50 views

Proving a relation is transitive

I am trying to understand transitive relations. I understand given that a set may have $\{(a,b)(b,c)\}$ it must contain $(a,c)$ for it to be transitive. But for longer sets I am getting confused in ...
0
votes
0answers
49 views

Please give feedback to my answers (sets) [duplicate]

Prove or find a counter-example to the claim that for all sets $A, B,C$ if $A\cap B = B\cap C = A\cap C = \varnothing$ then $A\cap B\cap C \neq\varnothing$. Solution False. Let $A = ...
0
votes
0answers
18 views

A and B are sets. Prove that A=B iff P(A) = P(B) where P is the power set. [duplicate]

Since P(A) = P(B) P(A) is a subset is P(B). A is also an element of P(A). But since P(A) is a subset of P(B) A is almost an element of P(B) which means A is a subset of B. Can I do the same thing to ...
0
votes
2answers
30 views

Is there some kind of right distributivity of the subset predicate over set union?

$X \cup Y \subset Z \leftrightarrow X \subset Z \wedge Y \subset Z$. Is there a similar simple rule for $X \subset Y \cup Z$?
1
vote
2answers
44 views

Are these proofs valid? Which method of proof is better?

I want to prove that S ∪ (T ∩ V) = (S ∪ T) ∩ (S ∪ V) Here's 2 methods of proof, the first one I thought up, the second is from my notes: First method: a. S ∪ (T ∩ V) ⊆ (S ∪ T) ∩ (S ∪ V) x ∈ S ∪ (T ...
0
votes
1answer
27 views

Missing step in proof?

I was just looking over my notes and found that some steps, while obvious, seem to be missing in-between steps. For example: $$x ∈ S \land (x ∈ T \lor x ∈ V) \Rightarrow (x ∈ S \land x ∈ T) \lor (x ∈ ...
0
votes
0answers
38 views

How to prove that for finite, nonempty sets $A,B$ $|A \times B| = |A|\cdot|B|$

With $|A| = a$ and $|B| = b$, bijections $f : A \rightarrow [a]$ and $g : B \rightarrow [b]$ exists. I can't seem to take one definitive action for this problem. Are there inequality cases with $a$ ...
1
vote
1answer
29 views

How do you define computational complexity abstractly?

Let the problem we're studying be $f : X \to Y$. Say, I don't know what I want to define time-complexity with respect to, I just know I have a map $|\cdot| : X \to \Bbb{R}$, such that $|\cdot| \geq ...
0
votes
1answer
23 views

How to prove that a union of a countably infinite set and a finite set is countably infinite with no intersection [duplicate]

I can get my head around this thing... So I can find examples of this using reals and naturals, but the intersection of reals and naturals is naturals. Is there a way to prove that the union of a ...
0
votes
3answers
45 views

How to Prove that a set is uncountably infinite if through bijection

So I know that and know how to find a bijection between a set of infinite binary strings and its power set. I came to a first conclusion that there exists a bijection between set S={0,1}* and P(N). ...
-3
votes
0answers
31 views

Find an example of sets $A,B,C$ such that $A\cap B = B\cap C = C \cap D = \emptyset$ but $A \cap B\cap C \neq\emptyset$ [duplicate]

Find an example of sets A,B,C such that $$A\cap B = B\cap C= C \cap D = \emptyset$$ but $$A \cap B\cap C\neq\emptyset$$
0
votes
0answers
19 views

Equivalence classes of the form (a,b)

https://www.dropbox.com/s/q0w2vwwz5w1b0y8/sets.jpg I can do the proof and under b the class would take the form x=3m +2 and y=2n+1 I know that I need to find the equivalence classes (0,0), (1,0), ...
2
votes
3answers
45 views

Explain “There is a unique function from $\emptyset$ to any set $A$”.

My book says: There is a unique function from $\emptyset$ to any set $A$. I don't understand how that is. Let $A=\{1,2,3\}$. Which element of $A$ do we map $\emptyset$ to? Do we map $\emptyset$ ...
0
votes
0answers
24 views

Bijective function with different domain and co-domain element count

To be bijective is to be both injective and surjective. Which in other words, have to have a one-on-one match right? Then how am I supposed to come up with a bijective function if the domain has a ...
0
votes
0answers
34 views

Proving equality with finite and pairwise disjoints

I'm having some problems proving this. Let $A_1,A_2,.....A_n$ be finite and pairwise disjoints. So any two sets are disjoint. How do we prove that $$|A_1 ∪ A_2 ∪ ....A_n| = |A_1|+|A_2|+....|A_n|$$
0
votes
0answers
27 views

some basic concepts on algebra / measure theory

I'm reading a book in Chinese on measure theory (Introduction on Measure Theory, by Yan Jia-an). In the beginning there are some algebra concepts defined that I'd like to confirm the exact meaning and ...
0
votes
1answer
27 views

prove that if A is a subset of B, B is a subset of C, and C is a subset of A, then A=B and B=C

To prove A=B, I must prove that A is a subset of B and B is a subset of A. A is a subset of B is already given. So all that is left is to prove B is a subset of A. Is it suffice to say that since A ...
-1
votes
0answers
34 views

Uncountably infinite: the set of all infinite binary strings [duplicate]

Given that $S=\{0,1\}^{ \mathbb{N} } $ is the set of all infinite binary strings. Is it possible to find a bijective function $f:S\rightarrow \mathcal P(\mathbb N)$? Thank you.
1
vote
3answers
42 views

Prove that $\{(a,b):a,b\in\mathbb N, a\geq b\}$ is denumerable.

If $S=\{(a,b):a,b\in\mathbb N, a\geq b\}$, how do I prove that $S$ is denumerable? Work: Since $S \subseteq\mathbb{N\times N}$ I know that $S$ is denumerable. But I don't know how to structure the ...